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