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