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