SimplifyCFG.cpp revision 3bd51b8df3212f765e6ffee06e32b9a670f9b16c
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/DerivedTypes.h" 18#include "llvm/GlobalVariable.h" 19#include "llvm/IRBuilder.h" 20#include "llvm/Instructions.h" 21#include "llvm/IntrinsicInst.h" 22#include "llvm/LLVMContext.h" 23#include "llvm/MDBuilder.h" 24#include "llvm/Metadata.h" 25#include "llvm/Module.h" 26#include "llvm/Operator.h" 27#include "llvm/Type.h" 28#include "llvm/ADT/DenseMap.h" 29#include "llvm/ADT/STLExtras.h" 30#include "llvm/ADT/SetVector.h" 31#include "llvm/ADT/SmallPtrSet.h" 32#include "llvm/ADT/SmallVector.h" 33#include "llvm/ADT/Statistic.h" 34#include "llvm/Analysis/InstructionSimplify.h" 35#include "llvm/Analysis/ValueTracking.h" 36#include "llvm/Support/CFG.h" 37#include "llvm/Support/CommandLine.h" 38#include "llvm/Support/ConstantRange.h" 39#include "llvm/Support/Debug.h" 40#include "llvm/Support/NoFolder.h" 41#include "llvm/Support/raw_ostream.h" 42#include "llvm/Target/TargetData.h" 43#include "llvm/Transforms/Utils/BasicBlockUtils.h" 44#include <algorithm> 45#include <set> 46#include <map> 47using namespace llvm; 48 49static cl::opt<unsigned> 50PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(1), 51 cl::desc("Control the amount of phi node folding to perform (default = 1)")); 52 53static cl::opt<bool> 54DupRet("simplifycfg-dup-ret", cl::Hidden, cl::init(false), 55 cl::desc("Duplicate return instructions into unconditional branches")); 56 57STATISTIC(NumSpeculations, "Number of speculative executed instructions"); 58STATISTIC(NumLookupTables, "Number of switch instructions turned into lookup tables"); 59 60namespace { 61 /// ValueEqualityComparisonCase - Represents a case of a switch. 62 struct ValueEqualityComparisonCase { 63 ConstantInt *Value; 64 BasicBlock *Dest; 65 66 ValueEqualityComparisonCase(ConstantInt *Value, BasicBlock *Dest) 67 : Value(Value), Dest(Dest) {} 68 69 bool operator<(ValueEqualityComparisonCase RHS) const { 70 // Comparing pointers is ok as we only rely on the order for uniquing. 71 return Value < RHS.Value; 72 } 73 }; 74 75class SimplifyCFGOpt { 76 const TargetData *const TD; 77 78 Value *isValueEqualityComparison(TerminatorInst *TI); 79 BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI, 80 std::vector<ValueEqualityComparisonCase> &Cases); 81 bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, 82 BasicBlock *Pred, 83 IRBuilder<> &Builder); 84 bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI, 85 IRBuilder<> &Builder); 86 87 bool SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder); 88 bool SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder); 89 bool SimplifyUnreachable(UnreachableInst *UI); 90 bool SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder); 91 bool SimplifyIndirectBr(IndirectBrInst *IBI); 92 bool SimplifyUncondBranch(BranchInst *BI, IRBuilder <> &Builder); 93 bool SimplifyCondBranch(BranchInst *BI, IRBuilder <>&Builder); 94 95public: 96 explicit SimplifyCFGOpt(const TargetData *td) : TD(td) {} 97 bool run(BasicBlock *BB); 98}; 99} 100 101/// SafeToMergeTerminators - Return true if it is safe to merge these two 102/// terminator instructions together. 103/// 104static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) { 105 if (SI1 == SI2) return false; // Can't merge with self! 106 107 // It is not safe to merge these two switch instructions if they have a common 108 // successor, and if that successor has a PHI node, and if *that* PHI node has 109 // conflicting incoming values from the two switch blocks. 110 BasicBlock *SI1BB = SI1->getParent(); 111 BasicBlock *SI2BB = SI2->getParent(); 112 SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 113 114 for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) 115 if (SI1Succs.count(*I)) 116 for (BasicBlock::iterator BBI = (*I)->begin(); 117 isa<PHINode>(BBI); ++BBI) { 118 PHINode *PN = cast<PHINode>(BBI); 119 if (PN->getIncomingValueForBlock(SI1BB) != 120 PN->getIncomingValueForBlock(SI2BB)) 121 return false; 122 } 123 124 return true; 125} 126 127/// isProfitableToFoldUnconditional - Return true if it is safe and profitable 128/// to merge these two terminator instructions together, where SI1 is an 129/// unconditional branch. PhiNodes will store all PHI nodes in common 130/// successors. 131/// 132static bool isProfitableToFoldUnconditional(BranchInst *SI1, 133 BranchInst *SI2, 134 Instruction *Cond, 135 SmallVectorImpl<PHINode*> &PhiNodes) { 136 if (SI1 == SI2) return false; // Can't merge with self! 137 assert(SI1->isUnconditional() && SI2->isConditional()); 138 139 // We fold the unconditional branch if we can easily update all PHI nodes in 140 // common successors: 141 // 1> We have a constant incoming value for the conditional branch; 142 // 2> We have "Cond" as the incoming value for the unconditional branch; 143 // 3> SI2->getCondition() and Cond have same operands. 144 CmpInst *Ci2 = dyn_cast<CmpInst>(SI2->getCondition()); 145 if (!Ci2) return false; 146 if (!(Cond->getOperand(0) == Ci2->getOperand(0) && 147 Cond->getOperand(1) == Ci2->getOperand(1)) && 148 !(Cond->getOperand(0) == Ci2->getOperand(1) && 149 Cond->getOperand(1) == Ci2->getOperand(0))) 150 return false; 151 152 BasicBlock *SI1BB = SI1->getParent(); 153 BasicBlock *SI2BB = SI2->getParent(); 154 SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 155 for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) 156 if (SI1Succs.count(*I)) 157 for (BasicBlock::iterator BBI = (*I)->begin(); 158 isa<PHINode>(BBI); ++BBI) { 159 PHINode *PN = cast<PHINode>(BBI); 160 if (PN->getIncomingValueForBlock(SI1BB) != Cond || 161 !isa<ConstantInt>(PN->getIncomingValueForBlock(SI2BB))) 162 return false; 163 PhiNodes.push_back(PN); 164 } 165 return true; 166} 167 168/// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will 169/// now be entries in it from the 'NewPred' block. The values that will be 170/// flowing into the PHI nodes will be the same as those coming in from 171/// ExistPred, an existing predecessor of Succ. 172static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, 173 BasicBlock *ExistPred) { 174 if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do 175 176 PHINode *PN; 177 for (BasicBlock::iterator I = Succ->begin(); 178 (PN = dyn_cast<PHINode>(I)); ++I) 179 PN->addIncoming(PN->getIncomingValueForBlock(ExistPred), NewPred); 180} 181 182 183/// GetIfCondition - Given a basic block (BB) with two predecessors (and at 184/// least one PHI node in it), check to see if the merge at this block is due 185/// to an "if condition". If so, return the boolean condition that determines 186/// which entry into BB will be taken. Also, return by references the block 187/// that will be entered from if the condition is true, and the block that will 188/// be entered if the condition is false. 189/// 190/// This does no checking to see if the true/false blocks have large or unsavory 191/// instructions in them. 192static Value *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, 193 BasicBlock *&IfFalse) { 194 PHINode *SomePHI = cast<PHINode>(BB->begin()); 195 assert(SomePHI->getNumIncomingValues() == 2 && 196 "Function can only handle blocks with 2 predecessors!"); 197 BasicBlock *Pred1 = SomePHI->getIncomingBlock(0); 198 BasicBlock *Pred2 = SomePHI->getIncomingBlock(1); 199 200 // We can only handle branches. Other control flow will be lowered to 201 // branches if possible anyway. 202 BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator()); 203 BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator()); 204 if (Pred1Br == 0 || Pred2Br == 0) 205 return 0; 206 207 // Eliminate code duplication by ensuring that Pred1Br is conditional if 208 // either are. 209 if (Pred2Br->isConditional()) { 210 // If both branches are conditional, we don't have an "if statement". In 211 // reality, we could transform this case, but since the condition will be 212 // required anyway, we stand no chance of eliminating it, so the xform is 213 // probably not profitable. 214 if (Pred1Br->isConditional()) 215 return 0; 216 217 std::swap(Pred1, Pred2); 218 std::swap(Pred1Br, Pred2Br); 219 } 220 221 if (Pred1Br->isConditional()) { 222 // The only thing we have to watch out for here is to make sure that Pred2 223 // doesn't have incoming edges from other blocks. If it does, the condition 224 // doesn't dominate BB. 225 if (Pred2->getSinglePredecessor() == 0) 226 return 0; 227 228 // If we found a conditional branch predecessor, make sure that it branches 229 // to BB and Pred2Br. If it doesn't, this isn't an "if statement". 230 if (Pred1Br->getSuccessor(0) == BB && 231 Pred1Br->getSuccessor(1) == Pred2) { 232 IfTrue = Pred1; 233 IfFalse = Pred2; 234 } else if (Pred1Br->getSuccessor(0) == Pred2 && 235 Pred1Br->getSuccessor(1) == BB) { 236 IfTrue = Pred2; 237 IfFalse = Pred1; 238 } else { 239 // We know that one arm of the conditional goes to BB, so the other must 240 // go somewhere unrelated, and this must not be an "if statement". 241 return 0; 242 } 243 244 return Pred1Br->getCondition(); 245 } 246 247 // Ok, if we got here, both predecessors end with an unconditional branch to 248 // BB. Don't panic! If both blocks only have a single (identical) 249 // predecessor, and THAT is a conditional branch, then we're all ok! 250 BasicBlock *CommonPred = Pred1->getSinglePredecessor(); 251 if (CommonPred == 0 || CommonPred != Pred2->getSinglePredecessor()) 252 return 0; 253 254 // Otherwise, if this is a conditional branch, then we can use it! 255 BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator()); 256 if (BI == 0) return 0; 257 258 assert(BI->isConditional() && "Two successors but not conditional?"); 259 if (BI->getSuccessor(0) == Pred1) { 260 IfTrue = Pred1; 261 IfFalse = Pred2; 262 } else { 263 IfTrue = Pred2; 264 IfFalse = Pred1; 265 } 266 return BI->getCondition(); 267} 268 269/// ComputeSpeculuationCost - Compute an abstract "cost" of speculating the 270/// given instruction, which is assumed to be safe to speculate. 1 means 271/// cheap, 2 means less cheap, and UINT_MAX means prohibitively expensive. 272static unsigned ComputeSpeculationCost(const User *I) { 273 assert(isSafeToSpeculativelyExecute(I) && 274 "Instruction is not safe to speculatively execute!"); 275 switch (Operator::getOpcode(I)) { 276 default: 277 // In doubt, be conservative. 278 return UINT_MAX; 279 case Instruction::GetElementPtr: 280 // GEPs are cheap if all indices are constant. 281 if (!cast<GEPOperator>(I)->hasAllConstantIndices()) 282 return UINT_MAX; 283 return 1; 284 case Instruction::Load: 285 case Instruction::Add: 286 case Instruction::Sub: 287 case Instruction::And: 288 case Instruction::Or: 289 case Instruction::Xor: 290 case Instruction::Shl: 291 case Instruction::LShr: 292 case Instruction::AShr: 293 case Instruction::ICmp: 294 case Instruction::Trunc: 295 case Instruction::ZExt: 296 case Instruction::SExt: 297 return 1; // These are all cheap. 298 299 case Instruction::Call: 300 case Instruction::Select: 301 return 2; 302 } 303} 304 305/// DominatesMergePoint - If we have a merge point of an "if condition" as 306/// accepted above, return true if the specified value dominates the block. We 307/// don't handle the true generality of domination here, just a special case 308/// which works well enough for us. 309/// 310/// If AggressiveInsts is non-null, and if V does not dominate BB, we check to 311/// see if V (which must be an instruction) and its recursive operands 312/// that do not dominate BB have a combined cost lower than CostRemaining and 313/// are non-trapping. If both are true, the instruction is inserted into the 314/// set and true is returned. 315/// 316/// The cost for most non-trapping instructions is defined as 1 except for 317/// Select whose cost is 2. 318/// 319/// After this function returns, CostRemaining is decreased by the cost of 320/// V plus its non-dominating operands. If that cost is greater than 321/// CostRemaining, false is returned and CostRemaining is undefined. 322static bool DominatesMergePoint(Value *V, BasicBlock *BB, 323 SmallPtrSet<Instruction*, 4> *AggressiveInsts, 324 unsigned &CostRemaining) { 325 Instruction *I = dyn_cast<Instruction>(V); 326 if (!I) { 327 // Non-instructions all dominate instructions, but not all constantexprs 328 // can be executed unconditionally. 329 if (ConstantExpr *C = dyn_cast<ConstantExpr>(V)) 330 if (C->canTrap()) 331 return false; 332 return true; 333 } 334 BasicBlock *PBB = I->getParent(); 335 336 // We don't want to allow weird loops that might have the "if condition" in 337 // the bottom of this block. 338 if (PBB == BB) return false; 339 340 // If this instruction is defined in a block that contains an unconditional 341 // branch to BB, then it must be in the 'conditional' part of the "if 342 // statement". If not, it definitely dominates the region. 343 BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator()); 344 if (BI == 0 || BI->isConditional() || BI->getSuccessor(0) != BB) 345 return true; 346 347 // If we aren't allowing aggressive promotion anymore, then don't consider 348 // instructions in the 'if region'. 349 if (AggressiveInsts == 0) return false; 350 351 // If we have seen this instruction before, don't count it again. 352 if (AggressiveInsts->count(I)) return true; 353 354 // Okay, it looks like the instruction IS in the "condition". Check to 355 // see if it's a cheap instruction to unconditionally compute, and if it 356 // only uses stuff defined outside of the condition. If so, hoist it out. 357 if (!isSafeToSpeculativelyExecute(I)) 358 return false; 359 360 unsigned Cost = ComputeSpeculationCost(I); 361 362 if (Cost > CostRemaining) 363 return false; 364 365 CostRemaining -= Cost; 366 367 // Okay, we can only really hoist these out if their operands do 368 // not take us over the cost threshold. 369 for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) 370 if (!DominatesMergePoint(*i, BB, AggressiveInsts, CostRemaining)) 371 return false; 372 // Okay, it's safe to do this! Remember this instruction. 373 AggressiveInsts->insert(I); 374 return true; 375} 376 377/// GetConstantInt - Extract ConstantInt from value, looking through IntToPtr 378/// and PointerNullValue. Return NULL if value is not a constant int. 379static ConstantInt *GetConstantInt(Value *V, const TargetData *TD) { 380 // Normal constant int. 381 ConstantInt *CI = dyn_cast<ConstantInt>(V); 382 if (CI || !TD || !isa<Constant>(V) || !V->getType()->isPointerTy()) 383 return CI; 384 385 // This is some kind of pointer constant. Turn it into a pointer-sized 386 // ConstantInt if possible. 387 IntegerType *PtrTy = TD->getIntPtrType(V->getContext()); 388 389 // Null pointer means 0, see SelectionDAGBuilder::getValue(const Value*). 390 if (isa<ConstantPointerNull>(V)) 391 return ConstantInt::get(PtrTy, 0); 392 393 // IntToPtr const int. 394 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 395 if (CE->getOpcode() == Instruction::IntToPtr) 396 if (ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) { 397 // The constant is very likely to have the right type already. 398 if (CI->getType() == PtrTy) 399 return CI; 400 else 401 return cast<ConstantInt> 402 (ConstantExpr::getIntegerCast(CI, PtrTy, /*isSigned=*/false)); 403 } 404 return 0; 405} 406 407/// GatherConstantCompares - Given a potentially 'or'd or 'and'd together 408/// collection of icmp eq/ne instructions that compare a value against a 409/// constant, return the value being compared, and stick the constant into the 410/// Values vector. 411static Value * 412GatherConstantCompares(Value *V, std::vector<ConstantInt*> &Vals, Value *&Extra, 413 const TargetData *TD, bool isEQ, unsigned &UsedICmps) { 414 Instruction *I = dyn_cast<Instruction>(V); 415 if (I == 0) return 0; 416 417 // If this is an icmp against a constant, handle this as one of the cases. 418 if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) { 419 if (ConstantInt *C = GetConstantInt(I->getOperand(1), TD)) { 420 if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) { 421 UsedICmps++; 422 Vals.push_back(C); 423 return I->getOperand(0); 424 } 425 426 // If we have "x ult 3" comparison, for example, then we can add 0,1,2 to 427 // the set. 428 ConstantRange Span = 429 ConstantRange::makeICmpRegion(ICI->getPredicate(), C->getValue()); 430 431 // If this is an and/!= check then we want to optimize "x ugt 2" into 432 // x != 0 && x != 1. 433 if (!isEQ) 434 Span = Span.inverse(); 435 436 // If there are a ton of values, we don't want to make a ginormous switch. 437 if (Span.getSetSize().ugt(8) || Span.isEmptySet()) 438 return 0; 439 440 for (APInt Tmp = Span.getLower(); Tmp != Span.getUpper(); ++Tmp) 441 Vals.push_back(ConstantInt::get(V->getContext(), Tmp)); 442 UsedICmps++; 443 return I->getOperand(0); 444 } 445 return 0; 446 } 447 448 // Otherwise, we can only handle an | or &, depending on isEQ. 449 if (I->getOpcode() != (isEQ ? Instruction::Or : Instruction::And)) 450 return 0; 451 452 unsigned NumValsBeforeLHS = Vals.size(); 453 unsigned UsedICmpsBeforeLHS = UsedICmps; 454 if (Value *LHS = GatherConstantCompares(I->getOperand(0), Vals, Extra, TD, 455 isEQ, UsedICmps)) { 456 unsigned NumVals = Vals.size(); 457 unsigned UsedICmpsBeforeRHS = UsedICmps; 458 if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD, 459 isEQ, UsedICmps)) { 460 if (LHS == RHS) 461 return LHS; 462 Vals.resize(NumVals); 463 UsedICmps = UsedICmpsBeforeRHS; 464 } 465 466 // The RHS of the or/and can't be folded in and we haven't used "Extra" yet, 467 // set it and return success. 468 if (Extra == 0 || Extra == I->getOperand(1)) { 469 Extra = I->getOperand(1); 470 return LHS; 471 } 472 473 Vals.resize(NumValsBeforeLHS); 474 UsedICmps = UsedICmpsBeforeLHS; 475 return 0; 476 } 477 478 // If the LHS can't be folded in, but Extra is available and RHS can, try to 479 // use LHS as Extra. 480 if (Extra == 0 || Extra == I->getOperand(0)) { 481 Value *OldExtra = Extra; 482 Extra = I->getOperand(0); 483 if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD, 484 isEQ, UsedICmps)) 485 return RHS; 486 assert(Vals.size() == NumValsBeforeLHS); 487 Extra = OldExtra; 488 } 489 490 return 0; 491} 492 493static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) { 494 Instruction *Cond = 0; 495 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 496 Cond = dyn_cast<Instruction>(SI->getCondition()); 497 } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 498 if (BI->isConditional()) 499 Cond = dyn_cast<Instruction>(BI->getCondition()); 500 } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(TI)) { 501 Cond = dyn_cast<Instruction>(IBI->getAddress()); 502 } 503 504 TI->eraseFromParent(); 505 if (Cond) RecursivelyDeleteTriviallyDeadInstructions(Cond); 506} 507 508/// isValueEqualityComparison - Return true if the specified terminator checks 509/// to see if a value is equal to constant integer value. 510Value *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) { 511 Value *CV = 0; 512 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 513 // Do not permit merging of large switch instructions into their 514 // predecessors unless there is only one predecessor. 515 if (SI->getNumSuccessors()*std::distance(pred_begin(SI->getParent()), 516 pred_end(SI->getParent())) <= 128) 517 CV = SI->getCondition(); 518 } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 519 if (BI->isConditional() && BI->getCondition()->hasOneUse()) 520 if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) 521 if ((ICI->getPredicate() == ICmpInst::ICMP_EQ || 522 ICI->getPredicate() == ICmpInst::ICMP_NE) && 523 GetConstantInt(ICI->getOperand(1), TD)) 524 CV = ICI->getOperand(0); 525 526 // Unwrap any lossless ptrtoint cast. 527 if (TD && CV && CV->getType() == TD->getIntPtrType(CV->getContext())) 528 if (PtrToIntInst *PTII = dyn_cast<PtrToIntInst>(CV)) 529 CV = PTII->getOperand(0); 530 return CV; 531} 532 533/// GetValueEqualityComparisonCases - Given a value comparison instruction, 534/// decode all of the 'cases' that it represents and return the 'default' block. 535BasicBlock *SimplifyCFGOpt:: 536GetValueEqualityComparisonCases(TerminatorInst *TI, 537 std::vector<ValueEqualityComparisonCase> 538 &Cases) { 539 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 540 Cases.reserve(SI->getNumCases()); 541 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; ++i) 542 Cases.push_back(ValueEqualityComparisonCase(i.getCaseValue(), 543 i.getCaseSuccessor())); 544 return SI->getDefaultDest(); 545 } 546 547 BranchInst *BI = cast<BranchInst>(TI); 548 ICmpInst *ICI = cast<ICmpInst>(BI->getCondition()); 549 BasicBlock *Succ = BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_NE); 550 Cases.push_back(ValueEqualityComparisonCase(GetConstantInt(ICI->getOperand(1), 551 TD), 552 Succ)); 553 return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ); 554} 555 556 557/// EliminateBlockCases - Given a vector of bb/value pairs, remove any entries 558/// in the list that match the specified block. 559static void EliminateBlockCases(BasicBlock *BB, 560 std::vector<ValueEqualityComparisonCase> &Cases) { 561 for (unsigned i = 0, e = Cases.size(); i != e; ++i) 562 if (Cases[i].Dest == BB) { 563 Cases.erase(Cases.begin()+i); 564 --i; --e; 565 } 566} 567 568/// ValuesOverlap - Return true if there are any keys in C1 that exist in C2 as 569/// well. 570static bool 571ValuesOverlap(std::vector<ValueEqualityComparisonCase> &C1, 572 std::vector<ValueEqualityComparisonCase > &C2) { 573 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2; 574 575 // Make V1 be smaller than V2. 576 if (V1->size() > V2->size()) 577 std::swap(V1, V2); 578 579 if (V1->size() == 0) return false; 580 if (V1->size() == 1) { 581 // Just scan V2. 582 ConstantInt *TheVal = (*V1)[0].Value; 583 for (unsigned i = 0, e = V2->size(); i != e; ++i) 584 if (TheVal == (*V2)[i].Value) 585 return true; 586 } 587 588 // Otherwise, just sort both lists and compare element by element. 589 array_pod_sort(V1->begin(), V1->end()); 590 array_pod_sort(V2->begin(), V2->end()); 591 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size(); 592 while (i1 != e1 && i2 != e2) { 593 if ((*V1)[i1].Value == (*V2)[i2].Value) 594 return true; 595 if ((*V1)[i1].Value < (*V2)[i2].Value) 596 ++i1; 597 else 598 ++i2; 599 } 600 return false; 601} 602 603/// SimplifyEqualityComparisonWithOnlyPredecessor - If TI is known to be a 604/// terminator instruction and its block is known to only have a single 605/// predecessor block, check to see if that predecessor is also a value 606/// comparison with the same value, and if that comparison determines the 607/// outcome of this comparison. If so, simplify TI. This does a very limited 608/// form of jump threading. 609bool SimplifyCFGOpt:: 610SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, 611 BasicBlock *Pred, 612 IRBuilder<> &Builder) { 613 Value *PredVal = isValueEqualityComparison(Pred->getTerminator()); 614 if (!PredVal) return false; // Not a value comparison in predecessor. 615 616 Value *ThisVal = isValueEqualityComparison(TI); 617 assert(ThisVal && "This isn't a value comparison!!"); 618 if (ThisVal != PredVal) return false; // Different predicates. 619 620 // TODO: Preserve branch weight metadata, similarly to how 621 // FoldValueComparisonIntoPredecessors preserves it. 622 623 // Find out information about when control will move from Pred to TI's block. 624 std::vector<ValueEqualityComparisonCase> PredCases; 625 BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(), 626 PredCases); 627 EliminateBlockCases(PredDef, PredCases); // Remove default from cases. 628 629 // Find information about how control leaves this block. 630 std::vector<ValueEqualityComparisonCase> ThisCases; 631 BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases); 632 EliminateBlockCases(ThisDef, ThisCases); // Remove default from cases. 633 634 // If TI's block is the default block from Pred's comparison, potentially 635 // simplify TI based on this knowledge. 636 if (PredDef == TI->getParent()) { 637 // If we are here, we know that the value is none of those cases listed in 638 // PredCases. If there are any cases in ThisCases that are in PredCases, we 639 // can simplify TI. 640 if (!ValuesOverlap(PredCases, ThisCases)) 641 return false; 642 643 if (isa<BranchInst>(TI)) { 644 // Okay, one of the successors of this condbr is dead. Convert it to a 645 // uncond br. 646 assert(ThisCases.size() == 1 && "Branch can only have one case!"); 647 // Insert the new branch. 648 Instruction *NI = Builder.CreateBr(ThisDef); 649 (void) NI; 650 651 // Remove PHI node entries for the dead edge. 652 ThisCases[0].Dest->removePredecessor(TI->getParent()); 653 654 DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 655 << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); 656 657 EraseTerminatorInstAndDCECond(TI); 658 return true; 659 } 660 661 SwitchInst *SI = cast<SwitchInst>(TI); 662 // Okay, TI has cases that are statically dead, prune them away. 663 SmallPtrSet<Constant*, 16> DeadCases; 664 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 665 DeadCases.insert(PredCases[i].Value); 666 667 DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 668 << "Through successor TI: " << *TI); 669 670 for (SwitchInst::CaseIt i = SI->case_end(), e = SI->case_begin(); i != e;) { 671 --i; 672 if (DeadCases.count(i.getCaseValue())) { 673 i.getCaseSuccessor()->removePredecessor(TI->getParent()); 674 SI->removeCase(i); 675 } 676 } 677 678 DEBUG(dbgs() << "Leaving: " << *TI << "\n"); 679 return true; 680 } 681 682 // Otherwise, TI's block must correspond to some matched value. Find out 683 // which value (or set of values) this is. 684 ConstantInt *TIV = 0; 685 BasicBlock *TIBB = TI->getParent(); 686 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 687 if (PredCases[i].Dest == TIBB) { 688 if (TIV != 0) 689 return false; // Cannot handle multiple values coming to this block. 690 TIV = PredCases[i].Value; 691 } 692 assert(TIV && "No edge from pred to succ?"); 693 694 // Okay, we found the one constant that our value can be if we get into TI's 695 // BB. Find out which successor will unconditionally be branched to. 696 BasicBlock *TheRealDest = 0; 697 for (unsigned i = 0, e = ThisCases.size(); i != e; ++i) 698 if (ThisCases[i].Value == TIV) { 699 TheRealDest = ThisCases[i].Dest; 700 break; 701 } 702 703 // If not handled by any explicit cases, it is handled by the default case. 704 if (TheRealDest == 0) TheRealDest = ThisDef; 705 706 // Remove PHI node entries for dead edges. 707 BasicBlock *CheckEdge = TheRealDest; 708 for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI) 709 if (*SI != CheckEdge) 710 (*SI)->removePredecessor(TIBB); 711 else 712 CheckEdge = 0; 713 714 // Insert the new branch. 715 Instruction *NI = Builder.CreateBr(TheRealDest); 716 (void) NI; 717 718 DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 719 << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); 720 721 EraseTerminatorInstAndDCECond(TI); 722 return true; 723} 724 725namespace { 726 /// ConstantIntOrdering - This class implements a stable ordering of constant 727 /// integers that does not depend on their address. This is important for 728 /// applications that sort ConstantInt's to ensure uniqueness. 729 struct ConstantIntOrdering { 730 bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { 731 return LHS->getValue().ult(RHS->getValue()); 732 } 733 }; 734} 735 736static int ConstantIntSortPredicate(const void *P1, const void *P2) { 737 const ConstantInt *LHS = *(const ConstantInt*const*)P1; 738 const ConstantInt *RHS = *(const ConstantInt*const*)P2; 739 if (LHS->getValue().ult(RHS->getValue())) 740 return 1; 741 if (LHS->getValue() == RHS->getValue()) 742 return 0; 743 return -1; 744} 745 746static inline bool HasBranchWeights(const Instruction* I) { 747 MDNode* ProfMD = I->getMetadata(LLVMContext::MD_prof); 748 if (ProfMD && ProfMD->getOperand(0)) 749 if (MDString* MDS = dyn_cast<MDString>(ProfMD->getOperand(0))) 750 return MDS->getString().equals("branch_weights"); 751 752 return false; 753} 754 755/// Tries to get a branch weight for the given instruction, returns NULL if it 756/// can't. Pos starts at 0. 757static ConstantInt* GetWeight(Instruction* I, int Pos) { 758 MDNode* ProfMD = I->getMetadata(LLVMContext::MD_prof); 759 if (ProfMD && ProfMD->getOperand(0)) { 760 if (MDString* MDS = dyn_cast<MDString>(ProfMD->getOperand(0))) { 761 if (MDS->getString().equals("branch_weights")) { 762 assert(ProfMD->getNumOperands() >= 3); 763 return dyn_cast<ConstantInt>(ProfMD->getOperand(1 + Pos)); 764 } 765 } 766 } 767 768 return 0; 769} 770 771/// Scale the given weights based on the successor TI's metadata. Scaling is 772/// done by multiplying every weight by the sum of the successor's weights. 773static void ScaleWeights(Instruction* STI, MutableArrayRef<uint64_t> Weights) { 774 // Sum the successor's weights 775 assert(HasBranchWeights(STI)); 776 unsigned Scale = 0; 777 MDNode* ProfMD = STI->getMetadata(LLVMContext::MD_prof); 778 for (unsigned i = 1; i < ProfMD->getNumOperands(); ++i) { 779 ConstantInt* CI = dyn_cast<ConstantInt>(ProfMD->getOperand(i)); 780 assert(CI); 781 Scale += CI->getValue().getZExtValue(); 782 } 783 784 // Skip default, as it's replaced during the folding 785 for (unsigned i = 1; i < Weights.size(); ++i) { 786 Weights[i] *= Scale; 787 } 788} 789 790/// Sees if any of the weights are too big for a uint32_t, and halves all the 791/// weights if any are. 792static void FitWeights(MutableArrayRef<uint64_t> Weights) { 793 bool Halve = false; 794 for (unsigned i = 0; i < Weights.size(); ++i) 795 if (Weights[i] > UINT_MAX) { 796 Halve = true; 797 break; 798 } 799 800 if (! Halve) 801 return; 802 803 for (unsigned i = 0; i < Weights.size(); ++i) 804 Weights[i] /= 2; 805} 806 807/// FoldValueComparisonIntoPredecessors - The specified terminator is a value 808/// equality comparison instruction (either a switch or a branch on "X == c"). 809/// See if any of the predecessors of the terminator block are value comparisons 810/// on the same value. If so, and if safe to do so, fold them together. 811bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI, 812 IRBuilder<> &Builder) { 813 BasicBlock *BB = TI->getParent(); 814 Value *CV = isValueEqualityComparison(TI); // CondVal 815 assert(CV && "Not a comparison?"); 816 bool Changed = false; 817 818 SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB)); 819 while (!Preds.empty()) { 820 BasicBlock *Pred = Preds.pop_back_val(); 821 822 // See if the predecessor is a comparison with the same value. 823 TerminatorInst *PTI = Pred->getTerminator(); 824 Value *PCV = isValueEqualityComparison(PTI); // PredCondVal 825 826 if (PCV == CV && SafeToMergeTerminators(TI, PTI)) { 827 // Figure out which 'cases' to copy from SI to PSI. 828 std::vector<ValueEqualityComparisonCase> BBCases; 829 BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases); 830 831 std::vector<ValueEqualityComparisonCase> PredCases; 832 BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases); 833 834 // Based on whether the default edge from PTI goes to BB or not, fill in 835 // PredCases and PredDefault with the new switch cases we would like to 836 // build. 837 SmallVector<BasicBlock*, 8> NewSuccessors; 838 839 // Update the branch weight metadata along the way 840 SmallVector<uint64_t, 8> Weights; 841 uint64_t PredDefaultWeight = 0; 842 bool PredHasWeights = HasBranchWeights(PTI); 843 bool SuccHasWeights = HasBranchWeights(TI); 844 845 if (PredHasWeights) { 846 MDNode* MD = PTI->getMetadata(LLVMContext::MD_prof); 847 assert(MD); 848 for (unsigned i = 1, e = MD->getNumOperands(); i < e; ++i) { 849 ConstantInt* CI = dyn_cast<ConstantInt>(MD->getOperand(i)); 850 assert(CI); 851 Weights.push_back(CI->getValue().getZExtValue()); 852 } 853 854 // If the predecessor is a conditional eq, then swap the default weight 855 // to be the first entry. 856 if (BranchInst* BI = dyn_cast<BranchInst>(PTI)) { 857 assert(Weights.size() == 2); 858 ICmpInst *ICI = cast<ICmpInst>(BI->getCondition()); 859 860 if (ICI->getPredicate() == ICmpInst::ICMP_EQ) { 861 std::swap(Weights.front(), Weights.back()); 862 } 863 } 864 865 PredDefaultWeight = Weights.front(); 866 } else if (SuccHasWeights) { 867 // If there are no predecessor weights but there are successor weights, 868 // populate Weights with 1, which will later be scaled to the sum of 869 // successor's weights 870 Weights.assign(1 + PredCases.size(), 1); 871 PredDefaultWeight = 1; 872 } 873 874 uint64_t SuccDefaultWeight = 0; 875 if (SuccHasWeights) { 876 int Index = 0; 877 if (BranchInst* BI = dyn_cast<BranchInst>(TI)) { 878 ICmpInst* ICI = dyn_cast<ICmpInst>(BI->getCondition()); 879 assert(ICI); 880 881 if (ICI->getPredicate() == ICmpInst::ICMP_EQ) 882 Index = 1; 883 } 884 885 SuccDefaultWeight = GetWeight(TI, Index)->getValue().getZExtValue(); 886 } 887 888 if (PredDefault == BB) { 889 // If this is the default destination from PTI, only the edges in TI 890 // that don't occur in PTI, or that branch to BB will be activated. 891 std::set<ConstantInt*, ConstantIntOrdering> PTIHandled; 892 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 893 if (PredCases[i].Dest != BB) 894 PTIHandled.insert(PredCases[i].Value); 895 else { 896 // The default destination is BB, we don't need explicit targets. 897 std::swap(PredCases[i], PredCases.back()); 898 899 if (PredHasWeights) { 900 std::swap(Weights[i+1], Weights.back()); 901 Weights.pop_back(); 902 } 903 904 PredCases.pop_back(); 905 --i; --e; 906 } 907 908 // Reconstruct the new switch statement we will be building. 909 if (PredDefault != BBDefault) { 910 PredDefault->removePredecessor(Pred); 911 PredDefault = BBDefault; 912 NewSuccessors.push_back(BBDefault); 913 } 914 915 if (SuccHasWeights) { 916 ScaleWeights(TI, Weights); 917 Weights.front() *= SuccDefaultWeight; 918 } else if (PredHasWeights) { 919 Weights.front() /= (1 + BBCases.size()); 920 } 921 922 for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 923 if (!PTIHandled.count(BBCases[i].Value) && 924 BBCases[i].Dest != BBDefault) { 925 PredCases.push_back(BBCases[i]); 926 NewSuccessors.push_back(BBCases[i].Dest); 927 if (SuccHasWeights) { 928 Weights.push_back(PredDefaultWeight * 929 GetWeight(TI, i)->getValue().getZExtValue()); 930 } else if (PredHasWeights) { 931 // Split the old default's weight amongst the children 932 assert(PredDefaultWeight != 0); 933 Weights.push_back(PredDefaultWeight / (1 + BBCases.size())); 934 } 935 } 936 937 } else { 938 // FIXME: preserve branch weight metadata, similarly to the 'then' 939 // above. For now, drop it. 940 PredHasWeights = false; 941 SuccHasWeights = false; 942 943 // If this is not the default destination from PSI, only the edges 944 // in SI that occur in PSI with a destination of BB will be 945 // activated. 946 std::set<ConstantInt*, ConstantIntOrdering> PTIHandled; 947 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 948 if (PredCases[i].Dest == BB) { 949 PTIHandled.insert(PredCases[i].Value); 950 std::swap(PredCases[i], PredCases.back()); 951 PredCases.pop_back(); 952 --i; --e; 953 } 954 955 // Okay, now we know which constants were sent to BB from the 956 // predecessor. Figure out where they will all go now. 957 for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 958 if (PTIHandled.count(BBCases[i].Value)) { 959 // If this is one we are capable of getting... 960 PredCases.push_back(BBCases[i]); 961 NewSuccessors.push_back(BBCases[i].Dest); 962 PTIHandled.erase(BBCases[i].Value);// This constant is taken care of 963 } 964 965 // If there are any constants vectored to BB that TI doesn't handle, 966 // they must go to the default destination of TI. 967 for (std::set<ConstantInt*, ConstantIntOrdering>::iterator I = 968 PTIHandled.begin(), 969 E = PTIHandled.end(); I != E; ++I) { 970 PredCases.push_back(ValueEqualityComparisonCase(*I, BBDefault)); 971 NewSuccessors.push_back(BBDefault); 972 } 973 } 974 975 // Okay, at this point, we know which new successor Pred will get. Make 976 // sure we update the number of entries in the PHI nodes for these 977 // successors. 978 for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i) 979 AddPredecessorToBlock(NewSuccessors[i], Pred, BB); 980 981 Builder.SetInsertPoint(PTI); 982 // Convert pointer to int before we switch. 983 if (CV->getType()->isPointerTy()) { 984 assert(TD && "Cannot switch on pointer without TargetData"); 985 CV = Builder.CreatePtrToInt(CV, TD->getIntPtrType(CV->getContext()), 986 "magicptr"); 987 } 988 989 // Now that the successors are updated, create the new Switch instruction. 990 SwitchInst *NewSI = Builder.CreateSwitch(CV, PredDefault, 991 PredCases.size()); 992 NewSI->setDebugLoc(PTI->getDebugLoc()); 993 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 994 NewSI->addCase(PredCases[i].Value, PredCases[i].Dest); 995 996 if (PredHasWeights || SuccHasWeights) { 997 // Halve the weights if any of them cannot fit in an uint32_t 998 FitWeights(Weights); 999 1000 SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end()); 1001 1002 NewSI->setMetadata(LLVMContext::MD_prof, 1003 MDBuilder(BB->getContext()). 1004 createBranchWeights(MDWeights)); 1005 } 1006 1007 EraseTerminatorInstAndDCECond(PTI); 1008 1009 // Okay, last check. If BB is still a successor of PSI, then we must 1010 // have an infinite loop case. If so, add an infinitely looping block 1011 // to handle the case to preserve the behavior of the code. 1012 BasicBlock *InfLoopBlock = 0; 1013 for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i) 1014 if (NewSI->getSuccessor(i) == BB) { 1015 if (InfLoopBlock == 0) { 1016 // Insert it at the end of the function, because it's either code, 1017 // or it won't matter if it's hot. :) 1018 InfLoopBlock = BasicBlock::Create(BB->getContext(), 1019 "infloop", BB->getParent()); 1020 BranchInst::Create(InfLoopBlock, InfLoopBlock); 1021 } 1022 NewSI->setSuccessor(i, InfLoopBlock); 1023 } 1024 1025 Changed = true; 1026 } 1027 } 1028 return Changed; 1029} 1030 1031// isSafeToHoistInvoke - If we would need to insert a select that uses the 1032// value of this invoke (comments in HoistThenElseCodeToIf explain why we 1033// would need to do this), we can't hoist the invoke, as there is nowhere 1034// to put the select in this case. 1035static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, 1036 Instruction *I1, Instruction *I2) { 1037 for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 1038 PHINode *PN; 1039 for (BasicBlock::iterator BBI = SI->begin(); 1040 (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 1041 Value *BB1V = PN->getIncomingValueForBlock(BB1); 1042 Value *BB2V = PN->getIncomingValueForBlock(BB2); 1043 if (BB1V != BB2V && (BB1V==I1 || BB2V==I2)) { 1044 return false; 1045 } 1046 } 1047 } 1048 return true; 1049} 1050 1051/// HoistThenElseCodeToIf - Given a conditional branch that goes to BB1 and 1052/// BB2, hoist any common code in the two blocks up into the branch block. The 1053/// caller of this function guarantees that BI's block dominates BB1 and BB2. 1054static bool HoistThenElseCodeToIf(BranchInst *BI) { 1055 // This does very trivial matching, with limited scanning, to find identical 1056 // instructions in the two blocks. In particular, we don't want to get into 1057 // O(M*N) situations here where M and N are the sizes of BB1 and BB2. As 1058 // such, we currently just scan for obviously identical instructions in an 1059 // identical order. 1060 BasicBlock *BB1 = BI->getSuccessor(0); // The true destination. 1061 BasicBlock *BB2 = BI->getSuccessor(1); // The false destination 1062 1063 BasicBlock::iterator BB1_Itr = BB1->begin(); 1064 BasicBlock::iterator BB2_Itr = BB2->begin(); 1065 1066 Instruction *I1 = BB1_Itr++, *I2 = BB2_Itr++; 1067 // Skip debug info if it is not identical. 1068 DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1); 1069 DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2); 1070 if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) { 1071 while (isa<DbgInfoIntrinsic>(I1)) 1072 I1 = BB1_Itr++; 1073 while (isa<DbgInfoIntrinsic>(I2)) 1074 I2 = BB2_Itr++; 1075 } 1076 if (isa<PHINode>(I1) || !I1->isIdenticalToWhenDefined(I2) || 1077 (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2))) 1078 return false; 1079 1080 // If we get here, we can hoist at least one instruction. 1081 BasicBlock *BIParent = BI->getParent(); 1082 1083 do { 1084 // If we are hoisting the terminator instruction, don't move one (making a 1085 // broken BB), instead clone it, and remove BI. 1086 if (isa<TerminatorInst>(I1)) 1087 goto HoistTerminator; 1088 1089 // For a normal instruction, we just move one to right before the branch, 1090 // then replace all uses of the other with the first. Finally, we remove 1091 // the now redundant second instruction. 1092 BIParent->getInstList().splice(BI, BB1->getInstList(), I1); 1093 if (!I2->use_empty()) 1094 I2->replaceAllUsesWith(I1); 1095 I1->intersectOptionalDataWith(I2); 1096 I2->eraseFromParent(); 1097 1098 I1 = BB1_Itr++; 1099 I2 = BB2_Itr++; 1100 // Skip debug info if it is not identical. 1101 DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1); 1102 DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2); 1103 if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) { 1104 while (isa<DbgInfoIntrinsic>(I1)) 1105 I1 = BB1_Itr++; 1106 while (isa<DbgInfoIntrinsic>(I2)) 1107 I2 = BB2_Itr++; 1108 } 1109 } while (I1->isIdenticalToWhenDefined(I2)); 1110 1111 return true; 1112 1113HoistTerminator: 1114 // It may not be possible to hoist an invoke. 1115 if (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)) 1116 return true; 1117 1118 // Okay, it is safe to hoist the terminator. 1119 Instruction *NT = I1->clone(); 1120 BIParent->getInstList().insert(BI, NT); 1121 if (!NT->getType()->isVoidTy()) { 1122 I1->replaceAllUsesWith(NT); 1123 I2->replaceAllUsesWith(NT); 1124 NT->takeName(I1); 1125 } 1126 1127 IRBuilder<true, NoFolder> Builder(NT); 1128 // Hoisting one of the terminators from our successor is a great thing. 1129 // Unfortunately, the successors of the if/else blocks may have PHI nodes in 1130 // them. If they do, all PHI entries for BB1/BB2 must agree for all PHI 1131 // nodes, so we insert select instruction to compute the final result. 1132 std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects; 1133 for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 1134 PHINode *PN; 1135 for (BasicBlock::iterator BBI = SI->begin(); 1136 (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 1137 Value *BB1V = PN->getIncomingValueForBlock(BB1); 1138 Value *BB2V = PN->getIncomingValueForBlock(BB2); 1139 if (BB1V == BB2V) continue; 1140 1141 // These values do not agree. Insert a select instruction before NT 1142 // that determines the right value. 1143 SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)]; 1144 if (SI == 0) 1145 SI = cast<SelectInst> 1146 (Builder.CreateSelect(BI->getCondition(), BB1V, BB2V, 1147 BB1V->getName()+"."+BB2V->getName())); 1148 1149 // Make the PHI node use the select for all incoming values for BB1/BB2 1150 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 1151 if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2) 1152 PN->setIncomingValue(i, SI); 1153 } 1154 } 1155 1156 // Update any PHI nodes in our new successors. 1157 for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) 1158 AddPredecessorToBlock(*SI, BIParent, BB1); 1159 1160 EraseTerminatorInstAndDCECond(BI); 1161 return true; 1162} 1163 1164/// SpeculativelyExecuteBB - Given a conditional branch that goes to BB1 1165/// and an BB2 and the only successor of BB1 is BB2, hoist simple code 1166/// (for now, restricted to a single instruction that's side effect free) from 1167/// the BB1 into the branch block to speculatively execute it. 1168/// 1169/// Turn 1170/// BB: 1171/// %t1 = icmp 1172/// br i1 %t1, label %BB1, label %BB2 1173/// BB1: 1174/// %t3 = add %t2, c 1175/// br label BB2 1176/// BB2: 1177/// => 1178/// BB: 1179/// %t1 = icmp 1180/// %t4 = add %t2, c 1181/// %t3 = select i1 %t1, %t2, %t3 1182static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) { 1183 // Only speculatively execution a single instruction (not counting the 1184 // terminator) for now. 1185 Instruction *HInst = NULL; 1186 Instruction *Term = BB1->getTerminator(); 1187 for (BasicBlock::iterator BBI = BB1->begin(), BBE = BB1->end(); 1188 BBI != BBE; ++BBI) { 1189 Instruction *I = BBI; 1190 // Skip debug info. 1191 if (isa<DbgInfoIntrinsic>(I)) continue; 1192 if (I == Term) break; 1193 1194 if (HInst) 1195 return false; 1196 HInst = I; 1197 } 1198 1199 BasicBlock *BIParent = BI->getParent(); 1200 1201 // Check the instruction to be hoisted, if there is one. 1202 if (HInst) { 1203 // Don't hoist the instruction if it's unsafe or expensive. 1204 if (!isSafeToSpeculativelyExecute(HInst)) 1205 return false; 1206 if (ComputeSpeculationCost(HInst) > PHINodeFoldingThreshold) 1207 return false; 1208 1209 // Do not hoist the instruction if any of its operands are defined but not 1210 // used in this BB. The transformation will prevent the operand from 1211 // being sunk into the use block. 1212 for (User::op_iterator i = HInst->op_begin(), e = HInst->op_end(); 1213 i != e; ++i) { 1214 Instruction *OpI = dyn_cast<Instruction>(*i); 1215 if (OpI && OpI->getParent() == BIParent && 1216 !OpI->mayHaveSideEffects() && 1217 !OpI->isUsedInBasicBlock(BIParent)) 1218 return false; 1219 } 1220 } 1221 1222 // Be conservative for now. FP select instruction can often be expensive. 1223 Value *BrCond = BI->getCondition(); 1224 if (isa<FCmpInst>(BrCond)) 1225 return false; 1226 1227 // If BB1 is actually on the false edge of the conditional branch, remember 1228 // to swap the select operands later. 1229 bool Invert = false; 1230 if (BB1 != BI->getSuccessor(0)) { 1231 assert(BB1 == BI->getSuccessor(1) && "No edge from 'if' block?"); 1232 Invert = true; 1233 } 1234 1235 // Collect interesting PHIs, and scan for hazards. 1236 SmallSetVector<std::pair<Value *, Value *>, 4> PHIs; 1237 BasicBlock *BB2 = BB1->getTerminator()->getSuccessor(0); 1238 for (BasicBlock::iterator I = BB2->begin(); 1239 PHINode *PN = dyn_cast<PHINode>(I); ++I) { 1240 Value *BB1V = PN->getIncomingValueForBlock(BB1); 1241 Value *BIParentV = PN->getIncomingValueForBlock(BIParent); 1242 1243 // Skip PHIs which are trivial. 1244 if (BB1V == BIParentV) 1245 continue; 1246 1247 // Check for saftey. 1248 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(BB1V)) { 1249 // An unfolded ConstantExpr could end up getting expanded into 1250 // Instructions. Don't speculate this and another instruction at 1251 // the same time. 1252 if (HInst) 1253 return false; 1254 if (!isSafeToSpeculativelyExecute(CE)) 1255 return false; 1256 if (ComputeSpeculationCost(CE) > PHINodeFoldingThreshold) 1257 return false; 1258 } 1259 1260 // Ok, we may insert a select for this PHI. 1261 PHIs.insert(std::make_pair(BB1V, BIParentV)); 1262 } 1263 1264 // If there are no PHIs to process, bail early. This helps ensure idempotence 1265 // as well. 1266 if (PHIs.empty()) 1267 return false; 1268 1269 // If we get here, we can hoist the instruction and if-convert. 1270 DEBUG(dbgs() << "SPECULATIVELY EXECUTING BB" << *BB1 << "\n";); 1271 1272 // Hoist the instruction. 1273 if (HInst) 1274 BIParent->getInstList().splice(BI, BB1->getInstList(), HInst); 1275 1276 // Insert selects and rewrite the PHI operands. 1277 IRBuilder<true, NoFolder> Builder(BI); 1278 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) { 1279 Value *TrueV = PHIs[i].first; 1280 Value *FalseV = PHIs[i].second; 1281 1282 // Create a select whose true value is the speculatively executed value and 1283 // false value is the previously determined FalseV. 1284 SelectInst *SI; 1285 if (Invert) 1286 SI = cast<SelectInst> 1287 (Builder.CreateSelect(BrCond, FalseV, TrueV, 1288 FalseV->getName() + "." + TrueV->getName())); 1289 else 1290 SI = cast<SelectInst> 1291 (Builder.CreateSelect(BrCond, TrueV, FalseV, 1292 TrueV->getName() + "." + FalseV->getName())); 1293 1294 // Make the PHI node use the select for all incoming values for "then" and 1295 // "if" blocks. 1296 for (BasicBlock::iterator I = BB2->begin(); 1297 PHINode *PN = dyn_cast<PHINode>(I); ++I) { 1298 unsigned BB1I = PN->getBasicBlockIndex(BB1); 1299 unsigned BIParentI = PN->getBasicBlockIndex(BIParent); 1300 Value *BB1V = PN->getIncomingValue(BB1I); 1301 Value *BIParentV = PN->getIncomingValue(BIParentI); 1302 if (TrueV == BB1V && FalseV == BIParentV) { 1303 PN->setIncomingValue(BB1I, SI); 1304 PN->setIncomingValue(BIParentI, SI); 1305 } 1306 } 1307 } 1308 1309 ++NumSpeculations; 1310 return true; 1311} 1312 1313/// BlockIsSimpleEnoughToThreadThrough - Return true if we can thread a branch 1314/// across this block. 1315static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) { 1316 BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 1317 unsigned Size = 0; 1318 1319 for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { 1320 if (isa<DbgInfoIntrinsic>(BBI)) 1321 continue; 1322 if (Size > 10) return false; // Don't clone large BB's. 1323 ++Size; 1324 1325 // We can only support instructions that do not define values that are 1326 // live outside of the current basic block. 1327 for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); 1328 UI != E; ++UI) { 1329 Instruction *U = cast<Instruction>(*UI); 1330 if (U->getParent() != BB || isa<PHINode>(U)) return false; 1331 } 1332 1333 // Looks ok, continue checking. 1334 } 1335 1336 return true; 1337} 1338 1339/// FoldCondBranchOnPHI - If we have a conditional branch on a PHI node value 1340/// that is defined in the same block as the branch and if any PHI entries are 1341/// constants, thread edges corresponding to that entry to be branches to their 1342/// ultimate destination. 1343static bool FoldCondBranchOnPHI(BranchInst *BI, const TargetData *TD) { 1344 BasicBlock *BB = BI->getParent(); 1345 PHINode *PN = dyn_cast<PHINode>(BI->getCondition()); 1346 // NOTE: we currently cannot transform this case if the PHI node is used 1347 // outside of the block. 1348 if (!PN || PN->getParent() != BB || !PN->hasOneUse()) 1349 return false; 1350 1351 // Degenerate case of a single entry PHI. 1352 if (PN->getNumIncomingValues() == 1) { 1353 FoldSingleEntryPHINodes(PN->getParent()); 1354 return true; 1355 } 1356 1357 // Now we know that this block has multiple preds and two succs. 1358 if (!BlockIsSimpleEnoughToThreadThrough(BB)) return false; 1359 1360 // Okay, this is a simple enough basic block. See if any phi values are 1361 // constants. 1362 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1363 ConstantInt *CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i)); 1364 if (CB == 0 || !CB->getType()->isIntegerTy(1)) continue; 1365 1366 // Okay, we now know that all edges from PredBB should be revectored to 1367 // branch to RealDest. 1368 BasicBlock *PredBB = PN->getIncomingBlock(i); 1369 BasicBlock *RealDest = BI->getSuccessor(!CB->getZExtValue()); 1370 1371 if (RealDest == BB) continue; // Skip self loops. 1372 // Skip if the predecessor's terminator is an indirect branch. 1373 if (isa<IndirectBrInst>(PredBB->getTerminator())) continue; 1374 1375 // The dest block might have PHI nodes, other predecessors and other 1376 // difficult cases. Instead of being smart about this, just insert a new 1377 // block that jumps to the destination block, effectively splitting 1378 // the edge we are about to create. 1379 BasicBlock *EdgeBB = BasicBlock::Create(BB->getContext(), 1380 RealDest->getName()+".critedge", 1381 RealDest->getParent(), RealDest); 1382 BranchInst::Create(RealDest, EdgeBB); 1383 1384 // Update PHI nodes. 1385 AddPredecessorToBlock(RealDest, EdgeBB, BB); 1386 1387 // BB may have instructions that are being threaded over. Clone these 1388 // instructions into EdgeBB. We know that there will be no uses of the 1389 // cloned instructions outside of EdgeBB. 1390 BasicBlock::iterator InsertPt = EdgeBB->begin(); 1391 DenseMap<Value*, Value*> TranslateMap; // Track translated values. 1392 for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { 1393 if (PHINode *PN = dyn_cast<PHINode>(BBI)) { 1394 TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB); 1395 continue; 1396 } 1397 // Clone the instruction. 1398 Instruction *N = BBI->clone(); 1399 if (BBI->hasName()) N->setName(BBI->getName()+".c"); 1400 1401 // Update operands due to translation. 1402 for (User::op_iterator i = N->op_begin(), e = N->op_end(); 1403 i != e; ++i) { 1404 DenseMap<Value*, Value*>::iterator PI = TranslateMap.find(*i); 1405 if (PI != TranslateMap.end()) 1406 *i = PI->second; 1407 } 1408 1409 // Check for trivial simplification. 1410 if (Value *V = SimplifyInstruction(N, TD)) { 1411 TranslateMap[BBI] = V; 1412 delete N; // Instruction folded away, don't need actual inst 1413 } else { 1414 // Insert the new instruction into its new home. 1415 EdgeBB->getInstList().insert(InsertPt, N); 1416 if (!BBI->use_empty()) 1417 TranslateMap[BBI] = N; 1418 } 1419 } 1420 1421 // Loop over all of the edges from PredBB to BB, changing them to branch 1422 // to EdgeBB instead. 1423 TerminatorInst *PredBBTI = PredBB->getTerminator(); 1424 for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i) 1425 if (PredBBTI->getSuccessor(i) == BB) { 1426 BB->removePredecessor(PredBB); 1427 PredBBTI->setSuccessor(i, EdgeBB); 1428 } 1429 1430 // Recurse, simplifying any other constants. 1431 return FoldCondBranchOnPHI(BI, TD) | true; 1432 } 1433 1434 return false; 1435} 1436 1437/// FoldTwoEntryPHINode - Given a BB that starts with the specified two-entry 1438/// PHI node, see if we can eliminate it. 1439static bool FoldTwoEntryPHINode(PHINode *PN, const TargetData *TD) { 1440 // Ok, this is a two entry PHI node. Check to see if this is a simple "if 1441 // statement", which has a very simple dominance structure. Basically, we 1442 // are trying to find the condition that is being branched on, which 1443 // subsequently causes this merge to happen. We really want control 1444 // dependence information for this check, but simplifycfg can't keep it up 1445 // to date, and this catches most of the cases we care about anyway. 1446 BasicBlock *BB = PN->getParent(); 1447 BasicBlock *IfTrue, *IfFalse; 1448 Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse); 1449 if (!IfCond || 1450 // Don't bother if the branch will be constant folded trivially. 1451 isa<ConstantInt>(IfCond)) 1452 return false; 1453 1454 // Okay, we found that we can merge this two-entry phi node into a select. 1455 // Doing so would require us to fold *all* two entry phi nodes in this block. 1456 // At some point this becomes non-profitable (particularly if the target 1457 // doesn't support cmov's). Only do this transformation if there are two or 1458 // fewer PHI nodes in this block. 1459 unsigned NumPhis = 0; 1460 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++NumPhis, ++I) 1461 if (NumPhis > 2) 1462 return false; 1463 1464 // Loop over the PHI's seeing if we can promote them all to select 1465 // instructions. While we are at it, keep track of the instructions 1466 // that need to be moved to the dominating block. 1467 SmallPtrSet<Instruction*, 4> AggressiveInsts; 1468 unsigned MaxCostVal0 = PHINodeFoldingThreshold, 1469 MaxCostVal1 = PHINodeFoldingThreshold; 1470 1471 for (BasicBlock::iterator II = BB->begin(); isa<PHINode>(II);) { 1472 PHINode *PN = cast<PHINode>(II++); 1473 if (Value *V = SimplifyInstruction(PN, TD)) { 1474 PN->replaceAllUsesWith(V); 1475 PN->eraseFromParent(); 1476 continue; 1477 } 1478 1479 if (!DominatesMergePoint(PN->getIncomingValue(0), BB, &AggressiveInsts, 1480 MaxCostVal0) || 1481 !DominatesMergePoint(PN->getIncomingValue(1), BB, &AggressiveInsts, 1482 MaxCostVal1)) 1483 return false; 1484 } 1485 1486 // If we folded the first phi, PN dangles at this point. Refresh it. If 1487 // we ran out of PHIs then we simplified them all. 1488 PN = dyn_cast<PHINode>(BB->begin()); 1489 if (PN == 0) return true; 1490 1491 // Don't fold i1 branches on PHIs which contain binary operators. These can 1492 // often be turned into switches and other things. 1493 if (PN->getType()->isIntegerTy(1) && 1494 (isa<BinaryOperator>(PN->getIncomingValue(0)) || 1495 isa<BinaryOperator>(PN->getIncomingValue(1)) || 1496 isa<BinaryOperator>(IfCond))) 1497 return false; 1498 1499 // If we all PHI nodes are promotable, check to make sure that all 1500 // instructions in the predecessor blocks can be promoted as well. If 1501 // not, we won't be able to get rid of the control flow, so it's not 1502 // worth promoting to select instructions. 1503 BasicBlock *DomBlock = 0; 1504 BasicBlock *IfBlock1 = PN->getIncomingBlock(0); 1505 BasicBlock *IfBlock2 = PN->getIncomingBlock(1); 1506 if (cast<BranchInst>(IfBlock1->getTerminator())->isConditional()) { 1507 IfBlock1 = 0; 1508 } else { 1509 DomBlock = *pred_begin(IfBlock1); 1510 for (BasicBlock::iterator I = IfBlock1->begin();!isa<TerminatorInst>(I);++I) 1511 if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) { 1512 // This is not an aggressive instruction that we can promote. 1513 // Because of this, we won't be able to get rid of the control 1514 // flow, so the xform is not worth it. 1515 return false; 1516 } 1517 } 1518 1519 if (cast<BranchInst>(IfBlock2->getTerminator())->isConditional()) { 1520 IfBlock2 = 0; 1521 } else { 1522 DomBlock = *pred_begin(IfBlock2); 1523 for (BasicBlock::iterator I = IfBlock2->begin();!isa<TerminatorInst>(I);++I) 1524 if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) { 1525 // This is not an aggressive instruction that we can promote. 1526 // Because of this, we won't be able to get rid of the control 1527 // flow, so the xform is not worth it. 1528 return false; 1529 } 1530 } 1531 1532 DEBUG(dbgs() << "FOUND IF CONDITION! " << *IfCond << " T: " 1533 << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"); 1534 1535 // If we can still promote the PHI nodes after this gauntlet of tests, 1536 // do all of the PHI's now. 1537 Instruction *InsertPt = DomBlock->getTerminator(); 1538 IRBuilder<true, NoFolder> Builder(InsertPt); 1539 1540 // Move all 'aggressive' instructions, which are defined in the 1541 // conditional parts of the if's up to the dominating block. 1542 if (IfBlock1) 1543 DomBlock->getInstList().splice(InsertPt, 1544 IfBlock1->getInstList(), IfBlock1->begin(), 1545 IfBlock1->getTerminator()); 1546 if (IfBlock2) 1547 DomBlock->getInstList().splice(InsertPt, 1548 IfBlock2->getInstList(), IfBlock2->begin(), 1549 IfBlock2->getTerminator()); 1550 1551 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 1552 // Change the PHI node into a select instruction. 1553 Value *TrueVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); 1554 Value *FalseVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); 1555 1556 SelectInst *NV = 1557 cast<SelectInst>(Builder.CreateSelect(IfCond, TrueVal, FalseVal, "")); 1558 PN->replaceAllUsesWith(NV); 1559 NV->takeName(PN); 1560 PN->eraseFromParent(); 1561 } 1562 1563 // At this point, IfBlock1 and IfBlock2 are both empty, so our if statement 1564 // has been flattened. Change DomBlock to jump directly to our new block to 1565 // avoid other simplifycfg's kicking in on the diamond. 1566 TerminatorInst *OldTI = DomBlock->getTerminator(); 1567 Builder.SetInsertPoint(OldTI); 1568 Builder.CreateBr(BB); 1569 OldTI->eraseFromParent(); 1570 return true; 1571} 1572 1573/// SimplifyCondBranchToTwoReturns - If we found a conditional branch that goes 1574/// to two returning blocks, try to merge them together into one return, 1575/// introducing a select if the return values disagree. 1576static bool SimplifyCondBranchToTwoReturns(BranchInst *BI, 1577 IRBuilder<> &Builder) { 1578 assert(BI->isConditional() && "Must be a conditional branch"); 1579 BasicBlock *TrueSucc = BI->getSuccessor(0); 1580 BasicBlock *FalseSucc = BI->getSuccessor(1); 1581 ReturnInst *TrueRet = cast<ReturnInst>(TrueSucc->getTerminator()); 1582 ReturnInst *FalseRet = cast<ReturnInst>(FalseSucc->getTerminator()); 1583 1584 // Check to ensure both blocks are empty (just a return) or optionally empty 1585 // with PHI nodes. If there are other instructions, merging would cause extra 1586 // computation on one path or the other. 1587 if (!TrueSucc->getFirstNonPHIOrDbg()->isTerminator()) 1588 return false; 1589 if (!FalseSucc->getFirstNonPHIOrDbg()->isTerminator()) 1590 return false; 1591 1592 Builder.SetInsertPoint(BI); 1593 // Okay, we found a branch that is going to two return nodes. If 1594 // there is no return value for this function, just change the 1595 // branch into a return. 1596 if (FalseRet->getNumOperands() == 0) { 1597 TrueSucc->removePredecessor(BI->getParent()); 1598 FalseSucc->removePredecessor(BI->getParent()); 1599 Builder.CreateRetVoid(); 1600 EraseTerminatorInstAndDCECond(BI); 1601 return true; 1602 } 1603 1604 // Otherwise, figure out what the true and false return values are 1605 // so we can insert a new select instruction. 1606 Value *TrueValue = TrueRet->getReturnValue(); 1607 Value *FalseValue = FalseRet->getReturnValue(); 1608 1609 // Unwrap any PHI nodes in the return blocks. 1610 if (PHINode *TVPN = dyn_cast_or_null<PHINode>(TrueValue)) 1611 if (TVPN->getParent() == TrueSucc) 1612 TrueValue = TVPN->getIncomingValueForBlock(BI->getParent()); 1613 if (PHINode *FVPN = dyn_cast_or_null<PHINode>(FalseValue)) 1614 if (FVPN->getParent() == FalseSucc) 1615 FalseValue = FVPN->getIncomingValueForBlock(BI->getParent()); 1616 1617 // In order for this transformation to be safe, we must be able to 1618 // unconditionally execute both operands to the return. This is 1619 // normally the case, but we could have a potentially-trapping 1620 // constant expression that prevents this transformation from being 1621 // safe. 1622 if (ConstantExpr *TCV = dyn_cast_or_null<ConstantExpr>(TrueValue)) 1623 if (TCV->canTrap()) 1624 return false; 1625 if (ConstantExpr *FCV = dyn_cast_or_null<ConstantExpr>(FalseValue)) 1626 if (FCV->canTrap()) 1627 return false; 1628 1629 // Okay, we collected all the mapped values and checked them for sanity, and 1630 // defined to really do this transformation. First, update the CFG. 1631 TrueSucc->removePredecessor(BI->getParent()); 1632 FalseSucc->removePredecessor(BI->getParent()); 1633 1634 // Insert select instructions where needed. 1635 Value *BrCond = BI->getCondition(); 1636 if (TrueValue) { 1637 // Insert a select if the results differ. 1638 if (TrueValue == FalseValue || isa<UndefValue>(FalseValue)) { 1639 } else if (isa<UndefValue>(TrueValue)) { 1640 TrueValue = FalseValue; 1641 } else { 1642 TrueValue = Builder.CreateSelect(BrCond, TrueValue, 1643 FalseValue, "retval"); 1644 } 1645 } 1646 1647 Value *RI = !TrueValue ? 1648 Builder.CreateRetVoid() : Builder.CreateRet(TrueValue); 1649 1650 (void) RI; 1651 1652 DEBUG(dbgs() << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:" 1653 << "\n " << *BI << "NewRet = " << *RI 1654 << "TRUEBLOCK: " << *TrueSucc << "FALSEBLOCK: "<< *FalseSucc); 1655 1656 EraseTerminatorInstAndDCECond(BI); 1657 1658 return true; 1659} 1660 1661/// ExtractBranchMetadata - Given a conditional BranchInstruction, retrieve the 1662/// probabilities of the branch taking each edge. Fills in the two APInt 1663/// parameters and return true, or returns false if no or invalid metadata was 1664/// found. 1665static bool ExtractBranchMetadata(BranchInst *BI, 1666 APInt &ProbTrue, APInt &ProbFalse) { 1667 assert(BI->isConditional() && 1668 "Looking for probabilities on unconditional branch?"); 1669 MDNode *ProfileData = BI->getMetadata(LLVMContext::MD_prof); 1670 if (!ProfileData || ProfileData->getNumOperands() != 3) return false; 1671 ConstantInt *CITrue = dyn_cast<ConstantInt>(ProfileData->getOperand(1)); 1672 ConstantInt *CIFalse = dyn_cast<ConstantInt>(ProfileData->getOperand(2)); 1673 if (!CITrue || !CIFalse) return false; 1674 ProbTrue = CITrue->getValue(); 1675 ProbFalse = CIFalse->getValue(); 1676 assert(ProbTrue.getBitWidth() == 32 && ProbFalse.getBitWidth() == 32 && 1677 "Branch probability metadata must be 32-bit integers"); 1678 return true; 1679} 1680 1681/// MultiplyAndLosePrecision - Multiplies A and B, then returns the result. In 1682/// the event of overflow, logically-shifts all four inputs right until the 1683/// multiply fits. 1684static APInt MultiplyAndLosePrecision(APInt &A, APInt &B, APInt &C, APInt &D, 1685 unsigned &BitsLost) { 1686 BitsLost = 0; 1687 bool Overflow = false; 1688 APInt Result = A.umul_ov(B, Overflow); 1689 if (Overflow) { 1690 APInt MaxB = APInt::getMaxValue(A.getBitWidth()).udiv(A); 1691 do { 1692 B = B.lshr(1); 1693 ++BitsLost; 1694 } while (B.ugt(MaxB)); 1695 A = A.lshr(BitsLost); 1696 C = C.lshr(BitsLost); 1697 D = D.lshr(BitsLost); 1698 Result = A * B; 1699 } 1700 return Result; 1701} 1702 1703/// checkCSEInPredecessor - Return true if the given instruction is available 1704/// in its predecessor block. If yes, the instruction will be removed. 1705/// 1706static bool checkCSEInPredecessor(Instruction *Inst, BasicBlock *PB) { 1707 if (!isa<BinaryOperator>(Inst) && !isa<CmpInst>(Inst)) 1708 return false; 1709 for (BasicBlock::iterator I = PB->begin(), E = PB->end(); I != E; I++) { 1710 Instruction *PBI = &*I; 1711 // Check whether Inst and PBI generate the same value. 1712 if (Inst->isIdenticalTo(PBI)) { 1713 Inst->replaceAllUsesWith(PBI); 1714 Inst->eraseFromParent(); 1715 return true; 1716 } 1717 } 1718 return false; 1719} 1720 1721/// FoldBranchToCommonDest - If this basic block is simple enough, and if a 1722/// predecessor branches to us and one of our successors, fold the block into 1723/// the predecessor and use logical operations to pick the right destination. 1724bool llvm::FoldBranchToCommonDest(BranchInst *BI) { 1725 BasicBlock *BB = BI->getParent(); 1726 1727 Instruction *Cond = 0; 1728 if (BI->isConditional()) 1729 Cond = dyn_cast<Instruction>(BI->getCondition()); 1730 else { 1731 // For unconditional branch, check for a simple CFG pattern, where 1732 // BB has a single predecessor and BB's successor is also its predecessor's 1733 // successor. If such pattern exisits, check for CSE between BB and its 1734 // predecessor. 1735 if (BasicBlock *PB = BB->getSinglePredecessor()) 1736 if (BranchInst *PBI = dyn_cast<BranchInst>(PB->getTerminator())) 1737 if (PBI->isConditional() && 1738 (BI->getSuccessor(0) == PBI->getSuccessor(0) || 1739 BI->getSuccessor(0) == PBI->getSuccessor(1))) { 1740 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); 1741 I != E; ) { 1742 Instruction *Curr = I++; 1743 if (isa<CmpInst>(Curr)) { 1744 Cond = Curr; 1745 break; 1746 } 1747 // Quit if we can't remove this instruction. 1748 if (!checkCSEInPredecessor(Curr, PB)) 1749 return false; 1750 } 1751 } 1752 1753 if (Cond == 0) 1754 return false; 1755 } 1756 1757 if (Cond == 0 || (!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) || 1758 Cond->getParent() != BB || !Cond->hasOneUse()) 1759 return false; 1760 1761 // Only allow this if the condition is a simple instruction that can be 1762 // executed unconditionally. It must be in the same block as the branch, and 1763 // must be at the front of the block. 1764 BasicBlock::iterator FrontIt = BB->front(); 1765 1766 // Ignore dbg intrinsics. 1767 while (isa<DbgInfoIntrinsic>(FrontIt)) ++FrontIt; 1768 1769 // Allow a single instruction to be hoisted in addition to the compare 1770 // that feeds the branch. We later ensure that any values that _it_ uses 1771 // were also live in the predecessor, so that we don't unnecessarily create 1772 // register pressure or inhibit out-of-order execution. 1773 Instruction *BonusInst = 0; 1774 if (&*FrontIt != Cond && 1775 FrontIt->hasOneUse() && *FrontIt->use_begin() == Cond && 1776 isSafeToSpeculativelyExecute(FrontIt)) { 1777 BonusInst = &*FrontIt; 1778 ++FrontIt; 1779 1780 // Ignore dbg intrinsics. 1781 while (isa<DbgInfoIntrinsic>(FrontIt)) ++FrontIt; 1782 } 1783 1784 // Only a single bonus inst is allowed. 1785 if (&*FrontIt != Cond) 1786 return false; 1787 1788 // Make sure the instruction after the condition is the cond branch. 1789 BasicBlock::iterator CondIt = Cond; ++CondIt; 1790 1791 // Ingore dbg intrinsics. 1792 while (isa<DbgInfoIntrinsic>(CondIt)) ++CondIt; 1793 1794 if (&*CondIt != BI) 1795 return false; 1796 1797 // Cond is known to be a compare or binary operator. Check to make sure that 1798 // neither operand is a potentially-trapping constant expression. 1799 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(0))) 1800 if (CE->canTrap()) 1801 return false; 1802 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(1))) 1803 if (CE->canTrap()) 1804 return false; 1805 1806 // Finally, don't infinitely unroll conditional loops. 1807 BasicBlock *TrueDest = BI->getSuccessor(0); 1808 BasicBlock *FalseDest = (BI->isConditional()) ? BI->getSuccessor(1) : 0; 1809 if (TrueDest == BB || FalseDest == BB) 1810 return false; 1811 1812 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 1813 BasicBlock *PredBlock = *PI; 1814 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator()); 1815 1816 // Check that we have two conditional branches. If there is a PHI node in 1817 // the common successor, verify that the same value flows in from both 1818 // blocks. 1819 SmallVector<PHINode*, 4> PHIs; 1820 if (PBI == 0 || PBI->isUnconditional() || 1821 (BI->isConditional() && 1822 !SafeToMergeTerminators(BI, PBI)) || 1823 (!BI->isConditional() && 1824 !isProfitableToFoldUnconditional(BI, PBI, Cond, PHIs))) 1825 continue; 1826 1827 // Determine if the two branches share a common destination. 1828 Instruction::BinaryOps Opc; 1829 bool InvertPredCond = false; 1830 1831 if (BI->isConditional()) { 1832 if (PBI->getSuccessor(0) == TrueDest) 1833 Opc = Instruction::Or; 1834 else if (PBI->getSuccessor(1) == FalseDest) 1835 Opc = Instruction::And; 1836 else if (PBI->getSuccessor(0) == FalseDest) 1837 Opc = Instruction::And, InvertPredCond = true; 1838 else if (PBI->getSuccessor(1) == TrueDest) 1839 Opc = Instruction::Or, InvertPredCond = true; 1840 else 1841 continue; 1842 } else { 1843 if (PBI->getSuccessor(0) != TrueDest && PBI->getSuccessor(1) != TrueDest) 1844 continue; 1845 } 1846 1847 // Ensure that any values used in the bonus instruction are also used 1848 // by the terminator of the predecessor. This means that those values 1849 // must already have been resolved, so we won't be inhibiting the 1850 // out-of-order core by speculating them earlier. 1851 if (BonusInst) { 1852 // Collect the values used by the bonus inst 1853 SmallPtrSet<Value*, 4> UsedValues; 1854 for (Instruction::op_iterator OI = BonusInst->op_begin(), 1855 OE = BonusInst->op_end(); OI != OE; ++OI) { 1856 Value *V = *OI; 1857 if (!isa<Constant>(V)) 1858 UsedValues.insert(V); 1859 } 1860 1861 SmallVector<std::pair<Value*, unsigned>, 4> Worklist; 1862 Worklist.push_back(std::make_pair(PBI->getOperand(0), 0)); 1863 1864 // Walk up to four levels back up the use-def chain of the predecessor's 1865 // terminator to see if all those values were used. The choice of four 1866 // levels is arbitrary, to provide a compile-time-cost bound. 1867 while (!Worklist.empty()) { 1868 std::pair<Value*, unsigned> Pair = Worklist.back(); 1869 Worklist.pop_back(); 1870 1871 if (Pair.second >= 4) continue; 1872 UsedValues.erase(Pair.first); 1873 if (UsedValues.empty()) break; 1874 1875 if (Instruction *I = dyn_cast<Instruction>(Pair.first)) { 1876 for (Instruction::op_iterator OI = I->op_begin(), OE = I->op_end(); 1877 OI != OE; ++OI) 1878 Worklist.push_back(std::make_pair(OI->get(), Pair.second+1)); 1879 } 1880 } 1881 1882 if (!UsedValues.empty()) return false; 1883 } 1884 1885 DEBUG(dbgs() << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB); 1886 IRBuilder<> Builder(PBI); 1887 1888 // If we need to invert the condition in the pred block to match, do so now. 1889 if (InvertPredCond) { 1890 Value *NewCond = PBI->getCondition(); 1891 1892 if (NewCond->hasOneUse() && isa<CmpInst>(NewCond)) { 1893 CmpInst *CI = cast<CmpInst>(NewCond); 1894 CI->setPredicate(CI->getInversePredicate()); 1895 } else { 1896 NewCond = Builder.CreateNot(NewCond, 1897 PBI->getCondition()->getName()+".not"); 1898 } 1899 1900 PBI->setCondition(NewCond); 1901 PBI->swapSuccessors(); 1902 } 1903 1904 // If we have a bonus inst, clone it into the predecessor block. 1905 Instruction *NewBonus = 0; 1906 if (BonusInst) { 1907 NewBonus = BonusInst->clone(); 1908 PredBlock->getInstList().insert(PBI, NewBonus); 1909 NewBonus->takeName(BonusInst); 1910 BonusInst->setName(BonusInst->getName()+".old"); 1911 } 1912 1913 // Clone Cond into the predecessor basic block, and or/and the 1914 // two conditions together. 1915 Instruction *New = Cond->clone(); 1916 if (BonusInst) New->replaceUsesOfWith(BonusInst, NewBonus); 1917 PredBlock->getInstList().insert(PBI, New); 1918 New->takeName(Cond); 1919 Cond->setName(New->getName()+".old"); 1920 1921 if (BI->isConditional()) { 1922 Instruction *NewCond = 1923 cast<Instruction>(Builder.CreateBinOp(Opc, PBI->getCondition(), 1924 New, "or.cond")); 1925 PBI->setCondition(NewCond); 1926 1927 if (PBI->getSuccessor(0) == BB) { 1928 AddPredecessorToBlock(TrueDest, PredBlock, BB); 1929 PBI->setSuccessor(0, TrueDest); 1930 } 1931 if (PBI->getSuccessor(1) == BB) { 1932 AddPredecessorToBlock(FalseDest, PredBlock, BB); 1933 PBI->setSuccessor(1, FalseDest); 1934 } 1935 } else { 1936 // Update PHI nodes in the common successors. 1937 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) { 1938 ConstantInt *PBI_C = cast<ConstantInt>( 1939 PHIs[i]->getIncomingValueForBlock(PBI->getParent())); 1940 assert(PBI_C->getType()->isIntegerTy(1)); 1941 Instruction *MergedCond = 0; 1942 if (PBI->getSuccessor(0) == TrueDest) { 1943 // Create (PBI_Cond and PBI_C) or (!PBI_Cond and BI_Value) 1944 // PBI_C is true: PBI_Cond or (!PBI_Cond and BI_Value) 1945 // is false: !PBI_Cond and BI_Value 1946 Instruction *NotCond = 1947 cast<Instruction>(Builder.CreateNot(PBI->getCondition(), 1948 "not.cond")); 1949 MergedCond = 1950 cast<Instruction>(Builder.CreateBinOp(Instruction::And, 1951 NotCond, New, 1952 "and.cond")); 1953 if (PBI_C->isOne()) 1954 MergedCond = 1955 cast<Instruction>(Builder.CreateBinOp(Instruction::Or, 1956 PBI->getCondition(), MergedCond, 1957 "or.cond")); 1958 } else { 1959 // Create (PBI_Cond and BI_Value) or (!PBI_Cond and PBI_C) 1960 // PBI_C is true: (PBI_Cond and BI_Value) or (!PBI_Cond) 1961 // is false: PBI_Cond and BI_Value 1962 MergedCond = 1963 cast<Instruction>(Builder.CreateBinOp(Instruction::And, 1964 PBI->getCondition(), New, 1965 "and.cond")); 1966 if (PBI_C->isOne()) { 1967 Instruction *NotCond = 1968 cast<Instruction>(Builder.CreateNot(PBI->getCondition(), 1969 "not.cond")); 1970 MergedCond = 1971 cast<Instruction>(Builder.CreateBinOp(Instruction::Or, 1972 NotCond, MergedCond, 1973 "or.cond")); 1974 } 1975 } 1976 // Update PHI Node. 1977 PHIs[i]->setIncomingValue(PHIs[i]->getBasicBlockIndex(PBI->getParent()), 1978 MergedCond); 1979 } 1980 // Change PBI from Conditional to Unconditional. 1981 BranchInst *New_PBI = BranchInst::Create(TrueDest, PBI); 1982 EraseTerminatorInstAndDCECond(PBI); 1983 PBI = New_PBI; 1984 } 1985 1986 // TODO: If BB is reachable from all paths through PredBlock, then we 1987 // could replace PBI's branch probabilities with BI's. 1988 1989 // Merge probability data into PredBlock's branch. 1990 APInt A, B, C, D; 1991 if (PBI->isConditional() && BI->isConditional() && 1992 ExtractBranchMetadata(PBI, C, D) && ExtractBranchMetadata(BI, A, B)) { 1993 // Given IR which does: 1994 // bbA: 1995 // br i1 %x, label %bbB, label %bbC 1996 // bbB: 1997 // br i1 %y, label %bbD, label %bbC 1998 // Let's call the probability that we take the edge from %bbA to %bbB 1999 // 'a', from %bbA to %bbC, 'b', from %bbB to %bbD 'c' and from %bbB to 2000 // %bbC probability 'd'. 2001 // 2002 // We transform the IR into: 2003 // bbA: 2004 // br i1 %z, label %bbD, label %bbC 2005 // where the probability of going to %bbD is (a*c) and going to bbC is 2006 // (b+a*d). 2007 // 2008 // Probabilities aren't stored as ratios directly. Using branch weights, 2009 // we get: 2010 // (a*c)% = A*C, (b+(a*d))% = A*D+B*C+B*D. 2011 2012 // In the event of overflow, we want to drop the LSB of the input 2013 // probabilities. 2014 unsigned BitsLost; 2015 2016 // Ignore overflow result on ProbTrue. 2017 APInt ProbTrue = MultiplyAndLosePrecision(A, C, B, D, BitsLost); 2018 2019 APInt Tmp1 = MultiplyAndLosePrecision(B, D, A, C, BitsLost); 2020 if (BitsLost) { 2021 ProbTrue = ProbTrue.lshr(BitsLost*2); 2022 } 2023 2024 APInt Tmp2 = MultiplyAndLosePrecision(A, D, C, B, BitsLost); 2025 if (BitsLost) { 2026 ProbTrue = ProbTrue.lshr(BitsLost*2); 2027 Tmp1 = Tmp1.lshr(BitsLost*2); 2028 } 2029 2030 APInt Tmp3 = MultiplyAndLosePrecision(B, C, A, D, BitsLost); 2031 if (BitsLost) { 2032 ProbTrue = ProbTrue.lshr(BitsLost*2); 2033 Tmp1 = Tmp1.lshr(BitsLost*2); 2034 Tmp2 = Tmp2.lshr(BitsLost*2); 2035 } 2036 2037 bool Overflow1 = false, Overflow2 = false; 2038 APInt Tmp4 = Tmp2.uadd_ov(Tmp3, Overflow1); 2039 APInt ProbFalse = Tmp4.uadd_ov(Tmp1, Overflow2); 2040 2041 if (Overflow1 || Overflow2) { 2042 ProbTrue = ProbTrue.lshr(1); 2043 Tmp1 = Tmp1.lshr(1); 2044 Tmp2 = Tmp2.lshr(1); 2045 Tmp3 = Tmp3.lshr(1); 2046 Tmp4 = Tmp2 + Tmp3; 2047 ProbFalse = Tmp4 + Tmp1; 2048 } 2049 2050 // The sum of branch weights must fit in 32-bits. 2051 if (ProbTrue.isNegative() && ProbFalse.isNegative()) { 2052 ProbTrue = ProbTrue.lshr(1); 2053 ProbFalse = ProbFalse.lshr(1); 2054 } 2055 2056 if (ProbTrue != ProbFalse) { 2057 // Normalize the result. 2058 APInt GCD = APIntOps::GreatestCommonDivisor(ProbTrue, ProbFalse); 2059 ProbTrue = ProbTrue.udiv(GCD); 2060 ProbFalse = ProbFalse.udiv(GCD); 2061 2062 MDBuilder MDB(BI->getContext()); 2063 MDNode *N = MDB.createBranchWeights(ProbTrue.getZExtValue(), 2064 ProbFalse.getZExtValue()); 2065 PBI->setMetadata(LLVMContext::MD_prof, N); 2066 } else { 2067 PBI->setMetadata(LLVMContext::MD_prof, NULL); 2068 } 2069 } else { 2070 PBI->setMetadata(LLVMContext::MD_prof, NULL); 2071 } 2072 2073 // Copy any debug value intrinsics into the end of PredBlock. 2074 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 2075 if (isa<DbgInfoIntrinsic>(*I)) 2076 I->clone()->insertBefore(PBI); 2077 2078 return true; 2079 } 2080 return false; 2081} 2082 2083/// SimplifyCondBranchToCondBranch - If we have a conditional branch as a 2084/// predecessor of another block, this function tries to simplify it. We know 2085/// that PBI and BI are both conditional branches, and BI is in one of the 2086/// successor blocks of PBI - PBI branches to BI. 2087static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { 2088 assert(PBI->isConditional() && BI->isConditional()); 2089 BasicBlock *BB = BI->getParent(); 2090 2091 // If this block ends with a branch instruction, and if there is a 2092 // predecessor that ends on a branch of the same condition, make 2093 // this conditional branch redundant. 2094 if (PBI->getCondition() == BI->getCondition() && 2095 PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 2096 // Okay, the outcome of this conditional branch is statically 2097 // knowable. If this block had a single pred, handle specially. 2098 if (BB->getSinglePredecessor()) { 2099 // Turn this into a branch on constant. 2100 bool CondIsTrue = PBI->getSuccessor(0) == BB; 2101 BI->setCondition(ConstantInt::get(Type::getInt1Ty(BB->getContext()), 2102 CondIsTrue)); 2103 return true; // Nuke the branch on constant. 2104 } 2105 2106 // Otherwise, if there are multiple predecessors, insert a PHI that merges 2107 // in the constant and simplify the block result. Subsequent passes of 2108 // simplifycfg will thread the block. 2109 if (BlockIsSimpleEnoughToThreadThrough(BB)) { 2110 pred_iterator PB = pred_begin(BB), PE = pred_end(BB); 2111 PHINode *NewPN = PHINode::Create(Type::getInt1Ty(BB->getContext()), 2112 std::distance(PB, PE), 2113 BI->getCondition()->getName() + ".pr", 2114 BB->begin()); 2115 // Okay, we're going to insert the PHI node. Since PBI is not the only 2116 // predecessor, compute the PHI'd conditional value for all of the preds. 2117 // Any predecessor where the condition is not computable we keep symbolic. 2118 for (pred_iterator PI = PB; PI != PE; ++PI) { 2119 BasicBlock *P = *PI; 2120 if ((PBI = dyn_cast<BranchInst>(P->getTerminator())) && 2121 PBI != BI && PBI->isConditional() && 2122 PBI->getCondition() == BI->getCondition() && 2123 PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 2124 bool CondIsTrue = PBI->getSuccessor(0) == BB; 2125 NewPN->addIncoming(ConstantInt::get(Type::getInt1Ty(BB->getContext()), 2126 CondIsTrue), P); 2127 } else { 2128 NewPN->addIncoming(BI->getCondition(), P); 2129 } 2130 } 2131 2132 BI->setCondition(NewPN); 2133 return true; 2134 } 2135 } 2136 2137 // If this is a conditional branch in an empty block, and if any 2138 // predecessors is a conditional branch to one of our destinations, 2139 // fold the conditions into logical ops and one cond br. 2140 BasicBlock::iterator BBI = BB->begin(); 2141 // Ignore dbg intrinsics. 2142 while (isa<DbgInfoIntrinsic>(BBI)) 2143 ++BBI; 2144 if (&*BBI != BI) 2145 return false; 2146 2147 2148 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(BI->getCondition())) 2149 if (CE->canTrap()) 2150 return false; 2151 2152 int PBIOp, BIOp; 2153 if (PBI->getSuccessor(0) == BI->getSuccessor(0)) 2154 PBIOp = BIOp = 0; 2155 else if (PBI->getSuccessor(0) == BI->getSuccessor(1)) 2156 PBIOp = 0, BIOp = 1; 2157 else if (PBI->getSuccessor(1) == BI->getSuccessor(0)) 2158 PBIOp = 1, BIOp = 0; 2159 else if (PBI->getSuccessor(1) == BI->getSuccessor(1)) 2160 PBIOp = BIOp = 1; 2161 else 2162 return false; 2163 2164 // Check to make sure that the other destination of this branch 2165 // isn't BB itself. If so, this is an infinite loop that will 2166 // keep getting unwound. 2167 if (PBI->getSuccessor(PBIOp) == BB) 2168 return false; 2169 2170 // Do not perform this transformation if it would require 2171 // insertion of a large number of select instructions. For targets 2172 // without predication/cmovs, this is a big pessimization. 2173 BasicBlock *CommonDest = PBI->getSuccessor(PBIOp); 2174 2175 unsigned NumPhis = 0; 2176 for (BasicBlock::iterator II = CommonDest->begin(); 2177 isa<PHINode>(II); ++II, ++NumPhis) 2178 if (NumPhis > 2) // Disable this xform. 2179 return false; 2180 2181 // Finally, if everything is ok, fold the branches to logical ops. 2182 BasicBlock *OtherDest = BI->getSuccessor(BIOp ^ 1); 2183 2184 DEBUG(dbgs() << "FOLDING BRs:" << *PBI->getParent() 2185 << "AND: " << *BI->getParent()); 2186 2187 2188 // If OtherDest *is* BB, then BB is a basic block with a single conditional 2189 // branch in it, where one edge (OtherDest) goes back to itself but the other 2190 // exits. We don't *know* that the program avoids the infinite loop 2191 // (even though that seems likely). If we do this xform naively, we'll end up 2192 // recursively unpeeling the loop. Since we know that (after the xform is 2193 // done) that the block *is* infinite if reached, we just make it an obviously 2194 // infinite loop with no cond branch. 2195 if (OtherDest == BB) { 2196 // Insert it at the end of the function, because it's either code, 2197 // or it won't matter if it's hot. :) 2198 BasicBlock *InfLoopBlock = BasicBlock::Create(BB->getContext(), 2199 "infloop", BB->getParent()); 2200 BranchInst::Create(InfLoopBlock, InfLoopBlock); 2201 OtherDest = InfLoopBlock; 2202 } 2203 2204 DEBUG(dbgs() << *PBI->getParent()->getParent()); 2205 2206 // BI may have other predecessors. Because of this, we leave 2207 // it alone, but modify PBI. 2208 2209 // Make sure we get to CommonDest on True&True directions. 2210 Value *PBICond = PBI->getCondition(); 2211 IRBuilder<true, NoFolder> Builder(PBI); 2212 if (PBIOp) 2213 PBICond = Builder.CreateNot(PBICond, PBICond->getName()+".not"); 2214 2215 Value *BICond = BI->getCondition(); 2216 if (BIOp) 2217 BICond = Builder.CreateNot(BICond, BICond->getName()+".not"); 2218 2219 // Merge the conditions. 2220 Value *Cond = Builder.CreateOr(PBICond, BICond, "brmerge"); 2221 2222 // Modify PBI to branch on the new condition to the new dests. 2223 PBI->setCondition(Cond); 2224 PBI->setSuccessor(0, CommonDest); 2225 PBI->setSuccessor(1, OtherDest); 2226 2227 // OtherDest may have phi nodes. If so, add an entry from PBI's 2228 // block that are identical to the entries for BI's block. 2229 AddPredecessorToBlock(OtherDest, PBI->getParent(), BB); 2230 2231 // We know that the CommonDest already had an edge from PBI to 2232 // it. If it has PHIs though, the PHIs may have different 2233 // entries for BB and PBI's BB. If so, insert a select to make 2234 // them agree. 2235 PHINode *PN; 2236 for (BasicBlock::iterator II = CommonDest->begin(); 2237 (PN = dyn_cast<PHINode>(II)); ++II) { 2238 Value *BIV = PN->getIncomingValueForBlock(BB); 2239 unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent()); 2240 Value *PBIV = PN->getIncomingValue(PBBIdx); 2241 if (BIV != PBIV) { 2242 // Insert a select in PBI to pick the right value. 2243 Value *NV = cast<SelectInst> 2244 (Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->getName()+".mux")); 2245 PN->setIncomingValue(PBBIdx, NV); 2246 } 2247 } 2248 2249 DEBUG(dbgs() << "INTO: " << *PBI->getParent()); 2250 DEBUG(dbgs() << *PBI->getParent()->getParent()); 2251 2252 // This basic block is probably dead. We know it has at least 2253 // one fewer predecessor. 2254 return true; 2255} 2256 2257// SimplifyTerminatorOnSelect - Simplifies a terminator by replacing it with a 2258// branch to TrueBB if Cond is true or to FalseBB if Cond is false. 2259// Takes care of updating the successors and removing the old terminator. 2260// Also makes sure not to introduce new successors by assuming that edges to 2261// non-successor TrueBBs and FalseBBs aren't reachable. 2262static bool SimplifyTerminatorOnSelect(TerminatorInst *OldTerm, Value *Cond, 2263 BasicBlock *TrueBB, BasicBlock *FalseBB){ 2264 // Remove any superfluous successor edges from the CFG. 2265 // First, figure out which successors to preserve. 2266 // If TrueBB and FalseBB are equal, only try to preserve one copy of that 2267 // successor. 2268 BasicBlock *KeepEdge1 = TrueBB; 2269 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : 0; 2270 2271 // Then remove the rest. 2272 for (unsigned I = 0, E = OldTerm->getNumSuccessors(); I != E; ++I) { 2273 BasicBlock *Succ = OldTerm->getSuccessor(I); 2274 // Make sure only to keep exactly one copy of each edge. 2275 if (Succ == KeepEdge1) 2276 KeepEdge1 = 0; 2277 else if (Succ == KeepEdge2) 2278 KeepEdge2 = 0; 2279 else 2280 Succ->removePredecessor(OldTerm->getParent()); 2281 } 2282 2283 IRBuilder<> Builder(OldTerm); 2284 Builder.SetCurrentDebugLocation(OldTerm->getDebugLoc()); 2285 2286 // Insert an appropriate new terminator. 2287 if ((KeepEdge1 == 0) && (KeepEdge2 == 0)) { 2288 if (TrueBB == FalseBB) 2289 // We were only looking for one successor, and it was present. 2290 // Create an unconditional branch to it. 2291 Builder.CreateBr(TrueBB); 2292 else 2293 // We found both of the successors we were looking for. 2294 // Create a conditional branch sharing the condition of the select. 2295 Builder.CreateCondBr(Cond, TrueBB, FalseBB); 2296 } else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) { 2297 // Neither of the selected blocks were successors, so this 2298 // terminator must be unreachable. 2299 new UnreachableInst(OldTerm->getContext(), OldTerm); 2300 } else { 2301 // One of the selected values was a successor, but the other wasn't. 2302 // Insert an unconditional branch to the one that was found; 2303 // the edge to the one that wasn't must be unreachable. 2304 if (KeepEdge1 == 0) 2305 // Only TrueBB was found. 2306 Builder.CreateBr(TrueBB); 2307 else 2308 // Only FalseBB was found. 2309 Builder.CreateBr(FalseBB); 2310 } 2311 2312 EraseTerminatorInstAndDCECond(OldTerm); 2313 return true; 2314} 2315 2316// SimplifySwitchOnSelect - Replaces 2317// (switch (select cond, X, Y)) on constant X, Y 2318// with a branch - conditional if X and Y lead to distinct BBs, 2319// unconditional otherwise. 2320static bool SimplifySwitchOnSelect(SwitchInst *SI, SelectInst *Select) { 2321 // Check for constant integer values in the select. 2322 ConstantInt *TrueVal = dyn_cast<ConstantInt>(Select->getTrueValue()); 2323 ConstantInt *FalseVal = dyn_cast<ConstantInt>(Select->getFalseValue()); 2324 if (!TrueVal || !FalseVal) 2325 return false; 2326 2327 // Find the relevant condition and destinations. 2328 Value *Condition = Select->getCondition(); 2329 BasicBlock *TrueBB = SI->findCaseValue(TrueVal).getCaseSuccessor(); 2330 BasicBlock *FalseBB = SI->findCaseValue(FalseVal).getCaseSuccessor(); 2331 2332 // Perform the actual simplification. 2333 return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB); 2334} 2335 2336// SimplifyIndirectBrOnSelect - Replaces 2337// (indirectbr (select cond, blockaddress(@fn, BlockA), 2338// blockaddress(@fn, BlockB))) 2339// with 2340// (br cond, BlockA, BlockB). 2341static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) { 2342 // Check that both operands of the select are block addresses. 2343 BlockAddress *TBA = dyn_cast<BlockAddress>(SI->getTrueValue()); 2344 BlockAddress *FBA = dyn_cast<BlockAddress>(SI->getFalseValue()); 2345 if (!TBA || !FBA) 2346 return false; 2347 2348 // Extract the actual blocks. 2349 BasicBlock *TrueBB = TBA->getBasicBlock(); 2350 BasicBlock *FalseBB = FBA->getBasicBlock(); 2351 2352 // Perform the actual simplification. 2353 return SimplifyTerminatorOnSelect(IBI, SI->getCondition(), TrueBB, FalseBB); 2354} 2355 2356/// TryToSimplifyUncondBranchWithICmpInIt - This is called when we find an icmp 2357/// instruction (a seteq/setne with a constant) as the only instruction in a 2358/// block that ends with an uncond branch. We are looking for a very specific 2359/// pattern that occurs when "A == 1 || A == 2 || A == 3" gets simplified. In 2360/// this case, we merge the first two "or's of icmp" into a switch, but then the 2361/// default value goes to an uncond block with a seteq in it, we get something 2362/// like: 2363/// 2364/// switch i8 %A, label %DEFAULT [ i8 1, label %end i8 2, label %end ] 2365/// DEFAULT: 2366/// %tmp = icmp eq i8 %A, 92 2367/// br label %end 2368/// end: 2369/// ... = phi i1 [ true, %entry ], [ %tmp, %DEFAULT ], [ true, %entry ] 2370/// 2371/// We prefer to split the edge to 'end' so that there is a true/false entry to 2372/// the PHI, merging the third icmp into the switch. 2373static bool TryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI, 2374 const TargetData *TD, 2375 IRBuilder<> &Builder) { 2376 BasicBlock *BB = ICI->getParent(); 2377 2378 // If the block has any PHIs in it or the icmp has multiple uses, it is too 2379 // complex. 2380 if (isa<PHINode>(BB->begin()) || !ICI->hasOneUse()) return false; 2381 2382 Value *V = ICI->getOperand(0); 2383 ConstantInt *Cst = cast<ConstantInt>(ICI->getOperand(1)); 2384 2385 // The pattern we're looking for is where our only predecessor is a switch on 2386 // 'V' and this block is the default case for the switch. In this case we can 2387 // fold the compared value into the switch to simplify things. 2388 BasicBlock *Pred = BB->getSinglePredecessor(); 2389 if (Pred == 0 || !isa<SwitchInst>(Pred->getTerminator())) return false; 2390 2391 SwitchInst *SI = cast<SwitchInst>(Pred->getTerminator()); 2392 if (SI->getCondition() != V) 2393 return false; 2394 2395 // If BB is reachable on a non-default case, then we simply know the value of 2396 // V in this block. Substitute it and constant fold the icmp instruction 2397 // away. 2398 if (SI->getDefaultDest() != BB) { 2399 ConstantInt *VVal = SI->findCaseDest(BB); 2400 assert(VVal && "Should have a unique destination value"); 2401 ICI->setOperand(0, VVal); 2402 2403 if (Value *V = SimplifyInstruction(ICI, TD)) { 2404 ICI->replaceAllUsesWith(V); 2405 ICI->eraseFromParent(); 2406 } 2407 // BB is now empty, so it is likely to simplify away. 2408 return SimplifyCFG(BB) | true; 2409 } 2410 2411 // Ok, the block is reachable from the default dest. If the constant we're 2412 // comparing exists in one of the other edges, then we can constant fold ICI 2413 // and zap it. 2414 if (SI->findCaseValue(Cst) != SI->case_default()) { 2415 Value *V; 2416 if (ICI->getPredicate() == ICmpInst::ICMP_EQ) 2417 V = ConstantInt::getFalse(BB->getContext()); 2418 else 2419 V = ConstantInt::getTrue(BB->getContext()); 2420 2421 ICI->replaceAllUsesWith(V); 2422 ICI->eraseFromParent(); 2423 // BB is now empty, so it is likely to simplify away. 2424 return SimplifyCFG(BB) | true; 2425 } 2426 2427 // The use of the icmp has to be in the 'end' block, by the only PHI node in 2428 // the block. 2429 BasicBlock *SuccBlock = BB->getTerminator()->getSuccessor(0); 2430 PHINode *PHIUse = dyn_cast<PHINode>(ICI->use_back()); 2431 if (PHIUse == 0 || PHIUse != &SuccBlock->front() || 2432 isa<PHINode>(++BasicBlock::iterator(PHIUse))) 2433 return false; 2434 2435 // If the icmp is a SETEQ, then the default dest gets false, the new edge gets 2436 // true in the PHI. 2437 Constant *DefaultCst = ConstantInt::getTrue(BB->getContext()); 2438 Constant *NewCst = ConstantInt::getFalse(BB->getContext()); 2439 2440 if (ICI->getPredicate() == ICmpInst::ICMP_EQ) 2441 std::swap(DefaultCst, NewCst); 2442 2443 // Replace ICI (which is used by the PHI for the default value) with true or 2444 // false depending on if it is EQ or NE. 2445 ICI->replaceAllUsesWith(DefaultCst); 2446 ICI->eraseFromParent(); 2447 2448 // Okay, the switch goes to this block on a default value. Add an edge from 2449 // the switch to the merge point on the compared value. 2450 BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "switch.edge", 2451 BB->getParent(), BB); 2452 SI->addCase(Cst, NewBB); 2453 2454 // NewBB branches to the phi block, add the uncond branch and the phi entry. 2455 Builder.SetInsertPoint(NewBB); 2456 Builder.SetCurrentDebugLocation(SI->getDebugLoc()); 2457 Builder.CreateBr(SuccBlock); 2458 PHIUse->addIncoming(NewCst, NewBB); 2459 return true; 2460} 2461 2462/// SimplifyBranchOnICmpChain - The specified branch is a conditional branch. 2463/// Check to see if it is branching on an or/and chain of icmp instructions, and 2464/// fold it into a switch instruction if so. 2465static bool SimplifyBranchOnICmpChain(BranchInst *BI, const TargetData *TD, 2466 IRBuilder<> &Builder) { 2467 Instruction *Cond = dyn_cast<Instruction>(BI->getCondition()); 2468 if (Cond == 0) return false; 2469 2470 2471 // Change br (X == 0 | X == 1), T, F into a switch instruction. 2472 // If this is a bunch of seteq's or'd together, or if it's a bunch of 2473 // 'setne's and'ed together, collect them. 2474 Value *CompVal = 0; 2475 std::vector<ConstantInt*> Values; 2476 bool TrueWhenEqual = true; 2477 Value *ExtraCase = 0; 2478 unsigned UsedICmps = 0; 2479 2480 if (Cond->getOpcode() == Instruction::Or) { 2481 CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, true, 2482 UsedICmps); 2483 } else if (Cond->getOpcode() == Instruction::And) { 2484 CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, false, 2485 UsedICmps); 2486 TrueWhenEqual = false; 2487 } 2488 2489 // If we didn't have a multiply compared value, fail. 2490 if (CompVal == 0) return false; 2491 2492 // Avoid turning single icmps into a switch. 2493 if (UsedICmps <= 1) 2494 return false; 2495 2496 // There might be duplicate constants in the list, which the switch 2497 // instruction can't handle, remove them now. 2498 array_pod_sort(Values.begin(), Values.end(), ConstantIntSortPredicate); 2499 Values.erase(std::unique(Values.begin(), Values.end()), Values.end()); 2500 2501 // If Extra was used, we require at least two switch values to do the 2502 // transformation. A switch with one value is just an cond branch. 2503 if (ExtraCase && Values.size() < 2) return false; 2504 2505 // TODO: Preserve branch weight metadata, similarly to how 2506 // FoldValueComparisonIntoPredecessors preserves it. 2507 2508 // Figure out which block is which destination. 2509 BasicBlock *DefaultBB = BI->getSuccessor(1); 2510 BasicBlock *EdgeBB = BI->getSuccessor(0); 2511 if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB); 2512 2513 BasicBlock *BB = BI->getParent(); 2514 2515 DEBUG(dbgs() << "Converting 'icmp' chain with " << Values.size() 2516 << " cases into SWITCH. BB is:\n" << *BB); 2517 2518 // If there are any extra values that couldn't be folded into the switch 2519 // then we evaluate them with an explicit branch first. Split the block 2520 // right before the condbr to handle it. 2521 if (ExtraCase) { 2522 BasicBlock *NewBB = BB->splitBasicBlock(BI, "switch.early.test"); 2523 // Remove the uncond branch added to the old block. 2524 TerminatorInst *OldTI = BB->getTerminator(); 2525 Builder.SetInsertPoint(OldTI); 2526 2527 if (TrueWhenEqual) 2528 Builder.CreateCondBr(ExtraCase, EdgeBB, NewBB); 2529 else 2530 Builder.CreateCondBr(ExtraCase, NewBB, EdgeBB); 2531 2532 OldTI->eraseFromParent(); 2533 2534 // If there are PHI nodes in EdgeBB, then we need to add a new entry to them 2535 // for the edge we just added. 2536 AddPredecessorToBlock(EdgeBB, BB, NewBB); 2537 2538 DEBUG(dbgs() << " ** 'icmp' chain unhandled condition: " << *ExtraCase 2539 << "\nEXTRABB = " << *BB); 2540 BB = NewBB; 2541 } 2542 2543 Builder.SetInsertPoint(BI); 2544 // Convert pointer to int before we switch. 2545 if (CompVal->getType()->isPointerTy()) { 2546 assert(TD && "Cannot switch on pointer without TargetData"); 2547 CompVal = Builder.CreatePtrToInt(CompVal, 2548 TD->getIntPtrType(CompVal->getContext()), 2549 "magicptr"); 2550 } 2551 2552 // Create the new switch instruction now. 2553 SwitchInst *New = Builder.CreateSwitch(CompVal, DefaultBB, Values.size()); 2554 2555 // Add all of the 'cases' to the switch instruction. 2556 for (unsigned i = 0, e = Values.size(); i != e; ++i) 2557 New->addCase(Values[i], EdgeBB); 2558 2559 // We added edges from PI to the EdgeBB. As such, if there were any 2560 // PHI nodes in EdgeBB, they need entries to be added corresponding to 2561 // the number of edges added. 2562 for (BasicBlock::iterator BBI = EdgeBB->begin(); 2563 isa<PHINode>(BBI); ++BBI) { 2564 PHINode *PN = cast<PHINode>(BBI); 2565 Value *InVal = PN->getIncomingValueForBlock(BB); 2566 for (unsigned i = 0, e = Values.size()-1; i != e; ++i) 2567 PN->addIncoming(InVal, BB); 2568 } 2569 2570 // Erase the old branch instruction. 2571 EraseTerminatorInstAndDCECond(BI); 2572 2573 DEBUG(dbgs() << " ** 'icmp' chain result is:\n" << *BB << '\n'); 2574 return true; 2575} 2576 2577bool SimplifyCFGOpt::SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder) { 2578 // If this is a trivial landing pad that just continues unwinding the caught 2579 // exception then zap the landing pad, turning its invokes into calls. 2580 BasicBlock *BB = RI->getParent(); 2581 LandingPadInst *LPInst = dyn_cast<LandingPadInst>(BB->getFirstNonPHI()); 2582 if (RI->getValue() != LPInst) 2583 // Not a landing pad, or the resume is not unwinding the exception that 2584 // caused control to branch here. 2585 return false; 2586 2587 // Check that there are no other instructions except for debug intrinsics. 2588 BasicBlock::iterator I = LPInst, E = RI; 2589 while (++I != E) 2590 if (!isa<DbgInfoIntrinsic>(I)) 2591 return false; 2592 2593 // Turn all invokes that unwind here into calls and delete the basic block. 2594 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;) { 2595 InvokeInst *II = cast<InvokeInst>((*PI++)->getTerminator()); 2596 SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3); 2597 // Insert a call instruction before the invoke. 2598 CallInst *Call = CallInst::Create(II->getCalledValue(), Args, "", II); 2599 Call->takeName(II); 2600 Call->setCallingConv(II->getCallingConv()); 2601 Call->setAttributes(II->getAttributes()); 2602 Call->setDebugLoc(II->getDebugLoc()); 2603 2604 // Anything that used the value produced by the invoke instruction now uses 2605 // the value produced by the call instruction. Note that we do this even 2606 // for void functions and calls with no uses so that the callgraph edge is 2607 // updated. 2608 II->replaceAllUsesWith(Call); 2609 BB->removePredecessor(II->getParent()); 2610 2611 // Insert a branch to the normal destination right before the invoke. 2612 BranchInst::Create(II->getNormalDest(), II); 2613 2614 // Finally, delete the invoke instruction! 2615 II->eraseFromParent(); 2616 } 2617 2618 // The landingpad is now unreachable. Zap it. 2619 BB->eraseFromParent(); 2620 return true; 2621} 2622 2623bool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder) { 2624 BasicBlock *BB = RI->getParent(); 2625 if (!BB->getFirstNonPHIOrDbg()->isTerminator()) return false; 2626 2627 // Find predecessors that end with branches. 2628 SmallVector<BasicBlock*, 8> UncondBranchPreds; 2629 SmallVector<BranchInst*, 8> CondBranchPreds; 2630 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 2631 BasicBlock *P = *PI; 2632 TerminatorInst *PTI = P->getTerminator(); 2633 if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) { 2634 if (BI->isUnconditional()) 2635 UncondBranchPreds.push_back(P); 2636 else 2637 CondBranchPreds.push_back(BI); 2638 } 2639 } 2640 2641 // If we found some, do the transformation! 2642 if (!UncondBranchPreds.empty() && DupRet) { 2643 while (!UncondBranchPreds.empty()) { 2644 BasicBlock *Pred = UncondBranchPreds.pop_back_val(); 2645 DEBUG(dbgs() << "FOLDING: " << *BB 2646 << "INTO UNCOND BRANCH PRED: " << *Pred); 2647 (void)FoldReturnIntoUncondBranch(RI, BB, Pred); 2648 } 2649 2650 // If we eliminated all predecessors of the block, delete the block now. 2651 if (pred_begin(BB) == pred_end(BB)) 2652 // We know there are no successors, so just nuke the block. 2653 BB->eraseFromParent(); 2654 2655 return true; 2656 } 2657 2658 // Check out all of the conditional branches going to this return 2659 // instruction. If any of them just select between returns, change the 2660 // branch itself into a select/return pair. 2661 while (!CondBranchPreds.empty()) { 2662 BranchInst *BI = CondBranchPreds.pop_back_val(); 2663 2664 // Check to see if the non-BB successor is also a return block. 2665 if (isa<ReturnInst>(BI->getSuccessor(0)->getTerminator()) && 2666 isa<ReturnInst>(BI->getSuccessor(1)->getTerminator()) && 2667 SimplifyCondBranchToTwoReturns(BI, Builder)) 2668 return true; 2669 } 2670 return false; 2671} 2672 2673bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) { 2674 BasicBlock *BB = UI->getParent(); 2675 2676 bool Changed = false; 2677 2678 // If there are any instructions immediately before the unreachable that can 2679 // be removed, do so. 2680 while (UI != BB->begin()) { 2681 BasicBlock::iterator BBI = UI; 2682 --BBI; 2683 // Do not delete instructions that can have side effects which might cause 2684 // the unreachable to not be reachable; specifically, calls and volatile 2685 // operations may have this effect. 2686 if (isa<CallInst>(BBI) && !isa<DbgInfoIntrinsic>(BBI)) break; 2687 2688 if (BBI->mayHaveSideEffects()) { 2689 if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) { 2690 if (SI->isVolatile()) 2691 break; 2692 } else if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) { 2693 if (LI->isVolatile()) 2694 break; 2695 } else if (AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(BBI)) { 2696 if (RMWI->isVolatile()) 2697 break; 2698 } else if (AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(BBI)) { 2699 if (CXI->isVolatile()) 2700 break; 2701 } else if (!isa<FenceInst>(BBI) && !isa<VAArgInst>(BBI) && 2702 !isa<LandingPadInst>(BBI)) { 2703 break; 2704 } 2705 // Note that deleting LandingPad's here is in fact okay, although it 2706 // involves a bit of subtle reasoning. If this inst is a LandingPad, 2707 // all the predecessors of this block will be the unwind edges of Invokes, 2708 // and we can therefore guarantee this block will be erased. 2709 } 2710 2711 // Delete this instruction (any uses are guaranteed to be dead) 2712 if (!BBI->use_empty()) 2713 BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); 2714 BBI->eraseFromParent(); 2715 Changed = true; 2716 } 2717 2718 // If the unreachable instruction is the first in the block, take a gander 2719 // at all of the predecessors of this instruction, and simplify them. 2720 if (&BB->front() != UI) return Changed; 2721 2722 SmallVector<BasicBlock*, 8> Preds(pred_begin(BB), pred_end(BB)); 2723 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 2724 TerminatorInst *TI = Preds[i]->getTerminator(); 2725 IRBuilder<> Builder(TI); 2726 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 2727 if (BI->isUnconditional()) { 2728 if (BI->getSuccessor(0) == BB) { 2729 new UnreachableInst(TI->getContext(), TI); 2730 TI->eraseFromParent(); 2731 Changed = true; 2732 } 2733 } else { 2734 if (BI->getSuccessor(0) == BB) { 2735 Builder.CreateBr(BI->getSuccessor(1)); 2736 EraseTerminatorInstAndDCECond(BI); 2737 } else if (BI->getSuccessor(1) == BB) { 2738 Builder.CreateBr(BI->getSuccessor(0)); 2739 EraseTerminatorInstAndDCECond(BI); 2740 Changed = true; 2741 } 2742 } 2743 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 2744 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); 2745 i != e; ++i) 2746 if (i.getCaseSuccessor() == BB) { 2747 BB->removePredecessor(SI->getParent()); 2748 SI->removeCase(i); 2749 --i; --e; 2750 Changed = true; 2751 } 2752 // If the default value is unreachable, figure out the most popular 2753 // destination and make it the default. 2754 if (SI->getDefaultDest() == BB) { 2755 std::map<BasicBlock*, std::pair<unsigned, unsigned> > Popularity; 2756 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); 2757 i != e; ++i) { 2758 std::pair<unsigned, unsigned> &entry = 2759 Popularity[i.getCaseSuccessor()]; 2760 if (entry.first == 0) { 2761 entry.first = 1; 2762 entry.second = i.getCaseIndex(); 2763 } else { 2764 entry.first++; 2765 } 2766 } 2767 2768 // Find the most popular block. 2769 unsigned MaxPop = 0; 2770 unsigned MaxIndex = 0; 2771 BasicBlock *MaxBlock = 0; 2772 for (std::map<BasicBlock*, std::pair<unsigned, unsigned> >::iterator 2773 I = Popularity.begin(), E = Popularity.end(); I != E; ++I) { 2774 if (I->second.first > MaxPop || 2775 (I->second.first == MaxPop && MaxIndex > I->second.second)) { 2776 MaxPop = I->second.first; 2777 MaxIndex = I->second.second; 2778 MaxBlock = I->first; 2779 } 2780 } 2781 if (MaxBlock) { 2782 // Make this the new default, allowing us to delete any explicit 2783 // edges to it. 2784 SI->setDefaultDest(MaxBlock); 2785 Changed = true; 2786 2787 // If MaxBlock has phinodes in it, remove MaxPop-1 entries from 2788 // it. 2789 if (isa<PHINode>(MaxBlock->begin())) 2790 for (unsigned i = 0; i != MaxPop-1; ++i) 2791 MaxBlock->removePredecessor(SI->getParent()); 2792 2793 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); 2794 i != e; ++i) 2795 if (i.getCaseSuccessor() == MaxBlock) { 2796 SI->removeCase(i); 2797 --i; --e; 2798 } 2799 } 2800 } 2801 } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) { 2802 if (II->getUnwindDest() == BB) { 2803 // Convert the invoke to a call instruction. This would be a good 2804 // place to note that the call does not throw though. 2805 BranchInst *BI = Builder.CreateBr(II->getNormalDest()); 2806 II->removeFromParent(); // Take out of symbol table 2807 2808 // Insert the call now... 2809 SmallVector<Value*, 8> Args(II->op_begin(), II->op_end()-3); 2810 Builder.SetInsertPoint(BI); 2811 CallInst *CI = Builder.CreateCall(II->getCalledValue(), 2812 Args, II->getName()); 2813 CI->setCallingConv(II->getCallingConv()); 2814 CI->setAttributes(II->getAttributes()); 2815 // If the invoke produced a value, the call does now instead. 2816 II->replaceAllUsesWith(CI); 2817 delete II; 2818 Changed = true; 2819 } 2820 } 2821 } 2822 2823 // If this block is now dead, remove it. 2824 if (pred_begin(BB) == pred_end(BB) && 2825 BB != &BB->getParent()->getEntryBlock()) { 2826 // We know there are no successors, so just nuke the block. 2827 BB->eraseFromParent(); 2828 return true; 2829 } 2830 2831 return Changed; 2832} 2833 2834/// TurnSwitchRangeIntoICmp - Turns a switch with that contains only a 2835/// integer range comparison into a sub, an icmp and a branch. 2836static bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder) { 2837 assert(SI->getNumCases() > 1 && "Degenerate switch?"); 2838 2839 // Make sure all cases point to the same destination and gather the values. 2840 SmallVector<ConstantInt *, 16> Cases; 2841 SwitchInst::CaseIt I = SI->case_begin(); 2842 Cases.push_back(I.getCaseValue()); 2843 SwitchInst::CaseIt PrevI = I++; 2844 for (SwitchInst::CaseIt E = SI->case_end(); I != E; PrevI = I++) { 2845 if (PrevI.getCaseSuccessor() != I.getCaseSuccessor()) 2846 return false; 2847 Cases.push_back(I.getCaseValue()); 2848 } 2849 assert(Cases.size() == SI->getNumCases() && "Not all cases gathered"); 2850 2851 // Sort the case values, then check if they form a range we can transform. 2852 array_pod_sort(Cases.begin(), Cases.end(), ConstantIntSortPredicate); 2853 for (unsigned I = 1, E = Cases.size(); I != E; ++I) { 2854 if (Cases[I-1]->getValue() != Cases[I]->getValue()+1) 2855 return false; 2856 } 2857 2858 Constant *Offset = ConstantExpr::getNeg(Cases.back()); 2859 Constant *NumCases = ConstantInt::get(Offset->getType(), SI->getNumCases()); 2860 2861 Value *Sub = SI->getCondition(); 2862 if (!Offset->isNullValue()) 2863 Sub = Builder.CreateAdd(Sub, Offset, Sub->getName()+".off"); 2864 Value *Cmp = Builder.CreateICmpULT(Sub, NumCases, "switch"); 2865 Builder.CreateCondBr( 2866 Cmp, SI->case_begin().getCaseSuccessor(), SI->getDefaultDest()); 2867 2868 // Prune obsolete incoming values off the successor's PHI nodes. 2869 for (BasicBlock::iterator BBI = SI->case_begin().getCaseSuccessor()->begin(); 2870 isa<PHINode>(BBI); ++BBI) { 2871 for (unsigned I = 0, E = SI->getNumCases()-1; I != E; ++I) 2872 cast<PHINode>(BBI)->removeIncomingValue(SI->getParent()); 2873 } 2874 SI->eraseFromParent(); 2875 2876 return true; 2877} 2878 2879/// EliminateDeadSwitchCases - Compute masked bits for the condition of a switch 2880/// and use it to remove dead cases. 2881static bool EliminateDeadSwitchCases(SwitchInst *SI) { 2882 Value *Cond = SI->getCondition(); 2883 unsigned Bits = cast<IntegerType>(Cond->getType())->getBitWidth(); 2884 APInt KnownZero(Bits, 0), KnownOne(Bits, 0); 2885 ComputeMaskedBits(Cond, KnownZero, KnownOne); 2886 2887 // Gather dead cases. 2888 SmallVector<ConstantInt*, 8> DeadCases; 2889 for (SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end(); I != E; ++I) { 2890 if ((I.getCaseValue()->getValue() & KnownZero) != 0 || 2891 (I.getCaseValue()->getValue() & KnownOne) != KnownOne) { 2892 DeadCases.push_back(I.getCaseValue()); 2893 DEBUG(dbgs() << "SimplifyCFG: switch case '" 2894 << I.getCaseValue() << "' is dead.\n"); 2895 } 2896 } 2897 2898 // Remove dead cases from the switch. 2899 for (unsigned I = 0, E = DeadCases.size(); I != E; ++I) { 2900 SwitchInst::CaseIt Case = SI->findCaseValue(DeadCases[I]); 2901 assert(Case != SI->case_default() && 2902 "Case was not found. Probably mistake in DeadCases forming."); 2903 // Prune unused values from PHI nodes. 2904 Case.getCaseSuccessor()->removePredecessor(SI->getParent()); 2905 SI->removeCase(Case); 2906 } 2907 2908 return !DeadCases.empty(); 2909} 2910 2911/// FindPHIForConditionForwarding - If BB would be eligible for simplification 2912/// by TryToSimplifyUncondBranchFromEmptyBlock (i.e. it is empty and terminated 2913/// by an unconditional branch), look at the phi node for BB in the successor 2914/// block and see if the incoming value is equal to CaseValue. If so, return 2915/// the phi node, and set PhiIndex to BB's index in the phi node. 2916static PHINode *FindPHIForConditionForwarding(ConstantInt *CaseValue, 2917 BasicBlock *BB, 2918 int *PhiIndex) { 2919 if (BB->getFirstNonPHIOrDbg() != BB->getTerminator()) 2920 return NULL; // BB must be empty to be a candidate for simplification. 2921 if (!BB->getSinglePredecessor()) 2922 return NULL; // BB must be dominated by the switch. 2923 2924 BranchInst *Branch = dyn_cast<BranchInst>(BB->getTerminator()); 2925 if (!Branch || !Branch->isUnconditional()) 2926 return NULL; // Terminator must be unconditional branch. 2927 2928 BasicBlock *Succ = Branch->getSuccessor(0); 2929 2930 BasicBlock::iterator I = Succ->begin(); 2931 while (PHINode *PHI = dyn_cast<PHINode>(I++)) { 2932 int Idx = PHI->getBasicBlockIndex(BB); 2933 assert(Idx >= 0 && "PHI has no entry for predecessor?"); 2934 2935 Value *InValue = PHI->getIncomingValue(Idx); 2936 if (InValue != CaseValue) continue; 2937 2938 *PhiIndex = Idx; 2939 return PHI; 2940 } 2941 2942 return NULL; 2943} 2944 2945/// ForwardSwitchConditionToPHI - Try to forward the condition of a switch 2946/// instruction to a phi node dominated by the switch, if that would mean that 2947/// some of the destination blocks of the switch can be folded away. 2948/// Returns true if a change is made. 2949static bool ForwardSwitchConditionToPHI(SwitchInst *SI) { 2950 typedef DenseMap<PHINode*, SmallVector<int,4> > ForwardingNodesMap; 2951 ForwardingNodesMap ForwardingNodes; 2952 2953 for (SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end(); I != E; ++I) { 2954 ConstantInt *CaseValue = I.getCaseValue(); 2955 BasicBlock *CaseDest = I.getCaseSuccessor(); 2956 2957 int PhiIndex; 2958 PHINode *PHI = FindPHIForConditionForwarding(CaseValue, CaseDest, 2959 &PhiIndex); 2960 if (!PHI) continue; 2961 2962 ForwardingNodes[PHI].push_back(PhiIndex); 2963 } 2964 2965 bool Changed = false; 2966 2967 for (ForwardingNodesMap::iterator I = ForwardingNodes.begin(), 2968 E = ForwardingNodes.end(); I != E; ++I) { 2969 PHINode *Phi = I->first; 2970 SmallVector<int,4> &Indexes = I->second; 2971 2972 if (Indexes.size() < 2) continue; 2973 2974 for (size_t I = 0, E = Indexes.size(); I != E; ++I) 2975 Phi->setIncomingValue(Indexes[I], SI->getCondition()); 2976 Changed = true; 2977 } 2978 2979 return Changed; 2980} 2981 2982/// ValidLookupTableConstant - Return true if the backend will be able to handle 2983/// initializing an array of constants like C. 2984bool ValidLookupTableConstant(Constant *C) { 2985 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) 2986 return CE->isGEPWithNoNotionalOverIndexing(); 2987 2988 return isa<ConstantFP>(C) || 2989 isa<ConstantInt>(C) || 2990 isa<ConstantPointerNull>(C) || 2991 isa<GlobalValue>(C) || 2992 isa<UndefValue>(C); 2993} 2994 2995/// GetCaseResulsts - Try to determine the resulting constant values in phi 2996/// nodes at the common destination basic block for one of the case 2997/// destinations of a switch instruction. 2998static bool GetCaseResults(SwitchInst *SI, 2999 BasicBlock *CaseDest, 3000 BasicBlock **CommonDest, 3001 SmallVector<std::pair<PHINode*,Constant*>, 4> &Res) { 3002 // The block from which we enter the common destination. 3003 BasicBlock *Pred = SI->getParent(); 3004 3005 // If CaseDest is empty, continue to its successor. 3006 if (CaseDest->getFirstNonPHIOrDbg() == CaseDest->getTerminator() && 3007 !isa<PHINode>(CaseDest->begin())) { 3008 3009 TerminatorInst *Terminator = CaseDest->getTerminator(); 3010 if (Terminator->getNumSuccessors() != 1) 3011 return false; 3012 3013 Pred = CaseDest; 3014 CaseDest = Terminator->getSuccessor(0); 3015 } 3016 3017 // If we did not have a CommonDest before, use the current one. 3018 if (!*CommonDest) 3019 *CommonDest = CaseDest; 3020 // If the destination isn't the common one, abort. 3021 if (CaseDest != *CommonDest) 3022 return false; 3023 3024 // Get the values for this case from phi nodes in the destination block. 3025 BasicBlock::iterator I = (*CommonDest)->begin(); 3026 while (PHINode *PHI = dyn_cast<PHINode>(I++)) { 3027 int Idx = PHI->getBasicBlockIndex(Pred); 3028 if (Idx == -1) 3029 continue; 3030 3031 Constant *ConstVal = dyn_cast<Constant>(PHI->getIncomingValue(Idx)); 3032 if (!ConstVal) 3033 return false; 3034 3035 // Be conservative about which kinds of constants we support. 3036 if (!ValidLookupTableConstant(ConstVal)) 3037 return false; 3038 3039 Res.push_back(std::make_pair(PHI, ConstVal)); 3040 } 3041 3042 return true; 3043} 3044 3045/// BuildLookupTable - Build a lookup table with the contents of Results, using 3046/// DefaultResult to fill the holes in the table. If the table ends up 3047/// containing the same result in each element, set *SingleResult to that value 3048/// and return NULL. 3049static GlobalVariable *BuildLookupTable( 3050 Module &M, 3051 uint64_t TableSize, 3052 ConstantInt *Offset, 3053 const std::vector<std::pair<ConstantInt*,Constant*> >& Results, 3054 Constant *DefaultResult, 3055 Constant **SingleResult) { 3056 assert(Results.size() && "Need values to build lookup table"); 3057 assert(TableSize >= Results.size() && "Table needs to hold all values"); 3058 3059 // If all values in the table are equal, this is that value. 3060 Constant *SameResult = Results.begin()->second; 3061 3062 // Build up the table contents. 3063 std::vector<Constant*> TableContents(TableSize); 3064 for (size_t I = 0, E = Results.size(); I != E; ++I) { 3065 ConstantInt *CaseVal = Results[I].first; 3066 Constant *CaseRes = Results[I].second; 3067 3068 uint64_t Idx = (CaseVal->getValue() - Offset->getValue()).getLimitedValue(); 3069 TableContents[Idx] = CaseRes; 3070 3071 if (CaseRes != SameResult) 3072 SameResult = NULL; 3073 } 3074 3075 // Fill in any holes in the table with the default result. 3076 if (Results.size() < TableSize) { 3077 for (unsigned i = 0; i < TableSize; ++i) { 3078 if (!TableContents[i]) 3079 TableContents[i] = DefaultResult; 3080 } 3081 3082 if (DefaultResult != SameResult) 3083 SameResult = NULL; 3084 } 3085 3086 // Same result was used in the entire table; just return that. 3087 if (SameResult) { 3088 *SingleResult = SameResult; 3089 return NULL; 3090 } 3091 3092 ArrayType *ArrayTy = ArrayType::get(DefaultResult->getType(), TableSize); 3093 Constant *Initializer = ConstantArray::get(ArrayTy, TableContents); 3094 3095 GlobalVariable *GV = new GlobalVariable(M, ArrayTy, /*constant=*/ true, 3096 GlobalVariable::PrivateLinkage, 3097 Initializer, 3098 "switch.table"); 3099 GV->setUnnamedAddr(true); 3100 return GV; 3101} 3102 3103/// SwitchToLookupTable - If the switch is only used to initialize one or more 3104/// phi nodes in a common successor block with different constant values, 3105/// replace the switch with lookup tables. 3106static bool SwitchToLookupTable(SwitchInst *SI, 3107 IRBuilder<> &Builder) { 3108 assert(SI->getNumCases() > 1 && "Degenerate switch?"); 3109 // FIXME: Handle unreachable cases. 3110 3111 // FIXME: If the switch is too sparse for a lookup table, perhaps we could 3112 // split off a dense part and build a lookup table for that. 3113 3114 // FIXME: If the results are all integers and the lookup table would fit in a 3115 // target-legal register, we should store them as a bitmap and use shift/mask 3116 // to look up the result. 3117 3118 // FIXME: This creates arrays of GEPs to constant strings, which means each 3119 // GEP needs a runtime relocation in PIC code. We should just build one big 3120 // string and lookup indices into that. 3121 3122 // Ignore the switch if the number of cases are too small. 3123 // This is similar to the check when building jump tables in 3124 // SelectionDAGBuilder::handleJTSwitchCase. 3125 // FIXME: Determine the best cut-off. 3126 if (SI->getNumCases() < 4) 3127 return false; 3128 3129 // Figure out the corresponding result for each case value and phi node in the 3130 // common destination, as well as the the min and max case values. 3131 assert(SI->case_begin() != SI->case_end()); 3132 SwitchInst::CaseIt CI = SI->case_begin(); 3133 ConstantInt *MinCaseVal = CI.getCaseValue(); 3134 ConstantInt *MaxCaseVal = CI.getCaseValue(); 3135 3136 BasicBlock *CommonDest = NULL; 3137 typedef std::vector<std::pair<ConstantInt*, Constant*> > ResultListTy; 3138 SmallDenseMap<PHINode*, ResultListTy> ResultLists; 3139 SmallDenseMap<PHINode*, Constant*> DefaultResults; 3140 SmallDenseMap<PHINode*, Type*> ResultTypes; 3141 SmallVector<PHINode*, 4> PHIs; 3142 3143 for (SwitchInst::CaseIt E = SI->case_end(); CI != E; ++CI) { 3144 ConstantInt *CaseVal = CI.getCaseValue(); 3145 if (CaseVal->getValue().slt(MinCaseVal->getValue())) 3146 MinCaseVal = CaseVal; 3147 if (CaseVal->getValue().sgt(MaxCaseVal->getValue())) 3148 MaxCaseVal = CaseVal; 3149 3150 // Resulting value at phi nodes for this case value. 3151 typedef SmallVector<std::pair<PHINode*, Constant*>, 4> ResultsTy; 3152 ResultsTy Results; 3153 if (!GetCaseResults(SI, CI.getCaseSuccessor(), &CommonDest, Results)) 3154 return false; 3155 3156 // Append the result from this case to the list for each phi. 3157 for (ResultsTy::iterator I = Results.begin(), E = Results.end(); I!=E; ++I) { 3158 if (!ResultLists.count(I->first)) 3159 PHIs.push_back(I->first); 3160 ResultLists[I->first].push_back(std::make_pair(CaseVal, I->second)); 3161 } 3162 } 3163 3164 // Get the resulting values for the default case. 3165 { 3166 SmallVector<std::pair<PHINode*, Constant*>, 4> DefaultResultsList; 3167 if (!GetCaseResults(SI, SI->getDefaultDest(), &CommonDest, DefaultResultsList)) 3168 return false; 3169 for (size_t I = 0, E = DefaultResultsList.size(); I != E; ++I) { 3170 PHINode *PHI = DefaultResultsList[I].first; 3171 Constant *Result = DefaultResultsList[I].second; 3172 DefaultResults[PHI] = Result; 3173 ResultTypes[PHI] = Result->getType(); 3174 } 3175 } 3176 3177 APInt RangeSpread = MaxCaseVal->getValue() - MinCaseVal->getValue(); 3178 // The table density should be at lest 40%. This is the same criterion as for 3179 // jump tables, see SelectionDAGBuilder::handleJTSwitchCase. 3180 // FIXME: Find the best cut-off. 3181 // Be careful to avoid overlow in the density computation. 3182 if (RangeSpread.zextOrSelf(64).ugt(UINT64_MAX / 4 - 1)) 3183 return false; 3184 uint64_t TableSize = RangeSpread.getLimitedValue() + 1; 3185 if (SI->getNumCases() * 10 < TableSize * 4) 3186 return false; 3187 3188 // Build the lookup tables. 3189 SmallDenseMap<PHINode*, GlobalVariable*> LookupTables; 3190 SmallDenseMap<PHINode*, Constant*> SingleResults; 3191 3192 Module &Mod = *CommonDest->getParent()->getParent(); 3193 for (SmallVector<PHINode*, 4>::iterator I = PHIs.begin(), E = PHIs.end(); 3194 I != E; ++I) { 3195 PHINode *PHI = *I; 3196 3197 Constant *SingleResult = NULL; 3198 LookupTables[PHI] = BuildLookupTable(Mod, TableSize, MinCaseVal, 3199 ResultLists[PHI], DefaultResults[PHI], 3200 &SingleResult); 3201 SingleResults[PHI] = SingleResult; 3202 } 3203 3204 // Create the BB that does the lookups. 3205 BasicBlock *LookupBB = BasicBlock::Create(Mod.getContext(), 3206 "switch.lookup", 3207 CommonDest->getParent(), 3208 CommonDest); 3209 3210 // Check whether the condition value is within the case range, and branch to 3211 // the new BB. 3212 Builder.SetInsertPoint(SI); 3213 Value *TableIndex = Builder.CreateSub(SI->getCondition(), MinCaseVal, 3214 "switch.tableidx"); 3215 Value *Cmp = Builder.CreateICmpULT(TableIndex, ConstantInt::get( 3216 MinCaseVal->getType(), TableSize)); 3217 Builder.CreateCondBr(Cmp, LookupBB, SI->getDefaultDest()); 3218 3219 // Populate the BB that does the lookups. 3220 Builder.SetInsertPoint(LookupBB); 3221 bool ReturnedEarly = false; 3222 for (SmallVector<PHINode*, 4>::iterator I = PHIs.begin(), E = PHIs.end(); 3223 I != E; ++I) { 3224 PHINode *PHI = *I; 3225 // There was a single result for this phi; just use that. 3226 if (Constant *SingleResult = SingleResults[PHI]) { 3227 PHI->addIncoming(SingleResult, LookupBB); 3228 continue; 3229 } 3230 3231 Value *GEPIndices[] = { Builder.getInt32(0), TableIndex }; 3232 Value *GEP = Builder.CreateInBoundsGEP(LookupTables[PHI], GEPIndices, 3233 "switch.gep"); 3234 Value *Result = Builder.CreateLoad(GEP, "switch.load"); 3235 3236 // If the result is only going to be used to return from the function, 3237 // we want to do that right here. 3238 if (PHI->hasOneUse() && isa<ReturnInst>(*PHI->use_begin())) { 3239 if (CommonDest->getFirstNonPHIOrDbg() == CommonDest->getTerminator()) { 3240 Builder.CreateRet(Result); 3241 ReturnedEarly = true; 3242 } 3243 } 3244 3245 if (!ReturnedEarly) 3246 PHI->addIncoming(Result, LookupBB); 3247 } 3248 3249 if (!ReturnedEarly) 3250 Builder.CreateBr(CommonDest); 3251 3252 // Remove the switch. 3253 for (unsigned i = 0; i < SI->getNumSuccessors(); ++i) { 3254 BasicBlock *Succ = SI->getSuccessor(i); 3255 if (Succ == SI->getDefaultDest()) continue; 3256 Succ->removePredecessor(SI->getParent()); 3257 } 3258 SI->eraseFromParent(); 3259 3260 ++NumLookupTables; 3261 return true; 3262} 3263 3264bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) { 3265 // If this switch is too complex to want to look at, ignore it. 3266 if (!isValueEqualityComparison(SI)) 3267 return false; 3268 3269 BasicBlock *BB = SI->getParent(); 3270 3271 // If we only have one predecessor, and if it is a branch on this value, 3272 // see if that predecessor totally determines the outcome of this switch. 3273 if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 3274 if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder)) 3275 return SimplifyCFG(BB) | true; 3276 3277 Value *Cond = SI->getCondition(); 3278 if (SelectInst *Select = dyn_cast<SelectInst>(Cond)) 3279 if (SimplifySwitchOnSelect(SI, Select)) 3280 return SimplifyCFG(BB) | true; 3281 3282 // If the block only contains the switch, see if we can fold the block 3283 // away into any preds. 3284 BasicBlock::iterator BBI = BB->begin(); 3285 // Ignore dbg intrinsics. 3286 while (isa<DbgInfoIntrinsic>(BBI)) 3287 ++BBI; 3288 if (SI == &*BBI) 3289 if (FoldValueComparisonIntoPredecessors(SI, Builder)) 3290 return SimplifyCFG(BB) | true; 3291 3292 // Try to transform the switch into an icmp and a branch. 3293 if (TurnSwitchRangeIntoICmp(SI, Builder)) 3294 return SimplifyCFG(BB) | true; 3295 3296 // Remove unreachable cases. 3297 if (EliminateDeadSwitchCases(SI)) 3298 return SimplifyCFG(BB) | true; 3299 3300 if (ForwardSwitchConditionToPHI(SI)) 3301 return SimplifyCFG(BB) | true; 3302 3303 if (SwitchToLookupTable(SI, Builder)) 3304 return SimplifyCFG(BB) | true; 3305 3306 return false; 3307} 3308 3309bool SimplifyCFGOpt::SimplifyIndirectBr(IndirectBrInst *IBI) { 3310 BasicBlock *BB = IBI->getParent(); 3311 bool Changed = false; 3312 3313 // Eliminate redundant destinations. 3314 SmallPtrSet<Value *, 8> Succs; 3315 for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { 3316 BasicBlock *Dest = IBI->getDestination(i); 3317 if (!Dest->hasAddressTaken() || !Succs.insert(Dest)) { 3318 Dest->removePredecessor(BB); 3319 IBI->removeDestination(i); 3320 --i; --e; 3321 Changed = true; 3322 } 3323 } 3324 3325 if (IBI->getNumDestinations() == 0) { 3326 // If the indirectbr has no successors, change it to unreachable. 3327 new UnreachableInst(IBI->getContext(), IBI); 3328 EraseTerminatorInstAndDCECond(IBI); 3329 return true; 3330 } 3331 3332 if (IBI->getNumDestinations() == 1) { 3333 // If the indirectbr has one successor, change it to a direct branch. 3334 BranchInst::Create(IBI->getDestination(0), IBI); 3335 EraseTerminatorInstAndDCECond(IBI); 3336 return true; 3337 } 3338 3339 if (SelectInst *SI = dyn_cast<SelectInst>(IBI->getAddress())) { 3340 if (SimplifyIndirectBrOnSelect(IBI, SI)) 3341 return SimplifyCFG(BB) | true; 3342 } 3343 return Changed; 3344} 3345 3346bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder){ 3347 BasicBlock *BB = BI->getParent(); 3348 3349 // If the Terminator is the only non-phi instruction, simplify the block. 3350 BasicBlock::iterator I = BB->getFirstNonPHIOrDbgOrLifetime(); 3351 if (I->isTerminator() && BB != &BB->getParent()->getEntryBlock() && 3352 TryToSimplifyUncondBranchFromEmptyBlock(BB)) 3353 return true; 3354 3355 // If the only instruction in the block is a seteq/setne comparison 3356 // against a constant, try to simplify the block. 3357 if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) 3358 if (ICI->isEquality() && isa<ConstantInt>(ICI->getOperand(1))) { 3359 for (++I; isa<DbgInfoIntrinsic>(I); ++I) 3360 ; 3361 if (I->isTerminator() && 3362 TryToSimplifyUncondBranchWithICmpInIt(ICI, TD, Builder)) 3363 return true; 3364 } 3365 3366 // If this basic block is ONLY a compare and a branch, and if a predecessor 3367 // branches to us and our successor, fold the comparison into the 3368 // predecessor and use logical operations to update the incoming value 3369 // for PHI nodes in common successor. 3370 if (FoldBranchToCommonDest(BI)) 3371 return SimplifyCFG(BB) | true; 3372 return false; 3373} 3374 3375 3376bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) { 3377 BasicBlock *BB = BI->getParent(); 3378 3379 // Conditional branch 3380 if (isValueEqualityComparison(BI)) { 3381 // If we only have one predecessor, and if it is a branch on this value, 3382 // see if that predecessor totally determines the outcome of this 3383 // switch. 3384 if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 3385 if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder)) 3386 return SimplifyCFG(BB) | true; 3387 3388 // This block must be empty, except for the setcond inst, if it exists. 3389 // Ignore dbg intrinsics. 3390 BasicBlock::iterator I = BB->begin(); 3391 // Ignore dbg intrinsics. 3392 while (isa<DbgInfoIntrinsic>(I)) 3393 ++I; 3394 if (&*I == BI) { 3395 if (FoldValueComparisonIntoPredecessors(BI, Builder)) 3396 return SimplifyCFG(BB) | true; 3397 } else if (&*I == cast<Instruction>(BI->getCondition())){ 3398 ++I; 3399 // Ignore dbg intrinsics. 3400 while (isa<DbgInfoIntrinsic>(I)) 3401 ++I; 3402 if (&*I == BI && FoldValueComparisonIntoPredecessors(BI, Builder)) 3403 return SimplifyCFG(BB) | true; 3404 } 3405 } 3406 3407 // Try to turn "br (X == 0 | X == 1), T, F" into a switch instruction. 3408 if (SimplifyBranchOnICmpChain(BI, TD, Builder)) 3409 return true; 3410 3411 // If this basic block is ONLY a compare and a branch, and if a predecessor 3412 // branches to us and one of our successors, fold the comparison into the 3413 // predecessor and use logical operations to pick the right destination. 3414 if (FoldBranchToCommonDest(BI)) 3415 return SimplifyCFG(BB) | true; 3416 3417 // We have a conditional branch to two blocks that are only reachable 3418 // from BI. We know that the condbr dominates the two blocks, so see if 3419 // there is any identical code in the "then" and "else" blocks. If so, we 3420 // can hoist it up to the branching block. 3421 if (BI->getSuccessor(0)->getSinglePredecessor() != 0) { 3422 if (BI->getSuccessor(1)->getSinglePredecessor() != 0) { 3423 if (HoistThenElseCodeToIf(BI)) 3424 return SimplifyCFG(BB) | true; 3425 } else { 3426 // If Successor #1 has multiple preds, we may be able to conditionally 3427 // execute Successor #0 if it branches to successor #1. 3428 TerminatorInst *Succ0TI = BI->getSuccessor(0)->getTerminator(); 3429 if (Succ0TI->getNumSuccessors() == 1 && 3430 Succ0TI->getSuccessor(0) == BI->getSuccessor(1)) 3431 if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0))) 3432 return SimplifyCFG(BB) | true; 3433 } 3434 } else if (BI->getSuccessor(1)->getSinglePredecessor() != 0) { 3435 // If Successor #0 has multiple preds, we may be able to conditionally 3436 // execute Successor #1 if it branches to successor #0. 3437 TerminatorInst *Succ1TI = BI->getSuccessor(1)->getTerminator(); 3438 if (Succ1TI->getNumSuccessors() == 1 && 3439 Succ1TI->getSuccessor(0) == BI->getSuccessor(0)) 3440 if (SpeculativelyExecuteBB(BI, BI->getSuccessor(1))) 3441 return SimplifyCFG(BB) | true; 3442 } 3443 3444 // If this is a branch on a phi node in the current block, thread control 3445 // through this block if any PHI node entries are constants. 3446 if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition())) 3447 if (PN->getParent() == BI->getParent()) 3448 if (FoldCondBranchOnPHI(BI, TD)) 3449 return SimplifyCFG(BB) | true; 3450 3451 // Scan predecessor blocks for conditional branches. 3452 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 3453 if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 3454 if (PBI != BI && PBI->isConditional()) 3455 if (SimplifyCondBranchToCondBranch(PBI, BI)) 3456 return SimplifyCFG(BB) | true; 3457 3458 return false; 3459} 3460 3461/// Check if passing a value to an instruction will cause undefined behavior. 3462static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I) { 3463 Constant *C = dyn_cast<Constant>(V); 3464 if (!C) 3465 return false; 3466 3467 if (!I->hasOneUse()) // Only look at single-use instructions, for compile time 3468 return false; 3469 3470 if (C->isNullValue()) { 3471 Instruction *Use = I->use_back(); 3472 3473 // Now make sure that there are no instructions in between that can alter 3474 // control flow (eg. calls) 3475 for (BasicBlock::iterator i = ++BasicBlock::iterator(I); &*i != Use; ++i) 3476 if (i == I->getParent()->end() || i->mayHaveSideEffects()) 3477 return false; 3478 3479 // Look through GEPs. A load from a GEP derived from NULL is still undefined 3480 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Use)) 3481 if (GEP->getPointerOperand() == I) 3482 return passingValueIsAlwaysUndefined(V, GEP); 3483 3484 // Look through bitcasts. 3485 if (BitCastInst *BC = dyn_cast<BitCastInst>(Use)) 3486 return passingValueIsAlwaysUndefined(V, BC); 3487 3488 // Load from null is undefined. 3489 if (LoadInst *LI = dyn_cast<LoadInst>(Use)) 3490 return LI->getPointerAddressSpace() == 0; 3491 3492 // Store to null is undefined. 3493 if (StoreInst *SI = dyn_cast<StoreInst>(Use)) 3494 return SI->getPointerAddressSpace() == 0 && SI->getPointerOperand() == I; 3495 } 3496 return false; 3497} 3498 3499/// If BB has an incoming value that will always trigger undefined behavior 3500/// (eg. null pointer dereference), remove the branch leading here. 3501static bool removeUndefIntroducingPredecessor(BasicBlock *BB) { 3502 for (BasicBlock::iterator i = BB->begin(); 3503 PHINode *PHI = dyn_cast<PHINode>(i); ++i) 3504 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) 3505 if (passingValueIsAlwaysUndefined(PHI->getIncomingValue(i), PHI)) { 3506 TerminatorInst *T = PHI->getIncomingBlock(i)->getTerminator(); 3507 IRBuilder<> Builder(T); 3508 if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 3509 BB->removePredecessor(PHI->getIncomingBlock(i)); 3510 // Turn uncoditional branches into unreachables and remove the dead 3511 // destination from conditional branches. 3512 if (BI->isUnconditional()) 3513 Builder.CreateUnreachable(); 3514 else 3515 Builder.CreateBr(BI->getSuccessor(0) == BB ? BI->getSuccessor(1) : 3516 BI->getSuccessor(0)); 3517 BI->eraseFromParent(); 3518 return true; 3519 } 3520 // TODO: SwitchInst. 3521 } 3522 3523 return false; 3524} 3525 3526bool SimplifyCFGOpt::run(BasicBlock *BB) { 3527 bool Changed = false; 3528 3529 assert(BB && BB->getParent() && "Block not embedded in function!"); 3530 assert(BB->getTerminator() && "Degenerate basic block encountered!"); 3531 3532 // Remove basic blocks that have no predecessors (except the entry block)... 3533 // or that just have themself as a predecessor. These are unreachable. 3534 if ((pred_begin(BB) == pred_end(BB) && 3535 BB != &BB->getParent()->getEntryBlock()) || 3536 BB->getSinglePredecessor() == BB) { 3537 DEBUG(dbgs() << "Removing BB: \n" << *BB); 3538 DeleteDeadBlock(BB); 3539 return true; 3540 } 3541 3542 // Check to see if we can constant propagate this terminator instruction 3543 // away... 3544 Changed |= ConstantFoldTerminator(BB, true); 3545 3546 // Check for and eliminate duplicate PHI nodes in this block. 3547 Changed |= EliminateDuplicatePHINodes(BB); 3548 3549 // Check for and remove branches that will always cause undefined behavior. 3550 Changed |= removeUndefIntroducingPredecessor(BB); 3551 3552 // Merge basic blocks into their predecessor if there is only one distinct 3553 // pred, and if there is only one distinct successor of the predecessor, and 3554 // if there are no PHI nodes. 3555 // 3556 if (MergeBlockIntoPredecessor(BB)) 3557 return true; 3558 3559 IRBuilder<> Builder(BB); 3560 3561 // If there is a trivial two-entry PHI node in this basic block, and we can 3562 // eliminate it, do so now. 3563 if (PHINode *PN = dyn_cast<PHINode>(BB->begin())) 3564 if (PN->getNumIncomingValues() == 2) 3565 Changed |= FoldTwoEntryPHINode(PN, TD); 3566 3567 Builder.SetInsertPoint(BB->getTerminator()); 3568 if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 3569 if (BI->isUnconditional()) { 3570 if (SimplifyUncondBranch(BI, Builder)) return true; 3571 } else { 3572 if (SimplifyCondBranch(BI, Builder)) return true; 3573 } 3574 } else if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 3575 if (SimplifyReturn(RI, Builder)) return true; 3576 } else if (ResumeInst *RI = dyn_cast<ResumeInst>(BB->getTerminator())) { 3577 if (SimplifyResume(RI, Builder)) return true; 3578 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { 3579 if (SimplifySwitch(SI, Builder)) return true; 3580 } else if (UnreachableInst *UI = 3581 dyn_cast<UnreachableInst>(BB->getTerminator())) { 3582 if (SimplifyUnreachable(UI)) return true; 3583 } else if (IndirectBrInst *IBI = 3584 dyn_cast<IndirectBrInst>(BB->getTerminator())) { 3585 if (SimplifyIndirectBr(IBI)) return true; 3586 } 3587 3588 return Changed; 3589} 3590 3591/// SimplifyCFG - This function is used to do simplification of a CFG. For 3592/// example, it adjusts branches to branches to eliminate the extra hop, it 3593/// eliminates unreachable basic blocks, and does other "peephole" optimization 3594/// of the CFG. It returns true if a modification was made. 3595/// 3596bool llvm::SimplifyCFG(BasicBlock *BB, const TargetData *TD) { 3597 return SimplifyCFGOpt(TD).run(BB); 3598} 3599