SimplifyCFG.cpp revision 280a6e607d8eb7401749a92db624a82de47da777
1//===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// 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/DerivedTypes.h" 20#include "llvm/Support/CFG.h" 21#include "llvm/Support/Debug.h" 22#include "llvm/Analysis/ConstantFolding.h" 23#include "llvm/Transforms/Utils/BasicBlockUtils.h" 24#include "llvm/ADT/SmallVector.h" 25#include "llvm/ADT/SmallPtrSet.h" 26#include <algorithm> 27#include <functional> 28#include <set> 29#include <map> 30using namespace llvm; 31 32/// SafeToMergeTerminators - Return true if it is safe to merge these two 33/// terminator instructions together. 34/// 35static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) { 36 if (SI1 == SI2) return false; // Can't merge with self! 37 38 // It is not safe to merge these two switch instructions if they have a common 39 // successor, and if that successor has a PHI node, and if *that* PHI node has 40 // conflicting incoming values from the two switch blocks. 41 BasicBlock *SI1BB = SI1->getParent(); 42 BasicBlock *SI2BB = SI2->getParent(); 43 SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 44 45 for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) 46 if (SI1Succs.count(*I)) 47 for (BasicBlock::iterator BBI = (*I)->begin(); 48 isa<PHINode>(BBI); ++BBI) { 49 PHINode *PN = cast<PHINode>(BBI); 50 if (PN->getIncomingValueForBlock(SI1BB) != 51 PN->getIncomingValueForBlock(SI2BB)) 52 return false; 53 } 54 55 return true; 56} 57 58/// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will 59/// now be entries in it from the 'NewPred' block. The values that will be 60/// flowing into the PHI nodes will be the same as those coming in from 61/// ExistPred, an existing predecessor of Succ. 62static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, 63 BasicBlock *ExistPred) { 64 assert(std::find(succ_begin(ExistPred), succ_end(ExistPred), Succ) != 65 succ_end(ExistPred) && "ExistPred is not a predecessor of Succ!"); 66 if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do 67 68 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 69 PHINode *PN = cast<PHINode>(I); 70 Value *V = PN->getIncomingValueForBlock(ExistPred); 71 PN->addIncoming(V, NewPred); 72 } 73} 74 75// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an 76// almost-empty BB ending in an unconditional branch to Succ, into succ. 77// 78// Assumption: Succ is the single successor for BB. 79// 80static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 81 assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 82 83 // Check to see if one of the predecessors of BB is already a predecessor of 84 // Succ. If so, we cannot do the transformation if there are any PHI nodes 85 // with incompatible values coming in from the two edges! 86 // 87 if (isa<PHINode>(Succ->front())) { 88 SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB)); 89 for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); 90 PI != PE; ++PI) 91 if (BBPreds.count(*PI)) { 92 // Loop over all of the PHI nodes checking to see if there are 93 // incompatible values coming in. 94 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 95 PHINode *PN = cast<PHINode>(I); 96 // Loop up the entries in the PHI node for BB and for *PI if the 97 // values coming in are non-equal, we cannot merge these two blocks 98 // (instead we should insert a conditional move or something, then 99 // merge the blocks). 100 if (PN->getIncomingValueForBlock(BB) != 101 PN->getIncomingValueForBlock(*PI)) 102 return false; // Values are not equal... 103 } 104 } 105 } 106 107 // Finally, if BB has PHI nodes that are used by things other than the PHIs in 108 // Succ and Succ has predecessors that are not Succ and not Pred, we cannot 109 // fold these blocks, as we don't know whether BB dominates Succ or not to 110 // update the PHI nodes correctly. 111 if (!isa<PHINode>(BB->begin()) || Succ->getSinglePredecessor()) return true; 112 113 // If the predecessors of Succ are only BB, handle it. 114 bool IsSafe = true; 115 for (pred_iterator PI = pred_begin(Succ), E = pred_end(Succ); PI != E; ++PI) 116 if (*PI != BB) { 117 IsSafe = false; 118 break; 119 } 120 if (IsSafe) return true; 121 122 // If the PHI nodes in BB are only used by instructions in Succ, we are ok if 123 // BB and Succ have no common predecessors. 124 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I) { 125 PHINode *PN = cast<PHINode>(I); 126 for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end(); UI != E; 127 ++UI) 128 if (cast<Instruction>(*UI)->getParent() != Succ) 129 return false; 130 } 131 132 // Scan the predecessor sets of BB and Succ, making sure there are no common 133 // predecessors. Common predecessors would cause us to build a phi node with 134 // differing incoming values, which is not legal. 135 SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB)); 136 for (pred_iterator PI = pred_begin(Succ), E = pred_end(Succ); PI != E; ++PI) 137 if (BBPreds.count(*PI)) 138 return false; 139 140 return true; 141} 142 143/// TryToSimplifyUncondBranchFromEmptyBlock - BB contains an unconditional 144/// branch to Succ, and contains no instructions other than PHI nodes and the 145/// branch. If possible, eliminate BB. 146static bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, 147 BasicBlock *Succ) { 148 // If our successor has PHI nodes, then we need to update them to include 149 // entries for BB's predecessors, not for BB itself. Be careful though, 150 // if this transformation fails (returns true) then we cannot do this 151 // transformation! 152 // 153 if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; 154 155 DOUT << "Killing Trivial BB: \n" << *BB; 156 157 if (isa<PHINode>(Succ->begin())) { 158 // If there is more than one pred of succ, and there are PHI nodes in 159 // the successor, then we need to add incoming edges for the PHI nodes 160 // 161 const SmallVector<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB)); 162 163 // Loop over all of the PHI nodes in the successor of BB. 164 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 165 PHINode *PN = cast<PHINode>(I); 166 Value *OldVal = PN->removeIncomingValue(BB, false); 167 assert(OldVal && "No entry in PHI for Pred BB!"); 168 169 // If this incoming value is one of the PHI nodes in BB, the new entries 170 // in the PHI node are the entries from the old PHI. 171 if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 172 PHINode *OldValPN = cast<PHINode>(OldVal); 173 for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) 174 PN->addIncoming(OldValPN->getIncomingValue(i), 175 OldValPN->getIncomingBlock(i)); 176 } else { 177 // Add an incoming value for each of the new incoming values. 178 for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) 179 PN->addIncoming(OldVal, BBPreds[i]); 180 } 181 } 182 } 183 184 if (isa<PHINode>(&BB->front())) { 185 SmallVector<BasicBlock*, 16> 186 OldSuccPreds(pred_begin(Succ), pred_end(Succ)); 187 188 // Move all PHI nodes in BB to Succ if they are alive, otherwise 189 // delete them. 190 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) 191 if (PN->use_empty()) { 192 // Just remove the dead phi. This happens if Succ's PHIs were the only 193 // users of the PHI nodes. 194 PN->eraseFromParent(); 195 } else { 196 // The instruction is alive, so this means that Succ must have 197 // *ONLY* had BB as a predecessor, and the PHI node is still valid 198 // now. Simply move it into Succ, because we know that BB 199 // strictly dominated Succ. 200 Succ->getInstList().splice(Succ->begin(), 201 BB->getInstList(), BB->begin()); 202 203 // We need to add new entries for the PHI node to account for 204 // predecessors of Succ that the PHI node does not take into 205 // account. At this point, since we know that BB dominated succ, 206 // this means that we should any newly added incoming edges should 207 // use the PHI node as the value for these edges, because they are 208 // loop back edges. 209 for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i) 210 if (OldSuccPreds[i] != BB) 211 PN->addIncoming(PN, OldSuccPreds[i]); 212 } 213 } 214 215 // Everything that jumped to BB now goes to Succ. 216 BB->replaceAllUsesWith(Succ); 217 if (!Succ->hasName()) Succ->takeName(BB); 218 BB->eraseFromParent(); // Delete the old basic block. 219 return true; 220} 221 222/// GetIfCondition - Given a basic block (BB) with two predecessors (and 223/// presumably PHI nodes in it), check to see if the merge at this block is due 224/// to an "if condition". If so, return the boolean condition that determines 225/// which entry into BB will be taken. Also, return by references the block 226/// that will be entered from if the condition is true, and the block that will 227/// be entered if the condition is false. 228/// 229/// 230static Value *GetIfCondition(BasicBlock *BB, 231 BasicBlock *&IfTrue, BasicBlock *&IfFalse) { 232 assert(std::distance(pred_begin(BB), pred_end(BB)) == 2 && 233 "Function can only handle blocks with 2 predecessors!"); 234 BasicBlock *Pred1 = *pred_begin(BB); 235 BasicBlock *Pred2 = *++pred_begin(BB); 236 237 // We can only handle branches. Other control flow will be lowered to 238 // branches if possible anyway. 239 if (!isa<BranchInst>(Pred1->getTerminator()) || 240 !isa<BranchInst>(Pred2->getTerminator())) 241 return 0; 242 BranchInst *Pred1Br = cast<BranchInst>(Pred1->getTerminator()); 243 BranchInst *Pred2Br = cast<BranchInst>(Pred2->getTerminator()); 244 245 // Eliminate code duplication by ensuring that Pred1Br is conditional if 246 // either are. 247 if (Pred2Br->isConditional()) { 248 // If both branches are conditional, we don't have an "if statement". In 249 // reality, we could transform this case, but since the condition will be 250 // required anyway, we stand no chance of eliminating it, so the xform is 251 // probably not profitable. 252 if (Pred1Br->isConditional()) 253 return 0; 254 255 std::swap(Pred1, Pred2); 256 std::swap(Pred1Br, Pred2Br); 257 } 258 259 if (Pred1Br->isConditional()) { 260 // If we found a conditional branch predecessor, make sure that it branches 261 // to BB and Pred2Br. If it doesn't, this isn't an "if statement". 262 if (Pred1Br->getSuccessor(0) == BB && 263 Pred1Br->getSuccessor(1) == Pred2) { 264 IfTrue = Pred1; 265 IfFalse = Pred2; 266 } else if (Pred1Br->getSuccessor(0) == Pred2 && 267 Pred1Br->getSuccessor(1) == BB) { 268 IfTrue = Pred2; 269 IfFalse = Pred1; 270 } else { 271 // We know that one arm of the conditional goes to BB, so the other must 272 // go somewhere unrelated, and this must not be an "if statement". 273 return 0; 274 } 275 276 // The only thing we have to watch out for here is to make sure that Pred2 277 // doesn't have incoming edges from other blocks. If it does, the condition 278 // doesn't dominate BB. 279 if (++pred_begin(Pred2) != pred_end(Pred2)) 280 return 0; 281 282 return Pred1Br->getCondition(); 283 } 284 285 // Ok, if we got here, both predecessors end with an unconditional branch to 286 // BB. Don't panic! If both blocks only have a single (identical) 287 // predecessor, and THAT is a conditional branch, then we're all ok! 288 if (pred_begin(Pred1) == pred_end(Pred1) || 289 ++pred_begin(Pred1) != pred_end(Pred1) || 290 pred_begin(Pred2) == pred_end(Pred2) || 291 ++pred_begin(Pred2) != pred_end(Pred2) || 292 *pred_begin(Pred1) != *pred_begin(Pred2)) 293 return 0; 294 295 // Otherwise, if this is a conditional branch, then we can use it! 296 BasicBlock *CommonPred = *pred_begin(Pred1); 297 if (BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator())) { 298 assert(BI->isConditional() && "Two successors but not conditional?"); 299 if (BI->getSuccessor(0) == Pred1) { 300 IfTrue = Pred1; 301 IfFalse = Pred2; 302 } else { 303 IfTrue = Pred2; 304 IfFalse = Pred1; 305 } 306 return BI->getCondition(); 307 } 308 return 0; 309} 310 311 312// If we have a merge point of an "if condition" as accepted above, return true 313// if the specified value dominates the block. We don't handle the true 314// generality of domination here, just a special case which works well enough 315// for us. 316// 317// If AggressiveInsts is non-null, and if V does not dominate BB, we check to 318// see if V (which must be an instruction) is cheap to compute and is 319// non-trapping. If both are true, the instruction is inserted into the set and 320// true is returned. 321static bool DominatesMergePoint(Value *V, BasicBlock *BB, 322 std::set<Instruction*> *AggressiveInsts) { 323 Instruction *I = dyn_cast<Instruction>(V); 324 if (!I) { 325 // Non-instructions all dominate instructions, but not all constantexprs 326 // can be executed unconditionally. 327 if (ConstantExpr *C = dyn_cast<ConstantExpr>(V)) 328 if (C->canTrap()) 329 return false; 330 return true; 331 } 332 BasicBlock *PBB = I->getParent(); 333 334 // We don't want to allow weird loops that might have the "if condition" in 335 // the bottom of this block. 336 if (PBB == BB) return false; 337 338 // If this instruction is defined in a block that contains an unconditional 339 // branch to BB, then it must be in the 'conditional' part of the "if 340 // statement". 341 if (BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator())) 342 if (BI->isUnconditional() && BI->getSuccessor(0) == BB) { 343 if (!AggressiveInsts) return false; 344 // Okay, it looks like the instruction IS in the "condition". Check to 345 // see if its a cheap instruction to unconditionally compute, and if it 346 // only uses stuff defined outside of the condition. If so, hoist it out. 347 switch (I->getOpcode()) { 348 default: return false; // Cannot hoist this out safely. 349 case Instruction::Load: 350 // We can hoist loads that are non-volatile and obviously cannot trap. 351 if (cast<LoadInst>(I)->isVolatile()) 352 return false; 353 if (!isa<AllocaInst>(I->getOperand(0)) && 354 !isa<Constant>(I->getOperand(0))) 355 return false; 356 357 // Finally, we have to check to make sure there are no instructions 358 // before the load in its basic block, as we are going to hoist the loop 359 // out to its predecessor. 360 if (PBB->begin() != BasicBlock::iterator(I)) 361 return false; 362 break; 363 case Instruction::Add: 364 case Instruction::Sub: 365 case Instruction::And: 366 case Instruction::Or: 367 case Instruction::Xor: 368 case Instruction::Shl: 369 case Instruction::LShr: 370 case Instruction::AShr: 371 case Instruction::ICmp: 372 case Instruction::FCmp: 373 if (I->getOperand(0)->getType()->isFPOrFPVector()) 374 return false; // FP arithmetic might trap. 375 break; // These are all cheap and non-trapping instructions. 376 } 377 378 // Okay, we can only really hoist these out if their operands are not 379 // defined in the conditional region. 380 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 381 if (!DominatesMergePoint(I->getOperand(i), BB, 0)) 382 return false; 383 // Okay, it's safe to do this! Remember this instruction. 384 AggressiveInsts->insert(I); 385 } 386 387 return true; 388} 389 390// GatherConstantSetEQs - Given a potentially 'or'd together collection of 391// icmp_eq instructions that compare a value against a constant, return the 392// value being compared, and stick the constant into the Values vector. 393static Value *GatherConstantSetEQs(Value *V, std::vector<ConstantInt*> &Values){ 394 if (Instruction *Inst = dyn_cast<Instruction>(V)) { 395 if (Inst->getOpcode() == Instruction::ICmp && 396 cast<ICmpInst>(Inst)->getPredicate() == ICmpInst::ICMP_EQ) { 397 if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) { 398 Values.push_back(C); 399 return Inst->getOperand(0); 400 } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) { 401 Values.push_back(C); 402 return Inst->getOperand(1); 403 } 404 } else if (Inst->getOpcode() == Instruction::Or) { 405 if (Value *LHS = GatherConstantSetEQs(Inst->getOperand(0), Values)) 406 if (Value *RHS = GatherConstantSetEQs(Inst->getOperand(1), Values)) 407 if (LHS == RHS) 408 return LHS; 409 } 410 } 411 return 0; 412} 413 414// GatherConstantSetNEs - Given a potentially 'and'd together collection of 415// setne instructions that compare a value against a constant, return the value 416// being compared, and stick the constant into the Values vector. 417static Value *GatherConstantSetNEs(Value *V, std::vector<ConstantInt*> &Values){ 418 if (Instruction *Inst = dyn_cast<Instruction>(V)) { 419 if (Inst->getOpcode() == Instruction::ICmp && 420 cast<ICmpInst>(Inst)->getPredicate() == ICmpInst::ICMP_NE) { 421 if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) { 422 Values.push_back(C); 423 return Inst->getOperand(0); 424 } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) { 425 Values.push_back(C); 426 return Inst->getOperand(1); 427 } 428 } else if (Inst->getOpcode() == Instruction::And) { 429 if (Value *LHS = GatherConstantSetNEs(Inst->getOperand(0), Values)) 430 if (Value *RHS = GatherConstantSetNEs(Inst->getOperand(1), Values)) 431 if (LHS == RHS) 432 return LHS; 433 } 434 } 435 return 0; 436} 437 438 439 440/// GatherValueComparisons - If the specified Cond is an 'and' or 'or' of a 441/// bunch of comparisons of one value against constants, return the value and 442/// the constants being compared. 443static bool GatherValueComparisons(Instruction *Cond, Value *&CompVal, 444 std::vector<ConstantInt*> &Values) { 445 if (Cond->getOpcode() == Instruction::Or) { 446 CompVal = GatherConstantSetEQs(Cond, Values); 447 448 // Return true to indicate that the condition is true if the CompVal is 449 // equal to one of the constants. 450 return true; 451 } else if (Cond->getOpcode() == Instruction::And) { 452 CompVal = GatherConstantSetNEs(Cond, Values); 453 454 // Return false to indicate that the condition is false if the CompVal is 455 // equal to one of the constants. 456 return false; 457 } 458 return false; 459} 460 461/// ErasePossiblyDeadInstructionTree - If the specified instruction is dead and 462/// has no side effects, nuke it. If it uses any instructions that become dead 463/// because the instruction is now gone, nuke them too. 464static void ErasePossiblyDeadInstructionTree(Instruction *I) { 465 if (!isInstructionTriviallyDead(I)) return; 466 467 SmallVector<Instruction*, 16> InstrsToInspect; 468 InstrsToInspect.push_back(I); 469 470 while (!InstrsToInspect.empty()) { 471 I = InstrsToInspect.back(); 472 InstrsToInspect.pop_back(); 473 474 if (!isInstructionTriviallyDead(I)) continue; 475 476 // If I is in the work list multiple times, remove previous instances. 477 for (unsigned i = 0, e = InstrsToInspect.size(); i != e; ++i) 478 if (InstrsToInspect[i] == I) { 479 InstrsToInspect.erase(InstrsToInspect.begin()+i); 480 --i, --e; 481 } 482 483 // Add operands of dead instruction to worklist. 484 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 485 if (Instruction *OpI = dyn_cast<Instruction>(I->getOperand(i))) 486 InstrsToInspect.push_back(OpI); 487 488 // Remove dead instruction. 489 I->eraseFromParent(); 490 } 491} 492 493// isValueEqualityComparison - Return true if the specified terminator checks to 494// see if a value is equal to constant integer value. 495static Value *isValueEqualityComparison(TerminatorInst *TI) { 496 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 497 // Do not permit merging of large switch instructions into their 498 // predecessors unless there is only one predecessor. 499 if (SI->getNumSuccessors() * std::distance(pred_begin(SI->getParent()), 500 pred_end(SI->getParent())) > 128) 501 return 0; 502 503 return SI->getCondition(); 504 } 505 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 506 if (BI->isConditional() && BI->getCondition()->hasOneUse()) 507 if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) 508 if ((ICI->getPredicate() == ICmpInst::ICMP_EQ || 509 ICI->getPredicate() == ICmpInst::ICMP_NE) && 510 isa<ConstantInt>(ICI->getOperand(1))) 511 return ICI->getOperand(0); 512 return 0; 513} 514 515// Given a value comparison instruction, decode all of the 'cases' that it 516// represents and return the 'default' block. 517static BasicBlock * 518GetValueEqualityComparisonCases(TerminatorInst *TI, 519 std::vector<std::pair<ConstantInt*, 520 BasicBlock*> > &Cases) { 521 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 522 Cases.reserve(SI->getNumCases()); 523 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 524 Cases.push_back(std::make_pair(SI->getCaseValue(i), SI->getSuccessor(i))); 525 return SI->getDefaultDest(); 526 } 527 528 BranchInst *BI = cast<BranchInst>(TI); 529 ICmpInst *ICI = cast<ICmpInst>(BI->getCondition()); 530 Cases.push_back(std::make_pair(cast<ConstantInt>(ICI->getOperand(1)), 531 BI->getSuccessor(ICI->getPredicate() == 532 ICmpInst::ICMP_NE))); 533 return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ); 534} 535 536 537// EliminateBlockCases - Given a vector of bb/value pairs, remove any entries 538// in the list that match the specified block. 539static void EliminateBlockCases(BasicBlock *BB, 540 std::vector<std::pair<ConstantInt*, BasicBlock*> > &Cases) { 541 for (unsigned i = 0, e = Cases.size(); i != e; ++i) 542 if (Cases[i].second == BB) { 543 Cases.erase(Cases.begin()+i); 544 --i; --e; 545 } 546} 547 548// ValuesOverlap - Return true if there are any keys in C1 that exist in C2 as 549// well. 550static bool 551ValuesOverlap(std::vector<std::pair<ConstantInt*, BasicBlock*> > &C1, 552 std::vector<std::pair<ConstantInt*, BasicBlock*> > &C2) { 553 std::vector<std::pair<ConstantInt*, BasicBlock*> > *V1 = &C1, *V2 = &C2; 554 555 // Make V1 be smaller than V2. 556 if (V1->size() > V2->size()) 557 std::swap(V1, V2); 558 559 if (V1->size() == 0) return false; 560 if (V1->size() == 1) { 561 // Just scan V2. 562 ConstantInt *TheVal = (*V1)[0].first; 563 for (unsigned i = 0, e = V2->size(); i != e; ++i) 564 if (TheVal == (*V2)[i].first) 565 return true; 566 } 567 568 // Otherwise, just sort both lists and compare element by element. 569 std::sort(V1->begin(), V1->end()); 570 std::sort(V2->begin(), V2->end()); 571 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size(); 572 while (i1 != e1 && i2 != e2) { 573 if ((*V1)[i1].first == (*V2)[i2].first) 574 return true; 575 if ((*V1)[i1].first < (*V2)[i2].first) 576 ++i1; 577 else 578 ++i2; 579 } 580 return false; 581} 582 583// SimplifyEqualityComparisonWithOnlyPredecessor - If TI is known to be a 584// terminator instruction and its block is known to only have a single 585// predecessor block, check to see if that predecessor is also a value 586// comparison with the same value, and if that comparison determines the outcome 587// of this comparison. If so, simplify TI. This does a very limited form of 588// jump threading. 589static bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, 590 BasicBlock *Pred) { 591 Value *PredVal = isValueEqualityComparison(Pred->getTerminator()); 592 if (!PredVal) return false; // Not a value comparison in predecessor. 593 594 Value *ThisVal = isValueEqualityComparison(TI); 595 assert(ThisVal && "This isn't a value comparison!!"); 596 if (ThisVal != PredVal) return false; // Different predicates. 597 598 // Find out information about when control will move from Pred to TI's block. 599 std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 600 BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(), 601 PredCases); 602 EliminateBlockCases(PredDef, PredCases); // Remove default from cases. 603 604 // Find information about how control leaves this block. 605 std::vector<std::pair<ConstantInt*, BasicBlock*> > ThisCases; 606 BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases); 607 EliminateBlockCases(ThisDef, ThisCases); // Remove default from cases. 608 609 // If TI's block is the default block from Pred's comparison, potentially 610 // simplify TI based on this knowledge. 611 if (PredDef == TI->getParent()) { 612 // If we are here, we know that the value is none of those cases listed in 613 // PredCases. If there are any cases in ThisCases that are in PredCases, we 614 // can simplify TI. 615 if (ValuesOverlap(PredCases, ThisCases)) { 616 if (BranchInst *BTI = dyn_cast<BranchInst>(TI)) { 617 // Okay, one of the successors of this condbr is dead. Convert it to a 618 // uncond br. 619 assert(ThisCases.size() == 1 && "Branch can only have one case!"); 620 Value *Cond = BTI->getCondition(); 621 // Insert the new branch. 622 Instruction *NI = BranchInst::Create(ThisDef, TI); 623 624 // Remove PHI node entries for the dead edge. 625 ThisCases[0].second->removePredecessor(TI->getParent()); 626 627 DOUT << "Threading pred instr: " << *Pred->getTerminator() 628 << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"; 629 630 TI->eraseFromParent(); // Nuke the old one. 631 // If condition is now dead, nuke it. 632 if (Instruction *CondI = dyn_cast<Instruction>(Cond)) 633 ErasePossiblyDeadInstructionTree(CondI); 634 return true; 635 636 } else { 637 SwitchInst *SI = cast<SwitchInst>(TI); 638 // Okay, TI has cases that are statically dead, prune them away. 639 SmallPtrSet<Constant*, 16> DeadCases; 640 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 641 DeadCases.insert(PredCases[i].first); 642 643 DOUT << "Threading pred instr: " << *Pred->getTerminator() 644 << "Through successor TI: " << *TI; 645 646 for (unsigned i = SI->getNumCases()-1; i != 0; --i) 647 if (DeadCases.count(SI->getCaseValue(i))) { 648 SI->getSuccessor(i)->removePredecessor(TI->getParent()); 649 SI->removeCase(i); 650 } 651 652 DOUT << "Leaving: " << *TI << "\n"; 653 return true; 654 } 655 } 656 657 } else { 658 // Otherwise, TI's block must correspond to some matched value. Find out 659 // which value (or set of values) this is. 660 ConstantInt *TIV = 0; 661 BasicBlock *TIBB = TI->getParent(); 662 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 663 if (PredCases[i].second == TIBB) { 664 if (TIV == 0) 665 TIV = PredCases[i].first; 666 else 667 return false; // Cannot handle multiple values coming to this block. 668 } 669 assert(TIV && "No edge from pred to succ?"); 670 671 // Okay, we found the one constant that our value can be if we get into TI's 672 // BB. Find out which successor will unconditionally be branched to. 673 BasicBlock *TheRealDest = 0; 674 for (unsigned i = 0, e = ThisCases.size(); i != e; ++i) 675 if (ThisCases[i].first == TIV) { 676 TheRealDest = ThisCases[i].second; 677 break; 678 } 679 680 // If not handled by any explicit cases, it is handled by the default case. 681 if (TheRealDest == 0) TheRealDest = ThisDef; 682 683 // Remove PHI node entries for dead edges. 684 BasicBlock *CheckEdge = TheRealDest; 685 for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI) 686 if (*SI != CheckEdge) 687 (*SI)->removePredecessor(TIBB); 688 else 689 CheckEdge = 0; 690 691 // Insert the new branch. 692 Instruction *NI = BranchInst::Create(TheRealDest, TI); 693 694 DOUT << "Threading pred instr: " << *Pred->getTerminator() 695 << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"; 696 Instruction *Cond = 0; 697 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 698 Cond = dyn_cast<Instruction>(BI->getCondition()); 699 TI->eraseFromParent(); // Nuke the old one. 700 701 if (Cond) ErasePossiblyDeadInstructionTree(Cond); 702 return true; 703 } 704 return false; 705} 706 707// FoldValueComparisonIntoPredecessors - The specified terminator is a value 708// equality comparison instruction (either a switch or a branch on "X == c"). 709// See if any of the predecessors of the terminator block are value comparisons 710// on the same value. If so, and if safe to do so, fold them together. 711static bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { 712 BasicBlock *BB = TI->getParent(); 713 Value *CV = isValueEqualityComparison(TI); // CondVal 714 assert(CV && "Not a comparison?"); 715 bool Changed = false; 716 717 SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB)); 718 while (!Preds.empty()) { 719 BasicBlock *Pred = Preds.back(); 720 Preds.pop_back(); 721 722 // See if the predecessor is a comparison with the same value. 723 TerminatorInst *PTI = Pred->getTerminator(); 724 Value *PCV = isValueEqualityComparison(PTI); // PredCondVal 725 726 if (PCV == CV && SafeToMergeTerminators(TI, PTI)) { 727 // Figure out which 'cases' to copy from SI to PSI. 728 std::vector<std::pair<ConstantInt*, BasicBlock*> > BBCases; 729 BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases); 730 731 std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 732 BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases); 733 734 // Based on whether the default edge from PTI goes to BB or not, fill in 735 // PredCases and PredDefault with the new switch cases we would like to 736 // build. 737 SmallVector<BasicBlock*, 8> NewSuccessors; 738 739 if (PredDefault == BB) { 740 // If this is the default destination from PTI, only the edges in TI 741 // that don't occur in PTI, or that branch to BB will be activated. 742 std::set<ConstantInt*> PTIHandled; 743 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 744 if (PredCases[i].second != BB) 745 PTIHandled.insert(PredCases[i].first); 746 else { 747 // The default destination is BB, we don't need explicit targets. 748 std::swap(PredCases[i], PredCases.back()); 749 PredCases.pop_back(); 750 --i; --e; 751 } 752 753 // Reconstruct the new switch statement we will be building. 754 if (PredDefault != BBDefault) { 755 PredDefault->removePredecessor(Pred); 756 PredDefault = BBDefault; 757 NewSuccessors.push_back(BBDefault); 758 } 759 for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 760 if (!PTIHandled.count(BBCases[i].first) && 761 BBCases[i].second != BBDefault) { 762 PredCases.push_back(BBCases[i]); 763 NewSuccessors.push_back(BBCases[i].second); 764 } 765 766 } else { 767 // If this is not the default destination from PSI, only the edges 768 // in SI that occur in PSI with a destination of BB will be 769 // activated. 770 std::set<ConstantInt*> PTIHandled; 771 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 772 if (PredCases[i].second == BB) { 773 PTIHandled.insert(PredCases[i].first); 774 std::swap(PredCases[i], PredCases.back()); 775 PredCases.pop_back(); 776 --i; --e; 777 } 778 779 // Okay, now we know which constants were sent to BB from the 780 // predecessor. Figure out where they will all go now. 781 for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 782 if (PTIHandled.count(BBCases[i].first)) { 783 // If this is one we are capable of getting... 784 PredCases.push_back(BBCases[i]); 785 NewSuccessors.push_back(BBCases[i].second); 786 PTIHandled.erase(BBCases[i].first);// This constant is taken care of 787 } 788 789 // If there are any constants vectored to BB that TI doesn't handle, 790 // they must go to the default destination of TI. 791 for (std::set<ConstantInt*>::iterator I = PTIHandled.begin(), 792 E = PTIHandled.end(); I != E; ++I) { 793 PredCases.push_back(std::make_pair(*I, BBDefault)); 794 NewSuccessors.push_back(BBDefault); 795 } 796 } 797 798 // Okay, at this point, we know which new successor Pred will get. Make 799 // sure we update the number of entries in the PHI nodes for these 800 // successors. 801 for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i) 802 AddPredecessorToBlock(NewSuccessors[i], Pred, BB); 803 804 // Now that the successors are updated, create the new Switch instruction. 805 SwitchInst *NewSI = SwitchInst::Create(CV, PredDefault, PredCases.size(), PTI); 806 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 807 NewSI->addCase(PredCases[i].first, PredCases[i].second); 808 809 Instruction *DeadCond = 0; 810 if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) 811 // If PTI is a branch, remember the condition. 812 DeadCond = dyn_cast<Instruction>(BI->getCondition()); 813 Pred->getInstList().erase(PTI); 814 815 // If the condition is dead now, remove the instruction tree. 816 if (DeadCond) ErasePossiblyDeadInstructionTree(DeadCond); 817 818 // Okay, last check. If BB is still a successor of PSI, then we must 819 // have an infinite loop case. If so, add an infinitely looping block 820 // to handle the case to preserve the behavior of the code. 821 BasicBlock *InfLoopBlock = 0; 822 for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i) 823 if (NewSI->getSuccessor(i) == BB) { 824 if (InfLoopBlock == 0) { 825 // Insert it at the end of the loop, because it's either code, 826 // or it won't matter if it's hot. :) 827 InfLoopBlock = BasicBlock::Create("infloop", BB->getParent()); 828 BranchInst::Create(InfLoopBlock, InfLoopBlock); 829 } 830 NewSI->setSuccessor(i, InfLoopBlock); 831 } 832 833 Changed = true; 834 } 835 } 836 return Changed; 837} 838 839/// HoistThenElseCodeToIf - Given a conditional branch that goes to BB1 and 840/// BB2, hoist any common code in the two blocks up into the branch block. The 841/// caller of this function guarantees that BI's block dominates BB1 and BB2. 842static bool HoistThenElseCodeToIf(BranchInst *BI) { 843 // This does very trivial matching, with limited scanning, to find identical 844 // instructions in the two blocks. In particular, we don't want to get into 845 // O(M*N) situations here where M and N are the sizes of BB1 and BB2. As 846 // such, we currently just scan for obviously identical instructions in an 847 // identical order. 848 BasicBlock *BB1 = BI->getSuccessor(0); // The true destination. 849 BasicBlock *BB2 = BI->getSuccessor(1); // The false destination 850 851 Instruction *I1 = BB1->begin(), *I2 = BB2->begin(); 852 if (I1->getOpcode() != I2->getOpcode() || isa<PHINode>(I1) || 853 isa<InvokeInst>(I1) || !I1->isIdenticalTo(I2)) 854 return false; 855 856 // If we get here, we can hoist at least one instruction. 857 BasicBlock *BIParent = BI->getParent(); 858 859 do { 860 // If we are hoisting the terminator instruction, don't move one (making a 861 // broken BB), instead clone it, and remove BI. 862 if (isa<TerminatorInst>(I1)) 863 goto HoistTerminator; 864 865 // For a normal instruction, we just move one to right before the branch, 866 // then replace all uses of the other with the first. Finally, we remove 867 // the now redundant second instruction. 868 BIParent->getInstList().splice(BI, BB1->getInstList(), I1); 869 if (!I2->use_empty()) 870 I2->replaceAllUsesWith(I1); 871 BB2->getInstList().erase(I2); 872 873 I1 = BB1->begin(); 874 I2 = BB2->begin(); 875 } while (I1->getOpcode() == I2->getOpcode() && I1->isIdenticalTo(I2)); 876 877 return true; 878 879HoistTerminator: 880 // Okay, it is safe to hoist the terminator. 881 Instruction *NT = I1->clone(); 882 BIParent->getInstList().insert(BI, NT); 883 if (NT->getType() != Type::VoidTy) { 884 I1->replaceAllUsesWith(NT); 885 I2->replaceAllUsesWith(NT); 886 NT->takeName(I1); 887 } 888 889 // Hoisting one of the terminators from our successor is a great thing. 890 // Unfortunately, the successors of the if/else blocks may have PHI nodes in 891 // them. If they do, all PHI entries for BB1/BB2 must agree for all PHI 892 // nodes, so we insert select instruction to compute the final result. 893 std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects; 894 for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 895 PHINode *PN; 896 for (BasicBlock::iterator BBI = SI->begin(); 897 (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 898 Value *BB1V = PN->getIncomingValueForBlock(BB1); 899 Value *BB2V = PN->getIncomingValueForBlock(BB2); 900 if (BB1V != BB2V) { 901 // These values do not agree. Insert a select instruction before NT 902 // that determines the right value. 903 SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)]; 904 if (SI == 0) 905 SI = SelectInst::Create(BI->getCondition(), BB1V, BB2V, 906 BB1V->getName()+"."+BB2V->getName(), NT); 907 // Make the PHI node use the select for all incoming values for BB1/BB2 908 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 909 if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2) 910 PN->setIncomingValue(i, SI); 911 } 912 } 913 } 914 915 // Update any PHI nodes in our new successors. 916 for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) 917 AddPredecessorToBlock(*SI, BIParent, BB1); 918 919 BI->eraseFromParent(); 920 return true; 921} 922 923/// BlockIsSimpleEnoughToThreadThrough - Return true if we can thread a branch 924/// across this block. 925static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) { 926 BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 927 unsigned Size = 0; 928 929 // If this basic block contains anything other than a PHI (which controls the 930 // branch) and branch itself, bail out. FIXME: improve this in the future. 931 for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI, ++Size) { 932 if (Size > 10) return false; // Don't clone large BB's. 933 934 // We can only support instructions that are do not define values that are 935 // live outside of the current basic block. 936 for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); 937 UI != E; ++UI) { 938 Instruction *U = cast<Instruction>(*UI); 939 if (U->getParent() != BB || isa<PHINode>(U)) return false; 940 } 941 942 // Looks ok, continue checking. 943 } 944 945 return true; 946} 947 948/// FoldCondBranchOnPHI - If we have a conditional branch on a PHI node value 949/// that is defined in the same block as the branch and if any PHI entries are 950/// constants, thread edges corresponding to that entry to be branches to their 951/// ultimate destination. 952static bool FoldCondBranchOnPHI(BranchInst *BI) { 953 BasicBlock *BB = BI->getParent(); 954 PHINode *PN = dyn_cast<PHINode>(BI->getCondition()); 955 // NOTE: we currently cannot transform this case if the PHI node is used 956 // outside of the block. 957 if (!PN || PN->getParent() != BB || !PN->hasOneUse()) 958 return false; 959 960 // Degenerate case of a single entry PHI. 961 if (PN->getNumIncomingValues() == 1) { 962 if (PN->getIncomingValue(0) != PN) 963 PN->replaceAllUsesWith(PN->getIncomingValue(0)); 964 else 965 PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 966 PN->eraseFromParent(); 967 return true; 968 } 969 970 // Now we know that this block has multiple preds and two succs. 971 if (!BlockIsSimpleEnoughToThreadThrough(BB)) return false; 972 973 // Okay, this is a simple enough basic block. See if any phi values are 974 // constants. 975 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 976 ConstantInt *CB; 977 if ((CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i))) && 978 CB->getType() == Type::Int1Ty) { 979 // Okay, we now know that all edges from PredBB should be revectored to 980 // branch to RealDest. 981 BasicBlock *PredBB = PN->getIncomingBlock(i); 982 BasicBlock *RealDest = BI->getSuccessor(!CB->getZExtValue()); 983 984 if (RealDest == BB) continue; // Skip self loops. 985 986 // The dest block might have PHI nodes, other predecessors and other 987 // difficult cases. Instead of being smart about this, just insert a new 988 // block that jumps to the destination block, effectively splitting 989 // the edge we are about to create. 990 BasicBlock *EdgeBB = BasicBlock::Create(RealDest->getName()+".critedge", 991 RealDest->getParent(), RealDest); 992 BranchInst::Create(RealDest, EdgeBB); 993 PHINode *PN; 994 for (BasicBlock::iterator BBI = RealDest->begin(); 995 (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 996 Value *V = PN->getIncomingValueForBlock(BB); 997 PN->addIncoming(V, EdgeBB); 998 } 999 1000 // BB may have instructions that are being threaded over. Clone these 1001 // instructions into EdgeBB. We know that there will be no uses of the 1002 // cloned instructions outside of EdgeBB. 1003 BasicBlock::iterator InsertPt = EdgeBB->begin(); 1004 std::map<Value*, Value*> TranslateMap; // Track translated values. 1005 for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { 1006 if (PHINode *PN = dyn_cast<PHINode>(BBI)) { 1007 TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB); 1008 } else { 1009 // Clone the instruction. 1010 Instruction *N = BBI->clone(); 1011 if (BBI->hasName()) N->setName(BBI->getName()+".c"); 1012 1013 // Update operands due to translation. 1014 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 1015 std::map<Value*, Value*>::iterator PI = 1016 TranslateMap.find(N->getOperand(i)); 1017 if (PI != TranslateMap.end()) 1018 N->setOperand(i, PI->second); 1019 } 1020 1021 // Check for trivial simplification. 1022 if (Constant *C = ConstantFoldInstruction(N)) { 1023 TranslateMap[BBI] = C; 1024 delete N; // Constant folded away, don't need actual inst 1025 } else { 1026 // Insert the new instruction into its new home. 1027 EdgeBB->getInstList().insert(InsertPt, N); 1028 if (!BBI->use_empty()) 1029 TranslateMap[BBI] = N; 1030 } 1031 } 1032 } 1033 1034 // Loop over all of the edges from PredBB to BB, changing them to branch 1035 // to EdgeBB instead. 1036 TerminatorInst *PredBBTI = PredBB->getTerminator(); 1037 for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i) 1038 if (PredBBTI->getSuccessor(i) == BB) { 1039 BB->removePredecessor(PredBB); 1040 PredBBTI->setSuccessor(i, EdgeBB); 1041 } 1042 1043 // Recurse, simplifying any other constants. 1044 return FoldCondBranchOnPHI(BI) | true; 1045 } 1046 } 1047 1048 return false; 1049} 1050 1051/// FoldTwoEntryPHINode - Given a BB that starts with the specified two-entry 1052/// PHI node, see if we can eliminate it. 1053static bool FoldTwoEntryPHINode(PHINode *PN) { 1054 // Ok, this is a two entry PHI node. Check to see if this is a simple "if 1055 // statement", which has a very simple dominance structure. Basically, we 1056 // are trying to find the condition that is being branched on, which 1057 // subsequently causes this merge to happen. We really want control 1058 // dependence information for this check, but simplifycfg can't keep it up 1059 // to date, and this catches most of the cases we care about anyway. 1060 // 1061 BasicBlock *BB = PN->getParent(); 1062 BasicBlock *IfTrue, *IfFalse; 1063 Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse); 1064 if (!IfCond) return false; 1065 1066 // Okay, we found that we can merge this two-entry phi node into a select. 1067 // Doing so would require us to fold *all* two entry phi nodes in this block. 1068 // At some point this becomes non-profitable (particularly if the target 1069 // doesn't support cmov's). Only do this transformation if there are two or 1070 // fewer PHI nodes in this block. 1071 unsigned NumPhis = 0; 1072 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++NumPhis, ++I) 1073 if (NumPhis > 2) 1074 return false; 1075 1076 DOUT << "FOUND IF CONDITION! " << *IfCond << " T: " 1077 << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"; 1078 1079 // Loop over the PHI's seeing if we can promote them all to select 1080 // instructions. While we are at it, keep track of the instructions 1081 // that need to be moved to the dominating block. 1082 std::set<Instruction*> AggressiveInsts; 1083 1084 BasicBlock::iterator AfterPHIIt = BB->begin(); 1085 while (isa<PHINode>(AfterPHIIt)) { 1086 PHINode *PN = cast<PHINode>(AfterPHIIt++); 1087 if (PN->getIncomingValue(0) == PN->getIncomingValue(1)) { 1088 if (PN->getIncomingValue(0) != PN) 1089 PN->replaceAllUsesWith(PN->getIncomingValue(0)); 1090 else 1091 PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 1092 } else if (!DominatesMergePoint(PN->getIncomingValue(0), BB, 1093 &AggressiveInsts) || 1094 !DominatesMergePoint(PN->getIncomingValue(1), BB, 1095 &AggressiveInsts)) { 1096 return false; 1097 } 1098 } 1099 1100 // If we all PHI nodes are promotable, check to make sure that all 1101 // instructions in the predecessor blocks can be promoted as well. If 1102 // not, we won't be able to get rid of the control flow, so it's not 1103 // worth promoting to select instructions. 1104 BasicBlock *DomBlock = 0, *IfBlock1 = 0, *IfBlock2 = 0; 1105 PN = cast<PHINode>(BB->begin()); 1106 BasicBlock *Pred = PN->getIncomingBlock(0); 1107 if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 1108 IfBlock1 = Pred; 1109 DomBlock = *pred_begin(Pred); 1110 for (BasicBlock::iterator I = Pred->begin(); 1111 !isa<TerminatorInst>(I); ++I) 1112 if (!AggressiveInsts.count(I)) { 1113 // This is not an aggressive instruction that we can promote. 1114 // Because of this, we won't be able to get rid of the control 1115 // flow, so the xform is not worth it. 1116 return false; 1117 } 1118 } 1119 1120 Pred = PN->getIncomingBlock(1); 1121 if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 1122 IfBlock2 = Pred; 1123 DomBlock = *pred_begin(Pred); 1124 for (BasicBlock::iterator I = Pred->begin(); 1125 !isa<TerminatorInst>(I); ++I) 1126 if (!AggressiveInsts.count(I)) { 1127 // This is not an aggressive instruction that we can promote. 1128 // Because of this, we won't be able to get rid of the control 1129 // flow, so the xform is not worth it. 1130 return false; 1131 } 1132 } 1133 1134 // If we can still promote the PHI nodes after this gauntlet of tests, 1135 // do all of the PHI's now. 1136 1137 // Move all 'aggressive' instructions, which are defined in the 1138 // conditional parts of the if's up to the dominating block. 1139 if (IfBlock1) { 1140 DomBlock->getInstList().splice(DomBlock->getTerminator(), 1141 IfBlock1->getInstList(), 1142 IfBlock1->begin(), 1143 IfBlock1->getTerminator()); 1144 } 1145 if (IfBlock2) { 1146 DomBlock->getInstList().splice(DomBlock->getTerminator(), 1147 IfBlock2->getInstList(), 1148 IfBlock2->begin(), 1149 IfBlock2->getTerminator()); 1150 } 1151 1152 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 1153 // Change the PHI node into a select instruction. 1154 Value *TrueVal = 1155 PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); 1156 Value *FalseVal = 1157 PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); 1158 1159 Value *NV = SelectInst::Create(IfCond, TrueVal, FalseVal, "", AfterPHIIt); 1160 PN->replaceAllUsesWith(NV); 1161 NV->takeName(PN); 1162 1163 BB->getInstList().erase(PN); 1164 } 1165 return true; 1166} 1167 1168/// SimplifyCondBranchToTwoReturns - If we found a conditional branch that goes 1169/// to two returning blocks, try to merge them together into one return, 1170/// introducing a select if the return values disagree. 1171static bool SimplifyCondBranchToTwoReturns(BranchInst *BI) { 1172 assert(BI->isConditional() && "Must be a conditional branch"); 1173 BasicBlock *TrueSucc = BI->getSuccessor(0); 1174 BasicBlock *FalseSucc = BI->getSuccessor(1); 1175 ReturnInst *TrueRet = cast<ReturnInst>(TrueSucc->getTerminator()); 1176 ReturnInst *FalseRet = cast<ReturnInst>(FalseSucc->getTerminator()); 1177 1178 // Check to ensure both blocks are empty (just a return) or optionally empty 1179 // with PHI nodes. If there are other instructions, merging would cause extra 1180 // computation on one path or the other. 1181 BasicBlock::iterator BBI = TrueRet; 1182 if (BBI != TrueSucc->begin() && !isa<PHINode>(--BBI)) 1183 return false; // Not empty with optional phi nodes. 1184 BBI = FalseRet; 1185 if (BBI != FalseSucc->begin() && !isa<PHINode>(--BBI)) 1186 return false; // Not empty with optional phi nodes. 1187 1188 // Okay, we found a branch that is going to two return nodes. If 1189 // there is no return value for this function, just change the 1190 // branch into a return. 1191 if (FalseRet->getNumOperands() == 0) { 1192 TrueSucc->removePredecessor(BI->getParent()); 1193 FalseSucc->removePredecessor(BI->getParent()); 1194 ReturnInst::Create(0, BI); 1195 BI->eraseFromParent(); 1196 return true; 1197 } 1198 1199 // Otherwise, build up the result values for the new return. 1200 SmallVector<Value*, 4> TrueResult; 1201 SmallVector<Value*, 4> FalseResult; 1202 1203 for (unsigned i = 0, e = TrueRet->getNumOperands(); i != e; ++i) { 1204 // Otherwise, figure out what the true and false return values are 1205 // so we can insert a new select instruction. 1206 Value *TrueValue = TrueRet->getOperand(i); 1207 Value *FalseValue = FalseRet->getOperand(i); 1208 1209 // Unwrap any PHI nodes in the return blocks. 1210 if (PHINode *TVPN = dyn_cast<PHINode>(TrueValue)) 1211 if (TVPN->getParent() == TrueSucc) 1212 TrueValue = TVPN->getIncomingValueForBlock(BI->getParent()); 1213 if (PHINode *FVPN = dyn_cast<PHINode>(FalseValue)) 1214 if (FVPN->getParent() == FalseSucc) 1215 FalseValue = FVPN->getIncomingValueForBlock(BI->getParent()); 1216 1217 // In order for this transformation to be safe, we must be able to 1218 // unconditionally execute both operands to the return. This is 1219 // normally the case, but we could have a potentially-trapping 1220 // constant expression that prevents this transformation from being 1221 // safe. 1222 if (ConstantExpr *TCV = dyn_cast<ConstantExpr>(TrueValue)) 1223 if (TCV->canTrap()) 1224 return false; 1225 if (ConstantExpr *FCV = dyn_cast<ConstantExpr>(FalseValue)) 1226 if (FCV->canTrap()) 1227 return false; 1228 1229 TrueResult.push_back(TrueValue); 1230 FalseResult.push_back(FalseValue); 1231 } 1232 1233 // Okay, we collected all the mapped values and checked them for sanity, and 1234 // defined to really do this transformation. First, update the CFG. 1235 TrueSucc->removePredecessor(BI->getParent()); 1236 FalseSucc->removePredecessor(BI->getParent()); 1237 1238 // Insert select instructions where needed. 1239 Value *BrCond = BI->getCondition(); 1240 for (unsigned i = 0, e = TrueRet->getNumOperands(); i != e; ++i) { 1241 // Insert a select if the results differ. 1242 if (TrueResult[i] == FalseResult[i] || isa<UndefValue>(FalseResult[i])) 1243 continue; 1244 if (isa<UndefValue>(TrueResult[i])) { 1245 TrueResult[i] = FalseResult[i]; 1246 continue; 1247 } 1248 1249 TrueResult[i] = SelectInst::Create(BrCond, TrueResult[i], 1250 FalseResult[i], "retval", BI); 1251 } 1252 1253 Value *RI = ReturnInst::Create(&TrueResult[0], TrueResult.size(), BI); 1254 1255 DOUT << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:" 1256 << "\n " << *BI << "NewRet = " << *RI 1257 << "TRUEBLOCK: " << *TrueSucc << "FALSEBLOCK: "<< *FalseSucc; 1258 1259 BI->eraseFromParent(); 1260 1261 if (Instruction *BrCondI = dyn_cast<Instruction>(BrCond)) 1262 ErasePossiblyDeadInstructionTree(BrCondI); 1263 return true; 1264} 1265 1266 1267namespace { 1268 /// ConstantIntOrdering - This class implements a stable ordering of constant 1269 /// integers that does not depend on their address. This is important for 1270 /// applications that sort ConstantInt's to ensure uniqueness. 1271 struct ConstantIntOrdering { 1272 bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { 1273 return LHS->getValue().ult(RHS->getValue()); 1274 } 1275 }; 1276} 1277 1278// SimplifyCFG - This function is used to do simplification of a CFG. For 1279// example, it adjusts branches to branches to eliminate the extra hop, it 1280// eliminates unreachable basic blocks, and does other "peephole" optimization 1281// of the CFG. It returns true if a modification was made. 1282// 1283// WARNING: The entry node of a function may not be simplified. 1284// 1285bool llvm::SimplifyCFG(BasicBlock *BB) { 1286 bool Changed = false; 1287 Function *M = BB->getParent(); 1288 1289 assert(BB && BB->getParent() && "Block not embedded in function!"); 1290 assert(BB->getTerminator() && "Degenerate basic block encountered!"); 1291 assert(&BB->getParent()->getEntryBlock() != BB && 1292 "Can't Simplify entry block!"); 1293 1294 // Remove basic blocks that have no predecessors... which are unreachable. 1295 if ((pred_begin(BB) == pred_end(BB)) || 1296 (*pred_begin(BB) == BB && ++pred_begin(BB) == pred_end(BB))) { 1297 DOUT << "Removing BB: \n" << *BB; 1298 1299 // Loop through all of our successors and make sure they know that one 1300 // of their predecessors is going away. 1301 for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 1302 SI->removePredecessor(BB); 1303 1304 while (!BB->empty()) { 1305 Instruction &I = BB->back(); 1306 // If this instruction is used, replace uses with an arbitrary 1307 // value. Because control flow can't get here, we don't care 1308 // what we replace the value with. Note that since this block is 1309 // unreachable, and all values contained within it must dominate their 1310 // uses, that all uses will eventually be removed. 1311 if (!I.use_empty()) 1312 // Make all users of this instruction use undef instead 1313 I.replaceAllUsesWith(UndefValue::get(I.getType())); 1314 1315 // Remove the instruction from the basic block 1316 BB->getInstList().pop_back(); 1317 } 1318 M->getBasicBlockList().erase(BB); 1319 return true; 1320 } 1321 1322 // Check to see if we can constant propagate this terminator instruction 1323 // away... 1324 Changed |= ConstantFoldTerminator(BB); 1325 1326 // If there is a trivial two-entry PHI node in this basic block, and we can 1327 // eliminate it, do so now. 1328 if (PHINode *PN = dyn_cast<PHINode>(BB->begin())) 1329 if (PN->getNumIncomingValues() == 2) 1330 Changed |= FoldTwoEntryPHINode(PN); 1331 1332 // If this is a returning block with only PHI nodes in it, fold the return 1333 // instruction into any unconditional branch predecessors. 1334 // 1335 // If any predecessor is a conditional branch that just selects among 1336 // different return values, fold the replace the branch/return with a select 1337 // and return. 1338 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 1339 BasicBlock::iterator BBI = BB->getTerminator(); 1340 if (BBI == BB->begin() || isa<PHINode>(--BBI)) { 1341 // Find predecessors that end with branches. 1342 SmallVector<BasicBlock*, 8> UncondBranchPreds; 1343 SmallVector<BranchInst*, 8> CondBranchPreds; 1344 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 1345 TerminatorInst *PTI = (*PI)->getTerminator(); 1346 if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) { 1347 if (BI->isUnconditional()) 1348 UncondBranchPreds.push_back(*PI); 1349 else 1350 CondBranchPreds.push_back(BI); 1351 } 1352 } 1353 1354 // If we found some, do the transformation! 1355 if (!UncondBranchPreds.empty()) { 1356 while (!UncondBranchPreds.empty()) { 1357 BasicBlock *Pred = UncondBranchPreds.back(); 1358 DOUT << "FOLDING: " << *BB 1359 << "INTO UNCOND BRANCH PRED: " << *Pred; 1360 UncondBranchPreds.pop_back(); 1361 Instruction *UncondBranch = Pred->getTerminator(); 1362 // Clone the return and add it to the end of the predecessor. 1363 Instruction *NewRet = RI->clone(); 1364 Pred->getInstList().push_back(NewRet); 1365 1366 // If the return instruction returns a value, and if the value was a 1367 // PHI node in "BB", propagate the right value into the return. 1368 if (NewRet->getNumOperands() == 1) 1369 if (PHINode *PN = dyn_cast<PHINode>(NewRet->getOperand(0))) 1370 if (PN->getParent() == BB) 1371 NewRet->setOperand(0, PN->getIncomingValueForBlock(Pred)); 1372 // Update any PHI nodes in the returning block to realize that we no 1373 // longer branch to them. 1374 BB->removePredecessor(Pred); 1375 Pred->getInstList().erase(UncondBranch); 1376 } 1377 1378 // If we eliminated all predecessors of the block, delete the block now. 1379 if (pred_begin(BB) == pred_end(BB)) 1380 // We know there are no successors, so just nuke the block. 1381 M->getBasicBlockList().erase(BB); 1382 1383 return true; 1384 } 1385 1386 // Check out all of the conditional branches going to this return 1387 // instruction. If any of them just select between returns, change the 1388 // branch itself into a select/return pair. 1389 while (!CondBranchPreds.empty()) { 1390 BranchInst *BI = CondBranchPreds.back(); 1391 CondBranchPreds.pop_back(); 1392 1393 // Check to see if the non-BB successor is also a return block. 1394 if (isa<ReturnInst>(BI->getSuccessor(0)->getTerminator()) && 1395 isa<ReturnInst>(BI->getSuccessor(1)->getTerminator()) && 1396 SimplifyCondBranchToTwoReturns(BI)) 1397 return true; 1398 } 1399 } 1400 } else if (isa<UnwindInst>(BB->begin())) { 1401 // Check to see if the first instruction in this block is just an unwind. 1402 // If so, replace any invoke instructions which use this as an exception 1403 // destination with call instructions, and any unconditional branch 1404 // predecessor with an unwind. 1405 // 1406 SmallVector<BasicBlock*, 8> Preds(pred_begin(BB), pred_end(BB)); 1407 while (!Preds.empty()) { 1408 BasicBlock *Pred = Preds.back(); 1409 if (BranchInst *BI = dyn_cast<BranchInst>(Pred->getTerminator())) { 1410 if (BI->isUnconditional()) { 1411 Pred->getInstList().pop_back(); // nuke uncond branch 1412 new UnwindInst(Pred); // Use unwind. 1413 Changed = true; 1414 } 1415 } else if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator())) 1416 if (II->getUnwindDest() == BB) { 1417 // Insert a new branch instruction before the invoke, because this 1418 // is now a fall through... 1419 BranchInst *BI = BranchInst::Create(II->getNormalDest(), II); 1420 Pred->getInstList().remove(II); // Take out of symbol table 1421 1422 // Insert the call now... 1423 SmallVector<Value*,8> Args(II->op_begin()+3, II->op_end()); 1424 CallInst *CI = CallInst::Create(II->getCalledValue(), 1425 Args.begin(), Args.end(), II->getName(), BI); 1426 CI->setCallingConv(II->getCallingConv()); 1427 CI->setParamAttrs(II->getParamAttrs()); 1428 // If the invoke produced a value, the Call now does instead 1429 II->replaceAllUsesWith(CI); 1430 delete II; 1431 Changed = true; 1432 } 1433 1434 Preds.pop_back(); 1435 } 1436 1437 // If this block is now dead, remove it. 1438 if (pred_begin(BB) == pred_end(BB)) { 1439 // We know there are no successors, so just nuke the block. 1440 M->getBasicBlockList().erase(BB); 1441 return true; 1442 } 1443 1444 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { 1445 if (isValueEqualityComparison(SI)) { 1446 // If we only have one predecessor, and if it is a branch on this value, 1447 // see if that predecessor totally determines the outcome of this switch. 1448 if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 1449 if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred)) 1450 return SimplifyCFG(BB) || 1; 1451 1452 // If the block only contains the switch, see if we can fold the block 1453 // away into any preds. 1454 if (SI == &BB->front()) 1455 if (FoldValueComparisonIntoPredecessors(SI)) 1456 return SimplifyCFG(BB) || 1; 1457 } 1458 } else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 1459 if (BI->isUnconditional()) { 1460 BasicBlock::iterator BBI = BB->begin(); // Skip over phi nodes... 1461 while (isa<PHINode>(*BBI)) ++BBI; 1462 1463 BasicBlock *Succ = BI->getSuccessor(0); 1464 if (BBI->isTerminator() && // Terminator is the only non-phi instruction! 1465 Succ != BB) // Don't hurt infinite loops! 1466 if (TryToSimplifyUncondBranchFromEmptyBlock(BB, Succ)) 1467 return 1; 1468 1469 } else { // Conditional branch 1470 if (isValueEqualityComparison(BI)) { 1471 // If we only have one predecessor, and if it is a branch on this value, 1472 // see if that predecessor totally determines the outcome of this 1473 // switch. 1474 if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 1475 if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred)) 1476 return SimplifyCFG(BB) || 1; 1477 1478 // This block must be empty, except for the setcond inst, if it exists. 1479 BasicBlock::iterator I = BB->begin(); 1480 if (&*I == BI || 1481 (&*I == cast<Instruction>(BI->getCondition()) && 1482 &*++I == BI)) 1483 if (FoldValueComparisonIntoPredecessors(BI)) 1484 return SimplifyCFG(BB) | true; 1485 } 1486 1487 // If this is a branch on a phi node in the current block, thread control 1488 // through this block if any PHI node entries are constants. 1489 if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition())) 1490 if (PN->getParent() == BI->getParent()) 1491 if (FoldCondBranchOnPHI(BI)) 1492 return SimplifyCFG(BB) | true; 1493 1494 // If this basic block is ONLY a setcc and a branch, and if a predecessor 1495 // branches to us and one of our successors, fold the setcc into the 1496 // predecessor and use logical operations to pick the right destination. 1497 BasicBlock *TrueDest = BI->getSuccessor(0); 1498 BasicBlock *FalseDest = BI->getSuccessor(1); 1499 if (Instruction *Cond = dyn_cast<Instruction>(BI->getCondition())) { 1500 BasicBlock::iterator CondIt = Cond; 1501 if ((isa<CmpInst>(Cond) || isa<BinaryOperator>(Cond)) && 1502 Cond->getParent() == BB && &BB->front() == Cond && 1503 &*++CondIt == BI && Cond->hasOneUse() && 1504 TrueDest != BB && FalseDest != BB) 1505 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI!=E; ++PI) 1506 if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 1507 if (PBI->isConditional() && SafeToMergeTerminators(BI, PBI)) { 1508 BasicBlock *PredBlock = *PI; 1509 if (PBI->getSuccessor(0) == FalseDest || 1510 PBI->getSuccessor(1) == TrueDest) { 1511 // Invert the predecessors condition test (xor it with true), 1512 // which allows us to write this code once. 1513 Value *NewCond = 1514 BinaryOperator::createNot(PBI->getCondition(), 1515 PBI->getCondition()->getName()+".not", PBI); 1516 PBI->setCondition(NewCond); 1517 BasicBlock *OldTrue = PBI->getSuccessor(0); 1518 BasicBlock *OldFalse = PBI->getSuccessor(1); 1519 PBI->setSuccessor(0, OldFalse); 1520 PBI->setSuccessor(1, OldTrue); 1521 } 1522 1523 if ((PBI->getSuccessor(0) == TrueDest && FalseDest != BB) || 1524 (PBI->getSuccessor(1) == FalseDest && TrueDest != BB)) { 1525 // Clone Cond into the predecessor basic block, and or/and the 1526 // two conditions together. 1527 Instruction *New = Cond->clone(); 1528 PredBlock->getInstList().insert(PBI, New); 1529 New->takeName(Cond); 1530 Cond->setName(New->getName()+".old"); 1531 Instruction::BinaryOps Opcode = 1532 PBI->getSuccessor(0) == TrueDest ? 1533 Instruction::Or : Instruction::And; 1534 Value *NewCond = 1535 BinaryOperator::create(Opcode, PBI->getCondition(), 1536 New, "bothcond", PBI); 1537 PBI->setCondition(NewCond); 1538 if (PBI->getSuccessor(0) == BB) { 1539 AddPredecessorToBlock(TrueDest, PredBlock, BB); 1540 PBI->setSuccessor(0, TrueDest); 1541 } 1542 if (PBI->getSuccessor(1) == BB) { 1543 AddPredecessorToBlock(FalseDest, PredBlock, BB); 1544 PBI->setSuccessor(1, FalseDest); 1545 } 1546 return SimplifyCFG(BB) | 1; 1547 } 1548 } 1549 } 1550 1551 // Scan predessor blocks for conditional branches. 1552 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 1553 if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 1554 if (PBI != BI && PBI->isConditional()) { 1555 1556 // If this block ends with a branch instruction, and if there is a 1557 // predecessor that ends on a branch of the same condition, make 1558 // this conditional branch redundant. 1559 if (PBI->getCondition() == BI->getCondition() && 1560 PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 1561 // Okay, the outcome of this conditional branch is statically 1562 // knowable. If this block had a single pred, handle specially. 1563 if (BB->getSinglePredecessor()) { 1564 // Turn this into a branch on constant. 1565 bool CondIsTrue = PBI->getSuccessor(0) == BB; 1566 BI->setCondition(ConstantInt::get(Type::Int1Ty, CondIsTrue)); 1567 return SimplifyCFG(BB); // Nuke the branch on constant. 1568 } 1569 1570 // Otherwise, if there are multiple predecessors, insert a PHI 1571 // that merges in the constant and simplify the block result. 1572 if (BlockIsSimpleEnoughToThreadThrough(BB)) { 1573 PHINode *NewPN = PHINode::Create(Type::Int1Ty, 1574 BI->getCondition()->getName()+".pr", 1575 BB->begin()); 1576 for (PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 1577 if ((PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) && 1578 PBI != BI && PBI->isConditional() && 1579 PBI->getCondition() == BI->getCondition() && 1580 PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 1581 bool CondIsTrue = PBI->getSuccessor(0) == BB; 1582 NewPN->addIncoming(ConstantInt::get(Type::Int1Ty, 1583 CondIsTrue), *PI); 1584 } else { 1585 NewPN->addIncoming(BI->getCondition(), *PI); 1586 } 1587 1588 BI->setCondition(NewPN); 1589 // This will thread the branch. 1590 return SimplifyCFG(BB) | true; 1591 } 1592 } 1593 1594 // If this is a conditional branch in an empty block, and if any 1595 // predecessors is a conditional branch to one of our destinations, 1596 // fold the conditions into logical ops and one cond br. 1597 if (&BB->front() == BI) { 1598 int PBIOp, BIOp; 1599 if (PBI->getSuccessor(0) == BI->getSuccessor(0)) { 1600 PBIOp = BIOp = 0; 1601 } else if (PBI->getSuccessor(0) == BI->getSuccessor(1)) { 1602 PBIOp = 0; BIOp = 1; 1603 } else if (PBI->getSuccessor(1) == BI->getSuccessor(0)) { 1604 PBIOp = 1; BIOp = 0; 1605 } else if (PBI->getSuccessor(1) == BI->getSuccessor(1)) { 1606 PBIOp = BIOp = 1; 1607 } else { 1608 PBIOp = BIOp = -1; 1609 } 1610 1611 // Check to make sure that the other destination of this branch 1612 // isn't BB itself. If so, this is an infinite loop that will 1613 // keep getting unwound. 1614 if (PBIOp != -1 && PBI->getSuccessor(PBIOp) == BB) 1615 PBIOp = BIOp = -1; 1616 1617 // Do not perform this transformation if it would require 1618 // insertion of a large number of select instructions. For targets 1619 // without predication/cmovs, this is a big pessimization. 1620 if (PBIOp != -1) { 1621 BasicBlock *CommonDest = PBI->getSuccessor(PBIOp); 1622 1623 unsigned NumPhis = 0; 1624 for (BasicBlock::iterator II = CommonDest->begin(); 1625 isa<PHINode>(II); ++II, ++NumPhis) { 1626 if (NumPhis > 2) { 1627 // Disable this xform. 1628 PBIOp = -1; 1629 break; 1630 } 1631 } 1632 } 1633 1634 // Finally, if everything is ok, fold the branches to logical ops. 1635 if (PBIOp != -1) { 1636 BasicBlock *CommonDest = PBI->getSuccessor(PBIOp); 1637 BasicBlock *OtherDest = BI->getSuccessor(BIOp ^ 1); 1638 1639 // If OtherDest *is* BB, then this is a basic block with just 1640 // a conditional branch in it, where one edge (OtherDesg) goes 1641 // back to the block. We know that the program doesn't get 1642 // stuck in the infinite loop, so the condition must be such 1643 // that OtherDest isn't branched through. Forward to CommonDest, 1644 // and avoid an infinite loop at optimizer time. 1645 if (OtherDest == BB) 1646 OtherDest = CommonDest; 1647 1648 DOUT << "FOLDING BRs:" << *PBI->getParent() 1649 << "AND: " << *BI->getParent(); 1650 1651 // BI may have other predecessors. Because of this, we leave 1652 // it alone, but modify PBI. 1653 1654 // Make sure we get to CommonDest on True&True directions. 1655 Value *PBICond = PBI->getCondition(); 1656 if (PBIOp) 1657 PBICond = BinaryOperator::createNot(PBICond, 1658 PBICond->getName()+".not", 1659 PBI); 1660 Value *BICond = BI->getCondition(); 1661 if (BIOp) 1662 BICond = BinaryOperator::createNot(BICond, 1663 BICond->getName()+".not", 1664 PBI); 1665 // Merge the conditions. 1666 Value *Cond = 1667 BinaryOperator::createOr(PBICond, BICond, "brmerge", PBI); 1668 1669 // Modify PBI to branch on the new condition to the new dests. 1670 PBI->setCondition(Cond); 1671 PBI->setSuccessor(0, CommonDest); 1672 PBI->setSuccessor(1, OtherDest); 1673 1674 // OtherDest may have phi nodes. If so, add an entry from PBI's 1675 // block that are identical to the entries for BI's block. 1676 PHINode *PN; 1677 for (BasicBlock::iterator II = OtherDest->begin(); 1678 (PN = dyn_cast<PHINode>(II)); ++II) { 1679 Value *V = PN->getIncomingValueForBlock(BB); 1680 PN->addIncoming(V, PBI->getParent()); 1681 } 1682 1683 // We know that the CommonDest already had an edge from PBI to 1684 // it. If it has PHIs though, the PHIs may have different 1685 // entries for BB and PBI's BB. If so, insert a select to make 1686 // them agree. 1687 for (BasicBlock::iterator II = CommonDest->begin(); 1688 (PN = dyn_cast<PHINode>(II)); ++II) { 1689 Value * BIV = PN->getIncomingValueForBlock(BB); 1690 unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent()); 1691 Value *PBIV = PN->getIncomingValue(PBBIdx); 1692 if (BIV != PBIV) { 1693 // Insert a select in PBI to pick the right value. 1694 Value *NV = SelectInst::Create(PBICond, PBIV, BIV, 1695 PBIV->getName()+".mux", PBI); 1696 PN->setIncomingValue(PBBIdx, NV); 1697 } 1698 } 1699 1700 DOUT << "INTO: " << *PBI->getParent(); 1701 1702 // This basic block is probably dead. We know it has at least 1703 // one fewer predecessor. 1704 return SimplifyCFG(BB) | true; 1705 } 1706 } 1707 } 1708 } 1709 } else if (isa<UnreachableInst>(BB->getTerminator())) { 1710 // If there are any instructions immediately before the unreachable that can 1711 // be removed, do so. 1712 Instruction *Unreachable = BB->getTerminator(); 1713 while (Unreachable != BB->begin()) { 1714 BasicBlock::iterator BBI = Unreachable; 1715 --BBI; 1716 if (isa<CallInst>(BBI)) break; 1717 // Delete this instruction 1718 BB->getInstList().erase(BBI); 1719 Changed = true; 1720 } 1721 1722 // If the unreachable instruction is the first in the block, take a gander 1723 // at all of the predecessors of this instruction, and simplify them. 1724 if (&BB->front() == Unreachable) { 1725 SmallVector<BasicBlock*, 8> Preds(pred_begin(BB), pred_end(BB)); 1726 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 1727 TerminatorInst *TI = Preds[i]->getTerminator(); 1728 1729 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 1730 if (BI->isUnconditional()) { 1731 if (BI->getSuccessor(0) == BB) { 1732 new UnreachableInst(TI); 1733 TI->eraseFromParent(); 1734 Changed = true; 1735 } 1736 } else { 1737 if (BI->getSuccessor(0) == BB) { 1738 BranchInst::Create(BI->getSuccessor(1), BI); 1739 BI->eraseFromParent(); 1740 } else if (BI->getSuccessor(1) == BB) { 1741 BranchInst::Create(BI->getSuccessor(0), BI); 1742 BI->eraseFromParent(); 1743 Changed = true; 1744 } 1745 } 1746 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 1747 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1748 if (SI->getSuccessor(i) == BB) { 1749 BB->removePredecessor(SI->getParent()); 1750 SI->removeCase(i); 1751 --i; --e; 1752 Changed = true; 1753 } 1754 // If the default value is unreachable, figure out the most popular 1755 // destination and make it the default. 1756 if (SI->getSuccessor(0) == BB) { 1757 std::map<BasicBlock*, unsigned> Popularity; 1758 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1759 Popularity[SI->getSuccessor(i)]++; 1760 1761 // Find the most popular block. 1762 unsigned MaxPop = 0; 1763 BasicBlock *MaxBlock = 0; 1764 for (std::map<BasicBlock*, unsigned>::iterator 1765 I = Popularity.begin(), E = Popularity.end(); I != E; ++I) { 1766 if (I->second > MaxPop) { 1767 MaxPop = I->second; 1768 MaxBlock = I->first; 1769 } 1770 } 1771 if (MaxBlock) { 1772 // Make this the new default, allowing us to delete any explicit 1773 // edges to it. 1774 SI->setSuccessor(0, MaxBlock); 1775 Changed = true; 1776 1777 // If MaxBlock has phinodes in it, remove MaxPop-1 entries from 1778 // it. 1779 if (isa<PHINode>(MaxBlock->begin())) 1780 for (unsigned i = 0; i != MaxPop-1; ++i) 1781 MaxBlock->removePredecessor(SI->getParent()); 1782 1783 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1784 if (SI->getSuccessor(i) == MaxBlock) { 1785 SI->removeCase(i); 1786 --i; --e; 1787 } 1788 } 1789 } 1790 } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) { 1791 if (II->getUnwindDest() == BB) { 1792 // Convert the invoke to a call instruction. This would be a good 1793 // place to note that the call does not throw though. 1794 BranchInst *BI = BranchInst::Create(II->getNormalDest(), II); 1795 II->removeFromParent(); // Take out of symbol table 1796 1797 // Insert the call now... 1798 SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end()); 1799 CallInst *CI = CallInst::Create(II->getCalledValue(), 1800 Args.begin(), Args.end(), 1801 II->getName(), BI); 1802 CI->setCallingConv(II->getCallingConv()); 1803 CI->setParamAttrs(II->getParamAttrs()); 1804 // If the invoke produced a value, the Call does now instead. 1805 II->replaceAllUsesWith(CI); 1806 delete II; 1807 Changed = true; 1808 } 1809 } 1810 } 1811 1812 // If this block is now dead, remove it. 1813 if (pred_begin(BB) == pred_end(BB)) { 1814 // We know there are no successors, so just nuke the block. 1815 M->getBasicBlockList().erase(BB); 1816 return true; 1817 } 1818 } 1819 } 1820 1821 // Merge basic blocks into their predecessor if there is only one distinct 1822 // pred, and if there is only one distinct successor of the predecessor, and 1823 // if there are no PHI nodes. 1824 // 1825 pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 1826 BasicBlock *OnlyPred = *PI++; 1827 for (; PI != PE; ++PI) // Search all predecessors, see if they are all same 1828 if (*PI != OnlyPred) { 1829 OnlyPred = 0; // There are multiple different predecessors... 1830 break; 1831 } 1832 1833 BasicBlock *OnlySucc = 0; 1834 if (OnlyPred && OnlyPred != BB && // Don't break self loops 1835 OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) { 1836 // Check to see if there is only one distinct successor... 1837 succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred)); 1838 OnlySucc = BB; 1839 for (; SI != SE; ++SI) 1840 if (*SI != OnlySucc) { 1841 OnlySucc = 0; // There are multiple distinct successors! 1842 break; 1843 } 1844 } 1845 1846 if (OnlySucc) { 1847 DOUT << "Merging: " << *BB << "into: " << *OnlyPred; 1848 1849 // Resolve any PHI nodes at the start of the block. They are all 1850 // guaranteed to have exactly one entry if they exist, unless there are 1851 // multiple duplicate (but guaranteed to be equal) entries for the 1852 // incoming edges. This occurs when there are multiple edges from 1853 // OnlyPred to OnlySucc. 1854 // 1855 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 1856 PN->replaceAllUsesWith(PN->getIncomingValue(0)); 1857 BB->getInstList().pop_front(); // Delete the phi node. 1858 } 1859 1860 // Delete the unconditional branch from the predecessor. 1861 OnlyPred->getInstList().pop_back(); 1862 1863 // Move all definitions in the successor to the predecessor. 1864 OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); 1865 1866 // Make all PHI nodes that referred to BB now refer to Pred as their 1867 // source. 1868 BB->replaceAllUsesWith(OnlyPred); 1869 1870 // Inherit predecessors name if it exists. 1871 if (!OnlyPred->hasName()) 1872 OnlyPred->takeName(BB); 1873 1874 // Erase basic block from the function. 1875 M->getBasicBlockList().erase(BB); 1876 1877 return true; 1878 } 1879 1880 // Otherwise, if this block only has a single predecessor, and if that block 1881 // is a conditional branch, see if we can hoist any code from this block up 1882 // into our predecessor. 1883 if (OnlyPred) 1884 if (BranchInst *BI = dyn_cast<BranchInst>(OnlyPred->getTerminator())) 1885 if (BI->isConditional()) { 1886 // Get the other block. 1887 BasicBlock *OtherBB = BI->getSuccessor(BI->getSuccessor(0) == BB); 1888 PI = pred_begin(OtherBB); 1889 ++PI; 1890 if (PI == pred_end(OtherBB)) { 1891 // We have a conditional branch to two blocks that are only reachable 1892 // from the condbr. We know that the condbr dominates the two blocks, 1893 // so see if there is any identical code in the "then" and "else" 1894 // blocks. If so, we can hoist it up to the branching block. 1895 Changed |= HoistThenElseCodeToIf(BI); 1896 } 1897 } 1898 1899 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 1900 if (BranchInst *BI = dyn_cast<BranchInst>((*PI)->getTerminator())) 1901 // Change br (X == 0 | X == 1), T, F into a switch instruction. 1902 if (BI->isConditional() && isa<Instruction>(BI->getCondition())) { 1903 Instruction *Cond = cast<Instruction>(BI->getCondition()); 1904 // If this is a bunch of seteq's or'd together, or if it's a bunch of 1905 // 'setne's and'ed together, collect them. 1906 Value *CompVal = 0; 1907 std::vector<ConstantInt*> Values; 1908 bool TrueWhenEqual = GatherValueComparisons(Cond, CompVal, Values); 1909 if (CompVal && CompVal->getType()->isInteger()) { 1910 // There might be duplicate constants in the list, which the switch 1911 // instruction can't handle, remove them now. 1912 std::sort(Values.begin(), Values.end(), ConstantIntOrdering()); 1913 Values.erase(std::unique(Values.begin(), Values.end()), Values.end()); 1914 1915 // Figure out which block is which destination. 1916 BasicBlock *DefaultBB = BI->getSuccessor(1); 1917 BasicBlock *EdgeBB = BI->getSuccessor(0); 1918 if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB); 1919 1920 // Create the new switch instruction now. 1921 SwitchInst *New = SwitchInst::Create(CompVal, DefaultBB,Values.size(),BI); 1922 1923 // Add all of the 'cases' to the switch instruction. 1924 for (unsigned i = 0, e = Values.size(); i != e; ++i) 1925 New->addCase(Values[i], EdgeBB); 1926 1927 // We added edges from PI to the EdgeBB. As such, if there were any 1928 // PHI nodes in EdgeBB, they need entries to be added corresponding to 1929 // the number of edges added. 1930 for (BasicBlock::iterator BBI = EdgeBB->begin(); 1931 isa<PHINode>(BBI); ++BBI) { 1932 PHINode *PN = cast<PHINode>(BBI); 1933 Value *InVal = PN->getIncomingValueForBlock(*PI); 1934 for (unsigned i = 0, e = Values.size()-1; i != e; ++i) 1935 PN->addIncoming(InVal, *PI); 1936 } 1937 1938 // Erase the old branch instruction. 1939 (*PI)->getInstList().erase(BI); 1940 1941 // Erase the potentially condition tree that was used to computed the 1942 // branch condition. 1943 ErasePossiblyDeadInstructionTree(Cond); 1944 return true; 1945 } 1946 } 1947 1948 return Changed; 1949} 1950