LLVM API Documentation
00001 //===- JumpThreading.cpp - Thread control through conditional blocks ------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the Jump Threading pass. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #define DEBUG_TYPE "jump-threading" 00015 #include "llvm/Transforms/Scalar.h" 00016 #include "llvm/IntrinsicInst.h" 00017 #include "llvm/LLVMContext.h" 00018 #include "llvm/Pass.h" 00019 #include "llvm/Analysis/ConstantFolding.h" 00020 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 00021 #include "llvm/Transforms/Utils/Local.h" 00022 #include "llvm/Target/TargetData.h" 00023 #include "llvm/ADT/DenseMap.h" 00024 #include "llvm/ADT/Statistic.h" 00025 #include "llvm/ADT/STLExtras.h" 00026 #include "llvm/ADT/SmallPtrSet.h" 00027 #include "llvm/ADT/SmallSet.h" 00028 #include "llvm/Support/CommandLine.h" 00029 #include "llvm/Support/Compiler.h" 00030 #include "llvm/Support/Debug.h" 00031 #include "llvm/Support/ValueHandle.h" 00032 #include "llvm/Support/raw_ostream.h" 00033 using namespace llvm; 00034 00035 STATISTIC(NumThreads, "Number of jumps threaded"); 00036 STATISTIC(NumFolds, "Number of terminators folded"); 00037 00038 static cl::opt<unsigned> 00039 Threshold("jump-threading-threshold", 00040 cl::desc("Max block size to duplicate for jump threading"), 00041 cl::init(6), cl::Hidden); 00042 00043 namespace { 00044 /// This pass performs 'jump threading', which looks at blocks that have 00045 /// multiple predecessors and multiple successors. If one or more of the 00046 /// predecessors of the block can be proven to always jump to one of the 00047 /// successors, we forward the edge from the predecessor to the successor by 00048 /// duplicating the contents of this block. 00049 /// 00050 /// An example of when this can occur is code like this: 00051 /// 00052 /// if () { ... 00053 /// X = 4; 00054 /// } 00055 /// if (X < 3) { 00056 /// 00057 /// In this case, the unconditional branch at the end of the first if can be 00058 /// revectored to the false side of the second if. 00059 /// 00060 class VISIBILITY_HIDDEN JumpThreading : public FunctionPass { 00061 TargetData *TD; 00062 #ifdef NDEBUG 00063 SmallPtrSet<BasicBlock*, 16> LoopHeaders; 00064 #else 00065 SmallSet<AssertingVH<BasicBlock>, 16> LoopHeaders; 00066 #endif 00067 public: 00068 static char ID; // Pass identification 00069 JumpThreading() : FunctionPass(&ID) {} 00070 00071 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00072 } 00073 00074 bool runOnFunction(Function &F); 00075 void FindLoopHeaders(Function &F); 00076 00077 bool ProcessBlock(BasicBlock *BB); 00078 bool ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, BasicBlock *SuccBB, 00079 unsigned JumpThreadCost); 00080 BasicBlock *FactorCommonPHIPreds(PHINode *PN, Value *Val); 00081 bool ProcessBranchOnDuplicateCond(BasicBlock *PredBB, BasicBlock *DestBB); 00082 bool ProcessSwitchOnDuplicateCond(BasicBlock *PredBB, BasicBlock *DestBB); 00083 00084 bool ProcessJumpOnPHI(PHINode *PN); 00085 bool ProcessBranchOnLogical(Value *V, BasicBlock *BB, bool isAnd); 00086 bool ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB); 00087 00088 bool SimplifyPartiallyRedundantLoad(LoadInst *LI); 00089 }; 00090 } 00091 00092 char JumpThreading::ID = 0; 00093 static RegisterPass<JumpThreading> 00094 X("jump-threading", "Jump Threading"); 00095 00096 // Public interface to the Jump Threading pass 00097 FunctionPass *llvm::createJumpThreadingPass() { return new JumpThreading(); } 00098 00099 /// runOnFunction - Top level algorithm. 00100 /// 00101 bool JumpThreading::runOnFunction(Function &F) { 00102 DEBUG(errs() << "Jump threading on function '" << F.getName() << "'\n"); 00103 TD = getAnalysisIfAvailable<TargetData>(); 00104 00105 FindLoopHeaders(F); 00106 00107 bool AnotherIteration = true, EverChanged = false; 00108 while (AnotherIteration) { 00109 AnotherIteration = false; 00110 bool Changed = false; 00111 for (Function::iterator I = F.begin(), E = F.end(); I != E;) { 00112 BasicBlock *BB = I; 00113 while (ProcessBlock(BB)) 00114 Changed = true; 00115 00116 ++I; 00117 00118 // If the block is trivially dead, zap it. This eliminates the successor 00119 // edges which simplifies the CFG. 00120 if (pred_begin(BB) == pred_end(BB) && 00121 BB != &BB->getParent()->getEntryBlock()) { 00122 DEBUG(errs() << " JT: Deleting dead block '" << BB->getName() 00123 << "' with terminator: " << *BB->getTerminator()); 00124 LoopHeaders.erase(BB); 00125 DeleteDeadBlock(BB); 00126 Changed = true; 00127 } 00128 } 00129 AnotherIteration = Changed; 00130 EverChanged |= Changed; 00131 } 00132 00133 LoopHeaders.clear(); 00134 return EverChanged; 00135 } 00136 00137 /// FindLoopHeaders - We do not want jump threading to turn proper loop 00138 /// structures into irreducible loops. Doing this breaks up the loop nesting 00139 /// hierarchy and pessimizes later transformations. To prevent this from 00140 /// happening, we first have to find the loop headers. Here we approximate this 00141 /// by finding targets of backedges in the CFG. 00142 /// 00143 /// Note that there definitely are cases when we want to allow threading of 00144 /// edges across a loop header. For example, threading a jump from outside the 00145 /// loop (the preheader) to an exit block of the loop is definitely profitable. 00146 /// It is also almost always profitable to thread backedges from within the loop 00147 /// to exit blocks, and is often profitable to thread backedges to other blocks 00148 /// within the loop (forming a nested loop). This simple analysis is not rich 00149 /// enough to track all of these properties and keep it up-to-date as the CFG 00150 /// mutates, so we don't allow any of these transformations. 00151 /// 00152 void JumpThreading::FindLoopHeaders(Function &F) { 00153 SmallVector<std::pair<const BasicBlock*,const BasicBlock*>, 32> Edges; 00154 FindFunctionBackedges(F, Edges); 00155 00156 for (unsigned i = 0, e = Edges.size(); i != e; ++i) 00157 LoopHeaders.insert(const_cast<BasicBlock*>(Edges[i].second)); 00158 } 00159 00160 00161 /// FactorCommonPHIPreds - If there are multiple preds with the same incoming 00162 /// value for the PHI, factor them together so we get one block to thread for 00163 /// the whole group. 00164 /// This is important for things like "phi i1 [true, true, false, true, x]" 00165 /// where we only need to clone the block for the true blocks once. 00166 /// 00167 BasicBlock *JumpThreading::FactorCommonPHIPreds(PHINode *PN, Value *Val) { 00168 SmallVector<BasicBlock*, 16> CommonPreds; 00169 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 00170 if (PN->getIncomingValue(i) == Val) 00171 CommonPreds.push_back(PN->getIncomingBlock(i)); 00172 00173 if (CommonPreds.size() == 1) 00174 return CommonPreds[0]; 00175 00176 DEBUG(errs() << " Factoring out " << CommonPreds.size() 00177 << " common predecessors.\n"); 00178 return SplitBlockPredecessors(PN->getParent(), 00179 &CommonPreds[0], CommonPreds.size(), 00180 ".thr_comm", this); 00181 } 00182 00183 00184 /// getJumpThreadDuplicationCost - Return the cost of duplicating this block to 00185 /// thread across it. 00186 static unsigned getJumpThreadDuplicationCost(const BasicBlock *BB) { 00187 /// Ignore PHI nodes, these will be flattened when duplication happens. 00188 BasicBlock::const_iterator I = BB->getFirstNonPHI(); 00189 00190 // Sum up the cost of each instruction until we get to the terminator. Don't 00191 // include the terminator because the copy won't include it. 00192 unsigned Size = 0; 00193 for (; !isa<TerminatorInst>(I); ++I) { 00194 // Debugger intrinsics don't incur code size. 00195 if (isa<DbgInfoIntrinsic>(I)) continue; 00196 00197 // If this is a pointer->pointer bitcast, it is free. 00198 if (isa<BitCastInst>(I) && isa<PointerType>(I->getType())) 00199 continue; 00200 00201 // All other instructions count for at least one unit. 00202 ++Size; 00203 00204 // Calls are more expensive. If they are non-intrinsic calls, we model them 00205 // as having cost of 4. If they are a non-vector intrinsic, we model them 00206 // as having cost of 2 total, and if they are a vector intrinsic, we model 00207 // them as having cost 1. 00208 if (const CallInst *CI = dyn_cast<CallInst>(I)) { 00209 if (!isa<IntrinsicInst>(CI)) 00210 Size += 3; 00211 else if (!isa<VectorType>(CI->getType())) 00212 Size += 1; 00213 } 00214 } 00215 00216 // Threading through a switch statement is particularly profitable. If this 00217 // block ends in a switch, decrease its cost to make it more likely to happen. 00218 if (isa<SwitchInst>(I)) 00219 Size = Size > 6 ? Size-6 : 0; 00220 00221 return Size; 00222 } 00223 00224 /// ProcessBlock - If there are any predecessors whose control can be threaded 00225 /// through to a successor, transform them now. 00226 bool JumpThreading::ProcessBlock(BasicBlock *BB) { 00227 // If this block has a single predecessor, and if that pred has a single 00228 // successor, merge the blocks. This encourages recursive jump threading 00229 // because now the condition in this block can be threaded through 00230 // predecessors of our predecessor block. 00231 if (BasicBlock *SinglePred = BB->getSinglePredecessor()) 00232 if (SinglePred->getTerminator()->getNumSuccessors() == 1 && 00233 SinglePred != BB) { 00234 // If SinglePred was a loop header, BB becomes one. 00235 if (LoopHeaders.erase(SinglePred)) 00236 LoopHeaders.insert(BB); 00237 00238 // Remember if SinglePred was the entry block of the function. If so, we 00239 // will need to move BB back to the entry position. 00240 bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock(); 00241 MergeBasicBlockIntoOnlyPred(BB); 00242 00243 if (isEntry && BB != &BB->getParent()->getEntryBlock()) 00244 BB->moveBefore(&BB->getParent()->getEntryBlock()); 00245 return true; 00246 } 00247 00248 // See if this block ends with a branch or switch. If so, see if the 00249 // condition is a phi node. If so, and if an entry of the phi node is a 00250 // constant, we can thread the block. 00251 Value *Condition; 00252 if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 00253 // Can't thread an unconditional jump. 00254 if (BI->isUnconditional()) return false; 00255 Condition = BI->getCondition(); 00256 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) 00257 Condition = SI->getCondition(); 00258 else 00259 return false; // Must be an invoke. 00260 00261 // If the terminator of this block is branching on a constant, simplify the 00262 // terminator to an unconditional branch. This can occur due to threading in 00263 // other blocks. 00264 if (isa<ConstantInt>(Condition)) { 00265 DEBUG(errs() << " In block '" << BB->getName() 00266 << "' folding terminator: " << *BB->getTerminator()); 00267 ++NumFolds; 00268 ConstantFoldTerminator(BB); 00269 return true; 00270 } 00271 00272 // If the terminator is branching on an undef, we can pick any of the 00273 // successors to branch to. Since this is arbitrary, we pick the successor 00274 // with the fewest predecessors. This should reduce the in-degree of the 00275 // others. 00276 if (isa<UndefValue>(Condition)) { 00277 TerminatorInst *BBTerm = BB->getTerminator(); 00278 unsigned MinSucc = 0; 00279 BasicBlock *TestBB = BBTerm->getSuccessor(MinSucc); 00280 // Compute the successor with the minimum number of predecessors. 00281 unsigned MinNumPreds = std::distance(pred_begin(TestBB), pred_end(TestBB)); 00282 for (unsigned i = 1, e = BBTerm->getNumSuccessors(); i != e; ++i) { 00283 TestBB = BBTerm->getSuccessor(i); 00284 unsigned NumPreds = std::distance(pred_begin(TestBB), pred_end(TestBB)); 00285 if (NumPreds < MinNumPreds) 00286 MinSucc = i; 00287 } 00288 00289 // Fold the branch/switch. 00290 for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) { 00291 if (i == MinSucc) continue; 00292 BBTerm->getSuccessor(i)->removePredecessor(BB); 00293 } 00294 00295 DEBUG(errs() << " In block '" << BB->getName() 00296 << "' folding undef terminator: " << *BBTerm); 00297 BranchInst::Create(BBTerm->getSuccessor(MinSucc), BBTerm); 00298 BBTerm->eraseFromParent(); 00299 return true; 00300 } 00301 00302 Instruction *CondInst = dyn_cast<Instruction>(Condition); 00303 00304 // If the condition is an instruction defined in another block, see if a 00305 // predecessor has the same condition: 00306 // br COND, BBX, BBY 00307 // BBX: 00308 // br COND, BBZ, BBW 00309 if (!Condition->hasOneUse() && // Multiple uses. 00310 (CondInst == 0 || CondInst->getParent() != BB)) { // Non-local definition. 00311 pred_iterator PI = pred_begin(BB), E = pred_end(BB); 00312 if (isa<BranchInst>(BB->getTerminator())) { 00313 for (; PI != E; ++PI) 00314 if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 00315 if (PBI->isConditional() && PBI->getCondition() == Condition && 00316 ProcessBranchOnDuplicateCond(*PI, BB)) 00317 return true; 00318 } else { 00319 assert(isa<SwitchInst>(BB->getTerminator()) && "Unknown jump terminator"); 00320 for (; PI != E; ++PI) 00321 if (SwitchInst *PSI = dyn_cast<SwitchInst>((*PI)->getTerminator())) 00322 if (PSI->getCondition() == Condition && 00323 ProcessSwitchOnDuplicateCond(*PI, BB)) 00324 return true; 00325 } 00326 } 00327 00328 // All the rest of our checks depend on the condition being an instruction. 00329 if (CondInst == 0) 00330 return false; 00331 00332 // See if this is a phi node in the current block. 00333 if (PHINode *PN = dyn_cast<PHINode>(CondInst)) 00334 if (PN->getParent() == BB) 00335 return ProcessJumpOnPHI(PN); 00336 00337 // If this is a conditional branch whose condition is and/or of a phi, try to 00338 // simplify it. 00339 if ((CondInst->getOpcode() == Instruction::And || 00340 CondInst->getOpcode() == Instruction::Or) && 00341 isa<BranchInst>(BB->getTerminator()) && 00342 ProcessBranchOnLogical(CondInst, BB, 00343 CondInst->getOpcode() == Instruction::And)) 00344 return true; 00345 00346 if (CmpInst *CondCmp = dyn_cast<CmpInst>(CondInst)) { 00347 if (isa<PHINode>(CondCmp->getOperand(0))) { 00348 // If we have "br (phi != 42)" and the phi node has any constant values 00349 // as operands, we can thread through this block. 00350 // 00351 // If we have "br (cmp phi, x)" and the phi node contains x such that the 00352 // comparison uniquely identifies the branch target, we can thread 00353 // through this block. 00354 00355 if (ProcessBranchOnCompare(CondCmp, BB)) 00356 return true; 00357 } 00358 00359 // If we have a comparison, loop over the predecessors to see if there is 00360 // a condition with the same value. 00361 pred_iterator PI = pred_begin(BB), E = pred_end(BB); 00362 for (; PI != E; ++PI) 00363 if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 00364 if (PBI->isConditional() && *PI != BB) { 00365 if (CmpInst *CI = dyn_cast<CmpInst>(PBI->getCondition())) { 00366 if (CI->getOperand(0) == CondCmp->getOperand(0) && 00367 CI->getOperand(1) == CondCmp->getOperand(1) && 00368 CI->getPredicate() == CondCmp->getPredicate()) { 00369 // TODO: Could handle things like (x != 4) --> (x == 17) 00370 if (ProcessBranchOnDuplicateCond(*PI, BB)) 00371 return true; 00372 } 00373 } 00374 } 00375 } 00376 00377 // Check for some cases that are worth simplifying. Right now we want to look 00378 // for loads that are used by a switch or by the condition for the branch. If 00379 // we see one, check to see if it's partially redundant. If so, insert a PHI 00380 // which can then be used to thread the values. 00381 // 00382 // This is particularly important because reg2mem inserts loads and stores all 00383 // over the place, and this blocks jump threading if we don't zap them. 00384 Value *SimplifyValue = CondInst; 00385 if (CmpInst *CondCmp = dyn_cast<CmpInst>(SimplifyValue)) 00386 if (isa<Constant>(CondCmp->getOperand(1))) 00387 SimplifyValue = CondCmp->getOperand(0); 00388 00389 if (LoadInst *LI = dyn_cast<LoadInst>(SimplifyValue)) 00390 if (SimplifyPartiallyRedundantLoad(LI)) 00391 return true; 00392 00393 // TODO: If we have: "br (X > 0)" and we have a predecessor where we know 00394 // "(X == 4)" thread through this block. 00395 00396 return false; 00397 } 00398 00399 /// ProcessBranchOnDuplicateCond - We found a block and a predecessor of that 00400 /// block that jump on exactly the same condition. This means that we almost 00401 /// always know the direction of the edge in the DESTBB: 00402 /// PREDBB: 00403 /// br COND, DESTBB, BBY 00404 /// DESTBB: 00405 /// br COND, BBZ, BBW 00406 /// 00407 /// If DESTBB has multiple predecessors, we can't just constant fold the branch 00408 /// in DESTBB, we have to thread over it. 00409 bool JumpThreading::ProcessBranchOnDuplicateCond(BasicBlock *PredBB, 00410 BasicBlock *BB) { 00411 BranchInst *PredBI = cast<BranchInst>(PredBB->getTerminator()); 00412 00413 // If both successors of PredBB go to DESTBB, we don't know anything. We can 00414 // fold the branch to an unconditional one, which allows other recursive 00415 // simplifications. 00416 bool BranchDir; 00417 if (PredBI->getSuccessor(1) != BB) 00418 BranchDir = true; 00419 else if (PredBI->getSuccessor(0) != BB) 00420 BranchDir = false; 00421 else { 00422 DEBUG(errs() << " In block '" << PredBB->getName() 00423 << "' folding terminator: " << *PredBB->getTerminator()); 00424 ++NumFolds; 00425 ConstantFoldTerminator(PredBB); 00426 return true; 00427 } 00428 00429 BranchInst *DestBI = cast<BranchInst>(BB->getTerminator()); 00430 00431 // If the dest block has one predecessor, just fix the branch condition to a 00432 // constant and fold it. 00433 if (BB->getSinglePredecessor()) { 00434 DEBUG(errs() << " In block '" << BB->getName() 00435 << "' folding condition to '" << BranchDir << "': " 00436 << *BB->getTerminator()); 00437 ++NumFolds; 00438 DestBI->setCondition(ConstantInt::get(Type::getInt1Ty(BB->getContext()), 00439 BranchDir)); 00440 ConstantFoldTerminator(BB); 00441 return true; 00442 } 00443 00444 // Otherwise we need to thread from PredBB to DestBB's successor which 00445 // involves code duplication. Check to see if it is worth it. 00446 unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB); 00447 if (JumpThreadCost > Threshold) { 00448 DEBUG(errs() << " Not threading BB '" << BB->getName() 00449 << "' - Cost is too high: " << JumpThreadCost << "\n"); 00450 return false; 00451 } 00452 00453 // Next, figure out which successor we are threading to. 00454 BasicBlock *SuccBB = DestBI->getSuccessor(!BranchDir); 00455 00456 // Ok, try to thread it! 00457 return ThreadEdge(BB, PredBB, SuccBB, JumpThreadCost); 00458 } 00459 00460 /// ProcessSwitchOnDuplicateCond - We found a block and a predecessor of that 00461 /// block that switch on exactly the same condition. This means that we almost 00462 /// always know the direction of the edge in the DESTBB: 00463 /// PREDBB: 00464 /// switch COND [... DESTBB, BBY ... ] 00465 /// DESTBB: 00466 /// switch COND [... BBZ, BBW ] 00467 /// 00468 /// Optimizing switches like this is very important, because simplifycfg builds 00469 /// switches out of repeated 'if' conditions. 00470 bool JumpThreading::ProcessSwitchOnDuplicateCond(BasicBlock *PredBB, 00471 BasicBlock *DestBB) { 00472 // Can't thread edge to self. 00473 if (PredBB == DestBB) 00474 return false; 00475 00476 00477 SwitchInst *PredSI = cast<SwitchInst>(PredBB->getTerminator()); 00478 SwitchInst *DestSI = cast<SwitchInst>(DestBB->getTerminator()); 00479 00480 // There are a variety of optimizations that we can potentially do on these 00481 // blocks: we order them from most to least preferable. 00482 00483 // If DESTBB *just* contains the switch, then we can forward edges from PREDBB 00484 // directly to their destination. This does not introduce *any* code size 00485 // growth. Skip debug info first. 00486 BasicBlock::iterator BBI = DestBB->begin(); 00487 while (isa<DbgInfoIntrinsic>(BBI)) 00488 BBI++; 00489 00490 // FIXME: Thread if it just contains a PHI. 00491 if (isa<SwitchInst>(BBI)) { 00492 bool MadeChange = false; 00493 // Ignore the default edge for now. 00494 for (unsigned i = 1, e = DestSI->getNumSuccessors(); i != e; ++i) { 00495 ConstantInt *DestVal = DestSI->getCaseValue(i); 00496 BasicBlock *DestSucc = DestSI->getSuccessor(i); 00497 00498 // Okay, DestSI has a case for 'DestVal' that goes to 'DestSucc'. See if 00499 // PredSI has an explicit case for it. If so, forward. If it is covered 00500 // by the default case, we can't update PredSI. 00501 unsigned PredCase = PredSI->findCaseValue(DestVal); 00502 if (PredCase == 0) continue; 00503 00504 // If PredSI doesn't go to DestBB on this value, then it won't reach the 00505 // case on this condition. 00506 if (PredSI->getSuccessor(PredCase) != DestBB && 00507 DestSI->getSuccessor(i) != DestBB) 00508 continue; 00509 00510 // Otherwise, we're safe to make the change. Make sure that the edge from 00511 // DestSI to DestSucc is not critical and has no PHI nodes. 00512 DEBUG(errs() << "FORWARDING EDGE " << *DestVal << " FROM: " << *PredSI); 00513 DEBUG(errs() << "THROUGH: " << *DestSI); 00514 00515 // If the destination has PHI nodes, just split the edge for updating 00516 // simplicity. 00517 if (isa<PHINode>(DestSucc->begin()) && !DestSucc->getSinglePredecessor()){ 00518 SplitCriticalEdge(DestSI, i, this); 00519 DestSucc = DestSI->getSuccessor(i); 00520 } 00521 FoldSingleEntryPHINodes(DestSucc); 00522 PredSI->setSuccessor(PredCase, DestSucc); 00523 MadeChange = true; 00524 } 00525 00526 if (MadeChange) 00527 return true; 00528 } 00529 00530 return false; 00531 } 00532 00533 00534 /// SimplifyPartiallyRedundantLoad - If LI is an obviously partially redundant 00535 /// load instruction, eliminate it by replacing it with a PHI node. This is an 00536 /// important optimization that encourages jump threading, and needs to be run 00537 /// interlaced with other jump threading tasks. 00538 bool JumpThreading::SimplifyPartiallyRedundantLoad(LoadInst *LI) { 00539 // Don't hack volatile loads. 00540 if (LI->isVolatile()) return false; 00541 00542 // If the load is defined in a block with exactly one predecessor, it can't be 00543 // partially redundant. 00544 BasicBlock *LoadBB = LI->getParent(); 00545 if (LoadBB->getSinglePredecessor()) 00546 return false; 00547 00548 Value *LoadedPtr = LI->getOperand(0); 00549 00550 // If the loaded operand is defined in the LoadBB, it can't be available. 00551 // FIXME: Could do PHI translation, that would be fun :) 00552 if (Instruction *PtrOp = dyn_cast<Instruction>(LoadedPtr)) 00553 if (PtrOp->getParent() == LoadBB) 00554 return false; 00555 00556 // Scan a few instructions up from the load, to see if it is obviously live at 00557 // the entry to its block. 00558 BasicBlock::iterator BBIt = LI; 00559 00560 if (Value *AvailableVal = FindAvailableLoadedValue(LoadedPtr, LoadBB, 00561 BBIt, 6)) { 00562 // If the value if the load is locally available within the block, just use 00563 // it. This frequently occurs for reg2mem'd allocas. 00564 //cerr << "LOAD ELIMINATED:\n" << *BBIt << *LI << "\n"; 00565 00566 // If the returned value is the load itself, replace with an undef. This can 00567 // only happen in dead loops. 00568 if (AvailableVal == LI) AvailableVal = UndefValue::get(LI->getType()); 00569 LI->replaceAllUsesWith(AvailableVal); 00570 LI->eraseFromParent(); 00571 return true; 00572 } 00573 00574 // Otherwise, if we scanned the whole block and got to the top of the block, 00575 // we know the block is locally transparent to the load. If not, something 00576 // might clobber its value. 00577 if (BBIt != LoadBB->begin()) 00578 return false; 00579 00580 00581 SmallPtrSet<BasicBlock*, 8> PredsScanned; 00582 typedef SmallVector<std::pair<BasicBlock*, Value*>, 8> AvailablePredsTy; 00583 AvailablePredsTy AvailablePreds; 00584 BasicBlock *OneUnavailablePred = 0; 00585 00586 // If we got here, the loaded value is transparent through to the start of the 00587 // block. Check to see if it is available in any of the predecessor blocks. 00588 for (pred_iterator PI = pred_begin(LoadBB), PE = pred_end(LoadBB); 00589 PI != PE; ++PI) { 00590 BasicBlock *PredBB = *PI; 00591 00592 // If we already scanned this predecessor, skip it. 00593 if (!PredsScanned.insert(PredBB)) 00594 continue; 00595 00596 // Scan the predecessor to see if the value is available in the pred. 00597 BBIt = PredBB->end(); 00598 Value *PredAvailable = FindAvailableLoadedValue(LoadedPtr, PredBB, BBIt, 6); 00599 if (!PredAvailable) { 00600 OneUnavailablePred = PredBB; 00601 continue; 00602 } 00603 00604 // If so, this load is partially redundant. Remember this info so that we 00605 // can create a PHI node. 00606 AvailablePreds.push_back(std::make_pair(PredBB, PredAvailable)); 00607 } 00608 00609 // If the loaded value isn't available in any predecessor, it isn't partially 00610 // redundant. 00611 if (AvailablePreds.empty()) return false; 00612 00613 // Okay, the loaded value is available in at least one (and maybe all!) 00614 // predecessors. If the value is unavailable in more than one unique 00615 // predecessor, we want to insert a merge block for those common predecessors. 00616 // This ensures that we only have to insert one reload, thus not increasing 00617 // code size. 00618 BasicBlock *UnavailablePred = 0; 00619 00620 // If there is exactly one predecessor where the value is unavailable, the 00621 // already computed 'OneUnavailablePred' block is it. If it ends in an 00622 // unconditional branch, we know that it isn't a critical edge. 00623 if (PredsScanned.size() == AvailablePreds.size()+1 && 00624 OneUnavailablePred->getTerminator()->getNumSuccessors() == 1) { 00625 UnavailablePred = OneUnavailablePred; 00626 } else if (PredsScanned.size() != AvailablePreds.size()) { 00627 // Otherwise, we had multiple unavailable predecessors or we had a critical 00628 // edge from the one. 00629 SmallVector<BasicBlock*, 8> PredsToSplit; 00630 SmallPtrSet<BasicBlock*, 8> AvailablePredSet; 00631 00632 for (unsigned i = 0, e = AvailablePreds.size(); i != e; ++i) 00633 AvailablePredSet.insert(AvailablePreds[i].first); 00634 00635 // Add all the unavailable predecessors to the PredsToSplit list. 00636 for (pred_iterator PI = pred_begin(LoadBB), PE = pred_end(LoadBB); 00637 PI != PE; ++PI) 00638 if (!AvailablePredSet.count(*PI)) 00639 PredsToSplit.push_back(*PI); 00640 00641 // Split them out to their own block. 00642 UnavailablePred = 00643 SplitBlockPredecessors(LoadBB, &PredsToSplit[0], PredsToSplit.size(), 00644 "thread-split", this); 00645 } 00646 00647 // If the value isn't available in all predecessors, then there will be 00648 // exactly one where it isn't available. Insert a load on that edge and add 00649 // it to the AvailablePreds list. 00650 if (UnavailablePred) { 00651 assert(UnavailablePred->getTerminator()->getNumSuccessors() == 1 && 00652 "Can't handle critical edge here!"); 00653 Value *NewVal = new LoadInst(LoadedPtr, LI->getName()+".pr", 00654 UnavailablePred->getTerminator()); 00655 AvailablePreds.push_back(std::make_pair(UnavailablePred, NewVal)); 00656 } 00657 00658 // Now we know that each predecessor of this block has a value in 00659 // AvailablePreds, sort them for efficient access as we're walking the preds. 00660 array_pod_sort(AvailablePreds.begin(), AvailablePreds.end()); 00661 00662 // Create a PHI node at the start of the block for the PRE'd load value. 00663 PHINode *PN = PHINode::Create(LI->getType(), "", LoadBB->begin()); 00664 PN->takeName(LI); 00665 00666 // Insert new entries into the PHI for each predecessor. A single block may 00667 // have multiple entries here. 00668 for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB); PI != E; 00669 ++PI) { 00670 AvailablePredsTy::iterator I = 00671 std::lower_bound(AvailablePreds.begin(), AvailablePreds.end(), 00672 std::make_pair(*PI, (Value*)0)); 00673 00674 assert(I != AvailablePreds.end() && I->first == *PI && 00675 "Didn't find entry for predecessor!"); 00676 00677 PN->addIncoming(I->second, I->first); 00678 } 00679 00680 //cerr << "PRE: " << *LI << *PN << "\n"; 00681 00682 LI->replaceAllUsesWith(PN); 00683 LI->eraseFromParent(); 00684 00685 return true; 00686 } 00687 00688 00689 /// ProcessJumpOnPHI - We have a conditional branch of switch on a PHI node in 00690 /// the current block. See if there are any simplifications we can do based on 00691 /// inputs to the phi node. 00692 /// 00693 bool JumpThreading::ProcessJumpOnPHI(PHINode *PN) { 00694 // See if the phi node has any constant values. If so, we can determine where 00695 // the corresponding predecessor will branch. 00696 ConstantInt *PredCst = 0; 00697 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 00698 if ((PredCst = dyn_cast<ConstantInt>(PN->getIncomingValue(i)))) 00699 break; 00700 00701 // If no incoming value has a constant, we don't know the destination of any 00702 // predecessors. 00703 if (PredCst == 0) 00704 return false; 00705 00706 // See if the cost of duplicating this block is low enough. 00707 BasicBlock *BB = PN->getParent(); 00708 unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB); 00709 if (JumpThreadCost > Threshold) { 00710 DEBUG(errs() << " Not threading BB '" << BB->getName() 00711 << "' - Cost is too high: " << JumpThreadCost << "\n"); 00712 return false; 00713 } 00714 00715 // If so, we can actually do this threading. Merge any common predecessors 00716 // that will act the same. 00717 BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst); 00718 00719 // Next, figure out which successor we are threading to. 00720 BasicBlock *SuccBB; 00721 if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) 00722 SuccBB = BI->getSuccessor(PredCst == 00723 ConstantInt::getFalse(PredBB->getContext())); 00724 else { 00725 SwitchInst *SI = cast<SwitchInst>(BB->getTerminator()); 00726 SuccBB = SI->getSuccessor(SI->findCaseValue(PredCst)); 00727 } 00728 00729 // Ok, try to thread it! 00730 return ThreadEdge(BB, PredBB, SuccBB, JumpThreadCost); 00731 } 00732 00733 /// ProcessJumpOnLogicalPHI - PN's basic block contains a conditional branch 00734 /// whose condition is an AND/OR where one side is PN. If PN has constant 00735 /// operands that permit us to evaluate the condition for some operand, thread 00736 /// through the block. For example with: 00737 /// br (and X, phi(Y, Z, false)) 00738 /// the predecessor corresponding to the 'false' will always jump to the false 00739 /// destination of the branch. 00740 /// 00741 bool JumpThreading::ProcessBranchOnLogical(Value *V, BasicBlock *BB, 00742 bool isAnd) { 00743 // If this is a binary operator tree of the same AND/OR opcode, check the 00744 // LHS/RHS. 00745 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V)) 00746 if ((isAnd && BO->getOpcode() == Instruction::And) || 00747 (!isAnd && BO->getOpcode() == Instruction::Or)) { 00748 if (ProcessBranchOnLogical(BO->getOperand(0), BB, isAnd)) 00749 return true; 00750 if (ProcessBranchOnLogical(BO->getOperand(1), BB, isAnd)) 00751 return true; 00752 } 00753 00754 // If this isn't a PHI node, we can't handle it. 00755 PHINode *PN = dyn_cast<PHINode>(V); 00756 if (!PN || PN->getParent() != BB) return false; 00757 00758 // We can only do the simplification for phi nodes of 'false' with AND or 00759 // 'true' with OR. See if we have any entries in the phi for this. 00760 unsigned PredNo = ~0U; 00761 ConstantInt *PredCst = ConstantInt::get(Type::getInt1Ty(BB->getContext()), 00762 !isAnd); 00763 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 00764 if (PN->getIncomingValue(i) == PredCst) { 00765 PredNo = i; 00766 break; 00767 } 00768 } 00769 00770 // If no match, bail out. 00771 if (PredNo == ~0U) 00772 return false; 00773 00774 // See if the cost of duplicating this block is low enough. 00775 unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB); 00776 if (JumpThreadCost > Threshold) { 00777 DEBUG(errs() << " Not threading BB '" << BB->getName() 00778 << "' - Cost is too high: " << JumpThreadCost << "\n"); 00779 return false; 00780 } 00781 00782 // If so, we can actually do this threading. Merge any common predecessors 00783 // that will act the same. 00784 BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst); 00785 00786 // Next, figure out which successor we are threading to. If this was an AND, 00787 // the constant must be FALSE, and we must be targeting the 'false' block. 00788 // If this is an OR, the constant must be TRUE, and we must be targeting the 00789 // 'true' block. 00790 BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(isAnd); 00791 00792 // Ok, try to thread it! 00793 return ThreadEdge(BB, PredBB, SuccBB, JumpThreadCost); 00794 } 00795 00796 /// GetResultOfComparison - Given an icmp/fcmp predicate and the left and right 00797 /// hand sides of the compare instruction, try to determine the result. If the 00798 /// result can not be determined, a null pointer is returned. 00799 static Constant *GetResultOfComparison(CmpInst::Predicate pred, 00800 Value *LHS, Value *RHS, 00801 LLVMContext &Context) { 00802 if (Constant *CLHS = dyn_cast<Constant>(LHS)) 00803 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 00804 return ConstantExpr::getCompare(pred, CLHS, CRHS); 00805 00806 if (LHS == RHS) 00807 if (isa<IntegerType>(LHS->getType()) || isa<PointerType>(LHS->getType())) 00808 return ICmpInst::isTrueWhenEqual(pred) ? 00809 ConstantInt::getTrue(Context) : ConstantInt::getFalse(Context); 00810 00811 return 0; 00812 } 00813 00814 /// ProcessBranchOnCompare - We found a branch on a comparison between a phi 00815 /// node and a value. If we can identify when the comparison is true between 00816 /// the phi inputs and the value, we can fold the compare for that edge and 00817 /// thread through it. 00818 bool JumpThreading::ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB) { 00819 PHINode *PN = cast<PHINode>(Cmp->getOperand(0)); 00820 Value *RHS = Cmp->getOperand(1); 00821 00822 // If the phi isn't in the current block, an incoming edge to this block 00823 // doesn't control the destination. 00824 if (PN->getParent() != BB) 00825 return false; 00826 00827 // We can do this simplification if any comparisons fold to true or false. 00828 // See if any do. 00829 Value *PredVal = 0; 00830 bool TrueDirection = false; 00831 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 00832 PredVal = PN->getIncomingValue(i); 00833 00834 Constant *Res = GetResultOfComparison(Cmp->getPredicate(), PredVal, 00835 RHS, Cmp->getContext()); 00836 if (!Res) { 00837 PredVal = 0; 00838 continue; 00839 } 00840 00841 // If this folded to a constant expr, we can't do anything. 00842 if (ConstantInt *ResC = dyn_cast<ConstantInt>(Res)) { 00843 TrueDirection = ResC->getZExtValue(); 00844 break; 00845 } 00846 // If this folded to undef, just go the false way. 00847 if (isa<UndefValue>(Res)) { 00848 TrueDirection = false; 00849 break; 00850 } 00851 00852 // Otherwise, we can't fold this input. 00853 PredVal = 0; 00854 } 00855 00856 // If no match, bail out. 00857 if (PredVal == 0) 00858 return false; 00859 00860 // See if the cost of duplicating this block is low enough. 00861 unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB); 00862 if (JumpThreadCost > Threshold) { 00863 DEBUG(errs() << " Not threading BB '" << BB->getName() 00864 << "' - Cost is too high: " << JumpThreadCost << "\n"); 00865 return false; 00866 } 00867 00868 // If so, we can actually do this threading. Merge any common predecessors 00869 // that will act the same. 00870 BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredVal); 00871 00872 // Next, get our successor. 00873 BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(!TrueDirection); 00874 00875 // Ok, try to thread it! 00876 return ThreadEdge(BB, PredBB, SuccBB, JumpThreadCost); 00877 } 00878 00879 00880 /// ThreadEdge - We have decided that it is safe and profitable to thread an 00881 /// edge from PredBB to SuccBB across BB. Transform the IR to reflect this 00882 /// change. 00883 bool JumpThreading::ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, 00884 BasicBlock *SuccBB, unsigned JumpThreadCost) { 00885 00886 // If threading to the same block as we come from, we would infinite loop. 00887 if (SuccBB == BB) { 00888 DEBUG(errs() << " Not threading across BB '" << BB->getName() 00889 << "' - would thread to self!\n"); 00890 return false; 00891 } 00892 00893 // If threading this would thread across a loop header, don't thread the edge. 00894 // See the comments above FindLoopHeaders for justifications and caveats. 00895 if (LoopHeaders.count(BB)) { 00896 DEBUG(errs() << " Not threading from '" << PredBB->getName() 00897 << "' across loop header BB '" << BB->getName() 00898 << "' to dest BB '" << SuccBB->getName() 00899 << "' - it might create an irreducible loop!\n"); 00900 return false; 00901 } 00902 00903 // And finally, do it! 00904 DEBUG(errs() << " Threading edge from '" << PredBB->getName() << "' to '" 00905 << SuccBB->getName() << "' with cost: " << JumpThreadCost 00906 << ", across block:\n " 00907 << *BB << "\n"); 00908 00909 // Jump Threading can not update SSA properties correctly if the values 00910 // defined in the duplicated block are used outside of the block itself. For 00911 // this reason, we spill all values that are used outside of BB to the stack. 00912 for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) { 00913 if (!I->isUsedOutsideOfBlock(BB)) 00914 continue; 00915 00916 // We found a use of I outside of BB. Create a new stack slot to 00917 // break this inter-block usage pattern. 00918 DemoteRegToStack(*I); 00919 } 00920 00921 // We are going to have to map operands from the original BB block to the new 00922 // copy of the block 'NewBB'. If there are PHI nodes in BB, evaluate them to 00923 // account for entry from PredBB. 00924 DenseMap<Instruction*, Value*> ValueMapping; 00925 00926 BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), 00927 BB->getName()+".thread", 00928 BB->getParent(), BB); 00929 NewBB->moveAfter(PredBB); 00930 00931 BasicBlock::iterator BI = BB->begin(); 00932 for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI) 00933 ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB); 00934 00935 // Clone the non-phi instructions of BB into NewBB, keeping track of the 00936 // mapping and using it to remap operands in the cloned instructions. 00937 for (; !isa<TerminatorInst>(BI); ++BI) { 00938 Instruction *New = BI->clone(BI->getContext()); 00939 New->setName(BI->getName()); 00940 NewBB->getInstList().push_back(New); 00941 ValueMapping[BI] = New; 00942 00943 // Remap operands to patch up intra-block references. 00944 for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i) 00945 if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) { 00946 DenseMap<Instruction*, Value*>::iterator I = ValueMapping.find(Inst); 00947 if (I != ValueMapping.end()) 00948 New->setOperand(i, I->second); 00949 } 00950 } 00951 00952 // We didn't copy the terminator from BB over to NewBB, because there is now 00953 // an unconditional jump to SuccBB. Insert the unconditional jump. 00954 BranchInst::Create(SuccBB, NewBB); 00955 00956 // Check to see if SuccBB has PHI nodes. If so, we need to add entries to the 00957 // PHI nodes for NewBB now. 00958 for (BasicBlock::iterator PNI = SuccBB->begin(); isa<PHINode>(PNI); ++PNI) { 00959 PHINode *PN = cast<PHINode>(PNI); 00960 // Ok, we have a PHI node. Figure out what the incoming value was for the 00961 // DestBlock. 00962 Value *IV = PN->getIncomingValueForBlock(BB); 00963 00964 // Remap the value if necessary. 00965 if (Instruction *Inst = dyn_cast<Instruction>(IV)) { 00966 DenseMap<Instruction*, Value*>::iterator I = ValueMapping.find(Inst); 00967 if (I != ValueMapping.end()) 00968 IV = I->second; 00969 } 00970 PN->addIncoming(IV, NewBB); 00971 } 00972 00973 // Ok, NewBB is good to go. Update the terminator of PredBB to jump to 00974 // NewBB instead of BB. This eliminates predecessors from BB, which requires 00975 // us to simplify any PHI nodes in BB. 00976 TerminatorInst *PredTerm = PredBB->getTerminator(); 00977 for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i) 00978 if (PredTerm->getSuccessor(i) == BB) { 00979 BB->removePredecessor(PredBB); 00980 PredTerm->setSuccessor(i, NewBB); 00981 } 00982 00983 // At this point, the IR is fully up to date and consistent. Do a quick scan 00984 // over the new instructions and zap any that are constants or dead. This 00985 // frequently happens because of phi translation. 00986 BI = NewBB->begin(); 00987 for (BasicBlock::iterator E = NewBB->end(); BI != E; ) { 00988 Instruction *Inst = BI++; 00989 if (Constant *C = ConstantFoldInstruction(Inst, BB->getContext(), TD)) { 00990 Inst->replaceAllUsesWith(C); 00991 Inst->eraseFromParent(); 00992 continue; 00993 } 00994 00995 RecursivelyDeleteTriviallyDeadInstructions(Inst); 00996 } 00997 00998 // Threaded an edge! 00999 ++NumThreads; 01000 return true; 01001 }