1 //===- JumpThreading.cpp - Thread control through conditional blocks ------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the Jump Threading pass.
12 //===----------------------------------------------------------------------===//
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/DenseMap.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
21 #include "llvm/Transforms/Utils/Local.h"
22 #include "llvm/Support/CommandLine.h"
23 #include "llvm/Support/Compiler.h"
24 #include "llvm/Support/Debug.h"
27 STATISTIC(NumThreads, "Number of jumps threaded");
28 STATISTIC(NumFolds, "Number of terminators folded");
30 static cl::opt<unsigned>
31 Threshold("jump-threading-threshold",
32 cl::desc("Max block size to duplicate for jump threading"),
33 cl::init(6), cl::Hidden);
36 /// This pass performs 'jump threading', which looks at blocks that have
37 /// multiple predecessors and multiple successors. If one or more of the
38 /// predecessors of the block can be proven to always jump to one of the
39 /// successors, we forward the edge from the predecessor to the successor by
40 /// duplicating the contents of this block.
42 /// An example of when this can occur is code like this:
49 /// In this case, the unconditional branch at the end of the first if can be
50 /// revectored to the false side of the second if.
52 class VISIBILITY_HIDDEN JumpThreading : public FunctionPass {
54 static char ID; // Pass identification
55 JumpThreading() : FunctionPass((intptr_t)&ID) {}
57 bool runOnFunction(Function &F);
58 bool ThreadBlock(BasicBlock *BB);
59 void ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, BasicBlock *SuccBB);
60 BasicBlock *FactorCommonPHIPreds(PHINode *PN, Constant *CstVal);
62 bool ProcessJumpOnPHI(PHINode *PN);
63 bool ProcessBranchOnLogical(Value *V, BasicBlock *BB, bool isAnd);
64 bool ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB);
68 char JumpThreading::ID = 0;
69 static RegisterPass<JumpThreading>
70 X("jump-threading", "Jump Threading");
72 // Public interface to the Jump Threading pass
73 FunctionPass *llvm::createJumpThreadingPass() { return new JumpThreading(); }
75 /// runOnFunction - Top level algorithm.
77 bool JumpThreading::runOnFunction(Function &F) {
78 DOUT << "Jump threading on function '" << F.getNameStart() << "'\n";
80 bool AnotherIteration = true, EverChanged = false;
81 while (AnotherIteration) {
82 AnotherIteration = false;
84 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
85 while (ThreadBlock(I))
87 AnotherIteration = Changed;
88 EverChanged |= Changed;
93 /// FactorCommonPHIPreds - If there are multiple preds with the same incoming
94 /// value for the PHI, factor them together so we get one block to thread for
96 /// This is important for things like "phi i1 [true, true, false, true, x]"
97 /// where we only need to clone the block for the true blocks once.
99 BasicBlock *JumpThreading::FactorCommonPHIPreds(PHINode *PN, Constant *CstVal) {
100 SmallVector<BasicBlock*, 16> CommonPreds;
101 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
102 if (PN->getIncomingValue(i) == CstVal)
103 CommonPreds.push_back(PN->getIncomingBlock(i));
105 if (CommonPreds.size() == 1)
106 return CommonPreds[0];
108 DOUT << " Factoring out " << CommonPreds.size()
109 << " common predecessors.\n";
110 return SplitBlockPredecessors(PN->getParent(),
111 &CommonPreds[0], CommonPreds.size(),
116 /// getJumpThreadDuplicationCost - Return the cost of duplicating this block to
117 /// thread across it.
118 static unsigned getJumpThreadDuplicationCost(const BasicBlock *BB) {
119 BasicBlock::const_iterator I = BB->begin();
120 /// Ignore PHI nodes, these will be flattened when duplication happens.
121 while (isa<PHINode>(*I)) ++I;
123 // Sum up the cost of each instruction until we get to the terminator. Don't
124 // include the terminator because the copy won't include it.
126 for (; !isa<TerminatorInst>(I); ++I) {
127 // Debugger intrinsics don't incur code size.
128 if (isa<DbgInfoIntrinsic>(I)) continue;
130 // If this is a pointer->pointer bitcast, it is free.
131 if (isa<BitCastInst>(I) && isa<PointerType>(I->getType()))
134 // All other instructions count for at least one unit.
137 // Calls are more expensive. If they are non-intrinsic calls, we model them
138 // as having cost of 4. If they are a non-vector intrinsic, we model them
139 // as having cost of 2 total, and if they are a vector intrinsic, we model
140 // them as having cost 1.
141 if (const CallInst *CI = dyn_cast<CallInst>(I)) {
142 if (!isa<IntrinsicInst>(CI))
144 else if (isa<VectorType>(CI->getType()))
149 // Threading through a switch statement is particularly profitable. If this
150 // block ends in a switch, decrease its cost to make it more likely to happen.
151 if (isa<SwitchInst>(I))
152 Size = Size > 6 ? Size-6 : 0;
158 /// ThreadBlock - If there are any predecessors whose control can be threaded
159 /// through to a successor, transform them now.
160 bool JumpThreading::ThreadBlock(BasicBlock *BB) {
161 // See if this block ends with a branch or switch. If so, see if the
162 // condition is a phi node. If so, and if an entry of the phi node is a
163 // constant, we can thread the block.
165 if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
166 // Can't thread an unconditional jump.
167 if (BI->isUnconditional()) return false;
168 Condition = BI->getCondition();
169 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator()))
170 Condition = SI->getCondition();
172 return false; // Must be an invoke.
174 // If the terminator of this block is branching on a constant, simplify the
175 // terminator to an unconditional branch. This can occur due to threading in
177 if (isa<ConstantInt>(Condition)) {
178 DOUT << " In block '" << BB->getNameStart()
179 << "' folding terminator: " << *BB->getTerminator();
181 ConstantFoldTerminator(BB);
185 // If there is only a single predecessor of this block, nothing to fold.
186 if (BB->getSinglePredecessor())
189 // See if this is a phi node in the current block.
190 PHINode *PN = dyn_cast<PHINode>(Condition);
191 if (PN && PN->getParent() == BB)
192 return ProcessJumpOnPHI(PN);
194 // If this is a conditional branch whose condition is and/or of a phi, try to
196 if (BinaryOperator *CondI = dyn_cast<BinaryOperator>(Condition)) {
197 if ((CondI->getOpcode() == Instruction::And ||
198 CondI->getOpcode() == Instruction::Or) &&
199 isa<BranchInst>(BB->getTerminator()) &&
200 ProcessBranchOnLogical(CondI, BB,
201 CondI->getOpcode() == Instruction::And))
205 // If we have "br (phi != 42)" and the phi node has any constant values as
206 // operands, we can thread through this block.
207 if (CmpInst *CondCmp = dyn_cast<CmpInst>(Condition))
208 if (isa<PHINode>(CondCmp->getOperand(0)) &&
209 isa<Constant>(CondCmp->getOperand(1)) &&
210 ProcessBranchOnCompare(CondCmp, BB))
216 /// ProcessJumpOnPHI - We have a conditional branch of switch on a PHI node in
217 /// the current block. See if there are any simplifications we can do based on
218 /// inputs to the phi node.
220 bool JumpThreading::ProcessJumpOnPHI(PHINode *PN) {
221 // See if the phi node has any constant values. If so, we can determine where
222 // the corresponding predecessor will branch.
223 ConstantInt *PredCst = 0;
224 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
225 if ((PredCst = dyn_cast<ConstantInt>(PN->getIncomingValue(i))))
228 // If no incoming value has a constant, we don't know the destination of any
233 // See if the cost of duplicating this block is low enough.
234 BasicBlock *BB = PN->getParent();
235 unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
236 if (JumpThreadCost > Threshold) {
237 DOUT << " Not threading BB '" << BB->getNameStart()
238 << "' - Cost is too high: " << JumpThreadCost << "\n";
242 // If so, we can actually do this threading. Merge any common predecessors
243 // that will act the same.
244 BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst);
246 // Next, figure out which successor we are threading to.
248 if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()))
249 SuccBB = BI->getSuccessor(PredCst == ConstantInt::getFalse());
251 SwitchInst *SI = cast<SwitchInst>(BB->getTerminator());
252 SuccBB = SI->getSuccessor(SI->findCaseValue(PredCst));
255 // If threading to the same block as we come from, we would infinite loop.
257 DOUT << " Not threading BB '" << BB->getNameStart()
258 << "' - would thread to self!\n";
262 // And finally, do it!
263 DOUT << " Threading edge from '" << PredBB->getNameStart() << "' to '"
264 << SuccBB->getNameStart() << "' with cost: " << JumpThreadCost
265 << ", across block:\n "
268 ThreadEdge(BB, PredBB, SuccBB);
273 /// ProcessJumpOnLogicalPHI - PN's basic block contains a conditional branch
274 /// whose condition is an AND/OR where one side is PN. If PN has constant
275 /// operands that permit us to evaluate the condition for some operand, thread
276 /// through the block. For example with:
277 /// br (and X, phi(Y, Z, false))
278 /// the predecessor corresponding to the 'false' will always jump to the false
279 /// destination of the branch.
281 bool JumpThreading::ProcessBranchOnLogical(Value *V, BasicBlock *BB,
283 // If this is a binary operator tree of the same AND/OR opcode, check the
285 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V))
286 if (isAnd && BO->getOpcode() == Instruction::And ||
287 !isAnd && BO->getOpcode() == Instruction::Or) {
288 if (ProcessBranchOnLogical(BO->getOperand(0), BB, isAnd))
290 if (ProcessBranchOnLogical(BO->getOperand(1), BB, isAnd))
294 // If this isn't a PHI node, we can't handle it.
295 PHINode *PN = dyn_cast<PHINode>(V);
296 if (!PN || PN->getParent() != BB) return false;
298 // We can only do the simplification for phi nodes of 'false' with AND or
299 // 'true' with OR. See if we have any entries in the phi for this.
300 unsigned PredNo = ~0U;
301 ConstantInt *PredCst = ConstantInt::get(Type::Int1Ty, !isAnd);
302 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
303 if (PN->getIncomingValue(i) == PredCst) {
309 // If no match, bail out.
313 // See if the cost of duplicating this block is low enough.
314 unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
315 if (JumpThreadCost > Threshold) {
316 DOUT << " Not threading BB '" << BB->getNameStart()
317 << "' - Cost is too high: " << JumpThreadCost << "\n";
321 // If so, we can actually do this threading. Merge any common predecessors
322 // that will act the same.
323 BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst);
325 // Next, figure out which successor we are threading to. If this was an AND,
326 // the constant must be FALSE, and we must be targeting the 'false' block.
327 // If this is an OR, the constant must be TRUE, and we must be targeting the
329 BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(isAnd);
331 // If threading to the same block as we come from, we would infinite loop.
333 DOUT << " Not threading BB '" << BB->getNameStart()
334 << "' - would thread to self!\n";
338 // And finally, do it!
339 DOUT << " Threading edge through bool from '" << PredBB->getNameStart()
340 << "' to '" << SuccBB->getNameStart() << "' with cost: "
341 << JumpThreadCost << ", across block:\n "
344 ThreadEdge(BB, PredBB, SuccBB);
349 /// ProcessBranchOnCompare - We found a branch on a comparison between a phi
350 /// node and a constant. If the PHI node contains any constants as inputs, we
351 /// can fold the compare for that edge and thread through it.
352 bool JumpThreading::ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB) {
353 PHINode *PN = cast<PHINode>(Cmp->getOperand(0));
354 Constant *RHS = cast<Constant>(Cmp->getOperand(1));
356 // If the phi isn't in the current block, an incoming edge to this block
357 // doesn't control the destination.
358 if (PN->getParent() != BB)
361 // We can do this simplification if any comparisons fold to true or false.
363 Constant *PredCst = 0;
364 bool TrueDirection = false;
365 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
366 PredCst = dyn_cast<Constant>(PN->getIncomingValue(i));
367 if (PredCst == 0) continue;
370 if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cmp))
371 Res = ConstantExpr::getICmp(ICI->getPredicate(), PredCst, RHS);
373 Res = ConstantExpr::getFCmp(cast<FCmpInst>(Cmp)->getPredicate(),
375 // If this folded to a constant expr, we can't do anything.
376 if (ConstantInt *ResC = dyn_cast<ConstantInt>(Res)) {
377 TrueDirection = ResC->getZExtValue();
380 // If this folded to undef, just go the false way.
381 if (isa<UndefValue>(Res)) {
382 TrueDirection = false;
386 // Otherwise, we can't fold this input.
390 // If no match, bail out.
394 // See if the cost of duplicating this block is low enough.
395 unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
396 if (JumpThreadCost > Threshold) {
397 DOUT << " Not threading BB '" << BB->getNameStart()
398 << "' - Cost is too high: " << JumpThreadCost << "\n";
402 // If so, we can actually do this threading. Merge any common predecessors
403 // that will act the same.
404 BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst);
406 // Next, get our successor.
407 BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(!TrueDirection);
409 // If threading to the same block as we come from, we would infinite loop.
411 DOUT << " Not threading BB '" << BB->getNameStart()
412 << "' - would thread to self!\n";
417 // And finally, do it!
418 DOUT << " Threading edge through bool from '" << PredBB->getNameStart()
419 << "' to '" << SuccBB->getNameStart() << "' with cost: "
420 << JumpThreadCost << ", across block:\n "
423 ThreadEdge(BB, PredBB, SuccBB);
429 /// ThreadEdge - We have decided that it is safe and profitable to thread an
430 /// edge from PredBB to SuccBB across BB. Transform the IR to reflect this
432 void JumpThreading::ThreadEdge(BasicBlock *BB, BasicBlock *PredBB,
433 BasicBlock *SuccBB) {
435 // Jump Threading can not update SSA properties correctly if the values
436 // defined in the duplicated block are used outside of the block itself. For
437 // this reason, we spill all values that are used outside of BB to the stack.
438 for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
439 if (!I->isUsedOutsideOfBlock(BB))
442 // We found a use of I outside of BB. Create a new stack slot to
443 // break this inter-block usage pattern.
444 if (!isa<StructType>(I->getType())) {
445 DemoteRegToStack(*I);
449 // Alternatively, I must be a call or invoke that returns multiple retvals.
450 // We can't use 'DemoteRegToStack' because that will create loads and
451 // stores of aggregates which is not valid yet. If I is a call, we can just
452 // pull all the getresult instructions up to this block. If I is an invoke,
453 // we are out of luck.
454 BasicBlock::iterator IP = I; ++IP;
455 for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
457 cast<GetResultInst>(UI)->moveBefore(IP);
460 // We are going to have to map operands from the original BB block to the new
461 // copy of the block 'NewBB'. If there are PHI nodes in BB, evaluate them to
462 // account for entry from PredBB.
463 DenseMap<Instruction*, Value*> ValueMapping;
466 BasicBlock::Create(BB->getName()+".thread", BB->getParent(), BB);
467 NewBB->moveAfter(PredBB);
469 BasicBlock::iterator BI = BB->begin();
470 for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
471 ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB);
473 // Clone the non-phi instructions of BB into NewBB, keeping track of the
474 // mapping and using it to remap operands in the cloned instructions.
475 for (; !isa<TerminatorInst>(BI); ++BI) {
476 Instruction *New = BI->clone();
477 New->setName(BI->getNameStart());
478 NewBB->getInstList().push_back(New);
479 ValueMapping[BI] = New;
481 // Remap operands to patch up intra-block references.
482 for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
483 if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i)))
484 if (Value *Remapped = ValueMapping[Inst])
485 New->setOperand(i, Remapped);
488 // We didn't copy the terminator from BB over to NewBB, because there is now
489 // an unconditional jump to SuccBB. Insert the unconditional jump.
490 BranchInst::Create(SuccBB, NewBB);
492 // Check to see if SuccBB has PHI nodes. If so, we need to add entries to the
493 // PHI nodes for NewBB now.
494 for (BasicBlock::iterator PNI = SuccBB->begin(); isa<PHINode>(PNI); ++PNI) {
495 PHINode *PN = cast<PHINode>(PNI);
496 // Ok, we have a PHI node. Figure out what the incoming value was for the
498 Value *IV = PN->getIncomingValueForBlock(BB);
500 // Remap the value if necessary.
501 if (Instruction *Inst = dyn_cast<Instruction>(IV))
502 if (Value *MappedIV = ValueMapping[Inst])
504 PN->addIncoming(IV, NewBB);
507 // Finally, NewBB is good to go. Update the terminator of PredBB to jump to
508 // NewBB instead of BB. This eliminates predecessors from BB, which requires
509 // us to simplify any PHI nodes in BB.
510 TerminatorInst *PredTerm = PredBB->getTerminator();
511 for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
512 if (PredTerm->getSuccessor(i) == BB) {
513 BB->removePredecessor(PredBB);
514 PredTerm->setSuccessor(i, NewBB);