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