Chris Lattner | 8383a7b | 2008-04-20 20:35:01 +0000 | [diff] [blame] | 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 | // |
Chris Lattner | 177480b | 2008-04-20 21:13:06 +0000 | [diff] [blame] | 10 | // This file implements the Jump Threading pass. |
Chris Lattner | 8383a7b | 2008-04-20 20:35:01 +0000 | [diff] [blame] | 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #define DEBUG_TYPE "jump-threading" |
| 15 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | 177480b | 2008-04-20 21:13:06 +0000 | [diff] [blame] | 16 | #include "llvm/IntrinsicInst.h" |
Chris Lattner | 8383a7b | 2008-04-20 20:35:01 +0000 | [diff] [blame] | 17 | #include "llvm/Pass.h" |
Chris Lattner | bd3401f | 2008-04-20 22:39:42 +0000 | [diff] [blame] | 18 | #include "llvm/ADT/DenseMap.h" |
Chris Lattner | 8383a7b | 2008-04-20 20:35:01 +0000 | [diff] [blame] | 19 | #include "llvm/ADT/Statistic.h" |
Chris Lattner | 2cc6751 | 2008-04-21 02:57:57 +0000 | [diff] [blame] | 20 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
Chris Lattner | bd3401f | 2008-04-20 22:39:42 +0000 | [diff] [blame] | 21 | #include "llvm/Transforms/Utils/Local.h" |
Chris Lattner | 8383a7b | 2008-04-20 20:35:01 +0000 | [diff] [blame] | 22 | #include "llvm/Support/CommandLine.h" |
| 23 | #include "llvm/Support/Compiler.h" |
Chris Lattner | 177480b | 2008-04-20 21:13:06 +0000 | [diff] [blame] | 24 | #include "llvm/Support/Debug.h" |
Chris Lattner | 8383a7b | 2008-04-20 20:35:01 +0000 | [diff] [blame] | 25 | using namespace llvm; |
| 26 | |
Chris Lattner | bd3401f | 2008-04-20 22:39:42 +0000 | [diff] [blame] | 27 | STATISTIC(NumThreads, "Number of jumps threaded"); |
| 28 | STATISTIC(NumFolds, "Number of terminators folded"); |
Chris Lattner | 8383a7b | 2008-04-20 20:35:01 +0000 | [diff] [blame] | 29 | |
Chris Lattner | 177480b | 2008-04-20 21:13:06 +0000 | [diff] [blame] | 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); |
| 34 | |
Chris Lattner | 8383a7b | 2008-04-20 20:35:01 +0000 | [diff] [blame] | 35 | namespace { |
Chris Lattner | 94019f8 | 2008-05-09 04:43:13 +0000 | [diff] [blame] | 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. |
| 41 | /// |
| 42 | /// An example of when this can occur is code like this: |
| 43 | /// |
| 44 | /// if () { ... |
| 45 | /// X = 4; |
| 46 | /// } |
| 47 | /// if (X < 3) { |
| 48 | /// |
| 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. |
| 51 | /// |
Chris Lattner | 8383a7b | 2008-04-20 20:35:01 +0000 | [diff] [blame] | 52 | class VISIBILITY_HIDDEN JumpThreading : public FunctionPass { |
| 53 | public: |
| 54 | static char ID; // Pass identification |
| 55 | JumpThreading() : FunctionPass((intptr_t)&ID) {} |
| 56 | |
| 57 | bool runOnFunction(Function &F); |
Chris Lattner | bd3401f | 2008-04-20 22:39:42 +0000 | [diff] [blame] | 58 | bool ThreadBlock(BasicBlock *BB); |
| 59 | void ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, BasicBlock *SuccBB); |
Chris Lattner | 6bf7750 | 2008-04-22 07:05:46 +0000 | [diff] [blame] | 60 | BasicBlock *FactorCommonPHIPreds(PHINode *PN, Constant *CstVal); |
| 61 | |
Chris Lattner | d38c14e | 2008-04-22 06:36:15 +0000 | [diff] [blame] | 62 | bool ProcessJumpOnPHI(PHINode *PN); |
Chris Lattner | ae65b3c | 2008-04-22 20:46:09 +0000 | [diff] [blame] | 63 | bool ProcessBranchOnLogical(Value *V, BasicBlock *BB, bool isAnd); |
Chris Lattner | a5ddb59 | 2008-04-22 21:40:39 +0000 | [diff] [blame] | 64 | bool ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB); |
Chris Lattner | 8383a7b | 2008-04-20 20:35:01 +0000 | [diff] [blame] | 65 | }; |
Chris Lattner | 8383a7b | 2008-04-20 20:35:01 +0000 | [diff] [blame] | 66 | } |
| 67 | |
Dan Gohman | 844731a | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 68 | char JumpThreading::ID = 0; |
| 69 | static RegisterPass<JumpThreading> |
| 70 | X("jump-threading", "Jump Threading"); |
| 71 | |
Chris Lattner | 8383a7b | 2008-04-20 20:35:01 +0000 | [diff] [blame] | 72 | // Public interface to the Jump Threading pass |
| 73 | FunctionPass *llvm::createJumpThreadingPass() { return new JumpThreading(); } |
| 74 | |
| 75 | /// runOnFunction - Top level algorithm. |
| 76 | /// |
| 77 | bool JumpThreading::runOnFunction(Function &F) { |
Chris Lattner | 177480b | 2008-04-20 21:13:06 +0000 | [diff] [blame] | 78 | DOUT << "Jump threading on function '" << F.getNameStart() << "'\n"; |
Chris Lattner | bd3401f | 2008-04-20 22:39:42 +0000 | [diff] [blame] | 79 | |
| 80 | bool AnotherIteration = true, EverChanged = false; |
| 81 | while (AnotherIteration) { |
| 82 | AnotherIteration = false; |
| 83 | bool Changed = false; |
| 84 | for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) |
| 85 | while (ThreadBlock(I)) |
| 86 | Changed = true; |
| 87 | AnotherIteration = Changed; |
| 88 | EverChanged |= Changed; |
| 89 | } |
| 90 | return EverChanged; |
Chris Lattner | 8383a7b | 2008-04-20 20:35:01 +0000 | [diff] [blame] | 91 | } |
Chris Lattner | 177480b | 2008-04-20 21:13:06 +0000 | [diff] [blame] | 92 | |
Chris Lattner | 6bf7750 | 2008-04-22 07:05:46 +0000 | [diff] [blame] | 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 |
| 95 | /// the whole group. |
| 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. |
| 98 | /// |
| 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)); |
| 104 | |
| 105 | if (CommonPreds.size() == 1) |
| 106 | return CommonPreds[0]; |
| 107 | |
| 108 | DOUT << " Factoring out " << CommonPreds.size() |
| 109 | << " common predecessors.\n"; |
| 110 | return SplitBlockPredecessors(PN->getParent(), |
| 111 | &CommonPreds[0], CommonPreds.size(), |
| 112 | ".thr_comm", this); |
| 113 | } |
| 114 | |
| 115 | |
Chris Lattner | 177480b | 2008-04-20 21:13:06 +0000 | [diff] [blame] | 116 | /// getJumpThreadDuplicationCost - Return the cost of duplicating this block to |
| 117 | /// thread across it. |
Chris Lattner | bd3401f | 2008-04-20 22:39:42 +0000 | [diff] [blame] | 118 | static unsigned getJumpThreadDuplicationCost(const BasicBlock *BB) { |
Chris Lattner | 177480b | 2008-04-20 21:13:06 +0000 | [diff] [blame] | 119 | /// Ignore PHI nodes, these will be flattened when duplication happens. |
Dan Gohman | 02dea8b | 2008-05-23 21:05:58 +0000 | [diff] [blame] | 120 | BasicBlock::const_iterator I = BB->getFirstNonPHI(); |
Chris Lattner | 177480b | 2008-04-20 21:13:06 +0000 | [diff] [blame] | 121 | |
| 122 | // Sum up the cost of each instruction until we get to the terminator. Don't |
| 123 | // include the terminator because the copy won't include it. |
| 124 | unsigned Size = 0; |
| 125 | for (; !isa<TerminatorInst>(I); ++I) { |
| 126 | // Debugger intrinsics don't incur code size. |
| 127 | if (isa<DbgInfoIntrinsic>(I)) continue; |
| 128 | |
| 129 | // If this is a pointer->pointer bitcast, it is free. |
| 130 | if (isa<BitCastInst>(I) && isa<PointerType>(I->getType())) |
| 131 | continue; |
| 132 | |
| 133 | // All other instructions count for at least one unit. |
| 134 | ++Size; |
| 135 | |
| 136 | // Calls are more expensive. If they are non-intrinsic calls, we model them |
| 137 | // as having cost of 4. If they are a non-vector intrinsic, we model them |
| 138 | // as having cost of 2 total, and if they are a vector intrinsic, we model |
| 139 | // them as having cost 1. |
| 140 | if (const CallInst *CI = dyn_cast<CallInst>(I)) { |
| 141 | if (!isa<IntrinsicInst>(CI)) |
| 142 | Size += 3; |
| 143 | else if (isa<VectorType>(CI->getType())) |
| 144 | Size += 1; |
| 145 | } |
| 146 | } |
| 147 | |
| 148 | // Threading through a switch statement is particularly profitable. If this |
| 149 | // block ends in a switch, decrease its cost to make it more likely to happen. |
| 150 | if (isa<SwitchInst>(I)) |
| 151 | Size = Size > 6 ? Size-6 : 0; |
| 152 | |
| 153 | return Size; |
| 154 | } |
| 155 | |
| 156 | |
| 157 | /// ThreadBlock - If there are any predecessors whose control can be threaded |
| 158 | /// through to a successor, transform them now. |
Chris Lattner | bd3401f | 2008-04-20 22:39:42 +0000 | [diff] [blame] | 159 | bool JumpThreading::ThreadBlock(BasicBlock *BB) { |
Matthijs Kooijman | 6e7b322 | 2008-05-20 07:26:45 +0000 | [diff] [blame] | 160 | // See if this block ends with a branch or switch. If so, see if the |
Chris Lattner | 177480b | 2008-04-20 21:13:06 +0000 | [diff] [blame] | 161 | // condition is a phi node. If so, and if an entry of the phi node is a |
| 162 | // constant, we can thread the block. |
| 163 | Value *Condition; |
Chris Lattner | bd3401f | 2008-04-20 22:39:42 +0000 | [diff] [blame] | 164 | if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { |
| 165 | // Can't thread an unconditional jump. |
| 166 | if (BI->isUnconditional()) return false; |
Chris Lattner | 177480b | 2008-04-20 21:13:06 +0000 | [diff] [blame] | 167 | Condition = BI->getCondition(); |
Chris Lattner | bd3401f | 2008-04-20 22:39:42 +0000 | [diff] [blame] | 168 | } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) |
Chris Lattner | 177480b | 2008-04-20 21:13:06 +0000 | [diff] [blame] | 169 | Condition = SI->getCondition(); |
| 170 | else |
| 171 | return false; // Must be an invoke. |
Chris Lattner | bd3401f | 2008-04-20 22:39:42 +0000 | [diff] [blame] | 172 | |
| 173 | // If the terminator of this block is branching on a constant, simplify the |
Chris Lattner | 037c781 | 2008-04-21 18:25:01 +0000 | [diff] [blame] | 174 | // terminator to an unconditional branch. This can occur due to threading in |
Chris Lattner | bd3401f | 2008-04-20 22:39:42 +0000 | [diff] [blame] | 175 | // other blocks. |
| 176 | if (isa<ConstantInt>(Condition)) { |
| 177 | DOUT << " In block '" << BB->getNameStart() |
| 178 | << "' folding terminator: " << *BB->getTerminator(); |
| 179 | ++NumFolds; |
| 180 | ConstantFoldTerminator(BB); |
| 181 | return true; |
| 182 | } |
| 183 | |
| 184 | // If there is only a single predecessor of this block, nothing to fold. |
| 185 | if (BB->getSinglePredecessor()) |
| 186 | return false; |
Chris Lattner | 177480b | 2008-04-20 21:13:06 +0000 | [diff] [blame] | 187 | |
| 188 | // See if this is a phi node in the current block. |
| 189 | PHINode *PN = dyn_cast<PHINode>(Condition); |
Chris Lattner | d38c14e | 2008-04-22 06:36:15 +0000 | [diff] [blame] | 190 | if (PN && PN->getParent() == BB) |
| 191 | return ProcessJumpOnPHI(PN); |
Chris Lattner | 177480b | 2008-04-20 21:13:06 +0000 | [diff] [blame] | 192 | |
Chris Lattner | 6bf7750 | 2008-04-22 07:05:46 +0000 | [diff] [blame] | 193 | // If this is a conditional branch whose condition is and/or of a phi, try to |
| 194 | // simplify it. |
| 195 | if (BinaryOperator *CondI = dyn_cast<BinaryOperator>(Condition)) { |
| 196 | if ((CondI->getOpcode() == Instruction::And || |
| 197 | CondI->getOpcode() == Instruction::Or) && |
Chris Lattner | ae65b3c | 2008-04-22 20:46:09 +0000 | [diff] [blame] | 198 | isa<BranchInst>(BB->getTerminator()) && |
| 199 | ProcessBranchOnLogical(CondI, BB, |
| 200 | CondI->getOpcode() == Instruction::And)) |
| 201 | return true; |
Chris Lattner | 6bf7750 | 2008-04-22 07:05:46 +0000 | [diff] [blame] | 202 | } |
| 203 | |
Chris Lattner | a5ddb59 | 2008-04-22 21:40:39 +0000 | [diff] [blame] | 204 | // If we have "br (phi != 42)" and the phi node has any constant values as |
| 205 | // operands, we can thread through this block. |
| 206 | if (CmpInst *CondCmp = dyn_cast<CmpInst>(Condition)) |
| 207 | if (isa<PHINode>(CondCmp->getOperand(0)) && |
| 208 | isa<Constant>(CondCmp->getOperand(1)) && |
| 209 | ProcessBranchOnCompare(CondCmp, BB)) |
| 210 | return true; |
| 211 | |
Chris Lattner | d38c14e | 2008-04-22 06:36:15 +0000 | [diff] [blame] | 212 | return false; |
| 213 | } |
| 214 | |
| 215 | /// ProcessJumpOnPHI - We have a conditional branch of switch on a PHI node in |
| 216 | /// the current block. See if there are any simplifications we can do based on |
| 217 | /// inputs to the phi node. |
| 218 | /// |
| 219 | bool JumpThreading::ProcessJumpOnPHI(PHINode *PN) { |
Chris Lattner | f9065a9 | 2008-04-20 21:18:09 +0000 | [diff] [blame] | 220 | // See if the phi node has any constant values. If so, we can determine where |
| 221 | // the corresponding predecessor will branch. |
Chris Lattner | bd3401f | 2008-04-20 22:39:42 +0000 | [diff] [blame] | 222 | ConstantInt *PredCst = 0; |
Chris Lattner | a5ddb59 | 2008-04-22 21:40:39 +0000 | [diff] [blame] | 223 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) |
| 224 | if ((PredCst = dyn_cast<ConstantInt>(PN->getIncomingValue(i)))) |
Chris Lattner | f9065a9 | 2008-04-20 21:18:09 +0000 | [diff] [blame] | 225 | break; |
Chris Lattner | f9065a9 | 2008-04-20 21:18:09 +0000 | [diff] [blame] | 226 | |
| 227 | // If no incoming value has a constant, we don't know the destination of any |
| 228 | // predecessors. |
Chris Lattner | a5ddb59 | 2008-04-22 21:40:39 +0000 | [diff] [blame] | 229 | if (PredCst == 0) |
Chris Lattner | f9065a9 | 2008-04-20 21:18:09 +0000 | [diff] [blame] | 230 | return false; |
| 231 | |
Chris Lattner | 177480b | 2008-04-20 21:13:06 +0000 | [diff] [blame] | 232 | // See if the cost of duplicating this block is low enough. |
Chris Lattner | d38c14e | 2008-04-22 06:36:15 +0000 | [diff] [blame] | 233 | BasicBlock *BB = PN->getParent(); |
Chris Lattner | 177480b | 2008-04-20 21:13:06 +0000 | [diff] [blame] | 234 | unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB); |
| 235 | if (JumpThreadCost > Threshold) { |
Chris Lattner | bd3401f | 2008-04-20 22:39:42 +0000 | [diff] [blame] | 236 | DOUT << " Not threading BB '" << BB->getNameStart() |
Chris Lattner | f9065a9 | 2008-04-20 21:18:09 +0000 | [diff] [blame] | 237 | << "' - Cost is too high: " << JumpThreadCost << "\n"; |
Chris Lattner | 177480b | 2008-04-20 21:13:06 +0000 | [diff] [blame] | 238 | return false; |
| 239 | } |
Chris Lattner | 177480b | 2008-04-20 21:13:06 +0000 | [diff] [blame] | 240 | |
Chris Lattner | 6bf7750 | 2008-04-22 07:05:46 +0000 | [diff] [blame] | 241 | // If so, we can actually do this threading. Merge any common predecessors |
| 242 | // that will act the same. |
| 243 | BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst); |
| 244 | |
| 245 | // Next, figure out which successor we are threading to. |
Chris Lattner | bd3401f | 2008-04-20 22:39:42 +0000 | [diff] [blame] | 246 | BasicBlock *SuccBB; |
| 247 | if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) |
| 248 | SuccBB = BI->getSuccessor(PredCst == ConstantInt::getFalse()); |
| 249 | else { |
| 250 | SwitchInst *SI = cast<SwitchInst>(BB->getTerminator()); |
| 251 | SuccBB = SI->getSuccessor(SI->findCaseValue(PredCst)); |
| 252 | } |
| 253 | |
Chris Lattner | eede65c | 2008-04-25 04:12:29 +0000 | [diff] [blame] | 254 | // If threading to the same block as we come from, we would infinite loop. |
| 255 | if (SuccBB == BB) { |
| 256 | DOUT << " Not threading BB '" << BB->getNameStart() |
| 257 | << "' - would thread to self!\n"; |
| 258 | return false; |
| 259 | } |
| 260 | |
Chris Lattner | 6bf7750 | 2008-04-22 07:05:46 +0000 | [diff] [blame] | 261 | // And finally, do it! |
Chris Lattner | bd3401f | 2008-04-20 22:39:42 +0000 | [diff] [blame] | 262 | DOUT << " Threading edge from '" << PredBB->getNameStart() << "' to '" |
| 263 | << SuccBB->getNameStart() << "' with cost: " << JumpThreadCost |
| 264 | << ", across block:\n " |
Chris Lattner | 6bf7750 | 2008-04-22 07:05:46 +0000 | [diff] [blame] | 265 | << *BB << "\n"; |
Chris Lattner | bd3401f | 2008-04-20 22:39:42 +0000 | [diff] [blame] | 266 | |
| 267 | ThreadEdge(BB, PredBB, SuccBB); |
| 268 | ++NumThreads; |
| 269 | return true; |
| 270 | } |
| 271 | |
Chris Lattner | 6bf7750 | 2008-04-22 07:05:46 +0000 | [diff] [blame] | 272 | /// ProcessJumpOnLogicalPHI - PN's basic block contains a conditional branch |
| 273 | /// whose condition is an AND/OR where one side is PN. If PN has constant |
| 274 | /// operands that permit us to evaluate the condition for some operand, thread |
| 275 | /// through the block. For example with: |
| 276 | /// br (and X, phi(Y, Z, false)) |
| 277 | /// the predecessor corresponding to the 'false' will always jump to the false |
| 278 | /// destination of the branch. |
| 279 | /// |
Chris Lattner | ae65b3c | 2008-04-22 20:46:09 +0000 | [diff] [blame] | 280 | bool JumpThreading::ProcessBranchOnLogical(Value *V, BasicBlock *BB, |
| 281 | bool isAnd) { |
| 282 | // If this is a binary operator tree of the same AND/OR opcode, check the |
| 283 | // LHS/RHS. |
| 284 | if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V)) |
Duncan Sands | 43e2a03 | 2008-05-27 11:50:51 +0000 | [diff] [blame^] | 285 | if ((isAnd && BO->getOpcode() == Instruction::And) || |
| 286 | (!isAnd && BO->getOpcode() == Instruction::Or)) { |
Chris Lattner | ae65b3c | 2008-04-22 20:46:09 +0000 | [diff] [blame] | 287 | if (ProcessBranchOnLogical(BO->getOperand(0), BB, isAnd)) |
| 288 | return true; |
| 289 | if (ProcessBranchOnLogical(BO->getOperand(1), BB, isAnd)) |
| 290 | return true; |
| 291 | } |
| 292 | |
| 293 | // If this isn't a PHI node, we can't handle it. |
| 294 | PHINode *PN = dyn_cast<PHINode>(V); |
| 295 | if (!PN || PN->getParent() != BB) return false; |
| 296 | |
Chris Lattner | 6bf7750 | 2008-04-22 07:05:46 +0000 | [diff] [blame] | 297 | // We can only do the simplification for phi nodes of 'false' with AND or |
| 298 | // 'true' with OR. See if we have any entries in the phi for this. |
| 299 | unsigned PredNo = ~0U; |
| 300 | ConstantInt *PredCst = ConstantInt::get(Type::Int1Ty, !isAnd); |
| 301 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { |
| 302 | if (PN->getIncomingValue(i) == PredCst) { |
| 303 | PredNo = i; |
| 304 | break; |
| 305 | } |
| 306 | } |
| 307 | |
| 308 | // If no match, bail out. |
| 309 | if (PredNo == ~0U) |
| 310 | return false; |
| 311 | |
| 312 | // See if the cost of duplicating this block is low enough. |
Chris Lattner | 6bf7750 | 2008-04-22 07:05:46 +0000 | [diff] [blame] | 313 | unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB); |
| 314 | if (JumpThreadCost > Threshold) { |
| 315 | DOUT << " Not threading BB '" << BB->getNameStart() |
| 316 | << "' - Cost is too high: " << JumpThreadCost << "\n"; |
| 317 | return false; |
| 318 | } |
| 319 | |
| 320 | // If so, we can actually do this threading. Merge any common predecessors |
| 321 | // that will act the same. |
| 322 | BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst); |
| 323 | |
| 324 | // Next, figure out which successor we are threading to. If this was an AND, |
| 325 | // the constant must be FALSE, and we must be targeting the 'false' block. |
| 326 | // If this is an OR, the constant must be TRUE, and we must be targeting the |
| 327 | // 'true' block. |
| 328 | BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(isAnd); |
| 329 | |
Chris Lattner | eede65c | 2008-04-25 04:12:29 +0000 | [diff] [blame] | 330 | // If threading to the same block as we come from, we would infinite loop. |
| 331 | if (SuccBB == BB) { |
| 332 | DOUT << " Not threading BB '" << BB->getNameStart() |
| 333 | << "' - would thread to self!\n"; |
| 334 | return false; |
| 335 | } |
| 336 | |
Chris Lattner | 6bf7750 | 2008-04-22 07:05:46 +0000 | [diff] [blame] | 337 | // And finally, do it! |
| 338 | DOUT << " Threading edge through bool from '" << PredBB->getNameStart() |
| 339 | << "' to '" << SuccBB->getNameStart() << "' with cost: " |
| 340 | << JumpThreadCost << ", across block:\n " |
| 341 | << *BB << "\n"; |
| 342 | |
| 343 | ThreadEdge(BB, PredBB, SuccBB); |
| 344 | ++NumThreads; |
| 345 | return true; |
| 346 | } |
| 347 | |
Chris Lattner | a5ddb59 | 2008-04-22 21:40:39 +0000 | [diff] [blame] | 348 | /// ProcessBranchOnCompare - We found a branch on a comparison between a phi |
| 349 | /// node and a constant. If the PHI node contains any constants as inputs, we |
| 350 | /// can fold the compare for that edge and thread through it. |
| 351 | bool JumpThreading::ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB) { |
| 352 | PHINode *PN = cast<PHINode>(Cmp->getOperand(0)); |
| 353 | Constant *RHS = cast<Constant>(Cmp->getOperand(1)); |
| 354 | |
| 355 | // If the phi isn't in the current block, an incoming edge to this block |
| 356 | // doesn't control the destination. |
| 357 | if (PN->getParent() != BB) |
| 358 | return false; |
| 359 | |
| 360 | // We can do this simplification if any comparisons fold to true or false. |
| 361 | // See if any do. |
| 362 | Constant *PredCst = 0; |
| 363 | bool TrueDirection = false; |
| 364 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { |
| 365 | PredCst = dyn_cast<Constant>(PN->getIncomingValue(i)); |
| 366 | if (PredCst == 0) continue; |
| 367 | |
| 368 | Constant *Res; |
| 369 | if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cmp)) |
| 370 | Res = ConstantExpr::getICmp(ICI->getPredicate(), PredCst, RHS); |
| 371 | else |
| 372 | Res = ConstantExpr::getFCmp(cast<FCmpInst>(Cmp)->getPredicate(), |
| 373 | PredCst, RHS); |
| 374 | // If this folded to a constant expr, we can't do anything. |
| 375 | if (ConstantInt *ResC = dyn_cast<ConstantInt>(Res)) { |
| 376 | TrueDirection = ResC->getZExtValue(); |
| 377 | break; |
| 378 | } |
| 379 | // If this folded to undef, just go the false way. |
| 380 | if (isa<UndefValue>(Res)) { |
| 381 | TrueDirection = false; |
| 382 | break; |
| 383 | } |
| 384 | |
| 385 | // Otherwise, we can't fold this input. |
| 386 | PredCst = 0; |
| 387 | } |
| 388 | |
| 389 | // If no match, bail out. |
| 390 | if (PredCst == 0) |
| 391 | return false; |
| 392 | |
| 393 | // See if the cost of duplicating this block is low enough. |
| 394 | unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB); |
| 395 | if (JumpThreadCost > Threshold) { |
| 396 | DOUT << " Not threading BB '" << BB->getNameStart() |
| 397 | << "' - Cost is too high: " << JumpThreadCost << "\n"; |
| 398 | return false; |
| 399 | } |
| 400 | |
| 401 | // If so, we can actually do this threading. Merge any common predecessors |
| 402 | // that will act the same. |
| 403 | BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst); |
| 404 | |
| 405 | // Next, get our successor. |
| 406 | BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(!TrueDirection); |
| 407 | |
Chris Lattner | eede65c | 2008-04-25 04:12:29 +0000 | [diff] [blame] | 408 | // If threading to the same block as we come from, we would infinite loop. |
| 409 | if (SuccBB == BB) { |
| 410 | DOUT << " Not threading BB '" << BB->getNameStart() |
| 411 | << "' - would thread to self!\n"; |
| 412 | return false; |
| 413 | } |
| 414 | |
| 415 | |
Chris Lattner | a5ddb59 | 2008-04-22 21:40:39 +0000 | [diff] [blame] | 416 | // And finally, do it! |
| 417 | DOUT << " Threading edge through bool from '" << PredBB->getNameStart() |
| 418 | << "' to '" << SuccBB->getNameStart() << "' with cost: " |
| 419 | << JumpThreadCost << ", across block:\n " |
| 420 | << *BB << "\n"; |
| 421 | |
| 422 | ThreadEdge(BB, PredBB, SuccBB); |
| 423 | ++NumThreads; |
| 424 | return true; |
| 425 | } |
| 426 | |
Chris Lattner | 6bf7750 | 2008-04-22 07:05:46 +0000 | [diff] [blame] | 427 | |
Chris Lattner | bd3401f | 2008-04-20 22:39:42 +0000 | [diff] [blame] | 428 | /// ThreadEdge - We have decided that it is safe and profitable to thread an |
| 429 | /// edge from PredBB to SuccBB across BB. Transform the IR to reflect this |
| 430 | /// change. |
| 431 | void JumpThreading::ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, |
| 432 | BasicBlock *SuccBB) { |
| 433 | |
| 434 | // Jump Threading can not update SSA properties correctly if the values |
| 435 | // defined in the duplicated block are used outside of the block itself. For |
| 436 | // this reason, we spill all values that are used outside of BB to the stack. |
Chris Lattner | 8554cc2 | 2008-05-05 20:21:22 +0000 | [diff] [blame] | 437 | for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) { |
| 438 | if (!I->isUsedOutsideOfBlock(BB)) |
| 439 | continue; |
| 440 | |
| 441 | // We found a use of I outside of BB. Create a new stack slot to |
| 442 | // break this inter-block usage pattern. |
| 443 | if (!isa<StructType>(I->getType())) { |
Chris Lattner | bd3401f | 2008-04-20 22:39:42 +0000 | [diff] [blame] | 444 | DemoteRegToStack(*I); |
Chris Lattner | 8554cc2 | 2008-05-05 20:21:22 +0000 | [diff] [blame] | 445 | continue; |
Chris Lattner | bd3401f | 2008-04-20 22:39:42 +0000 | [diff] [blame] | 446 | } |
Chris Lattner | 8554cc2 | 2008-05-05 20:21:22 +0000 | [diff] [blame] | 447 | |
| 448 | // Alternatively, I must be a call or invoke that returns multiple retvals. |
Chris Lattner | 9b34849 | 2008-05-06 02:31:18 +0000 | [diff] [blame] | 449 | // We can't use 'DemoteRegToStack' because that will create loads and |
Chris Lattner | 8554cc2 | 2008-05-05 20:21:22 +0000 | [diff] [blame] | 450 | // stores of aggregates which is not valid yet. If I is a call, we can just |
| 451 | // pull all the getresult instructions up to this block. If I is an invoke, |
| 452 | // we are out of luck. |
| 453 | BasicBlock::iterator IP = I; ++IP; |
| 454 | for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); |
| 455 | UI != E; ++UI) |
| 456 | cast<GetResultInst>(UI)->moveBefore(IP); |
| 457 | } |
Chris Lattner | bd3401f | 2008-04-20 22:39:42 +0000 | [diff] [blame] | 458 | |
| 459 | // We are going to have to map operands from the original BB block to the new |
| 460 | // copy of the block 'NewBB'. If there are PHI nodes in BB, evaluate them to |
| 461 | // account for entry from PredBB. |
| 462 | DenseMap<Instruction*, Value*> ValueMapping; |
| 463 | |
| 464 | BasicBlock *NewBB = |
| 465 | BasicBlock::Create(BB->getName()+".thread", BB->getParent(), BB); |
| 466 | NewBB->moveAfter(PredBB); |
| 467 | |
| 468 | BasicBlock::iterator BI = BB->begin(); |
| 469 | for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI) |
| 470 | ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB); |
| 471 | |
| 472 | // Clone the non-phi instructions of BB into NewBB, keeping track of the |
| 473 | // mapping and using it to remap operands in the cloned instructions. |
| 474 | for (; !isa<TerminatorInst>(BI); ++BI) { |
| 475 | Instruction *New = BI->clone(); |
| 476 | New->setName(BI->getNameStart()); |
| 477 | NewBB->getInstList().push_back(New); |
| 478 | ValueMapping[BI] = New; |
| 479 | |
| 480 | // Remap operands to patch up intra-block references. |
| 481 | for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i) |
| 482 | if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) |
| 483 | if (Value *Remapped = ValueMapping[Inst]) |
| 484 | New->setOperand(i, Remapped); |
| 485 | } |
| 486 | |
| 487 | // We didn't copy the terminator from BB over to NewBB, because there is now |
| 488 | // an unconditional jump to SuccBB. Insert the unconditional jump. |
| 489 | BranchInst::Create(SuccBB, NewBB); |
| 490 | |
| 491 | // Check to see if SuccBB has PHI nodes. If so, we need to add entries to the |
| 492 | // PHI nodes for NewBB now. |
| 493 | for (BasicBlock::iterator PNI = SuccBB->begin(); isa<PHINode>(PNI); ++PNI) { |
| 494 | PHINode *PN = cast<PHINode>(PNI); |
| 495 | // Ok, we have a PHI node. Figure out what the incoming value was for the |
| 496 | // DestBlock. |
| 497 | Value *IV = PN->getIncomingValueForBlock(BB); |
| 498 | |
| 499 | // Remap the value if necessary. |
| 500 | if (Instruction *Inst = dyn_cast<Instruction>(IV)) |
| 501 | if (Value *MappedIV = ValueMapping[Inst]) |
| 502 | IV = MappedIV; |
| 503 | PN->addIncoming(IV, NewBB); |
| 504 | } |
| 505 | |
| 506 | // Finally, NewBB is good to go. Update the terminator of PredBB to jump to |
| 507 | // NewBB instead of BB. This eliminates predecessors from BB, which requires |
| 508 | // us to simplify any PHI nodes in BB. |
| 509 | TerminatorInst *PredTerm = PredBB->getTerminator(); |
| 510 | for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i) |
| 511 | if (PredTerm->getSuccessor(i) == BB) { |
| 512 | BB->removePredecessor(PredBB); |
| 513 | PredTerm->setSuccessor(i, NewBB); |
| 514 | } |
Chris Lattner | 177480b | 2008-04-20 21:13:06 +0000 | [diff] [blame] | 515 | } |