LLVM API Documentation
00001 //===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source 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/Type.h" 00019 #include "llvm/Support/CFG.h" 00020 #include "llvm/Support/Debug.h" 00021 #include <algorithm> 00022 #include <functional> 00023 #include <set> 00024 #include <map> 00025 using namespace llvm; 00026 00027 // PropagatePredecessorsForPHIs - This gets "Succ" ready to have the 00028 // predecessors from "BB". This is a little tricky because "Succ" has PHI 00029 // nodes, which need to have extra slots added to them to hold the merge edges 00030 // from BB's predecessors, and BB itself might have had PHI nodes in it. This 00031 // function returns true (failure) if the Succ BB already has a predecessor that 00032 // is a predecessor of BB and incoming PHI arguments would not be discernible. 00033 // 00034 // Assumption: Succ is the single successor for BB. 00035 // 00036 static bool PropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 00037 assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 00038 00039 if (!isa<PHINode>(Succ->front())) 00040 return false; // We can make the transformation, no problem. 00041 00042 // If there is more than one predecessor, and there are PHI nodes in 00043 // the successor, then we need to add incoming edges for the PHI nodes 00044 // 00045 const std::vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB)); 00046 00047 // Check to see if one of the predecessors of BB is already a predecessor of 00048 // Succ. If so, we cannot do the transformation if there are any PHI nodes 00049 // with incompatible values coming in from the two edges! 00050 // 00051 for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); PI != PE; ++PI) 00052 if (std::find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end()) { 00053 // Loop over all of the PHI nodes checking to see if there are 00054 // incompatible values coming in. 00055 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 00056 PHINode *PN = cast<PHINode>(I); 00057 // Loop up the entries in the PHI node for BB and for *PI if the values 00058 // coming in are non-equal, we cannot merge these two blocks (instead we 00059 // should insert a conditional move or something, then merge the 00060 // blocks). 00061 int Idx1 = PN->getBasicBlockIndex(BB); 00062 int Idx2 = PN->getBasicBlockIndex(*PI); 00063 assert(Idx1 != -1 && Idx2 != -1 && 00064 "Didn't have entries for my predecessors??"); 00065 if (PN->getIncomingValue(Idx1) != PN->getIncomingValue(Idx2)) 00066 return true; // Values are not equal... 00067 } 00068 } 00069 00070 // Loop over all of the PHI nodes in the successor BB. 00071 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 00072 PHINode *PN = cast<PHINode>(I); 00073 Value *OldVal = PN->removeIncomingValue(BB, false); 00074 assert(OldVal && "No entry in PHI for Pred BB!"); 00075 00076 // If this incoming value is one of the PHI nodes in BB, the new entries in 00077 // the PHI node are the entries from the old PHI. 00078 if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 00079 PHINode *OldValPN = cast<PHINode>(OldVal); 00080 for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) 00081 PN->addIncoming(OldValPN->getIncomingValue(i), 00082 OldValPN->getIncomingBlock(i)); 00083 } else { 00084 for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(), 00085 End = BBPreds.end(); PredI != End; ++PredI) { 00086 // Add an incoming value for each of the new incoming values... 00087 PN->addIncoming(OldVal, *PredI); 00088 } 00089 } 00090 } 00091 return false; 00092 } 00093 00094 /// GetIfCondition - Given a basic block (BB) with two predecessors (and 00095 /// presumably PHI nodes in it), check to see if the merge at this block is due 00096 /// to an "if condition". If so, return the boolean condition that determines 00097 /// which entry into BB will be taken. Also, return by references the block 00098 /// that will be entered from if the condition is true, and the block that will 00099 /// be entered if the condition is false. 00100 /// 00101 /// 00102 static Value *GetIfCondition(BasicBlock *BB, 00103 BasicBlock *&IfTrue, BasicBlock *&IfFalse) { 00104 assert(std::distance(pred_begin(BB), pred_end(BB)) == 2 && 00105 "Function can only handle blocks with 2 predecessors!"); 00106 BasicBlock *Pred1 = *pred_begin(BB); 00107 BasicBlock *Pred2 = *++pred_begin(BB); 00108 00109 // We can only handle branches. Other control flow will be lowered to 00110 // branches if possible anyway. 00111 if (!isa<BranchInst>(Pred1->getTerminator()) || 00112 !isa<BranchInst>(Pred2->getTerminator())) 00113 return 0; 00114 BranchInst *Pred1Br = cast<BranchInst>(Pred1->getTerminator()); 00115 BranchInst *Pred2Br = cast<BranchInst>(Pred2->getTerminator()); 00116 00117 // Eliminate code duplication by ensuring that Pred1Br is conditional if 00118 // either are. 00119 if (Pred2Br->isConditional()) { 00120 // If both branches are conditional, we don't have an "if statement". In 00121 // reality, we could transform this case, but since the condition will be 00122 // required anyway, we stand no chance of eliminating it, so the xform is 00123 // probably not profitable. 00124 if (Pred1Br->isConditional()) 00125 return 0; 00126 00127 std::swap(Pred1, Pred2); 00128 std::swap(Pred1Br, Pred2Br); 00129 } 00130 00131 if (Pred1Br->isConditional()) { 00132 // If we found a conditional branch predecessor, make sure that it branches 00133 // to BB and Pred2Br. If it doesn't, this isn't an "if statement". 00134 if (Pred1Br->getSuccessor(0) == BB && 00135 Pred1Br->getSuccessor(1) == Pred2) { 00136 IfTrue = Pred1; 00137 IfFalse = Pred2; 00138 } else if (Pred1Br->getSuccessor(0) == Pred2 && 00139 Pred1Br->getSuccessor(1) == BB) { 00140 IfTrue = Pred2; 00141 IfFalse = Pred1; 00142 } else { 00143 // We know that one arm of the conditional goes to BB, so the other must 00144 // go somewhere unrelated, and this must not be an "if statement". 00145 return 0; 00146 } 00147 00148 // The only thing we have to watch out for here is to make sure that Pred2 00149 // doesn't have incoming edges from other blocks. If it does, the condition 00150 // doesn't dominate BB. 00151 if (++pred_begin(Pred2) != pred_end(Pred2)) 00152 return 0; 00153 00154 return Pred1Br->getCondition(); 00155 } 00156 00157 // Ok, if we got here, both predecessors end with an unconditional branch to 00158 // BB. Don't panic! If both blocks only have a single (identical) 00159 // predecessor, and THAT is a conditional branch, then we're all ok! 00160 if (pred_begin(Pred1) == pred_end(Pred1) || 00161 ++pred_begin(Pred1) != pred_end(Pred1) || 00162 pred_begin(Pred2) == pred_end(Pred2) || 00163 ++pred_begin(Pred2) != pred_end(Pred2) || 00164 *pred_begin(Pred1) != *pred_begin(Pred2)) 00165 return 0; 00166 00167 // Otherwise, if this is a conditional branch, then we can use it! 00168 BasicBlock *CommonPred = *pred_begin(Pred1); 00169 if (BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator())) { 00170 assert(BI->isConditional() && "Two successors but not conditional?"); 00171 if (BI->getSuccessor(0) == Pred1) { 00172 IfTrue = Pred1; 00173 IfFalse = Pred2; 00174 } else { 00175 IfTrue = Pred2; 00176 IfFalse = Pred1; 00177 } 00178 return BI->getCondition(); 00179 } 00180 return 0; 00181 } 00182 00183 00184 // If we have a merge point of an "if condition" as accepted above, return true 00185 // if the specified value dominates the block. We don't handle the true 00186 // generality of domination here, just a special case which works well enough 00187 // for us. 00188 // 00189 // If AggressiveInsts is non-null, and if V does not dominate BB, we check to 00190 // see if V (which must be an instruction) is cheap to compute and is 00191 // non-trapping. If both are true, the instruction is inserted into the set and 00192 // true is returned. 00193 static bool DominatesMergePoint(Value *V, BasicBlock *BB, 00194 std::set<Instruction*> *AggressiveInsts) { 00195 Instruction *I = dyn_cast<Instruction>(V); 00196 if (!I) return true; // Non-instructions all dominate instructions. 00197 BasicBlock *PBB = I->getParent(); 00198 00199 // We don't want to allow wierd loops that might have the "if condition" in 00200 // the bottom of this block. 00201 if (PBB == BB) return false; 00202 00203 // If this instruction is defined in a block that contains an unconditional 00204 // branch to BB, then it must be in the 'conditional' part of the "if 00205 // statement". 00206 if (BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator())) 00207 if (BI->isUnconditional() && BI->getSuccessor(0) == BB) { 00208 if (!AggressiveInsts) return false; 00209 // Okay, it looks like the instruction IS in the "condition". Check to 00210 // see if its a cheap instruction to unconditionally compute, and if it 00211 // only uses stuff defined outside of the condition. If so, hoist it out. 00212 switch (I->getOpcode()) { 00213 default: return false; // Cannot hoist this out safely. 00214 case Instruction::Load: 00215 // We can hoist loads that are non-volatile and obviously cannot trap. 00216 if (cast<LoadInst>(I)->isVolatile()) 00217 return false; 00218 if (!isa<AllocaInst>(I->getOperand(0)) && 00219 !isa<Constant>(I->getOperand(0))) 00220 return false; 00221 00222 // Finally, we have to check to make sure there are no instructions 00223 // before the load in its basic block, as we are going to hoist the loop 00224 // out to its predecessor. 00225 if (PBB->begin() != BasicBlock::iterator(I)) 00226 return false; 00227 break; 00228 case Instruction::Add: 00229 case Instruction::Sub: 00230 case Instruction::And: 00231 case Instruction::Or: 00232 case Instruction::Xor: 00233 case Instruction::Shl: 00234 case Instruction::Shr: 00235 break; // These are all cheap and non-trapping instructions. 00236 } 00237 00238 // Okay, we can only really hoist these out if their operands are not 00239 // defined in the conditional region. 00240 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 00241 if (!DominatesMergePoint(I->getOperand(i), BB, 0)) 00242 return false; 00243 // Okay, it's safe to do this! Remember this instruction. 00244 AggressiveInsts->insert(I); 00245 } 00246 00247 return true; 00248 } 00249 00250 // GatherConstantSetEQs - Given a potentially 'or'd together collection of seteq 00251 // instructions that compare a value against a constant, return the value being 00252 // compared, and stick the constant into the Values vector. 00253 static Value *GatherConstantSetEQs(Value *V, std::vector<ConstantInt*> &Values){ 00254 if (Instruction *Inst = dyn_cast<Instruction>(V)) 00255 if (Inst->getOpcode() == Instruction::SetEQ) { 00256 if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) { 00257 Values.push_back(C); 00258 return Inst->getOperand(0); 00259 } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) { 00260 Values.push_back(C); 00261 return Inst->getOperand(1); 00262 } 00263 } else if (Inst->getOpcode() == Instruction::Or) { 00264 if (Value *LHS = GatherConstantSetEQs(Inst->getOperand(0), Values)) 00265 if (Value *RHS = GatherConstantSetEQs(Inst->getOperand(1), Values)) 00266 if (LHS == RHS) 00267 return LHS; 00268 } 00269 return 0; 00270 } 00271 00272 // GatherConstantSetNEs - Given a potentially 'and'd together collection of 00273 // setne instructions that compare a value against a constant, return the value 00274 // being compared, and stick the constant into the Values vector. 00275 static Value *GatherConstantSetNEs(Value *V, std::vector<ConstantInt*> &Values){ 00276 if (Instruction *Inst = dyn_cast<Instruction>(V)) 00277 if (Inst->getOpcode() == Instruction::SetNE) { 00278 if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) { 00279 Values.push_back(C); 00280 return Inst->getOperand(0); 00281 } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) { 00282 Values.push_back(C); 00283 return Inst->getOperand(1); 00284 } 00285 } else if (Inst->getOpcode() == Instruction::Cast) { 00286 // Cast of X to bool is really a comparison against zero. 00287 assert(Inst->getType() == Type::BoolTy && "Can only handle bool values!"); 00288 Values.push_back(ConstantInt::get(Inst->getOperand(0)->getType(), 0)); 00289 return Inst->getOperand(0); 00290 } else if (Inst->getOpcode() == Instruction::And) { 00291 if (Value *LHS = GatherConstantSetNEs(Inst->getOperand(0), Values)) 00292 if (Value *RHS = GatherConstantSetNEs(Inst->getOperand(1), Values)) 00293 if (LHS == RHS) 00294 return LHS; 00295 } 00296 return 0; 00297 } 00298 00299 00300 00301 /// GatherValueComparisons - If the specified Cond is an 'and' or 'or' of a 00302 /// bunch of comparisons of one value against constants, return the value and 00303 /// the constants being compared. 00304 static bool GatherValueComparisons(Instruction *Cond, Value *&CompVal, 00305 std::vector<ConstantInt*> &Values) { 00306 if (Cond->getOpcode() == Instruction::Or) { 00307 CompVal = GatherConstantSetEQs(Cond, Values); 00308 00309 // Return true to indicate that the condition is true if the CompVal is 00310 // equal to one of the constants. 00311 return true; 00312 } else if (Cond->getOpcode() == Instruction::And) { 00313 CompVal = GatherConstantSetNEs(Cond, Values); 00314 00315 // Return false to indicate that the condition is false if the CompVal is 00316 // equal to one of the constants. 00317 return false; 00318 } 00319 return false; 00320 } 00321 00322 /// ErasePossiblyDeadInstructionTree - If the specified instruction is dead and 00323 /// has no side effects, nuke it. If it uses any instructions that become dead 00324 /// because the instruction is now gone, nuke them too. 00325 static void ErasePossiblyDeadInstructionTree(Instruction *I) { 00326 if (isInstructionTriviallyDead(I)) { 00327 std::vector<Value*> Operands(I->op_begin(), I->op_end()); 00328 I->getParent()->getInstList().erase(I); 00329 for (unsigned i = 0, e = Operands.size(); i != e; ++i) 00330 if (Instruction *OpI = dyn_cast<Instruction>(Operands[i])) 00331 ErasePossiblyDeadInstructionTree(OpI); 00332 } 00333 } 00334 00335 /// SafeToMergeTerminators - Return true if it is safe to merge these two 00336 /// terminator instructions together. 00337 /// 00338 static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) { 00339 if (SI1 == SI2) return false; // Can't merge with self! 00340 00341 // It is not safe to merge these two switch instructions if they have a common 00342 // successor, and if that successor has a PHI node, and if *that* PHI node has 00343 // conflicting incoming values from the two switch blocks. 00344 BasicBlock *SI1BB = SI1->getParent(); 00345 BasicBlock *SI2BB = SI2->getParent(); 00346 std::set<BasicBlock*> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 00347 00348 for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) 00349 if (SI1Succs.count(*I)) 00350 for (BasicBlock::iterator BBI = (*I)->begin(); 00351 isa<PHINode>(BBI); ++BBI) { 00352 PHINode *PN = cast<PHINode>(BBI); 00353 if (PN->getIncomingValueForBlock(SI1BB) != 00354 PN->getIncomingValueForBlock(SI2BB)) 00355 return false; 00356 } 00357 00358 return true; 00359 } 00360 00361 /// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will 00362 /// now be entries in it from the 'NewPred' block. The values that will be 00363 /// flowing into the PHI nodes will be the same as those coming in from 00364 /// ExistPred, an existing predecessor of Succ. 00365 static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, 00366 BasicBlock *ExistPred) { 00367 assert(std::find(succ_begin(ExistPred), succ_end(ExistPred), Succ) != 00368 succ_end(ExistPred) && "ExistPred is not a predecessor of Succ!"); 00369 if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do 00370 00371 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 00372 PHINode *PN = cast<PHINode>(I); 00373 Value *V = PN->getIncomingValueForBlock(ExistPred); 00374 PN->addIncoming(V, NewPred); 00375 } 00376 } 00377 00378 // isValueEqualityComparison - Return true if the specified terminator checks to 00379 // see if a value is equal to constant integer value. 00380 static Value *isValueEqualityComparison(TerminatorInst *TI) { 00381 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 00382 // Do not permit merging of large switch instructions into their 00383 // predecessors unless there is only one predecessor. 00384 if (SI->getNumSuccessors() * std::distance(pred_begin(SI->getParent()), 00385 pred_end(SI->getParent())) > 128) 00386 return 0; 00387 00388 return SI->getCondition(); 00389 } 00390 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 00391 if (BI->isConditional() && BI->getCondition()->hasOneUse()) 00392 if (SetCondInst *SCI = dyn_cast<SetCondInst>(BI->getCondition())) 00393 if ((SCI->getOpcode() == Instruction::SetEQ || 00394 SCI->getOpcode() == Instruction::SetNE) && 00395 isa<ConstantInt>(SCI->getOperand(1))) 00396 return SCI->getOperand(0); 00397 return 0; 00398 } 00399 00400 // Given a value comparison instruction, decode all of the 'cases' that it 00401 // represents and return the 'default' block. 00402 static BasicBlock * 00403 GetValueEqualityComparisonCases(TerminatorInst *TI, 00404 std::vector<std::pair<ConstantInt*, 00405 BasicBlock*> > &Cases) { 00406 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 00407 Cases.reserve(SI->getNumCases()); 00408 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 00409 Cases.push_back(std::make_pair(cast<ConstantInt>(SI->getCaseValue(i)), 00410 SI->getSuccessor(i))); 00411 return SI->getDefaultDest(); 00412 } 00413 00414 BranchInst *BI = cast<BranchInst>(TI); 00415 SetCondInst *SCI = cast<SetCondInst>(BI->getCondition()); 00416 Cases.push_back(std::make_pair(cast<ConstantInt>(SCI->getOperand(1)), 00417 BI->getSuccessor(SCI->getOpcode() == 00418 Instruction::SetNE))); 00419 return BI->getSuccessor(SCI->getOpcode() == Instruction::SetEQ); 00420 } 00421 00422 00423 // FoldValueComparisonIntoPredecessors - The specified terminator is a value 00424 // equality comparison instruction (either a switch or a branch on "X == c"). 00425 // See if any of the predecessors of the terminator block are value comparisons 00426 // on the same value. If so, and if safe to do so, fold them together. 00427 static bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { 00428 BasicBlock *BB = TI->getParent(); 00429 Value *CV = isValueEqualityComparison(TI); // CondVal 00430 assert(CV && "Not a comparison?"); 00431 bool Changed = false; 00432 00433 std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 00434 while (!Preds.empty()) { 00435 BasicBlock *Pred = Preds.back(); 00436 Preds.pop_back(); 00437 00438 // See if the predecessor is a comparison with the same value. 00439 TerminatorInst *PTI = Pred->getTerminator(); 00440 Value *PCV = isValueEqualityComparison(PTI); // PredCondVal 00441 00442 if (PCV == CV && SafeToMergeTerminators(TI, PTI)) { 00443 // Figure out which 'cases' to copy from SI to PSI. 00444 std::vector<std::pair<ConstantInt*, BasicBlock*> > BBCases; 00445 BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases); 00446 00447 std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 00448 BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases); 00449 00450 // Based on whether the default edge from PTI goes to BB or not, fill in 00451 // PredCases and PredDefault with the new switch cases we would like to 00452 // build. 00453 std::vector<BasicBlock*> NewSuccessors; 00454 00455 if (PredDefault == BB) { 00456 // If this is the default destination from PTI, only the edges in TI 00457 // that don't occur in PTI, or that branch to BB will be activated. 00458 std::set<ConstantInt*> PTIHandled; 00459 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 00460 if (PredCases[i].second != BB) 00461 PTIHandled.insert(PredCases[i].first); 00462 else { 00463 // The default destination is BB, we don't need explicit targets. 00464 std::swap(PredCases[i], PredCases.back()); 00465 PredCases.pop_back(); 00466 --i; --e; 00467 } 00468 00469 // Reconstruct the new switch statement we will be building. 00470 if (PredDefault != BBDefault) { 00471 PredDefault->removePredecessor(Pred); 00472 PredDefault = BBDefault; 00473 NewSuccessors.push_back(BBDefault); 00474 } 00475 for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 00476 if (!PTIHandled.count(BBCases[i].first) && 00477 BBCases[i].second != BBDefault) { 00478 PredCases.push_back(BBCases[i]); 00479 NewSuccessors.push_back(BBCases[i].second); 00480 } 00481 00482 } else { 00483 // If this is not the default destination from PSI, only the edges 00484 // in SI that occur in PSI with a destination of BB will be 00485 // activated. 00486 std::set<ConstantInt*> PTIHandled; 00487 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 00488 if (PredCases[i].second == BB) { 00489 PTIHandled.insert(PredCases[i].first); 00490 std::swap(PredCases[i], PredCases.back()); 00491 PredCases.pop_back(); 00492 --i; --e; 00493 } 00494 00495 // Okay, now we know which constants were sent to BB from the 00496 // predecessor. Figure out where they will all go now. 00497 for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 00498 if (PTIHandled.count(BBCases[i].first)) { 00499 // If this is one we are capable of getting... 00500 PredCases.push_back(BBCases[i]); 00501 NewSuccessors.push_back(BBCases[i].second); 00502 PTIHandled.erase(BBCases[i].first);// This constant is taken care of 00503 } 00504 00505 // If there are any constants vectored to BB that TI doesn't handle, 00506 // they must go to the default destination of TI. 00507 for (std::set<ConstantInt*>::iterator I = PTIHandled.begin(), 00508 E = PTIHandled.end(); I != E; ++I) { 00509 PredCases.push_back(std::make_pair(*I, BBDefault)); 00510 NewSuccessors.push_back(BBDefault); 00511 } 00512 } 00513 00514 // Okay, at this point, we know which new successor Pred will get. Make 00515 // sure we update the number of entries in the PHI nodes for these 00516 // successors. 00517 for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i) 00518 AddPredecessorToBlock(NewSuccessors[i], Pred, BB); 00519 00520 // Now that the successors are updated, create the new Switch instruction. 00521 SwitchInst *NewSI = new SwitchInst(CV, PredDefault, PTI); 00522 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 00523 NewSI->addCase(PredCases[i].first, PredCases[i].second); 00524 Pred->getInstList().erase(PTI); 00525 00526 // Okay, last check. If BB is still a successor of PSI, then we must 00527 // have an infinite loop case. If so, add an infinitely looping block 00528 // to handle the case to preserve the behavior of the code. 00529 BasicBlock *InfLoopBlock = 0; 00530 for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i) 00531 if (NewSI->getSuccessor(i) == BB) { 00532 if (InfLoopBlock == 0) { 00533 // Insert it at the end of the loop, because it's either code, 00534 // or it won't matter if it's hot. :) 00535 InfLoopBlock = new BasicBlock("infloop", BB->getParent()); 00536 new BranchInst(InfLoopBlock, InfLoopBlock); 00537 } 00538 NewSI->setSuccessor(i, InfLoopBlock); 00539 } 00540 00541 Changed = true; 00542 } 00543 } 00544 return Changed; 00545 } 00546 00547 /// HoistThenElseCodeToIf - Given a conditional branch that codes to BB1 and 00548 /// BB2, hoist any common code in the two blocks up into the branch block. The 00549 /// caller of this function guarantees that BI's block dominates BB1 and BB2. 00550 static bool HoistThenElseCodeToIf(BranchInst *BI) { 00551 // This does very trivial matching, with limited scanning, to find identical 00552 // instructions in the two blocks. In particular, we don't want to get into 00553 // O(M*N) situations here where M and N are the sizes of BB1 and BB2. As 00554 // such, we currently just scan for obviously identical instructions in an 00555 // identical order. 00556 BasicBlock *BB1 = BI->getSuccessor(0); // The true destination. 00557 BasicBlock *BB2 = BI->getSuccessor(1); // The false destination 00558 00559 Instruction *I1 = BB1->begin(), *I2 = BB2->begin(); 00560 if (I1->getOpcode() != I2->getOpcode() || !I1->isIdenticalTo(I2)) 00561 return false; 00562 00563 // If we get here, we can hoist at least one instruction. 00564 BasicBlock *BIParent = BI->getParent(); 00565 00566 do { 00567 // If we are hoisting the terminator instruction, don't move one (making a 00568 // broken BB), instead clone it, and remove BI. 00569 if (isa<TerminatorInst>(I1)) 00570 goto HoistTerminator; 00571 00572 // For a normal instruction, we just move one to right before the branch, 00573 // then replace all uses of the other with the first. Finally, we remove 00574 // the now redundant second instruction. 00575 BIParent->getInstList().splice(BI, BB1->getInstList(), I1); 00576 if (!I2->use_empty()) 00577 I2->replaceAllUsesWith(I1); 00578 BB2->getInstList().erase(I2); 00579 00580 I1 = BB1->begin(); 00581 I2 = BB2->begin(); 00582 } while (I1->getOpcode() == I2->getOpcode() && I1->isIdenticalTo(I2)); 00583 00584 return true; 00585 00586 HoistTerminator: 00587 // Okay, it is safe to hoist the terminator. 00588 Instruction *NT = I1->clone(); 00589 BIParent->getInstList().insert(BI, NT); 00590 if (NT->getType() != Type::VoidTy) { 00591 I1->replaceAllUsesWith(NT); 00592 I2->replaceAllUsesWith(NT); 00593 NT->setName(I1->getName()); 00594 } 00595 00596 // Hoisting one of the terminators from our successor is a great thing. 00597 // Unfortunately, the successors of the if/else blocks may have PHI nodes in 00598 // them. If they do, all PHI entries for BB1/BB2 must agree for all PHI 00599 // nodes, so we insert select instruction to compute the final result. 00600 std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects; 00601 for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 00602 PHINode *PN; 00603 for (BasicBlock::iterator BBI = SI->begin(); 00604 (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 00605 Value *BB1V = PN->getIncomingValueForBlock(BB1); 00606 Value *BB2V = PN->getIncomingValueForBlock(BB2); 00607 if (BB1V != BB2V) { 00608 // These values do not agree. Insert a select instruction before NT 00609 // that determines the right value. 00610 SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)]; 00611 if (SI == 0) 00612 SI = new SelectInst(BI->getCondition(), BB1V, BB2V, 00613 BB1V->getName()+"."+BB2V->getName(), NT); 00614 // Make the PHI node use the select for all incoming values for BB1/BB2 00615 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 00616 if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2) 00617 PN->setIncomingValue(i, SI); 00618 } 00619 } 00620 } 00621 00622 // Update any PHI nodes in our new successors. 00623 for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) 00624 AddPredecessorToBlock(*SI, BIParent, BB1); 00625 00626 BI->eraseFromParent(); 00627 return true; 00628 } 00629 00630 namespace { 00631 /// ConstantIntOrdering - This class implements a stable ordering of constant 00632 /// integers that does not depend on their address. This is important for 00633 /// applications that sort ConstantInt's to ensure uniqueness. 00634 struct ConstantIntOrdering { 00635 bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { 00636 return LHS->getRawValue() < RHS->getRawValue(); 00637 } 00638 }; 00639 } 00640 00641 00642 // SimplifyCFG - This function is used to do simplification of a CFG. For 00643 // example, it adjusts branches to branches to eliminate the extra hop, it 00644 // eliminates unreachable basic blocks, and does other "peephole" optimization 00645 // of the CFG. It returns true if a modification was made. 00646 // 00647 // WARNING: The entry node of a function may not be simplified. 00648 // 00649 bool llvm::SimplifyCFG(BasicBlock *BB) { 00650 bool Changed = false; 00651 Function *M = BB->getParent(); 00652 00653 assert(BB && BB->getParent() && "Block not embedded in function!"); 00654 assert(BB->getTerminator() && "Degenerate basic block encountered!"); 00655 assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!"); 00656 00657 // Remove basic blocks that have no predecessors... which are unreachable. 00658 if (pred_begin(BB) == pred_end(BB) || 00659 *pred_begin(BB) == BB && ++pred_begin(BB) == pred_end(BB)) { 00660 DEBUG(std::cerr << "Removing BB: \n" << *BB); 00661 00662 // Loop through all of our successors and make sure they know that one 00663 // of their predecessors is going away. 00664 for_each(succ_begin(BB), succ_end(BB), 00665 std::bind2nd(std::mem_fun(&BasicBlock::removePredecessor), BB)); 00666 00667 while (!BB->empty()) { 00668 Instruction &I = BB->back(); 00669 // If this instruction is used, replace uses with an arbitrary 00670 // constant value. Because control flow can't get here, we don't care 00671 // what we replace the value with. Note that since this block is 00672 // unreachable, and all values contained within it must dominate their 00673 // uses, that all uses will eventually be removed. 00674 if (!I.use_empty()) 00675 // Make all users of this instruction reference the constant instead 00676 I.replaceAllUsesWith(Constant::getNullValue(I.getType())); 00677 00678 // Remove the instruction from the basic block 00679 BB->getInstList().pop_back(); 00680 } 00681 M->getBasicBlockList().erase(BB); 00682 return true; 00683 } 00684 00685 // Check to see if we can constant propagate this terminator instruction 00686 // away... 00687 Changed |= ConstantFoldTerminator(BB); 00688 00689 // Check to see if this block has no non-phi instructions and only a single 00690 // successor. If so, replace references to this basic block with references 00691 // to the successor. 00692 succ_iterator SI(succ_begin(BB)); 00693 if (SI != succ_end(BB) && ++SI == succ_end(BB)) { // One succ? 00694 BasicBlock::iterator BBI = BB->begin(); // Skip over phi nodes... 00695 while (isa<PHINode>(*BBI)) ++BBI; 00696 00697 BasicBlock *Succ = *succ_begin(BB); // There is exactly one successor. 00698 if (BBI->isTerminator() && // Terminator is the only non-phi instruction! 00699 Succ != BB) { // Don't hurt infinite loops! 00700 // If our successor has PHI nodes, then we need to update them to include 00701 // entries for BB's predecessors, not for BB itself. Be careful though, 00702 // if this transformation fails (returns true) then we cannot do this 00703 // transformation! 00704 // 00705 if (!PropagatePredecessorsForPHIs(BB, Succ)) { 00706 DEBUG(std::cerr << "Killing Trivial BB: \n" << *BB); 00707 00708 if (isa<PHINode>(&BB->front())) { 00709 std::vector<BasicBlock*> 00710 OldSuccPreds(pred_begin(Succ), pred_end(Succ)); 00711 00712 // Move all PHI nodes in BB to Succ if they are alive, otherwise 00713 // delete them. 00714 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) 00715 if (PN->use_empty()) 00716 BB->getInstList().erase(BB->begin()); // Nuke instruction. 00717 else { 00718 // The instruction is alive, so this means that Succ must have 00719 // *ONLY* had BB as a predecessor, and the PHI node is still valid 00720 // now. Simply move it into Succ, because we know that BB 00721 // strictly dominated Succ. 00722 BB->getInstList().remove(BB->begin()); 00723 Succ->getInstList().push_front(PN); 00724 00725 // We need to add new entries for the PHI node to account for 00726 // predecessors of Succ that the PHI node does not take into 00727 // account. At this point, since we know that BB dominated succ, 00728 // this means that we should any newly added incoming edges should 00729 // use the PHI node as the value for these edges, because they are 00730 // loop back edges. 00731 for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i) 00732 if (OldSuccPreds[i] != BB) 00733 PN->addIncoming(PN, OldSuccPreds[i]); 00734 } 00735 } 00736 00737 // Everything that jumped to BB now goes to Succ. 00738 std::string OldName = BB->getName(); 00739 BB->replaceAllUsesWith(Succ); 00740 BB->eraseFromParent(); // Delete the old basic block. 00741 00742 if (!OldName.empty() && !Succ->hasName()) // Transfer name if we can 00743 Succ->setName(OldName); 00744 return true; 00745 } 00746 } 00747 } 00748 00749 // If this is a returning block with only PHI nodes in it, fold the return 00750 // instruction into any unconditional branch predecessors. 00751 // 00752 // If any predecessor is a conditional branch that just selects among 00753 // different return values, fold the replace the branch/return with a select 00754 // and return. 00755 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 00756 BasicBlock::iterator BBI = BB->getTerminator(); 00757 if (BBI == BB->begin() || isa<PHINode>(--BBI)) { 00758 // Find predecessors that end with branches. 00759 std::vector<BasicBlock*> UncondBranchPreds; 00760 std::vector<BranchInst*> CondBranchPreds; 00761 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 00762 TerminatorInst *PTI = (*PI)->getTerminator(); 00763 if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) 00764 if (BI->isUnconditional()) 00765 UncondBranchPreds.push_back(*PI); 00766 else 00767 CondBranchPreds.push_back(BI); 00768 } 00769 00770 // If we found some, do the transformation! 00771 if (!UncondBranchPreds.empty()) { 00772 while (!UncondBranchPreds.empty()) { 00773 BasicBlock *Pred = UncondBranchPreds.back(); 00774 UncondBranchPreds.pop_back(); 00775 Instruction *UncondBranch = Pred->getTerminator(); 00776 // Clone the return and add it to the end of the predecessor. 00777 Instruction *NewRet = RI->clone(); 00778 Pred->getInstList().push_back(NewRet); 00779 00780 // If the return instruction returns a value, and if the value was a 00781 // PHI node in "BB", propagate the right value into the return. 00782 if (NewRet->getNumOperands() == 1) 00783 if (PHINode *PN = dyn_cast<PHINode>(NewRet->getOperand(0))) 00784 if (PN->getParent() == BB) 00785 NewRet->setOperand(0, PN->getIncomingValueForBlock(Pred)); 00786 // Update any PHI nodes in the returning block to realize that we no 00787 // longer branch to them. 00788 BB->removePredecessor(Pred); 00789 Pred->getInstList().erase(UncondBranch); 00790 } 00791 00792 // If we eliminated all predecessors of the block, delete the block now. 00793 if (pred_begin(BB) == pred_end(BB)) 00794 // We know there are no successors, so just nuke the block. 00795 M->getBasicBlockList().erase(BB); 00796 00797 return true; 00798 } 00799 00800 // Check out all of the conditional branches going to this return 00801 // instruction. If any of them just select between returns, change the 00802 // branch itself into a select/return pair. 00803 while (!CondBranchPreds.empty()) { 00804 BranchInst *BI = CondBranchPreds.back(); 00805 CondBranchPreds.pop_back(); 00806 BasicBlock *TrueSucc = BI->getSuccessor(0); 00807 BasicBlock *FalseSucc = BI->getSuccessor(1); 00808 BasicBlock *OtherSucc = TrueSucc == BB ? FalseSucc : TrueSucc; 00809 00810 // Check to see if the non-BB successor is also a return block. 00811 if (isa<ReturnInst>(OtherSucc->getTerminator())) { 00812 // Check to see if there are only PHI instructions in this block. 00813 BasicBlock::iterator OSI = OtherSucc->getTerminator(); 00814 if (OSI == OtherSucc->begin() || isa<PHINode>(--OSI)) { 00815 // Okay, we found a branch that is going to two return nodes. If 00816 // there is no return value for this function, just change the 00817 // branch into a return. 00818 if (RI->getNumOperands() == 0) { 00819 TrueSucc->removePredecessor(BI->getParent()); 00820 FalseSucc->removePredecessor(BI->getParent()); 00821 new ReturnInst(0, BI); 00822 BI->getParent()->getInstList().erase(BI); 00823 return true; 00824 } 00825 00826 // Otherwise, figure out what the true and false return values are 00827 // so we can insert a new select instruction. 00828 Value *TrueValue = TrueSucc->getTerminator()->getOperand(0); 00829 Value *FalseValue = FalseSucc->getTerminator()->getOperand(0); 00830 00831 // Unwrap any PHI nodes in the return blocks. 00832 if (PHINode *TVPN = dyn_cast<PHINode>(TrueValue)) 00833 if (TVPN->getParent() == TrueSucc) 00834 TrueValue = TVPN->getIncomingValueForBlock(BI->getParent()); 00835 if (PHINode *FVPN = dyn_cast<PHINode>(FalseValue)) 00836 if (FVPN->getParent() == FalseSucc) 00837 FalseValue = FVPN->getIncomingValueForBlock(BI->getParent()); 00838 00839 TrueSucc->removePredecessor(BI->getParent()); 00840 FalseSucc->removePredecessor(BI->getParent()); 00841 00842 // Insert a new select instruction. 00843 Value *NewRetVal; 00844 Value *BrCond = BI->getCondition(); 00845 if (TrueValue != FalseValue) 00846 NewRetVal = new SelectInst(BrCond, TrueValue, 00847 FalseValue, "retval", BI); 00848 else 00849 NewRetVal = TrueValue; 00850 00851 new ReturnInst(NewRetVal, BI); 00852 BI->getParent()->getInstList().erase(BI); 00853 if (BrCond->use_empty()) 00854 if (Instruction *BrCondI = dyn_cast<Instruction>(BrCond)) 00855 BrCondI->getParent()->getInstList().erase(BrCondI); 00856 return true; 00857 } 00858 } 00859 } 00860 } 00861 } else if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->begin())) { 00862 // Check to see if the first instruction in this block is just an unwind. 00863 // If so, replace any invoke instructions which use this as an exception 00864 // destination with call instructions, and any unconditional branch 00865 // predecessor with an unwind. 00866 // 00867 std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 00868 while (!Preds.empty()) { 00869 BasicBlock *Pred = Preds.back(); 00870 if (BranchInst *BI = dyn_cast<BranchInst>(Pred->getTerminator())) { 00871 if (BI->isUnconditional()) { 00872 Pred->getInstList().pop_back(); // nuke uncond branch 00873 new UnwindInst(Pred); // Use unwind. 00874 Changed = true; 00875 } 00876 } else if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator())) 00877 if (II->getUnwindDest() == BB) { 00878 // Insert a new branch instruction before the invoke, because this 00879 // is now a fall through... 00880 BranchInst *BI = new BranchInst(II->getNormalDest(), II); 00881 Pred->getInstList().remove(II); // Take out of symbol table 00882 00883 // Insert the call now... 00884 std::vector<Value*> Args(II->op_begin()+3, II->op_end()); 00885 CallInst *CI = new CallInst(II->getCalledValue(), Args, 00886 II->getName(), BI); 00887 // If the invoke produced a value, the Call now does instead 00888 II->replaceAllUsesWith(CI); 00889 delete II; 00890 Changed = true; 00891 } 00892 00893 Preds.pop_back(); 00894 } 00895 00896 // If this block is now dead, remove it. 00897 if (pred_begin(BB) == pred_end(BB)) { 00898 // We know there are no successors, so just nuke the block. 00899 M->getBasicBlockList().erase(BB); 00900 return true; 00901 } 00902 00903 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->begin())) { 00904 if (isValueEqualityComparison(SI)) 00905 if (FoldValueComparisonIntoPredecessors(SI)) 00906 return SimplifyCFG(BB) || 1; 00907 } else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 00908 if (BI->isConditional()) { 00909 if (Value *CompVal = isValueEqualityComparison(BI)) { 00910 // This block must be empty, except for the setcond inst, if it exists. 00911 BasicBlock::iterator I = BB->begin(); 00912 if (&*I == BI || 00913 (&*I == cast<Instruction>(BI->getCondition()) && 00914 &*++I == BI)) 00915 if (FoldValueComparisonIntoPredecessors(BI)) 00916 return SimplifyCFG(BB) | true; 00917 } 00918 00919 // If this basic block is ONLY a setcc and a branch, and if a predecessor 00920 // branches to us and one of our successors, fold the setcc into the 00921 // predecessor and use logical operations to pick the right destination. 00922 BasicBlock *TrueDest = BI->getSuccessor(0); 00923 BasicBlock *FalseDest = BI->getSuccessor(1); 00924 if (BinaryOperator *Cond = dyn_cast<BinaryOperator>(BI->getCondition())) 00925 if (Cond->getParent() == BB && &BB->front() == Cond && 00926 Cond->getNext() == BI && Cond->hasOneUse() && 00927 TrueDest != BB && FalseDest != BB) 00928 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI!=E; ++PI) 00929 if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 00930 if (PBI->isConditional() && SafeToMergeTerminators(BI, PBI)) { 00931 BasicBlock *PredBlock = *PI; 00932 if (PBI->getSuccessor(0) == FalseDest || 00933 PBI->getSuccessor(1) == TrueDest) { 00934 // Invert the predecessors condition test (xor it with true), 00935 // which allows us to write this code once. 00936 Value *NewCond = 00937 BinaryOperator::createNot(PBI->getCondition(), 00938 PBI->getCondition()->getName()+".not", PBI); 00939 PBI->setCondition(NewCond); 00940 BasicBlock *OldTrue = PBI->getSuccessor(0); 00941 BasicBlock *OldFalse = PBI->getSuccessor(1); 00942 PBI->setSuccessor(0, OldFalse); 00943 PBI->setSuccessor(1, OldTrue); 00944 } 00945 00946 if (PBI->getSuccessor(0) == TrueDest || 00947 PBI->getSuccessor(1) == FalseDest) { 00948 // Clone Cond into the predecessor basic block, and or/and the 00949 // two conditions together. 00950 Instruction *New = Cond->clone(); 00951 New->setName(Cond->getName()); 00952 Cond->setName(Cond->getName()+".old"); 00953 PredBlock->getInstList().insert(PBI, New); 00954 Instruction::BinaryOps Opcode = 00955 PBI->getSuccessor(0) == TrueDest ? 00956 Instruction::Or : Instruction::And; 00957 Value *NewCond = 00958 BinaryOperator::create(Opcode, PBI->getCondition(), 00959 New, "bothcond", PBI); 00960 PBI->setCondition(NewCond); 00961 if (PBI->getSuccessor(0) == BB) { 00962 AddPredecessorToBlock(TrueDest, PredBlock, BB); 00963 PBI->setSuccessor(0, TrueDest); 00964 } 00965 if (PBI->getSuccessor(1) == BB) { 00966 AddPredecessorToBlock(FalseDest, PredBlock, BB); 00967 PBI->setSuccessor(1, FalseDest); 00968 } 00969 return SimplifyCFG(BB) | 1; 00970 } 00971 } 00972 00973 // If this block ends with a branch instruction, and if there is one 00974 // predecessor, see if the previous block ended with a branch on the same 00975 // condition, which makes this conditional branch redundant. 00976 pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 00977 BasicBlock *OnlyPred = *PI++; 00978 for (; PI != PE; ++PI)// Search all predecessors, see if they are all same 00979 if (*PI != OnlyPred) { 00980 OnlyPred = 0; // There are multiple different predecessors... 00981 break; 00982 } 00983 00984 if (OnlyPred) 00985 if (BranchInst *PBI = dyn_cast<BranchInst>(OnlyPred->getTerminator())) 00986 if (PBI->isConditional() && 00987 PBI->getCondition() == BI->getCondition() && 00988 (PBI->getSuccessor(0) != BB || PBI->getSuccessor(1) != BB)) { 00989 // Okay, the outcome of this conditional branch is statically 00990 // knowable. Delete the outgoing CFG edge that is impossible to 00991 // execute. 00992 bool CondIsTrue = PBI->getSuccessor(0) == BB; 00993 BI->getSuccessor(CondIsTrue)->removePredecessor(BB); 00994 new BranchInst(BI->getSuccessor(!CondIsTrue), BB); 00995 BB->getInstList().erase(BI); 00996 return SimplifyCFG(BB) | true; 00997 } 00998 } 00999 } else if (isa<UnreachableInst>(BB->getTerminator())) { 01000 // If there are any instructions immediately before the unreachable that can 01001 // be removed, do so. 01002 Instruction *Unreachable = BB->getTerminator(); 01003 while (Unreachable != BB->begin()) { 01004 BasicBlock::iterator BBI = Unreachable; 01005 --BBI; 01006 if (isa<CallInst>(BBI)) break; 01007 // Delete this instruction 01008 BB->getInstList().erase(BBI); 01009 Changed = true; 01010 } 01011 01012 // If the unreachable instruction is the first in the block, take a gander 01013 // at all of the predecessors of this instruction, and simplify them. 01014 if (&BB->front() == Unreachable) { 01015 std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 01016 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 01017 TerminatorInst *TI = Preds[i]->getTerminator(); 01018 01019 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 01020 if (BI->isUnconditional()) { 01021 if (BI->getSuccessor(0) == BB) { 01022 new UnreachableInst(TI); 01023 TI->eraseFromParent(); 01024 Changed = true; 01025 } 01026 } else { 01027 if (BI->getSuccessor(0) == BB) { 01028 new BranchInst(BI->getSuccessor(1), BI); 01029 BI->eraseFromParent(); 01030 } else if (BI->getSuccessor(1) == BB) { 01031 new BranchInst(BI->getSuccessor(0), BI); 01032 BI->eraseFromParent(); 01033 Changed = true; 01034 } 01035 } 01036 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 01037 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 01038 if (SI->getSuccessor(i) == BB) { 01039 SI->removeCase(i); 01040 --i; --e; 01041 Changed = true; 01042 } 01043 // If the default value is unreachable, figure out the most popular 01044 // destination and make it the default. 01045 if (SI->getSuccessor(0) == BB) { 01046 std::map<BasicBlock*, unsigned> Popularity; 01047 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 01048 Popularity[SI->getSuccessor(i)]++; 01049 01050 // Find the most popular block. 01051 unsigned MaxPop = 0; 01052 BasicBlock *MaxBlock = 0; 01053 for (std::map<BasicBlock*, unsigned>::iterator 01054 I = Popularity.begin(), E = Popularity.end(); I != E; ++I) { 01055 if (I->second > MaxPop) { 01056 MaxPop = I->second; 01057 MaxBlock = I->first; 01058 } 01059 } 01060 if (MaxBlock) { 01061 // Make this the new default, allowing us to delete any explicit 01062 // edges to it. 01063 SI->setSuccessor(0, MaxBlock); 01064 Changed = true; 01065 01066 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 01067 if (SI->getSuccessor(i) == MaxBlock) { 01068 SI->removeCase(i); 01069 --i; --e; 01070 } 01071 } 01072 } 01073 } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) { 01074 if (II->getUnwindDest() == BB) { 01075 // Convert the invoke to a call instruction. This would be a good 01076 // place to note that the call does not throw though. 01077 BranchInst *BI = new BranchInst(II->getNormalDest(), II); 01078 II->removeFromParent(); // Take out of symbol table 01079 01080 // Insert the call now... 01081 std::vector<Value*> Args(II->op_begin()+3, II->op_end()); 01082 CallInst *CI = new CallInst(II->getCalledValue(), Args, 01083 II->getName(), BI); 01084 // If the invoke produced a value, the Call does now instead. 01085 II->replaceAllUsesWith(CI); 01086 delete II; 01087 Changed = true; 01088 } 01089 } 01090 } 01091 01092 // If this block is now dead, remove it. 01093 if (pred_begin(BB) == pred_end(BB)) { 01094 // We know there are no successors, so just nuke the block. 01095 M->getBasicBlockList().erase(BB); 01096 return true; 01097 } 01098 } 01099 } 01100 01101 // Merge basic blocks into their predecessor if there is only one distinct 01102 // pred, and if there is only one distinct successor of the predecessor, and 01103 // if there are no PHI nodes. 01104 // 01105 pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 01106 BasicBlock *OnlyPred = *PI++; 01107 for (; PI != PE; ++PI) // Search all predecessors, see if they are all same 01108 if (*PI != OnlyPred) { 01109 OnlyPred = 0; // There are multiple different predecessors... 01110 break; 01111 } 01112 01113 BasicBlock *OnlySucc = 0; 01114 if (OnlyPred && OnlyPred != BB && // Don't break self loops 01115 OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) { 01116 // Check to see if there is only one distinct successor... 01117 succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred)); 01118 OnlySucc = BB; 01119 for (; SI != SE; ++SI) 01120 if (*SI != OnlySucc) { 01121 OnlySucc = 0; // There are multiple distinct successors! 01122 break; 01123 } 01124 } 01125 01126 if (OnlySucc) { 01127 DEBUG(std::cerr << "Merging: " << *BB << "into: " << *OnlyPred); 01128 TerminatorInst *Term = OnlyPred->getTerminator(); 01129 01130 // Resolve any PHI nodes at the start of the block. They are all 01131 // guaranteed to have exactly one entry if they exist, unless there are 01132 // multiple duplicate (but guaranteed to be equal) entries for the 01133 // incoming edges. This occurs when there are multiple edges from 01134 // OnlyPred to OnlySucc. 01135 // 01136 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 01137 PN->replaceAllUsesWith(PN->getIncomingValue(0)); 01138 BB->getInstList().pop_front(); // Delete the phi node... 01139 } 01140 01141 // Delete the unconditional branch from the predecessor... 01142 OnlyPred->getInstList().pop_back(); 01143 01144 // Move all definitions in the successor to the predecessor... 01145 OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); 01146 01147 // Make all PHI nodes that referred to BB now refer to Pred as their 01148 // source... 01149 BB->replaceAllUsesWith(OnlyPred); 01150 01151 std::string OldName = BB->getName(); 01152 01153 // Erase basic block from the function... 01154 M->getBasicBlockList().erase(BB); 01155 01156 // Inherit predecessors name if it exists... 01157 if (!OldName.empty() && !OnlyPred->hasName()) 01158 OnlyPred->setName(OldName); 01159 01160 return true; 01161 } 01162 01163 // Otherwise, if this block only has a single predecessor, and if that block 01164 // is a conditional branch, see if we can hoist any code from this block up 01165 // into our predecessor. 01166 if (OnlyPred) 01167 if (BranchInst *BI = dyn_cast<BranchInst>(OnlyPred->getTerminator())) { 01168 // This is guaranteed to be a condbr at this point. 01169 assert(BI->isConditional() && "Should have folded bb into pred!"); 01170 // Get the other block. 01171 BasicBlock *OtherBB = BI->getSuccessor(BI->getSuccessor(0) == BB); 01172 PI = pred_begin(OtherBB); 01173 ++PI; 01174 if (PI == pred_end(OtherBB)) { 01175 // We have a conditional branch to two blocks that are only reachable 01176 // from the condbr. We know that the condbr dominates the two blocks, 01177 // so see if there is any identical code in the "then" and "else" 01178 // blocks. If so, we can hoist it up to the branching block. 01179 Changed |= HoistThenElseCodeToIf(BI); 01180 } 01181 } 01182 01183 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 01184 if (BranchInst *BI = dyn_cast<BranchInst>((*PI)->getTerminator())) 01185 // Change br (X == 0 | X == 1), T, F into a switch instruction. 01186 if (BI->isConditional() && isa<Instruction>(BI->getCondition())) { 01187 Instruction *Cond = cast<Instruction>(BI->getCondition()); 01188 // If this is a bunch of seteq's or'd together, or if it's a bunch of 01189 // 'setne's and'ed together, collect them. 01190 Value *CompVal = 0; 01191 std::vector<ConstantInt*> Values; 01192 bool TrueWhenEqual = GatherValueComparisons(Cond, CompVal, Values); 01193 if (CompVal && CompVal->getType()->isInteger()) { 01194 // There might be duplicate constants in the list, which the switch 01195 // instruction can't handle, remove them now. 01196 std::sort(Values.begin(), Values.end(), ConstantIntOrdering()); 01197 Values.erase(std::unique(Values.begin(), Values.end()), Values.end()); 01198 01199 // Figure out which block is which destination. 01200 BasicBlock *DefaultBB = BI->getSuccessor(1); 01201 BasicBlock *EdgeBB = BI->getSuccessor(0); 01202 if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB); 01203 01204 // Create the new switch instruction now. 01205 SwitchInst *New = new SwitchInst(CompVal, DefaultBB, BI); 01206 01207 // Add all of the 'cases' to the switch instruction. 01208 for (unsigned i = 0, e = Values.size(); i != e; ++i) 01209 New->addCase(Values[i], EdgeBB); 01210 01211 // We added edges from PI to the EdgeBB. As such, if there were any 01212 // PHI nodes in EdgeBB, they need entries to be added corresponding to 01213 // the number of edges added. 01214 for (BasicBlock::iterator BBI = EdgeBB->begin(); 01215 isa<PHINode>(BBI); ++BBI) { 01216 PHINode *PN = cast<PHINode>(BBI); 01217 Value *InVal = PN->getIncomingValueForBlock(*PI); 01218 for (unsigned i = 0, e = Values.size()-1; i != e; ++i) 01219 PN->addIncoming(InVal, *PI); 01220 } 01221 01222 // Erase the old branch instruction. 01223 (*PI)->getInstList().erase(BI); 01224 01225 // Erase the potentially condition tree that was used to computed the 01226 // branch condition. 01227 ErasePossiblyDeadInstructionTree(Cond); 01228 return true; 01229 } 01230 } 01231 01232 // If there is a trivial two-entry PHI node in this basic block, and we can 01233 // eliminate it, do so now. 01234 if (PHINode *PN = dyn_cast<PHINode>(BB->begin())) 01235 if (PN->getNumIncomingValues() == 2) { 01236 // Ok, this is a two entry PHI node. Check to see if this is a simple "if 01237 // statement", which has a very simple dominance structure. Basically, we 01238 // are trying to find the condition that is being branched on, which 01239 // subsequently causes this merge to happen. We really want control 01240 // dependence information for this check, but simplifycfg can't keep it up 01241 // to date, and this catches most of the cases we care about anyway. 01242 // 01243 BasicBlock *IfTrue, *IfFalse; 01244 if (Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse)) { 01245 DEBUG(std::cerr << "FOUND IF CONDITION! " << *IfCond << " T: " 01246 << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"); 01247 01248 // Loop over the PHI's seeing if we can promote them all to select 01249 // instructions. While we are at it, keep track of the instructions 01250 // that need to be moved to the dominating block. 01251 std::set<Instruction*> AggressiveInsts; 01252 bool CanPromote = true; 01253 01254 BasicBlock::iterator AfterPHIIt = BB->begin(); 01255 while (isa<PHINode>(AfterPHIIt)) { 01256 PHINode *PN = cast<PHINode>(AfterPHIIt++); 01257 if (PN->getIncomingValue(0) == PN->getIncomingValue(1)) 01258 PN->replaceAllUsesWith(PN->getIncomingValue(0)); 01259 else if (!DominatesMergePoint(PN->getIncomingValue(0), BB, 01260 &AggressiveInsts) || 01261 !DominatesMergePoint(PN->getIncomingValue(1), BB, 01262 &AggressiveInsts)) { 01263 CanPromote = false; 01264 break; 01265 } 01266 } 01267 01268 // Did we eliminate all PHI's? 01269 CanPromote |= AfterPHIIt == BB->begin(); 01270 01271 // If we all PHI nodes are promotable, check to make sure that all 01272 // instructions in the predecessor blocks can be promoted as well. If 01273 // not, we won't be able to get rid of the control flow, so it's not 01274 // worth promoting to select instructions. 01275 BasicBlock *DomBlock = 0, *IfBlock1 = 0, *IfBlock2 = 0; 01276 if (CanPromote) { 01277 PN = cast<PHINode>(BB->begin()); 01278 BasicBlock *Pred = PN->getIncomingBlock(0); 01279 if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 01280 IfBlock1 = Pred; 01281 DomBlock = *pred_begin(Pred); 01282 for (BasicBlock::iterator I = Pred->begin(); 01283 !isa<TerminatorInst>(I); ++I) 01284 if (!AggressiveInsts.count(I)) { 01285 // This is not an aggressive instruction that we can promote. 01286 // Because of this, we won't be able to get rid of the control 01287 // flow, so the xform is not worth it. 01288 CanPromote = false; 01289 break; 01290 } 01291 } 01292 01293 Pred = PN->getIncomingBlock(1); 01294 if (CanPromote && 01295 cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 01296 IfBlock2 = Pred; 01297 DomBlock = *pred_begin(Pred); 01298 for (BasicBlock::iterator I = Pred->begin(); 01299 !isa<TerminatorInst>(I); ++I) 01300 if (!AggressiveInsts.count(I)) { 01301 // This is not an aggressive instruction that we can promote. 01302 // Because of this, we won't be able to get rid of the control 01303 // flow, so the xform is not worth it. 01304 CanPromote = false; 01305 break; 01306 } 01307 } 01308 } 01309 01310 // If we can still promote the PHI nodes after this gauntlet of tests, 01311 // do all of the PHI's now. 01312 if (CanPromote) { 01313 // Move all 'aggressive' instructions, which are defined in the 01314 // conditional parts of the if's up to the dominating block. 01315 if (IfBlock1) { 01316 DomBlock->getInstList().splice(DomBlock->getTerminator(), 01317 IfBlock1->getInstList(), 01318 IfBlock1->begin(), 01319 IfBlock1->getTerminator()); 01320 } 01321 if (IfBlock2) { 01322 DomBlock->getInstList().splice(DomBlock->getTerminator(), 01323 IfBlock2->getInstList(), 01324 IfBlock2->begin(), 01325 IfBlock2->getTerminator()); 01326 } 01327 01328 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 01329 // Change the PHI node into a select instruction. 01330 Value *TrueVal = 01331 PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); 01332 Value *FalseVal = 01333 PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); 01334 01335 std::string Name = PN->getName(); PN->setName(""); 01336 PN->replaceAllUsesWith(new SelectInst(IfCond, TrueVal, FalseVal, 01337 Name, AfterPHIIt)); 01338 BB->getInstList().erase(PN); 01339 } 01340 Changed = true; 01341 } 01342 } 01343 } 01344 01345 return Changed; 01346 }