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