SimplifyCFG.cpp revision 542f149f00afaf1125b8f2040cad4fe05ed24c3a
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#include "llvm/Transforms/Utils/Local.h" 15#include "llvm/Constants.h" 16#include "llvm/Instructions.h" 17#include "llvm/Type.h" 18#include "llvm/Support/CFG.h" 19#include <algorithm> 20#include <functional> 21#include <set> 22using namespace llvm; 23 24// PropagatePredecessorsForPHIs - This gets "Succ" ready to have the 25// predecessors from "BB". This is a little tricky because "Succ" has PHI 26// nodes, which need to have extra slots added to them to hold the merge edges 27// from BB's predecessors, and BB itself might have had PHI nodes in it. This 28// function returns true (failure) if the Succ BB already has a predecessor that 29// is a predecessor of BB and incoming PHI arguments would not be discernible. 30// 31// Assumption: Succ is the single successor for BB. 32// 33static bool PropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 34 assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 35 36 if (!isa<PHINode>(Succ->front())) 37 return false; // We can make the transformation, no problem. 38 39 // If there is more than one predecessor, and there are PHI nodes in 40 // the successor, then we need to add incoming edges for the PHI nodes 41 // 42 const std::vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB)); 43 44 // Check to see if one of the predecessors of BB is already a predecessor of 45 // Succ. If so, we cannot do the transformation if there are any PHI nodes 46 // with incompatible values coming in from the two edges! 47 // 48 for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); PI != PE; ++PI) 49 if (find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end()) { 50 // Loop over all of the PHI nodes checking to see if there are 51 // incompatible values coming in. 52 for (BasicBlock::iterator I = Succ->begin(); 53 PHINode *PN = dyn_cast<PHINode>(I); ++I) { 54 // Loop up the entries in the PHI node for BB and for *PI if the values 55 // coming in are non-equal, we cannot merge these two blocks (instead we 56 // should insert a conditional move or something, then merge the 57 // blocks). 58 int Idx1 = PN->getBasicBlockIndex(BB); 59 int Idx2 = PN->getBasicBlockIndex(*PI); 60 assert(Idx1 != -1 && Idx2 != -1 && 61 "Didn't have entries for my predecessors??"); 62 if (PN->getIncomingValue(Idx1) != PN->getIncomingValue(Idx2)) 63 return true; // Values are not equal... 64 } 65 } 66 67 // Loop over all of the PHI nodes in the successor BB 68 for (BasicBlock::iterator I = Succ->begin(); 69 PHINode *PN = dyn_cast<PHINode>(I); ++I) { 70 Value *OldVal = PN->removeIncomingValue(BB, false); 71 assert(OldVal && "No entry in PHI for Pred BB!"); 72 73 // If this incoming value is one of the PHI nodes in BB... 74 if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 75 PHINode *OldValPN = cast<PHINode>(OldVal); 76 for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(), 77 End = BBPreds.end(); PredI != End; ++PredI) { 78 PN->addIncoming(OldValPN->getIncomingValueForBlock(*PredI), *PredI); 79 } 80 } else { 81 for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(), 82 End = BBPreds.end(); PredI != End; ++PredI) { 83 // Add an incoming value for each of the new incoming values... 84 PN->addIncoming(OldVal, *PredI); 85 } 86 } 87 } 88 return false; 89} 90 91/// GetIfCondition - Given a basic block (BB) with two predecessors (and 92/// presumably PHI nodes in it), check to see if the merge at this block is due 93/// to an "if condition". If so, return the boolean condition that determines 94/// which entry into BB will be taken. Also, return by references the block 95/// that will be entered from if the condition is true, and the block that will 96/// be entered if the condition is false. 97/// 98/// 99static Value *GetIfCondition(BasicBlock *BB, 100 BasicBlock *&IfTrue, BasicBlock *&IfFalse) { 101 assert(std::distance(pred_begin(BB), pred_end(BB)) == 2 && 102 "Function can only handle blocks with 2 predecessors!"); 103 BasicBlock *Pred1 = *pred_begin(BB); 104 BasicBlock *Pred2 = *++pred_begin(BB); 105 106 // We can only handle branches. Other control flow will be lowered to 107 // branches if possible anyway. 108 if (!isa<BranchInst>(Pred1->getTerminator()) || 109 !isa<BranchInst>(Pred2->getTerminator())) 110 return 0; 111 BranchInst *Pred1Br = cast<BranchInst>(Pred1->getTerminator()); 112 BranchInst *Pred2Br = cast<BranchInst>(Pred2->getTerminator()); 113 114 // Eliminate code duplication by ensuring that Pred1Br is conditional if 115 // either are. 116 if (Pred2Br->isConditional()) { 117 // If both branches are conditional, we don't have an "if statement". In 118 // reality, we could transform this case, but since the condition will be 119 // required anyway, we stand no chance of eliminating it, so the xform is 120 // probably not profitable. 121 if (Pred1Br->isConditional()) 122 return 0; 123 124 std::swap(Pred1, Pred2); 125 std::swap(Pred1Br, Pred2Br); 126 } 127 128 if (Pred1Br->isConditional()) { 129 // If we found a conditional branch predecessor, make sure that it branches 130 // to BB and Pred2Br. If it doesn't, this isn't an "if statement". 131 if (Pred1Br->getSuccessor(0) == BB && 132 Pred1Br->getSuccessor(1) == Pred2) { 133 IfTrue = Pred1; 134 IfFalse = Pred2; 135 } else if (Pred1Br->getSuccessor(0) == Pred2 && 136 Pred1Br->getSuccessor(1) == BB) { 137 IfTrue = Pred2; 138 IfFalse = Pred1; 139 } else { 140 // We know that one arm of the conditional goes to BB, so the other must 141 // go somewhere unrelated, and this must not be an "if statement". 142 return 0; 143 } 144 145 // The only thing we have to watch out for here is to make sure that Pred2 146 // doesn't have incoming edges from other blocks. If it does, the condition 147 // doesn't dominate BB. 148 if (++pred_begin(Pred2) != pred_end(Pred2)) 149 return 0; 150 151 return Pred1Br->getCondition(); 152 } 153 154 // Ok, if we got here, both predecessors end with an unconditional branch to 155 // BB. Don't panic! If both blocks only have a single (identical) 156 // predecessor, and THAT is a conditional branch, then we're all ok! 157 if (pred_begin(Pred1) == pred_end(Pred1) || 158 ++pred_begin(Pred1) != pred_end(Pred1) || 159 pred_begin(Pred2) == pred_end(Pred2) || 160 ++pred_begin(Pred2) != pred_end(Pred2) || 161 *pred_begin(Pred1) != *pred_begin(Pred2)) 162 return 0; 163 164 // Otherwise, if this is a conditional branch, then we can use it! 165 BasicBlock *CommonPred = *pred_begin(Pred1); 166 if (BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator())) { 167 assert(BI->isConditional() && "Two successors but not conditional?"); 168 if (BI->getSuccessor(0) == Pred1) { 169 IfTrue = Pred1; 170 IfFalse = Pred2; 171 } else { 172 IfTrue = Pred2; 173 IfFalse = Pred1; 174 } 175 return BI->getCondition(); 176 } 177 return 0; 178} 179 180 181// If we have a merge point of an "if condition" as accepted above, return true 182// if the specified value dominates the block. We don't handle the true 183// generality of domination here, just a special case which works well enough 184// for us. 185static bool DominatesMergePoint(Value *V, BasicBlock *BB) { 186 if (Instruction *I = dyn_cast<Instruction>(V)) { 187 BasicBlock *PBB = I->getParent(); 188 // If this instruction is defined in a block that contains an unconditional 189 // branch to BB, then it must be in the 'conditional' part of the "if 190 // statement". 191 if (isa<BranchInst>(PBB->getTerminator()) && 192 cast<BranchInst>(PBB->getTerminator())->isUnconditional() && 193 cast<BranchInst>(PBB->getTerminator())->getSuccessor(0) == BB) 194 return false; 195 196 // We also don't want to allow wierd loops that might have the "if 197 // condition" in the bottom of this block. 198 if (PBB == BB) return false; 199 } 200 201 // Non-instructions all dominate instructions. 202 return true; 203} 204 205// GatherConstantSetEQs - Given a potentially 'or'd together collection of seteq 206// instructions that compare a value against a constant, return the value being 207// compared, and stick the constant into the Values vector. 208static Value *GatherConstantSetEQs(Value *V, std::vector<Constant*> &Values) { 209 if (Instruction *Inst = dyn_cast<Instruction>(V)) 210 if (Inst->getOpcode() == Instruction::SetEQ) { 211 if (Constant *C = dyn_cast<Constant>(Inst->getOperand(1))) { 212 Values.push_back(C); 213 return Inst->getOperand(0); 214 } else if (Constant *C = dyn_cast<Constant>(Inst->getOperand(0))) { 215 Values.push_back(C); 216 return Inst->getOperand(1); 217 } 218 } else if (Inst->getOpcode() == Instruction::Or) { 219 if (Value *LHS = GatherConstantSetEQs(Inst->getOperand(0), Values)) 220 if (Value *RHS = GatherConstantSetEQs(Inst->getOperand(1), Values)) 221 if (LHS == RHS) 222 return LHS; 223 } 224 return 0; 225} 226 227// GatherConstantSetNEs - Given a potentially 'and'd together collection of 228// setne instructions that compare a value against a constant, return the value 229// being compared, and stick the constant into the Values vector. 230static Value *GatherConstantSetNEs(Value *V, std::vector<Constant*> &Values) { 231 if (Instruction *Inst = dyn_cast<Instruction>(V)) 232 if (Inst->getOpcode() == Instruction::SetNE) { 233 if (Constant *C = dyn_cast<Constant>(Inst->getOperand(1))) { 234 Values.push_back(C); 235 return Inst->getOperand(0); 236 } else if (Constant *C = dyn_cast<Constant>(Inst->getOperand(0))) { 237 Values.push_back(C); 238 return Inst->getOperand(1); 239 } 240 } else if (Inst->getOpcode() == Instruction::Cast) { 241 // Cast of X to bool is really a comparison against zero. 242 assert(Inst->getType() == Type::BoolTy && "Can only handle bool values!"); 243 Values.push_back(Constant::getNullValue(Inst->getOperand(0)->getType())); 244 return Inst->getOperand(0); 245 } else if (Inst->getOpcode() == Instruction::And) { 246 if (Value *LHS = GatherConstantSetNEs(Inst->getOperand(0), Values)) 247 if (Value *RHS = GatherConstantSetNEs(Inst->getOperand(1), Values)) 248 if (LHS == RHS) 249 return LHS; 250 } 251 return 0; 252} 253 254 255 256/// GatherValueComparisons - If the specified Cond is an 'and' or 'or' of a 257/// bunch of comparisons of one value against constants, return the value and 258/// the constants being compared. 259static bool GatherValueComparisons(Instruction *Cond, Value *&CompVal, 260 std::vector<Constant*> &Values) { 261 if (Cond->getOpcode() == Instruction::Or) { 262 CompVal = GatherConstantSetEQs(Cond, Values); 263 264 // Return true to indicate that the condition is true if the CompVal is 265 // equal to one of the constants. 266 return true; 267 } else if (Cond->getOpcode() == Instruction::And) { 268 CompVal = GatherConstantSetNEs(Cond, Values); 269 270 // Return false to indicate that the condition is false if the CompVal is 271 // equal to one of the constants. 272 return false; 273 } 274 return false; 275} 276 277/// ErasePossiblyDeadInstructionTree - If the specified instruction is dead and 278/// has no side effects, nuke it. If it uses any instructions that become dead 279/// because the instruction is now gone, nuke them too. 280static void ErasePossiblyDeadInstructionTree(Instruction *I) { 281 if (isInstructionTriviallyDead(I)) { 282 std::vector<Value*> Operands(I->op_begin(), I->op_end()); 283 I->getParent()->getInstList().erase(I); 284 for (unsigned i = 0, e = Operands.size(); i != e; ++i) 285 if (Instruction *OpI = dyn_cast<Instruction>(Operands[i])) 286 ErasePossiblyDeadInstructionTree(OpI); 287 } 288} 289 290/// SafeToMergeTerminators - Return true if it is safe to merge these two 291/// terminator instructions together. 292/// 293static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) { 294 if (SI1 == SI2) return false; // Can't merge with self! 295 296 // It is not safe to merge these two switch instructions if they have a common 297 // successor, and if that successor has a PHI node, and if that PHI node has 298 // conflicting incoming values from the two switch blocks. 299 BasicBlock *SI1BB = SI1->getParent(); 300 BasicBlock *SI2BB = SI2->getParent(); 301 std::set<BasicBlock*> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 302 303 for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) 304 if (SI1Succs.count(*I)) 305 for (BasicBlock::iterator BBI = (*I)->begin(); 306 PHINode *PN = dyn_cast<PHINode>(BBI); ++BBI) 307 if (PN->getIncomingValueForBlock(SI1BB) != 308 PN->getIncomingValueForBlock(SI2BB)) 309 return false; 310 311 return true; 312} 313 314/// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will 315/// now be entries in it from the 'NewPred' block. The values that will be 316/// flowing into the PHI nodes will be the same as those coming in from 317/// ExistPred, and existing predecessor of Succ. 318static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, 319 BasicBlock *ExistPred) { 320 assert(std::find(succ_begin(ExistPred), succ_end(ExistPred), Succ) != 321 succ_end(ExistPred) && "ExistPred is not a predecessor of Succ!"); 322 if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do 323 324 for (BasicBlock::iterator I = Succ->begin(); 325 PHINode *PN = dyn_cast<PHINode>(I); ++I) { 326 Value *V = PN->getIncomingValueForBlock(ExistPred); 327 PN->addIncoming(V, NewPred); 328 } 329} 330 331// isValueEqualityComparison - Return true if the specified terminator checks to 332// see if a value is equal to constant integer value. 333static Value *isValueEqualityComparison(TerminatorInst *TI) { 334 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) 335 return SI->getCondition(); 336 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 337 if (BI->isConditional() && BI->getCondition()->hasOneUse()) 338 if (SetCondInst *SCI = dyn_cast<SetCondInst>(BI->getCondition())) 339 if ((SCI->getOpcode() == Instruction::SetEQ || 340 SCI->getOpcode() == Instruction::SetNE) && 341 isa<ConstantInt>(SCI->getOperand(1))) 342 return SCI->getOperand(0); 343 return 0; 344} 345 346// Given a value comparison instruction, decode all of the 'cases' that it 347// represents and return the 'default' block. 348static BasicBlock * 349GetValueEqualityComparisonCases(TerminatorInst *TI, 350 std::vector<std::pair<ConstantInt*, 351 BasicBlock*> > &Cases) { 352 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 353 Cases.reserve(SI->getNumCases()); 354 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 355 Cases.push_back(std::make_pair(cast<ConstantInt>(SI->getCaseValue(i)), 356 SI->getSuccessor(i))); 357 return SI->getDefaultDest(); 358 } 359 360 BranchInst *BI = cast<BranchInst>(TI); 361 SetCondInst *SCI = cast<SetCondInst>(BI->getCondition()); 362 Cases.push_back(std::make_pair(cast<ConstantInt>(SCI->getOperand(1)), 363 BI->getSuccessor(SCI->getOpcode() == 364 Instruction::SetNE))); 365 return BI->getSuccessor(SCI->getOpcode() == Instruction::SetEQ); 366} 367 368 369// FoldValueComparisonIntoPredecessors - The specified terminator is a value 370// equality comparison instruction (either a switch or a branch on "X == c"). 371// See if any of the predecessors of the terminator block are value comparisons 372// on the same value. If so, and if safe to do so, fold them together. 373static bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { 374 BasicBlock *BB = TI->getParent(); 375 Value *CV = isValueEqualityComparison(TI); // CondVal 376 assert(CV && "Not a comparison?"); 377 bool Changed = false; 378 379 std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 380 while (!Preds.empty()) { 381 BasicBlock *Pred = Preds.back(); 382 Preds.pop_back(); 383 384 // See if the predecessor is a comparison with the same value. 385 TerminatorInst *PTI = Pred->getTerminator(); 386 Value *PCV = isValueEqualityComparison(PTI); // PredCondVal 387 388 if (PCV == CV && SafeToMergeTerminators(TI, PTI)) { 389 // Figure out which 'cases' to copy from SI to PSI. 390 std::vector<std::pair<ConstantInt*, BasicBlock*> > BBCases; 391 BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases); 392 393 std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 394 BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases); 395 396 // Based on whether the default edge from PTI goes to BB or not, fill in 397 // PredCases and PredDefault with the new switch cases we would like to 398 // build. 399 std::vector<BasicBlock*> NewSuccessors; 400 401 if (PredDefault == BB) { 402 // If this is the default destination from PTI, only the edges in TI 403 // that don't occur in PTI, or that branch to BB will be activated. 404 std::set<ConstantInt*> PTIHandled; 405 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 406 if (PredCases[i].second != BB) 407 PTIHandled.insert(PredCases[i].first); 408 else { 409 // The default destination is BB, we don't need explicit targets. 410 std::swap(PredCases[i], PredCases.back()); 411 PredCases.pop_back(); 412 --i; --e; 413 } 414 415 // Reconstruct the new switch statement we will be building. 416 if (PredDefault != BBDefault) { 417 PredDefault->removePredecessor(Pred); 418 PredDefault = BBDefault; 419 NewSuccessors.push_back(BBDefault); 420 } 421 for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 422 if (!PTIHandled.count(BBCases[i].first) && 423 BBCases[i].second != BBDefault) { 424 PredCases.push_back(BBCases[i]); 425 NewSuccessors.push_back(BBCases[i].second); 426 } 427 428 } else { 429 // If this is not the default destination from PSI, only the edges 430 // in SI that occur in PSI with a destination of BB will be 431 // activated. 432 std::set<ConstantInt*> PTIHandled; 433 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 434 if (PredCases[i].second == BB) { 435 PTIHandled.insert(PredCases[i].first); 436 std::swap(PredCases[i], PredCases.back()); 437 PredCases.pop_back(); 438 --i; --e; 439 } 440 441 // Okay, now we know which constants were sent to BB from the 442 // predecessor. Figure out where they will all go now. 443 for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 444 if (PTIHandled.count(BBCases[i].first)) { 445 // If this is one we are capable of getting... 446 PredCases.push_back(BBCases[i]); 447 NewSuccessors.push_back(BBCases[i].second); 448 PTIHandled.erase(BBCases[i].first);// This constant is taken care of 449 } 450 451 // If there are any constants vectored to BB that TI doesn't handle, 452 // they must go to the default destination of TI. 453 for (std::set<ConstantInt*>::iterator I = PTIHandled.begin(), 454 E = PTIHandled.end(); I != E; ++I) { 455 PredCases.push_back(std::make_pair(*I, BBDefault)); 456 NewSuccessors.push_back(BBDefault); 457 } 458 } 459 460 // Okay, at this point, we know which new successor Pred will get. Make 461 // sure we update the number of entries in the PHI nodes for these 462 // successors. 463 for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i) 464 AddPredecessorToBlock(NewSuccessors[i], Pred, BB); 465 466 // Now that the successors are updated, create the new Switch instruction. 467 SwitchInst *NewSI = new SwitchInst(CV, PredDefault, PTI); 468 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 469 NewSI->addCase(PredCases[i].first, PredCases[i].second); 470 Pred->getInstList().erase(PTI); 471 472 // Okay, last check. If BB is still a successor of PSI, then we must 473 // have an infinite loop case. If so, add an infinitely looping block 474 // to handle the case to preserve the behavior of the code. 475 BasicBlock *InfLoopBlock = 0; 476 for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i) 477 if (NewSI->getSuccessor(i) == BB) { 478 if (InfLoopBlock == 0) { 479 // Insert it at the end of the loop, because it's either code, 480 // or it won't matter if it's hot. :) 481 InfLoopBlock = new BasicBlock("infloop", BB->getParent()); 482 new BranchInst(InfLoopBlock, InfLoopBlock); 483 } 484 NewSI->setSuccessor(i, InfLoopBlock); 485 } 486 487 Changed = true; 488 } 489 } 490 return Changed; 491} 492 493 494// SimplifyCFG - This function is used to do simplification of a CFG. For 495// example, it adjusts branches to branches to eliminate the extra hop, it 496// eliminates unreachable basic blocks, and does other "peephole" optimization 497// of the CFG. It returns true if a modification was made. 498// 499// WARNING: The entry node of a function may not be simplified. 500// 501bool llvm::SimplifyCFG(BasicBlock *BB) { 502 bool Changed = false; 503 Function *M = BB->getParent(); 504 505 assert(BB && BB->getParent() && "Block not embedded in function!"); 506 assert(BB->getTerminator() && "Degenerate basic block encountered!"); 507 assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!"); 508 509 // Remove basic blocks that have no predecessors... which are unreachable. 510 if (pred_begin(BB) == pred_end(BB) || 511 *pred_begin(BB) == BB && ++pred_begin(BB) == pred_end(BB)) { 512 //cerr << "Removing BB: \n" << BB; 513 514 // Loop through all of our successors and make sure they know that one 515 // of their predecessors is going away. 516 for_each(succ_begin(BB), succ_end(BB), 517 std::bind2nd(std::mem_fun(&BasicBlock::removePredecessor), BB)); 518 519 while (!BB->empty()) { 520 Instruction &I = BB->back(); 521 // If this instruction is used, replace uses with an arbitrary 522 // constant value. Because control flow can't get here, we don't care 523 // what we replace the value with. Note that since this block is 524 // unreachable, and all values contained within it must dominate their 525 // uses, that all uses will eventually be removed. 526 if (!I.use_empty()) 527 // Make all users of this instruction reference the constant instead 528 I.replaceAllUsesWith(Constant::getNullValue(I.getType())); 529 530 // Remove the instruction from the basic block 531 BB->getInstList().pop_back(); 532 } 533 M->getBasicBlockList().erase(BB); 534 return true; 535 } 536 537 // Check to see if we can constant propagate this terminator instruction 538 // away... 539 Changed |= ConstantFoldTerminator(BB); 540 541 // Check to see if this block has no non-phi instructions and only a single 542 // successor. If so, replace references to this basic block with references 543 // to the successor. 544 succ_iterator SI(succ_begin(BB)); 545 if (SI != succ_end(BB) && ++SI == succ_end(BB)) { // One succ? 546 547 BasicBlock::iterator BBI = BB->begin(); // Skip over phi nodes... 548 while (isa<PHINode>(*BBI)) ++BBI; 549 550 if (BBI->isTerminator()) { // Terminator is the only non-phi instruction! 551 BasicBlock *Succ = *succ_begin(BB); // There is exactly one successor 552 553 if (Succ != BB) { // Arg, don't hurt infinite loops! 554 // If our successor has PHI nodes, then we need to update them to 555 // include entries for BB's predecessors, not for BB itself. 556 // Be careful though, if this transformation fails (returns true) then 557 // we cannot do this transformation! 558 // 559 if (!PropagatePredecessorsForPHIs(BB, Succ)) { 560 //cerr << "Killing Trivial BB: \n" << BB; 561 std::string OldName = BB->getName(); 562 563 std::vector<BasicBlock*> 564 OldSuccPreds(pred_begin(Succ), pred_end(Succ)); 565 566 // Move all PHI nodes in BB to Succ if they are alive, otherwise 567 // delete them. 568 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) 569 if (PN->use_empty()) 570 BB->getInstList().erase(BB->begin()); // Nuke instruction... 571 else { 572 // The instruction is alive, so this means that Succ must have 573 // *ONLY* had BB as a predecessor, and the PHI node is still valid 574 // now. Simply move it into Succ, because we know that BB 575 // strictly dominated Succ. 576 BB->getInstList().remove(BB->begin()); 577 Succ->getInstList().push_front(PN); 578 579 // We need to add new entries for the PHI node to account for 580 // predecessors of Succ that the PHI node does not take into 581 // account. At this point, since we know that BB dominated succ, 582 // this means that we should any newly added incoming edges should 583 // use the PHI node as the value for these edges, because they are 584 // loop back edges. 585 586 for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i) 587 if (OldSuccPreds[i] != BB) 588 PN->addIncoming(PN, OldSuccPreds[i]); 589 } 590 591 // Everything that jumped to BB now goes to Succ... 592 BB->replaceAllUsesWith(Succ); 593 594 // Delete the old basic block... 595 M->getBasicBlockList().erase(BB); 596 597 if (!OldName.empty() && !Succ->hasName()) // Transfer name if we can 598 Succ->setName(OldName); 599 600 //cerr << "Function after removal: \n" << M; 601 return true; 602 } 603 } 604 } 605 } 606 607 // If this is a returning block with only PHI nodes in it, fold the return 608 // instruction into any unconditional branch predecessors. 609 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 610 BasicBlock::iterator BBI = BB->getTerminator(); 611 if (BBI == BB->begin() || isa<PHINode>(--BBI)) { 612 // Find predecessors that end with unconditional branches. 613 std::vector<BasicBlock*> UncondBranchPreds; 614 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 615 TerminatorInst *PTI = (*PI)->getTerminator(); 616 if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) 617 if (BI->isUnconditional()) 618 UncondBranchPreds.push_back(*PI); 619 } 620 621 // If we found some, do the transformation! 622 if (!UncondBranchPreds.empty()) { 623 while (!UncondBranchPreds.empty()) { 624 BasicBlock *Pred = UncondBranchPreds.back(); 625 UncondBranchPreds.pop_back(); 626 Instruction *UncondBranch = Pred->getTerminator(); 627 // Clone the return and add it to the end of the predecessor. 628 Instruction *NewRet = RI->clone(); 629 Pred->getInstList().push_back(NewRet); 630 631 // If the return instruction returns a value, and if the value was a 632 // PHI node in "BB", propagate the right value into the return. 633 if (NewRet->getNumOperands() == 1) 634 if (PHINode *PN = dyn_cast<PHINode>(NewRet->getOperand(0))) 635 if (PN->getParent() == BB) 636 NewRet->setOperand(0, PN->getIncomingValueForBlock(Pred)); 637 // Update any PHI nodes in the returning block to realize that we no 638 // longer branch to them. 639 BB->removePredecessor(Pred); 640 Pred->getInstList().erase(UncondBranch); 641 } 642 643 // If we eliminated all predecessors of the block, delete the block now. 644 if (pred_begin(BB) == pred_end(BB)) 645 // We know there are no successors, so just nuke the block. 646 M->getBasicBlockList().erase(BB); 647 648 return true; 649 } 650 } 651 } else if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->begin())) { 652 // Check to see if the first instruction in this block is just an unwind. 653 // If so, replace any invoke instructions which use this as an exception 654 // destination with call instructions. 655 // 656 std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 657 while (!Preds.empty()) { 658 BasicBlock *Pred = Preds.back(); 659 if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator())) 660 if (II->getUnwindDest() == BB) { 661 // Insert a new branch instruction before the invoke, because this 662 // is now a fall through... 663 BranchInst *BI = new BranchInst(II->getNormalDest(), II); 664 Pred->getInstList().remove(II); // Take out of symbol table 665 666 // Insert the call now... 667 std::vector<Value*> Args(II->op_begin()+3, II->op_end()); 668 CallInst *CI = new CallInst(II->getCalledValue(), Args, 669 II->getName(), BI); 670 // If the invoke produced a value, the Call now does instead 671 II->replaceAllUsesWith(CI); 672 delete II; 673 Changed = true; 674 } 675 676 Preds.pop_back(); 677 } 678 679 // If this block is now dead, remove it. 680 if (pred_begin(BB) == pred_end(BB)) { 681 // We know there are no successors, so just nuke the block. 682 M->getBasicBlockList().erase(BB); 683 return true; 684 } 685 686 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->begin())) { 687 if (FoldValueComparisonIntoPredecessors(SI)) 688 return SimplifyCFG(BB) || 1; 689 } else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 690 if (Value *CompVal = isValueEqualityComparison(BB->getTerminator())) { 691 // This block must be empty, except for the setcond inst, if it exists. 692 BasicBlock::iterator I = BB->begin(); 693 if (&*I == BI || 694 (&*I == cast<Instruction>(BI->getCondition()) && 695 &*++I == BI)) 696 if (FoldValueComparisonIntoPredecessors(BI)) 697 return SimplifyCFG(BB) || 1; 698 } 699 } 700 701 // Merge basic blocks into their predecessor if there is only one distinct 702 // pred, and if there is only one distinct successor of the predecessor, and 703 // if there are no PHI nodes. 704 // 705 pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 706 BasicBlock *OnlyPred = *PI++; 707 for (; PI != PE; ++PI) // Search all predecessors, see if they are all same 708 if (*PI != OnlyPred) { 709 OnlyPred = 0; // There are multiple different predecessors... 710 break; 711 } 712 713 BasicBlock *OnlySucc = 0; 714 if (OnlyPred && OnlyPred != BB && // Don't break self loops 715 OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) { 716 // Check to see if there is only one distinct successor... 717 succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred)); 718 OnlySucc = BB; 719 for (; SI != SE; ++SI) 720 if (*SI != OnlySucc) { 721 OnlySucc = 0; // There are multiple distinct successors! 722 break; 723 } 724 } 725 726 if (OnlySucc) { 727 //cerr << "Merging: " << BB << "into: " << OnlyPred; 728 TerminatorInst *Term = OnlyPred->getTerminator(); 729 730 // Resolve any PHI nodes at the start of the block. They are all 731 // guaranteed to have exactly one entry if they exist, unless there are 732 // multiple duplicate (but guaranteed to be equal) entries for the 733 // incoming edges. This occurs when there are multiple edges from 734 // OnlyPred to OnlySucc. 735 // 736 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 737 PN->replaceAllUsesWith(PN->getIncomingValue(0)); 738 BB->getInstList().pop_front(); // Delete the phi node... 739 } 740 741 // Delete the unconditional branch from the predecessor... 742 OnlyPred->getInstList().pop_back(); 743 744 // Move all definitions in the successor to the predecessor... 745 OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); 746 747 // Make all PHI nodes that referred to BB now refer to Pred as their 748 // source... 749 BB->replaceAllUsesWith(OnlyPred); 750 751 std::string OldName = BB->getName(); 752 753 // Erase basic block from the function... 754 M->getBasicBlockList().erase(BB); 755 756 // Inherit predecessors name if it exists... 757 if (!OldName.empty() && !OnlyPred->hasName()) 758 OnlyPred->setName(OldName); 759 760 return true; 761 } 762 763 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 764 if (BranchInst *BI = dyn_cast<BranchInst>((*PI)->getTerminator())) 765 // Change br (X == 0 | X == 1), T, F into a switch instruction. 766 if (BI->isConditional() && isa<Instruction>(BI->getCondition())) { 767 Instruction *Cond = cast<Instruction>(BI->getCondition()); 768 // If this is a bunch of seteq's or'd together, or if it's a bunch of 769 // 'setne's and'ed together, collect them. 770 Value *CompVal = 0; 771 std::vector<Constant*> Values; 772 bool TrueWhenEqual = GatherValueComparisons(Cond, CompVal, Values); 773 if (CompVal && CompVal->getType()->isInteger()) { 774 // There might be duplicate constants in the list, which the switch 775 // instruction can't handle, remove them now. 776 std::sort(Values.begin(), Values.end()); 777 Values.erase(std::unique(Values.begin(), Values.end()), Values.end()); 778 779 // Figure out which block is which destination. 780 BasicBlock *DefaultBB = BI->getSuccessor(1); 781 BasicBlock *EdgeBB = BI->getSuccessor(0); 782 if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB); 783 784 // Create the new switch instruction now. 785 SwitchInst *New = new SwitchInst(CompVal, DefaultBB, BI); 786 787 // Add all of the 'cases' to the switch instruction. 788 for (unsigned i = 0, e = Values.size(); i != e; ++i) 789 New->addCase(Values[i], EdgeBB); 790 791 // We added edges from PI to the EdgeBB. As such, if there were any 792 // PHI nodes in EdgeBB, they need entries to be added corresponding to 793 // the number of edges added. 794 for (BasicBlock::iterator BBI = EdgeBB->begin(); 795 PHINode *PN = dyn_cast<PHINode>(BBI); ++BBI) { 796 Value *InVal = PN->getIncomingValueForBlock(*PI); 797 for (unsigned i = 0, e = Values.size()-1; i != e; ++i) 798 PN->addIncoming(InVal, *PI); 799 } 800 801 // Erase the old branch instruction. 802 (*PI)->getInstList().erase(BI); 803 804 // Erase the potentially condition tree that was used to computed the 805 // branch condition. 806 ErasePossiblyDeadInstructionTree(Cond); 807 return true; 808 } 809 } 810 811 // If there is a trivial two-entry PHI node in this basic block, and we can 812 // eliminate it, do so now. 813 if (PHINode *PN = dyn_cast<PHINode>(BB->begin())) 814 if (PN->getNumIncomingValues() == 2) { 815 // Ok, this is a two entry PHI node. Check to see if this is a simple "if 816 // statement", which has a very simple dominance structure. Basically, we 817 // are trying to find the condition that is being branched on, which 818 // subsequently causes this merge to happen. We really want control 819 // dependence information for this check, but simplifycfg can't keep it up 820 // to date, and this catches most of the cases we care about anyway. 821 // 822 BasicBlock *IfTrue, *IfFalse; 823 if (Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse)) { 824 //std::cerr << "FOUND IF CONDITION! " << *IfCond << " T: " 825 // << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"; 826 827 // Figure out where to insert instructions as necessary. 828 BasicBlock::iterator AfterPHIIt = BB->begin(); 829 while (isa<PHINode>(AfterPHIIt)) ++AfterPHIIt; 830 831 BasicBlock::iterator I = BB->begin(); 832 while (PHINode *PN = dyn_cast<PHINode>(I)) { 833 ++I; 834 835 // If we can eliminate this PHI by directly computing it based on the 836 // condition, do so now. We can't eliminate PHI nodes where the 837 // incoming values are defined in the conditional parts of the branch, 838 // so check for this. 839 // 840 if (DominatesMergePoint(PN->getIncomingValue(0), BB) && 841 DominatesMergePoint(PN->getIncomingValue(1), BB)) { 842 Value *TrueVal = 843 PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); 844 Value *FalseVal = 845 PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); 846 847 // FIXME: when we have a 'select' statement, we can be completely 848 // generic and clean here and let the instcombine pass clean up 849 // after us, by folding the select instructions away when possible. 850 // 851 if (TrueVal == FalseVal) { 852 // Degenerate case... 853 PN->replaceAllUsesWith(TrueVal); 854 BB->getInstList().erase(PN); 855 Changed = true; 856 } else if (isa<ConstantBool>(TrueVal) && 857 isa<ConstantBool>(FalseVal)) { 858 if (TrueVal == ConstantBool::True) { 859 // The PHI node produces the same thing as the condition. 860 PN->replaceAllUsesWith(IfCond); 861 } else { 862 // The PHI node produces the inverse of the condition. Insert a 863 // "NOT" instruction, which is really a XOR. 864 Value *InverseCond = 865 BinaryOperator::createNot(IfCond, IfCond->getName()+".inv", 866 AfterPHIIt); 867 PN->replaceAllUsesWith(InverseCond); 868 } 869 BB->getInstList().erase(PN); 870 Changed = true; 871 } else if (isa<ConstantInt>(TrueVal) && isa<ConstantInt>(FalseVal)){ 872 // If this is a PHI of two constant integers, we insert a cast of 873 // the boolean to the integer type in question, giving us 0 or 1. 874 // Then we multiply this by the difference of the two constants, 875 // giving us 0 if false, and the difference if true. We add this 876 // result to the base constant, giving us our final value. We 877 // rely on the instruction combiner to eliminate many special 878 // cases, like turning multiplies into shifts when possible. 879 std::string Name = PN->getName(); PN->setName(""); 880 Value *TheCast = new CastInst(IfCond, TrueVal->getType(), 881 Name, AfterPHIIt); 882 Constant *TheDiff = ConstantExpr::get(Instruction::Sub, 883 cast<Constant>(TrueVal), 884 cast<Constant>(FalseVal)); 885 Value *V = TheCast; 886 if (TheDiff != ConstantInt::get(TrueVal->getType(), 1)) 887 V = BinaryOperator::create(Instruction::Mul, TheCast, 888 TheDiff, TheCast->getName()+".scale", 889 AfterPHIIt); 890 if (!cast<Constant>(FalseVal)->isNullValue()) 891 V = BinaryOperator::create(Instruction::Add, V, FalseVal, 892 V->getName()+".offs", AfterPHIIt); 893 PN->replaceAllUsesWith(V); 894 BB->getInstList().erase(PN); 895 Changed = true; 896 } else if (isa<ConstantInt>(FalseVal) && 897 cast<Constant>(FalseVal)->isNullValue()) { 898 // If the false condition is an integral zero value, we can 899 // compute the PHI by multiplying the condition by the other 900 // value. 901 std::string Name = PN->getName(); PN->setName(""); 902 Value *TheCast = new CastInst(IfCond, TrueVal->getType(), 903 Name+".c", AfterPHIIt); 904 Value *V = BinaryOperator::create(Instruction::Mul, TrueVal, 905 TheCast, Name, AfterPHIIt); 906 PN->replaceAllUsesWith(V); 907 BB->getInstList().erase(PN); 908 Changed = true; 909 } else if (isa<ConstantInt>(TrueVal) && 910 cast<Constant>(TrueVal)->isNullValue()) { 911 // If the true condition is an integral zero value, we can compute 912 // the PHI by multiplying the inverse condition by the other 913 // value. 914 std::string Name = PN->getName(); PN->setName(""); 915 Value *NotCond = BinaryOperator::createNot(IfCond, Name+".inv", 916 AfterPHIIt); 917 Value *TheCast = new CastInst(NotCond, TrueVal->getType(), 918 Name+".inv", AfterPHIIt); 919 Value *V = BinaryOperator::create(Instruction::Mul, FalseVal, 920 TheCast, Name, AfterPHIIt); 921 PN->replaceAllUsesWith(V); 922 BB->getInstList().erase(PN); 923 Changed = true; 924 } 925 } 926 } 927 } 928 } 929 930 return Changed; 931} 932