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