SimplifyCFG.cpp revision 4e073a871b208a2c9dfa004b3a93fb26f96daa17
1//===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// Peephole optimize the CFG. 11// 12//===----------------------------------------------------------------------===// 13 14#define DEBUG_TYPE "simplifycfg" 15#include "llvm/Transforms/Utils/Local.h" 16#include "llvm/Constants.h" 17#include "llvm/Instructions.h" 18#include "llvm/Type.h" 19#include "llvm/Support/CFG.h" 20#include "llvm/Support/Debug.h" 21#include <algorithm> 22#include <functional> 23#include <set> 24#include <map> 25using namespace llvm; 26 27// PropagatePredecessorsForPHIs - This gets "Succ" ready to have the 28// predecessors from "BB". This is a little tricky because "Succ" has PHI 29// nodes, which need to have extra slots added to them to hold the merge edges 30// from BB's predecessors, and BB itself might have had PHI nodes in it. This 31// function returns true (failure) if the Succ BB already has a predecessor that 32// is a predecessor of BB and incoming PHI arguments would not be discernible. 33// 34// Assumption: Succ is the single successor for BB. 35// 36static bool PropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 37 assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 38 39 if (!isa<PHINode>(Succ->front())) 40 return false; // We can make the transformation, no problem. 41 42 // If there is more than one predecessor, and there are PHI nodes in 43 // the successor, then we need to add incoming edges for the PHI nodes 44 // 45 const std::vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB)); 46 47 // Check to see if one of the predecessors of BB is already a predecessor of 48 // Succ. If so, we cannot do the transformation if there are any PHI nodes 49 // with incompatible values coming in from the two edges! 50 // 51 for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); PI != PE; ++PI) 52 if (std::find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end()) { 53 // Loop over all of the PHI nodes checking to see if there are 54 // incompatible values coming in. 55 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 56 PHINode *PN = cast<PHINode>(I); 57 // Loop up the entries in the PHI node for BB and for *PI if the values 58 // coming in are non-equal, we cannot merge these two blocks (instead we 59 // should insert a conditional move or something, then merge the 60 // blocks). 61 int Idx1 = PN->getBasicBlockIndex(BB); 62 int Idx2 = PN->getBasicBlockIndex(*PI); 63 assert(Idx1 != -1 && Idx2 != -1 && 64 "Didn't have entries for my predecessors??"); 65 if (PN->getIncomingValue(Idx1) != PN->getIncomingValue(Idx2)) 66 return true; // Values are not equal... 67 } 68 } 69 70 // Loop over all of the PHI nodes in the successor BB. 71 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 72 PHINode *PN = cast<PHINode>(I); 73 Value *OldVal = PN->removeIncomingValue(BB, false); 74 assert(OldVal && "No entry in PHI for Pred BB!"); 75 76 // If this incoming value is one of the PHI nodes in BB, the new entries in 77 // the PHI node are the entries from the old PHI. 78 if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 79 PHINode *OldValPN = cast<PHINode>(OldVal); 80 for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) 81 PN->addIncoming(OldValPN->getIncomingValue(i), 82 OldValPN->getIncomingBlock(i)); 83 } else { 84 for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(), 85 End = BBPreds.end(); PredI != End; ++PredI) { 86 // Add an incoming value for each of the new incoming values... 87 PN->addIncoming(OldVal, *PredI); 88 } 89 } 90 } 91 return false; 92} 93 94/// GetIfCondition - Given a basic block (BB) with two predecessors (and 95/// presumably PHI nodes in it), check to see if the merge at this block is due 96/// to an "if condition". If so, return the boolean condition that determines 97/// which entry into BB will be taken. Also, return by references the block 98/// that will be entered from if the condition is true, and the block that will 99/// be entered if the condition is false. 100/// 101/// 102static Value *GetIfCondition(BasicBlock *BB, 103 BasicBlock *&IfTrue, BasicBlock *&IfFalse) { 104 assert(std::distance(pred_begin(BB), pred_end(BB)) == 2 && 105 "Function can only handle blocks with 2 predecessors!"); 106 BasicBlock *Pred1 = *pred_begin(BB); 107 BasicBlock *Pred2 = *++pred_begin(BB); 108 109 // We can only handle branches. Other control flow will be lowered to 110 // branches if possible anyway. 111 if (!isa<BranchInst>(Pred1->getTerminator()) || 112 !isa<BranchInst>(Pred2->getTerminator())) 113 return 0; 114 BranchInst *Pred1Br = cast<BranchInst>(Pred1->getTerminator()); 115 BranchInst *Pred2Br = cast<BranchInst>(Pred2->getTerminator()); 116 117 // Eliminate code duplication by ensuring that Pred1Br is conditional if 118 // either are. 119 if (Pred2Br->isConditional()) { 120 // If both branches are conditional, we don't have an "if statement". In 121 // reality, we could transform this case, but since the condition will be 122 // required anyway, we stand no chance of eliminating it, so the xform is 123 // probably not profitable. 124 if (Pred1Br->isConditional()) 125 return 0; 126 127 std::swap(Pred1, Pred2); 128 std::swap(Pred1Br, Pred2Br); 129 } 130 131 if (Pred1Br->isConditional()) { 132 // If we found a conditional branch predecessor, make sure that it branches 133 // to BB and Pred2Br. If it doesn't, this isn't an "if statement". 134 if (Pred1Br->getSuccessor(0) == BB && 135 Pred1Br->getSuccessor(1) == Pred2) { 136 IfTrue = Pred1; 137 IfFalse = Pred2; 138 } else if (Pred1Br->getSuccessor(0) == Pred2 && 139 Pred1Br->getSuccessor(1) == BB) { 140 IfTrue = Pred2; 141 IfFalse = Pred1; 142 } else { 143 // We know that one arm of the conditional goes to BB, so the other must 144 // go somewhere unrelated, and this must not be an "if statement". 145 return 0; 146 } 147 148 // The only thing we have to watch out for here is to make sure that Pred2 149 // doesn't have incoming edges from other blocks. If it does, the condition 150 // doesn't dominate BB. 151 if (++pred_begin(Pred2) != pred_end(Pred2)) 152 return 0; 153 154 return Pred1Br->getCondition(); 155 } 156 157 // Ok, if we got here, both predecessors end with an unconditional branch to 158 // BB. Don't panic! If both blocks only have a single (identical) 159 // predecessor, and THAT is a conditional branch, then we're all ok! 160 if (pred_begin(Pred1) == pred_end(Pred1) || 161 ++pred_begin(Pred1) != pred_end(Pred1) || 162 pred_begin(Pred2) == pred_end(Pred2) || 163 ++pred_begin(Pred2) != pred_end(Pred2) || 164 *pred_begin(Pred1) != *pred_begin(Pred2)) 165 return 0; 166 167 // Otherwise, if this is a conditional branch, then we can use it! 168 BasicBlock *CommonPred = *pred_begin(Pred1); 169 if (BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator())) { 170 assert(BI->isConditional() && "Two successors but not conditional?"); 171 if (BI->getSuccessor(0) == Pred1) { 172 IfTrue = Pred1; 173 IfFalse = Pred2; 174 } else { 175 IfTrue = Pred2; 176 IfFalse = Pred1; 177 } 178 return BI->getCondition(); 179 } 180 return 0; 181} 182 183 184// If we have a merge point of an "if condition" as accepted above, return true 185// if the specified value dominates the block. We don't handle the true 186// generality of domination here, just a special case which works well enough 187// for us. 188// 189// If AggressiveInsts is non-null, and if V does not dominate BB, we check to 190// see if V (which must be an instruction) is cheap to compute and is 191// non-trapping. If both are true, the instruction is inserted into the set and 192// true is returned. 193static bool DominatesMergePoint(Value *V, BasicBlock *BB, 194 std::set<Instruction*> *AggressiveInsts) { 195 Instruction *I = dyn_cast<Instruction>(V); 196 if (!I) return true; // Non-instructions all dominate instructions. 197 BasicBlock *PBB = I->getParent(); 198 199 // We don't want to allow wierd loops that might have the "if condition" in 200 // the bottom of this block. 201 if (PBB == BB) return false; 202 203 // If this instruction is defined in a block that contains an unconditional 204 // branch to BB, then it must be in the 'conditional' part of the "if 205 // statement". 206 if (BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator())) 207 if (BI->isUnconditional() && BI->getSuccessor(0) == BB) { 208 if (!AggressiveInsts) return false; 209 // Okay, it looks like the instruction IS in the "condition". Check to 210 // see if its a cheap instruction to unconditionally compute, and if it 211 // only uses stuff defined outside of the condition. If so, hoist it out. 212 switch (I->getOpcode()) { 213 default: return false; // Cannot hoist this out safely. 214 case Instruction::Load: 215 // We can hoist loads that are non-volatile and obviously cannot trap. 216 if (cast<LoadInst>(I)->isVolatile()) 217 return false; 218 if (!isa<AllocaInst>(I->getOperand(0)) && 219 !isa<Constant>(I->getOperand(0))) 220 return false; 221 222 // Finally, we have to check to make sure there are no instructions 223 // before the load in its basic block, as we are going to hoist the loop 224 // out to its predecessor. 225 if (PBB->begin() != BasicBlock::iterator(I)) 226 return false; 227 break; 228 case Instruction::Add: 229 case Instruction::Sub: 230 case Instruction::And: 231 case Instruction::Or: 232 case Instruction::Xor: 233 case Instruction::Shl: 234 case Instruction::Shr: 235 break; // These are all cheap and non-trapping instructions. 236 } 237 238 // Okay, we can only really hoist these out if their operands are not 239 // defined in the conditional region. 240 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 241 if (!DominatesMergePoint(I->getOperand(i), BB, 0)) 242 return false; 243 // Okay, it's safe to do this! Remember this instruction. 244 AggressiveInsts->insert(I); 245 } 246 247 return true; 248} 249 250// GatherConstantSetEQs - Given a potentially 'or'd together collection of seteq 251// instructions that compare a value against a constant, return the value being 252// compared, and stick the constant into the Values vector. 253static Value *GatherConstantSetEQs(Value *V, std::vector<ConstantInt*> &Values){ 254 if (Instruction *Inst = dyn_cast<Instruction>(V)) 255 if (Inst->getOpcode() == Instruction::SetEQ) { 256 if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) { 257 Values.push_back(C); 258 return Inst->getOperand(0); 259 } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) { 260 Values.push_back(C); 261 return Inst->getOperand(1); 262 } 263 } else if (Inst->getOpcode() == Instruction::Or) { 264 if (Value *LHS = GatherConstantSetEQs(Inst->getOperand(0), Values)) 265 if (Value *RHS = GatherConstantSetEQs(Inst->getOperand(1), Values)) 266 if (LHS == RHS) 267 return LHS; 268 } 269 return 0; 270} 271 272// GatherConstantSetNEs - Given a potentially 'and'd together collection of 273// setne instructions that compare a value against a constant, return the value 274// being compared, and stick the constant into the Values vector. 275static Value *GatherConstantSetNEs(Value *V, std::vector<ConstantInt*> &Values){ 276 if (Instruction *Inst = dyn_cast<Instruction>(V)) 277 if (Inst->getOpcode() == Instruction::SetNE) { 278 if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) { 279 Values.push_back(C); 280 return Inst->getOperand(0); 281 } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) { 282 Values.push_back(C); 283 return Inst->getOperand(1); 284 } 285 } else if (Inst->getOpcode() == Instruction::Cast) { 286 // Cast of X to bool is really a comparison against zero. 287 assert(Inst->getType() == Type::BoolTy && "Can only handle bool values!"); 288 Values.push_back(ConstantInt::get(Inst->getOperand(0)->getType(), 0)); 289 return Inst->getOperand(0); 290 } else if (Inst->getOpcode() == Instruction::And) { 291 if (Value *LHS = GatherConstantSetNEs(Inst->getOperand(0), Values)) 292 if (Value *RHS = GatherConstantSetNEs(Inst->getOperand(1), Values)) 293 if (LHS == RHS) 294 return LHS; 295 } 296 return 0; 297} 298 299 300 301/// GatherValueComparisons - If the specified Cond is an 'and' or 'or' of a 302/// bunch of comparisons of one value against constants, return the value and 303/// the constants being compared. 304static bool GatherValueComparisons(Instruction *Cond, Value *&CompVal, 305 std::vector<ConstantInt*> &Values) { 306 if (Cond->getOpcode() == Instruction::Or) { 307 CompVal = GatherConstantSetEQs(Cond, Values); 308 309 // Return true to indicate that the condition is true if the CompVal is 310 // equal to one of the constants. 311 return true; 312 } else if (Cond->getOpcode() == Instruction::And) { 313 CompVal = GatherConstantSetNEs(Cond, Values); 314 315 // Return false to indicate that the condition is false if the CompVal is 316 // equal to one of the constants. 317 return false; 318 } 319 return false; 320} 321 322/// ErasePossiblyDeadInstructionTree - If the specified instruction is dead and 323/// has no side effects, nuke it. If it uses any instructions that become dead 324/// because the instruction is now gone, nuke them too. 325static void ErasePossiblyDeadInstructionTree(Instruction *I) { 326 if (isInstructionTriviallyDead(I)) { 327 std::vector<Value*> Operands(I->op_begin(), I->op_end()); 328 I->getParent()->getInstList().erase(I); 329 for (unsigned i = 0, e = Operands.size(); i != e; ++i) 330 if (Instruction *OpI = dyn_cast<Instruction>(Operands[i])) 331 ErasePossiblyDeadInstructionTree(OpI); 332 } 333} 334 335/// SafeToMergeTerminators - Return true if it is safe to merge these two 336/// terminator instructions together. 337/// 338static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) { 339 if (SI1 == SI2) return false; // Can't merge with self! 340 341 // It is not safe to merge these two switch instructions if they have a common 342 // successor, and if that successor has a PHI node, and if *that* PHI node has 343 // conflicting incoming values from the two switch blocks. 344 BasicBlock *SI1BB = SI1->getParent(); 345 BasicBlock *SI2BB = SI2->getParent(); 346 std::set<BasicBlock*> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 347 348 for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) 349 if (SI1Succs.count(*I)) 350 for (BasicBlock::iterator BBI = (*I)->begin(); 351 isa<PHINode>(BBI); ++BBI) { 352 PHINode *PN = cast<PHINode>(BBI); 353 if (PN->getIncomingValueForBlock(SI1BB) != 354 PN->getIncomingValueForBlock(SI2BB)) 355 return false; 356 } 357 358 return true; 359} 360 361/// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will 362/// now be entries in it from the 'NewPred' block. The values that will be 363/// flowing into the PHI nodes will be the same as those coming in from 364/// ExistPred, an existing predecessor of Succ. 365static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, 366 BasicBlock *ExistPred) { 367 assert(std::find(succ_begin(ExistPred), succ_end(ExistPred), Succ) != 368 succ_end(ExistPred) && "ExistPred is not a predecessor of Succ!"); 369 if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do 370 371 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 372 PHINode *PN = cast<PHINode>(I); 373 Value *V = PN->getIncomingValueForBlock(ExistPred); 374 PN->addIncoming(V, NewPred); 375 } 376} 377 378// isValueEqualityComparison - Return true if the specified terminator checks to 379// see if a value is equal to constant integer value. 380static Value *isValueEqualityComparison(TerminatorInst *TI) { 381 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 382 // Do not permit merging of large switch instructions into their 383 // predecessors unless there is only one predecessor. 384 if (SI->getNumSuccessors() * std::distance(pred_begin(SI->getParent()), 385 pred_end(SI->getParent())) > 128) 386 return 0; 387 388 return SI->getCondition(); 389 } 390 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 391 if (BI->isConditional() && BI->getCondition()->hasOneUse()) 392 if (SetCondInst *SCI = dyn_cast<SetCondInst>(BI->getCondition())) 393 if ((SCI->getOpcode() == Instruction::SetEQ || 394 SCI->getOpcode() == Instruction::SetNE) && 395 isa<ConstantInt>(SCI->getOperand(1))) 396 return SCI->getOperand(0); 397 return 0; 398} 399 400// Given a value comparison instruction, decode all of the 'cases' that it 401// represents and return the 'default' block. 402static BasicBlock * 403GetValueEqualityComparisonCases(TerminatorInst *TI, 404 std::vector<std::pair<ConstantInt*, 405 BasicBlock*> > &Cases) { 406 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 407 Cases.reserve(SI->getNumCases()); 408 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 409 Cases.push_back(std::make_pair(cast<ConstantInt>(SI->getCaseValue(i)), 410 SI->getSuccessor(i))); 411 return SI->getDefaultDest(); 412 } 413 414 BranchInst *BI = cast<BranchInst>(TI); 415 SetCondInst *SCI = cast<SetCondInst>(BI->getCondition()); 416 Cases.push_back(std::make_pair(cast<ConstantInt>(SCI->getOperand(1)), 417 BI->getSuccessor(SCI->getOpcode() == 418 Instruction::SetNE))); 419 return BI->getSuccessor(SCI->getOpcode() == Instruction::SetEQ); 420} 421 422 423// FoldValueComparisonIntoPredecessors - The specified terminator is a value 424// equality comparison instruction (either a switch or a branch on "X == c"). 425// See if any of the predecessors of the terminator block are value comparisons 426// on the same value. If so, and if safe to do so, fold them together. 427static bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { 428 BasicBlock *BB = TI->getParent(); 429 Value *CV = isValueEqualityComparison(TI); // CondVal 430 assert(CV && "Not a comparison?"); 431 bool Changed = false; 432 433 std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 434 while (!Preds.empty()) { 435 BasicBlock *Pred = Preds.back(); 436 Preds.pop_back(); 437 438 // See if the predecessor is a comparison with the same value. 439 TerminatorInst *PTI = Pred->getTerminator(); 440 Value *PCV = isValueEqualityComparison(PTI); // PredCondVal 441 442 if (PCV == CV && SafeToMergeTerminators(TI, PTI)) { 443 // Figure out which 'cases' to copy from SI to PSI. 444 std::vector<std::pair<ConstantInt*, BasicBlock*> > BBCases; 445 BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases); 446 447 std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 448 BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases); 449 450 // Based on whether the default edge from PTI goes to BB or not, fill in 451 // PredCases and PredDefault with the new switch cases we would like to 452 // build. 453 std::vector<BasicBlock*> NewSuccessors; 454 455 if (PredDefault == BB) { 456 // If this is the default destination from PTI, only the edges in TI 457 // that don't occur in PTI, or that branch to BB will be activated. 458 std::set<ConstantInt*> PTIHandled; 459 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 460 if (PredCases[i].second != BB) 461 PTIHandled.insert(PredCases[i].first); 462 else { 463 // The default destination is BB, we don't need explicit targets. 464 std::swap(PredCases[i], PredCases.back()); 465 PredCases.pop_back(); 466 --i; --e; 467 } 468 469 // Reconstruct the new switch statement we will be building. 470 if (PredDefault != BBDefault) { 471 PredDefault->removePredecessor(Pred); 472 PredDefault = BBDefault; 473 NewSuccessors.push_back(BBDefault); 474 } 475 for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 476 if (!PTIHandled.count(BBCases[i].first) && 477 BBCases[i].second != BBDefault) { 478 PredCases.push_back(BBCases[i]); 479 NewSuccessors.push_back(BBCases[i].second); 480 } 481 482 } else { 483 // If this is not the default destination from PSI, only the edges 484 // in SI that occur in PSI with a destination of BB will be 485 // activated. 486 std::set<ConstantInt*> PTIHandled; 487 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 488 if (PredCases[i].second == BB) { 489 PTIHandled.insert(PredCases[i].first); 490 std::swap(PredCases[i], PredCases.back()); 491 PredCases.pop_back(); 492 --i; --e; 493 } 494 495 // Okay, now we know which constants were sent to BB from the 496 // predecessor. Figure out where they will all go now. 497 for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 498 if (PTIHandled.count(BBCases[i].first)) { 499 // If this is one we are capable of getting... 500 PredCases.push_back(BBCases[i]); 501 NewSuccessors.push_back(BBCases[i].second); 502 PTIHandled.erase(BBCases[i].first);// This constant is taken care of 503 } 504 505 // If there are any constants vectored to BB that TI doesn't handle, 506 // they must go to the default destination of TI. 507 for (std::set<ConstantInt*>::iterator I = PTIHandled.begin(), 508 E = PTIHandled.end(); I != E; ++I) { 509 PredCases.push_back(std::make_pair(*I, BBDefault)); 510 NewSuccessors.push_back(BBDefault); 511 } 512 } 513 514 // Okay, at this point, we know which new successor Pred will get. Make 515 // sure we update the number of entries in the PHI nodes for these 516 // successors. 517 for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i) 518 AddPredecessorToBlock(NewSuccessors[i], Pred, BB); 519 520 // Now that the successors are updated, create the new Switch instruction. 521 SwitchInst *NewSI = new SwitchInst(CV, PredDefault, PTI); 522 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 523 NewSI->addCase(PredCases[i].first, PredCases[i].second); 524 Pred->getInstList().erase(PTI); 525 526 // Okay, last check. If BB is still a successor of PSI, then we must 527 // have an infinite loop case. If so, add an infinitely looping block 528 // to handle the case to preserve the behavior of the code. 529 BasicBlock *InfLoopBlock = 0; 530 for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i) 531 if (NewSI->getSuccessor(i) == BB) { 532 if (InfLoopBlock == 0) { 533 // Insert it at the end of the loop, because it's either code, 534 // or it won't matter if it's hot. :) 535 InfLoopBlock = new BasicBlock("infloop", BB->getParent()); 536 new BranchInst(InfLoopBlock, InfLoopBlock); 537 } 538 NewSI->setSuccessor(i, InfLoopBlock); 539 } 540 541 Changed = true; 542 } 543 } 544 return Changed; 545} 546 547namespace { 548 /// ConstantIntOrdering - This class implements a stable ordering of constant 549 /// integers that does not depend on their address. This is important for 550 /// applications that sort ConstantInt's to ensure uniqueness. 551 struct ConstantIntOrdering { 552 bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { 553 return LHS->getRawValue() < RHS->getRawValue(); 554 } 555 }; 556} 557 558 559// SimplifyCFG - This function is used to do simplification of a CFG. For 560// example, it adjusts branches to branches to eliminate the extra hop, it 561// eliminates unreachable basic blocks, and does other "peephole" optimization 562// of the CFG. It returns true if a modification was made. 563// 564// WARNING: The entry node of a function may not be simplified. 565// 566bool llvm::SimplifyCFG(BasicBlock *BB) { 567 bool Changed = false; 568 Function *M = BB->getParent(); 569 570 assert(BB && BB->getParent() && "Block not embedded in function!"); 571 assert(BB->getTerminator() && "Degenerate basic block encountered!"); 572 assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!"); 573 574 // Remove basic blocks that have no predecessors... which are unreachable. 575 if (pred_begin(BB) == pred_end(BB) || 576 *pred_begin(BB) == BB && ++pred_begin(BB) == pred_end(BB)) { 577 DEBUG(std::cerr << "Removing BB: \n" << *BB); 578 579 // Loop through all of our successors and make sure they know that one 580 // of their predecessors is going away. 581 for_each(succ_begin(BB), succ_end(BB), 582 std::bind2nd(std::mem_fun(&BasicBlock::removePredecessor), BB)); 583 584 while (!BB->empty()) { 585 Instruction &I = BB->back(); 586 // If this instruction is used, replace uses with an arbitrary 587 // constant value. Because control flow can't get here, we don't care 588 // what we replace the value with. Note that since this block is 589 // unreachable, and all values contained within it must dominate their 590 // uses, that all uses will eventually be removed. 591 if (!I.use_empty()) 592 // Make all users of this instruction reference the constant instead 593 I.replaceAllUsesWith(Constant::getNullValue(I.getType())); 594 595 // Remove the instruction from the basic block 596 BB->getInstList().pop_back(); 597 } 598 M->getBasicBlockList().erase(BB); 599 return true; 600 } 601 602 // Check to see if we can constant propagate this terminator instruction 603 // away... 604 Changed |= ConstantFoldTerminator(BB); 605 606 // Check to see if this block has no non-phi instructions and only a single 607 // successor. If so, replace references to this basic block with references 608 // to the successor. 609 succ_iterator SI(succ_begin(BB)); 610 if (SI != succ_end(BB) && ++SI == succ_end(BB)) { // One succ? 611 612 BasicBlock::iterator BBI = BB->begin(); // Skip over phi nodes... 613 while (isa<PHINode>(*BBI)) ++BBI; 614 615 if (BBI->isTerminator()) { // Terminator is the only non-phi instruction! 616 BasicBlock *Succ = *succ_begin(BB); // There is exactly one successor 617 618 if (Succ != BB) { // Arg, don't hurt infinite loops! 619 // If our successor has PHI nodes, then we need to update them to 620 // include entries for BB's predecessors, not for BB itself. 621 // Be careful though, if this transformation fails (returns true) then 622 // we cannot do this transformation! 623 // 624 if (!PropagatePredecessorsForPHIs(BB, Succ)) { 625 DEBUG(std::cerr << "Killing Trivial BB: \n" << *BB); 626 std::string OldName = BB->getName(); 627 628 std::vector<BasicBlock*> 629 OldSuccPreds(pred_begin(Succ), pred_end(Succ)); 630 631 // Move all PHI nodes in BB to Succ if they are alive, otherwise 632 // delete them. 633 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) 634 if (PN->use_empty()) 635 BB->getInstList().erase(BB->begin()); // Nuke instruction... 636 else { 637 // The instruction is alive, so this means that Succ must have 638 // *ONLY* had BB as a predecessor, and the PHI node is still valid 639 // now. Simply move it into Succ, because we know that BB 640 // strictly dominated Succ. 641 BB->getInstList().remove(BB->begin()); 642 Succ->getInstList().push_front(PN); 643 644 // We need to add new entries for the PHI node to account for 645 // predecessors of Succ that the PHI node does not take into 646 // account. At this point, since we know that BB dominated succ, 647 // this means that we should any newly added incoming edges should 648 // use the PHI node as the value for these edges, because they are 649 // loop back edges. 650 for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i) 651 if (OldSuccPreds[i] != BB) 652 PN->addIncoming(PN, OldSuccPreds[i]); 653 } 654 655 // Everything that jumped to BB now goes to Succ... 656 BB->replaceAllUsesWith(Succ); 657 658 // Delete the old basic block... 659 M->getBasicBlockList().erase(BB); 660 661 if (!OldName.empty() && !Succ->hasName()) // Transfer name if we can 662 Succ->setName(OldName); 663 return true; 664 } 665 } 666 } 667 } 668 669 // If this is a returning block with only PHI nodes in it, fold the return 670 // instruction into any unconditional branch predecessors. 671 // 672 // If any predecessor is a conditional branch that just selects among 673 // different return values, fold the replace the branch/return with a select 674 // and return. 675 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 676 BasicBlock::iterator BBI = BB->getTerminator(); 677 if (BBI == BB->begin() || isa<PHINode>(--BBI)) { 678 // Find predecessors that end with branches. 679 std::vector<BasicBlock*> UncondBranchPreds; 680 std::vector<BranchInst*> CondBranchPreds; 681 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 682 TerminatorInst *PTI = (*PI)->getTerminator(); 683 if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) 684 if (BI->isUnconditional()) 685 UncondBranchPreds.push_back(*PI); 686 else 687 CondBranchPreds.push_back(BI); 688 } 689 690 // If we found some, do the transformation! 691 if (!UncondBranchPreds.empty()) { 692 while (!UncondBranchPreds.empty()) { 693 BasicBlock *Pred = UncondBranchPreds.back(); 694 UncondBranchPreds.pop_back(); 695 Instruction *UncondBranch = Pred->getTerminator(); 696 // Clone the return and add it to the end of the predecessor. 697 Instruction *NewRet = RI->clone(); 698 Pred->getInstList().push_back(NewRet); 699 700 // If the return instruction returns a value, and if the value was a 701 // PHI node in "BB", propagate the right value into the return. 702 if (NewRet->getNumOperands() == 1) 703 if (PHINode *PN = dyn_cast<PHINode>(NewRet->getOperand(0))) 704 if (PN->getParent() == BB) 705 NewRet->setOperand(0, PN->getIncomingValueForBlock(Pred)); 706 // Update any PHI nodes in the returning block to realize that we no 707 // longer branch to them. 708 BB->removePredecessor(Pred); 709 Pred->getInstList().erase(UncondBranch); 710 } 711 712 // If we eliminated all predecessors of the block, delete the block now. 713 if (pred_begin(BB) == pred_end(BB)) 714 // We know there are no successors, so just nuke the block. 715 M->getBasicBlockList().erase(BB); 716 717 return true; 718 } 719 720 // Check out all of the conditional branches going to this return 721 // instruction. If any of them just select between returns, change the 722 // branch itself into a select/return pair. 723 while (!CondBranchPreds.empty()) { 724 BranchInst *BI = CondBranchPreds.back(); 725 CondBranchPreds.pop_back(); 726 BasicBlock *TrueSucc = BI->getSuccessor(0); 727 BasicBlock *FalseSucc = BI->getSuccessor(1); 728 BasicBlock *OtherSucc = TrueSucc == BB ? FalseSucc : TrueSucc; 729 730 // Check to see if the non-BB successor is also a return block. 731 if (isa<ReturnInst>(OtherSucc->getTerminator())) { 732 // Check to see if there are only PHI instructions in this block. 733 BasicBlock::iterator OSI = OtherSucc->getTerminator(); 734 if (OSI == OtherSucc->begin() || isa<PHINode>(--OSI)) { 735 // Okay, we found a branch that is going to two return nodes. If 736 // there is no return value for this function, just change the 737 // branch into a return. 738 if (RI->getNumOperands() == 0) { 739 TrueSucc->removePredecessor(BI->getParent()); 740 FalseSucc->removePredecessor(BI->getParent()); 741 new ReturnInst(0, BI); 742 BI->getParent()->getInstList().erase(BI); 743 return true; 744 } 745 746 // Otherwise, figure out what the true and false return values are 747 // so we can insert a new select instruction. 748 Value *TrueValue = TrueSucc->getTerminator()->getOperand(0); 749 Value *FalseValue = FalseSucc->getTerminator()->getOperand(0); 750 751 // Unwrap any PHI nodes in the return blocks. 752 if (PHINode *TVPN = dyn_cast<PHINode>(TrueValue)) 753 if (TVPN->getParent() == TrueSucc) 754 TrueValue = TVPN->getIncomingValueForBlock(BI->getParent()); 755 if (PHINode *FVPN = dyn_cast<PHINode>(FalseValue)) 756 if (FVPN->getParent() == FalseSucc) 757 FalseValue = FVPN->getIncomingValueForBlock(BI->getParent()); 758 759 TrueSucc->removePredecessor(BI->getParent()); 760 FalseSucc->removePredecessor(BI->getParent()); 761 762 // Insert a new select instruction. 763 Value *NewRetVal; 764 Value *BrCond = BI->getCondition(); 765 if (TrueValue != FalseValue) 766 NewRetVal = new SelectInst(BrCond, TrueValue, 767 FalseValue, "retval", BI); 768 else 769 NewRetVal = TrueValue; 770 771 new ReturnInst(NewRetVal, BI); 772 BI->getParent()->getInstList().erase(BI); 773 if (BrCond->use_empty()) 774 if (Instruction *BrCondI = dyn_cast<Instruction>(BrCond)) 775 BrCondI->getParent()->getInstList().erase(BrCondI); 776 return true; 777 } 778 } 779 } 780 } 781 } else if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->begin())) { 782 // Check to see if the first instruction in this block is just an unwind. 783 // If so, replace any invoke instructions which use this as an exception 784 // destination with call instructions, and any unconditional branch 785 // predecessor with an unwind. 786 // 787 std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 788 while (!Preds.empty()) { 789 BasicBlock *Pred = Preds.back(); 790 if (BranchInst *BI = dyn_cast<BranchInst>(Pred->getTerminator())) { 791 if (BI->isUnconditional()) { 792 Pred->getInstList().pop_back(); // nuke uncond branch 793 new UnwindInst(Pred); // Use unwind. 794 Changed = true; 795 } 796 } else if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator())) 797 if (II->getUnwindDest() == BB) { 798 // Insert a new branch instruction before the invoke, because this 799 // is now a fall through... 800 BranchInst *BI = new BranchInst(II->getNormalDest(), II); 801 Pred->getInstList().remove(II); // Take out of symbol table 802 803 // Insert the call now... 804 std::vector<Value*> Args(II->op_begin()+3, II->op_end()); 805 CallInst *CI = new CallInst(II->getCalledValue(), Args, 806 II->getName(), BI); 807 // If the invoke produced a value, the Call now does instead 808 II->replaceAllUsesWith(CI); 809 delete II; 810 Changed = true; 811 } 812 813 Preds.pop_back(); 814 } 815 816 // If this block is now dead, remove it. 817 if (pred_begin(BB) == pred_end(BB)) { 818 // We know there are no successors, so just nuke the block. 819 M->getBasicBlockList().erase(BB); 820 return true; 821 } 822 823 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->begin())) { 824 if (isValueEqualityComparison(SI)) 825 if (FoldValueComparisonIntoPredecessors(SI)) 826 return SimplifyCFG(BB) || 1; 827 } else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 828 if (BI->isConditional()) { 829 if (Value *CompVal = isValueEqualityComparison(BI)) { 830 // This block must be empty, except for the setcond inst, if it exists. 831 BasicBlock::iterator I = BB->begin(); 832 if (&*I == BI || 833 (&*I == cast<Instruction>(BI->getCondition()) && 834 &*++I == BI)) 835 if (FoldValueComparisonIntoPredecessors(BI)) 836 return SimplifyCFG(BB) | true; 837 } 838 839 // If this basic block is ONLY a setcc and a branch, and if a predecessor 840 // branches to us and one of our successors, fold the setcc into the 841 // predecessor and use logical operations to pick the right destination. 842 BasicBlock *TrueDest = BI->getSuccessor(0); 843 BasicBlock *FalseDest = BI->getSuccessor(1); 844 if (BinaryOperator *Cond = dyn_cast<BinaryOperator>(BI->getCondition())) 845 if (Cond->getParent() == BB && &BB->front() == Cond && 846 Cond->getNext() == BI && Cond->hasOneUse() && 847 TrueDest != BB && FalseDest != BB) 848 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI!=E; ++PI) 849 if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 850 if (PBI->isConditional() && SafeToMergeTerminators(BI, PBI)) { 851 BasicBlock *PredBlock = *PI; 852 if (PBI->getSuccessor(0) == FalseDest || 853 PBI->getSuccessor(1) == TrueDest) { 854 // Invert the predecessors condition test (xor it with true), 855 // which allows us to write this code once. 856 Value *NewCond = 857 BinaryOperator::createNot(PBI->getCondition(), 858 PBI->getCondition()->getName()+".not", PBI); 859 PBI->setCondition(NewCond); 860 BasicBlock *OldTrue = PBI->getSuccessor(0); 861 BasicBlock *OldFalse = PBI->getSuccessor(1); 862 PBI->setSuccessor(0, OldFalse); 863 PBI->setSuccessor(1, OldTrue); 864 } 865 866 if (PBI->getSuccessor(0) == TrueDest || 867 PBI->getSuccessor(1) == FalseDest) { 868 // Clone Cond into the predecessor basic block, and or/and the 869 // two conditions together. 870 Instruction *New = Cond->clone(); 871 New->setName(Cond->getName()); 872 Cond->setName(Cond->getName()+".old"); 873 PredBlock->getInstList().insert(PBI, New); 874 Instruction::BinaryOps Opcode = 875 PBI->getSuccessor(0) == TrueDest ? 876 Instruction::Or : Instruction::And; 877 Value *NewCond = 878 BinaryOperator::create(Opcode, PBI->getCondition(), 879 New, "bothcond", PBI); 880 PBI->setCondition(NewCond); 881 if (PBI->getSuccessor(0) == BB) { 882 AddPredecessorToBlock(TrueDest, PredBlock, BB); 883 PBI->setSuccessor(0, TrueDest); 884 } 885 if (PBI->getSuccessor(1) == BB) { 886 AddPredecessorToBlock(FalseDest, PredBlock, BB); 887 PBI->setSuccessor(1, FalseDest); 888 } 889 return SimplifyCFG(BB) | 1; 890 } 891 } 892 893 // If this block ends with a branch instruction, and if there is one 894 // predecessor, see if the previous block ended with a branch on the same 895 // condition, which makes this conditional branch redundant. 896 pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 897 BasicBlock *OnlyPred = *PI++; 898 for (; PI != PE; ++PI)// Search all predecessors, see if they are all same 899 if (*PI != OnlyPred) { 900 OnlyPred = 0; // There are multiple different predecessors... 901 break; 902 } 903 904 if (OnlyPred) 905 if (BranchInst *PBI = dyn_cast<BranchInst>(OnlyPred->getTerminator())) 906 if (PBI->isConditional() && 907 PBI->getCondition() == BI->getCondition() && 908 (PBI->getSuccessor(0) != BB || PBI->getSuccessor(1) != BB)) { 909 // Okay, the outcome of this conditional branch is statically 910 // knowable. Delete the outgoing CFG edge that is impossible to 911 // execute. 912 bool CondIsTrue = PBI->getSuccessor(0) == BB; 913 BI->getSuccessor(CondIsTrue)->removePredecessor(BB); 914 new BranchInst(BI->getSuccessor(!CondIsTrue), BB); 915 BB->getInstList().erase(BI); 916 return SimplifyCFG(BB) | true; 917 } 918 } 919 } else if (isa<UnreachableInst>(BB->getTerminator())) { 920 // If there are any instructions immediately before the unreachable that can 921 // be removed, do so. 922 Instruction *Unreachable = BB->getTerminator(); 923 while (Unreachable != BB->begin()) { 924 BasicBlock::iterator BBI = Unreachable; 925 --BBI; 926 if (isa<CallInst>(BBI)) break; 927 // Delete this instruction 928 BB->getInstList().erase(BBI); 929 Changed = true; 930 } 931 932 // If the unreachable instruction is the first in the block, take a gander 933 // at all of the predecessors of this instruction, and simplify them. 934 if (&BB->front() == Unreachable) { 935 std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 936 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 937 TerminatorInst *TI = Preds[i]->getTerminator(); 938 939 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 940 if (BI->isUnconditional()) { 941 if (BI->getSuccessor(0) == BB) { 942 new UnreachableInst(TI); 943 TI->eraseFromParent(); 944 Changed = true; 945 } 946 } else { 947 if (BI->getSuccessor(0) == BB) { 948 new BranchInst(BI->getSuccessor(1), BI); 949 BI->eraseFromParent(); 950 } else if (BI->getSuccessor(1) == BB) { 951 new BranchInst(BI->getSuccessor(0), BI); 952 BI->eraseFromParent(); 953 Changed = true; 954 } 955 } 956 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 957 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 958 if (SI->getSuccessor(i) == BB) { 959 SI->removeCase(i); 960 --i; --e; 961 Changed = true; 962 } 963 // If the default value is unreachable, figure out the most popular 964 // destination and make it the default. 965 if (SI->getSuccessor(0) == BB) { 966 std::map<BasicBlock*, unsigned> Popularity; 967 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 968 Popularity[SI->getSuccessor(i)]++; 969 970 // Find the most popular block. 971 unsigned MaxPop = 0; 972 BasicBlock *MaxBlock = 0; 973 for (std::map<BasicBlock*, unsigned>::iterator 974 I = Popularity.begin(), E = Popularity.end(); I != E; ++I) { 975 if (I->second > MaxPop) { 976 MaxPop = I->second; 977 MaxBlock = I->first; 978 } 979 } 980 if (MaxBlock) { 981 // Make this the new default, allowing us to delete any explicit 982 // edges to it. 983 SI->setSuccessor(0, MaxBlock); 984 Changed = true; 985 986 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 987 if (SI->getSuccessor(i) == MaxBlock) { 988 SI->removeCase(i); 989 --i; --e; 990 } 991 } 992 } 993 } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) { 994 if (II->getUnwindDest() == BB) { 995 // Convert the invoke to a call instruction. This would be a good 996 // place to note that the call does not throw though. 997 BranchInst *BI = new BranchInst(II->getNormalDest(), II); 998 II->removeFromParent(); // Take out of symbol table 999 1000 // Insert the call now... 1001 std::vector<Value*> Args(II->op_begin()+3, II->op_end()); 1002 CallInst *CI = new CallInst(II->getCalledValue(), Args, 1003 II->getName(), BI); 1004 // If the invoke produced a value, the Call does now instead. 1005 II->replaceAllUsesWith(CI); 1006 delete II; 1007 Changed = true; 1008 } 1009 } 1010 } 1011 1012 // If this block is now dead, remove it. 1013 if (pred_begin(BB) == pred_end(BB)) { 1014 // We know there are no successors, so just nuke the block. 1015 M->getBasicBlockList().erase(BB); 1016 return true; 1017 } 1018 } 1019 } 1020 1021 // Merge basic blocks into their predecessor if there is only one distinct 1022 // pred, and if there is only one distinct successor of the predecessor, and 1023 // if there are no PHI nodes. 1024 // 1025 pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 1026 BasicBlock *OnlyPred = *PI++; 1027 for (; PI != PE; ++PI) // Search all predecessors, see if they are all same 1028 if (*PI != OnlyPred) { 1029 OnlyPred = 0; // There are multiple different predecessors... 1030 break; 1031 } 1032 1033 BasicBlock *OnlySucc = 0; 1034 if (OnlyPred && OnlyPred != BB && // Don't break self loops 1035 OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) { 1036 // Check to see if there is only one distinct successor... 1037 succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred)); 1038 OnlySucc = BB; 1039 for (; SI != SE; ++SI) 1040 if (*SI != OnlySucc) { 1041 OnlySucc = 0; // There are multiple distinct successors! 1042 break; 1043 } 1044 } 1045 1046 if (OnlySucc) { 1047 DEBUG(std::cerr << "Merging: " << *BB << "into: " << *OnlyPred); 1048 TerminatorInst *Term = OnlyPred->getTerminator(); 1049 1050 // Resolve any PHI nodes at the start of the block. They are all 1051 // guaranteed to have exactly one entry if they exist, unless there are 1052 // multiple duplicate (but guaranteed to be equal) entries for the 1053 // incoming edges. This occurs when there are multiple edges from 1054 // OnlyPred to OnlySucc. 1055 // 1056 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 1057 PN->replaceAllUsesWith(PN->getIncomingValue(0)); 1058 BB->getInstList().pop_front(); // Delete the phi node... 1059 } 1060 1061 // Delete the unconditional branch from the predecessor... 1062 OnlyPred->getInstList().pop_back(); 1063 1064 // Move all definitions in the successor to the predecessor... 1065 OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); 1066 1067 // Make all PHI nodes that referred to BB now refer to Pred as their 1068 // source... 1069 BB->replaceAllUsesWith(OnlyPred); 1070 1071 std::string OldName = BB->getName(); 1072 1073 // Erase basic block from the function... 1074 M->getBasicBlockList().erase(BB); 1075 1076 // Inherit predecessors name if it exists... 1077 if (!OldName.empty() && !OnlyPred->hasName()) 1078 OnlyPred->setName(OldName); 1079 1080 return true; 1081 } 1082 1083 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 1084 if (BranchInst *BI = dyn_cast<BranchInst>((*PI)->getTerminator())) 1085 // Change br (X == 0 | X == 1), T, F into a switch instruction. 1086 if (BI->isConditional() && isa<Instruction>(BI->getCondition())) { 1087 Instruction *Cond = cast<Instruction>(BI->getCondition()); 1088 // If this is a bunch of seteq's or'd together, or if it's a bunch of 1089 // 'setne's and'ed together, collect them. 1090 Value *CompVal = 0; 1091 std::vector<ConstantInt*> Values; 1092 bool TrueWhenEqual = GatherValueComparisons(Cond, CompVal, Values); 1093 if (CompVal && CompVal->getType()->isInteger()) { 1094 // There might be duplicate constants in the list, which the switch 1095 // instruction can't handle, remove them now. 1096 std::sort(Values.begin(), Values.end(), ConstantIntOrdering()); 1097 Values.erase(std::unique(Values.begin(), Values.end()), Values.end()); 1098 1099 // Figure out which block is which destination. 1100 BasicBlock *DefaultBB = BI->getSuccessor(1); 1101 BasicBlock *EdgeBB = BI->getSuccessor(0); 1102 if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB); 1103 1104 // Create the new switch instruction now. 1105 SwitchInst *New = new SwitchInst(CompVal, DefaultBB, BI); 1106 1107 // Add all of the 'cases' to the switch instruction. 1108 for (unsigned i = 0, e = Values.size(); i != e; ++i) 1109 New->addCase(Values[i], EdgeBB); 1110 1111 // We added edges from PI to the EdgeBB. As such, if there were any 1112 // PHI nodes in EdgeBB, they need entries to be added corresponding to 1113 // the number of edges added. 1114 for (BasicBlock::iterator BBI = EdgeBB->begin(); 1115 isa<PHINode>(BBI); ++BBI) { 1116 PHINode *PN = cast<PHINode>(BBI); 1117 Value *InVal = PN->getIncomingValueForBlock(*PI); 1118 for (unsigned i = 0, e = Values.size()-1; i != e; ++i) 1119 PN->addIncoming(InVal, *PI); 1120 } 1121 1122 // Erase the old branch instruction. 1123 (*PI)->getInstList().erase(BI); 1124 1125 // Erase the potentially condition tree that was used to computed the 1126 // branch condition. 1127 ErasePossiblyDeadInstructionTree(Cond); 1128 return true; 1129 } 1130 } 1131 1132 // If there is a trivial two-entry PHI node in this basic block, and we can 1133 // eliminate it, do so now. 1134 if (PHINode *PN = dyn_cast<PHINode>(BB->begin())) 1135 if (PN->getNumIncomingValues() == 2) { 1136 // Ok, this is a two entry PHI node. Check to see if this is a simple "if 1137 // statement", which has a very simple dominance structure. Basically, we 1138 // are trying to find the condition that is being branched on, which 1139 // subsequently causes this merge to happen. We really want control 1140 // dependence information for this check, but simplifycfg can't keep it up 1141 // to date, and this catches most of the cases we care about anyway. 1142 // 1143 BasicBlock *IfTrue, *IfFalse; 1144 if (Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse)) { 1145 DEBUG(std::cerr << "FOUND IF CONDITION! " << *IfCond << " T: " 1146 << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"); 1147 1148 // Loop over the PHI's seeing if we can promote them all to select 1149 // instructions. While we are at it, keep track of the instructions 1150 // that need to be moved to the dominating block. 1151 std::set<Instruction*> AggressiveInsts; 1152 bool CanPromote = true; 1153 1154 BasicBlock::iterator AfterPHIIt = BB->begin(); 1155 while (isa<PHINode>(AfterPHIIt)) { 1156 PHINode *PN = cast<PHINode>(AfterPHIIt++); 1157 if (PN->getIncomingValue(0) == PN->getIncomingValue(1)) 1158 PN->replaceAllUsesWith(PN->getIncomingValue(0)); 1159 else if (!DominatesMergePoint(PN->getIncomingValue(0), BB, 1160 &AggressiveInsts) || 1161 !DominatesMergePoint(PN->getIncomingValue(1), BB, 1162 &AggressiveInsts)) { 1163 CanPromote = false; 1164 break; 1165 } 1166 } 1167 1168 // Did we eliminate all PHI's? 1169 CanPromote |= AfterPHIIt == BB->begin(); 1170 1171 // If we all PHI nodes are promotable, check to make sure that all 1172 // instructions in the predecessor blocks can be promoted as well. If 1173 // not, we won't be able to get rid of the control flow, so it's not 1174 // worth promoting to select instructions. 1175 BasicBlock *DomBlock = 0, *IfBlock1 = 0, *IfBlock2 = 0; 1176 if (CanPromote) { 1177 PN = cast<PHINode>(BB->begin()); 1178 BasicBlock *Pred = PN->getIncomingBlock(0); 1179 if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 1180 IfBlock1 = Pred; 1181 DomBlock = *pred_begin(Pred); 1182 for (BasicBlock::iterator I = Pred->begin(); 1183 !isa<TerminatorInst>(I); ++I) 1184 if (!AggressiveInsts.count(I)) { 1185 // This is not an aggressive instruction that we can promote. 1186 // Because of this, we won't be able to get rid of the control 1187 // flow, so the xform is not worth it. 1188 CanPromote = false; 1189 break; 1190 } 1191 } 1192 1193 Pred = PN->getIncomingBlock(1); 1194 if (CanPromote && 1195 cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 1196 IfBlock2 = Pred; 1197 DomBlock = *pred_begin(Pred); 1198 for (BasicBlock::iterator I = Pred->begin(); 1199 !isa<TerminatorInst>(I); ++I) 1200 if (!AggressiveInsts.count(I)) { 1201 // This is not an aggressive instruction that we can promote. 1202 // Because of this, we won't be able to get rid of the control 1203 // flow, so the xform is not worth it. 1204 CanPromote = false; 1205 break; 1206 } 1207 } 1208 } 1209 1210 // If we can still promote the PHI nodes after this gauntlet of tests, 1211 // do all of the PHI's now. 1212 if (CanPromote) { 1213 // Move all 'aggressive' instructions, which are defined in the 1214 // conditional parts of the if's up to the dominating block. 1215 if (IfBlock1) { 1216 DomBlock->getInstList().splice(DomBlock->getTerminator(), 1217 IfBlock1->getInstList(), 1218 IfBlock1->begin(), 1219 IfBlock1->getTerminator()); 1220 } 1221 if (IfBlock2) { 1222 DomBlock->getInstList().splice(DomBlock->getTerminator(), 1223 IfBlock2->getInstList(), 1224 IfBlock2->begin(), 1225 IfBlock2->getTerminator()); 1226 } 1227 1228 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 1229 // Change the PHI node into a select instruction. 1230 Value *TrueVal = 1231 PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); 1232 Value *FalseVal = 1233 PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); 1234 1235 std::string Name = PN->getName(); PN->setName(""); 1236 PN->replaceAllUsesWith(new SelectInst(IfCond, TrueVal, FalseVal, 1237 Name, AfterPHIIt)); 1238 BB->getInstList().erase(PN); 1239 } 1240 Changed = true; 1241 } 1242 } 1243 } 1244 1245 return Changed; 1246} 1247