LLVM API Documentation
00001 //===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===// 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 // Peephole optimize the CFG. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #define DEBUG_TYPE "simplifycfg" 00015 #include "llvm/Transforms/Utils/Local.h" 00016 #include "llvm/Constants.h" 00017 #include "llvm/Instructions.h" 00018 #include "llvm/IntrinsicInst.h" 00019 #include "llvm/LLVMContext.h" 00020 #include "llvm/Type.h" 00021 #include "llvm/DerivedTypes.h" 00022 #include "llvm/GlobalVariable.h" 00023 #include "llvm/Support/CFG.h" 00024 #include "llvm/Support/Debug.h" 00025 #include "llvm/Support/raw_ostream.h" 00026 #include "llvm/Analysis/ConstantFolding.h" 00027 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 00028 #include "llvm/ADT/SmallVector.h" 00029 #include "llvm/ADT/SmallPtrSet.h" 00030 #include "llvm/ADT/Statistic.h" 00031 #include <algorithm> 00032 #include <functional> 00033 #include <set> 00034 #include <map> 00035 using namespace llvm; 00036 00037 STATISTIC(NumSpeculations, "Number of speculative executed instructions"); 00038 00039 /// SafeToMergeTerminators - Return true if it is safe to merge these two 00040 /// terminator instructions together. 00041 /// 00042 static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) { 00043 if (SI1 == SI2) return false; // Can't merge with self! 00044 00045 // It is not safe to merge these two switch instructions if they have a common 00046 // successor, and if that successor has a PHI node, and if *that* PHI node has 00047 // conflicting incoming values from the two switch blocks. 00048 BasicBlock *SI1BB = SI1->getParent(); 00049 BasicBlock *SI2BB = SI2->getParent(); 00050 SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 00051 00052 for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) 00053 if (SI1Succs.count(*I)) 00054 for (BasicBlock::iterator BBI = (*I)->begin(); 00055 isa<PHINode>(BBI); ++BBI) { 00056 PHINode *PN = cast<PHINode>(BBI); 00057 if (PN->getIncomingValueForBlock(SI1BB) != 00058 PN->getIncomingValueForBlock(SI2BB)) 00059 return false; 00060 } 00061 00062 return true; 00063 } 00064 00065 /// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will 00066 /// now be entries in it from the 'NewPred' block. The values that will be 00067 /// flowing into the PHI nodes will be the same as those coming in from 00068 /// ExistPred, an existing predecessor of Succ. 00069 static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, 00070 BasicBlock *ExistPred) { 00071 assert(std::find(succ_begin(ExistPred), succ_end(ExistPred), Succ) != 00072 succ_end(ExistPred) && "ExistPred is not a predecessor of Succ!"); 00073 if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do 00074 00075 PHINode *PN; 00076 for (BasicBlock::iterator I = Succ->begin(); 00077 (PN = dyn_cast<PHINode>(I)); ++I) 00078 PN->addIncoming(PN->getIncomingValueForBlock(ExistPred), NewPred); 00079 } 00080 00081 /// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an 00082 /// almost-empty BB ending in an unconditional branch to Succ, into succ. 00083 /// 00084 /// Assumption: Succ is the single successor for BB. 00085 /// 00086 static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 00087 assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 00088 00089 DEBUG(errs() << "Looking to fold " << BB->getName() << " into " 00090 << Succ->getName() << "\n"); 00091 // Shortcut, if there is only a single predecessor it must be BB and merging 00092 // is always safe 00093 if (Succ->getSinglePredecessor()) return true; 00094 00095 // Make a list of the predecessors of BB 00096 typedef SmallPtrSet<BasicBlock*, 16> BlockSet; 00097 BlockSet BBPreds(pred_begin(BB), pred_end(BB)); 00098 00099 // Use that list to make another list of common predecessors of BB and Succ 00100 BlockSet CommonPreds; 00101 for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); 00102 PI != PE; ++PI) 00103 if (BBPreds.count(*PI)) 00104 CommonPreds.insert(*PI); 00105 00106 // Shortcut, if there are no common predecessors, merging is always safe 00107 if (CommonPreds.empty()) 00108 return true; 00109 00110 // Look at all the phi nodes in Succ, to see if they present a conflict when 00111 // merging these blocks 00112 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 00113 PHINode *PN = cast<PHINode>(I); 00114 00115 // If the incoming value from BB is again a PHINode in 00116 // BB which has the same incoming value for *PI as PN does, we can 00117 // merge the phi nodes and then the blocks can still be merged 00118 PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB)); 00119 if (BBPN && BBPN->getParent() == BB) { 00120 for (BlockSet::iterator PI = CommonPreds.begin(), PE = CommonPreds.end(); 00121 PI != PE; PI++) { 00122 if (BBPN->getIncomingValueForBlock(*PI) 00123 != PN->getIncomingValueForBlock(*PI)) { 00124 DEBUG(errs() << "Can't fold, phi node " << PN->getName() << " in " 00125 << Succ->getName() << " is conflicting with " 00126 << BBPN->getName() << " with regard to common predecessor " 00127 << (*PI)->getName() << "\n"); 00128 return false; 00129 } 00130 } 00131 } else { 00132 Value* Val = PN->getIncomingValueForBlock(BB); 00133 for (BlockSet::iterator PI = CommonPreds.begin(), PE = CommonPreds.end(); 00134 PI != PE; PI++) { 00135 // See if the incoming value for the common predecessor is equal to the 00136 // one for BB, in which case this phi node will not prevent the merging 00137 // of the block. 00138 if (Val != PN->getIncomingValueForBlock(*PI)) { 00139 DEBUG(errs() << "Can't fold, phi node " << PN->getName() << " in " 00140 << Succ->getName() << " is conflicting with regard to common " 00141 << "predecessor " << (*PI)->getName() << "\n"); 00142 return false; 00143 } 00144 } 00145 } 00146 } 00147 00148 return true; 00149 } 00150 00151 /// TryToSimplifyUncondBranchFromEmptyBlock - BB contains an unconditional 00152 /// branch to Succ, and contains no instructions other than PHI nodes and the 00153 /// branch. If possible, eliminate BB. 00154 static bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, 00155 BasicBlock *Succ) { 00156 // Check to see if merging these blocks would cause conflicts for any of the 00157 // phi nodes in BB or Succ. If not, we can safely merge. 00158 if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; 00159 00160 // Check for cases where Succ has multiple predecessors and a PHI node in BB 00161 // has uses which will not disappear when the PHI nodes are merged. It is 00162 // possible to handle such cases, but difficult: it requires checking whether 00163 // BB dominates Succ, which is non-trivial to calculate in the case where 00164 // Succ has multiple predecessors. Also, it requires checking whether 00165 // constructing the necessary self-referential PHI node doesn't intoduce any 00166 // conflicts; this isn't too difficult, but the previous code for doing this 00167 // was incorrect. 00168 // 00169 // Note that if this check finds a live use, BB dominates Succ, so BB is 00170 // something like a loop pre-header (or rarely, a part of an irreducible CFG); 00171 // folding the branch isn't profitable in that case anyway. 00172 if (!Succ->getSinglePredecessor()) { 00173 BasicBlock::iterator BBI = BB->begin(); 00174 while (isa<PHINode>(*BBI)) { 00175 for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); 00176 UI != E; ++UI) { 00177 if (PHINode* PN = dyn_cast<PHINode>(*UI)) { 00178 if (PN->getIncomingBlock(UI) != BB) 00179 return false; 00180 } else { 00181 return false; 00182 } 00183 } 00184 ++BBI; 00185 } 00186 } 00187 00188 DOUT << "Killing Trivial BB: \n" << *BB; 00189 00190 if (isa<PHINode>(Succ->begin())) { 00191 // If there is more than one pred of succ, and there are PHI nodes in 00192 // the successor, then we need to add incoming edges for the PHI nodes 00193 // 00194 const SmallVector<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB)); 00195 00196 // Loop over all of the PHI nodes in the successor of BB. 00197 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 00198 PHINode *PN = cast<PHINode>(I); 00199 Value *OldVal = PN->removeIncomingValue(BB, false); 00200 assert(OldVal && "No entry in PHI for Pred BB!"); 00201 00202 // If this incoming value is one of the PHI nodes in BB, the new entries 00203 // in the PHI node are the entries from the old PHI. 00204 if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 00205 PHINode *OldValPN = cast<PHINode>(OldVal); 00206 for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) 00207 // Note that, since we are merging phi nodes and BB and Succ might 00208 // have common predecessors, we could end up with a phi node with 00209 // identical incoming branches. This will be cleaned up later (and 00210 // will trigger asserts if we try to clean it up now, without also 00211 // simplifying the corresponding conditional branch). 00212 PN->addIncoming(OldValPN->getIncomingValue(i), 00213 OldValPN->getIncomingBlock(i)); 00214 } else { 00215 // Add an incoming value for each of the new incoming values. 00216 for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) 00217 PN->addIncoming(OldVal, BBPreds[i]); 00218 } 00219 } 00220 } 00221 00222 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 00223 if (Succ->getSinglePredecessor()) { 00224 // BB is the only predecessor of Succ, so Succ will end up with exactly 00225 // the same predecessors BB had. 00226 Succ->getInstList().splice(Succ->begin(), 00227 BB->getInstList(), BB->begin()); 00228 } else { 00229 // We explicitly check for such uses in CanPropagatePredecessorsForPHIs. 00230 assert(PN->use_empty() && "There shouldn't be any uses here!"); 00231 PN->eraseFromParent(); 00232 } 00233 } 00234 00235 // Everything that jumped to BB now goes to Succ. 00236 BB->replaceAllUsesWith(Succ); 00237 if (!Succ->hasName()) Succ->takeName(BB); 00238 BB->eraseFromParent(); // Delete the old basic block. 00239 return true; 00240 } 00241 00242 /// GetIfCondition - Given a basic block (BB) with two predecessors (and 00243 /// presumably PHI nodes in it), check to see if the merge at this block is due 00244 /// to an "if condition". If so, return the boolean condition that determines 00245 /// which entry into BB will be taken. Also, return by references the block 00246 /// that will be entered from if the condition is true, and the block that will 00247 /// be entered if the condition is false. 00248 /// 00249 /// 00250 static Value *GetIfCondition(BasicBlock *BB, 00251 BasicBlock *&IfTrue, BasicBlock *&IfFalse) { 00252 assert(std::distance(pred_begin(BB), pred_end(BB)) == 2 && 00253 "Function can only handle blocks with 2 predecessors!"); 00254 BasicBlock *Pred1 = *pred_begin(BB); 00255 BasicBlock *Pred2 = *++pred_begin(BB); 00256 00257 // We can only handle branches. Other control flow will be lowered to 00258 // branches if possible anyway. 00259 if (!isa<BranchInst>(Pred1->getTerminator()) || 00260 !isa<BranchInst>(Pred2->getTerminator())) 00261 return 0; 00262 BranchInst *Pred1Br = cast<BranchInst>(Pred1->getTerminator()); 00263 BranchInst *Pred2Br = cast<BranchInst>(Pred2->getTerminator()); 00264 00265 // Eliminate code duplication by ensuring that Pred1Br is conditional if 00266 // either are. 00267 if (Pred2Br->isConditional()) { 00268 // If both branches are conditional, we don't have an "if statement". In 00269 // reality, we could transform this case, but since the condition will be 00270 // required anyway, we stand no chance of eliminating it, so the xform is 00271 // probably not profitable. 00272 if (Pred1Br->isConditional()) 00273 return 0; 00274 00275 std::swap(Pred1, Pred2); 00276 std::swap(Pred1Br, Pred2Br); 00277 } 00278 00279 if (Pred1Br->isConditional()) { 00280 // If we found a conditional branch predecessor, make sure that it branches 00281 // to BB and Pred2Br. If it doesn't, this isn't an "if statement". 00282 if (Pred1Br->getSuccessor(0) == BB && 00283 Pred1Br->getSuccessor(1) == Pred2) { 00284 IfTrue = Pred1; 00285 IfFalse = Pred2; 00286 } else if (Pred1Br->getSuccessor(0) == Pred2 && 00287 Pred1Br->getSuccessor(1) == BB) { 00288 IfTrue = Pred2; 00289 IfFalse = Pred1; 00290 } else { 00291 // We know that one arm of the conditional goes to BB, so the other must 00292 // go somewhere unrelated, and this must not be an "if statement". 00293 return 0; 00294 } 00295 00296 // The only thing we have to watch out for here is to make sure that Pred2 00297 // doesn't have incoming edges from other blocks. If it does, the condition 00298 // doesn't dominate BB. 00299 if (++pred_begin(Pred2) != pred_end(Pred2)) 00300 return 0; 00301 00302 return Pred1Br->getCondition(); 00303 } 00304 00305 // Ok, if we got here, both predecessors end with an unconditional branch to 00306 // BB. Don't panic! If both blocks only have a single (identical) 00307 // predecessor, and THAT is a conditional branch, then we're all ok! 00308 if (pred_begin(Pred1) == pred_end(Pred1) || 00309 ++pred_begin(Pred1) != pred_end(Pred1) || 00310 pred_begin(Pred2) == pred_end(Pred2) || 00311 ++pred_begin(Pred2) != pred_end(Pred2) || 00312 *pred_begin(Pred1) != *pred_begin(Pred2)) 00313 return 0; 00314 00315 // Otherwise, if this is a conditional branch, then we can use it! 00316 BasicBlock *CommonPred = *pred_begin(Pred1); 00317 if (BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator())) { 00318 assert(BI->isConditional() && "Two successors but not conditional?"); 00319 if (BI->getSuccessor(0) == Pred1) { 00320 IfTrue = Pred1; 00321 IfFalse = Pred2; 00322 } else { 00323 IfTrue = Pred2; 00324 IfFalse = Pred1; 00325 } 00326 return BI->getCondition(); 00327 } 00328 return 0; 00329 } 00330 00331 /// DominatesMergePoint - If we have a merge point of an "if condition" as 00332 /// accepted above, return true if the specified value dominates the block. We 00333 /// don't handle the true generality of domination here, just a special case 00334 /// which works well enough for us. 00335 /// 00336 /// If AggressiveInsts is non-null, and if V does not dominate BB, we check to 00337 /// see if V (which must be an instruction) is cheap to compute and is 00338 /// non-trapping. If both are true, the instruction is inserted into the set 00339 /// and true is returned. 00340 static bool DominatesMergePoint(Value *V, BasicBlock *BB, 00341 std::set<Instruction*> *AggressiveInsts) { 00342 Instruction *I = dyn_cast<Instruction>(V); 00343 if (!I) { 00344 // Non-instructions all dominate instructions, but not all constantexprs 00345 // can be executed unconditionally. 00346 if (ConstantExpr *C = dyn_cast<ConstantExpr>(V)) 00347 if (C->canTrap()) 00348 return false; 00349 return true; 00350 } 00351 BasicBlock *PBB = I->getParent(); 00352 00353 // We don't want to allow weird loops that might have the "if condition" in 00354 // the bottom of this block. 00355 if (PBB == BB) return false; 00356 00357 // If this instruction is defined in a block that contains an unconditional 00358 // branch to BB, then it must be in the 'conditional' part of the "if 00359 // statement". 00360 if (BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator())) 00361 if (BI->isUnconditional() && BI->getSuccessor(0) == BB) { 00362 if (!AggressiveInsts) return false; 00363 // Okay, it looks like the instruction IS in the "condition". Check to 00364 // see if its a cheap instruction to unconditionally compute, and if it 00365 // only uses stuff defined outside of the condition. If so, hoist it out. 00366 if (!I->isSafeToSpeculativelyExecute()) 00367 return false; 00368 00369 switch (I->getOpcode()) { 00370 default: return false; // Cannot hoist this out safely. 00371 case Instruction::Load: { 00372 // We have to check to make sure there are no instructions before the 00373 // load in its basic block, as we are going to hoist the loop out to 00374 // its predecessor. 00375 BasicBlock::iterator IP = PBB->begin(); 00376 while (isa<DbgInfoIntrinsic>(IP)) 00377 IP++; 00378 if (IP != BasicBlock::iterator(I)) 00379 return false; 00380 break; 00381 } 00382 case Instruction::Add: 00383 case Instruction::Sub: 00384 case Instruction::And: 00385 case Instruction::Or: 00386 case Instruction::Xor: 00387 case Instruction::Shl: 00388 case Instruction::LShr: 00389 case Instruction::AShr: 00390 case Instruction::ICmp: 00391 break; // These are all cheap and non-trapping instructions. 00392 } 00393 00394 // Okay, we can only really hoist these out if their operands are not 00395 // defined in the conditional region. 00396 for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) 00397 if (!DominatesMergePoint(*i, BB, 0)) 00398 return false; 00399 // Okay, it's safe to do this! Remember this instruction. 00400 AggressiveInsts->insert(I); 00401 } 00402 00403 return true; 00404 } 00405 00406 /// GatherConstantSetEQs - Given a potentially 'or'd together collection of 00407 /// icmp_eq instructions that compare a value against a constant, return the 00408 /// value being compared, and stick the constant into the Values vector. 00409 static Value *GatherConstantSetEQs(Value *V, std::vector<ConstantInt*> &Values){ 00410 if (Instruction *Inst = dyn_cast<Instruction>(V)) { 00411 if (Inst->getOpcode() == Instruction::ICmp && 00412 cast<ICmpInst>(Inst)->getPredicate() == ICmpInst::ICMP_EQ) { 00413 if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) { 00414 Values.push_back(C); 00415 return Inst->getOperand(0); 00416 } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) { 00417 Values.push_back(C); 00418 return Inst->getOperand(1); 00419 } 00420 } else if (Inst->getOpcode() == Instruction::Or) { 00421 if (Value *LHS = GatherConstantSetEQs(Inst->getOperand(0), Values)) 00422 if (Value *RHS = GatherConstantSetEQs(Inst->getOperand(1), Values)) 00423 if (LHS == RHS) 00424 return LHS; 00425 } 00426 } 00427 return 0; 00428 } 00429 00430 /// GatherConstantSetNEs - Given a potentially 'and'd together collection of 00431 /// setne instructions that compare a value against a constant, return the value 00432 /// being compared, and stick the constant into the Values vector. 00433 static Value *GatherConstantSetNEs(Value *V, std::vector<ConstantInt*> &Values){ 00434 if (Instruction *Inst = dyn_cast<Instruction>(V)) { 00435 if (Inst->getOpcode() == Instruction::ICmp && 00436 cast<ICmpInst>(Inst)->getPredicate() == ICmpInst::ICMP_NE) { 00437 if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) { 00438 Values.push_back(C); 00439 return Inst->getOperand(0); 00440 } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) { 00441 Values.push_back(C); 00442 return Inst->getOperand(1); 00443 } 00444 } else if (Inst->getOpcode() == Instruction::And) { 00445 if (Value *LHS = GatherConstantSetNEs(Inst->getOperand(0), Values)) 00446 if (Value *RHS = GatherConstantSetNEs(Inst->getOperand(1), Values)) 00447 if (LHS == RHS) 00448 return LHS; 00449 } 00450 } 00451 return 0; 00452 } 00453 00454 /// GatherValueComparisons - If the specified Cond is an 'and' or 'or' of a 00455 /// bunch of comparisons of one value against constants, return the value and 00456 /// the constants being compared. 00457 static bool GatherValueComparisons(Instruction *Cond, Value *&CompVal, 00458 std::vector<ConstantInt*> &Values) { 00459 if (Cond->getOpcode() == Instruction::Or) { 00460 CompVal = GatherConstantSetEQs(Cond, Values); 00461 00462 // Return true to indicate that the condition is true if the CompVal is 00463 // equal to one of the constants. 00464 return true; 00465 } else if (Cond->getOpcode() == Instruction::And) { 00466 CompVal = GatherConstantSetNEs(Cond, Values); 00467 00468 // Return false to indicate that the condition is false if the CompVal is 00469 // equal to one of the constants. 00470 return false; 00471 } 00472 return false; 00473 } 00474 00475 static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) { 00476 Instruction* Cond = 0; 00477 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 00478 Cond = dyn_cast<Instruction>(SI->getCondition()); 00479 } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 00480 if (BI->isConditional()) 00481 Cond = dyn_cast<Instruction>(BI->getCondition()); 00482 } 00483 00484 TI->eraseFromParent(); 00485 if (Cond) RecursivelyDeleteTriviallyDeadInstructions(Cond); 00486 } 00487 00488 /// isValueEqualityComparison - Return true if the specified terminator checks 00489 /// to see if a value is equal to constant integer value. 00490 static Value *isValueEqualityComparison(TerminatorInst *TI) { 00491 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 00492 // Do not permit merging of large switch instructions into their 00493 // predecessors unless there is only one predecessor. 00494 if (SI->getNumSuccessors() * std::distance(pred_begin(SI->getParent()), 00495 pred_end(SI->getParent())) > 128) 00496 return 0; 00497 00498 return SI->getCondition(); 00499 } 00500 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 00501 if (BI->isConditional() && BI->getCondition()->hasOneUse()) 00502 if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) 00503 if ((ICI->getPredicate() == ICmpInst::ICMP_EQ || 00504 ICI->getPredicate() == ICmpInst::ICMP_NE) && 00505 isa<ConstantInt>(ICI->getOperand(1))) 00506 return ICI->getOperand(0); 00507 return 0; 00508 } 00509 00510 /// GetValueEqualityComparisonCases - Given a value comparison instruction, 00511 /// decode all of the 'cases' that it represents and return the 'default' block. 00512 static BasicBlock * 00513 GetValueEqualityComparisonCases(TerminatorInst *TI, 00514 std::vector<std::pair<ConstantInt*, 00515 BasicBlock*> > &Cases) { 00516 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 00517 Cases.reserve(SI->getNumCases()); 00518 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 00519 Cases.push_back(std::make_pair(SI->getCaseValue(i), SI->getSuccessor(i))); 00520 return SI->getDefaultDest(); 00521 } 00522 00523 BranchInst *BI = cast<BranchInst>(TI); 00524 ICmpInst *ICI = cast<ICmpInst>(BI->getCondition()); 00525 Cases.push_back(std::make_pair(cast<ConstantInt>(ICI->getOperand(1)), 00526 BI->getSuccessor(ICI->getPredicate() == 00527 ICmpInst::ICMP_NE))); 00528 return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ); 00529 } 00530 00531 00532 /// EliminateBlockCases - Given a vector of bb/value pairs, remove any entries 00533 /// in the list that match the specified block. 00534 static void EliminateBlockCases(BasicBlock *BB, 00535 std::vector<std::pair<ConstantInt*, BasicBlock*> > &Cases) { 00536 for (unsigned i = 0, e = Cases.size(); i != e; ++i) 00537 if (Cases[i].second == BB) { 00538 Cases.erase(Cases.begin()+i); 00539 --i; --e; 00540 } 00541 } 00542 00543 /// ValuesOverlap - Return true if there are any keys in C1 that exist in C2 as 00544 /// well. 00545 static bool 00546 ValuesOverlap(std::vector<std::pair<ConstantInt*, BasicBlock*> > &C1, 00547 std::vector<std::pair<ConstantInt*, BasicBlock*> > &C2) { 00548 std::vector<std::pair<ConstantInt*, BasicBlock*> > *V1 = &C1, *V2 = &C2; 00549 00550 // Make V1 be smaller than V2. 00551 if (V1->size() > V2->size()) 00552 std::swap(V1, V2); 00553 00554 if (V1->size() == 0) return false; 00555 if (V1->size() == 1) { 00556 // Just scan V2. 00557 ConstantInt *TheVal = (*V1)[0].first; 00558 for (unsigned i = 0, e = V2->size(); i != e; ++i) 00559 if (TheVal == (*V2)[i].first) 00560 return true; 00561 } 00562 00563 // Otherwise, just sort both lists and compare element by element. 00564 std::sort(V1->begin(), V1->end()); 00565 std::sort(V2->begin(), V2->end()); 00566 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size(); 00567 while (i1 != e1 && i2 != e2) { 00568 if ((*V1)[i1].first == (*V2)[i2].first) 00569 return true; 00570 if ((*V1)[i1].first < (*V2)[i2].first) 00571 ++i1; 00572 else 00573 ++i2; 00574 } 00575 return false; 00576 } 00577 00578 /// SimplifyEqualityComparisonWithOnlyPredecessor - If TI is known to be a 00579 /// terminator instruction and its block is known to only have a single 00580 /// predecessor block, check to see if that predecessor is also a value 00581 /// comparison with the same value, and if that comparison determines the 00582 /// outcome of this comparison. If so, simplify TI. This does a very limited 00583 /// form of jump threading. 00584 static bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, 00585 BasicBlock *Pred) { 00586 Value *PredVal = isValueEqualityComparison(Pred->getTerminator()); 00587 if (!PredVal) return false; // Not a value comparison in predecessor. 00588 00589 Value *ThisVal = isValueEqualityComparison(TI); 00590 assert(ThisVal && "This isn't a value comparison!!"); 00591 if (ThisVal != PredVal) return false; // Different predicates. 00592 00593 // Find out information about when control will move from Pred to TI's block. 00594 std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 00595 BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(), 00596 PredCases); 00597 EliminateBlockCases(PredDef, PredCases); // Remove default from cases. 00598 00599 // Find information about how control leaves this block. 00600 std::vector<std::pair<ConstantInt*, BasicBlock*> > ThisCases; 00601 BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases); 00602 EliminateBlockCases(ThisDef, ThisCases); // Remove default from cases. 00603 00604 // If TI's block is the default block from Pred's comparison, potentially 00605 // simplify TI based on this knowledge. 00606 if (PredDef == TI->getParent()) { 00607 // If we are here, we know that the value is none of those cases listed in 00608 // PredCases. If there are any cases in ThisCases that are in PredCases, we 00609 // can simplify TI. 00610 if (ValuesOverlap(PredCases, ThisCases)) { 00611 if (isa<BranchInst>(TI)) { 00612 // Okay, one of the successors of this condbr is dead. Convert it to a 00613 // uncond br. 00614 assert(ThisCases.size() == 1 && "Branch can only have one case!"); 00615 // Insert the new branch. 00616 Instruction *NI = BranchInst::Create(ThisDef, TI); 00617 00618 // Remove PHI node entries for the dead edge. 00619 ThisCases[0].second->removePredecessor(TI->getParent()); 00620 00621 DOUT << "Threading pred instr: " << *Pred->getTerminator() 00622 << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"; 00623 00624 EraseTerminatorInstAndDCECond(TI); 00625 return true; 00626 00627 } else { 00628 SwitchInst *SI = cast<SwitchInst>(TI); 00629 // Okay, TI has cases that are statically dead, prune them away. 00630 SmallPtrSet<Constant*, 16> DeadCases; 00631 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 00632 DeadCases.insert(PredCases[i].first); 00633 00634 DOUT << "Threading pred instr: " << *Pred->getTerminator() 00635 << "Through successor TI: " << *TI; 00636 00637 for (unsigned i = SI->getNumCases()-1; i != 0; --i) 00638 if (DeadCases.count(SI->getCaseValue(i))) { 00639 SI->getSuccessor(i)->removePredecessor(TI->getParent()); 00640 SI->removeCase(i); 00641 } 00642 00643 DOUT << "Leaving: " << *TI << "\n"; 00644 return true; 00645 } 00646 } 00647 00648 } else { 00649 // Otherwise, TI's block must correspond to some matched value. Find out 00650 // which value (or set of values) this is. 00651 ConstantInt *TIV = 0; 00652 BasicBlock *TIBB = TI->getParent(); 00653 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 00654 if (PredCases[i].second == TIBB) { 00655 if (TIV == 0) 00656 TIV = PredCases[i].first; 00657 else 00658 return false; // Cannot handle multiple values coming to this block. 00659 } 00660 assert(TIV && "No edge from pred to succ?"); 00661 00662 // Okay, we found the one constant that our value can be if we get into TI's 00663 // BB. Find out which successor will unconditionally be branched to. 00664 BasicBlock *TheRealDest = 0; 00665 for (unsigned i = 0, e = ThisCases.size(); i != e; ++i) 00666 if (ThisCases[i].first == TIV) { 00667 TheRealDest = ThisCases[i].second; 00668 break; 00669 } 00670 00671 // If not handled by any explicit cases, it is handled by the default case. 00672 if (TheRealDest == 0) TheRealDest = ThisDef; 00673 00674 // Remove PHI node entries for dead edges. 00675 BasicBlock *CheckEdge = TheRealDest; 00676 for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI) 00677 if (*SI != CheckEdge) 00678 (*SI)->removePredecessor(TIBB); 00679 else 00680 CheckEdge = 0; 00681 00682 // Insert the new branch. 00683 Instruction *NI = BranchInst::Create(TheRealDest, TI); 00684 00685 DOUT << "Threading pred instr: " << *Pred->getTerminator() 00686 << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"; 00687 00688 EraseTerminatorInstAndDCECond(TI); 00689 return true; 00690 } 00691 return false; 00692 } 00693 00694 namespace { 00695 /// ConstantIntOrdering - This class implements a stable ordering of constant 00696 /// integers that does not depend on their address. This is important for 00697 /// applications that sort ConstantInt's to ensure uniqueness. 00698 struct ConstantIntOrdering { 00699 bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { 00700 return LHS->getValue().ult(RHS->getValue()); 00701 } 00702 }; 00703 } 00704 00705 /// FoldValueComparisonIntoPredecessors - The specified terminator is a value 00706 /// equality comparison instruction (either a switch or a branch on "X == c"). 00707 /// See if any of the predecessors of the terminator block are value comparisons 00708 /// on the same value. If so, and if safe to do so, fold them together. 00709 static bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { 00710 BasicBlock *BB = TI->getParent(); 00711 Value *CV = isValueEqualityComparison(TI); // CondVal 00712 assert(CV && "Not a comparison?"); 00713 bool Changed = false; 00714 00715 SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB)); 00716 while (!Preds.empty()) { 00717 BasicBlock *Pred = Preds.pop_back_val(); 00718 00719 // See if the predecessor is a comparison with the same value. 00720 TerminatorInst *PTI = Pred->getTerminator(); 00721 Value *PCV = isValueEqualityComparison(PTI); // PredCondVal 00722 00723 if (PCV == CV && SafeToMergeTerminators(TI, PTI)) { 00724 // Figure out which 'cases' to copy from SI to PSI. 00725 std::vector<std::pair<ConstantInt*, BasicBlock*> > BBCases; 00726 BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases); 00727 00728 std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 00729 BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases); 00730 00731 // Based on whether the default edge from PTI goes to BB or not, fill in 00732 // PredCases and PredDefault with the new switch cases we would like to 00733 // build. 00734 SmallVector<BasicBlock*, 8> NewSuccessors; 00735 00736 if (PredDefault == BB) { 00737 // If this is the default destination from PTI, only the edges in TI 00738 // that don't occur in PTI, or that branch to BB will be activated. 00739 std::set<ConstantInt*, ConstantIntOrdering> PTIHandled; 00740 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 00741 if (PredCases[i].second != BB) 00742 PTIHandled.insert(PredCases[i].first); 00743 else { 00744 // The default destination is BB, we don't need explicit targets. 00745 std::swap(PredCases[i], PredCases.back()); 00746 PredCases.pop_back(); 00747 --i; --e; 00748 } 00749 00750 // Reconstruct the new switch statement we will be building. 00751 if (PredDefault != BBDefault) { 00752 PredDefault->removePredecessor(Pred); 00753 PredDefault = BBDefault; 00754 NewSuccessors.push_back(BBDefault); 00755 } 00756 for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 00757 if (!PTIHandled.count(BBCases[i].first) && 00758 BBCases[i].second != BBDefault) { 00759 PredCases.push_back(BBCases[i]); 00760 NewSuccessors.push_back(BBCases[i].second); 00761 } 00762 00763 } else { 00764 // If this is not the default destination from PSI, only the edges 00765 // in SI that occur in PSI with a destination of BB will be 00766 // activated. 00767 std::set<ConstantInt*, ConstantIntOrdering> PTIHandled; 00768 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 00769 if (PredCases[i].second == BB) { 00770 PTIHandled.insert(PredCases[i].first); 00771 std::swap(PredCases[i], PredCases.back()); 00772 PredCases.pop_back(); 00773 --i; --e; 00774 } 00775 00776 // Okay, now we know which constants were sent to BB from the 00777 // predecessor. Figure out where they will all go now. 00778 for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 00779 if (PTIHandled.count(BBCases[i].first)) { 00780 // If this is one we are capable of getting... 00781 PredCases.push_back(BBCases[i]); 00782 NewSuccessors.push_back(BBCases[i].second); 00783 PTIHandled.erase(BBCases[i].first);// This constant is taken care of 00784 } 00785 00786 // If there are any constants vectored to BB that TI doesn't handle, 00787 // they must go to the default destination of TI. 00788 for (std::set<ConstantInt*, ConstantIntOrdering>::iterator I = 00789 PTIHandled.begin(), 00790 E = PTIHandled.end(); I != E; ++I) { 00791 PredCases.push_back(std::make_pair(*I, BBDefault)); 00792 NewSuccessors.push_back(BBDefault); 00793 } 00794 } 00795 00796 // Okay, at this point, we know which new successor Pred will get. Make 00797 // sure we update the number of entries in the PHI nodes for these 00798 // successors. 00799 for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i) 00800 AddPredecessorToBlock(NewSuccessors[i], Pred, BB); 00801 00802 // Now that the successors are updated, create the new Switch instruction. 00803 SwitchInst *NewSI = SwitchInst::Create(CV, PredDefault, 00804 PredCases.size(), PTI); 00805 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 00806 NewSI->addCase(PredCases[i].first, PredCases[i].second); 00807 00808 EraseTerminatorInstAndDCECond(PTI); 00809 00810 // Okay, last check. If BB is still a successor of PSI, then we must 00811 // have an infinite loop case. If so, add an infinitely looping block 00812 // to handle the case to preserve the behavior of the code. 00813 BasicBlock *InfLoopBlock = 0; 00814 for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i) 00815 if (NewSI->getSuccessor(i) == BB) { 00816 if (InfLoopBlock == 0) { 00817 // Insert it at the end of the function, because it's either code, 00818 // or it won't matter if it's hot. :) 00819 InfLoopBlock = BasicBlock::Create(BB->getContext(), 00820 "infloop", BB->getParent()); 00821 BranchInst::Create(InfLoopBlock, InfLoopBlock); 00822 } 00823 NewSI->setSuccessor(i, InfLoopBlock); 00824 } 00825 00826 Changed = true; 00827 } 00828 } 00829 return Changed; 00830 } 00831 00832 // isSafeToHoistInvoke - If we would need to insert a select that uses the 00833 // value of this invoke (comments in HoistThenElseCodeToIf explain why we 00834 // would need to do this), we can't hoist the invoke, as there is nowhere 00835 // to put the select in this case. 00836 static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, 00837 Instruction *I1, Instruction *I2) { 00838 for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 00839 PHINode *PN; 00840 for (BasicBlock::iterator BBI = SI->begin(); 00841 (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 00842 Value *BB1V = PN->getIncomingValueForBlock(BB1); 00843 Value *BB2V = PN->getIncomingValueForBlock(BB2); 00844 if (BB1V != BB2V && (BB1V==I1 || BB2V==I2)) { 00845 return false; 00846 } 00847 } 00848 } 00849 return true; 00850 } 00851 00852 /// HoistThenElseCodeToIf - Given a conditional branch that goes to BB1 and 00853 /// BB2, hoist any common code in the two blocks up into the branch block. The 00854 /// caller of this function guarantees that BI's block dominates BB1 and BB2. 00855 static bool HoistThenElseCodeToIf(BranchInst *BI) { 00856 // This does very trivial matching, with limited scanning, to find identical 00857 // instructions in the two blocks. In particular, we don't want to get into 00858 // O(M*N) situations here where M and N are the sizes of BB1 and BB2. As 00859 // such, we currently just scan for obviously identical instructions in an 00860 // identical order. 00861 BasicBlock *BB1 = BI->getSuccessor(0); // The true destination. 00862 BasicBlock *BB2 = BI->getSuccessor(1); // The false destination 00863 00864 BasicBlock::iterator BB1_Itr = BB1->begin(); 00865 BasicBlock::iterator BB2_Itr = BB2->begin(); 00866 00867 Instruction *I1 = BB1_Itr++, *I2 = BB2_Itr++; 00868 while (isa<DbgInfoIntrinsic>(I1)) 00869 I1 = BB1_Itr++; 00870 while (isa<DbgInfoIntrinsic>(I2)) 00871 I2 = BB2_Itr++; 00872 if (I1->getOpcode() != I2->getOpcode() || isa<PHINode>(I1) || 00873 !I1->isIdenticalToWhenDefined(I2) || 00874 (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2))) 00875 return false; 00876 00877 // If we get here, we can hoist at least one instruction. 00878 BasicBlock *BIParent = BI->getParent(); 00879 00880 do { 00881 // If we are hoisting the terminator instruction, don't move one (making a 00882 // broken BB), instead clone it, and remove BI. 00883 if (isa<TerminatorInst>(I1)) 00884 goto HoistTerminator; 00885 00886 // For a normal instruction, we just move one to right before the branch, 00887 // then replace all uses of the other with the first. Finally, we remove 00888 // the now redundant second instruction. 00889 BIParent->getInstList().splice(BI, BB1->getInstList(), I1); 00890 if (!I2->use_empty()) 00891 I2->replaceAllUsesWith(I1); 00892 I1->intersectOptionalDataWith(I2); 00893 BB2->getInstList().erase(I2); 00894 00895 I1 = BB1_Itr++; 00896 while (isa<DbgInfoIntrinsic>(I1)) 00897 I1 = BB1_Itr++; 00898 I2 = BB2_Itr++; 00899 while (isa<DbgInfoIntrinsic>(I2)) 00900 I2 = BB2_Itr++; 00901 } while (I1->getOpcode() == I2->getOpcode() && 00902 I1->isIdenticalToWhenDefined(I2)); 00903 00904 return true; 00905 00906 HoistTerminator: 00907 // It may not be possible to hoist an invoke. 00908 if (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)) 00909 return true; 00910 00911 // Okay, it is safe to hoist the terminator. 00912 Instruction *NT = I1->clone(BB1->getContext()); 00913 BIParent->getInstList().insert(BI, NT); 00914 if (NT->getType() != Type::getVoidTy(BB1->getContext())) { 00915 I1->replaceAllUsesWith(NT); 00916 I2->replaceAllUsesWith(NT); 00917 NT->takeName(I1); 00918 } 00919 00920 // Hoisting one of the terminators from our successor is a great thing. 00921 // Unfortunately, the successors of the if/else blocks may have PHI nodes in 00922 // them. If they do, all PHI entries for BB1/BB2 must agree for all PHI 00923 // nodes, so we insert select instruction to compute the final result. 00924 std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects; 00925 for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 00926 PHINode *PN; 00927 for (BasicBlock::iterator BBI = SI->begin(); 00928 (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 00929 Value *BB1V = PN->getIncomingValueForBlock(BB1); 00930 Value *BB2V = PN->getIncomingValueForBlock(BB2); 00931 if (BB1V != BB2V) { 00932 // These values do not agree. Insert a select instruction before NT 00933 // that determines the right value. 00934 SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)]; 00935 if (SI == 0) 00936 SI = SelectInst::Create(BI->getCondition(), BB1V, BB2V, 00937 BB1V->getName()+"."+BB2V->getName(), NT); 00938 // Make the PHI node use the select for all incoming values for BB1/BB2 00939 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 00940 if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2) 00941 PN->setIncomingValue(i, SI); 00942 } 00943 } 00944 } 00945 00946 // Update any PHI nodes in our new successors. 00947 for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) 00948 AddPredecessorToBlock(*SI, BIParent, BB1); 00949 00950 EraseTerminatorInstAndDCECond(BI); 00951 return true; 00952 } 00953 00954 /// SpeculativelyExecuteBB - Given a conditional branch that goes to BB1 00955 /// and an BB2 and the only successor of BB1 is BB2, hoist simple code 00956 /// (for now, restricted to a single instruction that's side effect free) from 00957 /// the BB1 into the branch block to speculatively execute it. 00958 static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) { 00959 // Only speculatively execution a single instruction (not counting the 00960 // terminator) for now. 00961 Instruction *HInst = NULL; 00962 Instruction *Term = BB1->getTerminator(); 00963 for (BasicBlock::iterator BBI = BB1->begin(), BBE = BB1->end(); 00964 BBI != BBE; ++BBI) { 00965 Instruction *I = BBI; 00966 // Skip debug info. 00967 if (isa<DbgInfoIntrinsic>(I)) continue; 00968 if (I == Term) break; 00969 00970 if (!HInst) 00971 HInst = I; 00972 else 00973 return false; 00974 } 00975 if (!HInst) 00976 return false; 00977 00978 // Be conservative for now. FP select instruction can often be expensive. 00979 Value *BrCond = BI->getCondition(); 00980 if (isa<Instruction>(BrCond) && 00981 cast<Instruction>(BrCond)->getOpcode() == Instruction::FCmp) 00982 return false; 00983 00984 // If BB1 is actually on the false edge of the conditional branch, remember 00985 // to swap the select operands later. 00986 bool Invert = false; 00987 if (BB1 != BI->getSuccessor(0)) { 00988 assert(BB1 == BI->getSuccessor(1) && "No edge from 'if' block?"); 00989 Invert = true; 00990 } 00991 00992 // Turn 00993 // BB: 00994 // %t1 = icmp 00995 // br i1 %t1, label %BB1, label %BB2 00996 // BB1: 00997 // %t3 = add %t2, c 00998 // br label BB2 00999 // BB2: 01000 // => 01001 // BB: 01002 // %t1 = icmp 01003 // %t4 = add %t2, c 01004 // %t3 = select i1 %t1, %t2, %t3 01005 switch (HInst->getOpcode()) { 01006 default: return false; // Not safe / profitable to hoist. 01007 case Instruction::Add: 01008 case Instruction::Sub: 01009 // Not worth doing for vector ops. 01010 if (isa<VectorType>(HInst->getType())) 01011 return false; 01012 break; 01013 case Instruction::And: 01014 case Instruction::Or: 01015 case Instruction::Xor: 01016 case Instruction::Shl: 01017 case Instruction::LShr: 01018 case Instruction::AShr: 01019 // Don't mess with vector operations. 01020 if (isa<VectorType>(HInst->getType())) 01021 return false; 01022 break; // These are all cheap and non-trapping instructions. 01023 } 01024 01025 // If the instruction is obviously dead, don't try to predicate it. 01026 if (HInst->use_empty()) { 01027 HInst->eraseFromParent(); 01028 return true; 01029 } 01030 01031 // Can we speculatively execute the instruction? And what is the value 01032 // if the condition is false? Consider the phi uses, if the incoming value 01033 // from the "if" block are all the same V, then V is the value of the 01034 // select if the condition is false. 01035 BasicBlock *BIParent = BI->getParent(); 01036 SmallVector<PHINode*, 4> PHIUses; 01037 Value *FalseV = NULL; 01038 01039 BasicBlock *BB2 = BB1->getTerminator()->getSuccessor(0); 01040 for (Value::use_iterator UI = HInst->use_begin(), E = HInst->use_end(); 01041 UI != E; ++UI) { 01042 // Ignore any user that is not a PHI node in BB2. These can only occur in 01043 // unreachable blocks, because they would not be dominated by the instr. 01044 PHINode *PN = dyn_cast<PHINode>(UI); 01045 if (!PN || PN->getParent() != BB2) 01046 return false; 01047 PHIUses.push_back(PN); 01048 01049 Value *PHIV = PN->getIncomingValueForBlock(BIParent); 01050 if (!FalseV) 01051 FalseV = PHIV; 01052 else if (FalseV != PHIV) 01053 return false; // Inconsistent value when condition is false. 01054 } 01055 01056 assert(FalseV && "Must have at least one user, and it must be a PHI"); 01057 01058 // Do not hoist the instruction if any of its operands are defined but not 01059 // used in this BB. The transformation will prevent the operand from 01060 // being sunk into the use block. 01061 for (User::op_iterator i = HInst->op_begin(), e = HInst->op_end(); 01062 i != e; ++i) { 01063 Instruction *OpI = dyn_cast<Instruction>(*i); 01064 if (OpI && OpI->getParent() == BIParent && 01065 !OpI->isUsedInBasicBlock(BIParent)) 01066 return false; 01067 } 01068 01069 // If we get here, we can hoist the instruction. Try to place it 01070 // before the icmp instruction preceding the conditional branch. 01071 BasicBlock::iterator InsertPos = BI; 01072 if (InsertPos != BIParent->begin()) 01073 --InsertPos; 01074 // Skip debug info between condition and branch. 01075 while (InsertPos != BIParent->begin() && isa<DbgInfoIntrinsic>(InsertPos)) 01076 --InsertPos; 01077 if (InsertPos == BrCond && !isa<PHINode>(BrCond)) { 01078 SmallPtrSet<Instruction *, 4> BB1Insns; 01079 for(BasicBlock::iterator BB1I = BB1->begin(), BB1E = BB1->end(); 01080 BB1I != BB1E; ++BB1I) 01081 BB1Insns.insert(BB1I); 01082 for(Value::use_iterator UI = BrCond->use_begin(), UE = BrCond->use_end(); 01083 UI != UE; ++UI) { 01084 Instruction *Use = cast<Instruction>(*UI); 01085 if (BB1Insns.count(Use)) { 01086 // If BrCond uses the instruction that place it just before 01087 // branch instruction. 01088 InsertPos = BI; 01089 break; 01090 } 01091 } 01092 } else 01093 InsertPos = BI; 01094 BIParent->getInstList().splice(InsertPos, BB1->getInstList(), HInst); 01095 01096 // Create a select whose true value is the speculatively executed value and 01097 // false value is the previously determined FalseV. 01098 SelectInst *SI; 01099 if (Invert) 01100 SI = SelectInst::Create(BrCond, FalseV, HInst, 01101 FalseV->getName() + "." + HInst->getName(), BI); 01102 else 01103 SI = SelectInst::Create(BrCond, HInst, FalseV, 01104 HInst->getName() + "." + FalseV->getName(), BI); 01105 01106 // Make the PHI node use the select for all incoming values for "then" and 01107 // "if" blocks. 01108 for (unsigned i = 0, e = PHIUses.size(); i != e; ++i) { 01109 PHINode *PN = PHIUses[i]; 01110 for (unsigned j = 0, ee = PN->getNumIncomingValues(); j != ee; ++j) 01111 if (PN->getIncomingBlock(j) == BB1 || 01112 PN->getIncomingBlock(j) == BIParent) 01113 PN->setIncomingValue(j, SI); 01114 } 01115 01116 ++NumSpeculations; 01117 return true; 01118 } 01119 01120 /// BlockIsSimpleEnoughToThreadThrough - Return true if we can thread a branch 01121 /// across this block. 01122 static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) { 01123 BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 01124 unsigned Size = 0; 01125 01126 for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { 01127 if (isa<DbgInfoIntrinsic>(BBI)) 01128 continue; 01129 if (Size > 10) return false; // Don't clone large BB's. 01130 ++Size; 01131 01132 // We can only support instructions that do not define values that are 01133 // live outside of the current basic block. 01134 for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); 01135 UI != E; ++UI) { 01136 Instruction *U = cast<Instruction>(*UI); 01137 if (U->getParent() != BB || isa<PHINode>(U)) return false; 01138 } 01139 01140 // Looks ok, continue checking. 01141 } 01142 01143 return true; 01144 } 01145 01146 /// FoldCondBranchOnPHI - If we have a conditional branch on a PHI node value 01147 /// that is defined in the same block as the branch and if any PHI entries are 01148 /// constants, thread edges corresponding to that entry to be branches to their 01149 /// ultimate destination. 01150 static bool FoldCondBranchOnPHI(BranchInst *BI) { 01151 BasicBlock *BB = BI->getParent(); 01152 LLVMContext &Context = BB->getContext(); 01153 PHINode *PN = dyn_cast<PHINode>(BI->getCondition()); 01154 // NOTE: we currently cannot transform this case if the PHI node is used 01155 // outside of the block. 01156 if (!PN || PN->getParent() != BB || !PN->hasOneUse()) 01157 return false; 01158 01159 // Degenerate case of a single entry PHI. 01160 if (PN->getNumIncomingValues() == 1) { 01161 FoldSingleEntryPHINodes(PN->getParent()); 01162 return true; 01163 } 01164 01165 // Now we know that this block has multiple preds and two succs. 01166 if (!BlockIsSimpleEnoughToThreadThrough(BB)) return false; 01167 01168 // Okay, this is a simple enough basic block. See if any phi values are 01169 // constants. 01170 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 01171 ConstantInt *CB; 01172 if ((CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i))) && 01173 CB->getType() == Type::getInt1Ty(BB->getContext())) { 01174 // Okay, we now know that all edges from PredBB should be revectored to 01175 // branch to RealDest. 01176 BasicBlock *PredBB = PN->getIncomingBlock(i); 01177 BasicBlock *RealDest = BI->getSuccessor(!CB->getZExtValue()); 01178 01179 if (RealDest == BB) continue; // Skip self loops. 01180 01181 // The dest block might have PHI nodes, other predecessors and other 01182 // difficult cases. Instead of being smart about this, just insert a new 01183 // block that jumps to the destination block, effectively splitting 01184 // the edge we are about to create. 01185 BasicBlock *EdgeBB = BasicBlock::Create(BB->getContext(), 01186 RealDest->getName()+".critedge", 01187 RealDest->getParent(), RealDest); 01188 BranchInst::Create(RealDest, EdgeBB); 01189 PHINode *PN; 01190 for (BasicBlock::iterator BBI = RealDest->begin(); 01191 (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 01192 Value *V = PN->getIncomingValueForBlock(BB); 01193 PN->addIncoming(V, EdgeBB); 01194 } 01195 01196 // BB may have instructions that are being threaded over. Clone these 01197 // instructions into EdgeBB. We know that there will be no uses of the 01198 // cloned instructions outside of EdgeBB. 01199 BasicBlock::iterator InsertPt = EdgeBB->begin(); 01200 std::map<Value*, Value*> TranslateMap; // Track translated values. 01201 for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { 01202 if (PHINode *PN = dyn_cast<PHINode>(BBI)) { 01203 TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB); 01204 } else { 01205 // Clone the instruction. 01206 Instruction *N = BBI->clone(Context); 01207 if (BBI->hasName()) N->setName(BBI->getName()+".c"); 01208 01209 // Update operands due to translation. 01210 for (User::op_iterator i = N->op_begin(), e = N->op_end(); 01211 i != e; ++i) { 01212 std::map<Value*, Value*>::iterator PI = 01213 TranslateMap.find(*i); 01214 if (PI != TranslateMap.end()) 01215 *i = PI->second; 01216 } 01217 01218 // Check for trivial simplification. 01219 if (Constant *C = ConstantFoldInstruction(N, Context)) { 01220 TranslateMap[BBI] = C; 01221 delete N; // Constant folded away, don't need actual inst 01222 } else { 01223 // Insert the new instruction into its new home. 01224 EdgeBB->getInstList().insert(InsertPt, N); 01225 if (!BBI->use_empty()) 01226 TranslateMap[BBI] = N; 01227 } 01228 } 01229 } 01230 01231 // Loop over all of the edges from PredBB to BB, changing them to branch 01232 // to EdgeBB instead. 01233 TerminatorInst *PredBBTI = PredBB->getTerminator(); 01234 for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i) 01235 if (PredBBTI->getSuccessor(i) == BB) { 01236 BB->removePredecessor(PredBB); 01237 PredBBTI->setSuccessor(i, EdgeBB); 01238 } 01239 01240 // Recurse, simplifying any other constants. 01241 return FoldCondBranchOnPHI(BI) | true; 01242 } 01243 } 01244 01245 return false; 01246 } 01247 01248 /// FoldTwoEntryPHINode - Given a BB that starts with the specified two-entry 01249 /// PHI node, see if we can eliminate it. 01250 static bool FoldTwoEntryPHINode(PHINode *PN) { 01251 // Ok, this is a two entry PHI node. Check to see if this is a simple "if 01252 // statement", which has a very simple dominance structure. Basically, we 01253 // are trying to find the condition that is being branched on, which 01254 // subsequently causes this merge to happen. We really want control 01255 // dependence information for this check, but simplifycfg can't keep it up 01256 // to date, and this catches most of the cases we care about anyway. 01257 // 01258 BasicBlock *BB = PN->getParent(); 01259 BasicBlock *IfTrue, *IfFalse; 01260 Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse); 01261 if (!IfCond) return false; 01262 01263 // Okay, we found that we can merge this two-entry phi node into a select. 01264 // Doing so would require us to fold *all* two entry phi nodes in this block. 01265 // At some point this becomes non-profitable (particularly if the target 01266 // doesn't support cmov's). Only do this transformation if there are two or 01267 // fewer PHI nodes in this block. 01268 unsigned NumPhis = 0; 01269 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++NumPhis, ++I) 01270 if (NumPhis > 2) 01271 return false; 01272 01273 DEBUG(errs() << "FOUND IF CONDITION! " << *IfCond << " T: " 01274 << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"); 01275 01276 // Loop over the PHI's seeing if we can promote them all to select 01277 // instructions. While we are at it, keep track of the instructions 01278 // that need to be moved to the dominating block. 01279 std::set<Instruction*> AggressiveInsts; 01280 01281 BasicBlock::iterator AfterPHIIt = BB->begin(); 01282 while (isa<PHINode>(AfterPHIIt)) { 01283 PHINode *PN = cast<PHINode>(AfterPHIIt++); 01284 if (PN->getIncomingValue(0) == PN->getIncomingValue(1)) { 01285 if (PN->getIncomingValue(0) != PN) 01286 PN->replaceAllUsesWith(PN->getIncomingValue(0)); 01287 else 01288 PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 01289 } else if (!DominatesMergePoint(PN->getIncomingValue(0), BB, 01290 &AggressiveInsts) || 01291 !DominatesMergePoint(PN->getIncomingValue(1), BB, 01292 &AggressiveInsts)) { 01293 return false; 01294 } 01295 } 01296 01297 // If we all PHI nodes are promotable, check to make sure that all 01298 // instructions in the predecessor blocks can be promoted as well. If 01299 // not, we won't be able to get rid of the control flow, so it's not 01300 // worth promoting to select instructions. 01301 BasicBlock *DomBlock = 0, *IfBlock1 = 0, *IfBlock2 = 0; 01302 PN = cast<PHINode>(BB->begin()); 01303 BasicBlock *Pred = PN->getIncomingBlock(0); 01304 if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 01305 IfBlock1 = Pred; 01306 DomBlock = *pred_begin(Pred); 01307 for (BasicBlock::iterator I = Pred->begin(); 01308 !isa<TerminatorInst>(I); ++I) 01309 if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) { 01310 // This is not an aggressive instruction that we can promote. 01311 // Because of this, we won't be able to get rid of the control 01312 // flow, so the xform is not worth it. 01313 return false; 01314 } 01315 } 01316 01317 Pred = PN->getIncomingBlock(1); 01318 if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 01319 IfBlock2 = Pred; 01320 DomBlock = *pred_begin(Pred); 01321 for (BasicBlock::iterator I = Pred->begin(); 01322 !isa<TerminatorInst>(I); ++I) 01323 if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) { 01324 // This is not an aggressive instruction that we can promote. 01325 // Because of this, we won't be able to get rid of the control 01326 // flow, so the xform is not worth it. 01327 return false; 01328 } 01329 } 01330 01331 // If we can still promote the PHI nodes after this gauntlet of tests, 01332 // do all of the PHI's now. 01333 01334 // Move all 'aggressive' instructions, which are defined in the 01335 // conditional parts of the if's up to the dominating block. 01336 if (IfBlock1) { 01337 DomBlock->getInstList().splice(DomBlock->getTerminator(), 01338 IfBlock1->getInstList(), 01339 IfBlock1->begin(), 01340 IfBlock1->getTerminator()); 01341 } 01342 if (IfBlock2) { 01343 DomBlock->getInstList().splice(DomBlock->getTerminator(), 01344 IfBlock2->getInstList(), 01345 IfBlock2->begin(), 01346 IfBlock2->getTerminator()); 01347 } 01348 01349 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 01350 // Change the PHI node into a select instruction. 01351 Value *TrueVal = 01352 PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); 01353 Value *FalseVal = 01354 PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); 01355 01356 Value *NV = SelectInst::Create(IfCond, TrueVal, FalseVal, "", AfterPHIIt); 01357 PN->replaceAllUsesWith(NV); 01358 NV->takeName(PN); 01359 01360 BB->getInstList().erase(PN); 01361 } 01362 return true; 01363 } 01364 01365 /// isTerminatorFirstRelevantInsn - Return true if Term is very first 01366 /// instruction ignoring Phi nodes and dbg intrinsics. 01367 static bool isTerminatorFirstRelevantInsn(BasicBlock *BB, Instruction *Term) { 01368 BasicBlock::iterator BBI = Term; 01369 while (BBI != BB->begin()) { 01370 --BBI; 01371 if (!isa<DbgInfoIntrinsic>(BBI)) 01372 break; 01373 } 01374 01375 if (isa<PHINode>(BBI) || &*BBI == Term || isa<DbgInfoIntrinsic>(BBI)) 01376 return true; 01377 return false; 01378 } 01379 01380 /// SimplifyCondBranchToTwoReturns - If we found a conditional branch that goes 01381 /// to two returning blocks, try to merge them together into one return, 01382 /// introducing a select if the return values disagree. 01383 static bool SimplifyCondBranchToTwoReturns(BranchInst *BI) { 01384 assert(BI->isConditional() && "Must be a conditional branch"); 01385 BasicBlock *TrueSucc = BI->getSuccessor(0); 01386 BasicBlock *FalseSucc = BI->getSuccessor(1); 01387 ReturnInst *TrueRet = cast<ReturnInst>(TrueSucc->getTerminator()); 01388 ReturnInst *FalseRet = cast<ReturnInst>(FalseSucc->getTerminator()); 01389 01390 // Check to ensure both blocks are empty (just a return) or optionally empty 01391 // with PHI nodes. If there are other instructions, merging would cause extra 01392 // computation on one path or the other. 01393 if (!isTerminatorFirstRelevantInsn(TrueSucc, TrueRet)) 01394 return false; 01395 if (!isTerminatorFirstRelevantInsn(FalseSucc, FalseRet)) 01396 return false; 01397 01398 // Okay, we found a branch that is going to two return nodes. If 01399 // there is no return value for this function, just change the 01400 // branch into a return. 01401 if (FalseRet->getNumOperands() == 0) { 01402 TrueSucc->removePredecessor(BI->getParent()); 01403 FalseSucc->removePredecessor(BI->getParent()); 01404 ReturnInst::Create(BI->getContext(), 0, BI); 01405 EraseTerminatorInstAndDCECond(BI); 01406 return true; 01407 } 01408 01409 // Otherwise, figure out what the true and false return values are 01410 // so we can insert a new select instruction. 01411 Value *TrueValue = TrueRet->getReturnValue(); 01412 Value *FalseValue = FalseRet->getReturnValue(); 01413 01414 // Unwrap any PHI nodes in the return blocks. 01415 if (PHINode *TVPN = dyn_cast_or_null<PHINode>(TrueValue)) 01416 if (TVPN->getParent() == TrueSucc) 01417 TrueValue = TVPN->getIncomingValueForBlock(BI->getParent()); 01418 if (PHINode *FVPN = dyn_cast_or_null<PHINode>(FalseValue)) 01419 if (FVPN->getParent() == FalseSucc) 01420 FalseValue = FVPN->getIncomingValueForBlock(BI->getParent()); 01421 01422 // In order for this transformation to be safe, we must be able to 01423 // unconditionally execute both operands to the return. This is 01424 // normally the case, but we could have a potentially-trapping 01425 // constant expression that prevents this transformation from being 01426 // safe. 01427 if (ConstantExpr *TCV = dyn_cast_or_null<ConstantExpr>(TrueValue)) 01428 if (TCV->canTrap()) 01429 return false; 01430 if (ConstantExpr *FCV = dyn_cast_or_null<ConstantExpr>(FalseValue)) 01431 if (FCV->canTrap()) 01432 return false; 01433 01434 // Okay, we collected all the mapped values and checked them for sanity, and 01435 // defined to really do this transformation. First, update the CFG. 01436 TrueSucc->removePredecessor(BI->getParent()); 01437 FalseSucc->removePredecessor(BI->getParent()); 01438 01439 // Insert select instructions where needed. 01440 Value *BrCond = BI->getCondition(); 01441 if (TrueValue) { 01442 // Insert a select if the results differ. 01443 if (TrueValue == FalseValue || isa<UndefValue>(FalseValue)) { 01444 } else if (isa<UndefValue>(TrueValue)) { 01445 TrueValue = FalseValue; 01446 } else { 01447 TrueValue = SelectInst::Create(BrCond, TrueValue, 01448 FalseValue, "retval", BI); 01449 } 01450 } 01451 01452 Value *RI = !TrueValue ? 01453 ReturnInst::Create(BI->getContext(), BI) : 01454 ReturnInst::Create(BI->getContext(), TrueValue, BI); 01455 01456 DOUT << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:" 01457 << "\n " << *BI << "NewRet = " << *RI 01458 << "TRUEBLOCK: " << *TrueSucc << "FALSEBLOCK: "<< *FalseSucc; 01459 01460 EraseTerminatorInstAndDCECond(BI); 01461 01462 return true; 01463 } 01464 01465 /// FoldBranchToCommonDest - If this basic block is ONLY a setcc and a branch, 01466 /// and if a predecessor branches to us and one of our successors, fold the 01467 /// setcc into the predecessor and use logical operations to pick the right 01468 /// destination. 01469 bool llvm::FoldBranchToCommonDest(BranchInst *BI) { 01470 BasicBlock *BB = BI->getParent(); 01471 Instruction *Cond = dyn_cast<Instruction>(BI->getCondition()); 01472 if (Cond == 0) return false; 01473 01474 01475 // Only allow this if the condition is a simple instruction that can be 01476 // executed unconditionally. It must be in the same block as the branch, and 01477 // must be at the front of the block. 01478 BasicBlock::iterator FrontIt = BB->front(); 01479 // Ignore dbg intrinsics. 01480 while(isa<DbgInfoIntrinsic>(FrontIt)) 01481 ++FrontIt; 01482 if ((!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) || 01483 Cond->getParent() != BB || &*FrontIt != Cond || !Cond->hasOneUse()) { 01484 return false; 01485 } 01486 01487 // Make sure the instruction after the condition is the cond branch. 01488 BasicBlock::iterator CondIt = Cond; ++CondIt; 01489 // Ingore dbg intrinsics. 01490 while(isa<DbgInfoIntrinsic>(CondIt)) 01491 ++CondIt; 01492 if (&*CondIt != BI) { 01493 assert (!isa<DbgInfoIntrinsic>(CondIt) && "Hey do not forget debug info!"); 01494 return false; 01495 } 01496 01497 // Cond is known to be a compare or binary operator. Check to make sure that 01498 // neither operand is a potentially-trapping constant expression. 01499 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(0))) 01500 if (CE->canTrap()) 01501 return false; 01502 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(1))) 01503 if (CE->canTrap()) 01504 return false; 01505 01506 01507 // Finally, don't infinitely unroll conditional loops. 01508 BasicBlock *TrueDest = BI->getSuccessor(0); 01509 BasicBlock *FalseDest = BI->getSuccessor(1); 01510 if (TrueDest == BB || FalseDest == BB) 01511 return false; 01512 01513 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 01514 BasicBlock *PredBlock = *PI; 01515 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator()); 01516 01517 // Check that we have two conditional branches. If there is a PHI node in 01518 // the common successor, verify that the same value flows in from both 01519 // blocks. 01520 if (PBI == 0 || PBI->isUnconditional() || 01521 !SafeToMergeTerminators(BI, PBI)) 01522 continue; 01523 01524 Instruction::BinaryOps Opc; 01525 bool InvertPredCond = false; 01526 01527 if (PBI->getSuccessor(0) == TrueDest) 01528 Opc = Instruction::Or; 01529 else if (PBI->getSuccessor(1) == FalseDest) 01530 Opc = Instruction::And; 01531 else if (PBI->getSuccessor(0) == FalseDest) 01532 Opc = Instruction::And, InvertPredCond = true; 01533 else if (PBI->getSuccessor(1) == TrueDest) 01534 Opc = Instruction::Or, InvertPredCond = true; 01535 else 01536 continue; 01537 01538 DOUT << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB; 01539 01540 // If we need to invert the condition in the pred block to match, do so now. 01541 if (InvertPredCond) { 01542 Value *NewCond = 01543 BinaryOperator::CreateNot(PBI->getCondition(), 01544 PBI->getCondition()->getName()+".not", PBI); 01545 PBI->setCondition(NewCond); 01546 BasicBlock *OldTrue = PBI->getSuccessor(0); 01547 BasicBlock *OldFalse = PBI->getSuccessor(1); 01548 PBI->setSuccessor(0, OldFalse); 01549 PBI->setSuccessor(1, OldTrue); 01550 } 01551 01552 // Clone Cond into the predecessor basic block, and or/and the 01553 // two conditions together. 01554 Instruction *New = Cond->clone(BB->getContext()); 01555 PredBlock->getInstList().insert(PBI, New); 01556 New->takeName(Cond); 01557 Cond->setName(New->getName()+".old"); 01558 01559 Value *NewCond = BinaryOperator::Create(Opc, PBI->getCondition(), 01560 New, "or.cond", PBI); 01561 PBI->setCondition(NewCond); 01562 if (PBI->getSuccessor(0) == BB) { 01563 AddPredecessorToBlock(TrueDest, PredBlock, BB); 01564 PBI->setSuccessor(0, TrueDest); 01565 } 01566 if (PBI->getSuccessor(1) == BB) { 01567 AddPredecessorToBlock(FalseDest, PredBlock, BB); 01568 PBI->setSuccessor(1, FalseDest); 01569 } 01570 return true; 01571 } 01572 return false; 01573 } 01574 01575 /// SimplifyCondBranchToCondBranch - If we have a conditional branch as a 01576 /// predecessor of another block, this function tries to simplify it. We know 01577 /// that PBI and BI are both conditional branches, and BI is in one of the 01578 /// successor blocks of PBI - PBI branches to BI. 01579 static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { 01580 assert(PBI->isConditional() && BI->isConditional()); 01581 BasicBlock *BB = BI->getParent(); 01582 01583 // If this block ends with a branch instruction, and if there is a 01584 // predecessor that ends on a branch of the same condition, make 01585 // this conditional branch redundant. 01586 if (PBI->getCondition() == BI->getCondition() && 01587 PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 01588 // Okay, the outcome of this conditional branch is statically 01589 // knowable. If this block had a single pred, handle specially. 01590 if (BB->getSinglePredecessor()) { 01591 // Turn this into a branch on constant. 01592 bool CondIsTrue = PBI->getSuccessor(0) == BB; 01593 BI->setCondition(ConstantInt::get(Type::getInt1Ty(BB->getContext()), 01594 CondIsTrue)); 01595 return true; // Nuke the branch on constant. 01596 } 01597 01598 // Otherwise, if there are multiple predecessors, insert a PHI that merges 01599 // in the constant and simplify the block result. Subsequent passes of 01600 // simplifycfg will thread the block. 01601 if (BlockIsSimpleEnoughToThreadThrough(BB)) { 01602 PHINode *NewPN = PHINode::Create(Type::getInt1Ty(BB->getContext()), 01603 BI->getCondition()->getName() + ".pr", 01604 BB->begin()); 01605 // Okay, we're going to insert the PHI node. Since PBI is not the only 01606 // predecessor, compute the PHI'd conditional value for all of the preds. 01607 // Any predecessor where the condition is not computable we keep symbolic. 01608 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 01609 if ((PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) && 01610 PBI != BI && PBI->isConditional() && 01611 PBI->getCondition() == BI->getCondition() && 01612 PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 01613 bool CondIsTrue = PBI->getSuccessor(0) == BB; 01614 NewPN->addIncoming(ConstantInt::get(Type::getInt1Ty(BB->getContext()), 01615 CondIsTrue), *PI); 01616 } else { 01617 NewPN->addIncoming(BI->getCondition(), *PI); 01618 } 01619 01620 BI->setCondition(NewPN); 01621 return true; 01622 } 01623 } 01624 01625 // If this is a conditional branch in an empty block, and if any 01626 // predecessors is a conditional branch to one of our destinations, 01627 // fold the conditions into logical ops and one cond br. 01628 BasicBlock::iterator BBI = BB->begin(); 01629 // Ignore dbg intrinsics. 01630 while (isa<DbgInfoIntrinsic>(BBI)) 01631 ++BBI; 01632 if (&*BBI != BI) 01633 return false; 01634 01635 01636 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(BI->getCondition())) 01637 if (CE->canTrap()) 01638 return false; 01639 01640 int PBIOp, BIOp; 01641 if (PBI->getSuccessor(0) == BI->getSuccessor(0)) 01642 PBIOp = BIOp = 0; 01643 else if (PBI->getSuccessor(0) == BI->getSuccessor(1)) 01644 PBIOp = 0, BIOp = 1; 01645 else if (PBI->getSuccessor(1) == BI->getSuccessor(0)) 01646 PBIOp = 1, BIOp = 0; 01647 else if (PBI->getSuccessor(1) == BI->getSuccessor(1)) 01648 PBIOp = BIOp = 1; 01649 else 01650 return false; 01651 01652 // Check to make sure that the other destination of this branch 01653 // isn't BB itself. If so, this is an infinite loop that will 01654 // keep getting unwound. 01655 if (PBI->getSuccessor(PBIOp) == BB) 01656 return false; 01657 01658 // Do not perform this transformation if it would require 01659 // insertion of a large number of select instructions. For targets 01660 // without predication/cmovs, this is a big pessimization. 01661 BasicBlock *CommonDest = PBI->getSuccessor(PBIOp); 01662 01663 unsigned NumPhis = 0; 01664 for (BasicBlock::iterator II = CommonDest->begin(); 01665 isa<PHINode>(II); ++II, ++NumPhis) 01666 if (NumPhis > 2) // Disable this xform. 01667 return false; 01668 01669 // Finally, if everything is ok, fold the branches to logical ops. 01670 BasicBlock *OtherDest = BI->getSuccessor(BIOp ^ 1); 01671 01672 DOUT << "FOLDING BRs:" << *PBI->getParent() 01673 << "AND: " << *BI->getParent(); 01674 01675 01676 // If OtherDest *is* BB, then BB is a basic block with a single conditional 01677 // branch in it, where one edge (OtherDest) goes back to itself but the other 01678 // exits. We don't *know* that the program avoids the infinite loop 01679 // (even though that seems likely). If we do this xform naively, we'll end up 01680 // recursively unpeeling the loop. Since we know that (after the xform is 01681 // done) that the block *is* infinite if reached, we just make it an obviously 01682 // infinite loop with no cond branch. 01683 if (OtherDest == BB) { 01684 // Insert it at the end of the function, because it's either code, 01685 // or it won't matter if it's hot. :) 01686 BasicBlock *InfLoopBlock = BasicBlock::Create(BB->getContext(), 01687 "infloop", BB->getParent()); 01688 BranchInst::Create(InfLoopBlock, InfLoopBlock); 01689 OtherDest = InfLoopBlock; 01690 } 01691 01692 DOUT << *PBI->getParent()->getParent(); 01693 01694 // BI may have other predecessors. Because of this, we leave 01695 // it alone, but modify PBI. 01696 01697 // Make sure we get to CommonDest on True&True directions. 01698 Value *PBICond = PBI->getCondition(); 01699 if (PBIOp) 01700 PBICond = BinaryOperator::CreateNot(PBICond, 01701 PBICond->getName()+".not", 01702 PBI); 01703 Value *BICond = BI->getCondition(); 01704 if (BIOp) 01705 BICond = BinaryOperator::CreateNot(BICond, 01706 BICond->getName()+".not", 01707 PBI); 01708 // Merge the conditions. 01709 Value *Cond = BinaryOperator::CreateOr(PBICond, BICond, "brmerge", PBI); 01710 01711 // Modify PBI to branch on the new condition to the new dests. 01712 PBI->setCondition(Cond); 01713 PBI->setSuccessor(0, CommonDest); 01714 PBI->setSuccessor(1, OtherDest); 01715 01716 // OtherDest may have phi nodes. If so, add an entry from PBI's 01717 // block that are identical to the entries for BI's block. 01718 PHINode *PN; 01719 for (BasicBlock::iterator II = OtherDest->begin(); 01720 (PN = dyn_cast<PHINode>(II)); ++II) { 01721 Value *V = PN->getIncomingValueForBlock(BB); 01722 PN->addIncoming(V, PBI->getParent()); 01723 } 01724 01725 // We know that the CommonDest already had an edge from PBI to 01726 // it. If it has PHIs though, the PHIs may have different 01727 // entries for BB and PBI's BB. If so, insert a select to make 01728 // them agree. 01729 for (BasicBlock::iterator II = CommonDest->begin(); 01730 (PN = dyn_cast<PHINode>(II)); ++II) { 01731 Value *BIV = PN->getIncomingValueForBlock(BB); 01732 unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent()); 01733 Value *PBIV = PN->getIncomingValue(PBBIdx); 01734 if (BIV != PBIV) { 01735 // Insert a select in PBI to pick the right value. 01736 Value *NV = SelectInst::Create(PBICond, PBIV, BIV, 01737 PBIV->getName()+".mux", PBI); 01738 PN->setIncomingValue(PBBIdx, NV); 01739 } 01740 } 01741 01742 DOUT << "INTO: " << *PBI->getParent(); 01743 01744 DOUT << *PBI->getParent()->getParent(); 01745 01746 // This basic block is probably dead. We know it has at least 01747 // one fewer predecessor. 01748 return true; 01749 } 01750 01751 01752 /// SimplifyCFG - This function is used to do simplification of a CFG. For 01753 /// example, it adjusts branches to branches to eliminate the extra hop, it 01754 /// eliminates unreachable basic blocks, and does other "peephole" optimization 01755 /// of the CFG. It returns true if a modification was made. 01756 /// 01757 /// WARNING: The entry node of a function may not be simplified. 01758 /// 01759 bool llvm::SimplifyCFG(BasicBlock *BB) { 01760 bool Changed = false; 01761 Function *M = BB->getParent(); 01762 01763 assert(BB && BB->getParent() && "Block not embedded in function!"); 01764 assert(BB->getTerminator() && "Degenerate basic block encountered!"); 01765 assert(&BB->getParent()->getEntryBlock() != BB && 01766 "Can't Simplify entry block!"); 01767 01768 // Remove basic blocks that have no predecessors... or that just have themself 01769 // as a predecessor. These are unreachable. 01770 if (pred_begin(BB) == pred_end(BB) || BB->getSinglePredecessor() == BB) { 01771 DOUT << "Removing BB: \n" << *BB; 01772 DeleteDeadBlock(BB); 01773 return true; 01774 } 01775 01776 // Check to see if we can constant propagate this terminator instruction 01777 // away... 01778 Changed |= ConstantFoldTerminator(BB); 01779 01780 // If there is a trivial two-entry PHI node in this basic block, and we can 01781 // eliminate it, do so now. 01782 if (PHINode *PN = dyn_cast<PHINode>(BB->begin())) 01783 if (PN->getNumIncomingValues() == 2) 01784 Changed |= FoldTwoEntryPHINode(PN); 01785 01786 // If this is a returning block with only PHI nodes in it, fold the return 01787 // instruction into any unconditional branch predecessors. 01788 // 01789 // If any predecessor is a conditional branch that just selects among 01790 // different return values, fold the replace the branch/return with a select 01791 // and return. 01792 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 01793 if (isTerminatorFirstRelevantInsn(BB, BB->getTerminator())) { 01794 // Find predecessors that end with branches. 01795 SmallVector<BasicBlock*, 8> UncondBranchPreds; 01796 SmallVector<BranchInst*, 8> CondBranchPreds; 01797 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 01798 TerminatorInst *PTI = (*PI)->getTerminator(); 01799 if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) { 01800 if (BI->isUnconditional()) 01801 UncondBranchPreds.push_back(*PI); 01802 else 01803 CondBranchPreds.push_back(BI); 01804 } 01805 } 01806 01807 // If we found some, do the transformation! 01808 if (!UncondBranchPreds.empty()) { 01809 while (!UncondBranchPreds.empty()) { 01810 BasicBlock *Pred = UncondBranchPreds.pop_back_val(); 01811 DOUT << "FOLDING: " << *BB 01812 << "INTO UNCOND BRANCH PRED: " << *Pred; 01813 Instruction *UncondBranch = Pred->getTerminator(); 01814 // Clone the return and add it to the end of the predecessor. 01815 Instruction *NewRet = RI->clone(BB->getContext()); 01816 Pred->getInstList().push_back(NewRet); 01817 01818 BasicBlock::iterator BBI = RI; 01819 if (BBI != BB->begin()) { 01820 // Move region end info into the predecessor. 01821 if (DbgRegionEndInst *DREI = dyn_cast<DbgRegionEndInst>(--BBI)) 01822 DREI->moveBefore(NewRet); 01823 } 01824 01825 // If the return instruction returns a value, and if the value was a 01826 // PHI node in "BB", propagate the right value into the return. 01827 for (User::op_iterator i = NewRet->op_begin(), e = NewRet->op_end(); 01828 i != e; ++i) 01829 if (PHINode *PN = dyn_cast<PHINode>(*i)) 01830 if (PN->getParent() == BB) 01831 *i = PN->getIncomingValueForBlock(Pred); 01832 01833 // Update any PHI nodes in the returning block to realize that we no 01834 // longer branch to them. 01835 BB->removePredecessor(Pred); 01836 Pred->getInstList().erase(UncondBranch); 01837 } 01838 01839 // If we eliminated all predecessors of the block, delete the block now. 01840 if (pred_begin(BB) == pred_end(BB)) 01841 // We know there are no successors, so just nuke the block. 01842 M->getBasicBlockList().erase(BB); 01843 01844 return true; 01845 } 01846 01847 // Check out all of the conditional branches going to this return 01848 // instruction. If any of them just select between returns, change the 01849 // branch itself into a select/return pair. 01850 while (!CondBranchPreds.empty()) { 01851 BranchInst *BI = CondBranchPreds.pop_back_val(); 01852 01853 // Check to see if the non-BB successor is also a return block. 01854 if (isa<ReturnInst>(BI->getSuccessor(0)->getTerminator()) && 01855 isa<ReturnInst>(BI->getSuccessor(1)->getTerminator()) && 01856 SimplifyCondBranchToTwoReturns(BI)) 01857 return true; 01858 } 01859 } 01860 } else if (isa<UnwindInst>(BB->begin())) { 01861 // Check to see if the first instruction in this block is just an unwind. 01862 // If so, replace any invoke instructions which use this as an exception 01863 // destination with call instructions, and any unconditional branch 01864 // predecessor with an unwind. 01865 // 01866 SmallVector<BasicBlock*, 8> Preds(pred_begin(BB), pred_end(BB)); 01867 while (!Preds.empty()) { 01868 BasicBlock *Pred = Preds.back(); 01869 if (BranchInst *BI = dyn_cast<BranchInst>(Pred->getTerminator())) { 01870 if (BI->isUnconditional()) { 01871 Pred->getInstList().pop_back(); // nuke uncond branch 01872 new UnwindInst(Pred->getContext(), Pred); // Use unwind. 01873 Changed = true; 01874 } 01875 } else if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator())) 01876 if (II->getUnwindDest() == BB) { 01877 // Insert a new branch instruction before the invoke, because this 01878 // is now a fall through... 01879 BranchInst *BI = BranchInst::Create(II->getNormalDest(), II); 01880 Pred->getInstList().remove(II); // Take out of symbol table 01881 01882 // Insert the call now... 01883 SmallVector<Value*,8> Args(II->op_begin()+3, II->op_end()); 01884 CallInst *CI = CallInst::Create(II->getCalledValue(), 01885 Args.begin(), Args.end(), 01886 II->getName(), BI); 01887 CI->setCallingConv(II->getCallingConv()); 01888 CI->setAttributes(II->getAttributes()); 01889 // If the invoke produced a value, the Call now does instead 01890 II->replaceAllUsesWith(CI); 01891 delete II; 01892 Changed = true; 01893 } 01894 01895 Preds.pop_back(); 01896 } 01897 01898 // If this block is now dead, remove it. 01899 if (pred_begin(BB) == pred_end(BB)) { 01900 // We know there are no successors, so just nuke the block. 01901 M->getBasicBlockList().erase(BB); 01902 return true; 01903 } 01904 01905 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { 01906 if (isValueEqualityComparison(SI)) { 01907 // If we only have one predecessor, and if it is a branch on this value, 01908 // see if that predecessor totally determines the outcome of this switch. 01909 if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 01910 if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred)) 01911 return SimplifyCFG(BB) || 1; 01912 01913 // If the block only contains the switch, see if we can fold the block 01914 // away into any preds. 01915 BasicBlock::iterator BBI = BB->begin(); 01916 // Ignore dbg intrinsics. 01917 while (isa<DbgInfoIntrinsic>(BBI)) 01918 ++BBI; 01919 if (SI == &*BBI) 01920 if (FoldValueComparisonIntoPredecessors(SI)) 01921 return SimplifyCFG(BB) || 1; 01922 } 01923 } else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 01924 if (BI->isUnconditional()) { 01925 BasicBlock::iterator BBI = BB->getFirstNonPHI(); 01926 01927 BasicBlock *Succ = BI->getSuccessor(0); 01928 // Ignore dbg intrinsics. 01929 while (isa<DbgInfoIntrinsic>(BBI)) 01930 ++BBI; 01931 if (BBI->isTerminator() && // Terminator is the only non-phi instruction! 01932 Succ != BB) // Don't hurt infinite loops! 01933 if (TryToSimplifyUncondBranchFromEmptyBlock(BB, Succ)) 01934 return true; 01935 01936 } else { // Conditional branch 01937 if (isValueEqualityComparison(BI)) { 01938 // If we only have one predecessor, and if it is a branch on this value, 01939 // see if that predecessor totally determines the outcome of this 01940 // switch. 01941 if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 01942 if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred)) 01943 return SimplifyCFG(BB) || 1; 01944 01945 // This block must be empty, except for the setcond inst, if it exists. 01946 // Ignore dbg intrinsics. 01947 BasicBlock::iterator I = BB->begin(); 01948 // Ignore dbg intrinsics. 01949 while (isa<DbgInfoIntrinsic>(I)) 01950 ++I; 01951 if (&*I == BI) { 01952 if (FoldValueComparisonIntoPredecessors(BI)) 01953 return SimplifyCFG(BB) | true; 01954 } else if (&*I == cast<Instruction>(BI->getCondition())){ 01955 ++I; 01956 // Ignore dbg intrinsics. 01957 while (isa<DbgInfoIntrinsic>(I)) 01958 ++I; 01959 if(&*I == BI) { 01960 if (FoldValueComparisonIntoPredecessors(BI)) 01961 return SimplifyCFG(BB) | true; 01962 } 01963 } 01964 } 01965 01966 // If this is a branch on a phi node in the current block, thread control 01967 // through this block if any PHI node entries are constants. 01968 if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition())) 01969 if (PN->getParent() == BI->getParent()) 01970 if (FoldCondBranchOnPHI(BI)) 01971 return SimplifyCFG(BB) | true; 01972 01973 // If this basic block is ONLY a setcc and a branch, and if a predecessor 01974 // branches to us and one of our successors, fold the setcc into the 01975 // predecessor and use logical operations to pick the right destination. 01976 if (FoldBranchToCommonDest(BI)) 01977 return SimplifyCFG(BB) | 1; 01978 01979 01980 // Scan predecessor blocks for conditional branches. 01981 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 01982 if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 01983 if (PBI != BI && PBI->isConditional()) 01984 if (SimplifyCondBranchToCondBranch(PBI, BI)) 01985 return SimplifyCFG(BB) | true; 01986 } 01987 } else if (isa<UnreachableInst>(BB->getTerminator())) { 01988 // If there are any instructions immediately before the unreachable that can 01989 // be removed, do so. 01990 Instruction *Unreachable = BB->getTerminator(); 01991 while (Unreachable != BB->begin()) { 01992 BasicBlock::iterator BBI = Unreachable; 01993 --BBI; 01994 // Do not delete instructions that can have side effects, like calls 01995 // (which may never return) and volatile loads and stores. 01996 if (isa<CallInst>(BBI) && !isa<DbgInfoIntrinsic>(BBI)) break; 01997 01998 if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) 01999 if (SI->isVolatile()) 02000 break; 02001 02002 if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) 02003 if (LI->isVolatile()) 02004 break; 02005 02006 // Delete this instruction 02007 BB->getInstList().erase(BBI); 02008 Changed = true; 02009 } 02010 02011 // If the unreachable instruction is the first in the block, take a gander 02012 // at all of the predecessors of this instruction, and simplify them. 02013 if (&BB->front() == Unreachable) { 02014 SmallVector<BasicBlock*, 8> Preds(pred_begin(BB), pred_end(BB)); 02015 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 02016 TerminatorInst *TI = Preds[i]->getTerminator(); 02017 02018 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 02019 if (BI->isUnconditional()) { 02020 if (BI->getSuccessor(0) == BB) { 02021 new UnreachableInst(TI->getContext(), TI); 02022 TI->eraseFromParent(); 02023 Changed = true; 02024 } 02025 } else { 02026 if (BI->getSuccessor(0) == BB) { 02027 BranchInst::Create(BI->getSuccessor(1), BI); 02028 EraseTerminatorInstAndDCECond(BI); 02029 } else if (BI->getSuccessor(1) == BB) { 02030 BranchInst::Create(BI->getSuccessor(0), BI); 02031 EraseTerminatorInstAndDCECond(BI); 02032 Changed = true; 02033 } 02034 } 02035 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 02036 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 02037 if (SI->getSuccessor(i) == BB) { 02038 BB->removePredecessor(SI->getParent()); 02039 SI->removeCase(i); 02040 --i; --e; 02041 Changed = true; 02042 } 02043 // If the default value is unreachable, figure out the most popular 02044 // destination and make it the default. 02045 if (SI->getSuccessor(0) == BB) { 02046 std::map<BasicBlock*, unsigned> Popularity; 02047 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 02048 Popularity[SI->getSuccessor(i)]++; 02049 02050 // Find the most popular block. 02051 unsigned MaxPop = 0; 02052 BasicBlock *MaxBlock = 0; 02053 for (std::map<BasicBlock*, unsigned>::iterator 02054 I = Popularity.begin(), E = Popularity.end(); I != E; ++I) { 02055 if (I->second > MaxPop) { 02056 MaxPop = I->second; 02057 MaxBlock = I->first; 02058 } 02059 } 02060 if (MaxBlock) { 02061 // Make this the new default, allowing us to delete any explicit 02062 // edges to it. 02063 SI->setSuccessor(0, MaxBlock); 02064 Changed = true; 02065 02066 // If MaxBlock has phinodes in it, remove MaxPop-1 entries from 02067 // it. 02068 if (isa<PHINode>(MaxBlock->begin())) 02069 for (unsigned i = 0; i != MaxPop-1; ++i) 02070 MaxBlock->removePredecessor(SI->getParent()); 02071 02072 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 02073 if (SI->getSuccessor(i) == MaxBlock) { 02074 SI->removeCase(i); 02075 --i; --e; 02076 } 02077 } 02078 } 02079 } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) { 02080 if (II->getUnwindDest() == BB) { 02081 // Convert the invoke to a call instruction. This would be a good 02082 // place to note that the call does not throw though. 02083 BranchInst *BI = BranchInst::Create(II->getNormalDest(), II); 02084 II->removeFromParent(); // Take out of symbol table 02085 02086 // Insert the call now... 02087 SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end()); 02088 CallInst *CI = CallInst::Create(II->getCalledValue(), 02089 Args.begin(), Args.end(), 02090 II->getName(), BI); 02091 CI->setCallingConv(II->getCallingConv()); 02092 CI->setAttributes(II->getAttributes()); 02093 // If the invoke produced a value, the Call does now instead. 02094 II->replaceAllUsesWith(CI); 02095 delete II; 02096 Changed = true; 02097 } 02098 } 02099 } 02100 02101 // If this block is now dead, remove it. 02102 if (pred_begin(BB) == pred_end(BB)) { 02103 // We know there are no successors, so just nuke the block. 02104 M->getBasicBlockList().erase(BB); 02105 return true; 02106 } 02107 } 02108 } 02109 02110 // Merge basic blocks into their predecessor if there is only one distinct 02111 // pred, and if there is only one distinct successor of the predecessor, and 02112 // if there are no PHI nodes. 02113 // 02114 if (MergeBlockIntoPredecessor(BB)) 02115 return true; 02116 02117 // Otherwise, if this block only has a single predecessor, and if that block 02118 // is a conditional branch, see if we can hoist any code from this block up 02119 // into our predecessor. 02120 pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 02121 BasicBlock *OnlyPred = *PI++; 02122 for (; PI != PE; ++PI) // Search all predecessors, see if they are all same 02123 if (*PI != OnlyPred) { 02124 OnlyPred = 0; // There are multiple different predecessors... 02125 break; 02126 } 02127 02128 if (OnlyPred) 02129 if (BranchInst *BI = dyn_cast<BranchInst>(OnlyPred->getTerminator())) 02130 if (BI->isConditional()) { 02131 // Get the other block. 02132 BasicBlock *OtherBB = BI->getSuccessor(BI->getSuccessor(0) == BB); 02133 PI = pred_begin(OtherBB); 02134 ++PI; 02135 02136 if (PI == pred_end(OtherBB)) { 02137 // We have a conditional branch to two blocks that are only reachable 02138 // from the condbr. We know that the condbr dominates the two blocks, 02139 // so see if there is any identical code in the "then" and "else" 02140 // blocks. If so, we can hoist it up to the branching block. 02141 Changed |= HoistThenElseCodeToIf(BI); 02142 } else { 02143 BasicBlock* OnlySucc = NULL; 02144 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); 02145 SI != SE; ++SI) { 02146 if (!OnlySucc) 02147 OnlySucc = *SI; 02148 else if (*SI != OnlySucc) { 02149 OnlySucc = 0; // There are multiple distinct successors! 02150 break; 02151 } 02152 } 02153 02154 if (OnlySucc == OtherBB) { 02155 // If BB's only successor is the other successor of the predecessor, 02156 // i.e. a triangle, see if we can hoist any code from this block up 02157 // to the "if" block. 02158 Changed |= SpeculativelyExecuteBB(BI, BB); 02159 } 02160 } 02161 } 02162 02163 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 02164 if (BranchInst *BI = dyn_cast<BranchInst>((*PI)->getTerminator())) 02165 // Change br (X == 0 | X == 1), T, F into a switch instruction. 02166 if (BI->isConditional() && isa<Instruction>(BI->getCondition())) { 02167 Instruction *Cond = cast<Instruction>(BI->getCondition()); 02168 // If this is a bunch of seteq's or'd together, or if it's a bunch of 02169 // 'setne's and'ed together, collect them. 02170 Value *CompVal = 0; 02171 std::vector<ConstantInt*> Values; 02172 bool TrueWhenEqual = GatherValueComparisons(Cond, CompVal, Values); 02173 if (CompVal && CompVal->getType()->isInteger()) { 02174 // There might be duplicate constants in the list, which the switch 02175 // instruction can't handle, remove them now. 02176 std::sort(Values.begin(), Values.end(), ConstantIntOrdering()); 02177 Values.erase(std::unique(Values.begin(), Values.end()), Values.end()); 02178 02179 // Figure out which block is which destination. 02180 BasicBlock *DefaultBB = BI->getSuccessor(1); 02181 BasicBlock *EdgeBB = BI->getSuccessor(0); 02182 if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB); 02183 02184 // Create the new switch instruction now. 02185 SwitchInst *New = SwitchInst::Create(CompVal, DefaultBB, 02186 Values.size(), BI); 02187 02188 // Add all of the 'cases' to the switch instruction. 02189 for (unsigned i = 0, e = Values.size(); i != e; ++i) 02190 New->addCase(Values[i], EdgeBB); 02191 02192 // We added edges from PI to the EdgeBB. As such, if there were any 02193 // PHI nodes in EdgeBB, they need entries to be added corresponding to 02194 // the number of edges added. 02195 for (BasicBlock::iterator BBI = EdgeBB->begin(); 02196 isa<PHINode>(BBI); ++BBI) { 02197 PHINode *PN = cast<PHINode>(BBI); 02198 Value *InVal = PN->getIncomingValueForBlock(*PI); 02199 for (unsigned i = 0, e = Values.size()-1; i != e; ++i) 02200 PN->addIncoming(InVal, *PI); 02201 } 02202 02203 // Erase the old branch instruction. 02204 EraseTerminatorInstAndDCECond(BI); 02205 return true; 02206 } 02207 } 02208 02209 return Changed; 02210 }