JumpThreading.cpp revision f9065a904fca1018d6ea3e1536b9b3368c084725 
1//===- JumpThreading.cpp - Thread control through conditional blocks ------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the Jump Threading pass.
11//
12//===----------------------------------------------------------------------===//
13
14#define DEBUG_TYPE "jump-threading"
15#include "llvm/Transforms/Scalar.h"
16#include "llvm/IntrinsicInst.h"
17#include "llvm/Pass.h"
18#include "llvm/ADT/Statistic.h"
19#include "llvm/Support/CommandLine.h"
20#include "llvm/Support/Compiler.h"
21#include "llvm/Support/Debug.h"
22using namespace llvm;
23
24//STATISTIC(NumThreads, "Number of jumps threaded");
25
26static cl::opt<unsigned>
27Threshold("jump-threading-threshold",
28          cl::desc("Max block size to duplicate for jump threading"),
29          cl::init(6), cl::Hidden);
30
31namespace {
32  /// This pass performs 'jump threading', which looks at blocks that have
33  /// multiple predecessors and multiple successors.  If one or more of the
34  /// predecessors of the block can be proven to always jump to one of the
35  /// successors, we forward the edge from the predecessor to the successor by
36  /// duplicating the contents of this block.
37  ///
38  /// An example of when this can occur is code like this:
39  ///
40  ///   if () { ...
41  ///     X = 4;
42  ///   }
43  ///   if (X < 3) {
44  ///
45  /// In this case, the unconditional branch at the end of the first if can be
46  /// revectored to the false side of the second if.
47  ///
48  class VISIBILITY_HIDDEN JumpThreading : public FunctionPass {
49  public:
50    static char ID; // Pass identification
51    JumpThreading() : FunctionPass((intptr_t)&ID) {}
52
53    bool runOnFunction(Function &F);
54    bool ThreadBlock(BasicBlock &BB);
55  };
56  char JumpThreading::ID = 0;
57  RegisterPass<JumpThreading> X("jump-threading", "Jump Threading");
58}
59
60// Public interface to the Jump Threading pass
61FunctionPass *llvm::createJumpThreadingPass() { return new JumpThreading(); }
62
63/// runOnFunction - Top level algorithm.
64///
65bool JumpThreading::runOnFunction(Function &F) {
66  DOUT << "Jump threading on function '" << F.getNameStart() << "'\n";
67  bool Changed = false;
68  for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
69    Changed |= ThreadBlock(*I);
70  return Changed;
71}
72
73/// getJumpThreadDuplicationCost - Return the cost of duplicating this block to
74/// thread across it.
75static unsigned getJumpThreadDuplicationCost(const BasicBlock &BB) {
76  BasicBlock::const_iterator I = BB.begin();
77  /// Ignore PHI nodes, these will be flattened when duplication happens.
78  while (isa<PHINode>(*I)) ++I;
79
80  // Sum up the cost of each instruction until we get to the terminator.  Don't
81  // include the terminator because the copy won't include it.
82  unsigned Size = 0;
83  for (; !isa<TerminatorInst>(I); ++I) {
84    // Debugger intrinsics don't incur code size.
85    if (isa<DbgInfoIntrinsic>(I)) continue;
86
87    // If this is a pointer->pointer bitcast, it is free.
88    if (isa<BitCastInst>(I) && isa<PointerType>(I->getType()))
89      continue;
90
91    // All other instructions count for at least one unit.
92    ++Size;
93
94    // Calls are more expensive.  If they are non-intrinsic calls, we model them
95    // as having cost of 4.  If they are a non-vector intrinsic, we model them
96    // as having cost of 2 total, and if they are a vector intrinsic, we model
97    // them as having cost 1.
98    if (const CallInst *CI = dyn_cast<CallInst>(I)) {
99      if (!isa<IntrinsicInst>(CI))
100        Size += 3;
101      else if (isa<VectorType>(CI->getType()))
102        Size += 1;
103    }
104  }
105
106  // Threading through a switch statement is particularly profitable.  If this
107  // block ends in a switch, decrease its cost to make it more likely to happen.
108  if (isa<SwitchInst>(I))
109    Size = Size > 6 ? Size-6 : 0;
110
111  return Size;
112}
113
114
115/// ThreadBlock - If there are any predecessors whose control can be threaded
116/// through to a successor, transform them now.
117bool JumpThreading::ThreadBlock(BasicBlock &BB) {
118  // If there is only one predecessor or successor, then there is nothing to do.
119  if (BB.getTerminator()->getNumSuccessors() == 1 || BB.getSinglePredecessor())
120    return false;
121
122  // See if this block ends with a branch of switch.  If so, see if the
123  // condition is a phi node.  If so, and if an entry of the phi node is a
124  // constant, we can thread the block.
125  Value *Condition;
126  if (BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator()))
127    Condition = BI->getCondition();
128  else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB.getTerminator()))
129    Condition = SI->getCondition();
130  else
131    return false; // Must be an invoke.
132
133  // See if this is a phi node in the current block.
134  PHINode *PN = dyn_cast<PHINode>(Condition);
135  if (!PN || PN->getParent() != &BB) return false;
136
137  // See if the phi node has any constant values.  If so, we can determine where
138  // the corresponding predecessor will branch.
139  unsigned PredNo = ~0U;
140  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
141    if (isa<ConstantInt>(PN->getIncomingValue(i))) {
142      PredNo = i;
143      break;
144    }
145  }
146
147  // If no incoming value has a constant, we don't know the destination of any
148  // predecessors.
149  if (PredNo == ~0U)
150    return false;
151
152  // See if the cost of duplicating this block is low enough.
153  unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
154  if (JumpThreadCost > Threshold) {
155    DOUT << "  Not threading BB '" << BB.getNameStart()
156         << "' - Cost is too high: " << JumpThreadCost << "\n";
157    return false;
158  }
159
160  DOUT << "  Threading BB '" << BB.getNameStart() << "'.  Cost is: "
161       << JumpThreadCost << "\n";
162
163  return false;
164}
165