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