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 #include "llvm/Transforms/Utils/Local.h" 15 #include "llvm/ADT/DenseMap.h" 16 #include "llvm/ADT/STLExtras.h" 17 #include "llvm/ADT/SetVector.h" 18 #include "llvm/ADT/SmallPtrSet.h" 19 #include "llvm/ADT/SmallVector.h" 20 #include "llvm/ADT/Statistic.h" 21 #include "llvm/Analysis/ConstantFolding.h" 22 #include "llvm/Analysis/InstructionSimplify.h" 23 #include "llvm/Analysis/TargetTransformInfo.h" 24 #include "llvm/Analysis/ValueTracking.h" 25 #include "llvm/IR/CFG.h" 26 #include "llvm/IR/ConstantRange.h" 27 #include "llvm/IR/Constants.h" 28 #include "llvm/IR/DataLayout.h" 29 #include "llvm/IR/DerivedTypes.h" 30 #include "llvm/IR/GlobalVariable.h" 31 #include "llvm/IR/IRBuilder.h" 32 #include "llvm/IR/Instructions.h" 33 #include "llvm/IR/IntrinsicInst.h" 34 #include "llvm/IR/LLVMContext.h" 35 #include "llvm/IR/MDBuilder.h" 36 #include "llvm/IR/Metadata.h" 37 #include "llvm/IR/Module.h" 38 #include "llvm/IR/NoFolder.h" 39 #include "llvm/IR/Operator.h" 40 #include "llvm/IR/PatternMatch.h" 41 #include "llvm/IR/Type.h" 42 #include "llvm/Support/CommandLine.h" 43 #include "llvm/Support/Debug.h" 44 #include "llvm/Support/raw_ostream.h" 45 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 46 #include "llvm/Transforms/Utils/Local.h" 47 #include "llvm/Transforms/Utils/ValueMapper.h" 48 #include <algorithm> 49 #include <map> 50 #include <set> 51 using namespace llvm; 52 using namespace PatternMatch; 53 54 #define DEBUG_TYPE "simplifycfg" 55 56 // Chosen as 2 so as to be cheap, but still to have enough power to fold 57 // a select, so the "clamp" idiom (of a min followed by a max) will be caught. 58 // To catch this, we need to fold a compare and a select, hence '2' being the 59 // minimum reasonable default. 60 static cl::opt<unsigned> 61 PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2), 62 cl::desc("Control the amount of phi node folding to perform (default = 2)")); 63 64 static cl::opt<bool> 65 DupRet("simplifycfg-dup-ret", cl::Hidden, cl::init(false), 66 cl::desc("Duplicate return instructions into unconditional branches")); 67 68 static cl::opt<bool> 69 SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), 70 cl::desc("Sink common instructions down to the end block")); 71 72 static cl::opt<bool> HoistCondStores( 73 "simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), 74 cl::desc("Hoist conditional stores if an unconditional store precedes")); 75 76 STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps"); 77 STATISTIC(NumLinearMaps, "Number of switch instructions turned into linear mapping"); 78 STATISTIC(NumLookupTables, "Number of switch instructions turned into lookup tables"); 79 STATISTIC(NumLookupTablesHoles, "Number of switch instructions turned into lookup tables (holes checked)"); 80 STATISTIC(NumTableCmpReuses, "Number of reused switch table lookup compares"); 81 STATISTIC(NumSinkCommons, "Number of common instructions sunk down to the end block"); 82 STATISTIC(NumSpeculations, "Number of speculative executed instructions"); 83 84 namespace { 85 // The first field contains the value that the switch produces when a certain 86 // case group is selected, and the second field is a vector containing the cases 87 // composing the case group. 88 typedef SmallVector<std::pair<Constant *, SmallVector<ConstantInt *, 4>>, 2> 89 SwitchCaseResultVectorTy; 90 // The first field contains the phi node that generates a result of the switch 91 // and the second field contains the value generated for a certain case in the switch 92 // for that PHI. 93 typedef SmallVector<std::pair<PHINode *, Constant *>, 4> SwitchCaseResultsTy; 94 95 /// ValueEqualityComparisonCase - Represents a case of a switch. 96 struct ValueEqualityComparisonCase { 97 ConstantInt *Value; 98 BasicBlock *Dest; 99 100 ValueEqualityComparisonCase(ConstantInt *Value, BasicBlock *Dest) 101 : Value(Value), Dest(Dest) {} 102 103 bool operator<(ValueEqualityComparisonCase RHS) const { 104 // Comparing pointers is ok as we only rely on the order for uniquing. 105 return Value < RHS.Value; 106 } 107 108 bool operator==(BasicBlock *RHSDest) const { return Dest == RHSDest; } 109 }; 110 111 class SimplifyCFGOpt { 112 const TargetTransformInfo &TTI; 113 const DataLayout &DL; 114 unsigned BonusInstThreshold; 115 AssumptionCache *AC; 116 Value *isValueEqualityComparison(TerminatorInst *TI); 117 BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI, 118 std::vector<ValueEqualityComparisonCase> &Cases); 119 bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, 120 BasicBlock *Pred, 121 IRBuilder<> &Builder); 122 bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI, 123 IRBuilder<> &Builder); 124 125 bool SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder); 126 bool SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder); 127 bool SimplifyUnreachable(UnreachableInst *UI); 128 bool SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder); 129 bool SimplifyIndirectBr(IndirectBrInst *IBI); 130 bool SimplifyUncondBranch(BranchInst *BI, IRBuilder <> &Builder); 131 bool SimplifyCondBranch(BranchInst *BI, IRBuilder <>&Builder); 132 133 public: 134 SimplifyCFGOpt(const TargetTransformInfo &TTI, const DataLayout &DL, 135 unsigned BonusInstThreshold, AssumptionCache *AC) 136 : TTI(TTI), DL(DL), BonusInstThreshold(BonusInstThreshold), AC(AC) {} 137 bool run(BasicBlock *BB); 138 }; 139 } 140 141 /// SafeToMergeTerminators - Return true if it is safe to merge these two 142 /// terminator instructions together. 143 /// 144 static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) { 145 if (SI1 == SI2) return false; // Can't merge with self! 146 147 // It is not safe to merge these two switch instructions if they have a common 148 // successor, and if that successor has a PHI node, and if *that* PHI node has 149 // conflicting incoming values from the two switch blocks. 150 BasicBlock *SI1BB = SI1->getParent(); 151 BasicBlock *SI2BB = SI2->getParent(); 152 SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 153 154 for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) 155 if (SI1Succs.count(*I)) 156 for (BasicBlock::iterator BBI = (*I)->begin(); 157 isa<PHINode>(BBI); ++BBI) { 158 PHINode *PN = cast<PHINode>(BBI); 159 if (PN->getIncomingValueForBlock(SI1BB) != 160 PN->getIncomingValueForBlock(SI2BB)) 161 return false; 162 } 163 164 return true; 165 } 166 167 /// isProfitableToFoldUnconditional - Return true if it is safe and profitable 168 /// to merge these two terminator instructions together, where SI1 is an 169 /// unconditional branch. PhiNodes will store all PHI nodes in common 170 /// successors. 171 /// 172 static bool isProfitableToFoldUnconditional(BranchInst *SI1, 173 BranchInst *SI2, 174 Instruction *Cond, 175 SmallVectorImpl<PHINode*> &PhiNodes) { 176 if (SI1 == SI2) return false; // Can't merge with self! 177 assert(SI1->isUnconditional() && SI2->isConditional()); 178 179 // We fold the unconditional branch if we can easily update all PHI nodes in 180 // common successors: 181 // 1> We have a constant incoming value for the conditional branch; 182 // 2> We have "Cond" as the incoming value for the unconditional branch; 183 // 3> SI2->getCondition() and Cond have same operands. 184 CmpInst *Ci2 = dyn_cast<CmpInst>(SI2->getCondition()); 185 if (!Ci2) return false; 186 if (!(Cond->getOperand(0) == Ci2->getOperand(0) && 187 Cond->getOperand(1) == Ci2->getOperand(1)) && 188 !(Cond->getOperand(0) == Ci2->getOperand(1) && 189 Cond->getOperand(1) == Ci2->getOperand(0))) 190 return false; 191 192 BasicBlock *SI1BB = SI1->getParent(); 193 BasicBlock *SI2BB = SI2->getParent(); 194 SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 195 for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) 196 if (SI1Succs.count(*I)) 197 for (BasicBlock::iterator BBI = (*I)->begin(); 198 isa<PHINode>(BBI); ++BBI) { 199 PHINode *PN = cast<PHINode>(BBI); 200 if (PN->getIncomingValueForBlock(SI1BB) != Cond || 201 !isa<ConstantInt>(PN->getIncomingValueForBlock(SI2BB))) 202 return false; 203 PhiNodes.push_back(PN); 204 } 205 return true; 206 } 207 208 /// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will 209 /// now be entries in it from the 'NewPred' block. The values that will be 210 /// flowing into the PHI nodes will be the same as those coming in from 211 /// ExistPred, an existing predecessor of Succ. 212 static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, 213 BasicBlock *ExistPred) { 214 if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do 215 216 PHINode *PN; 217 for (BasicBlock::iterator I = Succ->begin(); 218 (PN = dyn_cast<PHINode>(I)); ++I) 219 PN->addIncoming(PN->getIncomingValueForBlock(ExistPred), NewPred); 220 } 221 222 /// ComputeSpeculationCost - Compute an abstract "cost" of speculating the 223 /// given instruction, which is assumed to be safe to speculate. TCC_Free means 224 /// cheap, TCC_Basic means less cheap, and TCC_Expensive means prohibitively 225 /// expensive. 226 static unsigned ComputeSpeculationCost(const User *I, 227 const TargetTransformInfo &TTI) { 228 assert(isSafeToSpeculativelyExecute(I) && 229 "Instruction is not safe to speculatively execute!"); 230 return TTI.getUserCost(I); 231 } 232 /// DominatesMergePoint - If we have a merge point of an "if condition" as 233 /// accepted above, return true if the specified value dominates the block. We 234 /// don't handle the true generality of domination here, just a special case 235 /// which works well enough for us. 236 /// 237 /// If AggressiveInsts is non-null, and if V does not dominate BB, we check to 238 /// see if V (which must be an instruction) and its recursive operands 239 /// that do not dominate BB have a combined cost lower than CostRemaining and 240 /// are non-trapping. If both are true, the instruction is inserted into the 241 /// set and true is returned. 242 /// 243 /// The cost for most non-trapping instructions is defined as 1 except for 244 /// Select whose cost is 2. 245 /// 246 /// After this function returns, CostRemaining is decreased by the cost of 247 /// V plus its non-dominating operands. If that cost is greater than 248 /// CostRemaining, false is returned and CostRemaining is undefined. 249 static bool DominatesMergePoint(Value *V, BasicBlock *BB, 250 SmallPtrSetImpl<Instruction*> *AggressiveInsts, 251 unsigned &CostRemaining, 252 const TargetTransformInfo &TTI) { 253 Instruction *I = dyn_cast<Instruction>(V); 254 if (!I) { 255 // Non-instructions all dominate instructions, but not all constantexprs 256 // can be executed unconditionally. 257 if (ConstantExpr *C = dyn_cast<ConstantExpr>(V)) 258 if (C->canTrap()) 259 return false; 260 return true; 261 } 262 BasicBlock *PBB = I->getParent(); 263 264 // We don't want to allow weird loops that might have the "if condition" in 265 // the bottom of this block. 266 if (PBB == BB) return false; 267 268 // If this instruction is defined in a block that contains an unconditional 269 // branch to BB, then it must be in the 'conditional' part of the "if 270 // statement". If not, it definitely dominates the region. 271 BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator()); 272 if (!BI || BI->isConditional() || BI->getSuccessor(0) != BB) 273 return true; 274 275 // If we aren't allowing aggressive promotion anymore, then don't consider 276 // instructions in the 'if region'. 277 if (!AggressiveInsts) return false; 278 279 // If we have seen this instruction before, don't count it again. 280 if (AggressiveInsts->count(I)) return true; 281 282 // Okay, it looks like the instruction IS in the "condition". Check to 283 // see if it's a cheap instruction to unconditionally compute, and if it 284 // only uses stuff defined outside of the condition. If so, hoist it out. 285 if (!isSafeToSpeculativelyExecute(I)) 286 return false; 287 288 unsigned Cost = ComputeSpeculationCost(I, TTI); 289 290 if (Cost > CostRemaining) 291 return false; 292 293 CostRemaining -= Cost; 294 295 // Okay, we can only really hoist these out if their operands do 296 // not take us over the cost threshold. 297 for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) 298 if (!DominatesMergePoint(*i, BB, AggressiveInsts, CostRemaining, TTI)) 299 return false; 300 // Okay, it's safe to do this! Remember this instruction. 301 AggressiveInsts->insert(I); 302 return true; 303 } 304 305 /// GetConstantInt - Extract ConstantInt from value, looking through IntToPtr 306 /// and PointerNullValue. Return NULL if value is not a constant int. 307 static ConstantInt *GetConstantInt(Value *V, const DataLayout &DL) { 308 // Normal constant int. 309 ConstantInt *CI = dyn_cast<ConstantInt>(V); 310 if (CI || !isa<Constant>(V) || !V->getType()->isPointerTy()) 311 return CI; 312 313 // This is some kind of pointer constant. Turn it into a pointer-sized 314 // ConstantInt if possible. 315 IntegerType *PtrTy = cast<IntegerType>(DL.getIntPtrType(V->getType())); 316 317 // Null pointer means 0, see SelectionDAGBuilder::getValue(const Value*). 318 if (isa<ConstantPointerNull>(V)) 319 return ConstantInt::get(PtrTy, 0); 320 321 // IntToPtr const int. 322 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 323 if (CE->getOpcode() == Instruction::IntToPtr) 324 if (ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) { 325 // The constant is very likely to have the right type already. 326 if (CI->getType() == PtrTy) 327 return CI; 328 else 329 return cast<ConstantInt> 330 (ConstantExpr::getIntegerCast(CI, PtrTy, /*isSigned=*/false)); 331 } 332 return nullptr; 333 } 334 335 namespace { 336 337 /// Given a chain of or (||) or and (&&) comparison of a value against a 338 /// constant, this will try to recover the information required for a switch 339 /// structure. 340 /// It will depth-first traverse the chain of comparison, seeking for patterns 341 /// like %a == 12 or %a < 4 and combine them to produce a set of integer 342 /// representing the different cases for the switch. 343 /// Note that if the chain is composed of '||' it will build the set of elements 344 /// that matches the comparisons (i.e. any of this value validate the chain) 345 /// while for a chain of '&&' it will build the set elements that make the test 346 /// fail. 347 struct ConstantComparesGatherer { 348 const DataLayout &DL; 349 Value *CompValue; /// Value found for the switch comparison 350 Value *Extra; /// Extra clause to be checked before the switch 351 SmallVector<ConstantInt *, 8> Vals; /// Set of integers to match in switch 352 unsigned UsedICmps; /// Number of comparisons matched in the and/or chain 353 354 /// Construct and compute the result for the comparison instruction Cond 355 ConstantComparesGatherer(Instruction *Cond, const DataLayout &DL) 356 : DL(DL), CompValue(nullptr), Extra(nullptr), UsedICmps(0) { 357 gather(Cond); 358 } 359 360 /// Prevent copy 361 ConstantComparesGatherer(const ConstantComparesGatherer &) = delete; 362 ConstantComparesGatherer & 363 operator=(const ConstantComparesGatherer &) = delete; 364 365 private: 366 367 /// Try to set the current value used for the comparison, it succeeds only if 368 /// it wasn't set before or if the new value is the same as the old one 369 bool setValueOnce(Value *NewVal) { 370 if(CompValue && CompValue != NewVal) return false; 371 CompValue = NewVal; 372 return (CompValue != nullptr); 373 } 374 375 /// Try to match Instruction "I" as a comparison against a constant and 376 /// populates the array Vals with the set of values that match (or do not 377 /// match depending on isEQ). 378 /// Return false on failure. On success, the Value the comparison matched 379 /// against is placed in CompValue. 380 /// If CompValue is already set, the function is expected to fail if a match 381 /// is found but the value compared to is different. 382 bool matchInstruction(Instruction *I, bool isEQ) { 383 // If this is an icmp against a constant, handle this as one of the cases. 384 ICmpInst *ICI; 385 ConstantInt *C; 386 if (!((ICI = dyn_cast<ICmpInst>(I)) && 387 (C = GetConstantInt(I->getOperand(1), DL)))) { 388 return false; 389 } 390 391 Value *RHSVal; 392 ConstantInt *RHSC; 393 394 // Pattern match a special case 395 // (x & ~2^x) == y --> x == y || x == y|2^x 396 // This undoes a transformation done by instcombine to fuse 2 compares. 397 if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) { 398 if (match(ICI->getOperand(0), 399 m_And(m_Value(RHSVal), m_ConstantInt(RHSC)))) { 400 APInt Not = ~RHSC->getValue(); 401 if (Not.isPowerOf2()) { 402 // If we already have a value for the switch, it has to match! 403 if(!setValueOnce(RHSVal)) 404 return false; 405 406 Vals.push_back(C); 407 Vals.push_back(ConstantInt::get(C->getContext(), 408 C->getValue() | Not)); 409 UsedICmps++; 410 return true; 411 } 412 } 413 414 // If we already have a value for the switch, it has to match! 415 if(!setValueOnce(ICI->getOperand(0))) 416 return false; 417 418 UsedICmps++; 419 Vals.push_back(C); 420 return ICI->getOperand(0); 421 } 422 423 // If we have "x ult 3", for example, then we can add 0,1,2 to the set. 424 ConstantRange Span = ConstantRange::makeAllowedICmpRegion( 425 ICI->getPredicate(), C->getValue()); 426 427 // Shift the range if the compare is fed by an add. This is the range 428 // compare idiom as emitted by instcombine. 429 Value *CandidateVal = I->getOperand(0); 430 if(match(I->getOperand(0), m_Add(m_Value(RHSVal), m_ConstantInt(RHSC)))) { 431 Span = Span.subtract(RHSC->getValue()); 432 CandidateVal = RHSVal; 433 } 434 435 // If this is an and/!= check, then we are looking to build the set of 436 // value that *don't* pass the and chain. I.e. to turn "x ugt 2" into 437 // x != 0 && x != 1. 438 if (!isEQ) 439 Span = Span.inverse(); 440 441 // If there are a ton of values, we don't want to make a ginormous switch. 442 if (Span.getSetSize().ugt(8) || Span.isEmptySet()) { 443 return false; 444 } 445 446 // If we already have a value for the switch, it has to match! 447 if(!setValueOnce(CandidateVal)) 448 return false; 449 450 // Add all values from the range to the set 451 for (APInt Tmp = Span.getLower(); Tmp != Span.getUpper(); ++Tmp) 452 Vals.push_back(ConstantInt::get(I->getContext(), Tmp)); 453 454 UsedICmps++; 455 return true; 456 457 } 458 459 /// gather - Given a potentially 'or'd or 'and'd together collection of icmp 460 /// eq/ne/lt/gt instructions that compare a value against a constant, extract 461 /// the value being compared, and stick the list constants into the Vals 462 /// vector. 463 /// One "Extra" case is allowed to differ from the other. 464 void gather(Value *V) { 465 Instruction *I = dyn_cast<Instruction>(V); 466 bool isEQ = (I->getOpcode() == Instruction::Or); 467 468 // Keep a stack (SmallVector for efficiency) for depth-first traversal 469 SmallVector<Value *, 8> DFT; 470 471 // Initialize 472 DFT.push_back(V); 473 474 while(!DFT.empty()) { 475 V = DFT.pop_back_val(); 476 477 if (Instruction *I = dyn_cast<Instruction>(V)) { 478 // If it is a || (or && depending on isEQ), process the operands. 479 if (I->getOpcode() == (isEQ ? Instruction::Or : Instruction::And)) { 480 DFT.push_back(I->getOperand(1)); 481 DFT.push_back(I->getOperand(0)); 482 continue; 483 } 484 485 // Try to match the current instruction 486 if (matchInstruction(I, isEQ)) 487 // Match succeed, continue the loop 488 continue; 489 } 490 491 // One element of the sequence of || (or &&) could not be match as a 492 // comparison against the same value as the others. 493 // We allow only one "Extra" case to be checked before the switch 494 if (!Extra) { 495 Extra = V; 496 continue; 497 } 498 // Failed to parse a proper sequence, abort now 499 CompValue = nullptr; 500 break; 501 } 502 } 503 }; 504 505 } 506 507 static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) { 508 Instruction *Cond = nullptr; 509 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 510 Cond = dyn_cast<Instruction>(SI->getCondition()); 511 } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 512 if (BI->isConditional()) 513 Cond = dyn_cast<Instruction>(BI->getCondition()); 514 } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(TI)) { 515 Cond = dyn_cast<Instruction>(IBI->getAddress()); 516 } 517 518 TI->eraseFromParent(); 519 if (Cond) RecursivelyDeleteTriviallyDeadInstructions(Cond); 520 } 521 522 /// isValueEqualityComparison - Return true if the specified terminator checks 523 /// to see if a value is equal to constant integer value. 524 Value *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) { 525 Value *CV = nullptr; 526 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 527 // Do not permit merging of large switch instructions into their 528 // predecessors unless there is only one predecessor. 529 if (SI->getNumSuccessors()*std::distance(pred_begin(SI->getParent()), 530 pred_end(SI->getParent())) <= 128) 531 CV = SI->getCondition(); 532 } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 533 if (BI->isConditional() && BI->getCondition()->hasOneUse()) 534 if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) { 535 if (ICI->isEquality() && GetConstantInt(ICI->getOperand(1), DL)) 536 CV = ICI->getOperand(0); 537 } 538 539 // Unwrap any lossless ptrtoint cast. 540 if (CV) { 541 if (PtrToIntInst *PTII = dyn_cast<PtrToIntInst>(CV)) { 542 Value *Ptr = PTII->getPointerOperand(); 543 if (PTII->getType() == DL.getIntPtrType(Ptr->getType())) 544 CV = Ptr; 545 } 546 } 547 return CV; 548 } 549 550 /// GetValueEqualityComparisonCases - Given a value comparison instruction, 551 /// decode all of the 'cases' that it represents and return the 'default' block. 552 BasicBlock *SimplifyCFGOpt:: 553 GetValueEqualityComparisonCases(TerminatorInst *TI, 554 std::vector<ValueEqualityComparisonCase> 555 &Cases) { 556 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 557 Cases.reserve(SI->getNumCases()); 558 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; ++i) 559 Cases.push_back(ValueEqualityComparisonCase(i.getCaseValue(), 560 i.getCaseSuccessor())); 561 return SI->getDefaultDest(); 562 } 563 564 BranchInst *BI = cast<BranchInst>(TI); 565 ICmpInst *ICI = cast<ICmpInst>(BI->getCondition()); 566 BasicBlock *Succ = BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_NE); 567 Cases.push_back(ValueEqualityComparisonCase(GetConstantInt(ICI->getOperand(1), 568 DL), 569 Succ)); 570 return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ); 571 } 572 573 574 /// EliminateBlockCases - Given a vector of bb/value pairs, remove any entries 575 /// in the list that match the specified block. 576 static void EliminateBlockCases(BasicBlock *BB, 577 std::vector<ValueEqualityComparisonCase> &Cases) { 578 Cases.erase(std::remove(Cases.begin(), Cases.end(), BB), Cases.end()); 579 } 580 581 /// ValuesOverlap - Return true if there are any keys in C1 that exist in C2 as 582 /// well. 583 static bool 584 ValuesOverlap(std::vector<ValueEqualityComparisonCase> &C1, 585 std::vector<ValueEqualityComparisonCase > &C2) { 586 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2; 587 588 // Make V1 be smaller than V2. 589 if (V1->size() > V2->size()) 590 std::swap(V1, V2); 591 592 if (V1->size() == 0) return false; 593 if (V1->size() == 1) { 594 // Just scan V2. 595 ConstantInt *TheVal = (*V1)[0].Value; 596 for (unsigned i = 0, e = V2->size(); i != e; ++i) 597 if (TheVal == (*V2)[i].Value) 598 return true; 599 } 600 601 // Otherwise, just sort both lists and compare element by element. 602 array_pod_sort(V1->begin(), V1->end()); 603 array_pod_sort(V2->begin(), V2->end()); 604 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size(); 605 while (i1 != e1 && i2 != e2) { 606 if ((*V1)[i1].Value == (*V2)[i2].Value) 607 return true; 608 if ((*V1)[i1].Value < (*V2)[i2].Value) 609 ++i1; 610 else 611 ++i2; 612 } 613 return false; 614 } 615 616 /// SimplifyEqualityComparisonWithOnlyPredecessor - If TI is known to be a 617 /// terminator instruction and its block is known to only have a single 618 /// predecessor block, check to see if that predecessor is also a value 619 /// comparison with the same value, and if that comparison determines the 620 /// outcome of this comparison. If so, simplify TI. This does a very limited 621 /// form of jump threading. 622 bool SimplifyCFGOpt:: 623 SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, 624 BasicBlock *Pred, 625 IRBuilder<> &Builder) { 626 Value *PredVal = isValueEqualityComparison(Pred->getTerminator()); 627 if (!PredVal) return false; // Not a value comparison in predecessor. 628 629 Value *ThisVal = isValueEqualityComparison(TI); 630 assert(ThisVal && "This isn't a value comparison!!"); 631 if (ThisVal != PredVal) return false; // Different predicates. 632 633 // TODO: Preserve branch weight metadata, similarly to how 634 // FoldValueComparisonIntoPredecessors preserves it. 635 636 // Find out information about when control will move from Pred to TI's block. 637 std::vector<ValueEqualityComparisonCase> PredCases; 638 BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(), 639 PredCases); 640 EliminateBlockCases(PredDef, PredCases); // Remove default from cases. 641 642 // Find information about how control leaves this block. 643 std::vector<ValueEqualityComparisonCase> ThisCases; 644 BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases); 645 EliminateBlockCases(ThisDef, ThisCases); // Remove default from cases. 646 647 // If TI's block is the default block from Pred's comparison, potentially 648 // simplify TI based on this knowledge. 649 if (PredDef == TI->getParent()) { 650 // If we are here, we know that the value is none of those cases listed in 651 // PredCases. If there are any cases in ThisCases that are in PredCases, we 652 // can simplify TI. 653 if (!ValuesOverlap(PredCases, ThisCases)) 654 return false; 655 656 if (isa<BranchInst>(TI)) { 657 // Okay, one of the successors of this condbr is dead. Convert it to a 658 // uncond br. 659 assert(ThisCases.size() == 1 && "Branch can only have one case!"); 660 // Insert the new branch. 661 Instruction *NI = Builder.CreateBr(ThisDef); 662 (void) NI; 663 664 // Remove PHI node entries for the dead edge. 665 ThisCases[0].Dest->removePredecessor(TI->getParent()); 666 667 DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 668 << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); 669 670 EraseTerminatorInstAndDCECond(TI); 671 return true; 672 } 673 674 SwitchInst *SI = cast<SwitchInst>(TI); 675 // Okay, TI has cases that are statically dead, prune them away. 676 SmallPtrSet<Constant*, 16> DeadCases; 677 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 678 DeadCases.insert(PredCases[i].Value); 679 680 DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 681 << "Through successor TI: " << *TI); 682 683 // Collect branch weights into a vector. 684 SmallVector<uint32_t, 8> Weights; 685 MDNode *MD = SI->getMetadata(LLVMContext::MD_prof); 686 bool HasWeight = MD && (MD->getNumOperands() == 2 + SI->getNumCases()); 687 if (HasWeight) 688 for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e; 689 ++MD_i) { 690 ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(MD_i)); 691 Weights.push_back(CI->getValue().getZExtValue()); 692 } 693 for (SwitchInst::CaseIt i = SI->case_end(), e = SI->case_begin(); i != e;) { 694 --i; 695 if (DeadCases.count(i.getCaseValue())) { 696 if (HasWeight) { 697 std::swap(Weights[i.getCaseIndex()+1], Weights.back()); 698 Weights.pop_back(); 699 } 700 i.getCaseSuccessor()->removePredecessor(TI->getParent()); 701 SI->removeCase(i); 702 } 703 } 704 if (HasWeight && Weights.size() >= 2) 705 SI->setMetadata(LLVMContext::MD_prof, 706 MDBuilder(SI->getParent()->getContext()). 707 createBranchWeights(Weights)); 708 709 DEBUG(dbgs() << "Leaving: " << *TI << "\n"); 710 return true; 711 } 712 713 // Otherwise, TI's block must correspond to some matched value. Find out 714 // which value (or set of values) this is. 715 ConstantInt *TIV = nullptr; 716 BasicBlock *TIBB = TI->getParent(); 717 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 718 if (PredCases[i].Dest == TIBB) { 719 if (TIV) 720 return false; // Cannot handle multiple values coming to this block. 721 TIV = PredCases[i].Value; 722 } 723 assert(TIV && "No edge from pred to succ?"); 724 725 // Okay, we found the one constant that our value can be if we get into TI's 726 // BB. Find out which successor will unconditionally be branched to. 727 BasicBlock *TheRealDest = nullptr; 728 for (unsigned i = 0, e = ThisCases.size(); i != e; ++i) 729 if (ThisCases[i].Value == TIV) { 730 TheRealDest = ThisCases[i].Dest; 731 break; 732 } 733 734 // If not handled by any explicit cases, it is handled by the default case. 735 if (!TheRealDest) TheRealDest = ThisDef; 736 737 // Remove PHI node entries for dead edges. 738 BasicBlock *CheckEdge = TheRealDest; 739 for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI) 740 if (*SI != CheckEdge) 741 (*SI)->removePredecessor(TIBB); 742 else 743 CheckEdge = nullptr; 744 745 // Insert the new branch. 746 Instruction *NI = Builder.CreateBr(TheRealDest); 747 (void) NI; 748 749 DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 750 << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); 751 752 EraseTerminatorInstAndDCECond(TI); 753 return true; 754 } 755 756 namespace { 757 /// ConstantIntOrdering - This class implements a stable ordering of constant 758 /// integers that does not depend on their address. This is important for 759 /// applications that sort ConstantInt's to ensure uniqueness. 760 struct ConstantIntOrdering { 761 bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { 762 return LHS->getValue().ult(RHS->getValue()); 763 } 764 }; 765 } 766 767 static int ConstantIntSortPredicate(ConstantInt *const *P1, 768 ConstantInt *const *P2) { 769 const ConstantInt *LHS = *P1; 770 const ConstantInt *RHS = *P2; 771 if (LHS->getValue().ult(RHS->getValue())) 772 return 1; 773 if (LHS->getValue() == RHS->getValue()) 774 return 0; 775 return -1; 776 } 777 778 static inline bool HasBranchWeights(const Instruction* I) { 779 MDNode *ProfMD = I->getMetadata(LLVMContext::MD_prof); 780 if (ProfMD && ProfMD->getOperand(0)) 781 if (MDString* MDS = dyn_cast<MDString>(ProfMD->getOperand(0))) 782 return MDS->getString().equals("branch_weights"); 783 784 return false; 785 } 786 787 /// Get Weights of a given TerminatorInst, the default weight is at the front 788 /// of the vector. If TI is a conditional eq, we need to swap the branch-weight 789 /// metadata. 790 static void GetBranchWeights(TerminatorInst *TI, 791 SmallVectorImpl<uint64_t> &Weights) { 792 MDNode *MD = TI->getMetadata(LLVMContext::MD_prof); 793 assert(MD); 794 for (unsigned i = 1, e = MD->getNumOperands(); i < e; ++i) { 795 ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(i)); 796 Weights.push_back(CI->getValue().getZExtValue()); 797 } 798 799 // If TI is a conditional eq, the default case is the false case, 800 // and the corresponding branch-weight data is at index 2. We swap the 801 // default weight to be the first entry. 802 if (BranchInst* BI = dyn_cast<BranchInst>(TI)) { 803 assert(Weights.size() == 2); 804 ICmpInst *ICI = cast<ICmpInst>(BI->getCondition()); 805 if (ICI->getPredicate() == ICmpInst::ICMP_EQ) 806 std::swap(Weights.front(), Weights.back()); 807 } 808 } 809 810 /// Keep halving the weights until all can fit in uint32_t. 811 static void FitWeights(MutableArrayRef<uint64_t> Weights) { 812 uint64_t Max = *std::max_element(Weights.begin(), Weights.end()); 813 if (Max > UINT_MAX) { 814 unsigned Offset = 32 - countLeadingZeros(Max); 815 for (uint64_t &I : Weights) 816 I >>= Offset; 817 } 818 } 819 820 /// FoldValueComparisonIntoPredecessors - The specified terminator is a value 821 /// equality comparison instruction (either a switch or a branch on "X == c"). 822 /// See if any of the predecessors of the terminator block are value comparisons 823 /// on the same value. If so, and if safe to do so, fold them together. 824 bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI, 825 IRBuilder<> &Builder) { 826 BasicBlock *BB = TI->getParent(); 827 Value *CV = isValueEqualityComparison(TI); // CondVal 828 assert(CV && "Not a comparison?"); 829 bool Changed = false; 830 831 SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB)); 832 while (!Preds.empty()) { 833 BasicBlock *Pred = Preds.pop_back_val(); 834 835 // See if the predecessor is a comparison with the same value. 836 TerminatorInst *PTI = Pred->getTerminator(); 837 Value *PCV = isValueEqualityComparison(PTI); // PredCondVal 838 839 if (PCV == CV && SafeToMergeTerminators(TI, PTI)) { 840 // Figure out which 'cases' to copy from SI to PSI. 841 std::vector<ValueEqualityComparisonCase> BBCases; 842 BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases); 843 844 std::vector<ValueEqualityComparisonCase> PredCases; 845 BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases); 846 847 // Based on whether the default edge from PTI goes to BB or not, fill in 848 // PredCases and PredDefault with the new switch cases we would like to 849 // build. 850 SmallVector<BasicBlock*, 8> NewSuccessors; 851 852 // Update the branch weight metadata along the way 853 SmallVector<uint64_t, 8> Weights; 854 bool PredHasWeights = HasBranchWeights(PTI); 855 bool SuccHasWeights = HasBranchWeights(TI); 856 857 if (PredHasWeights) { 858 GetBranchWeights(PTI, Weights); 859 // branch-weight metadata is inconsistent here. 860 if (Weights.size() != 1 + PredCases.size()) 861 PredHasWeights = SuccHasWeights = false; 862 } else if (SuccHasWeights) 863 // If there are no predecessor weights but there are successor weights, 864 // populate Weights with 1, which will later be scaled to the sum of 865 // successor's weights 866 Weights.assign(1 + PredCases.size(), 1); 867 868 SmallVector<uint64_t, 8> SuccWeights; 869 if (SuccHasWeights) { 870 GetBranchWeights(TI, SuccWeights); 871 // branch-weight metadata is inconsistent here. 872 if (SuccWeights.size() != 1 + BBCases.size()) 873 PredHasWeights = SuccHasWeights = false; 874 } else if (PredHasWeights) 875 SuccWeights.assign(1 + BBCases.size(), 1); 876 877 if (PredDefault == BB) { 878 // If this is the default destination from PTI, only the edges in TI 879 // that don't occur in PTI, or that branch to BB will be activated. 880 std::set<ConstantInt*, ConstantIntOrdering> PTIHandled; 881 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 882 if (PredCases[i].Dest != BB) 883 PTIHandled.insert(PredCases[i].Value); 884 else { 885 // The default destination is BB, we don't need explicit targets. 886 std::swap(PredCases[i], PredCases.back()); 887 888 if (PredHasWeights || SuccHasWeights) { 889 // Increase weight for the default case. 890 Weights[0] += Weights[i+1]; 891 std::swap(Weights[i+1], Weights.back()); 892 Weights.pop_back(); 893 } 894 895 PredCases.pop_back(); 896 --i; --e; 897 } 898 899 // Reconstruct the new switch statement we will be building. 900 if (PredDefault != BBDefault) { 901 PredDefault->removePredecessor(Pred); 902 PredDefault = BBDefault; 903 NewSuccessors.push_back(BBDefault); 904 } 905 906 unsigned CasesFromPred = Weights.size(); 907 uint64_t ValidTotalSuccWeight = 0; 908 for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 909 if (!PTIHandled.count(BBCases[i].Value) && 910 BBCases[i].Dest != BBDefault) { 911 PredCases.push_back(BBCases[i]); 912 NewSuccessors.push_back(BBCases[i].Dest); 913 if (SuccHasWeights || PredHasWeights) { 914 // The default weight is at index 0, so weight for the ith case 915 // should be at index i+1. Scale the cases from successor by 916 // PredDefaultWeight (Weights[0]). 917 Weights.push_back(Weights[0] * SuccWeights[i+1]); 918 ValidTotalSuccWeight += SuccWeights[i+1]; 919 } 920 } 921 922 if (SuccHasWeights || PredHasWeights) { 923 ValidTotalSuccWeight += SuccWeights[0]; 924 // Scale the cases from predecessor by ValidTotalSuccWeight. 925 for (unsigned i = 1; i < CasesFromPred; ++i) 926 Weights[i] *= ValidTotalSuccWeight; 927 // Scale the default weight by SuccDefaultWeight (SuccWeights[0]). 928 Weights[0] *= SuccWeights[0]; 929 } 930 } else { 931 // If this is not the default destination from PSI, only the edges 932 // in SI that occur in PSI with a destination of BB will be 933 // activated. 934 std::set<ConstantInt*, ConstantIntOrdering> PTIHandled; 935 std::map<ConstantInt*, uint64_t> WeightsForHandled; 936 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 937 if (PredCases[i].Dest == BB) { 938 PTIHandled.insert(PredCases[i].Value); 939 940 if (PredHasWeights || SuccHasWeights) { 941 WeightsForHandled[PredCases[i].Value] = Weights[i+1]; 942 std::swap(Weights[i+1], Weights.back()); 943 Weights.pop_back(); 944 } 945 946 std::swap(PredCases[i], PredCases.back()); 947 PredCases.pop_back(); 948 --i; --e; 949 } 950 951 // Okay, now we know which constants were sent to BB from the 952 // predecessor. Figure out where they will all go now. 953 for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 954 if (PTIHandled.count(BBCases[i].Value)) { 955 // If this is one we are capable of getting... 956 if (PredHasWeights || SuccHasWeights) 957 Weights.push_back(WeightsForHandled[BBCases[i].Value]); 958 PredCases.push_back(BBCases[i]); 959 NewSuccessors.push_back(BBCases[i].Dest); 960 PTIHandled.erase(BBCases[i].Value);// This constant is taken care of 961 } 962 963 // If there are any constants vectored to BB that TI doesn't handle, 964 // they must go to the default destination of TI. 965 for (std::set<ConstantInt*, ConstantIntOrdering>::iterator I = 966 PTIHandled.begin(), 967 E = PTIHandled.end(); I != E; ++I) { 968 if (PredHasWeights || SuccHasWeights) 969 Weights.push_back(WeightsForHandled[*I]); 970 PredCases.push_back(ValueEqualityComparisonCase(*I, BBDefault)); 971 NewSuccessors.push_back(BBDefault); 972 } 973 } 974 975 // Okay, at this point, we know which new successor Pred will get. Make 976 // sure we update the number of entries in the PHI nodes for these 977 // successors. 978 for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i) 979 AddPredecessorToBlock(NewSuccessors[i], Pred, BB); 980 981 Builder.SetInsertPoint(PTI); 982 // Convert pointer to int before we switch. 983 if (CV->getType()->isPointerTy()) { 984 CV = Builder.CreatePtrToInt(CV, DL.getIntPtrType(CV->getType()), 985 "magicptr"); 986 } 987 988 // Now that the successors are updated, create the new Switch instruction. 989 SwitchInst *NewSI = Builder.CreateSwitch(CV, PredDefault, 990 PredCases.size()); 991 NewSI->setDebugLoc(PTI->getDebugLoc()); 992 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 993 NewSI->addCase(PredCases[i].Value, PredCases[i].Dest); 994 995 if (PredHasWeights || SuccHasWeights) { 996 // Halve the weights if any of them cannot fit in an uint32_t 997 FitWeights(Weights); 998 999 SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end()); 1000 1001 NewSI->setMetadata(LLVMContext::MD_prof, 1002 MDBuilder(BB->getContext()). 1003 createBranchWeights(MDWeights)); 1004 } 1005 1006 EraseTerminatorInstAndDCECond(PTI); 1007 1008 // Okay, last check. If BB is still a successor of PSI, then we must 1009 // have an infinite loop case. If so, add an infinitely looping block 1010 // to handle the case to preserve the behavior of the code. 1011 BasicBlock *InfLoopBlock = nullptr; 1012 for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i) 1013 if (NewSI->getSuccessor(i) == BB) { 1014 if (!InfLoopBlock) { 1015 // Insert it at the end of the function, because it's either code, 1016 // or it won't matter if it's hot. :) 1017 InfLoopBlock = BasicBlock::Create(BB->getContext(), 1018 "infloop", BB->getParent()); 1019 BranchInst::Create(InfLoopBlock, InfLoopBlock); 1020 } 1021 NewSI->setSuccessor(i, InfLoopBlock); 1022 } 1023 1024 Changed = true; 1025 } 1026 } 1027 return Changed; 1028 } 1029 1030 // isSafeToHoistInvoke - If we would need to insert a select that uses the 1031 // value of this invoke (comments in HoistThenElseCodeToIf explain why we 1032 // would need to do this), we can't hoist the invoke, as there is nowhere 1033 // to put the select in this case. 1034 static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, 1035 Instruction *I1, Instruction *I2) { 1036 for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 1037 PHINode *PN; 1038 for (BasicBlock::iterator BBI = SI->begin(); 1039 (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 1040 Value *BB1V = PN->getIncomingValueForBlock(BB1); 1041 Value *BB2V = PN->getIncomingValueForBlock(BB2); 1042 if (BB1V != BB2V && (BB1V==I1 || BB2V==I2)) { 1043 return false; 1044 } 1045 } 1046 } 1047 return true; 1048 } 1049 1050 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I); 1051 1052 /// HoistThenElseCodeToIf - Given a conditional branch that goes to BB1 and 1053 /// BB2, hoist any common code in the two blocks up into the branch block. The 1054 /// caller of this function guarantees that BI's block dominates BB1 and BB2. 1055 static bool HoistThenElseCodeToIf(BranchInst *BI, 1056 const TargetTransformInfo &TTI) { 1057 // This does very trivial matching, with limited scanning, to find identical 1058 // instructions in the two blocks. In particular, we don't want to get into 1059 // O(M*N) situations here where M and N are the sizes of BB1 and BB2. As 1060 // such, we currently just scan for obviously identical instructions in an 1061 // identical order. 1062 BasicBlock *BB1 = BI->getSuccessor(0); // The true destination. 1063 BasicBlock *BB2 = BI->getSuccessor(1); // The false destination 1064 1065 BasicBlock::iterator BB1_Itr = BB1->begin(); 1066 BasicBlock::iterator BB2_Itr = BB2->begin(); 1067 1068 Instruction *I1 = BB1_Itr++, *I2 = BB2_Itr++; 1069 // Skip debug info if it is not identical. 1070 DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1); 1071 DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2); 1072 if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) { 1073 while (isa<DbgInfoIntrinsic>(I1)) 1074 I1 = BB1_Itr++; 1075 while (isa<DbgInfoIntrinsic>(I2)) 1076 I2 = BB2_Itr++; 1077 } 1078 if (isa<PHINode>(I1) || !I1->isIdenticalToWhenDefined(I2) || 1079 (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2))) 1080 return false; 1081 1082 BasicBlock *BIParent = BI->getParent(); 1083 1084 bool Changed = false; 1085 do { 1086 // If we are hoisting the terminator instruction, don't move one (making a 1087 // broken BB), instead clone it, and remove BI. 1088 if (isa<TerminatorInst>(I1)) 1089 goto HoistTerminator; 1090 1091 if (!TTI.isProfitableToHoist(I1) || !TTI.isProfitableToHoist(I2)) 1092 return Changed; 1093 1094 // For a normal instruction, we just move one to right before the branch, 1095 // then replace all uses of the other with the first. Finally, we remove 1096 // the now redundant second instruction. 1097 BIParent->getInstList().splice(BI, BB1->getInstList(), I1); 1098 if (!I2->use_empty()) 1099 I2->replaceAllUsesWith(I1); 1100 I1->intersectOptionalDataWith(I2); 1101 unsigned KnownIDs[] = { 1102 LLVMContext::MD_tbaa, 1103 LLVMContext::MD_range, 1104 LLVMContext::MD_fpmath, 1105 LLVMContext::MD_invariant_load, 1106 LLVMContext::MD_nonnull 1107 }; 1108 combineMetadata(I1, I2, KnownIDs); 1109 I2->eraseFromParent(); 1110 Changed = true; 1111 1112 I1 = BB1_Itr++; 1113 I2 = BB2_Itr++; 1114 // Skip debug info if it is not identical. 1115 DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1); 1116 DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2); 1117 if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) { 1118 while (isa<DbgInfoIntrinsic>(I1)) 1119 I1 = BB1_Itr++; 1120 while (isa<DbgInfoIntrinsic>(I2)) 1121 I2 = BB2_Itr++; 1122 } 1123 } while (I1->isIdenticalToWhenDefined(I2)); 1124 1125 return true; 1126 1127 HoistTerminator: 1128 // It may not be possible to hoist an invoke. 1129 if (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)) 1130 return Changed; 1131 1132 for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 1133 PHINode *PN; 1134 for (BasicBlock::iterator BBI = SI->begin(); 1135 (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 1136 Value *BB1V = PN->getIncomingValueForBlock(BB1); 1137 Value *BB2V = PN->getIncomingValueForBlock(BB2); 1138 if (BB1V == BB2V) 1139 continue; 1140 1141 // Check for passingValueIsAlwaysUndefined here because we would rather 1142 // eliminate undefined control flow then converting it to a select. 1143 if (passingValueIsAlwaysUndefined(BB1V, PN) || 1144 passingValueIsAlwaysUndefined(BB2V, PN)) 1145 return Changed; 1146 1147 if (isa<ConstantExpr>(BB1V) && !isSafeToSpeculativelyExecute(BB1V)) 1148 return Changed; 1149 if (isa<ConstantExpr>(BB2V) && !isSafeToSpeculativelyExecute(BB2V)) 1150 return Changed; 1151 } 1152 } 1153 1154 // Okay, it is safe to hoist the terminator. 1155 Instruction *NT = I1->clone(); 1156 BIParent->getInstList().insert(BI, NT); 1157 if (!NT->getType()->isVoidTy()) { 1158 I1->replaceAllUsesWith(NT); 1159 I2->replaceAllUsesWith(NT); 1160 NT->takeName(I1); 1161 } 1162 1163 IRBuilder<true, NoFolder> Builder(NT); 1164 // Hoisting one of the terminators from our successor is a great thing. 1165 // Unfortunately, the successors of the if/else blocks may have PHI nodes in 1166 // them. If they do, all PHI entries for BB1/BB2 must agree for all PHI 1167 // nodes, so we insert select instruction to compute the final result. 1168 std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects; 1169 for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 1170 PHINode *PN; 1171 for (BasicBlock::iterator BBI = SI->begin(); 1172 (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 1173 Value *BB1V = PN->getIncomingValueForBlock(BB1); 1174 Value *BB2V = PN->getIncomingValueForBlock(BB2); 1175 if (BB1V == BB2V) continue; 1176 1177 // These values do not agree. Insert a select instruction before NT 1178 // that determines the right value. 1179 SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)]; 1180 if (!SI) 1181 SI = cast<SelectInst> 1182 (Builder.CreateSelect(BI->getCondition(), BB1V, BB2V, 1183 BB1V->getName()+"."+BB2V->getName())); 1184 1185 // Make the PHI node use the select for all incoming values for BB1/BB2 1186 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 1187 if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2) 1188 PN->setIncomingValue(i, SI); 1189 } 1190 } 1191 1192 // Update any PHI nodes in our new successors. 1193 for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) 1194 AddPredecessorToBlock(*SI, BIParent, BB1); 1195 1196 EraseTerminatorInstAndDCECond(BI); 1197 return true; 1198 } 1199 1200 /// SinkThenElseCodeToEnd - Given an unconditional branch that goes to BBEnd, 1201 /// check whether BBEnd has only two predecessors and the other predecessor 1202 /// ends with an unconditional branch. If it is true, sink any common code 1203 /// in the two predecessors to BBEnd. 1204 static bool SinkThenElseCodeToEnd(BranchInst *BI1) { 1205 assert(BI1->isUnconditional()); 1206 BasicBlock *BB1 = BI1->getParent(); 1207 BasicBlock *BBEnd = BI1->getSuccessor(0); 1208 1209 // Check that BBEnd has two predecessors and the other predecessor ends with 1210 // an unconditional branch. 1211 pred_iterator PI = pred_begin(BBEnd), PE = pred_end(BBEnd); 1212 BasicBlock *Pred0 = *PI++; 1213 if (PI == PE) // Only one predecessor. 1214 return false; 1215 BasicBlock *Pred1 = *PI++; 1216 if (PI != PE) // More than two predecessors. 1217 return false; 1218 BasicBlock *BB2 = (Pred0 == BB1) ? Pred1 : Pred0; 1219 BranchInst *BI2 = dyn_cast<BranchInst>(BB2->getTerminator()); 1220 if (!BI2 || !BI2->isUnconditional()) 1221 return false; 1222 1223 // Gather the PHI nodes in BBEnd. 1224 SmallDenseMap<std::pair<Value *, Value *>, PHINode *> JointValueMap; 1225 Instruction *FirstNonPhiInBBEnd = nullptr; 1226 for (BasicBlock::iterator I = BBEnd->begin(), E = BBEnd->end(); I != E; ++I) { 1227 if (PHINode *PN = dyn_cast<PHINode>(I)) { 1228 Value *BB1V = PN->getIncomingValueForBlock(BB1); 1229 Value *BB2V = PN->getIncomingValueForBlock(BB2); 1230 JointValueMap[std::make_pair(BB1V, BB2V)] = PN; 1231 } else { 1232 FirstNonPhiInBBEnd = &*I; 1233 break; 1234 } 1235 } 1236 if (!FirstNonPhiInBBEnd) 1237 return false; 1238 1239 // This does very trivial matching, with limited scanning, to find identical 1240 // instructions in the two blocks. We scan backward for obviously identical 1241 // instructions in an identical order. 1242 BasicBlock::InstListType::reverse_iterator RI1 = BB1->getInstList().rbegin(), 1243 RE1 = BB1->getInstList().rend(), 1244 RI2 = BB2->getInstList().rbegin(), 1245 RE2 = BB2->getInstList().rend(); 1246 // Skip debug info. 1247 while (RI1 != RE1 && isa<DbgInfoIntrinsic>(&*RI1)) ++RI1; 1248 if (RI1 == RE1) 1249 return false; 1250 while (RI2 != RE2 && isa<DbgInfoIntrinsic>(&*RI2)) ++RI2; 1251 if (RI2 == RE2) 1252 return false; 1253 // Skip the unconditional branches. 1254 ++RI1; 1255 ++RI2; 1256 1257 bool Changed = false; 1258 while (RI1 != RE1 && RI2 != RE2) { 1259 // Skip debug info. 1260 while (RI1 != RE1 && isa<DbgInfoIntrinsic>(&*RI1)) ++RI1; 1261 if (RI1 == RE1) 1262 return Changed; 1263 while (RI2 != RE2 && isa<DbgInfoIntrinsic>(&*RI2)) ++RI2; 1264 if (RI2 == RE2) 1265 return Changed; 1266 1267 Instruction *I1 = &*RI1, *I2 = &*RI2; 1268 auto InstPair = std::make_pair(I1, I2); 1269 // I1 and I2 should have a single use in the same PHI node, and they 1270 // perform the same operation. 1271 // Cannot move control-flow-involving, volatile loads, vaarg, etc. 1272 if (isa<PHINode>(I1) || isa<PHINode>(I2) || 1273 isa<TerminatorInst>(I1) || isa<TerminatorInst>(I2) || 1274 isa<LandingPadInst>(I1) || isa<LandingPadInst>(I2) || 1275 isa<AllocaInst>(I1) || isa<AllocaInst>(I2) || 1276 I1->mayHaveSideEffects() || I2->mayHaveSideEffects() || 1277 I1->mayReadOrWriteMemory() || I2->mayReadOrWriteMemory() || 1278 !I1->hasOneUse() || !I2->hasOneUse() || 1279 !JointValueMap.count(InstPair)) 1280 return Changed; 1281 1282 // Check whether we should swap the operands of ICmpInst. 1283 // TODO: Add support of communativity. 1284 ICmpInst *ICmp1 = dyn_cast<ICmpInst>(I1), *ICmp2 = dyn_cast<ICmpInst>(I2); 1285 bool SwapOpnds = false; 1286 if (ICmp1 && ICmp2 && 1287 ICmp1->getOperand(0) != ICmp2->getOperand(0) && 1288 ICmp1->getOperand(1) != ICmp2->getOperand(1) && 1289 (ICmp1->getOperand(0) == ICmp2->getOperand(1) || 1290 ICmp1->getOperand(1) == ICmp2->getOperand(0))) { 1291 ICmp2->swapOperands(); 1292 SwapOpnds = true; 1293 } 1294 if (!I1->isSameOperationAs(I2)) { 1295 if (SwapOpnds) 1296 ICmp2->swapOperands(); 1297 return Changed; 1298 } 1299 1300 // The operands should be either the same or they need to be generated 1301 // with a PHI node after sinking. We only handle the case where there is 1302 // a single pair of different operands. 1303 Value *DifferentOp1 = nullptr, *DifferentOp2 = nullptr; 1304 unsigned Op1Idx = ~0U; 1305 for (unsigned I = 0, E = I1->getNumOperands(); I != E; ++I) { 1306 if (I1->getOperand(I) == I2->getOperand(I)) 1307 continue; 1308 // Early exit if we have more-than one pair of different operands or if 1309 // we need a PHI node to replace a constant. 1310 if (Op1Idx != ~0U || 1311 isa<Constant>(I1->getOperand(I)) || 1312 isa<Constant>(I2->getOperand(I))) { 1313 // If we can't sink the instructions, undo the swapping. 1314 if (SwapOpnds) 1315 ICmp2->swapOperands(); 1316 return Changed; 1317 } 1318 DifferentOp1 = I1->getOperand(I); 1319 Op1Idx = I; 1320 DifferentOp2 = I2->getOperand(I); 1321 } 1322 1323 DEBUG(dbgs() << "SINK common instructions " << *I1 << "\n"); 1324 DEBUG(dbgs() << " " << *I2 << "\n"); 1325 1326 // We insert the pair of different operands to JointValueMap and 1327 // remove (I1, I2) from JointValueMap. 1328 if (Op1Idx != ~0U) { 1329 auto &NewPN = JointValueMap[std::make_pair(DifferentOp1, DifferentOp2)]; 1330 if (!NewPN) { 1331 NewPN = 1332 PHINode::Create(DifferentOp1->getType(), 2, 1333 DifferentOp1->getName() + ".sink", BBEnd->begin()); 1334 NewPN->addIncoming(DifferentOp1, BB1); 1335 NewPN->addIncoming(DifferentOp2, BB2); 1336 DEBUG(dbgs() << "Create PHI node " << *NewPN << "\n";); 1337 } 1338 // I1 should use NewPN instead of DifferentOp1. 1339 I1->setOperand(Op1Idx, NewPN); 1340 } 1341 PHINode *OldPN = JointValueMap[InstPair]; 1342 JointValueMap.erase(InstPair); 1343 1344 // We need to update RE1 and RE2 if we are going to sink the first 1345 // instruction in the basic block down. 1346 bool UpdateRE1 = (I1 == BB1->begin()), UpdateRE2 = (I2 == BB2->begin()); 1347 // Sink the instruction. 1348 BBEnd->getInstList().splice(FirstNonPhiInBBEnd, BB1->getInstList(), I1); 1349 if (!OldPN->use_empty()) 1350 OldPN->replaceAllUsesWith(I1); 1351 OldPN->eraseFromParent(); 1352 1353 if (!I2->use_empty()) 1354 I2->replaceAllUsesWith(I1); 1355 I1->intersectOptionalDataWith(I2); 1356 // TODO: Use combineMetadata here to preserve what metadata we can 1357 // (analogous to the hoisting case above). 1358 I2->eraseFromParent(); 1359 1360 if (UpdateRE1) 1361 RE1 = BB1->getInstList().rend(); 1362 if (UpdateRE2) 1363 RE2 = BB2->getInstList().rend(); 1364 FirstNonPhiInBBEnd = I1; 1365 NumSinkCommons++; 1366 Changed = true; 1367 } 1368 return Changed; 1369 } 1370 1371 /// \brief Determine if we can hoist sink a sole store instruction out of a 1372 /// conditional block. 1373 /// 1374 /// We are looking for code like the following: 1375 /// BrBB: 1376 /// store i32 %add, i32* %arrayidx2 1377 /// ... // No other stores or function calls (we could be calling a memory 1378 /// ... // function). 1379 /// %cmp = icmp ult %x, %y 1380 /// br i1 %cmp, label %EndBB, label %ThenBB 1381 /// ThenBB: 1382 /// store i32 %add5, i32* %arrayidx2 1383 /// br label EndBB 1384 /// EndBB: 1385 /// ... 1386 /// We are going to transform this into: 1387 /// BrBB: 1388 /// store i32 %add, i32* %arrayidx2 1389 /// ... // 1390 /// %cmp = icmp ult %x, %y 1391 /// %add.add5 = select i1 %cmp, i32 %add, %add5 1392 /// store i32 %add.add5, i32* %arrayidx2 1393 /// ... 1394 /// 1395 /// \return The pointer to the value of the previous store if the store can be 1396 /// hoisted into the predecessor block. 0 otherwise. 1397 static Value *isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, 1398 BasicBlock *StoreBB, BasicBlock *EndBB) { 1399 StoreInst *StoreToHoist = dyn_cast<StoreInst>(I); 1400 if (!StoreToHoist) 1401 return nullptr; 1402 1403 // Volatile or atomic. 1404 if (!StoreToHoist->isSimple()) 1405 return nullptr; 1406 1407 Value *StorePtr = StoreToHoist->getPointerOperand(); 1408 1409 // Look for a store to the same pointer in BrBB. 1410 unsigned MaxNumInstToLookAt = 10; 1411 for (BasicBlock::reverse_iterator RI = BrBB->rbegin(), 1412 RE = BrBB->rend(); RI != RE && (--MaxNumInstToLookAt); ++RI) { 1413 Instruction *CurI = &*RI; 1414 1415 // Could be calling an instruction that effects memory like free(). 1416 if (CurI->mayHaveSideEffects() && !isa<StoreInst>(CurI)) 1417 return nullptr; 1418 1419 StoreInst *SI = dyn_cast<StoreInst>(CurI); 1420 // Found the previous store make sure it stores to the same location. 1421 if (SI && SI->getPointerOperand() == StorePtr) 1422 // Found the previous store, return its value operand. 1423 return SI->getValueOperand(); 1424 else if (SI) 1425 return nullptr; // Unknown store. 1426 } 1427 1428 return nullptr; 1429 } 1430 1431 /// \brief Speculate a conditional basic block flattening the CFG. 1432 /// 1433 /// Note that this is a very risky transform currently. Speculating 1434 /// instructions like this is most often not desirable. Instead, there is an MI 1435 /// pass which can do it with full awareness of the resource constraints. 1436 /// However, some cases are "obvious" and we should do directly. An example of 1437 /// this is speculating a single, reasonably cheap instruction. 1438 /// 1439 /// There is only one distinct advantage to flattening the CFG at the IR level: 1440 /// it makes very common but simplistic optimizations such as are common in 1441 /// instcombine and the DAG combiner more powerful by removing CFG edges and 1442 /// modeling their effects with easier to reason about SSA value graphs. 1443 /// 1444 /// 1445 /// An illustration of this transform is turning this IR: 1446 /// \code 1447 /// BB: 1448 /// %cmp = icmp ult %x, %y 1449 /// br i1 %cmp, label %EndBB, label %ThenBB 1450 /// ThenBB: 1451 /// %sub = sub %x, %y 1452 /// br label BB2 1453 /// EndBB: 1454 /// %phi = phi [ %sub, %ThenBB ], [ 0, %EndBB ] 1455 /// ... 1456 /// \endcode 1457 /// 1458 /// Into this IR: 1459 /// \code 1460 /// BB: 1461 /// %cmp = icmp ult %x, %y 1462 /// %sub = sub %x, %y 1463 /// %cond = select i1 %cmp, 0, %sub 1464 /// ... 1465 /// \endcode 1466 /// 1467 /// \returns true if the conditional block is removed. 1468 static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB, 1469 const TargetTransformInfo &TTI) { 1470 // Be conservative for now. FP select instruction can often be expensive. 1471 Value *BrCond = BI->getCondition(); 1472 if (isa<FCmpInst>(BrCond)) 1473 return false; 1474 1475 BasicBlock *BB = BI->getParent(); 1476 BasicBlock *EndBB = ThenBB->getTerminator()->getSuccessor(0); 1477 1478 // If ThenBB is actually on the false edge of the conditional branch, remember 1479 // to swap the select operands later. 1480 bool Invert = false; 1481 if (ThenBB != BI->getSuccessor(0)) { 1482 assert(ThenBB == BI->getSuccessor(1) && "No edge from 'if' block?"); 1483 Invert = true; 1484 } 1485 assert(EndBB == BI->getSuccessor(!Invert) && "No edge from to end block"); 1486 1487 // Keep a count of how many times instructions are used within CondBB when 1488 // they are candidates for sinking into CondBB. Specifically: 1489 // - They are defined in BB, and 1490 // - They have no side effects, and 1491 // - All of their uses are in CondBB. 1492 SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts; 1493 1494 unsigned SpeculationCost = 0; 1495 Value *SpeculatedStoreValue = nullptr; 1496 StoreInst *SpeculatedStore = nullptr; 1497 for (BasicBlock::iterator BBI = ThenBB->begin(), 1498 BBE = std::prev(ThenBB->end()); 1499 BBI != BBE; ++BBI) { 1500 Instruction *I = BBI; 1501 // Skip debug info. 1502 if (isa<DbgInfoIntrinsic>(I)) 1503 continue; 1504 1505 // Only speculatively execute a single instruction (not counting the 1506 // terminator) for now. 1507 ++SpeculationCost; 1508 if (SpeculationCost > 1) 1509 return false; 1510 1511 // Don't hoist the instruction if it's unsafe or expensive. 1512 if (!isSafeToSpeculativelyExecute(I) && 1513 !(HoistCondStores && (SpeculatedStoreValue = isSafeToSpeculateStore( 1514 I, BB, ThenBB, EndBB)))) 1515 return false; 1516 if (!SpeculatedStoreValue && 1517 ComputeSpeculationCost(I, TTI) > 1518 PHINodeFoldingThreshold * TargetTransformInfo::TCC_Basic) 1519 return false; 1520 1521 // Store the store speculation candidate. 1522 if (SpeculatedStoreValue) 1523 SpeculatedStore = cast<StoreInst>(I); 1524 1525 // Do not hoist the instruction if any of its operands are defined but not 1526 // used in BB. The transformation will prevent the operand from 1527 // being sunk into the use block. 1528 for (User::op_iterator i = I->op_begin(), e = I->op_end(); 1529 i != e; ++i) { 1530 Instruction *OpI = dyn_cast<Instruction>(*i); 1531 if (!OpI || OpI->getParent() != BB || 1532 OpI->mayHaveSideEffects()) 1533 continue; // Not a candidate for sinking. 1534 1535 ++SinkCandidateUseCounts[OpI]; 1536 } 1537 } 1538 1539 // Consider any sink candidates which are only used in CondBB as costs for 1540 // speculation. Note, while we iterate over a DenseMap here, we are summing 1541 // and so iteration order isn't significant. 1542 for (SmallDenseMap<Instruction *, unsigned, 4>::iterator I = 1543 SinkCandidateUseCounts.begin(), E = SinkCandidateUseCounts.end(); 1544 I != E; ++I) 1545 if (I->first->getNumUses() == I->second) { 1546 ++SpeculationCost; 1547 if (SpeculationCost > 1) 1548 return false; 1549 } 1550 1551 // Check that the PHI nodes can be converted to selects. 1552 bool HaveRewritablePHIs = false; 1553 for (BasicBlock::iterator I = EndBB->begin(); 1554 PHINode *PN = dyn_cast<PHINode>(I); ++I) { 1555 Value *OrigV = PN->getIncomingValueForBlock(BB); 1556 Value *ThenV = PN->getIncomingValueForBlock(ThenBB); 1557 1558 // FIXME: Try to remove some of the duplication with HoistThenElseCodeToIf. 1559 // Skip PHIs which are trivial. 1560 if (ThenV == OrigV) 1561 continue; 1562 1563 // Don't convert to selects if we could remove undefined behavior instead. 1564 if (passingValueIsAlwaysUndefined(OrigV, PN) || 1565 passingValueIsAlwaysUndefined(ThenV, PN)) 1566 return false; 1567 1568 HaveRewritablePHIs = true; 1569 ConstantExpr *OrigCE = dyn_cast<ConstantExpr>(OrigV); 1570 ConstantExpr *ThenCE = dyn_cast<ConstantExpr>(ThenV); 1571 if (!OrigCE && !ThenCE) 1572 continue; // Known safe and cheap. 1573 1574 if ((ThenCE && !isSafeToSpeculativelyExecute(ThenCE)) || 1575 (OrigCE && !isSafeToSpeculativelyExecute(OrigCE))) 1576 return false; 1577 unsigned OrigCost = OrigCE ? ComputeSpeculationCost(OrigCE, TTI) : 0; 1578 unsigned ThenCost = ThenCE ? ComputeSpeculationCost(ThenCE, TTI) : 0; 1579 unsigned MaxCost = 2 * PHINodeFoldingThreshold * 1580 TargetTransformInfo::TCC_Basic; 1581 if (OrigCost + ThenCost > MaxCost) 1582 return false; 1583 1584 // Account for the cost of an unfolded ConstantExpr which could end up 1585 // getting expanded into Instructions. 1586 // FIXME: This doesn't account for how many operations are combined in the 1587 // constant expression. 1588 ++SpeculationCost; 1589 if (SpeculationCost > 1) 1590 return false; 1591 } 1592 1593 // If there are no PHIs to process, bail early. This helps ensure idempotence 1594 // as well. 1595 if (!HaveRewritablePHIs && !(HoistCondStores && SpeculatedStoreValue)) 1596 return false; 1597 1598 // If we get here, we can hoist the instruction and if-convert. 1599 DEBUG(dbgs() << "SPECULATIVELY EXECUTING BB" << *ThenBB << "\n";); 1600 1601 // Insert a select of the value of the speculated store. 1602 if (SpeculatedStoreValue) { 1603 IRBuilder<true, NoFolder> Builder(BI); 1604 Value *TrueV = SpeculatedStore->getValueOperand(); 1605 Value *FalseV = SpeculatedStoreValue; 1606 if (Invert) 1607 std::swap(TrueV, FalseV); 1608 Value *S = Builder.CreateSelect(BrCond, TrueV, FalseV, TrueV->getName() + 1609 "." + FalseV->getName()); 1610 SpeculatedStore->setOperand(0, S); 1611 } 1612 1613 // Hoist the instructions. 1614 BB->getInstList().splice(BI, ThenBB->getInstList(), ThenBB->begin(), 1615 std::prev(ThenBB->end())); 1616 1617 // Insert selects and rewrite the PHI operands. 1618 IRBuilder<true, NoFolder> Builder(BI); 1619 for (BasicBlock::iterator I = EndBB->begin(); 1620 PHINode *PN = dyn_cast<PHINode>(I); ++I) { 1621 unsigned OrigI = PN->getBasicBlockIndex(BB); 1622 unsigned ThenI = PN->getBasicBlockIndex(ThenBB); 1623 Value *OrigV = PN->getIncomingValue(OrigI); 1624 Value *ThenV = PN->getIncomingValue(ThenI); 1625 1626 // Skip PHIs which are trivial. 1627 if (OrigV == ThenV) 1628 continue; 1629 1630 // Create a select whose true value is the speculatively executed value and 1631 // false value is the preexisting value. Swap them if the branch 1632 // destinations were inverted. 1633 Value *TrueV = ThenV, *FalseV = OrigV; 1634 if (Invert) 1635 std::swap(TrueV, FalseV); 1636 Value *V = Builder.CreateSelect(BrCond, TrueV, FalseV, 1637 TrueV->getName() + "." + FalseV->getName()); 1638 PN->setIncomingValue(OrigI, V); 1639 PN->setIncomingValue(ThenI, V); 1640 } 1641 1642 ++NumSpeculations; 1643 return true; 1644 } 1645 1646 /// \returns True if this block contains a CallInst with the NoDuplicate 1647 /// attribute. 1648 static bool HasNoDuplicateCall(const BasicBlock *BB) { 1649 for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 1650 const CallInst *CI = dyn_cast<CallInst>(I); 1651 if (!CI) 1652 continue; 1653 if (CI->cannotDuplicate()) 1654 return true; 1655 } 1656 return false; 1657 } 1658 1659 /// BlockIsSimpleEnoughToThreadThrough - Return true if we can thread a branch 1660 /// across this block. 1661 static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) { 1662 BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 1663 unsigned Size = 0; 1664 1665 for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { 1666 if (isa<DbgInfoIntrinsic>(BBI)) 1667 continue; 1668 if (Size > 10) return false; // Don't clone large BB's. 1669 ++Size; 1670 1671 // We can only support instructions that do not define values that are 1672 // live outside of the current basic block. 1673 for (User *U : BBI->users()) { 1674 Instruction *UI = cast<Instruction>(U); 1675 if (UI->getParent() != BB || isa<PHINode>(UI)) return false; 1676 } 1677 1678 // Looks ok, continue checking. 1679 } 1680 1681 return true; 1682 } 1683 1684 /// FoldCondBranchOnPHI - If we have a conditional branch on a PHI node value 1685 /// that is defined in the same block as the branch and if any PHI entries are 1686 /// constants, thread edges corresponding to that entry to be branches to their 1687 /// ultimate destination. 1688 static bool FoldCondBranchOnPHI(BranchInst *BI, const DataLayout &DL) { 1689 BasicBlock *BB = BI->getParent(); 1690 PHINode *PN = dyn_cast<PHINode>(BI->getCondition()); 1691 // NOTE: we currently cannot transform this case if the PHI node is used 1692 // outside of the block. 1693 if (!PN || PN->getParent() != BB || !PN->hasOneUse()) 1694 return false; 1695 1696 // Degenerate case of a single entry PHI. 1697 if (PN->getNumIncomingValues() == 1) { 1698 FoldSingleEntryPHINodes(PN->getParent()); 1699 return true; 1700 } 1701 1702 // Now we know that this block has multiple preds and two succs. 1703 if (!BlockIsSimpleEnoughToThreadThrough(BB)) return false; 1704 1705 if (HasNoDuplicateCall(BB)) return false; 1706 1707 // Okay, this is a simple enough basic block. See if any phi values are 1708 // constants. 1709 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1710 ConstantInt *CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i)); 1711 if (!CB || !CB->getType()->isIntegerTy(1)) continue; 1712 1713 // Okay, we now know that all edges from PredBB should be revectored to 1714 // branch to RealDest. 1715 BasicBlock *PredBB = PN->getIncomingBlock(i); 1716 BasicBlock *RealDest = BI->getSuccessor(!CB->getZExtValue()); 1717 1718 if (RealDest == BB) continue; // Skip self loops. 1719 // Skip if the predecessor's terminator is an indirect branch. 1720 if (isa<IndirectBrInst>(PredBB->getTerminator())) continue; 1721 1722 // The dest block might have PHI nodes, other predecessors and other 1723 // difficult cases. Instead of being smart about this, just insert a new 1724 // block that jumps to the destination block, effectively splitting 1725 // the edge we are about to create. 1726 BasicBlock *EdgeBB = BasicBlock::Create(BB->getContext(), 1727 RealDest->getName()+".critedge", 1728 RealDest->getParent(), RealDest); 1729 BranchInst::Create(RealDest, EdgeBB); 1730 1731 // Update PHI nodes. 1732 AddPredecessorToBlock(RealDest, EdgeBB, BB); 1733 1734 // BB may have instructions that are being threaded over. Clone these 1735 // instructions into EdgeBB. We know that there will be no uses of the 1736 // cloned instructions outside of EdgeBB. 1737 BasicBlock::iterator InsertPt = EdgeBB->begin(); 1738 DenseMap<Value*, Value*> TranslateMap; // Track translated values. 1739 for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { 1740 if (PHINode *PN = dyn_cast<PHINode>(BBI)) { 1741 TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB); 1742 continue; 1743 } 1744 // Clone the instruction. 1745 Instruction *N = BBI->clone(); 1746 if (BBI->hasName()) N->setName(BBI->getName()+".c"); 1747 1748 // Update operands due to translation. 1749 for (User::op_iterator i = N->op_begin(), e = N->op_end(); 1750 i != e; ++i) { 1751 DenseMap<Value*, Value*>::iterator PI = TranslateMap.find(*i); 1752 if (PI != TranslateMap.end()) 1753 *i = PI->second; 1754 } 1755 1756 // Check for trivial simplification. 1757 if (Value *V = SimplifyInstruction(N, DL)) { 1758 TranslateMap[BBI] = V; 1759 delete N; // Instruction folded away, don't need actual inst 1760 } else { 1761 // Insert the new instruction into its new home. 1762 EdgeBB->getInstList().insert(InsertPt, N); 1763 if (!BBI->use_empty()) 1764 TranslateMap[BBI] = N; 1765 } 1766 } 1767 1768 // Loop over all of the edges from PredBB to BB, changing them to branch 1769 // to EdgeBB instead. 1770 TerminatorInst *PredBBTI = PredBB->getTerminator(); 1771 for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i) 1772 if (PredBBTI->getSuccessor(i) == BB) { 1773 BB->removePredecessor(PredBB); 1774 PredBBTI->setSuccessor(i, EdgeBB); 1775 } 1776 1777 // Recurse, simplifying any other constants. 1778 return FoldCondBranchOnPHI(BI, DL) | true; 1779 } 1780 1781 return false; 1782 } 1783 1784 /// FoldTwoEntryPHINode - Given a BB that starts with the specified two-entry 1785 /// PHI node, see if we can eliminate it. 1786 static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, 1787 const DataLayout &DL) { 1788 // Ok, this is a two entry PHI node. Check to see if this is a simple "if 1789 // statement", which has a very simple dominance structure. Basically, we 1790 // are trying to find the condition that is being branched on, which 1791 // subsequently causes this merge to happen. We really want control 1792 // dependence information for this check, but simplifycfg can't keep it up 1793 // to date, and this catches most of the cases we care about anyway. 1794 BasicBlock *BB = PN->getParent(); 1795 BasicBlock *IfTrue, *IfFalse; 1796 Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse); 1797 if (!IfCond || 1798 // Don't bother if the branch will be constant folded trivially. 1799 isa<ConstantInt>(IfCond)) 1800 return false; 1801 1802 // Okay, we found that we can merge this two-entry phi node into a select. 1803 // Doing so would require us to fold *all* two entry phi nodes in this block. 1804 // At some point this becomes non-profitable (particularly if the target 1805 // doesn't support cmov's). Only do this transformation if there are two or 1806 // fewer PHI nodes in this block. 1807 unsigned NumPhis = 0; 1808 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++NumPhis, ++I) 1809 if (NumPhis > 2) 1810 return false; 1811 1812 // Loop over the PHI's seeing if we can promote them all to select 1813 // instructions. While we are at it, keep track of the instructions 1814 // that need to be moved to the dominating block. 1815 SmallPtrSet<Instruction*, 4> AggressiveInsts; 1816 unsigned MaxCostVal0 = PHINodeFoldingThreshold, 1817 MaxCostVal1 = PHINodeFoldingThreshold; 1818 MaxCostVal0 *= TargetTransformInfo::TCC_Basic; 1819 MaxCostVal1 *= TargetTransformInfo::TCC_Basic; 1820 1821 for (BasicBlock::iterator II = BB->begin(); isa<PHINode>(II);) { 1822 PHINode *PN = cast<PHINode>(II++); 1823 if (Value *V = SimplifyInstruction(PN, DL)) { 1824 PN->replaceAllUsesWith(V); 1825 PN->eraseFromParent(); 1826 continue; 1827 } 1828 1829 if (!DominatesMergePoint(PN->getIncomingValue(0), BB, &AggressiveInsts, 1830 MaxCostVal0, TTI) || 1831 !DominatesMergePoint(PN->getIncomingValue(1), BB, &AggressiveInsts, 1832 MaxCostVal1, TTI)) 1833 return false; 1834 } 1835 1836 // If we folded the first phi, PN dangles at this point. Refresh it. If 1837 // we ran out of PHIs then we simplified them all. 1838 PN = dyn_cast<PHINode>(BB->begin()); 1839 if (!PN) return true; 1840 1841 // Don't fold i1 branches on PHIs which contain binary operators. These can 1842 // often be turned into switches and other things. 1843 if (PN->getType()->isIntegerTy(1) && 1844 (isa<BinaryOperator>(PN->getIncomingValue(0)) || 1845 isa<BinaryOperator>(PN->getIncomingValue(1)) || 1846 isa<BinaryOperator>(IfCond))) 1847 return false; 1848 1849 // If we all PHI nodes are promotable, check to make sure that all 1850 // instructions in the predecessor blocks can be promoted as well. If 1851 // not, we won't be able to get rid of the control flow, so it's not 1852 // worth promoting to select instructions. 1853 BasicBlock *DomBlock = nullptr; 1854 BasicBlock *IfBlock1 = PN->getIncomingBlock(0); 1855 BasicBlock *IfBlock2 = PN->getIncomingBlock(1); 1856 if (cast<BranchInst>(IfBlock1->getTerminator())->isConditional()) { 1857 IfBlock1 = nullptr; 1858 } else { 1859 DomBlock = *pred_begin(IfBlock1); 1860 for (BasicBlock::iterator I = IfBlock1->begin();!isa<TerminatorInst>(I);++I) 1861 if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) { 1862 // This is not an aggressive instruction that we can promote. 1863 // Because of this, we won't be able to get rid of the control 1864 // flow, so the xform is not worth it. 1865 return false; 1866 } 1867 } 1868 1869 if (cast<BranchInst>(IfBlock2->getTerminator())->isConditional()) { 1870 IfBlock2 = nullptr; 1871 } else { 1872 DomBlock = *pred_begin(IfBlock2); 1873 for (BasicBlock::iterator I = IfBlock2->begin();!isa<TerminatorInst>(I);++I) 1874 if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) { 1875 // This is not an aggressive instruction that we can promote. 1876 // Because of this, we won't be able to get rid of the control 1877 // flow, so the xform is not worth it. 1878 return false; 1879 } 1880 } 1881 1882 DEBUG(dbgs() << "FOUND IF CONDITION! " << *IfCond << " T: " 1883 << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"); 1884 1885 // If we can still promote the PHI nodes after this gauntlet of tests, 1886 // do all of the PHI's now. 1887 Instruction *InsertPt = DomBlock->getTerminator(); 1888 IRBuilder<true, NoFolder> Builder(InsertPt); 1889 1890 // Move all 'aggressive' instructions, which are defined in the 1891 // conditional parts of the if's up to the dominating block. 1892 if (IfBlock1) 1893 DomBlock->getInstList().splice(InsertPt, 1894 IfBlock1->getInstList(), IfBlock1->begin(), 1895 IfBlock1->getTerminator()); 1896 if (IfBlock2) 1897 DomBlock->getInstList().splice(InsertPt, 1898 IfBlock2->getInstList(), IfBlock2->begin(), 1899 IfBlock2->getTerminator()); 1900 1901 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 1902 // Change the PHI node into a select instruction. 1903 Value *TrueVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); 1904 Value *FalseVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); 1905 1906 SelectInst *NV = 1907 cast<SelectInst>(Builder.CreateSelect(IfCond, TrueVal, FalseVal, "")); 1908 PN->replaceAllUsesWith(NV); 1909 NV->takeName(PN); 1910 PN->eraseFromParent(); 1911 } 1912 1913 // At this point, IfBlock1 and IfBlock2 are both empty, so our if statement 1914 // has been flattened. Change DomBlock to jump directly to our new block to 1915 // avoid other simplifycfg's kicking in on the diamond. 1916 TerminatorInst *OldTI = DomBlock->getTerminator(); 1917 Builder.SetInsertPoint(OldTI); 1918 Builder.CreateBr(BB); 1919 OldTI->eraseFromParent(); 1920 return true; 1921 } 1922 1923 /// SimplifyCondBranchToTwoReturns - If we found a conditional branch that goes 1924 /// to two returning blocks, try to merge them together into one return, 1925 /// introducing a select if the return values disagree. 1926 static bool SimplifyCondBranchToTwoReturns(BranchInst *BI, 1927 IRBuilder<> &Builder) { 1928 assert(BI->isConditional() && "Must be a conditional branch"); 1929 BasicBlock *TrueSucc = BI->getSuccessor(0); 1930 BasicBlock *FalseSucc = BI->getSuccessor(1); 1931 ReturnInst *TrueRet = cast<ReturnInst>(TrueSucc->getTerminator()); 1932 ReturnInst *FalseRet = cast<ReturnInst>(FalseSucc->getTerminator()); 1933 1934 // Check to ensure both blocks are empty (just a return) or optionally empty 1935 // with PHI nodes. If there are other instructions, merging would cause extra 1936 // computation on one path or the other. 1937 if (!TrueSucc->getFirstNonPHIOrDbg()->isTerminator()) 1938 return false; 1939 if (!FalseSucc->getFirstNonPHIOrDbg()->isTerminator()) 1940 return false; 1941 1942 Builder.SetInsertPoint(BI); 1943 // Okay, we found a branch that is going to two return nodes. If 1944 // there is no return value for this function, just change the 1945 // branch into a return. 1946 if (FalseRet->getNumOperands() == 0) { 1947 TrueSucc->removePredecessor(BI->getParent()); 1948 FalseSucc->removePredecessor(BI->getParent()); 1949 Builder.CreateRetVoid(); 1950 EraseTerminatorInstAndDCECond(BI); 1951 return true; 1952 } 1953 1954 // Otherwise, figure out what the true and false return values are 1955 // so we can insert a new select instruction. 1956 Value *TrueValue = TrueRet->getReturnValue(); 1957 Value *FalseValue = FalseRet->getReturnValue(); 1958 1959 // Unwrap any PHI nodes in the return blocks. 1960 if (PHINode *TVPN = dyn_cast_or_null<PHINode>(TrueValue)) 1961 if (TVPN->getParent() == TrueSucc) 1962 TrueValue = TVPN->getIncomingValueForBlock(BI->getParent()); 1963 if (PHINode *FVPN = dyn_cast_or_null<PHINode>(FalseValue)) 1964 if (FVPN->getParent() == FalseSucc) 1965 FalseValue = FVPN->getIncomingValueForBlock(BI->getParent()); 1966 1967 // In order for this transformation to be safe, we must be able to 1968 // unconditionally execute both operands to the return. This is 1969 // normally the case, but we could have a potentially-trapping 1970 // constant expression that prevents this transformation from being 1971 // safe. 1972 if (ConstantExpr *TCV = dyn_cast_or_null<ConstantExpr>(TrueValue)) 1973 if (TCV->canTrap()) 1974 return false; 1975 if (ConstantExpr *FCV = dyn_cast_or_null<ConstantExpr>(FalseValue)) 1976 if (FCV->canTrap()) 1977 return false; 1978 1979 // Okay, we collected all the mapped values and checked them for sanity, and 1980 // defined to really do this transformation. First, update the CFG. 1981 TrueSucc->removePredecessor(BI->getParent()); 1982 FalseSucc->removePredecessor(BI->getParent()); 1983 1984 // Insert select instructions where needed. 1985 Value *BrCond = BI->getCondition(); 1986 if (TrueValue) { 1987 // Insert a select if the results differ. 1988 if (TrueValue == FalseValue || isa<UndefValue>(FalseValue)) { 1989 } else if (isa<UndefValue>(TrueValue)) { 1990 TrueValue = FalseValue; 1991 } else { 1992 TrueValue = Builder.CreateSelect(BrCond, TrueValue, 1993 FalseValue, "retval"); 1994 } 1995 } 1996 1997 Value *RI = !TrueValue ? 1998 Builder.CreateRetVoid() : Builder.CreateRet(TrueValue); 1999 2000 (void) RI; 2001 2002 DEBUG(dbgs() << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:" 2003 << "\n " << *BI << "NewRet = " << *RI 2004 << "TRUEBLOCK: " << *TrueSucc << "FALSEBLOCK: "<< *FalseSucc); 2005 2006 EraseTerminatorInstAndDCECond(BI); 2007 2008 return true; 2009 } 2010 2011 /// ExtractBranchMetadata - Given a conditional BranchInstruction, retrieve the 2012 /// probabilities of the branch taking each edge. Fills in the two APInt 2013 /// parameters and return true, or returns false if no or invalid metadata was 2014 /// found. 2015 static bool ExtractBranchMetadata(BranchInst *BI, 2016 uint64_t &ProbTrue, uint64_t &ProbFalse) { 2017 assert(BI->isConditional() && 2018 "Looking for probabilities on unconditional branch?"); 2019 MDNode *ProfileData = BI->getMetadata(LLVMContext::MD_prof); 2020 if (!ProfileData || ProfileData->getNumOperands() != 3) return false; 2021 ConstantInt *CITrue = 2022 mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(1)); 2023 ConstantInt *CIFalse = 2024 mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(2)); 2025 if (!CITrue || !CIFalse) return false; 2026 ProbTrue = CITrue->getValue().getZExtValue(); 2027 ProbFalse = CIFalse->getValue().getZExtValue(); 2028 return true; 2029 } 2030 2031 /// checkCSEInPredecessor - Return true if the given instruction is available 2032 /// in its predecessor block. If yes, the instruction will be removed. 2033 /// 2034 static bool checkCSEInPredecessor(Instruction *Inst, BasicBlock *PB) { 2035 if (!isa<BinaryOperator>(Inst) && !isa<CmpInst>(Inst)) 2036 return false; 2037 for (BasicBlock::iterator I = PB->begin(), E = PB->end(); I != E; I++) { 2038 Instruction *PBI = &*I; 2039 // Check whether Inst and PBI generate the same value. 2040 if (Inst->isIdenticalTo(PBI)) { 2041 Inst->replaceAllUsesWith(PBI); 2042 Inst->eraseFromParent(); 2043 return true; 2044 } 2045 } 2046 return false; 2047 } 2048 2049 /// FoldBranchToCommonDest - If this basic block is simple enough, and if a 2050 /// predecessor branches to us and one of our successors, fold the block into 2051 /// the predecessor and use logical operations to pick the right destination. 2052 bool llvm::FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold) { 2053 BasicBlock *BB = BI->getParent(); 2054 2055 Instruction *Cond = nullptr; 2056 if (BI->isConditional()) 2057 Cond = dyn_cast<Instruction>(BI->getCondition()); 2058 else { 2059 // For unconditional branch, check for a simple CFG pattern, where 2060 // BB has a single predecessor and BB's successor is also its predecessor's 2061 // successor. If such pattern exisits, check for CSE between BB and its 2062 // predecessor. 2063 if (BasicBlock *PB = BB->getSinglePredecessor()) 2064 if (BranchInst *PBI = dyn_cast<BranchInst>(PB->getTerminator())) 2065 if (PBI->isConditional() && 2066 (BI->getSuccessor(0) == PBI->getSuccessor(0) || 2067 BI->getSuccessor(0) == PBI->getSuccessor(1))) { 2068 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); 2069 I != E; ) { 2070 Instruction *Curr = I++; 2071 if (isa<CmpInst>(Curr)) { 2072 Cond = Curr; 2073 break; 2074 } 2075 // Quit if we can't remove this instruction. 2076 if (!checkCSEInPredecessor(Curr, PB)) 2077 return false; 2078 } 2079 } 2080 2081 if (!Cond) 2082 return false; 2083 } 2084 2085 if (!Cond || (!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) || 2086 Cond->getParent() != BB || !Cond->hasOneUse()) 2087 return false; 2088 2089 // Make sure the instruction after the condition is the cond branch. 2090 BasicBlock::iterator CondIt = Cond; ++CondIt; 2091 2092 // Ignore dbg intrinsics. 2093 while (isa<DbgInfoIntrinsic>(CondIt)) ++CondIt; 2094 2095 if (&*CondIt != BI) 2096 return false; 2097 2098 // Only allow this transformation if computing the condition doesn't involve 2099 // too many instructions and these involved instructions can be executed 2100 // unconditionally. We denote all involved instructions except the condition 2101 // as "bonus instructions", and only allow this transformation when the 2102 // number of the bonus instructions does not exceed a certain threshold. 2103 unsigned NumBonusInsts = 0; 2104 for (auto I = BB->begin(); Cond != I; ++I) { 2105 // Ignore dbg intrinsics. 2106 if (isa<DbgInfoIntrinsic>(I)) 2107 continue; 2108 if (!I->hasOneUse() || !isSafeToSpeculativelyExecute(I)) 2109 return false; 2110 // I has only one use and can be executed unconditionally. 2111 Instruction *User = dyn_cast<Instruction>(I->user_back()); 2112 if (User == nullptr || User->getParent() != BB) 2113 return false; 2114 // I is used in the same BB. Since BI uses Cond and doesn't have more slots 2115 // to use any other instruction, User must be an instruction between next(I) 2116 // and Cond. 2117 ++NumBonusInsts; 2118 // Early exits once we reach the limit. 2119 if (NumBonusInsts > BonusInstThreshold) 2120 return false; 2121 } 2122 2123 // Cond is known to be a compare or binary operator. Check to make sure that 2124 // neither operand is a potentially-trapping constant expression. 2125 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(0))) 2126 if (CE->canTrap()) 2127 return false; 2128 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(1))) 2129 if (CE->canTrap()) 2130 return false; 2131 2132 // Finally, don't infinitely unroll conditional loops. 2133 BasicBlock *TrueDest = BI->getSuccessor(0); 2134 BasicBlock *FalseDest = (BI->isConditional()) ? BI->getSuccessor(1) : nullptr; 2135 if (TrueDest == BB || FalseDest == BB) 2136 return false; 2137 2138 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 2139 BasicBlock *PredBlock = *PI; 2140 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator()); 2141 2142 // Check that we have two conditional branches. If there is a PHI node in 2143 // the common successor, verify that the same value flows in from both 2144 // blocks. 2145 SmallVector<PHINode*, 4> PHIs; 2146 if (!PBI || PBI->isUnconditional() || 2147 (BI->isConditional() && 2148 !SafeToMergeTerminators(BI, PBI)) || 2149 (!BI->isConditional() && 2150 !isProfitableToFoldUnconditional(BI, PBI, Cond, PHIs))) 2151 continue; 2152 2153 // Determine if the two branches share a common destination. 2154 Instruction::BinaryOps Opc = Instruction::BinaryOpsEnd; 2155 bool InvertPredCond = false; 2156 2157 if (BI->isConditional()) { 2158 if (PBI->getSuccessor(0) == TrueDest) 2159 Opc = Instruction::Or; 2160 else if (PBI->getSuccessor(1) == FalseDest) 2161 Opc = Instruction::And; 2162 else if (PBI->getSuccessor(0) == FalseDest) 2163 Opc = Instruction::And, InvertPredCond = true; 2164 else if (PBI->getSuccessor(1) == TrueDest) 2165 Opc = Instruction::Or, InvertPredCond = true; 2166 else 2167 continue; 2168 } else { 2169 if (PBI->getSuccessor(0) != TrueDest && PBI->getSuccessor(1) != TrueDest) 2170 continue; 2171 } 2172 2173 DEBUG(dbgs() << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB); 2174 IRBuilder<> Builder(PBI); 2175 2176 // If we need to invert the condition in the pred block to match, do so now. 2177 if (InvertPredCond) { 2178 Value *NewCond = PBI->getCondition(); 2179 2180 if (NewCond->hasOneUse() && isa<CmpInst>(NewCond)) { 2181 CmpInst *CI = cast<CmpInst>(NewCond); 2182 CI->setPredicate(CI->getInversePredicate()); 2183 } else { 2184 NewCond = Builder.CreateNot(NewCond, 2185 PBI->getCondition()->getName()+".not"); 2186 } 2187 2188 PBI->setCondition(NewCond); 2189 PBI->swapSuccessors(); 2190 } 2191 2192 // If we have bonus instructions, clone them into the predecessor block. 2193 // Note that there may be mutliple predecessor blocks, so we cannot move 2194 // bonus instructions to a predecessor block. 2195 ValueToValueMapTy VMap; // maps original values to cloned values 2196 // We already make sure Cond is the last instruction before BI. Therefore, 2197 // every instructions before Cond other than DbgInfoIntrinsic are bonus 2198 // instructions. 2199 for (auto BonusInst = BB->begin(); Cond != BonusInst; ++BonusInst) { 2200 if (isa<DbgInfoIntrinsic>(BonusInst)) 2201 continue; 2202 Instruction *NewBonusInst = BonusInst->clone(); 2203 RemapInstruction(NewBonusInst, VMap, 2204 RF_NoModuleLevelChanges | RF_IgnoreMissingEntries); 2205 VMap[BonusInst] = NewBonusInst; 2206 2207 // If we moved a load, we cannot any longer claim any knowledge about 2208 // its potential value. The previous information might have been valid 2209 // only given the branch precondition. 2210 // For an analogous reason, we must also drop all the metadata whose 2211 // semantics we don't understand. 2212 NewBonusInst->dropUnknownMetadata(LLVMContext::MD_dbg); 2213 2214 PredBlock->getInstList().insert(PBI, NewBonusInst); 2215 NewBonusInst->takeName(BonusInst); 2216 BonusInst->setName(BonusInst->getName() + ".old"); 2217 } 2218 2219 // Clone Cond into the predecessor basic block, and or/and the 2220 // two conditions together. 2221 Instruction *New = Cond->clone(); 2222 RemapInstruction(New, VMap, 2223 RF_NoModuleLevelChanges | RF_IgnoreMissingEntries); 2224 PredBlock->getInstList().insert(PBI, New); 2225 New->takeName(Cond); 2226 Cond->setName(New->getName() + ".old"); 2227 2228 if (BI->isConditional()) { 2229 Instruction *NewCond = 2230 cast<Instruction>(Builder.CreateBinOp(Opc, PBI->getCondition(), 2231 New, "or.cond")); 2232 PBI->setCondition(NewCond); 2233 2234 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight; 2235 bool PredHasWeights = ExtractBranchMetadata(PBI, PredTrueWeight, 2236 PredFalseWeight); 2237 bool SuccHasWeights = ExtractBranchMetadata(BI, SuccTrueWeight, 2238 SuccFalseWeight); 2239 SmallVector<uint64_t, 8> NewWeights; 2240 2241 if (PBI->getSuccessor(0) == BB) { 2242 if (PredHasWeights && SuccHasWeights) { 2243 // PBI: br i1 %x, BB, FalseDest 2244 // BI: br i1 %y, TrueDest, FalseDest 2245 //TrueWeight is TrueWeight for PBI * TrueWeight for BI. 2246 NewWeights.push_back(PredTrueWeight * SuccTrueWeight); 2247 //FalseWeight is FalseWeight for PBI * TotalWeight for BI + 2248 // TrueWeight for PBI * FalseWeight for BI. 2249 // We assume that total weights of a BranchInst can fit into 32 bits. 2250 // Therefore, we will not have overflow using 64-bit arithmetic. 2251 NewWeights.push_back(PredFalseWeight * (SuccFalseWeight + 2252 SuccTrueWeight) + PredTrueWeight * SuccFalseWeight); 2253 } 2254 AddPredecessorToBlock(TrueDest, PredBlock, BB); 2255 PBI->setSuccessor(0, TrueDest); 2256 } 2257 if (PBI->getSuccessor(1) == BB) { 2258 if (PredHasWeights && SuccHasWeights) { 2259 // PBI: br i1 %x, TrueDest, BB 2260 // BI: br i1 %y, TrueDest, FalseDest 2261 //TrueWeight is TrueWeight for PBI * TotalWeight for BI + 2262 // FalseWeight for PBI * TrueWeight for BI. 2263 NewWeights.push_back(PredTrueWeight * (SuccFalseWeight + 2264 SuccTrueWeight) + PredFalseWeight * SuccTrueWeight); 2265 //FalseWeight is FalseWeight for PBI * FalseWeight for BI. 2266 NewWeights.push_back(PredFalseWeight * SuccFalseWeight); 2267 } 2268 AddPredecessorToBlock(FalseDest, PredBlock, BB); 2269 PBI->setSuccessor(1, FalseDest); 2270 } 2271 if (NewWeights.size() == 2) { 2272 // Halve the weights if any of them cannot fit in an uint32_t 2273 FitWeights(NewWeights); 2274 2275 SmallVector<uint32_t, 8> MDWeights(NewWeights.begin(),NewWeights.end()); 2276 PBI->setMetadata(LLVMContext::MD_prof, 2277 MDBuilder(BI->getContext()). 2278 createBranchWeights(MDWeights)); 2279 } else 2280 PBI->setMetadata(LLVMContext::MD_prof, nullptr); 2281 } else { 2282 // Update PHI nodes in the common successors. 2283 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) { 2284 ConstantInt *PBI_C = cast<ConstantInt>( 2285 PHIs[i]->getIncomingValueForBlock(PBI->getParent())); 2286 assert(PBI_C->getType()->isIntegerTy(1)); 2287 Instruction *MergedCond = nullptr; 2288 if (PBI->getSuccessor(0) == TrueDest) { 2289 // Create (PBI_Cond and PBI_C) or (!PBI_Cond and BI_Value) 2290 // PBI_C is true: PBI_Cond or (!PBI_Cond and BI_Value) 2291 // is false: !PBI_Cond and BI_Value 2292 Instruction *NotCond = 2293 cast<Instruction>(Builder.CreateNot(PBI->getCondition(), 2294 "not.cond")); 2295 MergedCond = 2296 cast<Instruction>(Builder.CreateBinOp(Instruction::And, 2297 NotCond, New, 2298 "and.cond")); 2299 if (PBI_C->isOne()) 2300 MergedCond = 2301 cast<Instruction>(Builder.CreateBinOp(Instruction::Or, 2302 PBI->getCondition(), MergedCond, 2303 "or.cond")); 2304 } else { 2305 // Create (PBI_Cond and BI_Value) or (!PBI_Cond and PBI_C) 2306 // PBI_C is true: (PBI_Cond and BI_Value) or (!PBI_Cond) 2307 // is false: PBI_Cond and BI_Value 2308 MergedCond = 2309 cast<Instruction>(Builder.CreateBinOp(Instruction::And, 2310 PBI->getCondition(), New, 2311 "and.cond")); 2312 if (PBI_C->isOne()) { 2313 Instruction *NotCond = 2314 cast<Instruction>(Builder.CreateNot(PBI->getCondition(), 2315 "not.cond")); 2316 MergedCond = 2317 cast<Instruction>(Builder.CreateBinOp(Instruction::Or, 2318 NotCond, MergedCond, 2319 "or.cond")); 2320 } 2321 } 2322 // Update PHI Node. 2323 PHIs[i]->setIncomingValue(PHIs[i]->getBasicBlockIndex(PBI->getParent()), 2324 MergedCond); 2325 } 2326 // Change PBI from Conditional to Unconditional. 2327 BranchInst *New_PBI = BranchInst::Create(TrueDest, PBI); 2328 EraseTerminatorInstAndDCECond(PBI); 2329 PBI = New_PBI; 2330 } 2331 2332 // TODO: If BB is reachable from all paths through PredBlock, then we 2333 // could replace PBI's branch probabilities with BI's. 2334 2335 // Copy any debug value intrinsics into the end of PredBlock. 2336 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 2337 if (isa<DbgInfoIntrinsic>(*I)) 2338 I->clone()->insertBefore(PBI); 2339 2340 return true; 2341 } 2342 return false; 2343 } 2344 2345 /// SimplifyCondBranchToCondBranch - If we have a conditional branch as a 2346 /// predecessor of another block, this function tries to simplify it. We know 2347 /// that PBI and BI are both conditional branches, and BI is in one of the 2348 /// successor blocks of PBI - PBI branches to BI. 2349 static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { 2350 assert(PBI->isConditional() && BI->isConditional()); 2351 BasicBlock *BB = BI->getParent(); 2352 2353 // If this block ends with a branch instruction, and if there is a 2354 // predecessor that ends on a branch of the same condition, make 2355 // this conditional branch redundant. 2356 if (PBI->getCondition() == BI->getCondition() && 2357 PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 2358 // Okay, the outcome of this conditional branch is statically 2359 // knowable. If this block had a single pred, handle specially. 2360 if (BB->getSinglePredecessor()) { 2361 // Turn this into a branch on constant. 2362 bool CondIsTrue = PBI->getSuccessor(0) == BB; 2363 BI->setCondition(ConstantInt::get(Type::getInt1Ty(BB->getContext()), 2364 CondIsTrue)); 2365 return true; // Nuke the branch on constant. 2366 } 2367 2368 // Otherwise, if there are multiple predecessors, insert a PHI that merges 2369 // in the constant and simplify the block result. Subsequent passes of 2370 // simplifycfg will thread the block. 2371 if (BlockIsSimpleEnoughToThreadThrough(BB)) { 2372 pred_iterator PB = pred_begin(BB), PE = pred_end(BB); 2373 PHINode *NewPN = PHINode::Create(Type::getInt1Ty(BB->getContext()), 2374 std::distance(PB, PE), 2375 BI->getCondition()->getName() + ".pr", 2376 BB->begin()); 2377 // Okay, we're going to insert the PHI node. Since PBI is not the only 2378 // predecessor, compute the PHI'd conditional value for all of the preds. 2379 // Any predecessor where the condition is not computable we keep symbolic. 2380 for (pred_iterator PI = PB; PI != PE; ++PI) { 2381 BasicBlock *P = *PI; 2382 if ((PBI = dyn_cast<BranchInst>(P->getTerminator())) && 2383 PBI != BI && PBI->isConditional() && 2384 PBI->getCondition() == BI->getCondition() && 2385 PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 2386 bool CondIsTrue = PBI->getSuccessor(0) == BB; 2387 NewPN->addIncoming(ConstantInt::get(Type::getInt1Ty(BB->getContext()), 2388 CondIsTrue), P); 2389 } else { 2390 NewPN->addIncoming(BI->getCondition(), P); 2391 } 2392 } 2393 2394 BI->setCondition(NewPN); 2395 return true; 2396 } 2397 } 2398 2399 // If this is a conditional branch in an empty block, and if any 2400 // predecessors are a conditional branch to one of our destinations, 2401 // fold the conditions into logical ops and one cond br. 2402 BasicBlock::iterator BBI = BB->begin(); 2403 // Ignore dbg intrinsics. 2404 while (isa<DbgInfoIntrinsic>(BBI)) 2405 ++BBI; 2406 if (&*BBI != BI) 2407 return false; 2408 2409 2410 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(BI->getCondition())) 2411 if (CE->canTrap()) 2412 return false; 2413 2414 int PBIOp, BIOp; 2415 if (PBI->getSuccessor(0) == BI->getSuccessor(0)) 2416 PBIOp = BIOp = 0; 2417 else if (PBI->getSuccessor(0) == BI->getSuccessor(1)) 2418 PBIOp = 0, BIOp = 1; 2419 else if (PBI->getSuccessor(1) == BI->getSuccessor(0)) 2420 PBIOp = 1, BIOp = 0; 2421 else if (PBI->getSuccessor(1) == BI->getSuccessor(1)) 2422 PBIOp = BIOp = 1; 2423 else 2424 return false; 2425 2426 // Check to make sure that the other destination of this branch 2427 // isn't BB itself. If so, this is an infinite loop that will 2428 // keep getting unwound. 2429 if (PBI->getSuccessor(PBIOp) == BB) 2430 return false; 2431 2432 // Do not perform this transformation if it would require 2433 // insertion of a large number of select instructions. For targets 2434 // without predication/cmovs, this is a big pessimization. 2435 2436 // Also do not perform this transformation if any phi node in the common 2437 // destination block can trap when reached by BB or PBB (PR17073). In that 2438 // case, it would be unsafe to hoist the operation into a select instruction. 2439 2440 BasicBlock *CommonDest = PBI->getSuccessor(PBIOp); 2441 unsigned NumPhis = 0; 2442 for (BasicBlock::iterator II = CommonDest->begin(); 2443 isa<PHINode>(II); ++II, ++NumPhis) { 2444 if (NumPhis > 2) // Disable this xform. 2445 return false; 2446 2447 PHINode *PN = cast<PHINode>(II); 2448 Value *BIV = PN->getIncomingValueForBlock(BB); 2449 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(BIV)) 2450 if (CE->canTrap()) 2451 return false; 2452 2453 unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent()); 2454 Value *PBIV = PN->getIncomingValue(PBBIdx); 2455 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(PBIV)) 2456 if (CE->canTrap()) 2457 return false; 2458 } 2459 2460 // Finally, if everything is ok, fold the branches to logical ops. 2461 BasicBlock *OtherDest = BI->getSuccessor(BIOp ^ 1); 2462 2463 DEBUG(dbgs() << "FOLDING BRs:" << *PBI->getParent() 2464 << "AND: " << *BI->getParent()); 2465 2466 2467 // If OtherDest *is* BB, then BB is a basic block with a single conditional 2468 // branch in it, where one edge (OtherDest) goes back to itself but the other 2469 // exits. We don't *know* that the program avoids the infinite loop 2470 // (even though that seems likely). If we do this xform naively, we'll end up 2471 // recursively unpeeling the loop. Since we know that (after the xform is 2472 // done) that the block *is* infinite if reached, we just make it an obviously 2473 // infinite loop with no cond branch. 2474 if (OtherDest == BB) { 2475 // Insert it at the end of the function, because it's either code, 2476 // or it won't matter if it's hot. :) 2477 BasicBlock *InfLoopBlock = BasicBlock::Create(BB->getContext(), 2478 "infloop", BB->getParent()); 2479 BranchInst::Create(InfLoopBlock, InfLoopBlock); 2480 OtherDest = InfLoopBlock; 2481 } 2482 2483 DEBUG(dbgs() << *PBI->getParent()->getParent()); 2484 2485 // BI may have other predecessors. Because of this, we leave 2486 // it alone, but modify PBI. 2487 2488 // Make sure we get to CommonDest on True&True directions. 2489 Value *PBICond = PBI->getCondition(); 2490 IRBuilder<true, NoFolder> Builder(PBI); 2491 if (PBIOp) 2492 PBICond = Builder.CreateNot(PBICond, PBICond->getName()+".not"); 2493 2494 Value *BICond = BI->getCondition(); 2495 if (BIOp) 2496 BICond = Builder.CreateNot(BICond, BICond->getName()+".not"); 2497 2498 // Merge the conditions. 2499 Value *Cond = Builder.CreateOr(PBICond, BICond, "brmerge"); 2500 2501 // Modify PBI to branch on the new condition to the new dests. 2502 PBI->setCondition(Cond); 2503 PBI->setSuccessor(0, CommonDest); 2504 PBI->setSuccessor(1, OtherDest); 2505 2506 // Update branch weight for PBI. 2507 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight; 2508 bool PredHasWeights = ExtractBranchMetadata(PBI, PredTrueWeight, 2509 PredFalseWeight); 2510 bool SuccHasWeights = ExtractBranchMetadata(BI, SuccTrueWeight, 2511 SuccFalseWeight); 2512 if (PredHasWeights && SuccHasWeights) { 2513 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight; 2514 uint64_t PredOther = PBIOp ?PredTrueWeight : PredFalseWeight; 2515 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight; 2516 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight; 2517 // The weight to CommonDest should be PredCommon * SuccTotal + 2518 // PredOther * SuccCommon. 2519 // The weight to OtherDest should be PredOther * SuccOther. 2520 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) + 2521 PredOther * SuccCommon, 2522 PredOther * SuccOther}; 2523 // Halve the weights if any of them cannot fit in an uint32_t 2524 FitWeights(NewWeights); 2525 2526 PBI->setMetadata(LLVMContext::MD_prof, 2527 MDBuilder(BI->getContext()) 2528 .createBranchWeights(NewWeights[0], NewWeights[1])); 2529 } 2530 2531 // OtherDest may have phi nodes. If so, add an entry from PBI's 2532 // block that are identical to the entries for BI's block. 2533 AddPredecessorToBlock(OtherDest, PBI->getParent(), BB); 2534 2535 // We know that the CommonDest already had an edge from PBI to 2536 // it. If it has PHIs though, the PHIs may have different 2537 // entries for BB and PBI's BB. If so, insert a select to make 2538 // them agree. 2539 PHINode *PN; 2540 for (BasicBlock::iterator II = CommonDest->begin(); 2541 (PN = dyn_cast<PHINode>(II)); ++II) { 2542 Value *BIV = PN->getIncomingValueForBlock(BB); 2543 unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent()); 2544 Value *PBIV = PN->getIncomingValue(PBBIdx); 2545 if (BIV != PBIV) { 2546 // Insert a select in PBI to pick the right value. 2547 Value *NV = cast<SelectInst> 2548 (Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->getName()+".mux")); 2549 PN->setIncomingValue(PBBIdx, NV); 2550 } 2551 } 2552 2553 DEBUG(dbgs() << "INTO: " << *PBI->getParent()); 2554 DEBUG(dbgs() << *PBI->getParent()->getParent()); 2555 2556 // This basic block is probably dead. We know it has at least 2557 // one fewer predecessor. 2558 return true; 2559 } 2560 2561 // SimplifyTerminatorOnSelect - Simplifies a terminator by replacing it with a 2562 // branch to TrueBB if Cond is true or to FalseBB if Cond is false. 2563 // Takes care of updating the successors and removing the old terminator. 2564 // Also makes sure not to introduce new successors by assuming that edges to 2565 // non-successor TrueBBs and FalseBBs aren't reachable. 2566 static bool SimplifyTerminatorOnSelect(TerminatorInst *OldTerm, Value *Cond, 2567 BasicBlock *TrueBB, BasicBlock *FalseBB, 2568 uint32_t TrueWeight, 2569 uint32_t FalseWeight){ 2570 // Remove any superfluous successor edges from the CFG. 2571 // First, figure out which successors to preserve. 2572 // If TrueBB and FalseBB are equal, only try to preserve one copy of that 2573 // successor. 2574 BasicBlock *KeepEdge1 = TrueBB; 2575 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : nullptr; 2576 2577 // Then remove the rest. 2578 for (unsigned I = 0, E = OldTerm->getNumSuccessors(); I != E; ++I) { 2579 BasicBlock *Succ = OldTerm->getSuccessor(I); 2580 // Make sure only to keep exactly one copy of each edge. 2581 if (Succ == KeepEdge1) 2582 KeepEdge1 = nullptr; 2583 else if (Succ == KeepEdge2) 2584 KeepEdge2 = nullptr; 2585 else 2586 Succ->removePredecessor(OldTerm->getParent()); 2587 } 2588 2589 IRBuilder<> Builder(OldTerm); 2590 Builder.SetCurrentDebugLocation(OldTerm->getDebugLoc()); 2591 2592 // Insert an appropriate new terminator. 2593 if (!KeepEdge1 && !KeepEdge2) { 2594 if (TrueBB == FalseBB) 2595 // We were only looking for one successor, and it was present. 2596 // Create an unconditional branch to it. 2597 Builder.CreateBr(TrueBB); 2598 else { 2599 // We found both of the successors we were looking for. 2600 // Create a conditional branch sharing the condition of the select. 2601 BranchInst *NewBI = Builder.CreateCondBr(Cond, TrueBB, FalseBB); 2602 if (TrueWeight != FalseWeight) 2603 NewBI->setMetadata(LLVMContext::MD_prof, 2604 MDBuilder(OldTerm->getContext()). 2605 createBranchWeights(TrueWeight, FalseWeight)); 2606 } 2607 } else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) { 2608 // Neither of the selected blocks were successors, so this 2609 // terminator must be unreachable. 2610 new UnreachableInst(OldTerm->getContext(), OldTerm); 2611 } else { 2612 // One of the selected values was a successor, but the other wasn't. 2613 // Insert an unconditional branch to the one that was found; 2614 // the edge to the one that wasn't must be unreachable. 2615 if (!KeepEdge1) 2616 // Only TrueBB was found. 2617 Builder.CreateBr(TrueBB); 2618 else 2619 // Only FalseBB was found. 2620 Builder.CreateBr(FalseBB); 2621 } 2622 2623 EraseTerminatorInstAndDCECond(OldTerm); 2624 return true; 2625 } 2626 2627 // SimplifySwitchOnSelect - Replaces 2628 // (switch (select cond, X, Y)) on constant X, Y 2629 // with a branch - conditional if X and Y lead to distinct BBs, 2630 // unconditional otherwise. 2631 static bool SimplifySwitchOnSelect(SwitchInst *SI, SelectInst *Select) { 2632 // Check for constant integer values in the select. 2633 ConstantInt *TrueVal = dyn_cast<ConstantInt>(Select->getTrueValue()); 2634 ConstantInt *FalseVal = dyn_cast<ConstantInt>(Select->getFalseValue()); 2635 if (!TrueVal || !FalseVal) 2636 return false; 2637 2638 // Find the relevant condition and destinations. 2639 Value *Condition = Select->getCondition(); 2640 BasicBlock *TrueBB = SI->findCaseValue(TrueVal).getCaseSuccessor(); 2641 BasicBlock *FalseBB = SI->findCaseValue(FalseVal).getCaseSuccessor(); 2642 2643 // Get weight for TrueBB and FalseBB. 2644 uint32_t TrueWeight = 0, FalseWeight = 0; 2645 SmallVector<uint64_t, 8> Weights; 2646 bool HasWeights = HasBranchWeights(SI); 2647 if (HasWeights) { 2648 GetBranchWeights(SI, Weights); 2649 if (Weights.size() == 1 + SI->getNumCases()) { 2650 TrueWeight = (uint32_t)Weights[SI->findCaseValue(TrueVal). 2651 getSuccessorIndex()]; 2652 FalseWeight = (uint32_t)Weights[SI->findCaseValue(FalseVal). 2653 getSuccessorIndex()]; 2654 } 2655 } 2656 2657 // Perform the actual simplification. 2658 return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, 2659 TrueWeight, FalseWeight); 2660 } 2661 2662 // SimplifyIndirectBrOnSelect - Replaces 2663 // (indirectbr (select cond, blockaddress(@fn, BlockA), 2664 // blockaddress(@fn, BlockB))) 2665 // with 2666 // (br cond, BlockA, BlockB). 2667 static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) { 2668 // Check that both operands of the select are block addresses. 2669 BlockAddress *TBA = dyn_cast<BlockAddress>(SI->getTrueValue()); 2670 BlockAddress *FBA = dyn_cast<BlockAddress>(SI->getFalseValue()); 2671 if (!TBA || !FBA) 2672 return false; 2673 2674 // Extract the actual blocks. 2675 BasicBlock *TrueBB = TBA->getBasicBlock(); 2676 BasicBlock *FalseBB = FBA->getBasicBlock(); 2677 2678 // Perform the actual simplification. 2679 return SimplifyTerminatorOnSelect(IBI, SI->getCondition(), TrueBB, FalseBB, 2680 0, 0); 2681 } 2682 2683 /// TryToSimplifyUncondBranchWithICmpInIt - This is called when we find an icmp 2684 /// instruction (a seteq/setne with a constant) as the only instruction in a 2685 /// block that ends with an uncond branch. We are looking for a very specific 2686 /// pattern that occurs when "A == 1 || A == 2 || A == 3" gets simplified. In 2687 /// this case, we merge the first two "or's of icmp" into a switch, but then the 2688 /// default value goes to an uncond block with a seteq in it, we get something 2689 /// like: 2690 /// 2691 /// switch i8 %A, label %DEFAULT [ i8 1, label %end i8 2, label %end ] 2692 /// DEFAULT: 2693 /// %tmp = icmp eq i8 %A, 92 2694 /// br label %end 2695 /// end: 2696 /// ... = phi i1 [ true, %entry ], [ %tmp, %DEFAULT ], [ true, %entry ] 2697 /// 2698 /// We prefer to split the edge to 'end' so that there is a true/false entry to 2699 /// the PHI, merging the third icmp into the switch. 2700 static bool TryToSimplifyUncondBranchWithICmpInIt( 2701 ICmpInst *ICI, IRBuilder<> &Builder, const DataLayout &DL, 2702 const TargetTransformInfo &TTI, unsigned BonusInstThreshold, 2703 AssumptionCache *AC) { 2704 BasicBlock *BB = ICI->getParent(); 2705 2706 // If the block has any PHIs in it or the icmp has multiple uses, it is too 2707 // complex. 2708 if (isa<PHINode>(BB->begin()) || !ICI->hasOneUse()) return false; 2709 2710 Value *V = ICI->getOperand(0); 2711 ConstantInt *Cst = cast<ConstantInt>(ICI->getOperand(1)); 2712 2713 // The pattern we're looking for is where our only predecessor is a switch on 2714 // 'V' and this block is the default case for the switch. In this case we can 2715 // fold the compared value into the switch to simplify things. 2716 BasicBlock *Pred = BB->getSinglePredecessor(); 2717 if (!Pred || !isa<SwitchInst>(Pred->getTerminator())) return false; 2718 2719 SwitchInst *SI = cast<SwitchInst>(Pred->getTerminator()); 2720 if (SI->getCondition() != V) 2721 return false; 2722 2723 // If BB is reachable on a non-default case, then we simply know the value of 2724 // V in this block. Substitute it and constant fold the icmp instruction 2725 // away. 2726 if (SI->getDefaultDest() != BB) { 2727 ConstantInt *VVal = SI->findCaseDest(BB); 2728 assert(VVal && "Should have a unique destination value"); 2729 ICI->setOperand(0, VVal); 2730 2731 if (Value *V = SimplifyInstruction(ICI, DL)) { 2732 ICI->replaceAllUsesWith(V); 2733 ICI->eraseFromParent(); 2734 } 2735 // BB is now empty, so it is likely to simplify away. 2736 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 2737 } 2738 2739 // Ok, the block is reachable from the default dest. If the constant we're 2740 // comparing exists in one of the other edges, then we can constant fold ICI 2741 // and zap it. 2742 if (SI->findCaseValue(Cst) != SI->case_default()) { 2743 Value *V; 2744 if (ICI->getPredicate() == ICmpInst::ICMP_EQ) 2745 V = ConstantInt::getFalse(BB->getContext()); 2746 else 2747 V = ConstantInt::getTrue(BB->getContext()); 2748 2749 ICI->replaceAllUsesWith(V); 2750 ICI->eraseFromParent(); 2751 // BB is now empty, so it is likely to simplify away. 2752 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 2753 } 2754 2755 // The use of the icmp has to be in the 'end' block, by the only PHI node in 2756 // the block. 2757 BasicBlock *SuccBlock = BB->getTerminator()->getSuccessor(0); 2758 PHINode *PHIUse = dyn_cast<PHINode>(ICI->user_back()); 2759 if (PHIUse == nullptr || PHIUse != &SuccBlock->front() || 2760 isa<PHINode>(++BasicBlock::iterator(PHIUse))) 2761 return false; 2762 2763 // If the icmp is a SETEQ, then the default dest gets false, the new edge gets 2764 // true in the PHI. 2765 Constant *DefaultCst = ConstantInt::getTrue(BB->getContext()); 2766 Constant *NewCst = ConstantInt::getFalse(BB->getContext()); 2767 2768 if (ICI->getPredicate() == ICmpInst::ICMP_EQ) 2769 std::swap(DefaultCst, NewCst); 2770 2771 // Replace ICI (which is used by the PHI for the default value) with true or 2772 // false depending on if it is EQ or NE. 2773 ICI->replaceAllUsesWith(DefaultCst); 2774 ICI->eraseFromParent(); 2775 2776 // Okay, the switch goes to this block on a default value. Add an edge from 2777 // the switch to the merge point on the compared value. 2778 BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "switch.edge", 2779 BB->getParent(), BB); 2780 SmallVector<uint64_t, 8> Weights; 2781 bool HasWeights = HasBranchWeights(SI); 2782 if (HasWeights) { 2783 GetBranchWeights(SI, Weights); 2784 if (Weights.size() == 1 + SI->getNumCases()) { 2785 // Split weight for default case to case for "Cst". 2786 Weights[0] = (Weights[0]+1) >> 1; 2787 Weights.push_back(Weights[0]); 2788 2789 SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end()); 2790 SI->setMetadata(LLVMContext::MD_prof, 2791 MDBuilder(SI->getContext()). 2792 createBranchWeights(MDWeights)); 2793 } 2794 } 2795 SI->addCase(Cst, NewBB); 2796 2797 // NewBB branches to the phi block, add the uncond branch and the phi entry. 2798 Builder.SetInsertPoint(NewBB); 2799 Builder.SetCurrentDebugLocation(SI->getDebugLoc()); 2800 Builder.CreateBr(SuccBlock); 2801 PHIUse->addIncoming(NewCst, NewBB); 2802 return true; 2803 } 2804 2805 /// SimplifyBranchOnICmpChain - The specified branch is a conditional branch. 2806 /// Check to see if it is branching on an or/and chain of icmp instructions, and 2807 /// fold it into a switch instruction if so. 2808 static bool SimplifyBranchOnICmpChain(BranchInst *BI, IRBuilder<> &Builder, 2809 const DataLayout &DL) { 2810 Instruction *Cond = dyn_cast<Instruction>(BI->getCondition()); 2811 if (!Cond) return false; 2812 2813 // Change br (X == 0 | X == 1), T, F into a switch instruction. 2814 // If this is a bunch of seteq's or'd together, or if it's a bunch of 2815 // 'setne's and'ed together, collect them. 2816 2817 // Try to gather values from a chain of and/or to be turned into a switch 2818 ConstantComparesGatherer ConstantCompare(Cond, DL); 2819 // Unpack the result 2820 SmallVectorImpl<ConstantInt*> &Values = ConstantCompare.Vals; 2821 Value *CompVal = ConstantCompare.CompValue; 2822 unsigned UsedICmps = ConstantCompare.UsedICmps; 2823 Value *ExtraCase = ConstantCompare.Extra; 2824 2825 // If we didn't have a multiply compared value, fail. 2826 if (!CompVal) return false; 2827 2828 // Avoid turning single icmps into a switch. 2829 if (UsedICmps <= 1) 2830 return false; 2831 2832 bool TrueWhenEqual = (Cond->getOpcode() == Instruction::Or); 2833 2834 // There might be duplicate constants in the list, which the switch 2835 // instruction can't handle, remove them now. 2836 array_pod_sort(Values.begin(), Values.end(), ConstantIntSortPredicate); 2837 Values.erase(std::unique(Values.begin(), Values.end()), Values.end()); 2838 2839 // If Extra was used, we require at least two switch values to do the 2840 // transformation. A switch with one value is just an cond branch. 2841 if (ExtraCase && Values.size() < 2) return false; 2842 2843 // TODO: Preserve branch weight metadata, similarly to how 2844 // FoldValueComparisonIntoPredecessors preserves it. 2845 2846 // Figure out which block is which destination. 2847 BasicBlock *DefaultBB = BI->getSuccessor(1); 2848 BasicBlock *EdgeBB = BI->getSuccessor(0); 2849 if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB); 2850 2851 BasicBlock *BB = BI->getParent(); 2852 2853 DEBUG(dbgs() << "Converting 'icmp' chain with " << Values.size() 2854 << " cases into SWITCH. BB is:\n" << *BB); 2855 2856 // If there are any extra values that couldn't be folded into the switch 2857 // then we evaluate them with an explicit branch first. Split the block 2858 // right before the condbr to handle it. 2859 if (ExtraCase) { 2860 BasicBlock *NewBB = BB->splitBasicBlock(BI, "switch.early.test"); 2861 // Remove the uncond branch added to the old block. 2862 TerminatorInst *OldTI = BB->getTerminator(); 2863 Builder.SetInsertPoint(OldTI); 2864 2865 if (TrueWhenEqual) 2866 Builder.CreateCondBr(ExtraCase, EdgeBB, NewBB); 2867 else 2868 Builder.CreateCondBr(ExtraCase, NewBB, EdgeBB); 2869 2870 OldTI->eraseFromParent(); 2871 2872 // If there are PHI nodes in EdgeBB, then we need to add a new entry to them 2873 // for the edge we just added. 2874 AddPredecessorToBlock(EdgeBB, BB, NewBB); 2875 2876 DEBUG(dbgs() << " ** 'icmp' chain unhandled condition: " << *ExtraCase 2877 << "\nEXTRABB = " << *BB); 2878 BB = NewBB; 2879 } 2880 2881 Builder.SetInsertPoint(BI); 2882 // Convert pointer to int before we switch. 2883 if (CompVal->getType()->isPointerTy()) { 2884 CompVal = Builder.CreatePtrToInt( 2885 CompVal, DL.getIntPtrType(CompVal->getType()), "magicptr"); 2886 } 2887 2888 // Create the new switch instruction now. 2889 SwitchInst *New = Builder.CreateSwitch(CompVal, DefaultBB, Values.size()); 2890 2891 // Add all of the 'cases' to the switch instruction. 2892 for (unsigned i = 0, e = Values.size(); i != e; ++i) 2893 New->addCase(Values[i], EdgeBB); 2894 2895 // We added edges from PI to the EdgeBB. As such, if there were any 2896 // PHI nodes in EdgeBB, they need entries to be added corresponding to 2897 // the number of edges added. 2898 for (BasicBlock::iterator BBI = EdgeBB->begin(); 2899 isa<PHINode>(BBI); ++BBI) { 2900 PHINode *PN = cast<PHINode>(BBI); 2901 Value *InVal = PN->getIncomingValueForBlock(BB); 2902 for (unsigned i = 0, e = Values.size()-1; i != e; ++i) 2903 PN->addIncoming(InVal, BB); 2904 } 2905 2906 // Erase the old branch instruction. 2907 EraseTerminatorInstAndDCECond(BI); 2908 2909 DEBUG(dbgs() << " ** 'icmp' chain result is:\n" << *BB << '\n'); 2910 return true; 2911 } 2912 2913 bool SimplifyCFGOpt::SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder) { 2914 // If this is a trivial landing pad that just continues unwinding the caught 2915 // exception then zap the landing pad, turning its invokes into calls. 2916 BasicBlock *BB = RI->getParent(); 2917 LandingPadInst *LPInst = dyn_cast<LandingPadInst>(BB->getFirstNonPHI()); 2918 if (RI->getValue() != LPInst) 2919 // Not a landing pad, or the resume is not unwinding the exception that 2920 // caused control to branch here. 2921 return false; 2922 2923 // Check that there are no other instructions except for debug intrinsics. 2924 BasicBlock::iterator I = LPInst, E = RI; 2925 while (++I != E) 2926 if (!isa<DbgInfoIntrinsic>(I)) 2927 return false; 2928 2929 // Turn all invokes that unwind here into calls and delete the basic block. 2930 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;) { 2931 InvokeInst *II = cast<InvokeInst>((*PI++)->getTerminator()); 2932 SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3); 2933 // Insert a call instruction before the invoke. 2934 CallInst *Call = CallInst::Create(II->getCalledValue(), Args, "", II); 2935 Call->takeName(II); 2936 Call->setCallingConv(II->getCallingConv()); 2937 Call->setAttributes(II->getAttributes()); 2938 Call->setDebugLoc(II->getDebugLoc()); 2939 2940 // Anything that used the value produced by the invoke instruction now uses 2941 // the value produced by the call instruction. Note that we do this even 2942 // for void functions and calls with no uses so that the callgraph edge is 2943 // updated. 2944 II->replaceAllUsesWith(Call); 2945 BB->removePredecessor(II->getParent()); 2946 2947 // Insert a branch to the normal destination right before the invoke. 2948 BranchInst::Create(II->getNormalDest(), II); 2949 2950 // Finally, delete the invoke instruction! 2951 II->eraseFromParent(); 2952 } 2953 2954 // The landingpad is now unreachable. Zap it. 2955 BB->eraseFromParent(); 2956 return true; 2957 } 2958 2959 bool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder) { 2960 BasicBlock *BB = RI->getParent(); 2961 if (!BB->getFirstNonPHIOrDbg()->isTerminator()) return false; 2962 2963 // Find predecessors that end with branches. 2964 SmallVector<BasicBlock*, 8> UncondBranchPreds; 2965 SmallVector<BranchInst*, 8> CondBranchPreds; 2966 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 2967 BasicBlock *P = *PI; 2968 TerminatorInst *PTI = P->getTerminator(); 2969 if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) { 2970 if (BI->isUnconditional()) 2971 UncondBranchPreds.push_back(P); 2972 else 2973 CondBranchPreds.push_back(BI); 2974 } 2975 } 2976 2977 // If we found some, do the transformation! 2978 if (!UncondBranchPreds.empty() && DupRet) { 2979 while (!UncondBranchPreds.empty()) { 2980 BasicBlock *Pred = UncondBranchPreds.pop_back_val(); 2981 DEBUG(dbgs() << "FOLDING: " << *BB 2982 << "INTO UNCOND BRANCH PRED: " << *Pred); 2983 (void)FoldReturnIntoUncondBranch(RI, BB, Pred); 2984 } 2985 2986 // If we eliminated all predecessors of the block, delete the block now. 2987 if (pred_empty(BB)) 2988 // We know there are no successors, so just nuke the block. 2989 BB->eraseFromParent(); 2990 2991 return true; 2992 } 2993 2994 // Check out all of the conditional branches going to this return 2995 // instruction. If any of them just select between returns, change the 2996 // branch itself into a select/return pair. 2997 while (!CondBranchPreds.empty()) { 2998 BranchInst *BI = CondBranchPreds.pop_back_val(); 2999 3000 // Check to see if the non-BB successor is also a return block. 3001 if (isa<ReturnInst>(BI->getSuccessor(0)->getTerminator()) && 3002 isa<ReturnInst>(BI->getSuccessor(1)->getTerminator()) && 3003 SimplifyCondBranchToTwoReturns(BI, Builder)) 3004 return true; 3005 } 3006 return false; 3007 } 3008 3009 bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) { 3010 BasicBlock *BB = UI->getParent(); 3011 3012 bool Changed = false; 3013 3014 // If there are any instructions immediately before the unreachable that can 3015 // be removed, do so. 3016 while (UI != BB->begin()) { 3017 BasicBlock::iterator BBI = UI; 3018 --BBI; 3019 // Do not delete instructions that can have side effects which might cause 3020 // the unreachable to not be reachable; specifically, calls and volatile 3021 // operations may have this effect. 3022 if (isa<CallInst>(BBI) && !isa<DbgInfoIntrinsic>(BBI)) break; 3023 3024 if (BBI->mayHaveSideEffects()) { 3025 if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) { 3026 if (SI->isVolatile()) 3027 break; 3028 } else if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) { 3029 if (LI->isVolatile()) 3030 break; 3031 } else if (AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(BBI)) { 3032 if (RMWI->isVolatile()) 3033 break; 3034 } else if (AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(BBI)) { 3035 if (CXI->isVolatile()) 3036 break; 3037 } else if (!isa<FenceInst>(BBI) && !isa<VAArgInst>(BBI) && 3038 !isa<LandingPadInst>(BBI)) { 3039 break; 3040 } 3041 // Note that deleting LandingPad's here is in fact okay, although it 3042 // involves a bit of subtle reasoning. If this inst is a LandingPad, 3043 // all the predecessors of this block will be the unwind edges of Invokes, 3044 // and we can therefore guarantee this block will be erased. 3045 } 3046 3047 // Delete this instruction (any uses are guaranteed to be dead) 3048 if (!BBI->use_empty()) 3049 BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); 3050 BBI->eraseFromParent(); 3051 Changed = true; 3052 } 3053 3054 // If the unreachable instruction is the first in the block, take a gander 3055 // at all of the predecessors of this instruction, and simplify them. 3056 if (&BB->front() != UI) return Changed; 3057 3058 SmallVector<BasicBlock*, 8> Preds(pred_begin(BB), pred_end(BB)); 3059 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 3060 TerminatorInst *TI = Preds[i]->getTerminator(); 3061 IRBuilder<> Builder(TI); 3062 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 3063 if (BI->isUnconditional()) { 3064 if (BI->getSuccessor(0) == BB) { 3065 new UnreachableInst(TI->getContext(), TI); 3066 TI->eraseFromParent(); 3067 Changed = true; 3068 } 3069 } else { 3070 if (BI->getSuccessor(0) == BB) { 3071 Builder.CreateBr(BI->getSuccessor(1)); 3072 EraseTerminatorInstAndDCECond(BI); 3073 } else if (BI->getSuccessor(1) == BB) { 3074 Builder.CreateBr(BI->getSuccessor(0)); 3075 EraseTerminatorInstAndDCECond(BI); 3076 Changed = true; 3077 } 3078 } 3079 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 3080 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); 3081 i != e; ++i) 3082 if (i.getCaseSuccessor() == BB) { 3083 BB->removePredecessor(SI->getParent()); 3084 SI->removeCase(i); 3085 --i; --e; 3086 Changed = true; 3087 } 3088 } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) { 3089 if (II->getUnwindDest() == BB) { 3090 // Convert the invoke to a call instruction. This would be a good 3091 // place to note that the call does not throw though. 3092 BranchInst *BI = Builder.CreateBr(II->getNormalDest()); 3093 II->removeFromParent(); // Take out of symbol table 3094 3095 // Insert the call now... 3096 SmallVector<Value*, 8> Args(II->op_begin(), II->op_end()-3); 3097 Builder.SetInsertPoint(BI); 3098 CallInst *CI = Builder.CreateCall(II->getCalledValue(), 3099 Args, II->getName()); 3100 CI->setCallingConv(II->getCallingConv()); 3101 CI->setAttributes(II->getAttributes()); 3102 // If the invoke produced a value, the call does now instead. 3103 II->replaceAllUsesWith(CI); 3104 delete II; 3105 Changed = true; 3106 } 3107 } 3108 } 3109 3110 // If this block is now dead, remove it. 3111 if (pred_empty(BB) && 3112 BB != &BB->getParent()->getEntryBlock()) { 3113 // We know there are no successors, so just nuke the block. 3114 BB->eraseFromParent(); 3115 return true; 3116 } 3117 3118 return Changed; 3119 } 3120 3121 static bool CasesAreContiguous(SmallVectorImpl<ConstantInt *> &Cases) { 3122 assert(Cases.size() >= 1); 3123 3124 array_pod_sort(Cases.begin(), Cases.end(), ConstantIntSortPredicate); 3125 for (size_t I = 1, E = Cases.size(); I != E; ++I) { 3126 if (Cases[I - 1]->getValue() != Cases[I]->getValue() + 1) 3127 return false; 3128 } 3129 return true; 3130 } 3131 3132 /// Turn a switch with two reachable destinations into an integer range 3133 /// comparison and branch. 3134 static bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder) { 3135 assert(SI->getNumCases() > 1 && "Degenerate switch?"); 3136 3137 bool HasDefault = 3138 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()); 3139 3140 // Partition the cases into two sets with different destinations. 3141 BasicBlock *DestA = HasDefault ? SI->getDefaultDest() : nullptr; 3142 BasicBlock *DestB = nullptr; 3143 SmallVector <ConstantInt *, 16> CasesA; 3144 SmallVector <ConstantInt *, 16> CasesB; 3145 3146 for (SwitchInst::CaseIt I : SI->cases()) { 3147 BasicBlock *Dest = I.getCaseSuccessor(); 3148 if (!DestA) DestA = Dest; 3149 if (Dest == DestA) { 3150 CasesA.push_back(I.getCaseValue()); 3151 continue; 3152 } 3153 if (!DestB) DestB = Dest; 3154 if (Dest == DestB) { 3155 CasesB.push_back(I.getCaseValue()); 3156 continue; 3157 } 3158 return false; // More than two destinations. 3159 } 3160 3161 assert(DestA && DestB && "Single-destination switch should have been folded."); 3162 assert(DestA != DestB); 3163 assert(DestB != SI->getDefaultDest()); 3164 assert(!CasesB.empty() && "There must be non-default cases."); 3165 assert(!CasesA.empty() || HasDefault); 3166 3167 // Figure out if one of the sets of cases form a contiguous range. 3168 SmallVectorImpl<ConstantInt *> *ContiguousCases = nullptr; 3169 BasicBlock *ContiguousDest = nullptr; 3170 BasicBlock *OtherDest = nullptr; 3171 if (!CasesA.empty() && CasesAreContiguous(CasesA)) { 3172 ContiguousCases = &CasesA; 3173 ContiguousDest = DestA; 3174 OtherDest = DestB; 3175 } else if (CasesAreContiguous(CasesB)) { 3176 ContiguousCases = &CasesB; 3177 ContiguousDest = DestB; 3178 OtherDest = DestA; 3179 } else 3180 return false; 3181 3182 // Start building the compare and branch. 3183 3184 Constant *Offset = ConstantExpr::getNeg(ContiguousCases->back()); 3185 Constant *NumCases = ConstantInt::get(Offset->getType(), ContiguousCases->size()); 3186 3187 Value *Sub = SI->getCondition(); 3188 if (!Offset->isNullValue()) 3189 Sub = Builder.CreateAdd(Sub, Offset, Sub->getName() + ".off"); 3190 3191 Value *Cmp; 3192 // If NumCases overflowed, then all possible values jump to the successor. 3193 if (NumCases->isNullValue() && !ContiguousCases->empty()) 3194 Cmp = ConstantInt::getTrue(SI->getContext()); 3195 else 3196 Cmp = Builder.CreateICmpULT(Sub, NumCases, "switch"); 3197 BranchInst *NewBI = Builder.CreateCondBr(Cmp, ContiguousDest, OtherDest); 3198 3199 // Update weight for the newly-created conditional branch. 3200 if (HasBranchWeights(SI)) { 3201 SmallVector<uint64_t, 8> Weights; 3202 GetBranchWeights(SI, Weights); 3203 if (Weights.size() == 1 + SI->getNumCases()) { 3204 uint64_t TrueWeight = 0; 3205 uint64_t FalseWeight = 0; 3206 for (size_t I = 0, E = Weights.size(); I != E; ++I) { 3207 if (SI->getSuccessor(I) == ContiguousDest) 3208 TrueWeight += Weights[I]; 3209 else 3210 FalseWeight += Weights[I]; 3211 } 3212 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) { 3213 TrueWeight /= 2; 3214 FalseWeight /= 2; 3215 } 3216 NewBI->setMetadata(LLVMContext::MD_prof, 3217 MDBuilder(SI->getContext()).createBranchWeights( 3218 (uint32_t)TrueWeight, (uint32_t)FalseWeight)); 3219 } 3220 } 3221 3222 // Prune obsolete incoming values off the successors' PHI nodes. 3223 for (auto BBI = ContiguousDest->begin(); isa<PHINode>(BBI); ++BBI) { 3224 unsigned PreviousEdges = ContiguousCases->size(); 3225 if (ContiguousDest == SI->getDefaultDest()) ++PreviousEdges; 3226 for (unsigned I = 0, E = PreviousEdges - 1; I != E; ++I) 3227 cast<PHINode>(BBI)->removeIncomingValue(SI->getParent()); 3228 } 3229 for (auto BBI = OtherDest->begin(); isa<PHINode>(BBI); ++BBI) { 3230 unsigned PreviousEdges = SI->getNumCases() - ContiguousCases->size(); 3231 if (OtherDest == SI->getDefaultDest()) ++PreviousEdges; 3232 for (unsigned I = 0, E = PreviousEdges - 1; I != E; ++I) 3233 cast<PHINode>(BBI)->removeIncomingValue(SI->getParent()); 3234 } 3235 3236 // Drop the switch. 3237 SI->eraseFromParent(); 3238 3239 return true; 3240 } 3241 3242 /// EliminateDeadSwitchCases - Compute masked bits for the condition of a switch 3243 /// and use it to remove dead cases. 3244 static bool EliminateDeadSwitchCases(SwitchInst *SI, AssumptionCache *AC, 3245 const DataLayout &DL) { 3246 Value *Cond = SI->getCondition(); 3247 unsigned Bits = Cond->getType()->getIntegerBitWidth(); 3248 APInt KnownZero(Bits, 0), KnownOne(Bits, 0); 3249 computeKnownBits(Cond, KnownZero, KnownOne, DL, 0, AC, SI); 3250 3251 // Gather dead cases. 3252 SmallVector<ConstantInt*, 8> DeadCases; 3253 for (SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end(); I != E; ++I) { 3254 if ((I.getCaseValue()->getValue() & KnownZero) != 0 || 3255 (I.getCaseValue()->getValue() & KnownOne) != KnownOne) { 3256 DeadCases.push_back(I.getCaseValue()); 3257 DEBUG(dbgs() << "SimplifyCFG: switch case '" 3258 << I.getCaseValue() << "' is dead.\n"); 3259 } 3260 } 3261 3262 SmallVector<uint64_t, 8> Weights; 3263 bool HasWeight = HasBranchWeights(SI); 3264 if (HasWeight) { 3265 GetBranchWeights(SI, Weights); 3266 HasWeight = (Weights.size() == 1 + SI->getNumCases()); 3267 } 3268 3269 // Remove dead cases from the switch. 3270 for (unsigned I = 0, E = DeadCases.size(); I != E; ++I) { 3271 SwitchInst::CaseIt Case = SI->findCaseValue(DeadCases[I]); 3272 assert(Case != SI->case_default() && 3273 "Case was not found. Probably mistake in DeadCases forming."); 3274 if (HasWeight) { 3275 std::swap(Weights[Case.getCaseIndex()+1], Weights.back()); 3276 Weights.pop_back(); 3277 } 3278 3279 // Prune unused values from PHI nodes. 3280 Case.getCaseSuccessor()->removePredecessor(SI->getParent()); 3281 SI->removeCase(Case); 3282 } 3283 if (HasWeight && Weights.size() >= 2) { 3284 SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end()); 3285 SI->setMetadata(LLVMContext::MD_prof, 3286 MDBuilder(SI->getParent()->getContext()). 3287 createBranchWeights(MDWeights)); 3288 } 3289 3290 return !DeadCases.empty(); 3291 } 3292 3293 /// FindPHIForConditionForwarding - If BB would be eligible for simplification 3294 /// by TryToSimplifyUncondBranchFromEmptyBlock (i.e. it is empty and terminated 3295 /// by an unconditional branch), look at the phi node for BB in the successor 3296 /// block and see if the incoming value is equal to CaseValue. If so, return 3297 /// the phi node, and set PhiIndex to BB's index in the phi node. 3298 static PHINode *FindPHIForConditionForwarding(ConstantInt *CaseValue, 3299 BasicBlock *BB, 3300 int *PhiIndex) { 3301 if (BB->getFirstNonPHIOrDbg() != BB->getTerminator()) 3302 return nullptr; // BB must be empty to be a candidate for simplification. 3303 if (!BB->getSinglePredecessor()) 3304 return nullptr; // BB must be dominated by the switch. 3305 3306 BranchInst *Branch = dyn_cast<BranchInst>(BB->getTerminator()); 3307 if (!Branch || !Branch->isUnconditional()) 3308 return nullptr; // Terminator must be unconditional branch. 3309 3310 BasicBlock *Succ = Branch->getSuccessor(0); 3311 3312 BasicBlock::iterator I = Succ->begin(); 3313 while (PHINode *PHI = dyn_cast<PHINode>(I++)) { 3314 int Idx = PHI->getBasicBlockIndex(BB); 3315 assert(Idx >= 0 && "PHI has no entry for predecessor?"); 3316 3317 Value *InValue = PHI->getIncomingValue(Idx); 3318 if (InValue != CaseValue) continue; 3319 3320 *PhiIndex = Idx; 3321 return PHI; 3322 } 3323 3324 return nullptr; 3325 } 3326 3327 /// ForwardSwitchConditionToPHI - Try to forward the condition of a switch 3328 /// instruction to a phi node dominated by the switch, if that would mean that 3329 /// some of the destination blocks of the switch can be folded away. 3330 /// Returns true if a change is made. 3331 static bool ForwardSwitchConditionToPHI(SwitchInst *SI) { 3332 typedef DenseMap<PHINode*, SmallVector<int,4> > ForwardingNodesMap; 3333 ForwardingNodesMap ForwardingNodes; 3334 3335 for (SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end(); I != E; ++I) { 3336 ConstantInt *CaseValue = I.getCaseValue(); 3337 BasicBlock *CaseDest = I.getCaseSuccessor(); 3338 3339 int PhiIndex; 3340 PHINode *PHI = FindPHIForConditionForwarding(CaseValue, CaseDest, 3341 &PhiIndex); 3342 if (!PHI) continue; 3343 3344 ForwardingNodes[PHI].push_back(PhiIndex); 3345 } 3346 3347 bool Changed = false; 3348 3349 for (ForwardingNodesMap::iterator I = ForwardingNodes.begin(), 3350 E = ForwardingNodes.end(); I != E; ++I) { 3351 PHINode *Phi = I->first; 3352 SmallVectorImpl<int> &Indexes = I->second; 3353 3354 if (Indexes.size() < 2) continue; 3355 3356 for (size_t I = 0, E = Indexes.size(); I != E; ++I) 3357 Phi->setIncomingValue(Indexes[I], SI->getCondition()); 3358 Changed = true; 3359 } 3360 3361 return Changed; 3362 } 3363 3364 /// ValidLookupTableConstant - Return true if the backend will be able to handle 3365 /// initializing an array of constants like C. 3366 static bool ValidLookupTableConstant(Constant *C) { 3367 if (C->isThreadDependent()) 3368 return false; 3369 if (C->isDLLImportDependent()) 3370 return false; 3371 3372 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) 3373 return CE->isGEPWithNoNotionalOverIndexing(); 3374 3375 return isa<ConstantFP>(C) || 3376 isa<ConstantInt>(C) || 3377 isa<ConstantPointerNull>(C) || 3378 isa<GlobalValue>(C) || 3379 isa<UndefValue>(C); 3380 } 3381 3382 /// LookupConstant - If V is a Constant, return it. Otherwise, try to look up 3383 /// its constant value in ConstantPool, returning 0 if it's not there. 3384 static Constant *LookupConstant(Value *V, 3385 const SmallDenseMap<Value*, Constant*>& ConstantPool) { 3386 if (Constant *C = dyn_cast<Constant>(V)) 3387 return C; 3388 return ConstantPool.lookup(V); 3389 } 3390 3391 /// ConstantFold - Try to fold instruction I into a constant. This works for 3392 /// simple instructions such as binary operations where both operands are 3393 /// constant or can be replaced by constants from the ConstantPool. Returns the 3394 /// resulting constant on success, 0 otherwise. 3395 static Constant * 3396 ConstantFold(Instruction *I, const DataLayout &DL, 3397 const SmallDenseMap<Value *, Constant *> &ConstantPool) { 3398 if (SelectInst *Select = dyn_cast<SelectInst>(I)) { 3399 Constant *A = LookupConstant(Select->getCondition(), ConstantPool); 3400 if (!A) 3401 return nullptr; 3402 if (A->isAllOnesValue()) 3403 return LookupConstant(Select->getTrueValue(), ConstantPool); 3404 if (A->isNullValue()) 3405 return LookupConstant(Select->getFalseValue(), ConstantPool); 3406 return nullptr; 3407 } 3408 3409 SmallVector<Constant *, 4> COps; 3410 for (unsigned N = 0, E = I->getNumOperands(); N != E; ++N) { 3411 if (Constant *A = LookupConstant(I->getOperand(N), ConstantPool)) 3412 COps.push_back(A); 3413 else 3414 return nullptr; 3415 } 3416 3417 if (CmpInst *Cmp = dyn_cast<CmpInst>(I)) { 3418 return ConstantFoldCompareInstOperands(Cmp->getPredicate(), COps[0], 3419 COps[1], DL); 3420 } 3421 3422 return ConstantFoldInstOperands(I->getOpcode(), I->getType(), COps, DL); 3423 } 3424 3425 /// GetCaseResults - Try to determine the resulting constant values in phi nodes 3426 /// at the common destination basic block, *CommonDest, for one of the case 3427 /// destionations CaseDest corresponding to value CaseVal (0 for the default 3428 /// case), of a switch instruction SI. 3429 static bool 3430 GetCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, 3431 BasicBlock **CommonDest, 3432 SmallVectorImpl<std::pair<PHINode *, Constant *>> &Res, 3433 const DataLayout &DL) { 3434 // The block from which we enter the common destination. 3435 BasicBlock *Pred = SI->getParent(); 3436 3437 // If CaseDest is empty except for some side-effect free instructions through 3438 // which we can constant-propagate the CaseVal, continue to its successor. 3439 SmallDenseMap<Value*, Constant*> ConstantPool; 3440 ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal)); 3441 for (BasicBlock::iterator I = CaseDest->begin(), E = CaseDest->end(); I != E; 3442 ++I) { 3443 if (TerminatorInst *T = dyn_cast<TerminatorInst>(I)) { 3444 // If the terminator is a simple branch, continue to the next block. 3445 if (T->getNumSuccessors() != 1) 3446 return false; 3447 Pred = CaseDest; 3448 CaseDest = T->getSuccessor(0); 3449 } else if (isa<DbgInfoIntrinsic>(I)) { 3450 // Skip debug intrinsic. 3451 continue; 3452 } else if (Constant *C = ConstantFold(I, DL, ConstantPool)) { 3453 // Instruction is side-effect free and constant. 3454 3455 // If the instruction has uses outside this block or a phi node slot for 3456 // the block, it is not safe to bypass the instruction since it would then 3457 // no longer dominate all its uses. 3458 for (auto &Use : I->uses()) { 3459 User *User = Use.getUser(); 3460 if (Instruction *I = dyn_cast<Instruction>(User)) 3461 if (I->getParent() == CaseDest) 3462 continue; 3463 if (PHINode *Phi = dyn_cast<PHINode>(User)) 3464 if (Phi->getIncomingBlock(Use) == CaseDest) 3465 continue; 3466 return false; 3467 } 3468 3469 ConstantPool.insert(std::make_pair(I, C)); 3470 } else { 3471 break; 3472 } 3473 } 3474 3475 // If we did not have a CommonDest before, use the current one. 3476 if (!*CommonDest) 3477 *CommonDest = CaseDest; 3478 // If the destination isn't the common one, abort. 3479 if (CaseDest != *CommonDest) 3480 return false; 3481 3482 // Get the values for this case from phi nodes in the destination block. 3483 BasicBlock::iterator I = (*CommonDest)->begin(); 3484 while (PHINode *PHI = dyn_cast<PHINode>(I++)) { 3485 int Idx = PHI->getBasicBlockIndex(Pred); 3486 if (Idx == -1) 3487 continue; 3488 3489 Constant *ConstVal = LookupConstant(PHI->getIncomingValue(Idx), 3490 ConstantPool); 3491 if (!ConstVal) 3492 return false; 3493 3494 // Be conservative about which kinds of constants we support. 3495 if (!ValidLookupTableConstant(ConstVal)) 3496 return false; 3497 3498 Res.push_back(std::make_pair(PHI, ConstVal)); 3499 } 3500 3501 return Res.size() > 0; 3502 } 3503 3504 // MapCaseToResult - Helper function used to 3505 // add CaseVal to the list of cases that generate Result. 3506 static void MapCaseToResult(ConstantInt *CaseVal, 3507 SwitchCaseResultVectorTy &UniqueResults, 3508 Constant *Result) { 3509 for (auto &I : UniqueResults) { 3510 if (I.first == Result) { 3511 I.second.push_back(CaseVal); 3512 return; 3513 } 3514 } 3515 UniqueResults.push_back(std::make_pair(Result, 3516 SmallVector<ConstantInt*, 4>(1, CaseVal))); 3517 } 3518 3519 // InitializeUniqueCases - Helper function that initializes a map containing 3520 // results for the PHI node of the common destination block for a switch 3521 // instruction. Returns false if multiple PHI nodes have been found or if 3522 // there is not a common destination block for the switch. 3523 static bool InitializeUniqueCases(SwitchInst *SI, PHINode *&PHI, 3524 BasicBlock *&CommonDest, 3525 SwitchCaseResultVectorTy &UniqueResults, 3526 Constant *&DefaultResult, 3527 const DataLayout &DL) { 3528 for (auto &I : SI->cases()) { 3529 ConstantInt *CaseVal = I.getCaseValue(); 3530 3531 // Resulting value at phi nodes for this case value. 3532 SwitchCaseResultsTy Results; 3533 if (!GetCaseResults(SI, CaseVal, I.getCaseSuccessor(), &CommonDest, Results, 3534 DL)) 3535 return false; 3536 3537 // Only one value per case is permitted 3538 if (Results.size() > 1) 3539 return false; 3540 MapCaseToResult(CaseVal, UniqueResults, Results.begin()->second); 3541 3542 // Check the PHI consistency. 3543 if (!PHI) 3544 PHI = Results[0].first; 3545 else if (PHI != Results[0].first) 3546 return false; 3547 } 3548 // Find the default result value. 3549 SmallVector<std::pair<PHINode *, Constant *>, 1> DefaultResults; 3550 BasicBlock *DefaultDest = SI->getDefaultDest(); 3551 GetCaseResults(SI, nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults, 3552 DL); 3553 // If the default value is not found abort unless the default destination 3554 // is unreachable. 3555 DefaultResult = 3556 DefaultResults.size() == 1 ? DefaultResults.begin()->second : nullptr; 3557 if ((!DefaultResult && 3558 !isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg()))) 3559 return false; 3560 3561 return true; 3562 } 3563 3564 // ConvertTwoCaseSwitch - Helper function that checks if it is possible to 3565 // transform a switch with only two cases (or two cases + default) 3566 // that produces a result into a value select. 3567 // Example: 3568 // switch (a) { 3569 // case 10: %0 = icmp eq i32 %a, 10 3570 // return 10; %1 = select i1 %0, i32 10, i32 4 3571 // case 20: ----> %2 = icmp eq i32 %a, 20 3572 // return 2; %3 = select i1 %2, i32 2, i32 %1 3573 // default: 3574 // return 4; 3575 // } 3576 static Value * 3577 ConvertTwoCaseSwitch(const SwitchCaseResultVectorTy &ResultVector, 3578 Constant *DefaultResult, Value *Condition, 3579 IRBuilder<> &Builder) { 3580 assert(ResultVector.size() == 2 && 3581 "We should have exactly two unique results at this point"); 3582 // If we are selecting between only two cases transform into a simple 3583 // select or a two-way select if default is possible. 3584 if (ResultVector[0].second.size() == 1 && 3585 ResultVector[1].second.size() == 1) { 3586 ConstantInt *const FirstCase = ResultVector[0].second[0]; 3587 ConstantInt *const SecondCase = ResultVector[1].second[0]; 3588 3589 bool DefaultCanTrigger = DefaultResult; 3590 Value *SelectValue = ResultVector[1].first; 3591 if (DefaultCanTrigger) { 3592 Value *const ValueCompare = 3593 Builder.CreateICmpEQ(Condition, SecondCase, "switch.selectcmp"); 3594 SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first, 3595 DefaultResult, "switch.select"); 3596 } 3597 Value *const ValueCompare = 3598 Builder.CreateICmpEQ(Condition, FirstCase, "switch.selectcmp"); 3599 return Builder.CreateSelect(ValueCompare, ResultVector[0].first, SelectValue, 3600 "switch.select"); 3601 } 3602 3603 return nullptr; 3604 } 3605 3606 // RemoveSwitchAfterSelectConversion - Helper function to cleanup a switch 3607 // instruction that has been converted into a select, fixing up PHI nodes and 3608 // basic blocks. 3609 static void RemoveSwitchAfterSelectConversion(SwitchInst *SI, PHINode *PHI, 3610 Value *SelectValue, 3611 IRBuilder<> &Builder) { 3612 BasicBlock *SelectBB = SI->getParent(); 3613 while (PHI->getBasicBlockIndex(SelectBB) >= 0) 3614 PHI->removeIncomingValue(SelectBB); 3615 PHI->addIncoming(SelectValue, SelectBB); 3616 3617 Builder.CreateBr(PHI->getParent()); 3618 3619 // Remove the switch. 3620 for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) { 3621 BasicBlock *Succ = SI->getSuccessor(i); 3622 3623 if (Succ == PHI->getParent()) 3624 continue; 3625 Succ->removePredecessor(SelectBB); 3626 } 3627 SI->eraseFromParent(); 3628 } 3629 3630 /// SwitchToSelect - If the switch is only used to initialize one or more 3631 /// phi nodes in a common successor block with only two different 3632 /// constant values, replace the switch with select. 3633 static bool SwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, 3634 AssumptionCache *AC, const DataLayout &DL) { 3635 Value *const Cond = SI->getCondition(); 3636 PHINode *PHI = nullptr; 3637 BasicBlock *CommonDest = nullptr; 3638 Constant *DefaultResult; 3639 SwitchCaseResultVectorTy UniqueResults; 3640 // Collect all the cases that will deliver the same value from the switch. 3641 if (!InitializeUniqueCases(SI, PHI, CommonDest, UniqueResults, DefaultResult, 3642 DL)) 3643 return false; 3644 // Selects choose between maximum two values. 3645 if (UniqueResults.size() != 2) 3646 return false; 3647 assert(PHI != nullptr && "PHI for value select not found"); 3648 3649 Builder.SetInsertPoint(SI); 3650 Value *SelectValue = ConvertTwoCaseSwitch( 3651 UniqueResults, 3652 DefaultResult, Cond, Builder); 3653 if (SelectValue) { 3654 RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, Builder); 3655 return true; 3656 } 3657 // The switch couldn't be converted into a select. 3658 return false; 3659 } 3660 3661 namespace { 3662 /// SwitchLookupTable - This class represents a lookup table that can be used 3663 /// to replace a switch. 3664 class SwitchLookupTable { 3665 public: 3666 /// SwitchLookupTable - Create a lookup table to use as a switch replacement 3667 /// with the contents of Values, using DefaultValue to fill any holes in the 3668 /// table. 3669 SwitchLookupTable( 3670 Module &M, uint64_t TableSize, ConstantInt *Offset, 3671 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values, 3672 Constant *DefaultValue, const DataLayout &DL); 3673 3674 /// BuildLookup - Build instructions with Builder to retrieve the value at 3675 /// the position given by Index in the lookup table. 3676 Value *BuildLookup(Value *Index, IRBuilder<> &Builder); 3677 3678 /// WouldFitInRegister - Return true if a table with TableSize elements of 3679 /// type ElementType would fit in a target-legal register. 3680 static bool WouldFitInRegister(const DataLayout &DL, uint64_t TableSize, 3681 const Type *ElementType); 3682 3683 private: 3684 // Depending on the contents of the table, it can be represented in 3685 // different ways. 3686 enum { 3687 // For tables where each element contains the same value, we just have to 3688 // store that single value and return it for each lookup. 3689 SingleValueKind, 3690 3691 // For tables where there is a linear relationship between table index 3692 // and values. We calculate the result with a simple multiplication 3693 // and addition instead of a table lookup. 3694 LinearMapKind, 3695 3696 // For small tables with integer elements, we can pack them into a bitmap 3697 // that fits into a target-legal register. Values are retrieved by 3698 // shift and mask operations. 3699 BitMapKind, 3700 3701 // The table is stored as an array of values. Values are retrieved by load 3702 // instructions from the table. 3703 ArrayKind 3704 } Kind; 3705 3706 // For SingleValueKind, this is the single value. 3707 Constant *SingleValue; 3708 3709 // For BitMapKind, this is the bitmap. 3710 ConstantInt *BitMap; 3711 IntegerType *BitMapElementTy; 3712 3713 // For LinearMapKind, these are the constants used to derive the value. 3714 ConstantInt *LinearOffset; 3715 ConstantInt *LinearMultiplier; 3716 3717 // For ArrayKind, this is the array. 3718 GlobalVariable *Array; 3719 }; 3720 } 3721 3722 SwitchLookupTable::SwitchLookupTable( 3723 Module &M, uint64_t TableSize, ConstantInt *Offset, 3724 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values, 3725 Constant *DefaultValue, const DataLayout &DL) 3726 : SingleValue(nullptr), BitMap(nullptr), BitMapElementTy(nullptr), 3727 LinearOffset(nullptr), LinearMultiplier(nullptr), Array(nullptr) { 3728 assert(Values.size() && "Can't build lookup table without values!"); 3729 assert(TableSize >= Values.size() && "Can't fit values in table!"); 3730 3731 // If all values in the table are equal, this is that value. 3732 SingleValue = Values.begin()->second; 3733 3734 Type *ValueType = Values.begin()->second->getType(); 3735 3736 // Build up the table contents. 3737 SmallVector<Constant*, 64> TableContents(TableSize); 3738 for (size_t I = 0, E = Values.size(); I != E; ++I) { 3739 ConstantInt *CaseVal = Values[I].first; 3740 Constant *CaseRes = Values[I].second; 3741 assert(CaseRes->getType() == ValueType); 3742 3743 uint64_t Idx = (CaseVal->getValue() - Offset->getValue()) 3744 .getLimitedValue(); 3745 TableContents[Idx] = CaseRes; 3746 3747 if (CaseRes != SingleValue) 3748 SingleValue = nullptr; 3749 } 3750 3751 // Fill in any holes in the table with the default result. 3752 if (Values.size() < TableSize) { 3753 assert(DefaultValue && 3754 "Need a default value to fill the lookup table holes."); 3755 assert(DefaultValue->getType() == ValueType); 3756 for (uint64_t I = 0; I < TableSize; ++I) { 3757 if (!TableContents[I]) 3758 TableContents[I] = DefaultValue; 3759 } 3760 3761 if (DefaultValue != SingleValue) 3762 SingleValue = nullptr; 3763 } 3764 3765 // If each element in the table contains the same value, we only need to store 3766 // that single value. 3767 if (SingleValue) { 3768 Kind = SingleValueKind; 3769 return; 3770 } 3771 3772 // Check if we can derive the value with a linear transformation from the 3773 // table index. 3774 if (isa<IntegerType>(ValueType)) { 3775 bool LinearMappingPossible = true; 3776 APInt PrevVal; 3777 APInt DistToPrev; 3778 assert(TableSize >= 2 && "Should be a SingleValue table."); 3779 // Check if there is the same distance between two consecutive values. 3780 for (uint64_t I = 0; I < TableSize; ++I) { 3781 ConstantInt *ConstVal = dyn_cast<ConstantInt>(TableContents[I]); 3782 if (!ConstVal) { 3783 // This is an undef. We could deal with it, but undefs in lookup tables 3784 // are very seldom. It's probably not worth the additional complexity. 3785 LinearMappingPossible = false; 3786 break; 3787 } 3788 APInt Val = ConstVal->getValue(); 3789 if (I != 0) { 3790 APInt Dist = Val - PrevVal; 3791 if (I == 1) { 3792 DistToPrev = Dist; 3793 } else if (Dist != DistToPrev) { 3794 LinearMappingPossible = false; 3795 break; 3796 } 3797 } 3798 PrevVal = Val; 3799 } 3800 if (LinearMappingPossible) { 3801 LinearOffset = cast<ConstantInt>(TableContents[0]); 3802 LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev); 3803 Kind = LinearMapKind; 3804 ++NumLinearMaps; 3805 return; 3806 } 3807 } 3808 3809 // If the type is integer and the table fits in a register, build a bitmap. 3810 if (WouldFitInRegister(DL, TableSize, ValueType)) { 3811 IntegerType *IT = cast<IntegerType>(ValueType); 3812 APInt TableInt(TableSize * IT->getBitWidth(), 0); 3813 for (uint64_t I = TableSize; I > 0; --I) { 3814 TableInt <<= IT->getBitWidth(); 3815 // Insert values into the bitmap. Undef values are set to zero. 3816 if (!isa<UndefValue>(TableContents[I - 1])) { 3817 ConstantInt *Val = cast<ConstantInt>(TableContents[I - 1]); 3818 TableInt |= Val->getValue().zext(TableInt.getBitWidth()); 3819 } 3820 } 3821 BitMap = ConstantInt::get(M.getContext(), TableInt); 3822 BitMapElementTy = IT; 3823 Kind = BitMapKind; 3824 ++NumBitMaps; 3825 return; 3826 } 3827 3828 // Store the table in an array. 3829 ArrayType *ArrayTy = ArrayType::get(ValueType, TableSize); 3830 Constant *Initializer = ConstantArray::get(ArrayTy, TableContents); 3831 3832 Array = new GlobalVariable(M, ArrayTy, /*constant=*/ true, 3833 GlobalVariable::PrivateLinkage, 3834 Initializer, 3835 "switch.table"); 3836 Array->setUnnamedAddr(true); 3837 Kind = ArrayKind; 3838 } 3839 3840 Value *SwitchLookupTable::BuildLookup(Value *Index, IRBuilder<> &Builder) { 3841 switch (Kind) { 3842 case SingleValueKind: 3843 return SingleValue; 3844 case LinearMapKind: { 3845 // Derive the result value from the input value. 3846 Value *Result = Builder.CreateIntCast(Index, LinearMultiplier->getType(), 3847 false, "switch.idx.cast"); 3848 if (!LinearMultiplier->isOne()) 3849 Result = Builder.CreateMul(Result, LinearMultiplier, "switch.idx.mult"); 3850 if (!LinearOffset->isZero()) 3851 Result = Builder.CreateAdd(Result, LinearOffset, "switch.offset"); 3852 return Result; 3853 } 3854 case BitMapKind: { 3855 // Type of the bitmap (e.g. i59). 3856 IntegerType *MapTy = BitMap->getType(); 3857 3858 // Cast Index to the same type as the bitmap. 3859 // Note: The Index is <= the number of elements in the table, so 3860 // truncating it to the width of the bitmask is safe. 3861 Value *ShiftAmt = Builder.CreateZExtOrTrunc(Index, MapTy, "switch.cast"); 3862 3863 // Multiply the shift amount by the element width. 3864 ShiftAmt = Builder.CreateMul(ShiftAmt, 3865 ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()), 3866 "switch.shiftamt"); 3867 3868 // Shift down. 3869 Value *DownShifted = Builder.CreateLShr(BitMap, ShiftAmt, 3870 "switch.downshift"); 3871 // Mask off. 3872 return Builder.CreateTrunc(DownShifted, BitMapElementTy, 3873 "switch.masked"); 3874 } 3875 case ArrayKind: { 3876 // Make sure the table index will not overflow when treated as signed. 3877 IntegerType *IT = cast<IntegerType>(Index->getType()); 3878 uint64_t TableSize = Array->getInitializer()->getType() 3879 ->getArrayNumElements(); 3880 if (TableSize > (1ULL << (IT->getBitWidth() - 1))) 3881 Index = Builder.CreateZExt(Index, 3882 IntegerType::get(IT->getContext(), 3883 IT->getBitWidth() + 1), 3884 "switch.tableidx.zext"); 3885 3886 Value *GEPIndices[] = { Builder.getInt32(0), Index }; 3887 Value *GEP = Builder.CreateInBoundsGEP(Array->getValueType(), Array, 3888 GEPIndices, "switch.gep"); 3889 return Builder.CreateLoad(GEP, "switch.load"); 3890 } 3891 } 3892 llvm_unreachable("Unknown lookup table kind!"); 3893 } 3894 3895 bool SwitchLookupTable::WouldFitInRegister(const DataLayout &DL, 3896 uint64_t TableSize, 3897 const Type *ElementType) { 3898 const IntegerType *IT = dyn_cast<IntegerType>(ElementType); 3899 if (!IT) 3900 return false; 3901 // FIXME: If the type is wider than it needs to be, e.g. i8 but all values 3902 // are <= 15, we could try to narrow the type. 3903 3904 // Avoid overflow, fitsInLegalInteger uses unsigned int for the width. 3905 if (TableSize >= UINT_MAX/IT->getBitWidth()) 3906 return false; 3907 return DL.fitsInLegalInteger(TableSize * IT->getBitWidth()); 3908 } 3909 3910 /// ShouldBuildLookupTable - Determine whether a lookup table should be built 3911 /// for this switch, based on the number of cases, size of the table and the 3912 /// types of the results. 3913 static bool 3914 ShouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, 3915 const TargetTransformInfo &TTI, const DataLayout &DL, 3916 const SmallDenseMap<PHINode *, Type *> &ResultTypes) { 3917 if (SI->getNumCases() > TableSize || TableSize >= UINT64_MAX / 10) 3918 return false; // TableSize overflowed, or mul below might overflow. 3919 3920 bool AllTablesFitInRegister = true; 3921 bool HasIllegalType = false; 3922 for (const auto &I : ResultTypes) { 3923 Type *Ty = I.second; 3924 3925 // Saturate this flag to true. 3926 HasIllegalType = HasIllegalType || !TTI.isTypeLegal(Ty); 3927 3928 // Saturate this flag to false. 3929 AllTablesFitInRegister = AllTablesFitInRegister && 3930 SwitchLookupTable::WouldFitInRegister(DL, TableSize, Ty); 3931 3932 // If both flags saturate, we're done. NOTE: This *only* works with 3933 // saturating flags, and all flags have to saturate first due to the 3934 // non-deterministic behavior of iterating over a dense map. 3935 if (HasIllegalType && !AllTablesFitInRegister) 3936 break; 3937 } 3938 3939 // If each table would fit in a register, we should build it anyway. 3940 if (AllTablesFitInRegister) 3941 return true; 3942 3943 // Don't build a table that doesn't fit in-register if it has illegal types. 3944 if (HasIllegalType) 3945 return false; 3946 3947 // The table density should be at least 40%. This is the same criterion as for 3948 // jump tables, see SelectionDAGBuilder::handleJTSwitchCase. 3949 // FIXME: Find the best cut-off. 3950 return SI->getNumCases() * 10 >= TableSize * 4; 3951 } 3952 3953 /// Try to reuse the switch table index compare. Following pattern: 3954 /// \code 3955 /// if (idx < tablesize) 3956 /// r = table[idx]; // table does not contain default_value 3957 /// else 3958 /// r = default_value; 3959 /// if (r != default_value) 3960 /// ... 3961 /// \endcode 3962 /// Is optimized to: 3963 /// \code 3964 /// cond = idx < tablesize; 3965 /// if (cond) 3966 /// r = table[idx]; 3967 /// else 3968 /// r = default_value; 3969 /// if (cond) 3970 /// ... 3971 /// \endcode 3972 /// Jump threading will then eliminate the second if(cond). 3973 static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, 3974 BranchInst *RangeCheckBranch, Constant *DefaultValue, 3975 const SmallVectorImpl<std::pair<ConstantInt*, Constant*> >& Values) { 3976 3977 ICmpInst *CmpInst = dyn_cast<ICmpInst>(PhiUser); 3978 if (!CmpInst) 3979 return; 3980 3981 // We require that the compare is in the same block as the phi so that jump 3982 // threading can do its work afterwards. 3983 if (CmpInst->getParent() != PhiBlock) 3984 return; 3985 3986 Constant *CmpOp1 = dyn_cast<Constant>(CmpInst->getOperand(1)); 3987 if (!CmpOp1) 3988 return; 3989 3990 Value *RangeCmp = RangeCheckBranch->getCondition(); 3991 Constant *TrueConst = ConstantInt::getTrue(RangeCmp->getType()); 3992 Constant *FalseConst = ConstantInt::getFalse(RangeCmp->getType()); 3993 3994 // Check if the compare with the default value is constant true or false. 3995 Constant *DefaultConst = ConstantExpr::getICmp(CmpInst->getPredicate(), 3996 DefaultValue, CmpOp1, true); 3997 if (DefaultConst != TrueConst && DefaultConst != FalseConst) 3998 return; 3999 4000 // Check if the compare with the case values is distinct from the default 4001 // compare result. 4002 for (auto ValuePair : Values) { 4003 Constant *CaseConst = ConstantExpr::getICmp(CmpInst->getPredicate(), 4004 ValuePair.second, CmpOp1, true); 4005 if (!CaseConst || CaseConst == DefaultConst) 4006 return; 4007 assert((CaseConst == TrueConst || CaseConst == FalseConst) && 4008 "Expect true or false as compare result."); 4009 } 4010 4011 // Check if the branch instruction dominates the phi node. It's a simple 4012 // dominance check, but sufficient for our needs. 4013 // Although this check is invariant in the calling loops, it's better to do it 4014 // at this late stage. Practically we do it at most once for a switch. 4015 BasicBlock *BranchBlock = RangeCheckBranch->getParent(); 4016 for (auto PI = pred_begin(PhiBlock), E = pred_end(PhiBlock); PI != E; ++PI) { 4017 BasicBlock *Pred = *PI; 4018 if (Pred != BranchBlock && Pred->getUniquePredecessor() != BranchBlock) 4019 return; 4020 } 4021 4022 if (DefaultConst == FalseConst) { 4023 // The compare yields the same result. We can replace it. 4024 CmpInst->replaceAllUsesWith(RangeCmp); 4025 ++NumTableCmpReuses; 4026 } else { 4027 // The compare yields the same result, just inverted. We can replace it. 4028 Value *InvertedTableCmp = BinaryOperator::CreateXor(RangeCmp, 4029 ConstantInt::get(RangeCmp->getType(), 1), "inverted.cmp", 4030 RangeCheckBranch); 4031 CmpInst->replaceAllUsesWith(InvertedTableCmp); 4032 ++NumTableCmpReuses; 4033 } 4034 } 4035 4036 /// SwitchToLookupTable - If the switch is only used to initialize one or more 4037 /// phi nodes in a common successor block with different constant values, 4038 /// replace the switch with lookup tables. 4039 static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, 4040 const DataLayout &DL, 4041 const TargetTransformInfo &TTI) { 4042 assert(SI->getNumCases() > 1 && "Degenerate switch?"); 4043 4044 // Only build lookup table when we have a target that supports it. 4045 if (!TTI.shouldBuildLookupTables()) 4046 return false; 4047 4048 // FIXME: If the switch is too sparse for a lookup table, perhaps we could 4049 // split off a dense part and build a lookup table for that. 4050 4051 // FIXME: This creates arrays of GEPs to constant strings, which means each 4052 // GEP needs a runtime relocation in PIC code. We should just build one big 4053 // string and lookup indices into that. 4054 4055 // Ignore switches with less than three cases. Lookup tables will not make them 4056 // faster, so we don't analyze them. 4057 if (SI->getNumCases() < 3) 4058 return false; 4059 4060 // Figure out the corresponding result for each case value and phi node in the 4061 // common destination, as well as the the min and max case values. 4062 assert(SI->case_begin() != SI->case_end()); 4063 SwitchInst::CaseIt CI = SI->case_begin(); 4064 ConstantInt *MinCaseVal = CI.getCaseValue(); 4065 ConstantInt *MaxCaseVal = CI.getCaseValue(); 4066 4067 BasicBlock *CommonDest = nullptr; 4068 typedef SmallVector<std::pair<ConstantInt*, Constant*>, 4> ResultListTy; 4069 SmallDenseMap<PHINode*, ResultListTy> ResultLists; 4070 SmallDenseMap<PHINode*, Constant*> DefaultResults; 4071 SmallDenseMap<PHINode*, Type*> ResultTypes; 4072 SmallVector<PHINode*, 4> PHIs; 4073 4074 for (SwitchInst::CaseIt E = SI->case_end(); CI != E; ++CI) { 4075 ConstantInt *CaseVal = CI.getCaseValue(); 4076 if (CaseVal->getValue().slt(MinCaseVal->getValue())) 4077 MinCaseVal = CaseVal; 4078 if (CaseVal->getValue().sgt(MaxCaseVal->getValue())) 4079 MaxCaseVal = CaseVal; 4080 4081 // Resulting value at phi nodes for this case value. 4082 typedef SmallVector<std::pair<PHINode*, Constant*>, 4> ResultsTy; 4083 ResultsTy Results; 4084 if (!GetCaseResults(SI, CaseVal, CI.getCaseSuccessor(), &CommonDest, 4085 Results, DL)) 4086 return false; 4087 4088 // Append the result from this case to the list for each phi. 4089 for (const auto &I : Results) { 4090 PHINode *PHI = I.first; 4091 Constant *Value = I.second; 4092 if (!ResultLists.count(PHI)) 4093 PHIs.push_back(PHI); 4094 ResultLists[PHI].push_back(std::make_pair(CaseVal, Value)); 4095 } 4096 } 4097 4098 // Keep track of the result types. 4099 for (PHINode *PHI : PHIs) { 4100 ResultTypes[PHI] = ResultLists[PHI][0].second->getType(); 4101 } 4102 4103 uint64_t NumResults = ResultLists[PHIs[0]].size(); 4104 APInt RangeSpread = MaxCaseVal->getValue() - MinCaseVal->getValue(); 4105 uint64_t TableSize = RangeSpread.getLimitedValue() + 1; 4106 bool TableHasHoles = (NumResults < TableSize); 4107 4108 // If the table has holes, we need a constant result for the default case 4109 // or a bitmask that fits in a register. 4110 SmallVector<std::pair<PHINode*, Constant*>, 4> DefaultResultsList; 4111 bool HasDefaultResults = GetCaseResults(SI, nullptr, SI->getDefaultDest(), 4112 &CommonDest, DefaultResultsList, DL); 4113 4114 bool NeedMask = (TableHasHoles && !HasDefaultResults); 4115 if (NeedMask) { 4116 // As an extra penalty for the validity test we require more cases. 4117 if (SI->getNumCases() < 4) // FIXME: Find best threshold value (benchmark). 4118 return false; 4119 if (!DL.fitsInLegalInteger(TableSize)) 4120 return false; 4121 } 4122 4123 for (const auto &I : DefaultResultsList) { 4124 PHINode *PHI = I.first; 4125 Constant *Result = I.second; 4126 DefaultResults[PHI] = Result; 4127 } 4128 4129 if (!ShouldBuildLookupTable(SI, TableSize, TTI, DL, ResultTypes)) 4130 return false; 4131 4132 // Create the BB that does the lookups. 4133 Module &Mod = *CommonDest->getParent()->getParent(); 4134 BasicBlock *LookupBB = BasicBlock::Create(Mod.getContext(), 4135 "switch.lookup", 4136 CommonDest->getParent(), 4137 CommonDest); 4138 4139 // Compute the table index value. 4140 Builder.SetInsertPoint(SI); 4141 Value *TableIndex = Builder.CreateSub(SI->getCondition(), MinCaseVal, 4142 "switch.tableidx"); 4143 4144 // Compute the maximum table size representable by the integer type we are 4145 // switching upon. 4146 unsigned CaseSize = MinCaseVal->getType()->getPrimitiveSizeInBits(); 4147 uint64_t MaxTableSize = CaseSize > 63 ? UINT64_MAX : 1ULL << CaseSize; 4148 assert(MaxTableSize >= TableSize && 4149 "It is impossible for a switch to have more entries than the max " 4150 "representable value of its input integer type's size."); 4151 4152 // If the default destination is unreachable, or if the lookup table covers 4153 // all values of the conditional variable, branch directly to the lookup table 4154 // BB. Otherwise, check that the condition is within the case range. 4155 const bool DefaultIsReachable = 4156 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()); 4157 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize); 4158 BranchInst *RangeCheckBranch = nullptr; 4159 4160 if (!DefaultIsReachable || GeneratingCoveredLookupTable) { 4161 Builder.CreateBr(LookupBB); 4162 // We cached PHINodes in PHIs, to avoid accessing deleted PHINodes later, 4163 // do not delete PHINodes here. 4164 SI->getDefaultDest()->removePredecessor(SI->getParent(), 4165 /*DontDeleteUselessPHIs=*/true); 4166 } else { 4167 Value *Cmp = Builder.CreateICmpULT(TableIndex, ConstantInt::get( 4168 MinCaseVal->getType(), TableSize)); 4169 RangeCheckBranch = Builder.CreateCondBr(Cmp, LookupBB, SI->getDefaultDest()); 4170 } 4171 4172 // Populate the BB that does the lookups. 4173 Builder.SetInsertPoint(LookupBB); 4174 4175 if (NeedMask) { 4176 // Before doing the lookup we do the hole check. 4177 // The LookupBB is therefore re-purposed to do the hole check 4178 // and we create a new LookupBB. 4179 BasicBlock *MaskBB = LookupBB; 4180 MaskBB->setName("switch.hole_check"); 4181 LookupBB = BasicBlock::Create(Mod.getContext(), 4182 "switch.lookup", 4183 CommonDest->getParent(), 4184 CommonDest); 4185 4186 // Make the mask's bitwidth at least 8bit and a power-of-2 to avoid 4187 // unnecessary illegal types. 4188 uint64_t TableSizePowOf2 = NextPowerOf2(std::max(7ULL, TableSize - 1ULL)); 4189 APInt MaskInt(TableSizePowOf2, 0); 4190 APInt One(TableSizePowOf2, 1); 4191 // Build bitmask; fill in a 1 bit for every case. 4192 const ResultListTy &ResultList = ResultLists[PHIs[0]]; 4193 for (size_t I = 0, E = ResultList.size(); I != E; ++I) { 4194 uint64_t Idx = (ResultList[I].first->getValue() - 4195 MinCaseVal->getValue()).getLimitedValue(); 4196 MaskInt |= One << Idx; 4197 } 4198 ConstantInt *TableMask = ConstantInt::get(Mod.getContext(), MaskInt); 4199 4200 // Get the TableIndex'th bit of the bitmask. 4201 // If this bit is 0 (meaning hole) jump to the default destination, 4202 // else continue with table lookup. 4203 IntegerType *MapTy = TableMask->getType(); 4204 Value *MaskIndex = Builder.CreateZExtOrTrunc(TableIndex, MapTy, 4205 "switch.maskindex"); 4206 Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex, 4207 "switch.shifted"); 4208 Value *LoBit = Builder.CreateTrunc(Shifted, 4209 Type::getInt1Ty(Mod.getContext()), 4210 "switch.lobit"); 4211 Builder.CreateCondBr(LoBit, LookupBB, SI->getDefaultDest()); 4212 4213 Builder.SetInsertPoint(LookupBB); 4214 AddPredecessorToBlock(SI->getDefaultDest(), MaskBB, SI->getParent()); 4215 } 4216 4217 bool ReturnedEarly = false; 4218 for (size_t I = 0, E = PHIs.size(); I != E; ++I) { 4219 PHINode *PHI = PHIs[I]; 4220 const ResultListTy &ResultList = ResultLists[PHI]; 4221 4222 // If using a bitmask, use any value to fill the lookup table holes. 4223 Constant *DV = NeedMask ? ResultLists[PHI][0].second : DefaultResults[PHI]; 4224 SwitchLookupTable Table(Mod, TableSize, MinCaseVal, ResultList, DV, DL); 4225 4226 Value *Result = Table.BuildLookup(TableIndex, Builder); 4227 4228 // If the result is used to return immediately from the function, we want to 4229 // do that right here. 4230 if (PHI->hasOneUse() && isa<ReturnInst>(*PHI->user_begin()) && 4231 PHI->user_back() == CommonDest->getFirstNonPHIOrDbg()) { 4232 Builder.CreateRet(Result); 4233 ReturnedEarly = true; 4234 break; 4235 } 4236 4237 // Do a small peephole optimization: re-use the switch table compare if 4238 // possible. 4239 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) { 4240 BasicBlock *PhiBlock = PHI->getParent(); 4241 // Search for compare instructions which use the phi. 4242 for (auto *User : PHI->users()) { 4243 reuseTableCompare(User, PhiBlock, RangeCheckBranch, DV, ResultList); 4244 } 4245 } 4246 4247 PHI->addIncoming(Result, LookupBB); 4248 } 4249 4250 if (!ReturnedEarly) 4251 Builder.CreateBr(CommonDest); 4252 4253 // Remove the switch. 4254 for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) { 4255 BasicBlock *Succ = SI->getSuccessor(i); 4256 4257 if (Succ == SI->getDefaultDest()) 4258 continue; 4259 Succ->removePredecessor(SI->getParent()); 4260 } 4261 SI->eraseFromParent(); 4262 4263 ++NumLookupTables; 4264 if (NeedMask) 4265 ++NumLookupTablesHoles; 4266 return true; 4267 } 4268 4269 bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) { 4270 BasicBlock *BB = SI->getParent(); 4271 4272 if (isValueEqualityComparison(SI)) { 4273 // If we only have one predecessor, and if it is a branch on this value, 4274 // see if that predecessor totally determines the outcome of this switch. 4275 if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 4276 if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder)) 4277 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 4278 4279 Value *Cond = SI->getCondition(); 4280 if (SelectInst *Select = dyn_cast<SelectInst>(Cond)) 4281 if (SimplifySwitchOnSelect(SI, Select)) 4282 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 4283 4284 // If the block only contains the switch, see if we can fold the block 4285 // away into any preds. 4286 BasicBlock::iterator BBI = BB->begin(); 4287 // Ignore dbg intrinsics. 4288 while (isa<DbgInfoIntrinsic>(BBI)) 4289 ++BBI; 4290 if (SI == &*BBI) 4291 if (FoldValueComparisonIntoPredecessors(SI, Builder)) 4292 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 4293 } 4294 4295 // Try to transform the switch into an icmp and a branch. 4296 if (TurnSwitchRangeIntoICmp(SI, Builder)) 4297 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 4298 4299 // Remove unreachable cases. 4300 if (EliminateDeadSwitchCases(SI, AC, DL)) 4301 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 4302 4303 if (SwitchToSelect(SI, Builder, AC, DL)) 4304 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 4305 4306 if (ForwardSwitchConditionToPHI(SI)) 4307 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 4308 4309 if (SwitchToLookupTable(SI, Builder, DL, TTI)) 4310 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 4311 4312 return false; 4313 } 4314 4315 bool SimplifyCFGOpt::SimplifyIndirectBr(IndirectBrInst *IBI) { 4316 BasicBlock *BB = IBI->getParent(); 4317 bool Changed = false; 4318 4319 // Eliminate redundant destinations. 4320 SmallPtrSet<Value *, 8> Succs; 4321 for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { 4322 BasicBlock *Dest = IBI->getDestination(i); 4323 if (!Dest->hasAddressTaken() || !Succs.insert(Dest).second) { 4324 Dest->removePredecessor(BB); 4325 IBI->removeDestination(i); 4326 --i; --e; 4327 Changed = true; 4328 } 4329 } 4330 4331 if (IBI->getNumDestinations() == 0) { 4332 // If the indirectbr has no successors, change it to unreachable. 4333 new UnreachableInst(IBI->getContext(), IBI); 4334 EraseTerminatorInstAndDCECond(IBI); 4335 return true; 4336 } 4337 4338 if (IBI->getNumDestinations() == 1) { 4339 // If the indirectbr has one successor, change it to a direct branch. 4340 BranchInst::Create(IBI->getDestination(0), IBI); 4341 EraseTerminatorInstAndDCECond(IBI); 4342 return true; 4343 } 4344 4345 if (SelectInst *SI = dyn_cast<SelectInst>(IBI->getAddress())) { 4346 if (SimplifyIndirectBrOnSelect(IBI, SI)) 4347 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 4348 } 4349 return Changed; 4350 } 4351 4352 /// Given an block with only a single landing pad and a unconditional branch 4353 /// try to find another basic block which this one can be merged with. This 4354 /// handles cases where we have multiple invokes with unique landing pads, but 4355 /// a shared handler. 4356 /// 4357 /// We specifically choose to not worry about merging non-empty blocks 4358 /// here. That is a PRE/scheduling problem and is best solved elsewhere. In 4359 /// practice, the optimizer produces empty landing pad blocks quite frequently 4360 /// when dealing with exception dense code. (see: instcombine, gvn, if-else 4361 /// sinking in this file) 4362 /// 4363 /// This is primarily a code size optimization. We need to avoid performing 4364 /// any transform which might inhibit optimization (such as our ability to 4365 /// specialize a particular handler via tail commoning). We do this by not 4366 /// merging any blocks which require us to introduce a phi. Since the same 4367 /// values are flowing through both blocks, we don't loose any ability to 4368 /// specialize. If anything, we make such specialization more likely. 4369 /// 4370 /// TODO - This transformation could remove entries from a phi in the target 4371 /// block when the inputs in the phi are the same for the two blocks being 4372 /// merged. In some cases, this could result in removal of the PHI entirely. 4373 static bool TryToMergeLandingPad(LandingPadInst *LPad, BranchInst *BI, 4374 BasicBlock *BB) { 4375 auto Succ = BB->getUniqueSuccessor(); 4376 assert(Succ); 4377 // If there's a phi in the successor block, we'd likely have to introduce 4378 // a phi into the merged landing pad block. 4379 if (isa<PHINode>(*Succ->begin())) 4380 return false; 4381 4382 for (BasicBlock *OtherPred : predecessors(Succ)) { 4383 if (BB == OtherPred) 4384 continue; 4385 BasicBlock::iterator I = OtherPred->begin(); 4386 LandingPadInst *LPad2 = dyn_cast<LandingPadInst>(I); 4387 if (!LPad2 || !LPad2->isIdenticalTo(LPad)) 4388 continue; 4389 for (++I; isa<DbgInfoIntrinsic>(I); ++I) {} 4390 BranchInst *BI2 = dyn_cast<BranchInst>(I); 4391 if (!BI2 || !BI2->isIdenticalTo(BI)) 4392 continue; 4393 4394 // We've found an identical block. Update our predeccessors to take that 4395 // path instead and make ourselves dead. 4396 SmallSet<BasicBlock *, 16> Preds; 4397 Preds.insert(pred_begin(BB), pred_end(BB)); 4398 for (BasicBlock *Pred : Preds) { 4399 InvokeInst *II = cast<InvokeInst>(Pred->getTerminator()); 4400 assert(II->getNormalDest() != BB && 4401 II->getUnwindDest() == BB && "unexpected successor"); 4402 II->setUnwindDest(OtherPred); 4403 } 4404 4405 // The debug info in OtherPred doesn't cover the merged control flow that 4406 // used to go through BB. We need to delete it or update it. 4407 for (auto I = OtherPred->begin(), E = OtherPred->end(); 4408 I != E;) { 4409 Instruction &Inst = *I; I++; 4410 if (isa<DbgInfoIntrinsic>(Inst)) 4411 Inst.eraseFromParent(); 4412 } 4413 4414 SmallSet<BasicBlock *, 16> Succs; 4415 Succs.insert(succ_begin(BB), succ_end(BB)); 4416 for (BasicBlock *Succ : Succs) { 4417 Succ->removePredecessor(BB); 4418 } 4419 4420 IRBuilder<> Builder(BI); 4421 Builder.CreateUnreachable(); 4422 BI->eraseFromParent(); 4423 return true; 4424 } 4425 return false; 4426 } 4427 4428 bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder){ 4429 BasicBlock *BB = BI->getParent(); 4430 4431 if (SinkCommon && SinkThenElseCodeToEnd(BI)) 4432 return true; 4433 4434 // If the Terminator is the only non-phi instruction, simplify the block. 4435 BasicBlock::iterator I = BB->getFirstNonPHIOrDbg(); 4436 if (I->isTerminator() && BB != &BB->getParent()->getEntryBlock() && 4437 TryToSimplifyUncondBranchFromEmptyBlock(BB)) 4438 return true; 4439 4440 // If the only instruction in the block is a seteq/setne comparison 4441 // against a constant, try to simplify the block. 4442 if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) 4443 if (ICI->isEquality() && isa<ConstantInt>(ICI->getOperand(1))) { 4444 for (++I; isa<DbgInfoIntrinsic>(I); ++I) 4445 ; 4446 if (I->isTerminator() && 4447 TryToSimplifyUncondBranchWithICmpInIt(ICI, Builder, DL, TTI, 4448 BonusInstThreshold, AC)) 4449 return true; 4450 } 4451 4452 // See if we can merge an empty landing pad block with another which is 4453 // equivalent. 4454 if (LandingPadInst *LPad = dyn_cast<LandingPadInst>(I)) { 4455 for (++I; isa<DbgInfoIntrinsic>(I); ++I) {} 4456 if (I->isTerminator() && 4457 TryToMergeLandingPad(LPad, BI, BB)) 4458 return true; 4459 } 4460 4461 // If this basic block is ONLY a compare and a branch, and if a predecessor 4462 // branches to us and our successor, fold the comparison into the 4463 // predecessor and use logical operations to update the incoming value 4464 // for PHI nodes in common successor. 4465 if (FoldBranchToCommonDest(BI, BonusInstThreshold)) 4466 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 4467 return false; 4468 } 4469 4470 4471 bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) { 4472 BasicBlock *BB = BI->getParent(); 4473 4474 // Conditional branch 4475 if (isValueEqualityComparison(BI)) { 4476 // If we only have one predecessor, and if it is a branch on this value, 4477 // see if that predecessor totally determines the outcome of this 4478 // switch. 4479 if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 4480 if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder)) 4481 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 4482 4483 // This block must be empty, except for the setcond inst, if it exists. 4484 // Ignore dbg intrinsics. 4485 BasicBlock::iterator I = BB->begin(); 4486 // Ignore dbg intrinsics. 4487 while (isa<DbgInfoIntrinsic>(I)) 4488 ++I; 4489 if (&*I == BI) { 4490 if (FoldValueComparisonIntoPredecessors(BI, Builder)) 4491 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 4492 } else if (&*I == cast<Instruction>(BI->getCondition())){ 4493 ++I; 4494 // Ignore dbg intrinsics. 4495 while (isa<DbgInfoIntrinsic>(I)) 4496 ++I; 4497 if (&*I == BI && FoldValueComparisonIntoPredecessors(BI, Builder)) 4498 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 4499 } 4500 } 4501 4502 // Try to turn "br (X == 0 | X == 1), T, F" into a switch instruction. 4503 if (SimplifyBranchOnICmpChain(BI, Builder, DL)) 4504 return true; 4505 4506 // If this basic block is ONLY a compare and a branch, and if a predecessor 4507 // branches to us and one of our successors, fold the comparison into the 4508 // predecessor and use logical operations to pick the right destination. 4509 if (FoldBranchToCommonDest(BI, BonusInstThreshold)) 4510 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 4511 4512 // We have a conditional branch to two blocks that are only reachable 4513 // from BI. We know that the condbr dominates the two blocks, so see if 4514 // there is any identical code in the "then" and "else" blocks. If so, we 4515 // can hoist it up to the branching block. 4516 if (BI->getSuccessor(0)->getSinglePredecessor()) { 4517 if (BI->getSuccessor(1)->getSinglePredecessor()) { 4518 if (HoistThenElseCodeToIf(BI, TTI)) 4519 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 4520 } else { 4521 // If Successor #1 has multiple preds, we may be able to conditionally 4522 // execute Successor #0 if it branches to Successor #1. 4523 TerminatorInst *Succ0TI = BI->getSuccessor(0)->getTerminator(); 4524 if (Succ0TI->getNumSuccessors() == 1 && 4525 Succ0TI->getSuccessor(0) == BI->getSuccessor(1)) 4526 if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0), TTI)) 4527 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 4528 } 4529 } else if (BI->getSuccessor(1)->getSinglePredecessor()) { 4530 // If Successor #0 has multiple preds, we may be able to conditionally 4531 // execute Successor #1 if it branches to Successor #0. 4532 TerminatorInst *Succ1TI = BI->getSuccessor(1)->getTerminator(); 4533 if (Succ1TI->getNumSuccessors() == 1 && 4534 Succ1TI->getSuccessor(0) == BI->getSuccessor(0)) 4535 if (SpeculativelyExecuteBB(BI, BI->getSuccessor(1), TTI)) 4536 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 4537 } 4538 4539 // If this is a branch on a phi node in the current block, thread control 4540 // through this block if any PHI node entries are constants. 4541 if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition())) 4542 if (PN->getParent() == BI->getParent()) 4543 if (FoldCondBranchOnPHI(BI, DL)) 4544 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 4545 4546 // Scan predecessor blocks for conditional branches. 4547 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 4548 if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 4549 if (PBI != BI && PBI->isConditional()) 4550 if (SimplifyCondBranchToCondBranch(PBI, BI)) 4551 return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; 4552 4553 return false; 4554 } 4555 4556 /// Check if passing a value to an instruction will cause undefined behavior. 4557 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I) { 4558 Constant *C = dyn_cast<Constant>(V); 4559 if (!C) 4560 return false; 4561 4562 if (I->use_empty()) 4563 return false; 4564 4565 if (C->isNullValue()) { 4566 // Only look at the first use, avoid hurting compile time with long uselists 4567 User *Use = *I->user_begin(); 4568 4569 // Now make sure that there are no instructions in between that can alter 4570 // control flow (eg. calls) 4571 for (BasicBlock::iterator i = ++BasicBlock::iterator(I); &*i != Use; ++i) 4572 if (i == I->getParent()->end() || i->mayHaveSideEffects()) 4573 return false; 4574 4575 // Look through GEPs. A load from a GEP derived from NULL is still undefined 4576 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Use)) 4577 if (GEP->getPointerOperand() == I) 4578 return passingValueIsAlwaysUndefined(V, GEP); 4579 4580 // Look through bitcasts. 4581 if (BitCastInst *BC = dyn_cast<BitCastInst>(Use)) 4582 return passingValueIsAlwaysUndefined(V, BC); 4583 4584 // Load from null is undefined. 4585 if (LoadInst *LI = dyn_cast<LoadInst>(Use)) 4586 if (!LI->isVolatile()) 4587 return LI->getPointerAddressSpace() == 0; 4588 4589 // Store to null is undefined. 4590 if (StoreInst *SI = dyn_cast<StoreInst>(Use)) 4591 if (!SI->isVolatile()) 4592 return SI->getPointerAddressSpace() == 0 && SI->getPointerOperand() == I; 4593 } 4594 return false; 4595 } 4596 4597 /// If BB has an incoming value that will always trigger undefined behavior 4598 /// (eg. null pointer dereference), remove the branch leading here. 4599 static bool removeUndefIntroducingPredecessor(BasicBlock *BB) { 4600 for (BasicBlock::iterator i = BB->begin(); 4601 PHINode *PHI = dyn_cast<PHINode>(i); ++i) 4602 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) 4603 if (passingValueIsAlwaysUndefined(PHI->getIncomingValue(i), PHI)) { 4604 TerminatorInst *T = PHI->getIncomingBlock(i)->getTerminator(); 4605 IRBuilder<> Builder(T); 4606 if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 4607 BB->removePredecessor(PHI->getIncomingBlock(i)); 4608 // Turn uncoditional branches into unreachables and remove the dead 4609 // destination from conditional branches. 4610 if (BI->isUnconditional()) 4611 Builder.CreateUnreachable(); 4612 else 4613 Builder.CreateBr(BI->getSuccessor(0) == BB ? BI->getSuccessor(1) : 4614 BI->getSuccessor(0)); 4615 BI->eraseFromParent(); 4616 return true; 4617 } 4618 // TODO: SwitchInst. 4619 } 4620 4621 return false; 4622 } 4623 4624 bool SimplifyCFGOpt::run(BasicBlock *BB) { 4625 bool Changed = false; 4626 4627 assert(BB && BB->getParent() && "Block not embedded in function!"); 4628 assert(BB->getTerminator() && "Degenerate basic block encountered!"); 4629 4630 // Remove basic blocks that have no predecessors (except the entry block)... 4631 // or that just have themself as a predecessor. These are unreachable. 4632 if ((pred_empty(BB) && 4633 BB != &BB->getParent()->getEntryBlock()) || 4634 BB->getSinglePredecessor() == BB) { 4635 DEBUG(dbgs() << "Removing BB: \n" << *BB); 4636 DeleteDeadBlock(BB); 4637 return true; 4638 } 4639 4640 // Check to see if we can constant propagate this terminator instruction 4641 // away... 4642 Changed |= ConstantFoldTerminator(BB, true); 4643 4644 // Check for and eliminate duplicate PHI nodes in this block. 4645 Changed |= EliminateDuplicatePHINodes(BB); 4646 4647 // Check for and remove branches that will always cause undefined behavior. 4648 Changed |= removeUndefIntroducingPredecessor(BB); 4649 4650 // Merge basic blocks into their predecessor if there is only one distinct 4651 // pred, and if there is only one distinct successor of the predecessor, and 4652 // if there are no PHI nodes. 4653 // 4654 if (MergeBlockIntoPredecessor(BB)) 4655 return true; 4656 4657 IRBuilder<> Builder(BB); 4658 4659 // If there is a trivial two-entry PHI node in this basic block, and we can 4660 // eliminate it, do so now. 4661 if (PHINode *PN = dyn_cast<PHINode>(BB->begin())) 4662 if (PN->getNumIncomingValues() == 2) 4663 Changed |= FoldTwoEntryPHINode(PN, TTI, DL); 4664 4665 Builder.SetInsertPoint(BB->getTerminator()); 4666 if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 4667 if (BI->isUnconditional()) { 4668 if (SimplifyUncondBranch(BI, Builder)) return true; 4669 } else { 4670 if (SimplifyCondBranch(BI, Builder)) return true; 4671 } 4672 } else if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 4673 if (SimplifyReturn(RI, Builder)) return true; 4674 } else if (ResumeInst *RI = dyn_cast<ResumeInst>(BB->getTerminator())) { 4675 if (SimplifyResume(RI, Builder)) return true; 4676 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { 4677 if (SimplifySwitch(SI, Builder)) return true; 4678 } else if (UnreachableInst *UI = 4679 dyn_cast<UnreachableInst>(BB->getTerminator())) { 4680 if (SimplifyUnreachable(UI)) return true; 4681 } else if (IndirectBrInst *IBI = 4682 dyn_cast<IndirectBrInst>(BB->getTerminator())) { 4683 if (SimplifyIndirectBr(IBI)) return true; 4684 } 4685 4686 return Changed; 4687 } 4688 4689 /// SimplifyCFG - This function is used to do simplification of a CFG. For 4690 /// example, it adjusts branches to branches to eliminate the extra hop, it 4691 /// eliminates unreachable basic blocks, and does other "peephole" optimization 4692 /// of the CFG. It returns true if a modification was made. 4693 /// 4694 bool llvm::SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, 4695 unsigned BonusInstThreshold, AssumptionCache *AC) { 4696 return SimplifyCFGOpt(TTI, BB->getModule()->getDataLayout(), 4697 BonusInstThreshold, AC).run(BB); 4698 } 4699