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/ADT/APInt.h" 15 #include "llvm/ADT/ArrayRef.h" 16 #include "llvm/ADT/DenseMap.h" 17 #include "llvm/ADT/Optional.h" 18 #include "llvm/ADT/STLExtras.h" 19 #include "llvm/ADT/SetOperations.h" 20 #include "llvm/ADT/SetVector.h" 21 #include "llvm/ADT/SmallPtrSet.h" 22 #include "llvm/ADT/SmallVector.h" 23 #include "llvm/ADT/Statistic.h" 24 #include "llvm/ADT/StringRef.h" 25 #include "llvm/Analysis/AssumptionCache.h" 26 #include "llvm/Analysis/ConstantFolding.h" 27 #include "llvm/Analysis/EHPersonalities.h" 28 #include "llvm/Analysis/InstructionSimplify.h" 29 #include "llvm/Analysis/TargetTransformInfo.h" 30 #include "llvm/Transforms/Utils/Local.h" 31 #include "llvm/Analysis/ValueTracking.h" 32 #include "llvm/IR/Attributes.h" 33 #include "llvm/IR/BasicBlock.h" 34 #include "llvm/IR/CFG.h" 35 #include "llvm/IR/CallSite.h" 36 #include "llvm/IR/Constant.h" 37 #include "llvm/IR/ConstantRange.h" 38 #include "llvm/IR/Constants.h" 39 #include "llvm/IR/DataLayout.h" 40 #include "llvm/IR/DerivedTypes.h" 41 #include "llvm/IR/Function.h" 42 #include "llvm/IR/GlobalValue.h" 43 #include "llvm/IR/GlobalVariable.h" 44 #include "llvm/IR/IRBuilder.h" 45 #include "llvm/IR/InstrTypes.h" 46 #include "llvm/IR/Instruction.h" 47 #include "llvm/IR/Instructions.h" 48 #include "llvm/IR/IntrinsicInst.h" 49 #include "llvm/IR/Intrinsics.h" 50 #include "llvm/IR/LLVMContext.h" 51 #include "llvm/IR/MDBuilder.h" 52 #include "llvm/IR/Metadata.h" 53 #include "llvm/IR/Module.h" 54 #include "llvm/IR/NoFolder.h" 55 #include "llvm/IR/Operator.h" 56 #include "llvm/IR/PatternMatch.h" 57 #include "llvm/IR/Type.h" 58 #include "llvm/IR/Use.h" 59 #include "llvm/IR/User.h" 60 #include "llvm/IR/Value.h" 61 #include "llvm/Support/Casting.h" 62 #include "llvm/Support/CommandLine.h" 63 #include "llvm/Support/Debug.h" 64 #include "llvm/Support/ErrorHandling.h" 65 #include "llvm/Support/KnownBits.h" 66 #include "llvm/Support/MathExtras.h" 67 #include "llvm/Support/raw_ostream.h" 68 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 69 #include "llvm/Transforms/Utils/ValueMapper.h" 70 #include <algorithm> 71 #include <cassert> 72 #include <climits> 73 #include <cstddef> 74 #include <cstdint> 75 #include <iterator> 76 #include <map> 77 #include <set> 78 #include <tuple> 79 #include <utility> 80 #include <vector> 81 82 using namespace llvm; 83 using namespace PatternMatch; 84 85 #define DEBUG_TYPE "simplifycfg" 86 87 // Chosen as 2 so as to be cheap, but still to have enough power to fold 88 // a select, so the "clamp" idiom (of a min followed by a max) will be caught. 89 // To catch this, we need to fold a compare and a select, hence '2' being the 90 // minimum reasonable default. 91 static cl::opt<unsigned> PHINodeFoldingThreshold( 92 "phi-node-folding-threshold", cl::Hidden, cl::init(2), 93 cl::desc( 94 "Control the amount of phi node folding to perform (default = 2)")); 95 96 static cl::opt<bool> DupRet( 97 "simplifycfg-dup-ret", cl::Hidden, cl::init(false), 98 cl::desc("Duplicate return instructions into unconditional branches")); 99 100 static cl::opt<bool> 101 SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), 102 cl::desc("Sink common instructions down to the end block")); 103 104 static cl::opt<bool> HoistCondStores( 105 "simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), 106 cl::desc("Hoist conditional stores if an unconditional store precedes")); 107 108 static cl::opt<bool> MergeCondStores( 109 "simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true), 110 cl::desc("Hoist conditional stores even if an unconditional store does not " 111 "precede - hoist multiple conditional stores into a single " 112 "predicated store")); 113 114 static cl::opt<bool> MergeCondStoresAggressively( 115 "simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false), 116 cl::desc("When merging conditional stores, do so even if the resultant " 117 "basic blocks are unlikely to be if-converted as a result")); 118 119 static cl::opt<bool> SpeculateOneExpensiveInst( 120 "speculate-one-expensive-inst", cl::Hidden, cl::init(true), 121 cl::desc("Allow exactly one expensive instruction to be speculatively " 122 "executed")); 123 124 static cl::opt<unsigned> MaxSpeculationDepth( 125 "max-speculation-depth", cl::Hidden, cl::init(10), 126 cl::desc("Limit maximum recursion depth when calculating costs of " 127 "speculatively executed instructions")); 128 129 STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps"); 130 STATISTIC(NumLinearMaps, 131 "Number of switch instructions turned into linear mapping"); 132 STATISTIC(NumLookupTables, 133 "Number of switch instructions turned into lookup tables"); 134 STATISTIC( 135 NumLookupTablesHoles, 136 "Number of switch instructions turned into lookup tables (holes checked)"); 137 STATISTIC(NumTableCmpReuses, "Number of reused switch table lookup compares"); 138 STATISTIC(NumSinkCommons, 139 "Number of common instructions sunk down to the end block"); 140 STATISTIC(NumSpeculations, "Number of speculative executed instructions"); 141 142 namespace { 143 144 // The first field contains the value that the switch produces when a certain 145 // case group is selected, and the second field is a vector containing the 146 // cases composing the case group. 147 using SwitchCaseResultVectorTy = 148 SmallVector<std::pair<Constant *, SmallVector<ConstantInt *, 4>>, 2>; 149 150 // The first field contains the phi node that generates a result of the switch 151 // and the second field contains the value generated for a certain case in the 152 // switch for that PHI. 153 using SwitchCaseResultsTy = SmallVector<std::pair<PHINode *, Constant *>, 4>; 154 155 /// ValueEqualityComparisonCase - Represents a case of a switch. 156 struct ValueEqualityComparisonCase { 157 ConstantInt *Value; 158 BasicBlock *Dest; 159 160 ValueEqualityComparisonCase(ConstantInt *Value, BasicBlock *Dest) 161 : Value(Value), Dest(Dest) {} 162 163 bool operator<(ValueEqualityComparisonCase RHS) const { 164 // Comparing pointers is ok as we only rely on the order for uniquing. 165 return Value < RHS.Value; 166 } 167 168 bool operator==(BasicBlock *RHSDest) const { return Dest == RHSDest; } 169 }; 170 171 class SimplifyCFGOpt { 172 const TargetTransformInfo &TTI; 173 const DataLayout &DL; 174 SmallPtrSetImpl<BasicBlock *> *LoopHeaders; 175 const SimplifyCFGOptions &Options; 176 177 Value *isValueEqualityComparison(TerminatorInst *TI); 178 BasicBlock *GetValueEqualityComparisonCases( 179 TerminatorInst *TI, std::vector<ValueEqualityComparisonCase> &Cases); 180 bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, 181 BasicBlock *Pred, 182 IRBuilder<> &Builder); 183 bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI, 184 IRBuilder<> &Builder); 185 186 bool SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder); 187 bool SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder); 188 bool SimplifySingleResume(ResumeInst *RI); 189 bool SimplifyCommonResume(ResumeInst *RI); 190 bool SimplifyCleanupReturn(CleanupReturnInst *RI); 191 bool SimplifyUnreachable(UnreachableInst *UI); 192 bool SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder); 193 bool SimplifyIndirectBr(IndirectBrInst *IBI); 194 bool SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder); 195 bool SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder); 196 197 public: 198 SimplifyCFGOpt(const TargetTransformInfo &TTI, const DataLayout &DL, 199 SmallPtrSetImpl<BasicBlock *> *LoopHeaders, 200 const SimplifyCFGOptions &Opts) 201 : TTI(TTI), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {} 202 203 bool run(BasicBlock *BB); 204 }; 205 206 } // end anonymous namespace 207 208 /// Return true if it is safe to merge these two 209 /// terminator instructions together. 210 static bool 211 SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2, 212 SmallSetVector<BasicBlock *, 4> *FailBlocks = nullptr) { 213 if (SI1 == SI2) 214 return false; // Can't merge with self! 215 216 // It is not safe to merge these two switch instructions if they have a common 217 // successor, and if that successor has a PHI node, and if *that* PHI node has 218 // conflicting incoming values from the two switch blocks. 219 BasicBlock *SI1BB = SI1->getParent(); 220 BasicBlock *SI2BB = SI2->getParent(); 221 222 SmallPtrSet<BasicBlock *, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 223 bool Fail = false; 224 for (BasicBlock *Succ : successors(SI2BB)) 225 if (SI1Succs.count(Succ)) 226 for (BasicBlock::iterator BBI = Succ->begin(); isa<PHINode>(BBI); ++BBI) { 227 PHINode *PN = cast<PHINode>(BBI); 228 if (PN->getIncomingValueForBlock(SI1BB) != 229 PN->getIncomingValueForBlock(SI2BB)) { 230 if (FailBlocks) 231 FailBlocks->insert(Succ); 232 Fail = true; 233 } 234 } 235 236 return !Fail; 237 } 238 239 /// Return true if it is safe and profitable to merge these two terminator 240 /// instructions together, where SI1 is an unconditional branch. PhiNodes will 241 /// store all PHI nodes in common successors. 242 static bool 243 isProfitableToFoldUnconditional(BranchInst *SI1, BranchInst *SI2, 244 Instruction *Cond, 245 SmallVectorImpl<PHINode *> &PhiNodes) { 246 if (SI1 == SI2) 247 return false; // Can't merge with self! 248 assert(SI1->isUnconditional() && SI2->isConditional()); 249 250 // We fold the unconditional branch if we can easily update all PHI nodes in 251 // common successors: 252 // 1> We have a constant incoming value for the conditional branch; 253 // 2> We have "Cond" as the incoming value for the unconditional branch; 254 // 3> SI2->getCondition() and Cond have same operands. 255 CmpInst *Ci2 = dyn_cast<CmpInst>(SI2->getCondition()); 256 if (!Ci2) 257 return false; 258 if (!(Cond->getOperand(0) == Ci2->getOperand(0) && 259 Cond->getOperand(1) == Ci2->getOperand(1)) && 260 !(Cond->getOperand(0) == Ci2->getOperand(1) && 261 Cond->getOperand(1) == Ci2->getOperand(0))) 262 return false; 263 264 BasicBlock *SI1BB = SI1->getParent(); 265 BasicBlock *SI2BB = SI2->getParent(); 266 SmallPtrSet<BasicBlock *, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 267 for (BasicBlock *Succ : successors(SI2BB)) 268 if (SI1Succs.count(Succ)) 269 for (BasicBlock::iterator BBI = Succ->begin(); isa<PHINode>(BBI); ++BBI) { 270 PHINode *PN = cast<PHINode>(BBI); 271 if (PN->getIncomingValueForBlock(SI1BB) != Cond || 272 !isa<ConstantInt>(PN->getIncomingValueForBlock(SI2BB))) 273 return false; 274 PhiNodes.push_back(PN); 275 } 276 return true; 277 } 278 279 /// Update PHI nodes in Succ to indicate that there will now be entries in it 280 /// from the 'NewPred' block. The values that will be flowing into the PHI nodes 281 /// will be the same as those coming in from ExistPred, an existing predecessor 282 /// of Succ. 283 static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, 284 BasicBlock *ExistPred) { 285 for (PHINode &PN : Succ->phis()) 286 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred); 287 } 288 289 /// Compute an abstract "cost" of speculating the given instruction, 290 /// which is assumed to be safe to speculate. TCC_Free means cheap, 291 /// TCC_Basic means less cheap, and TCC_Expensive means prohibitively 292 /// expensive. 293 static unsigned ComputeSpeculationCost(const User *I, 294 const TargetTransformInfo &TTI) { 295 assert(isSafeToSpeculativelyExecute(I) && 296 "Instruction is not safe to speculatively execute!"); 297 return TTI.getUserCost(I); 298 } 299 300 /// If we have a merge point of an "if condition" as accepted above, 301 /// return true if the specified value dominates the block. We 302 /// don't handle the true generality of domination here, just a special case 303 /// which works well enough for us. 304 /// 305 /// If AggressiveInsts is non-null, and if V does not dominate BB, we check to 306 /// see if V (which must be an instruction) and its recursive operands 307 /// that do not dominate BB have a combined cost lower than CostRemaining and 308 /// are non-trapping. If both are true, the instruction is inserted into the 309 /// set and true is returned. 310 /// 311 /// The cost for most non-trapping instructions is defined as 1 except for 312 /// Select whose cost is 2. 313 /// 314 /// After this function returns, CostRemaining is decreased by the cost of 315 /// V plus its non-dominating operands. If that cost is greater than 316 /// CostRemaining, false is returned and CostRemaining is undefined. 317 static bool DominatesMergePoint(Value *V, BasicBlock *BB, 318 SmallPtrSetImpl<Instruction *> *AggressiveInsts, 319 unsigned &CostRemaining, 320 const TargetTransformInfo &TTI, 321 unsigned Depth = 0) { 322 // It is possible to hit a zero-cost cycle (phi/gep instructions for example), 323 // so limit the recursion depth. 324 // TODO: While this recursion limit does prevent pathological behavior, it 325 // would be better to track visited instructions to avoid cycles. 326 if (Depth == MaxSpeculationDepth) 327 return false; 328 329 Instruction *I = dyn_cast<Instruction>(V); 330 if (!I) { 331 // Non-instructions all dominate instructions, but not all constantexprs 332 // can be executed unconditionally. 333 if (ConstantExpr *C = dyn_cast<ConstantExpr>(V)) 334 if (C->canTrap()) 335 return false; 336 return true; 337 } 338 BasicBlock *PBB = I->getParent(); 339 340 // We don't want to allow weird loops that might have the "if condition" in 341 // the bottom of this block. 342 if (PBB == BB) 343 return false; 344 345 // If this instruction is defined in a block that contains an unconditional 346 // branch to BB, then it must be in the 'conditional' part of the "if 347 // statement". If not, it definitely dominates the region. 348 BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator()); 349 if (!BI || BI->isConditional() || BI->getSuccessor(0) != BB) 350 return true; 351 352 // If we aren't allowing aggressive promotion anymore, then don't consider 353 // instructions in the 'if region'. 354 if (!AggressiveInsts) 355 return false; 356 357 // If we have seen this instruction before, don't count it again. 358 if (AggressiveInsts->count(I)) 359 return true; 360 361 // Okay, it looks like the instruction IS in the "condition". Check to 362 // see if it's a cheap instruction to unconditionally compute, and if it 363 // only uses stuff defined outside of the condition. If so, hoist it out. 364 if (!isSafeToSpeculativelyExecute(I)) 365 return false; 366 367 unsigned Cost = ComputeSpeculationCost(I, TTI); 368 369 // Allow exactly one instruction to be speculated regardless of its cost 370 // (as long as it is safe to do so). 371 // This is intended to flatten the CFG even if the instruction is a division 372 // or other expensive operation. The speculation of an expensive instruction 373 // is expected to be undone in CodeGenPrepare if the speculation has not 374 // enabled further IR optimizations. 375 if (Cost > CostRemaining && 376 (!SpeculateOneExpensiveInst || !AggressiveInsts->empty() || Depth > 0)) 377 return false; 378 379 // Avoid unsigned wrap. 380 CostRemaining = (Cost > CostRemaining) ? 0 : CostRemaining - Cost; 381 382 // Okay, we can only really hoist these out if their operands do 383 // not take us over the cost threshold. 384 for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) 385 if (!DominatesMergePoint(*i, BB, AggressiveInsts, CostRemaining, TTI, 386 Depth + 1)) 387 return false; 388 // Okay, it's safe to do this! Remember this instruction. 389 AggressiveInsts->insert(I); 390 return true; 391 } 392 393 /// Extract ConstantInt from value, looking through IntToPtr 394 /// and PointerNullValue. Return NULL if value is not a constant int. 395 static ConstantInt *GetConstantInt(Value *V, const DataLayout &DL) { 396 // Normal constant int. 397 ConstantInt *CI = dyn_cast<ConstantInt>(V); 398 if (CI || !isa<Constant>(V) || !V->getType()->isPointerTy()) 399 return CI; 400 401 // This is some kind of pointer constant. Turn it into a pointer-sized 402 // ConstantInt if possible. 403 IntegerType *PtrTy = cast<IntegerType>(DL.getIntPtrType(V->getType())); 404 405 // Null pointer means 0, see SelectionDAGBuilder::getValue(const Value*). 406 if (isa<ConstantPointerNull>(V)) 407 return ConstantInt::get(PtrTy, 0); 408 409 // IntToPtr const int. 410 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 411 if (CE->getOpcode() == Instruction::IntToPtr) 412 if (ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) { 413 // The constant is very likely to have the right type already. 414 if (CI->getType() == PtrTy) 415 return CI; 416 else 417 return cast<ConstantInt>( 418 ConstantExpr::getIntegerCast(CI, PtrTy, /*isSigned=*/false)); 419 } 420 return nullptr; 421 } 422 423 namespace { 424 425 /// Given a chain of or (||) or and (&&) comparison of a value against a 426 /// constant, this will try to recover the information required for a switch 427 /// structure. 428 /// It will depth-first traverse the chain of comparison, seeking for patterns 429 /// like %a == 12 or %a < 4 and combine them to produce a set of integer 430 /// representing the different cases for the switch. 431 /// Note that if the chain is composed of '||' it will build the set of elements 432 /// that matches the comparisons (i.e. any of this value validate the chain) 433 /// while for a chain of '&&' it will build the set elements that make the test 434 /// fail. 435 struct ConstantComparesGatherer { 436 const DataLayout &DL; 437 438 /// Value found for the switch comparison 439 Value *CompValue = nullptr; 440 441 /// Extra clause to be checked before the switch 442 Value *Extra = nullptr; 443 444 /// Set of integers to match in switch 445 SmallVector<ConstantInt *, 8> Vals; 446 447 /// Number of comparisons matched in the and/or chain 448 unsigned UsedICmps = 0; 449 450 /// Construct and compute the result for the comparison instruction Cond 451 ConstantComparesGatherer(Instruction *Cond, const DataLayout &DL) : DL(DL) { 452 gather(Cond); 453 } 454 455 ConstantComparesGatherer(const ConstantComparesGatherer &) = delete; 456 ConstantComparesGatherer & 457 operator=(const ConstantComparesGatherer &) = delete; 458 459 private: 460 /// Try to set the current value used for the comparison, it succeeds only if 461 /// it wasn't set before or if the new value is the same as the old one 462 bool setValueOnce(Value *NewVal) { 463 if (CompValue && CompValue != NewVal) 464 return false; 465 CompValue = NewVal; 466 return (CompValue != nullptr); 467 } 468 469 /// Try to match Instruction "I" as a comparison against a constant and 470 /// populates the array Vals with the set of values that match (or do not 471 /// match depending on isEQ). 472 /// Return false on failure. On success, the Value the comparison matched 473 /// against is placed in CompValue. 474 /// If CompValue is already set, the function is expected to fail if a match 475 /// is found but the value compared to is different. 476 bool matchInstruction(Instruction *I, bool isEQ) { 477 // If this is an icmp against a constant, handle this as one of the cases. 478 ICmpInst *ICI; 479 ConstantInt *C; 480 if (!((ICI = dyn_cast<ICmpInst>(I)) && 481 (C = GetConstantInt(I->getOperand(1), DL)))) { 482 return false; 483 } 484 485 Value *RHSVal; 486 const APInt *RHSC; 487 488 // Pattern match a special case 489 // (x & ~2^z) == y --> x == y || x == y|2^z 490 // This undoes a transformation done by instcombine to fuse 2 compares. 491 if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) { 492 // It's a little bit hard to see why the following transformations are 493 // correct. Here is a CVC3 program to verify them for 64-bit values: 494 495 /* 496 ONE : BITVECTOR(64) = BVZEROEXTEND(0bin1, 63); 497 x : BITVECTOR(64); 498 y : BITVECTOR(64); 499 z : BITVECTOR(64); 500 mask : BITVECTOR(64) = BVSHL(ONE, z); 501 QUERY( (y & ~mask = y) => 502 ((x & ~mask = y) <=> (x = y OR x = (y | mask))) 503 ); 504 QUERY( (y | mask = y) => 505 ((x | mask = y) <=> (x = y OR x = (y & ~mask))) 506 ); 507 */ 508 509 // Please note that each pattern must be a dual implication (<--> or 510 // iff). One directional implication can create spurious matches. If the 511 // implication is only one-way, an unsatisfiable condition on the left 512 // side can imply a satisfiable condition on the right side. Dual 513 // implication ensures that satisfiable conditions are transformed to 514 // other satisfiable conditions and unsatisfiable conditions are 515 // transformed to other unsatisfiable conditions. 516 517 // Here is a concrete example of a unsatisfiable condition on the left 518 // implying a satisfiable condition on the right: 519 // 520 // mask = (1 << z) 521 // (x & ~mask) == y --> (x == y || x == (y | mask)) 522 // 523 // Substituting y = 3, z = 0 yields: 524 // (x & -2) == 3 --> (x == 3 || x == 2) 525 526 // Pattern match a special case: 527 /* 528 QUERY( (y & ~mask = y) => 529 ((x & ~mask = y) <=> (x = y OR x = (y | mask))) 530 ); 531 */ 532 if (match(ICI->getOperand(0), 533 m_And(m_Value(RHSVal), m_APInt(RHSC)))) { 534 APInt Mask = ~*RHSC; 535 if (Mask.isPowerOf2() && (C->getValue() & ~Mask) == C->getValue()) { 536 // If we already have a value for the switch, it has to match! 537 if (!setValueOnce(RHSVal)) 538 return false; 539 540 Vals.push_back(C); 541 Vals.push_back( 542 ConstantInt::get(C->getContext(), 543 C->getValue() | Mask)); 544 UsedICmps++; 545 return true; 546 } 547 } 548 549 // Pattern match a special case: 550 /* 551 QUERY( (y | mask = y) => 552 ((x | mask = y) <=> (x = y OR x = (y & ~mask))) 553 ); 554 */ 555 if (match(ICI->getOperand(0), 556 m_Or(m_Value(RHSVal), m_APInt(RHSC)))) { 557 APInt Mask = *RHSC; 558 if (Mask.isPowerOf2() && (C->getValue() | Mask) == C->getValue()) { 559 // If we already have a value for the switch, it has to match! 560 if (!setValueOnce(RHSVal)) 561 return false; 562 563 Vals.push_back(C); 564 Vals.push_back(ConstantInt::get(C->getContext(), 565 C->getValue() & ~Mask)); 566 UsedICmps++; 567 return true; 568 } 569 } 570 571 // If we already have a value for the switch, it has to match! 572 if (!setValueOnce(ICI->getOperand(0))) 573 return false; 574 575 UsedICmps++; 576 Vals.push_back(C); 577 return ICI->getOperand(0); 578 } 579 580 // If we have "x ult 3", for example, then we can add 0,1,2 to the set. 581 ConstantRange Span = ConstantRange::makeAllowedICmpRegion( 582 ICI->getPredicate(), C->getValue()); 583 584 // Shift the range if the compare is fed by an add. This is the range 585 // compare idiom as emitted by instcombine. 586 Value *CandidateVal = I->getOperand(0); 587 if (match(I->getOperand(0), m_Add(m_Value(RHSVal), m_APInt(RHSC)))) { 588 Span = Span.subtract(*RHSC); 589 CandidateVal = RHSVal; 590 } 591 592 // If this is an and/!= check, then we are looking to build the set of 593 // value that *don't* pass the and chain. I.e. to turn "x ugt 2" into 594 // x != 0 && x != 1. 595 if (!isEQ) 596 Span = Span.inverse(); 597 598 // If there are a ton of values, we don't want to make a ginormous switch. 599 if (Span.isSizeLargerThan(8) || Span.isEmptySet()) { 600 return false; 601 } 602 603 // If we already have a value for the switch, it has to match! 604 if (!setValueOnce(CandidateVal)) 605 return false; 606 607 // Add all values from the range to the set 608 for (APInt Tmp = Span.getLower(); Tmp != Span.getUpper(); ++Tmp) 609 Vals.push_back(ConstantInt::get(I->getContext(), Tmp)); 610 611 UsedICmps++; 612 return true; 613 } 614 615 /// Given a potentially 'or'd or 'and'd together collection of icmp 616 /// eq/ne/lt/gt instructions that compare a value against a constant, extract 617 /// the value being compared, and stick the list constants into the Vals 618 /// vector. 619 /// One "Extra" case is allowed to differ from the other. 620 void gather(Value *V) { 621 Instruction *I = dyn_cast<Instruction>(V); 622 bool isEQ = (I->getOpcode() == Instruction::Or); 623 624 // Keep a stack (SmallVector for efficiency) for depth-first traversal 625 SmallVector<Value *, 8> DFT; 626 SmallPtrSet<Value *, 8> Visited; 627 628 // Initialize 629 Visited.insert(V); 630 DFT.push_back(V); 631 632 while (!DFT.empty()) { 633 V = DFT.pop_back_val(); 634 635 if (Instruction *I = dyn_cast<Instruction>(V)) { 636 // If it is a || (or && depending on isEQ), process the operands. 637 if (I->getOpcode() == (isEQ ? Instruction::Or : Instruction::And)) { 638 if (Visited.insert(I->getOperand(1)).second) 639 DFT.push_back(I->getOperand(1)); 640 if (Visited.insert(I->getOperand(0)).second) 641 DFT.push_back(I->getOperand(0)); 642 continue; 643 } 644 645 // Try to match the current instruction 646 if (matchInstruction(I, isEQ)) 647 // Match succeed, continue the loop 648 continue; 649 } 650 651 // One element of the sequence of || (or &&) could not be match as a 652 // comparison against the same value as the others. 653 // We allow only one "Extra" case to be checked before the switch 654 if (!Extra) { 655 Extra = V; 656 continue; 657 } 658 // Failed to parse a proper sequence, abort now 659 CompValue = nullptr; 660 break; 661 } 662 } 663 }; 664 665 } // end anonymous namespace 666 667 static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) { 668 Instruction *Cond = nullptr; 669 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 670 Cond = dyn_cast<Instruction>(SI->getCondition()); 671 } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 672 if (BI->isConditional()) 673 Cond = dyn_cast<Instruction>(BI->getCondition()); 674 } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(TI)) { 675 Cond = dyn_cast<Instruction>(IBI->getAddress()); 676 } 677 678 TI->eraseFromParent(); 679 if (Cond) 680 RecursivelyDeleteTriviallyDeadInstructions(Cond); 681 } 682 683 /// Return true if the specified terminator checks 684 /// to see if a value is equal to constant integer value. 685 Value *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) { 686 Value *CV = nullptr; 687 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 688 // Do not permit merging of large switch instructions into their 689 // predecessors unless there is only one predecessor. 690 if (SI->getNumSuccessors() * pred_size(SI->getParent()) <= 128) 691 CV = SI->getCondition(); 692 } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 693 if (BI->isConditional() && BI->getCondition()->hasOneUse()) 694 if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) { 695 if (ICI->isEquality() && GetConstantInt(ICI->getOperand(1), DL)) 696 CV = ICI->getOperand(0); 697 } 698 699 // Unwrap any lossless ptrtoint cast. 700 if (CV) { 701 if (PtrToIntInst *PTII = dyn_cast<PtrToIntInst>(CV)) { 702 Value *Ptr = PTII->getPointerOperand(); 703 if (PTII->getType() == DL.getIntPtrType(Ptr->getType())) 704 CV = Ptr; 705 } 706 } 707 return CV; 708 } 709 710 /// Given a value comparison instruction, 711 /// decode all of the 'cases' that it represents and return the 'default' block. 712 BasicBlock *SimplifyCFGOpt::GetValueEqualityComparisonCases( 713 TerminatorInst *TI, std::vector<ValueEqualityComparisonCase> &Cases) { 714 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 715 Cases.reserve(SI->getNumCases()); 716 for (auto Case : SI->cases()) 717 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(), 718 Case.getCaseSuccessor())); 719 return SI->getDefaultDest(); 720 } 721 722 BranchInst *BI = cast<BranchInst>(TI); 723 ICmpInst *ICI = cast<ICmpInst>(BI->getCondition()); 724 BasicBlock *Succ = BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_NE); 725 Cases.push_back(ValueEqualityComparisonCase( 726 GetConstantInt(ICI->getOperand(1), DL), Succ)); 727 return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ); 728 } 729 730 /// Given a vector of bb/value pairs, remove any entries 731 /// in the list that match the specified block. 732 static void 733 EliminateBlockCases(BasicBlock *BB, 734 std::vector<ValueEqualityComparisonCase> &Cases) { 735 Cases.erase(std::remove(Cases.begin(), Cases.end(), BB), Cases.end()); 736 } 737 738 /// Return true if there are any keys in C1 that exist in C2 as well. 739 static bool ValuesOverlap(std::vector<ValueEqualityComparisonCase> &C1, 740 std::vector<ValueEqualityComparisonCase> &C2) { 741 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2; 742 743 // Make V1 be smaller than V2. 744 if (V1->size() > V2->size()) 745 std::swap(V1, V2); 746 747 if (V1->empty()) 748 return false; 749 if (V1->size() == 1) { 750 // Just scan V2. 751 ConstantInt *TheVal = (*V1)[0].Value; 752 for (unsigned i = 0, e = V2->size(); i != e; ++i) 753 if (TheVal == (*V2)[i].Value) 754 return true; 755 } 756 757 // Otherwise, just sort both lists and compare element by element. 758 array_pod_sort(V1->begin(), V1->end()); 759 array_pod_sort(V2->begin(), V2->end()); 760 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size(); 761 while (i1 != e1 && i2 != e2) { 762 if ((*V1)[i1].Value == (*V2)[i2].Value) 763 return true; 764 if ((*V1)[i1].Value < (*V2)[i2].Value) 765 ++i1; 766 else 767 ++i2; 768 } 769 return false; 770 } 771 772 // Set branch weights on SwitchInst. This sets the metadata if there is at 773 // least one non-zero weight. 774 static void setBranchWeights(SwitchInst *SI, ArrayRef<uint32_t> Weights) { 775 // Check that there is at least one non-zero weight. Otherwise, pass 776 // nullptr to setMetadata which will erase the existing metadata. 777 MDNode *N = nullptr; 778 if (llvm::any_of(Weights, [](uint32_t W) { return W != 0; })) 779 N = MDBuilder(SI->getParent()->getContext()).createBranchWeights(Weights); 780 SI->setMetadata(LLVMContext::MD_prof, N); 781 } 782 783 // Similar to the above, but for branch and select instructions that take 784 // exactly 2 weights. 785 static void setBranchWeights(Instruction *I, uint32_t TrueWeight, 786 uint32_t FalseWeight) { 787 assert(isa<BranchInst>(I) || isa<SelectInst>(I)); 788 // Check that there is at least one non-zero weight. Otherwise, pass 789 // nullptr to setMetadata which will erase the existing metadata. 790 MDNode *N = nullptr; 791 if (TrueWeight || FalseWeight) 792 N = MDBuilder(I->getParent()->getContext()) 793 .createBranchWeights(TrueWeight, FalseWeight); 794 I->setMetadata(LLVMContext::MD_prof, N); 795 } 796 797 /// If TI is known to be a terminator instruction and its block is known to 798 /// only have a single predecessor block, check to see if that predecessor is 799 /// also a value comparison with the same value, and if that comparison 800 /// determines the outcome of this comparison. If so, simplify TI. This does a 801 /// very limited form of jump threading. 802 bool SimplifyCFGOpt::SimplifyEqualityComparisonWithOnlyPredecessor( 803 TerminatorInst *TI, BasicBlock *Pred, IRBuilder<> &Builder) { 804 Value *PredVal = isValueEqualityComparison(Pred->getTerminator()); 805 if (!PredVal) 806 return false; // Not a value comparison in predecessor. 807 808 Value *ThisVal = isValueEqualityComparison(TI); 809 assert(ThisVal && "This isn't a value comparison!!"); 810 if (ThisVal != PredVal) 811 return false; // Different predicates. 812 813 // TODO: Preserve branch weight metadata, similarly to how 814 // FoldValueComparisonIntoPredecessors preserves it. 815 816 // Find out information about when control will move from Pred to TI's block. 817 std::vector<ValueEqualityComparisonCase> PredCases; 818 BasicBlock *PredDef = 819 GetValueEqualityComparisonCases(Pred->getTerminator(), PredCases); 820 EliminateBlockCases(PredDef, PredCases); // Remove default from cases. 821 822 // Find information about how control leaves this block. 823 std::vector<ValueEqualityComparisonCase> ThisCases; 824 BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases); 825 EliminateBlockCases(ThisDef, ThisCases); // Remove default from cases. 826 827 // If TI's block is the default block from Pred's comparison, potentially 828 // simplify TI based on this knowledge. 829 if (PredDef == TI->getParent()) { 830 // If we are here, we know that the value is none of those cases listed in 831 // PredCases. If there are any cases in ThisCases that are in PredCases, we 832 // can simplify TI. 833 if (!ValuesOverlap(PredCases, ThisCases)) 834 return false; 835 836 if (isa<BranchInst>(TI)) { 837 // Okay, one of the successors of this condbr is dead. Convert it to a 838 // uncond br. 839 assert(ThisCases.size() == 1 && "Branch can only have one case!"); 840 // Insert the new branch. 841 Instruction *NI = Builder.CreateBr(ThisDef); 842 (void)NI; 843 844 // Remove PHI node entries for the dead edge. 845 ThisCases[0].Dest->removePredecessor(TI->getParent()); 846 847 LLVM_DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 848 << "Through successor TI: " << *TI << "Leaving: " << *NI 849 << "\n"); 850 851 EraseTerminatorInstAndDCECond(TI); 852 return true; 853 } 854 855 SwitchInst *SI = cast<SwitchInst>(TI); 856 // Okay, TI has cases that are statically dead, prune them away. 857 SmallPtrSet<Constant *, 16> DeadCases; 858 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 859 DeadCases.insert(PredCases[i].Value); 860 861 LLVM_DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 862 << "Through successor TI: " << *TI); 863 864 // Collect branch weights into a vector. 865 SmallVector<uint32_t, 8> Weights; 866 MDNode *MD = SI->getMetadata(LLVMContext::MD_prof); 867 bool HasWeight = MD && (MD->getNumOperands() == 2 + SI->getNumCases()); 868 if (HasWeight) 869 for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e; 870 ++MD_i) { 871 ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(MD_i)); 872 Weights.push_back(CI->getValue().getZExtValue()); 873 } 874 for (SwitchInst::CaseIt i = SI->case_end(), e = SI->case_begin(); i != e;) { 875 --i; 876 if (DeadCases.count(i->getCaseValue())) { 877 if (HasWeight) { 878 std::swap(Weights[i->getCaseIndex() + 1], Weights.back()); 879 Weights.pop_back(); 880 } 881 i->getCaseSuccessor()->removePredecessor(TI->getParent()); 882 SI->removeCase(i); 883 } 884 } 885 if (HasWeight && Weights.size() >= 2) 886 setBranchWeights(SI, Weights); 887 888 LLVM_DEBUG(dbgs() << "Leaving: " << *TI << "\n"); 889 return true; 890 } 891 892 // Otherwise, TI's block must correspond to some matched value. Find out 893 // which value (or set of values) this is. 894 ConstantInt *TIV = nullptr; 895 BasicBlock *TIBB = TI->getParent(); 896 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 897 if (PredCases[i].Dest == TIBB) { 898 if (TIV) 899 return false; // Cannot handle multiple values coming to this block. 900 TIV = PredCases[i].Value; 901 } 902 assert(TIV && "No edge from pred to succ?"); 903 904 // Okay, we found the one constant that our value can be if we get into TI's 905 // BB. Find out which successor will unconditionally be branched to. 906 BasicBlock *TheRealDest = nullptr; 907 for (unsigned i = 0, e = ThisCases.size(); i != e; ++i) 908 if (ThisCases[i].Value == TIV) { 909 TheRealDest = ThisCases[i].Dest; 910 break; 911 } 912 913 // If not handled by any explicit cases, it is handled by the default case. 914 if (!TheRealDest) 915 TheRealDest = ThisDef; 916 917 // Remove PHI node entries for dead edges. 918 BasicBlock *CheckEdge = TheRealDest; 919 for (BasicBlock *Succ : successors(TIBB)) 920 if (Succ != CheckEdge) 921 Succ->removePredecessor(TIBB); 922 else 923 CheckEdge = nullptr; 924 925 // Insert the new branch. 926 Instruction *NI = Builder.CreateBr(TheRealDest); 927 (void)NI; 928 929 LLVM_DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 930 << "Through successor TI: " << *TI << "Leaving: " << *NI 931 << "\n"); 932 933 EraseTerminatorInstAndDCECond(TI); 934 return true; 935 } 936 937 namespace { 938 939 /// This class implements a stable ordering of constant 940 /// integers that does not depend on their address. This is important for 941 /// applications that sort ConstantInt's to ensure uniqueness. 942 struct ConstantIntOrdering { 943 bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { 944 return LHS->getValue().ult(RHS->getValue()); 945 } 946 }; 947 948 } // end anonymous namespace 949 950 static int ConstantIntSortPredicate(ConstantInt *const *P1, 951 ConstantInt *const *P2) { 952 const ConstantInt *LHS = *P1; 953 const ConstantInt *RHS = *P2; 954 if (LHS == RHS) 955 return 0; 956 return LHS->getValue().ult(RHS->getValue()) ? 1 : -1; 957 } 958 959 static inline bool HasBranchWeights(const Instruction *I) { 960 MDNode *ProfMD = I->getMetadata(LLVMContext::MD_prof); 961 if (ProfMD && ProfMD->getOperand(0)) 962 if (MDString *MDS = dyn_cast<MDString>(ProfMD->getOperand(0))) 963 return MDS->getString().equals("branch_weights"); 964 965 return false; 966 } 967 968 /// Get Weights of a given TerminatorInst, the default weight is at the front 969 /// of the vector. If TI is a conditional eq, we need to swap the branch-weight 970 /// metadata. 971 static void GetBranchWeights(TerminatorInst *TI, 972 SmallVectorImpl<uint64_t> &Weights) { 973 MDNode *MD = TI->getMetadata(LLVMContext::MD_prof); 974 assert(MD); 975 for (unsigned i = 1, e = MD->getNumOperands(); i < e; ++i) { 976 ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(i)); 977 Weights.push_back(CI->getValue().getZExtValue()); 978 } 979 980 // If TI is a conditional eq, the default case is the false case, 981 // and the corresponding branch-weight data is at index 2. We swap the 982 // default weight to be the first entry. 983 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 984 assert(Weights.size() == 2); 985 ICmpInst *ICI = cast<ICmpInst>(BI->getCondition()); 986 if (ICI->getPredicate() == ICmpInst::ICMP_EQ) 987 std::swap(Weights.front(), Weights.back()); 988 } 989 } 990 991 /// Keep halving the weights until all can fit in uint32_t. 992 static void FitWeights(MutableArrayRef<uint64_t> Weights) { 993 uint64_t Max = *std::max_element(Weights.begin(), Weights.end()); 994 if (Max > UINT_MAX) { 995 unsigned Offset = 32 - countLeadingZeros(Max); 996 for (uint64_t &I : Weights) 997 I >>= Offset; 998 } 999 } 1000 1001 /// The specified terminator is a value equality comparison instruction 1002 /// (either a switch or a branch on "X == c"). 1003 /// See if any of the predecessors of the terminator block are value comparisons 1004 /// on the same value. If so, and if safe to do so, fold them together. 1005 bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI, 1006 IRBuilder<> &Builder) { 1007 BasicBlock *BB = TI->getParent(); 1008 Value *CV = isValueEqualityComparison(TI); // CondVal 1009 assert(CV && "Not a comparison?"); 1010 bool Changed = false; 1011 1012 SmallVector<BasicBlock *, 16> Preds(pred_begin(BB), pred_end(BB)); 1013 while (!Preds.empty()) { 1014 BasicBlock *Pred = Preds.pop_back_val(); 1015 1016 // See if the predecessor is a comparison with the same value. 1017 TerminatorInst *PTI = Pred->getTerminator(); 1018 Value *PCV = isValueEqualityComparison(PTI); // PredCondVal 1019 1020 if (PCV == CV && TI != PTI) { 1021 SmallSetVector<BasicBlock*, 4> FailBlocks; 1022 if (!SafeToMergeTerminators(TI, PTI, &FailBlocks)) { 1023 for (auto *Succ : FailBlocks) { 1024 if (!SplitBlockPredecessors(Succ, TI->getParent(), ".fold.split")) 1025 return false; 1026 } 1027 } 1028 1029 // Figure out which 'cases' to copy from SI to PSI. 1030 std::vector<ValueEqualityComparisonCase> BBCases; 1031 BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases); 1032 1033 std::vector<ValueEqualityComparisonCase> PredCases; 1034 BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases); 1035 1036 // Based on whether the default edge from PTI goes to BB or not, fill in 1037 // PredCases and PredDefault with the new switch cases we would like to 1038 // build. 1039 SmallVector<BasicBlock *, 8> NewSuccessors; 1040 1041 // Update the branch weight metadata along the way 1042 SmallVector<uint64_t, 8> Weights; 1043 bool PredHasWeights = HasBranchWeights(PTI); 1044 bool SuccHasWeights = HasBranchWeights(TI); 1045 1046 if (PredHasWeights) { 1047 GetBranchWeights(PTI, Weights); 1048 // branch-weight metadata is inconsistent here. 1049 if (Weights.size() != 1 + PredCases.size()) 1050 PredHasWeights = SuccHasWeights = false; 1051 } else if (SuccHasWeights) 1052 // If there are no predecessor weights but there are successor weights, 1053 // populate Weights with 1, which will later be scaled to the sum of 1054 // successor's weights 1055 Weights.assign(1 + PredCases.size(), 1); 1056 1057 SmallVector<uint64_t, 8> SuccWeights; 1058 if (SuccHasWeights) { 1059 GetBranchWeights(TI, SuccWeights); 1060 // branch-weight metadata is inconsistent here. 1061 if (SuccWeights.size() != 1 + BBCases.size()) 1062 PredHasWeights = SuccHasWeights = false; 1063 } else if (PredHasWeights) 1064 SuccWeights.assign(1 + BBCases.size(), 1); 1065 1066 if (PredDefault == BB) { 1067 // If this is the default destination from PTI, only the edges in TI 1068 // that don't occur in PTI, or that branch to BB will be activated. 1069 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled; 1070 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 1071 if (PredCases[i].Dest != BB) 1072 PTIHandled.insert(PredCases[i].Value); 1073 else { 1074 // The default destination is BB, we don't need explicit targets. 1075 std::swap(PredCases[i], PredCases.back()); 1076 1077 if (PredHasWeights || SuccHasWeights) { 1078 // Increase weight for the default case. 1079 Weights[0] += Weights[i + 1]; 1080 std::swap(Weights[i + 1], Weights.back()); 1081 Weights.pop_back(); 1082 } 1083 1084 PredCases.pop_back(); 1085 --i; 1086 --e; 1087 } 1088 1089 // Reconstruct the new switch statement we will be building. 1090 if (PredDefault != BBDefault) { 1091 PredDefault->removePredecessor(Pred); 1092 PredDefault = BBDefault; 1093 NewSuccessors.push_back(BBDefault); 1094 } 1095 1096 unsigned CasesFromPred = Weights.size(); 1097 uint64_t ValidTotalSuccWeight = 0; 1098 for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 1099 if (!PTIHandled.count(BBCases[i].Value) && 1100 BBCases[i].Dest != BBDefault) { 1101 PredCases.push_back(BBCases[i]); 1102 NewSuccessors.push_back(BBCases[i].Dest); 1103 if (SuccHasWeights || PredHasWeights) { 1104 // The default weight is at index 0, so weight for the ith case 1105 // should be at index i+1. Scale the cases from successor by 1106 // PredDefaultWeight (Weights[0]). 1107 Weights.push_back(Weights[0] * SuccWeights[i + 1]); 1108 ValidTotalSuccWeight += SuccWeights[i + 1]; 1109 } 1110 } 1111 1112 if (SuccHasWeights || PredHasWeights) { 1113 ValidTotalSuccWeight += SuccWeights[0]; 1114 // Scale the cases from predecessor by ValidTotalSuccWeight. 1115 for (unsigned i = 1; i < CasesFromPred; ++i) 1116 Weights[i] *= ValidTotalSuccWeight; 1117 // Scale the default weight by SuccDefaultWeight (SuccWeights[0]). 1118 Weights[0] *= SuccWeights[0]; 1119 } 1120 } else { 1121 // If this is not the default destination from PSI, only the edges 1122 // in SI that occur in PSI with a destination of BB will be 1123 // activated. 1124 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled; 1125 std::map<ConstantInt *, uint64_t> WeightsForHandled; 1126 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 1127 if (PredCases[i].Dest == BB) { 1128 PTIHandled.insert(PredCases[i].Value); 1129 1130 if (PredHasWeights || SuccHasWeights) { 1131 WeightsForHandled[PredCases[i].Value] = Weights[i + 1]; 1132 std::swap(Weights[i + 1], Weights.back()); 1133 Weights.pop_back(); 1134 } 1135 1136 std::swap(PredCases[i], PredCases.back()); 1137 PredCases.pop_back(); 1138 --i; 1139 --e; 1140 } 1141 1142 // Okay, now we know which constants were sent to BB from the 1143 // predecessor. Figure out where they will all go now. 1144 for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 1145 if (PTIHandled.count(BBCases[i].Value)) { 1146 // If this is one we are capable of getting... 1147 if (PredHasWeights || SuccHasWeights) 1148 Weights.push_back(WeightsForHandled[BBCases[i].Value]); 1149 PredCases.push_back(BBCases[i]); 1150 NewSuccessors.push_back(BBCases[i].Dest); 1151 PTIHandled.erase( 1152 BBCases[i].Value); // This constant is taken care of 1153 } 1154 1155 // If there are any constants vectored to BB that TI doesn't handle, 1156 // they must go to the default destination of TI. 1157 for (ConstantInt *I : PTIHandled) { 1158 if (PredHasWeights || SuccHasWeights) 1159 Weights.push_back(WeightsForHandled[I]); 1160 PredCases.push_back(ValueEqualityComparisonCase(I, BBDefault)); 1161 NewSuccessors.push_back(BBDefault); 1162 } 1163 } 1164 1165 // Okay, at this point, we know which new successor Pred will get. Make 1166 // sure we update the number of entries in the PHI nodes for these 1167 // successors. 1168 for (BasicBlock *NewSuccessor : NewSuccessors) 1169 AddPredecessorToBlock(NewSuccessor, Pred, BB); 1170 1171 Builder.SetInsertPoint(PTI); 1172 // Convert pointer to int before we switch. 1173 if (CV->getType()->isPointerTy()) { 1174 CV = Builder.CreatePtrToInt(CV, DL.getIntPtrType(CV->getType()), 1175 "magicptr"); 1176 } 1177 1178 // Now that the successors are updated, create the new Switch instruction. 1179 SwitchInst *NewSI = 1180 Builder.CreateSwitch(CV, PredDefault, PredCases.size()); 1181 NewSI->setDebugLoc(PTI->getDebugLoc()); 1182 for (ValueEqualityComparisonCase &V : PredCases) 1183 NewSI->addCase(V.Value, V.Dest); 1184 1185 if (PredHasWeights || SuccHasWeights) { 1186 // Halve the weights if any of them cannot fit in an uint32_t 1187 FitWeights(Weights); 1188 1189 SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end()); 1190 1191 setBranchWeights(NewSI, MDWeights); 1192 } 1193 1194 EraseTerminatorInstAndDCECond(PTI); 1195 1196 // Okay, last check. If BB is still a successor of PSI, then we must 1197 // have an infinite loop case. If so, add an infinitely looping block 1198 // to handle the case to preserve the behavior of the code. 1199 BasicBlock *InfLoopBlock = nullptr; 1200 for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i) 1201 if (NewSI->getSuccessor(i) == BB) { 1202 if (!InfLoopBlock) { 1203 // Insert it at the end of the function, because it's either code, 1204 // or it won't matter if it's hot. :) 1205 InfLoopBlock = BasicBlock::Create(BB->getContext(), "infloop", 1206 BB->getParent()); 1207 BranchInst::Create(InfLoopBlock, InfLoopBlock); 1208 } 1209 NewSI->setSuccessor(i, InfLoopBlock); 1210 } 1211 1212 Changed = true; 1213 } 1214 } 1215 return Changed; 1216 } 1217 1218 // If we would need to insert a select that uses the value of this invoke 1219 // (comments in HoistThenElseCodeToIf explain why we would need to do this), we 1220 // can't hoist the invoke, as there is nowhere to put the select in this case. 1221 static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, 1222 Instruction *I1, Instruction *I2) { 1223 for (BasicBlock *Succ : successors(BB1)) { 1224 for (const PHINode &PN : Succ->phis()) { 1225 Value *BB1V = PN.getIncomingValueForBlock(BB1); 1226 Value *BB2V = PN.getIncomingValueForBlock(BB2); 1227 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) { 1228 return false; 1229 } 1230 } 1231 } 1232 return true; 1233 } 1234 1235 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I); 1236 1237 /// Given a conditional branch that goes to BB1 and BB2, hoist any common code 1238 /// in the two blocks up into the branch block. The caller of this function 1239 /// guarantees that BI's block dominates BB1 and BB2. 1240 static bool HoistThenElseCodeToIf(BranchInst *BI, 1241 const TargetTransformInfo &TTI) { 1242 // This does very trivial matching, with limited scanning, to find identical 1243 // instructions in the two blocks. In particular, we don't want to get into 1244 // O(M*N) situations here where M and N are the sizes of BB1 and BB2. As 1245 // such, we currently just scan for obviously identical instructions in an 1246 // identical order. 1247 BasicBlock *BB1 = BI->getSuccessor(0); // The true destination. 1248 BasicBlock *BB2 = BI->getSuccessor(1); // The false destination 1249 1250 BasicBlock::iterator BB1_Itr = BB1->begin(); 1251 BasicBlock::iterator BB2_Itr = BB2->begin(); 1252 1253 Instruction *I1 = &*BB1_Itr++, *I2 = &*BB2_Itr++; 1254 // Skip debug info if it is not identical. 1255 DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1); 1256 DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2); 1257 if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) { 1258 while (isa<DbgInfoIntrinsic>(I1)) 1259 I1 = &*BB1_Itr++; 1260 while (isa<DbgInfoIntrinsic>(I2)) 1261 I2 = &*BB2_Itr++; 1262 } 1263 if (isa<PHINode>(I1) || !I1->isIdenticalToWhenDefined(I2) || 1264 (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2))) 1265 return false; 1266 1267 BasicBlock *BIParent = BI->getParent(); 1268 1269 bool Changed = false; 1270 do { 1271 // If we are hoisting the terminator instruction, don't move one (making a 1272 // broken BB), instead clone it, and remove BI. 1273 if (isa<TerminatorInst>(I1)) 1274 goto HoistTerminator; 1275 1276 // If we're going to hoist a call, make sure that the two instructions we're 1277 // commoning/hoisting are both marked with musttail, or neither of them is 1278 // marked as such. Otherwise, we might end up in a situation where we hoist 1279 // from a block where the terminator is a `ret` to a block where the terminator 1280 // is a `br`, and `musttail` calls expect to be followed by a return. 1281 auto *C1 = dyn_cast<CallInst>(I1); 1282 auto *C2 = dyn_cast<CallInst>(I2); 1283 if (C1 && C2) 1284 if (C1->isMustTailCall() != C2->isMustTailCall()) 1285 return Changed; 1286 1287 if (!TTI.isProfitableToHoist(I1) || !TTI.isProfitableToHoist(I2)) 1288 return Changed; 1289 1290 if (isa<DbgInfoIntrinsic>(I1) || isa<DbgInfoIntrinsic>(I2)) { 1291 assert (isa<DbgInfoIntrinsic>(I1) && isa<DbgInfoIntrinsic>(I2)); 1292 // The debug location is an integral part of a debug info intrinsic 1293 // and can't be separated from it or replaced. Instead of attempting 1294 // to merge locations, simply hoist both copies of the intrinsic. 1295 BIParent->getInstList().splice(BI->getIterator(), 1296 BB1->getInstList(), I1); 1297 BIParent->getInstList().splice(BI->getIterator(), 1298 BB2->getInstList(), I2); 1299 Changed = true; 1300 } else { 1301 // For a normal instruction, we just move one to right before the branch, 1302 // then replace all uses of the other with the first. Finally, we remove 1303 // the now redundant second instruction. 1304 BIParent->getInstList().splice(BI->getIterator(), 1305 BB1->getInstList(), I1); 1306 if (!I2->use_empty()) 1307 I2->replaceAllUsesWith(I1); 1308 I1->andIRFlags(I2); 1309 unsigned KnownIDs[] = {LLVMContext::MD_tbaa, 1310 LLVMContext::MD_range, 1311 LLVMContext::MD_fpmath, 1312 LLVMContext::MD_invariant_load, 1313 LLVMContext::MD_nonnull, 1314 LLVMContext::MD_invariant_group, 1315 LLVMContext::MD_align, 1316 LLVMContext::MD_dereferenceable, 1317 LLVMContext::MD_dereferenceable_or_null, 1318 LLVMContext::MD_mem_parallel_loop_access}; 1319 combineMetadata(I1, I2, KnownIDs); 1320 1321 // I1 and I2 are being combined into a single instruction. Its debug 1322 // location is the merged locations of the original instructions. 1323 I1->applyMergedLocation(I1->getDebugLoc(), I2->getDebugLoc()); 1324 1325 I2->eraseFromParent(); 1326 Changed = true; 1327 } 1328 1329 I1 = &*BB1_Itr++; 1330 I2 = &*BB2_Itr++; 1331 // Skip debug info if it is not identical. 1332 DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1); 1333 DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2); 1334 if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) { 1335 while (isa<DbgInfoIntrinsic>(I1)) 1336 I1 = &*BB1_Itr++; 1337 while (isa<DbgInfoIntrinsic>(I2)) 1338 I2 = &*BB2_Itr++; 1339 } 1340 } while (I1->isIdenticalToWhenDefined(I2)); 1341 1342 return true; 1343 1344 HoistTerminator: 1345 // It may not be possible to hoist an invoke. 1346 if (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)) 1347 return Changed; 1348 1349 for (BasicBlock *Succ : successors(BB1)) { 1350 for (PHINode &PN : Succ->phis()) { 1351 Value *BB1V = PN.getIncomingValueForBlock(BB1); 1352 Value *BB2V = PN.getIncomingValueForBlock(BB2); 1353 if (BB1V == BB2V) 1354 continue; 1355 1356 // Check for passingValueIsAlwaysUndefined here because we would rather 1357 // eliminate undefined control flow then converting it to a select. 1358 if (passingValueIsAlwaysUndefined(BB1V, &PN) || 1359 passingValueIsAlwaysUndefined(BB2V, &PN)) 1360 return Changed; 1361 1362 if (isa<ConstantExpr>(BB1V) && !isSafeToSpeculativelyExecute(BB1V)) 1363 return Changed; 1364 if (isa<ConstantExpr>(BB2V) && !isSafeToSpeculativelyExecute(BB2V)) 1365 return Changed; 1366 } 1367 } 1368 1369 // Okay, it is safe to hoist the terminator. 1370 Instruction *NT = I1->clone(); 1371 BIParent->getInstList().insert(BI->getIterator(), NT); 1372 if (!NT->getType()->isVoidTy()) { 1373 I1->replaceAllUsesWith(NT); 1374 I2->replaceAllUsesWith(NT); 1375 NT->takeName(I1); 1376 } 1377 1378 IRBuilder<NoFolder> Builder(NT); 1379 // Hoisting one of the terminators from our successor is a great thing. 1380 // Unfortunately, the successors of the if/else blocks may have PHI nodes in 1381 // them. If they do, all PHI entries for BB1/BB2 must agree for all PHI 1382 // nodes, so we insert select instruction to compute the final result. 1383 std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects; 1384 for (BasicBlock *Succ : successors(BB1)) { 1385 for (PHINode &PN : Succ->phis()) { 1386 Value *BB1V = PN.getIncomingValueForBlock(BB1); 1387 Value *BB2V = PN.getIncomingValueForBlock(BB2); 1388 if (BB1V == BB2V) 1389 continue; 1390 1391 // These values do not agree. Insert a select instruction before NT 1392 // that determines the right value. 1393 SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)]; 1394 if (!SI) 1395 SI = cast<SelectInst>( 1396 Builder.CreateSelect(BI->getCondition(), BB1V, BB2V, 1397 BB1V->getName() + "." + BB2V->getName(), BI)); 1398 1399 // Make the PHI node use the select for all incoming values for BB1/BB2 1400 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) 1401 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2) 1402 PN.setIncomingValue(i, SI); 1403 } 1404 } 1405 1406 // Update any PHI nodes in our new successors. 1407 for (BasicBlock *Succ : successors(BB1)) 1408 AddPredecessorToBlock(Succ, BIParent, BB1); 1409 1410 EraseTerminatorInstAndDCECond(BI); 1411 return true; 1412 } 1413 1414 // All instructions in Insts belong to different blocks that all unconditionally 1415 // branch to a common successor. Analyze each instruction and return true if it 1416 // would be possible to sink them into their successor, creating one common 1417 // instruction instead. For every value that would be required to be provided by 1418 // PHI node (because an operand varies in each input block), add to PHIOperands. 1419 static bool canSinkInstructions( 1420 ArrayRef<Instruction *> Insts, 1421 DenseMap<Instruction *, SmallVector<Value *, 4>> &PHIOperands) { 1422 // Prune out obviously bad instructions to move. Any non-store instruction 1423 // must have exactly one use, and we check later that use is by a single, 1424 // common PHI instruction in the successor. 1425 for (auto *I : Insts) { 1426 // These instructions may change or break semantics if moved. 1427 if (isa<PHINode>(I) || I->isEHPad() || isa<AllocaInst>(I) || 1428 I->getType()->isTokenTy()) 1429 return false; 1430 1431 // Conservatively return false if I is an inline-asm instruction. Sinking 1432 // and merging inline-asm instructions can potentially create arguments 1433 // that cannot satisfy the inline-asm constraints. 1434 if (const auto *C = dyn_cast<CallInst>(I)) 1435 if (C->isInlineAsm()) 1436 return false; 1437 1438 // Everything must have only one use too, apart from stores which 1439 // have no uses. 1440 if (!isa<StoreInst>(I) && !I->hasOneUse()) 1441 return false; 1442 } 1443 1444 const Instruction *I0 = Insts.front(); 1445 for (auto *I : Insts) 1446 if (!I->isSameOperationAs(I0)) 1447 return false; 1448 1449 // All instructions in Insts are known to be the same opcode. If they aren't 1450 // stores, check the only user of each is a PHI or in the same block as the 1451 // instruction, because if a user is in the same block as an instruction 1452 // we're contemplating sinking, it must already be determined to be sinkable. 1453 if (!isa<StoreInst>(I0)) { 1454 auto *PNUse = dyn_cast<PHINode>(*I0->user_begin()); 1455 auto *Succ = I0->getParent()->getTerminator()->getSuccessor(0); 1456 if (!all_of(Insts, [&PNUse,&Succ](const Instruction *I) -> bool { 1457 auto *U = cast<Instruction>(*I->user_begin()); 1458 return (PNUse && 1459 PNUse->getParent() == Succ && 1460 PNUse->getIncomingValueForBlock(I->getParent()) == I) || 1461 U->getParent() == I->getParent(); 1462 })) 1463 return false; 1464 } 1465 1466 // Because SROA can't handle speculating stores of selects, try not 1467 // to sink loads or stores of allocas when we'd have to create a PHI for 1468 // the address operand. Also, because it is likely that loads or stores 1469 // of allocas will disappear when Mem2Reg/SROA is run, don't sink them. 1470 // This can cause code churn which can have unintended consequences down 1471 // the line - see https://llvm.org/bugs/show_bug.cgi?id=30244. 1472 // FIXME: This is a workaround for a deficiency in SROA - see 1473 // https://llvm.org/bugs/show_bug.cgi?id=30188 1474 if (isa<StoreInst>(I0) && any_of(Insts, [](const Instruction *I) { 1475 return isa<AllocaInst>(I->getOperand(1)); 1476 })) 1477 return false; 1478 if (isa<LoadInst>(I0) && any_of(Insts, [](const Instruction *I) { 1479 return isa<AllocaInst>(I->getOperand(0)); 1480 })) 1481 return false; 1482 1483 for (unsigned OI = 0, OE = I0->getNumOperands(); OI != OE; ++OI) { 1484 if (I0->getOperand(OI)->getType()->isTokenTy()) 1485 // Don't touch any operand of token type. 1486 return false; 1487 1488 auto SameAsI0 = [&I0, OI](const Instruction *I) { 1489 assert(I->getNumOperands() == I0->getNumOperands()); 1490 return I->getOperand(OI) == I0->getOperand(OI); 1491 }; 1492 if (!all_of(Insts, SameAsI0)) { 1493 if (!canReplaceOperandWithVariable(I0, OI)) 1494 // We can't create a PHI from this GEP. 1495 return false; 1496 // Don't create indirect calls! The called value is the final operand. 1497 if ((isa<CallInst>(I0) || isa<InvokeInst>(I0)) && OI == OE - 1) { 1498 // FIXME: if the call was *already* indirect, we should do this. 1499 return false; 1500 } 1501 for (auto *I : Insts) 1502 PHIOperands[I].push_back(I->getOperand(OI)); 1503 } 1504 } 1505 return true; 1506 } 1507 1508 // Assuming canSinkLastInstruction(Blocks) has returned true, sink the last 1509 // instruction of every block in Blocks to their common successor, commoning 1510 // into one instruction. 1511 static bool sinkLastInstruction(ArrayRef<BasicBlock*> Blocks) { 1512 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0); 1513 1514 // canSinkLastInstruction returning true guarantees that every block has at 1515 // least one non-terminator instruction. 1516 SmallVector<Instruction*,4> Insts; 1517 for (auto *BB : Blocks) { 1518 Instruction *I = BB->getTerminator(); 1519 do { 1520 I = I->getPrevNode(); 1521 } while (isa<DbgInfoIntrinsic>(I) && I != &BB->front()); 1522 if (!isa<DbgInfoIntrinsic>(I)) 1523 Insts.push_back(I); 1524 } 1525 1526 // The only checking we need to do now is that all users of all instructions 1527 // are the same PHI node. canSinkLastInstruction should have checked this but 1528 // it is slightly over-aggressive - it gets confused by commutative instructions 1529 // so double-check it here. 1530 Instruction *I0 = Insts.front(); 1531 if (!isa<StoreInst>(I0)) { 1532 auto *PNUse = dyn_cast<PHINode>(*I0->user_begin()); 1533 if (!all_of(Insts, [&PNUse](const Instruction *I) -> bool { 1534 auto *U = cast<Instruction>(*I->user_begin()); 1535 return U == PNUse; 1536 })) 1537 return false; 1538 } 1539 1540 // We don't need to do any more checking here; canSinkLastInstruction should 1541 // have done it all for us. 1542 SmallVector<Value*, 4> NewOperands; 1543 for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O) { 1544 // This check is different to that in canSinkLastInstruction. There, we 1545 // cared about the global view once simplifycfg (and instcombine) have 1546 // completed - it takes into account PHIs that become trivially 1547 // simplifiable. However here we need a more local view; if an operand 1548 // differs we create a PHI and rely on instcombine to clean up the very 1549 // small mess we may make. 1550 bool NeedPHI = any_of(Insts, [&I0, O](const Instruction *I) { 1551 return I->getOperand(O) != I0->getOperand(O); 1552 }); 1553 if (!NeedPHI) { 1554 NewOperands.push_back(I0->getOperand(O)); 1555 continue; 1556 } 1557 1558 // Create a new PHI in the successor block and populate it. 1559 auto *Op = I0->getOperand(O); 1560 assert(!Op->getType()->isTokenTy() && "Can't PHI tokens!"); 1561 auto *PN = PHINode::Create(Op->getType(), Insts.size(), 1562 Op->getName() + ".sink", &BBEnd->front()); 1563 for (auto *I : Insts) 1564 PN->addIncoming(I->getOperand(O), I->getParent()); 1565 NewOperands.push_back(PN); 1566 } 1567 1568 // Arbitrarily use I0 as the new "common" instruction; remap its operands 1569 // and move it to the start of the successor block. 1570 for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O) 1571 I0->getOperandUse(O).set(NewOperands[O]); 1572 I0->moveBefore(&*BBEnd->getFirstInsertionPt()); 1573 1574 // Update metadata and IR flags, and merge debug locations. 1575 for (auto *I : Insts) 1576 if (I != I0) { 1577 // The debug location for the "common" instruction is the merged locations 1578 // of all the commoned instructions. We start with the original location 1579 // of the "common" instruction and iteratively merge each location in the 1580 // loop below. 1581 // This is an N-way merge, which will be inefficient if I0 is a CallInst. 1582 // However, as N-way merge for CallInst is rare, so we use simplified API 1583 // instead of using complex API for N-way merge. 1584 I0->applyMergedLocation(I0->getDebugLoc(), I->getDebugLoc()); 1585 combineMetadataForCSE(I0, I); 1586 I0->andIRFlags(I); 1587 } 1588 1589 if (!isa<StoreInst>(I0)) { 1590 // canSinkLastInstruction checked that all instructions were used by 1591 // one and only one PHI node. Find that now, RAUW it to our common 1592 // instruction and nuke it. 1593 assert(I0->hasOneUse()); 1594 auto *PN = cast<PHINode>(*I0->user_begin()); 1595 PN->replaceAllUsesWith(I0); 1596 PN->eraseFromParent(); 1597 } 1598 1599 // Finally nuke all instructions apart from the common instruction. 1600 for (auto *I : Insts) 1601 if (I != I0) 1602 I->eraseFromParent(); 1603 1604 return true; 1605 } 1606 1607 namespace { 1608 1609 // LockstepReverseIterator - Iterates through instructions 1610 // in a set of blocks in reverse order from the first non-terminator. 1611 // For example (assume all blocks have size n): 1612 // LockstepReverseIterator I([B1, B2, B3]); 1613 // *I-- = [B1[n], B2[n], B3[n]]; 1614 // *I-- = [B1[n-1], B2[n-1], B3[n-1]]; 1615 // *I-- = [B1[n-2], B2[n-2], B3[n-2]]; 1616 // ... 1617 class LockstepReverseIterator { 1618 ArrayRef<BasicBlock*> Blocks; 1619 SmallVector<Instruction*,4> Insts; 1620 bool Fail; 1621 1622 public: 1623 LockstepReverseIterator(ArrayRef<BasicBlock*> Blocks) : Blocks(Blocks) { 1624 reset(); 1625 } 1626 1627 void reset() { 1628 Fail = false; 1629 Insts.clear(); 1630 for (auto *BB : Blocks) { 1631 Instruction *Inst = BB->getTerminator(); 1632 for (Inst = Inst->getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);) 1633 Inst = Inst->getPrevNode(); 1634 if (!Inst) { 1635 // Block wasn't big enough. 1636 Fail = true; 1637 return; 1638 } 1639 Insts.push_back(Inst); 1640 } 1641 } 1642 1643 bool isValid() const { 1644 return !Fail; 1645 } 1646 1647 void operator--() { 1648 if (Fail) 1649 return; 1650 for (auto *&Inst : Insts) { 1651 for (Inst = Inst->getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);) 1652 Inst = Inst->getPrevNode(); 1653 // Already at beginning of block. 1654 if (!Inst) { 1655 Fail = true; 1656 return; 1657 } 1658 } 1659 } 1660 1661 ArrayRef<Instruction*> operator * () const { 1662 return Insts; 1663 } 1664 }; 1665 1666 } // end anonymous namespace 1667 1668 /// Check whether BB's predecessors end with unconditional branches. If it is 1669 /// true, sink any common code from the predecessors to BB. 1670 /// We also allow one predecessor to end with conditional branch (but no more 1671 /// than one). 1672 static bool SinkCommonCodeFromPredecessors(BasicBlock *BB) { 1673 // We support two situations: 1674 // (1) all incoming arcs are unconditional 1675 // (2) one incoming arc is conditional 1676 // 1677 // (2) is very common in switch defaults and 1678 // else-if patterns; 1679 // 1680 // if (a) f(1); 1681 // else if (b) f(2); 1682 // 1683 // produces: 1684 // 1685 // [if] 1686 // / \ 1687 // [f(1)] [if] 1688 // | | \ 1689 // | | | 1690 // | [f(2)]| 1691 // \ | / 1692 // [ end ] 1693 // 1694 // [end] has two unconditional predecessor arcs and one conditional. The 1695 // conditional refers to the implicit empty 'else' arc. This conditional 1696 // arc can also be caused by an empty default block in a switch. 1697 // 1698 // In this case, we attempt to sink code from all *unconditional* arcs. 1699 // If we can sink instructions from these arcs (determined during the scan 1700 // phase below) we insert a common successor for all unconditional arcs and 1701 // connect that to [end], to enable sinking: 1702 // 1703 // [if] 1704 // / \ 1705 // [x(1)] [if] 1706 // | | \ 1707 // | | \ 1708 // | [x(2)] | 1709 // \ / | 1710 // [sink.split] | 1711 // \ / 1712 // [ end ] 1713 // 1714 SmallVector<BasicBlock*,4> UnconditionalPreds; 1715 Instruction *Cond = nullptr; 1716 for (auto *B : predecessors(BB)) { 1717 auto *T = B->getTerminator(); 1718 if (isa<BranchInst>(T) && cast<BranchInst>(T)->isUnconditional()) 1719 UnconditionalPreds.push_back(B); 1720 else if ((isa<BranchInst>(T) || isa<SwitchInst>(T)) && !Cond) 1721 Cond = T; 1722 else 1723 return false; 1724 } 1725 if (UnconditionalPreds.size() < 2) 1726 return false; 1727 1728 bool Changed = false; 1729 // We take a two-step approach to tail sinking. First we scan from the end of 1730 // each block upwards in lockstep. If the n'th instruction from the end of each 1731 // block can be sunk, those instructions are added to ValuesToSink and we 1732 // carry on. If we can sink an instruction but need to PHI-merge some operands 1733 // (because they're not identical in each instruction) we add these to 1734 // PHIOperands. 1735 unsigned ScanIdx = 0; 1736 SmallPtrSet<Value*,4> InstructionsToSink; 1737 DenseMap<Instruction*, SmallVector<Value*,4>> PHIOperands; 1738 LockstepReverseIterator LRI(UnconditionalPreds); 1739 while (LRI.isValid() && 1740 canSinkInstructions(*LRI, PHIOperands)) { 1741 LLVM_DEBUG(dbgs() << "SINK: instruction can be sunk: " << *(*LRI)[0] 1742 << "\n"); 1743 InstructionsToSink.insert((*LRI).begin(), (*LRI).end()); 1744 ++ScanIdx; 1745 --LRI; 1746 } 1747 1748 auto ProfitableToSinkInstruction = [&](LockstepReverseIterator &LRI) { 1749 unsigned NumPHIdValues = 0; 1750 for (auto *I : *LRI) 1751 for (auto *V : PHIOperands[I]) 1752 if (InstructionsToSink.count(V) == 0) 1753 ++NumPHIdValues; 1754 LLVM_DEBUG(dbgs() << "SINK: #phid values: " << NumPHIdValues << "\n"); 1755 unsigned NumPHIInsts = NumPHIdValues / UnconditionalPreds.size(); 1756 if ((NumPHIdValues % UnconditionalPreds.size()) != 0) 1757 NumPHIInsts++; 1758 1759 return NumPHIInsts <= 1; 1760 }; 1761 1762 if (ScanIdx > 0 && Cond) { 1763 // Check if we would actually sink anything first! This mutates the CFG and 1764 // adds an extra block. The goal in doing this is to allow instructions that 1765 // couldn't be sunk before to be sunk - obviously, speculatable instructions 1766 // (such as trunc, add) can be sunk and predicated already. So we check that 1767 // we're going to sink at least one non-speculatable instruction. 1768 LRI.reset(); 1769 unsigned Idx = 0; 1770 bool Profitable = false; 1771 while (ProfitableToSinkInstruction(LRI) && Idx < ScanIdx) { 1772 if (!isSafeToSpeculativelyExecute((*LRI)[0])) { 1773 Profitable = true; 1774 break; 1775 } 1776 --LRI; 1777 ++Idx; 1778 } 1779 if (!Profitable) 1780 return false; 1781 1782 LLVM_DEBUG(dbgs() << "SINK: Splitting edge\n"); 1783 // We have a conditional edge and we're going to sink some instructions. 1784 // Insert a new block postdominating all blocks we're going to sink from. 1785 if (!SplitBlockPredecessors(BB, UnconditionalPreds, ".sink.split")) 1786 // Edges couldn't be split. 1787 return false; 1788 Changed = true; 1789 } 1790 1791 // Now that we've analyzed all potential sinking candidates, perform the 1792 // actual sink. We iteratively sink the last non-terminator of the source 1793 // blocks into their common successor unless doing so would require too 1794 // many PHI instructions to be generated (currently only one PHI is allowed 1795 // per sunk instruction). 1796 // 1797 // We can use InstructionsToSink to discount values needing PHI-merging that will 1798 // actually be sunk in a later iteration. This allows us to be more 1799 // aggressive in what we sink. This does allow a false positive where we 1800 // sink presuming a later value will also be sunk, but stop half way through 1801 // and never actually sink it which means we produce more PHIs than intended. 1802 // This is unlikely in practice though. 1803 for (unsigned SinkIdx = 0; SinkIdx != ScanIdx; ++SinkIdx) { 1804 LLVM_DEBUG(dbgs() << "SINK: Sink: " 1805 << *UnconditionalPreds[0]->getTerminator()->getPrevNode() 1806 << "\n"); 1807 1808 // Because we've sunk every instruction in turn, the current instruction to 1809 // sink is always at index 0. 1810 LRI.reset(); 1811 if (!ProfitableToSinkInstruction(LRI)) { 1812 // Too many PHIs would be created. 1813 LLVM_DEBUG( 1814 dbgs() << "SINK: stopping here, too many PHIs would be created!\n"); 1815 break; 1816 } 1817 1818 if (!sinkLastInstruction(UnconditionalPreds)) 1819 return Changed; 1820 NumSinkCommons++; 1821 Changed = true; 1822 } 1823 return Changed; 1824 } 1825 1826 /// Determine if we can hoist sink a sole store instruction out of a 1827 /// conditional block. 1828 /// 1829 /// We are looking for code like the following: 1830 /// BrBB: 1831 /// store i32 %add, i32* %arrayidx2 1832 /// ... // No other stores or function calls (we could be calling a memory 1833 /// ... // function). 1834 /// %cmp = icmp ult %x, %y 1835 /// br i1 %cmp, label %EndBB, label %ThenBB 1836 /// ThenBB: 1837 /// store i32 %add5, i32* %arrayidx2 1838 /// br label EndBB 1839 /// EndBB: 1840 /// ... 1841 /// We are going to transform this into: 1842 /// BrBB: 1843 /// store i32 %add, i32* %arrayidx2 1844 /// ... // 1845 /// %cmp = icmp ult %x, %y 1846 /// %add.add5 = select i1 %cmp, i32 %add, %add5 1847 /// store i32 %add.add5, i32* %arrayidx2 1848 /// ... 1849 /// 1850 /// \return The pointer to the value of the previous store if the store can be 1851 /// hoisted into the predecessor block. 0 otherwise. 1852 static Value *isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, 1853 BasicBlock *StoreBB, BasicBlock *EndBB) { 1854 StoreInst *StoreToHoist = dyn_cast<StoreInst>(I); 1855 if (!StoreToHoist) 1856 return nullptr; 1857 1858 // Volatile or atomic. 1859 if (!StoreToHoist->isSimple()) 1860 return nullptr; 1861 1862 Value *StorePtr = StoreToHoist->getPointerOperand(); 1863 1864 // Look for a store to the same pointer in BrBB. 1865 unsigned MaxNumInstToLookAt = 9; 1866 for (Instruction &CurI : reverse(BrBB->instructionsWithoutDebug())) { 1867 if (!MaxNumInstToLookAt) 1868 break; 1869 --MaxNumInstToLookAt; 1870 1871 // Could be calling an instruction that affects memory like free(). 1872 if (CurI.mayHaveSideEffects() && !isa<StoreInst>(CurI)) 1873 return nullptr; 1874 1875 if (auto *SI = dyn_cast<StoreInst>(&CurI)) { 1876 // Found the previous store make sure it stores to the same location. 1877 if (SI->getPointerOperand() == StorePtr) 1878 // Found the previous store, return its value operand. 1879 return SI->getValueOperand(); 1880 return nullptr; // Unknown store. 1881 } 1882 } 1883 1884 return nullptr; 1885 } 1886 1887 /// Speculate a conditional basic block flattening the CFG. 1888 /// 1889 /// Note that this is a very risky transform currently. Speculating 1890 /// instructions like this is most often not desirable. Instead, there is an MI 1891 /// pass which can do it with full awareness of the resource constraints. 1892 /// However, some cases are "obvious" and we should do directly. An example of 1893 /// this is speculating a single, reasonably cheap instruction. 1894 /// 1895 /// There is only one distinct advantage to flattening the CFG at the IR level: 1896 /// it makes very common but simplistic optimizations such as are common in 1897 /// instcombine and the DAG combiner more powerful by removing CFG edges and 1898 /// modeling their effects with easier to reason about SSA value graphs. 1899 /// 1900 /// 1901 /// An illustration of this transform is turning this IR: 1902 /// \code 1903 /// BB: 1904 /// %cmp = icmp ult %x, %y 1905 /// br i1 %cmp, label %EndBB, label %ThenBB 1906 /// ThenBB: 1907 /// %sub = sub %x, %y 1908 /// br label BB2 1909 /// EndBB: 1910 /// %phi = phi [ %sub, %ThenBB ], [ 0, %EndBB ] 1911 /// ... 1912 /// \endcode 1913 /// 1914 /// Into this IR: 1915 /// \code 1916 /// BB: 1917 /// %cmp = icmp ult %x, %y 1918 /// %sub = sub %x, %y 1919 /// %cond = select i1 %cmp, 0, %sub 1920 /// ... 1921 /// \endcode 1922 /// 1923 /// \returns true if the conditional block is removed. 1924 static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB, 1925 const TargetTransformInfo &TTI) { 1926 // Be conservative for now. FP select instruction can often be expensive. 1927 Value *BrCond = BI->getCondition(); 1928 if (isa<FCmpInst>(BrCond)) 1929 return false; 1930 1931 BasicBlock *BB = BI->getParent(); 1932 BasicBlock *EndBB = ThenBB->getTerminator()->getSuccessor(0); 1933 1934 // If ThenBB is actually on the false edge of the conditional branch, remember 1935 // to swap the select operands later. 1936 bool Invert = false; 1937 if (ThenBB != BI->getSuccessor(0)) { 1938 assert(ThenBB == BI->getSuccessor(1) && "No edge from 'if' block?"); 1939 Invert = true; 1940 } 1941 assert(EndBB == BI->getSuccessor(!Invert) && "No edge from to end block"); 1942 1943 // Keep a count of how many times instructions are used within CondBB when 1944 // they are candidates for sinking into CondBB. Specifically: 1945 // - They are defined in BB, and 1946 // - They have no side effects, and 1947 // - All of their uses are in CondBB. 1948 SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts; 1949 1950 SmallVector<Instruction *, 4> SpeculatedDbgIntrinsics; 1951 1952 unsigned SpeculationCost = 0; 1953 Value *SpeculatedStoreValue = nullptr; 1954 StoreInst *SpeculatedStore = nullptr; 1955 for (BasicBlock::iterator BBI = ThenBB->begin(), 1956 BBE = std::prev(ThenBB->end()); 1957 BBI != BBE; ++BBI) { 1958 Instruction *I = &*BBI; 1959 // Skip debug info. 1960 if (isa<DbgInfoIntrinsic>(I)) { 1961 SpeculatedDbgIntrinsics.push_back(I); 1962 continue; 1963 } 1964 1965 // Only speculatively execute a single instruction (not counting the 1966 // terminator) for now. 1967 ++SpeculationCost; 1968 if (SpeculationCost > 1) 1969 return false; 1970 1971 // Don't hoist the instruction if it's unsafe or expensive. 1972 if (!isSafeToSpeculativelyExecute(I) && 1973 !(HoistCondStores && (SpeculatedStoreValue = isSafeToSpeculateStore( 1974 I, BB, ThenBB, EndBB)))) 1975 return false; 1976 if (!SpeculatedStoreValue && 1977 ComputeSpeculationCost(I, TTI) > 1978 PHINodeFoldingThreshold * TargetTransformInfo::TCC_Basic) 1979 return false; 1980 1981 // Store the store speculation candidate. 1982 if (SpeculatedStoreValue) 1983 SpeculatedStore = cast<StoreInst>(I); 1984 1985 // Do not hoist the instruction if any of its operands are defined but not 1986 // used in BB. The transformation will prevent the operand from 1987 // being sunk into the use block. 1988 for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) { 1989 Instruction *OpI = dyn_cast<Instruction>(*i); 1990 if (!OpI || OpI->getParent() != BB || OpI->mayHaveSideEffects()) 1991 continue; // Not a candidate for sinking. 1992 1993 ++SinkCandidateUseCounts[OpI]; 1994 } 1995 } 1996 1997 // Consider any sink candidates which are only used in CondBB as costs for 1998 // speculation. Note, while we iterate over a DenseMap here, we are summing 1999 // and so iteration order isn't significant. 2000 for (SmallDenseMap<Instruction *, unsigned, 4>::iterator 2001 I = SinkCandidateUseCounts.begin(), 2002 E = SinkCandidateUseCounts.end(); 2003 I != E; ++I) 2004 if (I->first->getNumUses() == I->second) { 2005 ++SpeculationCost; 2006 if (SpeculationCost > 1) 2007 return false; 2008 } 2009 2010 // Check that the PHI nodes can be converted to selects. 2011 bool HaveRewritablePHIs = false; 2012 for (PHINode &PN : EndBB->phis()) { 2013 Value *OrigV = PN.getIncomingValueForBlock(BB); 2014 Value *ThenV = PN.getIncomingValueForBlock(ThenBB); 2015 2016 // FIXME: Try to remove some of the duplication with HoistThenElseCodeToIf. 2017 // Skip PHIs which are trivial. 2018 if (ThenV == OrigV) 2019 continue; 2020 2021 // Don't convert to selects if we could remove undefined behavior instead. 2022 if (passingValueIsAlwaysUndefined(OrigV, &PN) || 2023 passingValueIsAlwaysUndefined(ThenV, &PN)) 2024 return false; 2025 2026 HaveRewritablePHIs = true; 2027 ConstantExpr *OrigCE = dyn_cast<ConstantExpr>(OrigV); 2028 ConstantExpr *ThenCE = dyn_cast<ConstantExpr>(ThenV); 2029 if (!OrigCE && !ThenCE) 2030 continue; // Known safe and cheap. 2031 2032 if ((ThenCE && !isSafeToSpeculativelyExecute(ThenCE)) || 2033 (OrigCE && !isSafeToSpeculativelyExecute(OrigCE))) 2034 return false; 2035 unsigned OrigCost = OrigCE ? ComputeSpeculationCost(OrigCE, TTI) : 0; 2036 unsigned ThenCost = ThenCE ? ComputeSpeculationCost(ThenCE, TTI) : 0; 2037 unsigned MaxCost = 2038 2 * PHINodeFoldingThreshold * TargetTransformInfo::TCC_Basic; 2039 if (OrigCost + ThenCost > MaxCost) 2040 return false; 2041 2042 // Account for the cost of an unfolded ConstantExpr which could end up 2043 // getting expanded into Instructions. 2044 // FIXME: This doesn't account for how many operations are combined in the 2045 // constant expression. 2046 ++SpeculationCost; 2047 if (SpeculationCost > 1) 2048 return false; 2049 } 2050 2051 // If there are no PHIs to process, bail early. This helps ensure idempotence 2052 // as well. 2053 if (!HaveRewritablePHIs && !(HoistCondStores && SpeculatedStoreValue)) 2054 return false; 2055 2056 // If we get here, we can hoist the instruction and if-convert. 2057 LLVM_DEBUG(dbgs() << "SPECULATIVELY EXECUTING BB" << *ThenBB << "\n";); 2058 2059 // Insert a select of the value of the speculated store. 2060 if (SpeculatedStoreValue) { 2061 IRBuilder<NoFolder> Builder(BI); 2062 Value *TrueV = SpeculatedStore->getValueOperand(); 2063 Value *FalseV = SpeculatedStoreValue; 2064 if (Invert) 2065 std::swap(TrueV, FalseV); 2066 Value *S = Builder.CreateSelect( 2067 BrCond, TrueV, FalseV, "spec.store.select", BI); 2068 SpeculatedStore->setOperand(0, S); 2069 SpeculatedStore->applyMergedLocation(BI->getDebugLoc(), 2070 SpeculatedStore->getDebugLoc()); 2071 } 2072 2073 // Metadata can be dependent on the condition we are hoisting above. 2074 // Conservatively strip all metadata on the instruction. 2075 for (auto &I : *ThenBB) 2076 I.dropUnknownNonDebugMetadata(); 2077 2078 // Hoist the instructions. 2079 BB->getInstList().splice(BI->getIterator(), ThenBB->getInstList(), 2080 ThenBB->begin(), std::prev(ThenBB->end())); 2081 2082 // Insert selects and rewrite the PHI operands. 2083 IRBuilder<NoFolder> Builder(BI); 2084 for (PHINode &PN : EndBB->phis()) { 2085 unsigned OrigI = PN.getBasicBlockIndex(BB); 2086 unsigned ThenI = PN.getBasicBlockIndex(ThenBB); 2087 Value *OrigV = PN.getIncomingValue(OrigI); 2088 Value *ThenV = PN.getIncomingValue(ThenI); 2089 2090 // Skip PHIs which are trivial. 2091 if (OrigV == ThenV) 2092 continue; 2093 2094 // Create a select whose true value is the speculatively executed value and 2095 // false value is the preexisting value. Swap them if the branch 2096 // destinations were inverted. 2097 Value *TrueV = ThenV, *FalseV = OrigV; 2098 if (Invert) 2099 std::swap(TrueV, FalseV); 2100 Value *V = Builder.CreateSelect( 2101 BrCond, TrueV, FalseV, "spec.select", BI); 2102 PN.setIncomingValue(OrigI, V); 2103 PN.setIncomingValue(ThenI, V); 2104 } 2105 2106 // Remove speculated dbg intrinsics. 2107 // FIXME: Is it possible to do this in a more elegant way? Moving/merging the 2108 // dbg value for the different flows and inserting it after the select. 2109 for (Instruction *I : SpeculatedDbgIntrinsics) 2110 I->eraseFromParent(); 2111 2112 ++NumSpeculations; 2113 return true; 2114 } 2115 2116 /// Return true if we can thread a branch across this block. 2117 static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) { 2118 unsigned Size = 0; 2119 2120 for (Instruction &I : BB->instructionsWithoutDebug()) { 2121 if (Size > 10) 2122 return false; // Don't clone large BB's. 2123 ++Size; 2124 2125 // We can only support instructions that do not define values that are 2126 // live outside of the current basic block. 2127 for (User *U : I.users()) { 2128 Instruction *UI = cast<Instruction>(U); 2129 if (UI->getParent() != BB || isa<PHINode>(UI)) 2130 return false; 2131 } 2132 2133 // Looks ok, continue checking. 2134 } 2135 2136 return true; 2137 } 2138 2139 /// If we have a conditional branch on a PHI node value that is defined in the 2140 /// same block as the branch and if any PHI entries are constants, thread edges 2141 /// corresponding to that entry to be branches to their ultimate destination. 2142 static bool FoldCondBranchOnPHI(BranchInst *BI, const DataLayout &DL, 2143 AssumptionCache *AC) { 2144 BasicBlock *BB = BI->getParent(); 2145 PHINode *PN = dyn_cast<PHINode>(BI->getCondition()); 2146 // NOTE: we currently cannot transform this case if the PHI node is used 2147 // outside of the block. 2148 if (!PN || PN->getParent() != BB || !PN->hasOneUse()) 2149 return false; 2150 2151 // Degenerate case of a single entry PHI. 2152 if (PN->getNumIncomingValues() == 1) { 2153 FoldSingleEntryPHINodes(PN->getParent()); 2154 return true; 2155 } 2156 2157 // Now we know that this block has multiple preds and two succs. 2158 if (!BlockIsSimpleEnoughToThreadThrough(BB)) 2159 return false; 2160 2161 // Can't fold blocks that contain noduplicate or convergent calls. 2162 if (any_of(*BB, [](const Instruction &I) { 2163 const CallInst *CI = dyn_cast<CallInst>(&I); 2164 return CI && (CI->cannotDuplicate() || CI->isConvergent()); 2165 })) 2166 return false; 2167 2168 // Okay, this is a simple enough basic block. See if any phi values are 2169 // constants. 2170 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 2171 ConstantInt *CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i)); 2172 if (!CB || !CB->getType()->isIntegerTy(1)) 2173 continue; 2174 2175 // Okay, we now know that all edges from PredBB should be revectored to 2176 // branch to RealDest. 2177 BasicBlock *PredBB = PN->getIncomingBlock(i); 2178 BasicBlock *RealDest = BI->getSuccessor(!CB->getZExtValue()); 2179 2180 if (RealDest == BB) 2181 continue; // Skip self loops. 2182 // Skip if the predecessor's terminator is an indirect branch. 2183 if (isa<IndirectBrInst>(PredBB->getTerminator())) 2184 continue; 2185 2186 // The dest block might have PHI nodes, other predecessors and other 2187 // difficult cases. Instead of being smart about this, just insert a new 2188 // block that jumps to the destination block, effectively splitting 2189 // the edge we are about to create. 2190 BasicBlock *EdgeBB = 2191 BasicBlock::Create(BB->getContext(), RealDest->getName() + ".critedge", 2192 RealDest->getParent(), RealDest); 2193 BranchInst::Create(RealDest, EdgeBB); 2194 2195 // Update PHI nodes. 2196 AddPredecessorToBlock(RealDest, EdgeBB, BB); 2197 2198 // BB may have instructions that are being threaded over. Clone these 2199 // instructions into EdgeBB. We know that there will be no uses of the 2200 // cloned instructions outside of EdgeBB. 2201 BasicBlock::iterator InsertPt = EdgeBB->begin(); 2202 DenseMap<Value *, Value *> TranslateMap; // Track translated values. 2203 for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { 2204 if (PHINode *PN = dyn_cast<PHINode>(BBI)) { 2205 TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB); 2206 continue; 2207 } 2208 // Clone the instruction. 2209 Instruction *N = BBI->clone(); 2210 if (BBI->hasName()) 2211 N->setName(BBI->getName() + ".c"); 2212 2213 // Update operands due to translation. 2214 for (User::op_iterator i = N->op_begin(), e = N->op_end(); i != e; ++i) { 2215 DenseMap<Value *, Value *>::iterator PI = TranslateMap.find(*i); 2216 if (PI != TranslateMap.end()) 2217 *i = PI->second; 2218 } 2219 2220 // Check for trivial simplification. 2221 if (Value *V = SimplifyInstruction(N, {DL, nullptr, nullptr, AC})) { 2222 if (!BBI->use_empty()) 2223 TranslateMap[&*BBI] = V; 2224 if (!N->mayHaveSideEffects()) { 2225 N->deleteValue(); // Instruction folded away, don't need actual inst 2226 N = nullptr; 2227 } 2228 } else { 2229 if (!BBI->use_empty()) 2230 TranslateMap[&*BBI] = N; 2231 } 2232 // Insert the new instruction into its new home. 2233 if (N) 2234 EdgeBB->getInstList().insert(InsertPt, N); 2235 2236 // Register the new instruction with the assumption cache if necessary. 2237 if (auto *II = dyn_cast_or_null<IntrinsicInst>(N)) 2238 if (II->getIntrinsicID() == Intrinsic::assume) 2239 AC->registerAssumption(II); 2240 } 2241 2242 // Loop over all of the edges from PredBB to BB, changing them to branch 2243 // to EdgeBB instead. 2244 TerminatorInst *PredBBTI = PredBB->getTerminator(); 2245 for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i) 2246 if (PredBBTI->getSuccessor(i) == BB) { 2247 BB->removePredecessor(PredBB); 2248 PredBBTI->setSuccessor(i, EdgeBB); 2249 } 2250 2251 // Recurse, simplifying any other constants. 2252 return FoldCondBranchOnPHI(BI, DL, AC) | true; 2253 } 2254 2255 return false; 2256 } 2257 2258 /// Given a BB that starts with the specified two-entry PHI node, 2259 /// see if we can eliminate it. 2260 static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, 2261 const DataLayout &DL) { 2262 // Ok, this is a two entry PHI node. Check to see if this is a simple "if 2263 // statement", which has a very simple dominance structure. Basically, we 2264 // are trying to find the condition that is being branched on, which 2265 // subsequently causes this merge to happen. We really want control 2266 // dependence information for this check, but simplifycfg can't keep it up 2267 // to date, and this catches most of the cases we care about anyway. 2268 BasicBlock *BB = PN->getParent(); 2269 const Function *Fn = BB->getParent(); 2270 if (Fn && Fn->hasFnAttribute(Attribute::OptForFuzzing)) 2271 return false; 2272 2273 BasicBlock *IfTrue, *IfFalse; 2274 Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse); 2275 if (!IfCond || 2276 // Don't bother if the branch will be constant folded trivially. 2277 isa<ConstantInt>(IfCond)) 2278 return false; 2279 2280 // Okay, we found that we can merge this two-entry phi node into a select. 2281 // Doing so would require us to fold *all* two entry phi nodes in this block. 2282 // At some point this becomes non-profitable (particularly if the target 2283 // doesn't support cmov's). Only do this transformation if there are two or 2284 // fewer PHI nodes in this block. 2285 unsigned NumPhis = 0; 2286 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++NumPhis, ++I) 2287 if (NumPhis > 2) 2288 return false; 2289 2290 // Loop over the PHI's seeing if we can promote them all to select 2291 // instructions. While we are at it, keep track of the instructions 2292 // that need to be moved to the dominating block. 2293 SmallPtrSet<Instruction *, 4> AggressiveInsts; 2294 unsigned MaxCostVal0 = PHINodeFoldingThreshold, 2295 MaxCostVal1 = PHINodeFoldingThreshold; 2296 MaxCostVal0 *= TargetTransformInfo::TCC_Basic; 2297 MaxCostVal1 *= TargetTransformInfo::TCC_Basic; 2298 2299 for (BasicBlock::iterator II = BB->begin(); isa<PHINode>(II);) { 2300 PHINode *PN = cast<PHINode>(II++); 2301 if (Value *V = SimplifyInstruction(PN, {DL, PN})) { 2302 PN->replaceAllUsesWith(V); 2303 PN->eraseFromParent(); 2304 continue; 2305 } 2306 2307 if (!DominatesMergePoint(PN->getIncomingValue(0), BB, &AggressiveInsts, 2308 MaxCostVal0, TTI) || 2309 !DominatesMergePoint(PN->getIncomingValue(1), BB, &AggressiveInsts, 2310 MaxCostVal1, TTI)) 2311 return false; 2312 } 2313 2314 // If we folded the first phi, PN dangles at this point. Refresh it. If 2315 // we ran out of PHIs then we simplified them all. 2316 PN = dyn_cast<PHINode>(BB->begin()); 2317 if (!PN) 2318 return true; 2319 2320 // Don't fold i1 branches on PHIs which contain binary operators. These can 2321 // often be turned into switches and other things. 2322 if (PN->getType()->isIntegerTy(1) && 2323 (isa<BinaryOperator>(PN->getIncomingValue(0)) || 2324 isa<BinaryOperator>(PN->getIncomingValue(1)) || 2325 isa<BinaryOperator>(IfCond))) 2326 return false; 2327 2328 // If all PHI nodes are promotable, check to make sure that all instructions 2329 // in the predecessor blocks can be promoted as well. If not, we won't be able 2330 // to get rid of the control flow, so it's not worth promoting to select 2331 // instructions. 2332 BasicBlock *DomBlock = nullptr; 2333 BasicBlock *IfBlock1 = PN->getIncomingBlock(0); 2334 BasicBlock *IfBlock2 = PN->getIncomingBlock(1); 2335 if (cast<BranchInst>(IfBlock1->getTerminator())->isConditional()) { 2336 IfBlock1 = nullptr; 2337 } else { 2338 DomBlock = *pred_begin(IfBlock1); 2339 for (BasicBlock::iterator I = IfBlock1->begin(); !isa<TerminatorInst>(I); 2340 ++I) 2341 if (!AggressiveInsts.count(&*I) && !isa<DbgInfoIntrinsic>(I)) { 2342 // This is not an aggressive instruction that we can promote. 2343 // Because of this, we won't be able to get rid of the control flow, so 2344 // the xform is not worth it. 2345 return false; 2346 } 2347 } 2348 2349 if (cast<BranchInst>(IfBlock2->getTerminator())->isConditional()) { 2350 IfBlock2 = nullptr; 2351 } else { 2352 DomBlock = *pred_begin(IfBlock2); 2353 for (BasicBlock::iterator I = IfBlock2->begin(); !isa<TerminatorInst>(I); 2354 ++I) 2355 if (!AggressiveInsts.count(&*I) && !isa<DbgInfoIntrinsic>(I)) { 2356 // This is not an aggressive instruction that we can promote. 2357 // Because of this, we won't be able to get rid of the control flow, so 2358 // the xform is not worth it. 2359 return false; 2360 } 2361 } 2362 2363 LLVM_DEBUG(dbgs() << "FOUND IF CONDITION! " << *IfCond 2364 << " T: " << IfTrue->getName() 2365 << " F: " << IfFalse->getName() << "\n"); 2366 2367 // If we can still promote the PHI nodes after this gauntlet of tests, 2368 // do all of the PHI's now. 2369 Instruction *InsertPt = DomBlock->getTerminator(); 2370 IRBuilder<NoFolder> Builder(InsertPt); 2371 2372 // Move all 'aggressive' instructions, which are defined in the 2373 // conditional parts of the if's up to the dominating block. 2374 if (IfBlock1) { 2375 for (auto &I : *IfBlock1) 2376 I.dropUnknownNonDebugMetadata(); 2377 DomBlock->getInstList().splice(InsertPt->getIterator(), 2378 IfBlock1->getInstList(), IfBlock1->begin(), 2379 IfBlock1->getTerminator()->getIterator()); 2380 } 2381 if (IfBlock2) { 2382 for (auto &I : *IfBlock2) 2383 I.dropUnknownNonDebugMetadata(); 2384 DomBlock->getInstList().splice(InsertPt->getIterator(), 2385 IfBlock2->getInstList(), IfBlock2->begin(), 2386 IfBlock2->getTerminator()->getIterator()); 2387 } 2388 2389 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 2390 // Change the PHI node into a select instruction. 2391 Value *TrueVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); 2392 Value *FalseVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); 2393 2394 Value *Sel = Builder.CreateSelect(IfCond, TrueVal, FalseVal, "", InsertPt); 2395 PN->replaceAllUsesWith(Sel); 2396 Sel->takeName(PN); 2397 PN->eraseFromParent(); 2398 } 2399 2400 // At this point, IfBlock1 and IfBlock2 are both empty, so our if statement 2401 // has been flattened. Change DomBlock to jump directly to our new block to 2402 // avoid other simplifycfg's kicking in on the diamond. 2403 TerminatorInst *OldTI = DomBlock->getTerminator(); 2404 Builder.SetInsertPoint(OldTI); 2405 Builder.CreateBr(BB); 2406 OldTI->eraseFromParent(); 2407 return true; 2408 } 2409 2410 /// If we found a conditional branch that goes to two returning blocks, 2411 /// try to merge them together into one return, 2412 /// introducing a select if the return values disagree. 2413 static bool SimplifyCondBranchToTwoReturns(BranchInst *BI, 2414 IRBuilder<> &Builder) { 2415 assert(BI->isConditional() && "Must be a conditional branch"); 2416 BasicBlock *TrueSucc = BI->getSuccessor(0); 2417 BasicBlock *FalseSucc = BI->getSuccessor(1); 2418 ReturnInst *TrueRet = cast<ReturnInst>(TrueSucc->getTerminator()); 2419 ReturnInst *FalseRet = cast<ReturnInst>(FalseSucc->getTerminator()); 2420 2421 // Check to ensure both blocks are empty (just a return) or optionally empty 2422 // with PHI nodes. If there are other instructions, merging would cause extra 2423 // computation on one path or the other. 2424 if (!TrueSucc->getFirstNonPHIOrDbg()->isTerminator()) 2425 return false; 2426 if (!FalseSucc->getFirstNonPHIOrDbg()->isTerminator()) 2427 return false; 2428 2429 Builder.SetInsertPoint(BI); 2430 // Okay, we found a branch that is going to two return nodes. If 2431 // there is no return value for this function, just change the 2432 // branch into a return. 2433 if (FalseRet->getNumOperands() == 0) { 2434 TrueSucc->removePredecessor(BI->getParent()); 2435 FalseSucc->removePredecessor(BI->getParent()); 2436 Builder.CreateRetVoid(); 2437 EraseTerminatorInstAndDCECond(BI); 2438 return true; 2439 } 2440 2441 // Otherwise, figure out what the true and false return values are 2442 // so we can insert a new select instruction. 2443 Value *TrueValue = TrueRet->getReturnValue(); 2444 Value *FalseValue = FalseRet->getReturnValue(); 2445 2446 // Unwrap any PHI nodes in the return blocks. 2447 if (PHINode *TVPN = dyn_cast_or_null<PHINode>(TrueValue)) 2448 if (TVPN->getParent() == TrueSucc) 2449 TrueValue = TVPN->getIncomingValueForBlock(BI->getParent()); 2450 if (PHINode *FVPN = dyn_cast_or_null<PHINode>(FalseValue)) 2451 if (FVPN->getParent() == FalseSucc) 2452 FalseValue = FVPN->getIncomingValueForBlock(BI->getParent()); 2453 2454 // In order for this transformation to be safe, we must be able to 2455 // unconditionally execute both operands to the return. This is 2456 // normally the case, but we could have a potentially-trapping 2457 // constant expression that prevents this transformation from being 2458 // safe. 2459 if (ConstantExpr *TCV = dyn_cast_or_null<ConstantExpr>(TrueValue)) 2460 if (TCV->canTrap()) 2461 return false; 2462 if (ConstantExpr *FCV = dyn_cast_or_null<ConstantExpr>(FalseValue)) 2463 if (FCV->canTrap()) 2464 return false; 2465 2466 // Okay, we collected all the mapped values and checked them for sanity, and 2467 // defined to really do this transformation. First, update the CFG. 2468 TrueSucc->removePredecessor(BI->getParent()); 2469 FalseSucc->removePredecessor(BI->getParent()); 2470 2471 // Insert select instructions where needed. 2472 Value *BrCond = BI->getCondition(); 2473 if (TrueValue) { 2474 // Insert a select if the results differ. 2475 if (TrueValue == FalseValue || isa<UndefValue>(FalseValue)) { 2476 } else if (isa<UndefValue>(TrueValue)) { 2477 TrueValue = FalseValue; 2478 } else { 2479 TrueValue = 2480 Builder.CreateSelect(BrCond, TrueValue, FalseValue, "retval", BI); 2481 } 2482 } 2483 2484 Value *RI = 2485 !TrueValue ? Builder.CreateRetVoid() : Builder.CreateRet(TrueValue); 2486 2487 (void)RI; 2488 2489 LLVM_DEBUG(dbgs() << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:" 2490 << "\n " << *BI << "NewRet = " << *RI << "TRUEBLOCK: " 2491 << *TrueSucc << "FALSEBLOCK: " << *FalseSucc); 2492 2493 EraseTerminatorInstAndDCECond(BI); 2494 2495 return true; 2496 } 2497 2498 /// Return true if the given instruction is available 2499 /// in its predecessor block. If yes, the instruction will be removed. 2500 static bool tryCSEWithPredecessor(Instruction *Inst, BasicBlock *PB) { 2501 if (!isa<BinaryOperator>(Inst) && !isa<CmpInst>(Inst)) 2502 return false; 2503 for (Instruction &I : *PB) { 2504 Instruction *PBI = &I; 2505 // Check whether Inst and PBI generate the same value. 2506 if (Inst->isIdenticalTo(PBI)) { 2507 Inst->replaceAllUsesWith(PBI); 2508 Inst->eraseFromParent(); 2509 return true; 2510 } 2511 } 2512 return false; 2513 } 2514 2515 /// Return true if either PBI or BI has branch weight available, and store 2516 /// the weights in {Pred|Succ}{True|False}Weight. If one of PBI and BI does 2517 /// not have branch weight, use 1:1 as its weight. 2518 static bool extractPredSuccWeights(BranchInst *PBI, BranchInst *BI, 2519 uint64_t &PredTrueWeight, 2520 uint64_t &PredFalseWeight, 2521 uint64_t &SuccTrueWeight, 2522 uint64_t &SuccFalseWeight) { 2523 bool PredHasWeights = 2524 PBI->extractProfMetadata(PredTrueWeight, PredFalseWeight); 2525 bool SuccHasWeights = 2526 BI->extractProfMetadata(SuccTrueWeight, SuccFalseWeight); 2527 if (PredHasWeights || SuccHasWeights) { 2528 if (!PredHasWeights) 2529 PredTrueWeight = PredFalseWeight = 1; 2530 if (!SuccHasWeights) 2531 SuccTrueWeight = SuccFalseWeight = 1; 2532 return true; 2533 } else { 2534 return false; 2535 } 2536 } 2537 2538 /// If this basic block is simple enough, and if a predecessor branches to us 2539 /// and one of our successors, fold the block into the predecessor and use 2540 /// logical operations to pick the right destination. 2541 bool llvm::FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold) { 2542 BasicBlock *BB = BI->getParent(); 2543 2544 Instruction *Cond = nullptr; 2545 if (BI->isConditional()) 2546 Cond = dyn_cast<Instruction>(BI->getCondition()); 2547 else { 2548 // For unconditional branch, check for a simple CFG pattern, where 2549 // BB has a single predecessor and BB's successor is also its predecessor's 2550 // successor. If such pattern exists, check for CSE between BB and its 2551 // predecessor. 2552 if (BasicBlock *PB = BB->getSinglePredecessor()) 2553 if (BranchInst *PBI = dyn_cast<BranchInst>(PB->getTerminator())) 2554 if (PBI->isConditional() && 2555 (BI->getSuccessor(0) == PBI->getSuccessor(0) || 2556 BI->getSuccessor(0) == PBI->getSuccessor(1))) { 2557 for (auto I = BB->instructionsWithoutDebug().begin(), 2558 E = BB->instructionsWithoutDebug().end(); 2559 I != E;) { 2560 Instruction *Curr = &*I++; 2561 if (isa<CmpInst>(Curr)) { 2562 Cond = Curr; 2563 break; 2564 } 2565 // Quit if we can't remove this instruction. 2566 if (!tryCSEWithPredecessor(Curr, PB)) 2567 return false; 2568 } 2569 } 2570 2571 if (!Cond) 2572 return false; 2573 } 2574 2575 if (!Cond || (!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) || 2576 Cond->getParent() != BB || !Cond->hasOneUse()) 2577 return false; 2578 2579 // Make sure the instruction after the condition is the cond branch. 2580 BasicBlock::iterator CondIt = ++Cond->getIterator(); 2581 2582 // Ignore dbg intrinsics. 2583 while (isa<DbgInfoIntrinsic>(CondIt)) 2584 ++CondIt; 2585 2586 if (&*CondIt != BI) 2587 return false; 2588 2589 // Only allow this transformation if computing the condition doesn't involve 2590 // too many instructions and these involved instructions can be executed 2591 // unconditionally. We denote all involved instructions except the condition 2592 // as "bonus instructions", and only allow this transformation when the 2593 // number of the bonus instructions does not exceed a certain threshold. 2594 unsigned NumBonusInsts = 0; 2595 for (auto I = BB->begin(); Cond != &*I; ++I) { 2596 // Ignore dbg intrinsics. 2597 if (isa<DbgInfoIntrinsic>(I)) 2598 continue; 2599 if (!I->hasOneUse() || !isSafeToSpeculativelyExecute(&*I)) 2600 return false; 2601 // I has only one use and can be executed unconditionally. 2602 Instruction *User = dyn_cast<Instruction>(I->user_back()); 2603 if (User == nullptr || User->getParent() != BB) 2604 return false; 2605 // I is used in the same BB. Since BI uses Cond and doesn't have more slots 2606 // to use any other instruction, User must be an instruction between next(I) 2607 // and Cond. 2608 ++NumBonusInsts; 2609 // Early exits once we reach the limit. 2610 if (NumBonusInsts > BonusInstThreshold) 2611 return false; 2612 } 2613 2614 // Cond is known to be a compare or binary operator. Check to make sure that 2615 // neither operand is a potentially-trapping constant expression. 2616 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(0))) 2617 if (CE->canTrap()) 2618 return false; 2619 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(1))) 2620 if (CE->canTrap()) 2621 return false; 2622 2623 // Finally, don't infinitely unroll conditional loops. 2624 BasicBlock *TrueDest = BI->getSuccessor(0); 2625 BasicBlock *FalseDest = (BI->isConditional()) ? BI->getSuccessor(1) : nullptr; 2626 if (TrueDest == BB || FalseDest == BB) 2627 return false; 2628 2629 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 2630 BasicBlock *PredBlock = *PI; 2631 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator()); 2632 2633 // Check that we have two conditional branches. If there is a PHI node in 2634 // the common successor, verify that the same value flows in from both 2635 // blocks. 2636 SmallVector<PHINode *, 4> PHIs; 2637 if (!PBI || PBI->isUnconditional() || 2638 (BI->isConditional() && !SafeToMergeTerminators(BI, PBI)) || 2639 (!BI->isConditional() && 2640 !isProfitableToFoldUnconditional(BI, PBI, Cond, PHIs))) 2641 continue; 2642 2643 // Determine if the two branches share a common destination. 2644 Instruction::BinaryOps Opc = Instruction::BinaryOpsEnd; 2645 bool InvertPredCond = false; 2646 2647 if (BI->isConditional()) { 2648 if (PBI->getSuccessor(0) == TrueDest) { 2649 Opc = Instruction::Or; 2650 } else if (PBI->getSuccessor(1) == FalseDest) { 2651 Opc = Instruction::And; 2652 } else if (PBI->getSuccessor(0) == FalseDest) { 2653 Opc = Instruction::And; 2654 InvertPredCond = true; 2655 } else if (PBI->getSuccessor(1) == TrueDest) { 2656 Opc = Instruction::Or; 2657 InvertPredCond = true; 2658 } else { 2659 continue; 2660 } 2661 } else { 2662 if (PBI->getSuccessor(0) != TrueDest && PBI->getSuccessor(1) != TrueDest) 2663 continue; 2664 } 2665 2666 LLVM_DEBUG(dbgs() << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB); 2667 IRBuilder<> Builder(PBI); 2668 2669 // If we need to invert the condition in the pred block to match, do so now. 2670 if (InvertPredCond) { 2671 Value *NewCond = PBI->getCondition(); 2672 2673 if (NewCond->hasOneUse() && isa<CmpInst>(NewCond)) { 2674 CmpInst *CI = cast<CmpInst>(NewCond); 2675 CI->setPredicate(CI->getInversePredicate()); 2676 } else { 2677 NewCond = 2678 Builder.CreateNot(NewCond, PBI->getCondition()->getName() + ".not"); 2679 } 2680 2681 PBI->setCondition(NewCond); 2682 PBI->swapSuccessors(); 2683 } 2684 2685 // If we have bonus instructions, clone them into the predecessor block. 2686 // Note that there may be multiple predecessor blocks, so we cannot move 2687 // bonus instructions to a predecessor block. 2688 ValueToValueMapTy VMap; // maps original values to cloned values 2689 // We already make sure Cond is the last instruction before BI. Therefore, 2690 // all instructions before Cond other than DbgInfoIntrinsic are bonus 2691 // instructions. 2692 for (auto BonusInst = BB->begin(); Cond != &*BonusInst; ++BonusInst) { 2693 if (isa<DbgInfoIntrinsic>(BonusInst)) 2694 continue; 2695 Instruction *NewBonusInst = BonusInst->clone(); 2696 RemapInstruction(NewBonusInst, VMap, 2697 RF_NoModuleLevelChanges | RF_IgnoreMissingLocals); 2698 VMap[&*BonusInst] = NewBonusInst; 2699 2700 // If we moved a load, we cannot any longer claim any knowledge about 2701 // its potential value. The previous information might have been valid 2702 // only given the branch precondition. 2703 // For an analogous reason, we must also drop all the metadata whose 2704 // semantics we don't understand. 2705 NewBonusInst->dropUnknownNonDebugMetadata(); 2706 2707 PredBlock->getInstList().insert(PBI->getIterator(), NewBonusInst); 2708 NewBonusInst->takeName(&*BonusInst); 2709 BonusInst->setName(BonusInst->getName() + ".old"); 2710 } 2711 2712 // Clone Cond into the predecessor basic block, and or/and the 2713 // two conditions together. 2714 Instruction *New = Cond->clone(); 2715 RemapInstruction(New, VMap, 2716 RF_NoModuleLevelChanges | RF_IgnoreMissingLocals); 2717 PredBlock->getInstList().insert(PBI->getIterator(), New); 2718 New->takeName(Cond); 2719 Cond->setName(New->getName() + ".old"); 2720 2721 if (BI->isConditional()) { 2722 Instruction *NewCond = cast<Instruction>( 2723 Builder.CreateBinOp(Opc, PBI->getCondition(), New, "or.cond")); 2724 PBI->setCondition(NewCond); 2725 2726 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight; 2727 bool HasWeights = 2728 extractPredSuccWeights(PBI, BI, PredTrueWeight, PredFalseWeight, 2729 SuccTrueWeight, SuccFalseWeight); 2730 SmallVector<uint64_t, 8> NewWeights; 2731 2732 if (PBI->getSuccessor(0) == BB) { 2733 if (HasWeights) { 2734 // PBI: br i1 %x, BB, FalseDest 2735 // BI: br i1 %y, TrueDest, FalseDest 2736 // TrueWeight is TrueWeight for PBI * TrueWeight for BI. 2737 NewWeights.push_back(PredTrueWeight * SuccTrueWeight); 2738 // FalseWeight is FalseWeight for PBI * TotalWeight for BI + 2739 // TrueWeight for PBI * FalseWeight for BI. 2740 // We assume that total weights of a BranchInst can fit into 32 bits. 2741 // Therefore, we will not have overflow using 64-bit arithmetic. 2742 NewWeights.push_back(PredFalseWeight * 2743 (SuccFalseWeight + SuccTrueWeight) + 2744 PredTrueWeight * SuccFalseWeight); 2745 } 2746 AddPredecessorToBlock(TrueDest, PredBlock, BB); 2747 PBI->setSuccessor(0, TrueDest); 2748 } 2749 if (PBI->getSuccessor(1) == BB) { 2750 if (HasWeights) { 2751 // PBI: br i1 %x, TrueDest, BB 2752 // BI: br i1 %y, TrueDest, FalseDest 2753 // TrueWeight is TrueWeight for PBI * TotalWeight for BI + 2754 // FalseWeight for PBI * TrueWeight for BI. 2755 NewWeights.push_back(PredTrueWeight * 2756 (SuccFalseWeight + SuccTrueWeight) + 2757 PredFalseWeight * SuccTrueWeight); 2758 // FalseWeight is FalseWeight for PBI * FalseWeight for BI. 2759 NewWeights.push_back(PredFalseWeight * SuccFalseWeight); 2760 } 2761 AddPredecessorToBlock(FalseDest, PredBlock, BB); 2762 PBI->setSuccessor(1, FalseDest); 2763 } 2764 if (NewWeights.size() == 2) { 2765 // Halve the weights if any of them cannot fit in an uint32_t 2766 FitWeights(NewWeights); 2767 2768 SmallVector<uint32_t, 8> MDWeights(NewWeights.begin(), 2769 NewWeights.end()); 2770 setBranchWeights(PBI, MDWeights[0], MDWeights[1]); 2771 } else 2772 PBI->setMetadata(LLVMContext::MD_prof, nullptr); 2773 } else { 2774 // Update PHI nodes in the common successors. 2775 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) { 2776 ConstantInt *PBI_C = cast<ConstantInt>( 2777 PHIs[i]->getIncomingValueForBlock(PBI->getParent())); 2778 assert(PBI_C->getType()->isIntegerTy(1)); 2779 Instruction *MergedCond = nullptr; 2780 if (PBI->getSuccessor(0) == TrueDest) { 2781 // Create (PBI_Cond and PBI_C) or (!PBI_Cond and BI_Value) 2782 // PBI_C is true: PBI_Cond or (!PBI_Cond and BI_Value) 2783 // is false: !PBI_Cond and BI_Value 2784 Instruction *NotCond = cast<Instruction>( 2785 Builder.CreateNot(PBI->getCondition(), "not.cond")); 2786 MergedCond = cast<Instruction>( 2787 Builder.CreateBinOp(Instruction::And, NotCond, New, "and.cond")); 2788 if (PBI_C->isOne()) 2789 MergedCond = cast<Instruction>(Builder.CreateBinOp( 2790 Instruction::Or, PBI->getCondition(), MergedCond, "or.cond")); 2791 } else { 2792 // Create (PBI_Cond and BI_Value) or (!PBI_Cond and PBI_C) 2793 // PBI_C is true: (PBI_Cond and BI_Value) or (!PBI_Cond) 2794 // is false: PBI_Cond and BI_Value 2795 MergedCond = cast<Instruction>(Builder.CreateBinOp( 2796 Instruction::And, PBI->getCondition(), New, "and.cond")); 2797 if (PBI_C->isOne()) { 2798 Instruction *NotCond = cast<Instruction>( 2799 Builder.CreateNot(PBI->getCondition(), "not.cond")); 2800 MergedCond = cast<Instruction>(Builder.CreateBinOp( 2801 Instruction::Or, NotCond, MergedCond, "or.cond")); 2802 } 2803 } 2804 // Update PHI Node. 2805 PHIs[i]->setIncomingValue(PHIs[i]->getBasicBlockIndex(PBI->getParent()), 2806 MergedCond); 2807 } 2808 // Change PBI from Conditional to Unconditional. 2809 BranchInst *New_PBI = BranchInst::Create(TrueDest, PBI); 2810 EraseTerminatorInstAndDCECond(PBI); 2811 PBI = New_PBI; 2812 } 2813 2814 // If BI was a loop latch, it may have had associated loop metadata. 2815 // We need to copy it to the new latch, that is, PBI. 2816 if (MDNode *LoopMD = BI->getMetadata(LLVMContext::MD_loop)) 2817 PBI->setMetadata(LLVMContext::MD_loop, LoopMD); 2818 2819 // TODO: If BB is reachable from all paths through PredBlock, then we 2820 // could replace PBI's branch probabilities with BI's. 2821 2822 // Copy any debug value intrinsics into the end of PredBlock. 2823 for (Instruction &I : *BB) 2824 if (isa<DbgInfoIntrinsic>(I)) 2825 I.clone()->insertBefore(PBI); 2826 2827 return true; 2828 } 2829 return false; 2830 } 2831 2832 // If there is only one store in BB1 and BB2, return it, otherwise return 2833 // nullptr. 2834 static StoreInst *findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2) { 2835 StoreInst *S = nullptr; 2836 for (auto *BB : {BB1, BB2}) { 2837 if (!BB) 2838 continue; 2839 for (auto &I : *BB) 2840 if (auto *SI = dyn_cast<StoreInst>(&I)) { 2841 if (S) 2842 // Multiple stores seen. 2843 return nullptr; 2844 else 2845 S = SI; 2846 } 2847 } 2848 return S; 2849 } 2850 2851 static Value *ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, 2852 Value *AlternativeV = nullptr) { 2853 // PHI is going to be a PHI node that allows the value V that is defined in 2854 // BB to be referenced in BB's only successor. 2855 // 2856 // If AlternativeV is nullptr, the only value we care about in PHI is V. It 2857 // doesn't matter to us what the other operand is (it'll never get used). We 2858 // could just create a new PHI with an undef incoming value, but that could 2859 // increase register pressure if EarlyCSE/InstCombine can't fold it with some 2860 // other PHI. So here we directly look for some PHI in BB's successor with V 2861 // as an incoming operand. If we find one, we use it, else we create a new 2862 // one. 2863 // 2864 // If AlternativeV is not nullptr, we care about both incoming values in PHI. 2865 // PHI must be exactly: phi <ty> [ %BB, %V ], [ %OtherBB, %AlternativeV] 2866 // where OtherBB is the single other predecessor of BB's only successor. 2867 PHINode *PHI = nullptr; 2868 BasicBlock *Succ = BB->getSingleSuccessor(); 2869 2870 for (auto I = Succ->begin(); isa<PHINode>(I); ++I) 2871 if (cast<PHINode>(I)->getIncomingValueForBlock(BB) == V) { 2872 PHI = cast<PHINode>(I); 2873 if (!AlternativeV) 2874 break; 2875 2876 assert(pred_size(Succ) == 2); 2877 auto PredI = pred_begin(Succ); 2878 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI; 2879 if (PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV) 2880 break; 2881 PHI = nullptr; 2882 } 2883 if (PHI) 2884 return PHI; 2885 2886 // If V is not an instruction defined in BB, just return it. 2887 if (!AlternativeV && 2888 (!isa<Instruction>(V) || cast<Instruction>(V)->getParent() != BB)) 2889 return V; 2890 2891 PHI = PHINode::Create(V->getType(), 2, "simplifycfg.merge", &Succ->front()); 2892 PHI->addIncoming(V, BB); 2893 for (BasicBlock *PredBB : predecessors(Succ)) 2894 if (PredBB != BB) 2895 PHI->addIncoming( 2896 AlternativeV ? AlternativeV : UndefValue::get(V->getType()), PredBB); 2897 return PHI; 2898 } 2899 2900 static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, 2901 BasicBlock *QTB, BasicBlock *QFB, 2902 BasicBlock *PostBB, Value *Address, 2903 bool InvertPCond, bool InvertQCond, 2904 const DataLayout &DL) { 2905 auto IsaBitcastOfPointerType = [](const Instruction &I) { 2906 return Operator::getOpcode(&I) == Instruction::BitCast && 2907 I.getType()->isPointerTy(); 2908 }; 2909 2910 // If we're not in aggressive mode, we only optimize if we have some 2911 // confidence that by optimizing we'll allow P and/or Q to be if-converted. 2912 auto IsWorthwhile = [&](BasicBlock *BB) { 2913 if (!BB) 2914 return true; 2915 // Heuristic: if the block can be if-converted/phi-folded and the 2916 // instructions inside are all cheap (arithmetic/GEPs), it's worthwhile to 2917 // thread this store. 2918 unsigned N = 0; 2919 for (auto &I : BB->instructionsWithoutDebug()) { 2920 // Cheap instructions viable for folding. 2921 if (isa<BinaryOperator>(I) || isa<GetElementPtrInst>(I) || 2922 isa<StoreInst>(I)) 2923 ++N; 2924 // Free instructions. 2925 else if (isa<TerminatorInst>(I) || IsaBitcastOfPointerType(I)) 2926 continue; 2927 else 2928 return false; 2929 } 2930 // The store we want to merge is counted in N, so add 1 to make sure 2931 // we're counting the instructions that would be left. 2932 return N <= (PHINodeFoldingThreshold + 1); 2933 }; 2934 2935 if (!MergeCondStoresAggressively && 2936 (!IsWorthwhile(PTB) || !IsWorthwhile(PFB) || !IsWorthwhile(QTB) || 2937 !IsWorthwhile(QFB))) 2938 return false; 2939 2940 // For every pointer, there must be exactly two stores, one coming from 2941 // PTB or PFB, and the other from QTB or QFB. We don't support more than one 2942 // store (to any address) in PTB,PFB or QTB,QFB. 2943 // FIXME: We could relax this restriction with a bit more work and performance 2944 // testing. 2945 StoreInst *PStore = findUniqueStoreInBlocks(PTB, PFB); 2946 StoreInst *QStore = findUniqueStoreInBlocks(QTB, QFB); 2947 if (!PStore || !QStore) 2948 return false; 2949 2950 // Now check the stores are compatible. 2951 if (!QStore->isUnordered() || !PStore->isUnordered()) 2952 return false; 2953 2954 // Check that sinking the store won't cause program behavior changes. Sinking 2955 // the store out of the Q blocks won't change any behavior as we're sinking 2956 // from a block to its unconditional successor. But we're moving a store from 2957 // the P blocks down through the middle block (QBI) and past both QFB and QTB. 2958 // So we need to check that there are no aliasing loads or stores in 2959 // QBI, QTB and QFB. We also need to check there are no conflicting memory 2960 // operations between PStore and the end of its parent block. 2961 // 2962 // The ideal way to do this is to query AliasAnalysis, but we don't 2963 // preserve AA currently so that is dangerous. Be super safe and just 2964 // check there are no other memory operations at all. 2965 for (auto &I : *QFB->getSinglePredecessor()) 2966 if (I.mayReadOrWriteMemory()) 2967 return false; 2968 for (auto &I : *QFB) 2969 if (&I != QStore && I.mayReadOrWriteMemory()) 2970 return false; 2971 if (QTB) 2972 for (auto &I : *QTB) 2973 if (&I != QStore && I.mayReadOrWriteMemory()) 2974 return false; 2975 for (auto I = BasicBlock::iterator(PStore), E = PStore->getParent()->end(); 2976 I != E; ++I) 2977 if (&*I != PStore && I->mayReadOrWriteMemory()) 2978 return false; 2979 2980 // If PostBB has more than two predecessors, we need to split it so we can 2981 // sink the store. 2982 if (std::next(pred_begin(PostBB), 2) != pred_end(PostBB)) { 2983 // We know that QFB's only successor is PostBB. And QFB has a single 2984 // predecessor. If QTB exists, then its only successor is also PostBB. 2985 // If QTB does not exist, then QFB's only predecessor has a conditional 2986 // branch to QFB and PostBB. 2987 BasicBlock *TruePred = QTB ? QTB : QFB->getSinglePredecessor(); 2988 BasicBlock *NewBB = SplitBlockPredecessors(PostBB, { QFB, TruePred}, 2989 "condstore.split"); 2990 if (!NewBB) 2991 return false; 2992 PostBB = NewBB; 2993 } 2994 2995 // OK, we're going to sink the stores to PostBB. The store has to be 2996 // conditional though, so first create the predicate. 2997 Value *PCond = cast<BranchInst>(PFB->getSinglePredecessor()->getTerminator()) 2998 ->getCondition(); 2999 Value *QCond = cast<BranchInst>(QFB->getSinglePredecessor()->getTerminator()) 3000 ->getCondition(); 3001 3002 Value *PPHI = ensureValueAvailableInSuccessor(PStore->getValueOperand(), 3003 PStore->getParent()); 3004 Value *QPHI = ensureValueAvailableInSuccessor(QStore->getValueOperand(), 3005 QStore->getParent(), PPHI); 3006 3007 IRBuilder<> QB(&*PostBB->getFirstInsertionPt()); 3008 3009 Value *PPred = PStore->getParent() == PTB ? PCond : QB.CreateNot(PCond); 3010 Value *QPred = QStore->getParent() == QTB ? QCond : QB.CreateNot(QCond); 3011 3012 if (InvertPCond) 3013 PPred = QB.CreateNot(PPred); 3014 if (InvertQCond) 3015 QPred = QB.CreateNot(QPred); 3016 Value *CombinedPred = QB.CreateOr(PPred, QPred); 3017 3018 auto *T = 3019 SplitBlockAndInsertIfThen(CombinedPred, &*QB.GetInsertPoint(), false); 3020 QB.SetInsertPoint(T); 3021 StoreInst *SI = cast<StoreInst>(QB.CreateStore(QPHI, Address)); 3022 AAMDNodes AAMD; 3023 PStore->getAAMetadata(AAMD, /*Merge=*/false); 3024 PStore->getAAMetadata(AAMD, /*Merge=*/true); 3025 SI->setAAMetadata(AAMD); 3026 unsigned PAlignment = PStore->getAlignment(); 3027 unsigned QAlignment = QStore->getAlignment(); 3028 unsigned TypeAlignment = 3029 DL.getABITypeAlignment(SI->getValueOperand()->getType()); 3030 unsigned MinAlignment; 3031 unsigned MaxAlignment; 3032 std::tie(MinAlignment, MaxAlignment) = std::minmax(PAlignment, QAlignment); 3033 // Choose the minimum alignment. If we could prove both stores execute, we 3034 // could use biggest one. In this case, though, we only know that one of the 3035 // stores executes. And we don't know it's safe to take the alignment from a 3036 // store that doesn't execute. 3037 if (MinAlignment != 0) { 3038 // Choose the minimum of all non-zero alignments. 3039 SI->setAlignment(MinAlignment); 3040 } else if (MaxAlignment != 0) { 3041 // Choose the minimal alignment between the non-zero alignment and the ABI 3042 // default alignment for the type of the stored value. 3043 SI->setAlignment(std::min(MaxAlignment, TypeAlignment)); 3044 } else { 3045 // If both alignments are zero, use ABI default alignment for the type of 3046 // the stored value. 3047 SI->setAlignment(TypeAlignment); 3048 } 3049 3050 QStore->eraseFromParent(); 3051 PStore->eraseFromParent(); 3052 3053 return true; 3054 } 3055 3056 static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI, 3057 const DataLayout &DL) { 3058 // The intention here is to find diamonds or triangles (see below) where each 3059 // conditional block contains a store to the same address. Both of these 3060 // stores are conditional, so they can't be unconditionally sunk. But it may 3061 // be profitable to speculatively sink the stores into one merged store at the 3062 // end, and predicate the merged store on the union of the two conditions of 3063 // PBI and QBI. 3064 // 3065 // This can reduce the number of stores executed if both of the conditions are 3066 // true, and can allow the blocks to become small enough to be if-converted. 3067 // This optimization will also chain, so that ladders of test-and-set 3068 // sequences can be if-converted away. 3069 // 3070 // We only deal with simple diamonds or triangles: 3071 // 3072 // PBI or PBI or a combination of the two 3073 // / \ | \ 3074 // PTB PFB | PFB 3075 // \ / | / 3076 // QBI QBI 3077 // / \ | \ 3078 // QTB QFB | QFB 3079 // \ / | / 3080 // PostBB PostBB 3081 // 3082 // We model triangles as a type of diamond with a nullptr "true" block. 3083 // Triangles are canonicalized so that the fallthrough edge is represented by 3084 // a true condition, as in the diagram above. 3085 BasicBlock *PTB = PBI->getSuccessor(0); 3086 BasicBlock *PFB = PBI->getSuccessor(1); 3087 BasicBlock *QTB = QBI->getSuccessor(0); 3088 BasicBlock *QFB = QBI->getSuccessor(1); 3089 BasicBlock *PostBB = QFB->getSingleSuccessor(); 3090 3091 // Make sure we have a good guess for PostBB. If QTB's only successor is 3092 // QFB, then QFB is a better PostBB. 3093 if (QTB->getSingleSuccessor() == QFB) 3094 PostBB = QFB; 3095 3096 // If we couldn't find a good PostBB, stop. 3097 if (!PostBB) 3098 return false; 3099 3100 bool InvertPCond = false, InvertQCond = false; 3101 // Canonicalize fallthroughs to the true branches. 3102 if (PFB == QBI->getParent()) { 3103 std::swap(PFB, PTB); 3104 InvertPCond = true; 3105 } 3106 if (QFB == PostBB) { 3107 std::swap(QFB, QTB); 3108 InvertQCond = true; 3109 } 3110 3111 // From this point on we can assume PTB or QTB may be fallthroughs but PFB 3112 // and QFB may not. Model fallthroughs as a nullptr block. 3113 if (PTB == QBI->getParent()) 3114 PTB = nullptr; 3115 if (QTB == PostBB) 3116 QTB = nullptr; 3117 3118 // Legality bailouts. We must have at least the non-fallthrough blocks and 3119 // the post-dominating block, and the non-fallthroughs must only have one 3120 // predecessor. 3121 auto HasOnePredAndOneSucc = [](BasicBlock *BB, BasicBlock *P, BasicBlock *S) { 3122 return BB->getSinglePredecessor() == P && BB->getSingleSuccessor() == S; 3123 }; 3124 if (!HasOnePredAndOneSucc(PFB, PBI->getParent(), QBI->getParent()) || 3125 !HasOnePredAndOneSucc(QFB, QBI->getParent(), PostBB)) 3126 return false; 3127 if ((PTB && !HasOnePredAndOneSucc(PTB, PBI->getParent(), QBI->getParent())) || 3128 (QTB && !HasOnePredAndOneSucc(QTB, QBI->getParent(), PostBB))) 3129 return false; 3130 if (!QBI->getParent()->hasNUses(2)) 3131 return false; 3132 3133 // OK, this is a sequence of two diamonds or triangles. 3134 // Check if there are stores in PTB or PFB that are repeated in QTB or QFB. 3135 SmallPtrSet<Value *, 4> PStoreAddresses, QStoreAddresses; 3136 for (auto *BB : {PTB, PFB}) { 3137 if (!BB) 3138 continue; 3139 for (auto &I : *BB) 3140 if (StoreInst *SI = dyn_cast<StoreInst>(&I)) 3141 PStoreAddresses.insert(SI->getPointerOperand()); 3142 } 3143 for (auto *BB : {QTB, QFB}) { 3144 if (!BB) 3145 continue; 3146 for (auto &I : *BB) 3147 if (StoreInst *SI = dyn_cast<StoreInst>(&I)) 3148 QStoreAddresses.insert(SI->getPointerOperand()); 3149 } 3150 3151 set_intersect(PStoreAddresses, QStoreAddresses); 3152 // set_intersect mutates PStoreAddresses in place. Rename it here to make it 3153 // clear what it contains. 3154 auto &CommonAddresses = PStoreAddresses; 3155 3156 bool Changed = false; 3157 for (auto *Address : CommonAddresses) 3158 Changed |= mergeConditionalStoreToAddress( 3159 PTB, PFB, QTB, QFB, PostBB, Address, InvertPCond, InvertQCond, DL); 3160 return Changed; 3161 } 3162 3163 /// If we have a conditional branch as a predecessor of another block, 3164 /// this function tries to simplify it. We know 3165 /// that PBI and BI are both conditional branches, and BI is in one of the 3166 /// successor blocks of PBI - PBI branches to BI. 3167 static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, 3168 const DataLayout &DL) { 3169 assert(PBI->isConditional() && BI->isConditional()); 3170 BasicBlock *BB = BI->getParent(); 3171 3172 // If this block ends with a branch instruction, and if there is a 3173 // predecessor that ends on a branch of the same condition, make 3174 // this conditional branch redundant. 3175 if (PBI->getCondition() == BI->getCondition() && 3176 PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 3177 // Okay, the outcome of this conditional branch is statically 3178 // knowable. If this block had a single pred, handle specially. 3179 if (BB->getSinglePredecessor()) { 3180 // Turn this into a branch on constant. 3181 bool CondIsTrue = PBI->getSuccessor(0) == BB; 3182 BI->setCondition( 3183 ConstantInt::get(Type::getInt1Ty(BB->getContext()), CondIsTrue)); 3184 return true; // Nuke the branch on constant. 3185 } 3186 3187 // Otherwise, if there are multiple predecessors, insert a PHI that merges 3188 // in the constant and simplify the block result. Subsequent passes of 3189 // simplifycfg will thread the block. 3190 if (BlockIsSimpleEnoughToThreadThrough(BB)) { 3191 pred_iterator PB = pred_begin(BB), PE = pred_end(BB); 3192 PHINode *NewPN = PHINode::Create( 3193 Type::getInt1Ty(BB->getContext()), std::distance(PB, PE), 3194 BI->getCondition()->getName() + ".pr", &BB->front()); 3195 // Okay, we're going to insert the PHI node. Since PBI is not the only 3196 // predecessor, compute the PHI'd conditional value for all of the preds. 3197 // Any predecessor where the condition is not computable we keep symbolic. 3198 for (pred_iterator PI = PB; PI != PE; ++PI) { 3199 BasicBlock *P = *PI; 3200 if ((PBI = dyn_cast<BranchInst>(P->getTerminator())) && PBI != BI && 3201 PBI->isConditional() && PBI->getCondition() == BI->getCondition() && 3202 PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 3203 bool CondIsTrue = PBI->getSuccessor(0) == BB; 3204 NewPN->addIncoming( 3205 ConstantInt::get(Type::getInt1Ty(BB->getContext()), CondIsTrue), 3206 P); 3207 } else { 3208 NewPN->addIncoming(BI->getCondition(), P); 3209 } 3210 } 3211 3212 BI->setCondition(NewPN); 3213 return true; 3214 } 3215 } 3216 3217 if (auto *CE = dyn_cast<ConstantExpr>(BI->getCondition())) 3218 if (CE->canTrap()) 3219 return false; 3220 3221 // If both branches are conditional and both contain stores to the same 3222 // address, remove the stores from the conditionals and create a conditional 3223 // merged store at the end. 3224 if (MergeCondStores && mergeConditionalStores(PBI, BI, DL)) 3225 return true; 3226 3227 // If this is a conditional branch in an empty block, and if any 3228 // predecessors are a conditional branch to one of our destinations, 3229 // fold the conditions into logical ops and one cond br. 3230 3231 // Ignore dbg intrinsics. 3232 if (&*BB->instructionsWithoutDebug().begin() != BI) 3233 return false; 3234 3235 int PBIOp, BIOp; 3236 if (PBI->getSuccessor(0) == BI->getSuccessor(0)) { 3237 PBIOp = 0; 3238 BIOp = 0; 3239 } else if (PBI->getSuccessor(0) == BI->getSuccessor(1)) { 3240 PBIOp = 0; 3241 BIOp = 1; 3242 } else if (PBI->getSuccessor(1) == BI->getSuccessor(0)) { 3243 PBIOp = 1; 3244 BIOp = 0; 3245 } else if (PBI->getSuccessor(1) == BI->getSuccessor(1)) { 3246 PBIOp = 1; 3247 BIOp = 1; 3248 } else { 3249 return false; 3250 } 3251 3252 // Check to make sure that the other destination of this branch 3253 // isn't BB itself. If so, this is an infinite loop that will 3254 // keep getting unwound. 3255 if (PBI->getSuccessor(PBIOp) == BB) 3256 return false; 3257 3258 // Do not perform this transformation if it would require 3259 // insertion of a large number of select instructions. For targets 3260 // without predication/cmovs, this is a big pessimization. 3261 3262 // Also do not perform this transformation if any phi node in the common 3263 // destination block can trap when reached by BB or PBB (PR17073). In that 3264 // case, it would be unsafe to hoist the operation into a select instruction. 3265 3266 BasicBlock *CommonDest = PBI->getSuccessor(PBIOp); 3267 unsigned NumPhis = 0; 3268 for (BasicBlock::iterator II = CommonDest->begin(); isa<PHINode>(II); 3269 ++II, ++NumPhis) { 3270 if (NumPhis > 2) // Disable this xform. 3271 return false; 3272 3273 PHINode *PN = cast<PHINode>(II); 3274 Value *BIV = PN->getIncomingValueForBlock(BB); 3275 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(BIV)) 3276 if (CE->canTrap()) 3277 return false; 3278 3279 unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent()); 3280 Value *PBIV = PN->getIncomingValue(PBBIdx); 3281 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(PBIV)) 3282 if (CE->canTrap()) 3283 return false; 3284 } 3285 3286 // Finally, if everything is ok, fold the branches to logical ops. 3287 BasicBlock *OtherDest = BI->getSuccessor(BIOp ^ 1); 3288 3289 LLVM_DEBUG(dbgs() << "FOLDING BRs:" << *PBI->getParent() 3290 << "AND: " << *BI->getParent()); 3291 3292 // If OtherDest *is* BB, then BB is a basic block with a single conditional 3293 // branch in it, where one edge (OtherDest) goes back to itself but the other 3294 // exits. We don't *know* that the program avoids the infinite loop 3295 // (even though that seems likely). If we do this xform naively, we'll end up 3296 // recursively unpeeling the loop. Since we know that (after the xform is 3297 // done) that the block *is* infinite if reached, we just make it an obviously 3298 // infinite loop with no cond branch. 3299 if (OtherDest == BB) { 3300 // Insert it at the end of the function, because it's either code, 3301 // or it won't matter if it's hot. :) 3302 BasicBlock *InfLoopBlock = 3303 BasicBlock::Create(BB->getContext(), "infloop", BB->getParent()); 3304 BranchInst::Create(InfLoopBlock, InfLoopBlock); 3305 OtherDest = InfLoopBlock; 3306 } 3307 3308 LLVM_DEBUG(dbgs() << *PBI->getParent()->getParent()); 3309 3310 // BI may have other predecessors. Because of this, we leave 3311 // it alone, but modify PBI. 3312 3313 // Make sure we get to CommonDest on True&True directions. 3314 Value *PBICond = PBI->getCondition(); 3315 IRBuilder<NoFolder> Builder(PBI); 3316 if (PBIOp) 3317 PBICond = Builder.CreateNot(PBICond, PBICond->getName() + ".not"); 3318 3319 Value *BICond = BI->getCondition(); 3320 if (BIOp) 3321 BICond = Builder.CreateNot(BICond, BICond->getName() + ".not"); 3322 3323 // Merge the conditions. 3324 Value *Cond = Builder.CreateOr(PBICond, BICond, "brmerge"); 3325 3326 // Modify PBI to branch on the new condition to the new dests. 3327 PBI->setCondition(Cond); 3328 PBI->setSuccessor(0, CommonDest); 3329 PBI->setSuccessor(1, OtherDest); 3330 3331 // Update branch weight for PBI. 3332 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight; 3333 uint64_t PredCommon, PredOther, SuccCommon, SuccOther; 3334 bool HasWeights = 3335 extractPredSuccWeights(PBI, BI, PredTrueWeight, PredFalseWeight, 3336 SuccTrueWeight, SuccFalseWeight); 3337 if (HasWeights) { 3338 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight; 3339 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight; 3340 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight; 3341 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight; 3342 // The weight to CommonDest should be PredCommon * SuccTotal + 3343 // PredOther * SuccCommon. 3344 // The weight to OtherDest should be PredOther * SuccOther. 3345 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) + 3346 PredOther * SuccCommon, 3347 PredOther * SuccOther}; 3348 // Halve the weights if any of them cannot fit in an uint32_t 3349 FitWeights(NewWeights); 3350 3351 setBranchWeights(PBI, NewWeights[0], NewWeights[1]); 3352 } 3353 3354 // OtherDest may have phi nodes. If so, add an entry from PBI's 3355 // block that are identical to the entries for BI's block. 3356 AddPredecessorToBlock(OtherDest, PBI->getParent(), BB); 3357 3358 // We know that the CommonDest already had an edge from PBI to 3359 // it. If it has PHIs though, the PHIs may have different 3360 // entries for BB and PBI's BB. If so, insert a select to make 3361 // them agree. 3362 for (PHINode &PN : CommonDest->phis()) { 3363 Value *BIV = PN.getIncomingValueForBlock(BB); 3364 unsigned PBBIdx = PN.getBasicBlockIndex(PBI->getParent()); 3365 Value *PBIV = PN.getIncomingValue(PBBIdx); 3366 if (BIV != PBIV) { 3367 // Insert a select in PBI to pick the right value. 3368 SelectInst *NV = cast<SelectInst>( 3369 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->getName() + ".mux")); 3370 PN.setIncomingValue(PBBIdx, NV); 3371 // Although the select has the same condition as PBI, the original branch 3372 // weights for PBI do not apply to the new select because the select's 3373 // 'logical' edges are incoming edges of the phi that is eliminated, not 3374 // the outgoing edges of PBI. 3375 if (HasWeights) { 3376 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight; 3377 uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight; 3378 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight; 3379 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight; 3380 // The weight to PredCommonDest should be PredCommon * SuccTotal. 3381 // The weight to PredOtherDest should be PredOther * SuccCommon. 3382 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther), 3383 PredOther * SuccCommon}; 3384 3385 FitWeights(NewWeights); 3386 3387 setBranchWeights(NV, NewWeights[0], NewWeights[1]); 3388 } 3389 } 3390 } 3391 3392 LLVM_DEBUG(dbgs() << "INTO: " << *PBI->getParent()); 3393 LLVM_DEBUG(dbgs() << *PBI->getParent()->getParent()); 3394 3395 // This basic block is probably dead. We know it has at least 3396 // one fewer predecessor. 3397 return true; 3398 } 3399 3400 // Simplifies a terminator by replacing it with a branch to TrueBB if Cond is 3401 // true or to FalseBB if Cond is false. 3402 // Takes care of updating the successors and removing the old terminator. 3403 // Also makes sure not to introduce new successors by assuming that edges to 3404 // non-successor TrueBBs and FalseBBs aren't reachable. 3405 static bool SimplifyTerminatorOnSelect(TerminatorInst *OldTerm, Value *Cond, 3406 BasicBlock *TrueBB, BasicBlock *FalseBB, 3407 uint32_t TrueWeight, 3408 uint32_t FalseWeight) { 3409 // Remove any superfluous successor edges from the CFG. 3410 // First, figure out which successors to preserve. 3411 // If TrueBB and FalseBB are equal, only try to preserve one copy of that 3412 // successor. 3413 BasicBlock *KeepEdge1 = TrueBB; 3414 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : nullptr; 3415 3416 // Then remove the rest. 3417 for (BasicBlock *Succ : OldTerm->successors()) { 3418 // Make sure only to keep exactly one copy of each edge. 3419 if (Succ == KeepEdge1) 3420 KeepEdge1 = nullptr; 3421 else if (Succ == KeepEdge2) 3422 KeepEdge2 = nullptr; 3423 else 3424 Succ->removePredecessor(OldTerm->getParent(), 3425 /*DontDeleteUselessPHIs=*/true); 3426 } 3427 3428 IRBuilder<> Builder(OldTerm); 3429 Builder.SetCurrentDebugLocation(OldTerm->getDebugLoc()); 3430 3431 // Insert an appropriate new terminator. 3432 if (!KeepEdge1 && !KeepEdge2) { 3433 if (TrueBB == FalseBB) 3434 // We were only looking for one successor, and it was present. 3435 // Create an unconditional branch to it. 3436 Builder.CreateBr(TrueBB); 3437 else { 3438 // We found both of the successors we were looking for. 3439 // Create a conditional branch sharing the condition of the select. 3440 BranchInst *NewBI = Builder.CreateCondBr(Cond, TrueBB, FalseBB); 3441 if (TrueWeight != FalseWeight) 3442 setBranchWeights(NewBI, TrueWeight, FalseWeight); 3443 } 3444 } else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) { 3445 // Neither of the selected blocks were successors, so this 3446 // terminator must be unreachable. 3447 new UnreachableInst(OldTerm->getContext(), OldTerm); 3448 } else { 3449 // One of the selected values was a successor, but the other wasn't. 3450 // Insert an unconditional branch to the one that was found; 3451 // the edge to the one that wasn't must be unreachable. 3452 if (!KeepEdge1) 3453 // Only TrueBB was found. 3454 Builder.CreateBr(TrueBB); 3455 else 3456 // Only FalseBB was found. 3457 Builder.CreateBr(FalseBB); 3458 } 3459 3460 EraseTerminatorInstAndDCECond(OldTerm); 3461 return true; 3462 } 3463 3464 // Replaces 3465 // (switch (select cond, X, Y)) on constant X, Y 3466 // with a branch - conditional if X and Y lead to distinct BBs, 3467 // unconditional otherwise. 3468 static bool SimplifySwitchOnSelect(SwitchInst *SI, SelectInst *Select) { 3469 // Check for constant integer values in the select. 3470 ConstantInt *TrueVal = dyn_cast<ConstantInt>(Select->getTrueValue()); 3471 ConstantInt *FalseVal = dyn_cast<ConstantInt>(Select->getFalseValue()); 3472 if (!TrueVal || !FalseVal) 3473 return false; 3474 3475 // Find the relevant condition and destinations. 3476 Value *Condition = Select->getCondition(); 3477 BasicBlock *TrueBB = SI->findCaseValue(TrueVal)->getCaseSuccessor(); 3478 BasicBlock *FalseBB = SI->findCaseValue(FalseVal)->getCaseSuccessor(); 3479 3480 // Get weight for TrueBB and FalseBB. 3481 uint32_t TrueWeight = 0, FalseWeight = 0; 3482 SmallVector<uint64_t, 8> Weights; 3483 bool HasWeights = HasBranchWeights(SI); 3484 if (HasWeights) { 3485 GetBranchWeights(SI, Weights); 3486 if (Weights.size() == 1 + SI->getNumCases()) { 3487 TrueWeight = 3488 (uint32_t)Weights[SI->findCaseValue(TrueVal)->getSuccessorIndex()]; 3489 FalseWeight = 3490 (uint32_t)Weights[SI->findCaseValue(FalseVal)->getSuccessorIndex()]; 3491 } 3492 } 3493 3494 // Perform the actual simplification. 3495 return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight, 3496 FalseWeight); 3497 } 3498 3499 // Replaces 3500 // (indirectbr (select cond, blockaddress(@fn, BlockA), 3501 // blockaddress(@fn, BlockB))) 3502 // with 3503 // (br cond, BlockA, BlockB). 3504 static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) { 3505 // Check that both operands of the select are block addresses. 3506 BlockAddress *TBA = dyn_cast<BlockAddress>(SI->getTrueValue()); 3507 BlockAddress *FBA = dyn_cast<BlockAddress>(SI->getFalseValue()); 3508 if (!TBA || !FBA) 3509 return false; 3510 3511 // Extract the actual blocks. 3512 BasicBlock *TrueBB = TBA->getBasicBlock(); 3513 BasicBlock *FalseBB = FBA->getBasicBlock(); 3514 3515 // Perform the actual simplification. 3516 return SimplifyTerminatorOnSelect(IBI, SI->getCondition(), TrueBB, FalseBB, 0, 3517 0); 3518 } 3519 3520 /// This is called when we find an icmp instruction 3521 /// (a seteq/setne with a constant) as the only instruction in a 3522 /// block that ends with an uncond branch. We are looking for a very specific 3523 /// pattern that occurs when "A == 1 || A == 2 || A == 3" gets simplified. In 3524 /// this case, we merge the first two "or's of icmp" into a switch, but then the 3525 /// default value goes to an uncond block with a seteq in it, we get something 3526 /// like: 3527 /// 3528 /// switch i8 %A, label %DEFAULT [ i8 1, label %end i8 2, label %end ] 3529 /// DEFAULT: 3530 /// %tmp = icmp eq i8 %A, 92 3531 /// br label %end 3532 /// end: 3533 /// ... = phi i1 [ true, %entry ], [ %tmp, %DEFAULT ], [ true, %entry ] 3534 /// 3535 /// We prefer to split the edge to 'end' so that there is a true/false entry to 3536 /// the PHI, merging the third icmp into the switch. 3537 static bool tryToSimplifyUncondBranchWithICmpInIt( 3538 ICmpInst *ICI, IRBuilder<> &Builder, const DataLayout &DL, 3539 const TargetTransformInfo &TTI, const SimplifyCFGOptions &Options) { 3540 BasicBlock *BB = ICI->getParent(); 3541 3542 // If the block has any PHIs in it or the icmp has multiple uses, it is too 3543 // complex. 3544 if (isa<PHINode>(BB->begin()) || !ICI->hasOneUse()) 3545 return false; 3546 3547 Value *V = ICI->getOperand(0); 3548 ConstantInt *Cst = cast<ConstantInt>(ICI->getOperand(1)); 3549 3550 // The pattern we're looking for is where our only predecessor is a switch on 3551 // 'V' and this block is the default case for the switch. In this case we can 3552 // fold the compared value into the switch to simplify things. 3553 BasicBlock *Pred = BB->getSinglePredecessor(); 3554 if (!Pred || !isa<SwitchInst>(Pred->getTerminator())) 3555 return false; 3556 3557 SwitchInst *SI = cast<SwitchInst>(Pred->getTerminator()); 3558 if (SI->getCondition() != V) 3559 return false; 3560 3561 // If BB is reachable on a non-default case, then we simply know the value of 3562 // V in this block. Substitute it and constant fold the icmp instruction 3563 // away. 3564 if (SI->getDefaultDest() != BB) { 3565 ConstantInt *VVal = SI->findCaseDest(BB); 3566 assert(VVal && "Should have a unique destination value"); 3567 ICI->setOperand(0, VVal); 3568 3569 if (Value *V = SimplifyInstruction(ICI, {DL, ICI})) { 3570 ICI->replaceAllUsesWith(V); 3571 ICI->eraseFromParent(); 3572 } 3573 // BB is now empty, so it is likely to simplify away. 3574 return simplifyCFG(BB, TTI, Options) | true; 3575 } 3576 3577 // Ok, the block is reachable from the default dest. If the constant we're 3578 // comparing exists in one of the other edges, then we can constant fold ICI 3579 // and zap it. 3580 if (SI->findCaseValue(Cst) != SI->case_default()) { 3581 Value *V; 3582 if (ICI->getPredicate() == ICmpInst::ICMP_EQ) 3583 V = ConstantInt::getFalse(BB->getContext()); 3584 else 3585 V = ConstantInt::getTrue(BB->getContext()); 3586 3587 ICI->replaceAllUsesWith(V); 3588 ICI->eraseFromParent(); 3589 // BB is now empty, so it is likely to simplify away. 3590 return simplifyCFG(BB, TTI, Options) | true; 3591 } 3592 3593 // The use of the icmp has to be in the 'end' block, by the only PHI node in 3594 // the block. 3595 BasicBlock *SuccBlock = BB->getTerminator()->getSuccessor(0); 3596 PHINode *PHIUse = dyn_cast<PHINode>(ICI->user_back()); 3597 if (PHIUse == nullptr || PHIUse != &SuccBlock->front() || 3598 isa<PHINode>(++BasicBlock::iterator(PHIUse))) 3599 return false; 3600 3601 // If the icmp is a SETEQ, then the default dest gets false, the new edge gets 3602 // true in the PHI. 3603 Constant *DefaultCst = ConstantInt::getTrue(BB->getContext()); 3604 Constant *NewCst = ConstantInt::getFalse(BB->getContext()); 3605 3606 if (ICI->getPredicate() == ICmpInst::ICMP_EQ) 3607 std::swap(DefaultCst, NewCst); 3608 3609 // Replace ICI (which is used by the PHI for the default value) with true or 3610 // false depending on if it is EQ or NE. 3611 ICI->replaceAllUsesWith(DefaultCst); 3612 ICI->eraseFromParent(); 3613 3614 // Okay, the switch goes to this block on a default value. Add an edge from 3615 // the switch to the merge point on the compared value. 3616 BasicBlock *NewBB = 3617 BasicBlock::Create(BB->getContext(), "switch.edge", BB->getParent(), BB); 3618 SmallVector<uint64_t, 8> Weights; 3619 bool HasWeights = HasBranchWeights(SI); 3620 if (HasWeights) { 3621 GetBranchWeights(SI, Weights); 3622 if (Weights.size() == 1 + SI->getNumCases()) { 3623 // Split weight for default case to case for "Cst". 3624 Weights[0] = (Weights[0] + 1) >> 1; 3625 Weights.push_back(Weights[0]); 3626 3627 SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end()); 3628 setBranchWeights(SI, MDWeights); 3629 } 3630 } 3631 SI->addCase(Cst, NewBB); 3632 3633 // NewBB branches to the phi block, add the uncond branch and the phi entry. 3634 Builder.SetInsertPoint(NewBB); 3635 Builder.SetCurrentDebugLocation(SI->getDebugLoc()); 3636 Builder.CreateBr(SuccBlock); 3637 PHIUse->addIncoming(NewCst, NewBB); 3638 return true; 3639 } 3640 3641 /// The specified branch is a conditional branch. 3642 /// Check to see if it is branching on an or/and chain of icmp instructions, and 3643 /// fold it into a switch instruction if so. 3644 static bool SimplifyBranchOnICmpChain(BranchInst *BI, IRBuilder<> &Builder, 3645 const DataLayout &DL) { 3646 Instruction *Cond = dyn_cast<Instruction>(BI->getCondition()); 3647 if (!Cond) 3648 return false; 3649 3650 // Change br (X == 0 | X == 1), T, F into a switch instruction. 3651 // If this is a bunch of seteq's or'd together, or if it's a bunch of 3652 // 'setne's and'ed together, collect them. 3653 3654 // Try to gather values from a chain of and/or to be turned into a switch 3655 ConstantComparesGatherer ConstantCompare(Cond, DL); 3656 // Unpack the result 3657 SmallVectorImpl<ConstantInt *> &Values = ConstantCompare.Vals; 3658 Value *CompVal = ConstantCompare.CompValue; 3659 unsigned UsedICmps = ConstantCompare.UsedICmps; 3660 Value *ExtraCase = ConstantCompare.Extra; 3661 3662 // If we didn't have a multiply compared value, fail. 3663 if (!CompVal) 3664 return false; 3665 3666 // Avoid turning single icmps into a switch. 3667 if (UsedICmps <= 1) 3668 return false; 3669 3670 bool TrueWhenEqual = (Cond->getOpcode() == Instruction::Or); 3671 3672 // There might be duplicate constants in the list, which the switch 3673 // instruction can't handle, remove them now. 3674 array_pod_sort(Values.begin(), Values.end(), ConstantIntSortPredicate); 3675 Values.erase(std::unique(Values.begin(), Values.end()), Values.end()); 3676 3677 // If Extra was used, we require at least two switch values to do the 3678 // transformation. A switch with one value is just a conditional branch. 3679 if (ExtraCase && Values.size() < 2) 3680 return false; 3681 3682 // TODO: Preserve branch weight metadata, similarly to how 3683 // FoldValueComparisonIntoPredecessors preserves it. 3684 3685 // Figure out which block is which destination. 3686 BasicBlock *DefaultBB = BI->getSuccessor(1); 3687 BasicBlock *EdgeBB = BI->getSuccessor(0); 3688 if (!TrueWhenEqual) 3689 std::swap(DefaultBB, EdgeBB); 3690 3691 BasicBlock *BB = BI->getParent(); 3692 3693 LLVM_DEBUG(dbgs() << "Converting 'icmp' chain with " << Values.size() 3694 << " cases into SWITCH. BB is:\n" 3695 << *BB); 3696 3697 // If there are any extra values that couldn't be folded into the switch 3698 // then we evaluate them with an explicit branch first. Split the block 3699 // right before the condbr to handle it. 3700 if (ExtraCase) { 3701 BasicBlock *NewBB = 3702 BB->splitBasicBlock(BI->getIterator(), "switch.early.test"); 3703 // Remove the uncond branch added to the old block. 3704 TerminatorInst *OldTI = BB->getTerminator(); 3705 Builder.SetInsertPoint(OldTI); 3706 3707 if (TrueWhenEqual) 3708 Builder.CreateCondBr(ExtraCase, EdgeBB, NewBB); 3709 else 3710 Builder.CreateCondBr(ExtraCase, NewBB, EdgeBB); 3711 3712 OldTI->eraseFromParent(); 3713 3714 // If there are PHI nodes in EdgeBB, then we need to add a new entry to them 3715 // for the edge we just added. 3716 AddPredecessorToBlock(EdgeBB, BB, NewBB); 3717 3718 LLVM_DEBUG(dbgs() << " ** 'icmp' chain unhandled condition: " << *ExtraCase 3719 << "\nEXTRABB = " << *BB); 3720 BB = NewBB; 3721 } 3722 3723 Builder.SetInsertPoint(BI); 3724 // Convert pointer to int before we switch. 3725 if (CompVal->getType()->isPointerTy()) { 3726 CompVal = Builder.CreatePtrToInt( 3727 CompVal, DL.getIntPtrType(CompVal->getType()), "magicptr"); 3728 } 3729 3730 // Create the new switch instruction now. 3731 SwitchInst *New = Builder.CreateSwitch(CompVal, DefaultBB, Values.size()); 3732 3733 // Add all of the 'cases' to the switch instruction. 3734 for (unsigned i = 0, e = Values.size(); i != e; ++i) 3735 New->addCase(Values[i], EdgeBB); 3736 3737 // We added edges from PI to the EdgeBB. As such, if there were any 3738 // PHI nodes in EdgeBB, they need entries to be added corresponding to 3739 // the number of edges added. 3740 for (BasicBlock::iterator BBI = EdgeBB->begin(); isa<PHINode>(BBI); ++BBI) { 3741 PHINode *PN = cast<PHINode>(BBI); 3742 Value *InVal = PN->getIncomingValueForBlock(BB); 3743 for (unsigned i = 0, e = Values.size() - 1; i != e; ++i) 3744 PN->addIncoming(InVal, BB); 3745 } 3746 3747 // Erase the old branch instruction. 3748 EraseTerminatorInstAndDCECond(BI); 3749 3750 LLVM_DEBUG(dbgs() << " ** 'icmp' chain result is:\n" << *BB << '\n'); 3751 return true; 3752 } 3753 3754 bool SimplifyCFGOpt::SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder) { 3755 if (isa<PHINode>(RI->getValue())) 3756 return SimplifyCommonResume(RI); 3757 else if (isa<LandingPadInst>(RI->getParent()->getFirstNonPHI()) && 3758 RI->getValue() == RI->getParent()->getFirstNonPHI()) 3759 // The resume must unwind the exception that caused control to branch here. 3760 return SimplifySingleResume(RI); 3761 3762 return false; 3763 } 3764 3765 // Simplify resume that is shared by several landing pads (phi of landing pad). 3766 bool SimplifyCFGOpt::SimplifyCommonResume(ResumeInst *RI) { 3767 BasicBlock *BB = RI->getParent(); 3768 3769 // Check that there are no other instructions except for debug intrinsics 3770 // between the phi of landing pads (RI->getValue()) and resume instruction. 3771 BasicBlock::iterator I = cast<Instruction>(RI->getValue())->getIterator(), 3772 E = RI->getIterator(); 3773 while (++I != E) 3774 if (!isa<DbgInfoIntrinsic>(I)) 3775 return false; 3776 3777 SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks; 3778 auto *PhiLPInst = cast<PHINode>(RI->getValue()); 3779 3780 // Check incoming blocks to see if any of them are trivial. 3781 for (unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End; 3782 Idx++) { 3783 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx); 3784 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx); 3785 3786 // If the block has other successors, we can not delete it because 3787 // it has other dependents. 3788 if (IncomingBB->getUniqueSuccessor() != BB) 3789 continue; 3790 3791 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI()); 3792 // Not the landing pad that caused the control to branch here. 3793 if (IncomingValue != LandingPad) 3794 continue; 3795 3796 bool isTrivial = true; 3797 3798 I = IncomingBB->getFirstNonPHI()->getIterator(); 3799 E = IncomingBB->getTerminator()->getIterator(); 3800 while (++I != E) 3801 if (!isa<DbgInfoIntrinsic>(I)) { 3802 isTrivial = false; 3803 break; 3804 } 3805 3806 if (isTrivial) 3807 TrivialUnwindBlocks.insert(IncomingBB); 3808 } 3809 3810 // If no trivial unwind blocks, don't do any simplifications. 3811 if (TrivialUnwindBlocks.empty()) 3812 return false; 3813 3814 // Turn all invokes that unwind here into calls. 3815 for (auto *TrivialBB : TrivialUnwindBlocks) { 3816 // Blocks that will be simplified should be removed from the phi node. 3817 // Note there could be multiple edges to the resume block, and we need 3818 // to remove them all. 3819 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1) 3820 BB->removePredecessor(TrivialBB, true); 3821 3822 for (pred_iterator PI = pred_begin(TrivialBB), PE = pred_end(TrivialBB); 3823 PI != PE;) { 3824 BasicBlock *Pred = *PI++; 3825 removeUnwindEdge(Pred); 3826 } 3827 3828 // In each SimplifyCFG run, only the current processed block can be erased. 3829 // Otherwise, it will break the iteration of SimplifyCFG pass. So instead 3830 // of erasing TrivialBB, we only remove the branch to the common resume 3831 // block so that we can later erase the resume block since it has no 3832 // predecessors. 3833 TrivialBB->getTerminator()->eraseFromParent(); 3834 new UnreachableInst(RI->getContext(), TrivialBB); 3835 } 3836 3837 // Delete the resume block if all its predecessors have been removed. 3838 if (pred_empty(BB)) 3839 BB->eraseFromParent(); 3840 3841 return !TrivialUnwindBlocks.empty(); 3842 } 3843 3844 // Simplify resume that is only used by a single (non-phi) landing pad. 3845 bool SimplifyCFGOpt::SimplifySingleResume(ResumeInst *RI) { 3846 BasicBlock *BB = RI->getParent(); 3847 LandingPadInst *LPInst = dyn_cast<LandingPadInst>(BB->getFirstNonPHI()); 3848 assert(RI->getValue() == LPInst && 3849 "Resume must unwind the exception that caused control to here"); 3850 3851 // Check that there are no other instructions except for debug intrinsics. 3852 BasicBlock::iterator I = LPInst->getIterator(), E = RI->getIterator(); 3853 while (++I != E) 3854 if (!isa<DbgInfoIntrinsic>(I)) 3855 return false; 3856 3857 // Turn all invokes that unwind here into calls and delete the basic block. 3858 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;) { 3859 BasicBlock *Pred = *PI++; 3860 removeUnwindEdge(Pred); 3861 } 3862 3863 // The landingpad is now unreachable. Zap it. 3864 BB->eraseFromParent(); 3865 if (LoopHeaders) 3866 LoopHeaders->erase(BB); 3867 return true; 3868 } 3869 3870 static bool removeEmptyCleanup(CleanupReturnInst *RI) { 3871 // If this is a trivial cleanup pad that executes no instructions, it can be 3872 // eliminated. If the cleanup pad continues to the caller, any predecessor 3873 // that is an EH pad will be updated to continue to the caller and any 3874 // predecessor that terminates with an invoke instruction will have its invoke 3875 // instruction converted to a call instruction. If the cleanup pad being 3876 // simplified does not continue to the caller, each predecessor will be 3877 // updated to continue to the unwind destination of the cleanup pad being 3878 // simplified. 3879 BasicBlock *BB = RI->getParent(); 3880 CleanupPadInst *CPInst = RI->getCleanupPad(); 3881 if (CPInst->getParent() != BB) 3882 // This isn't an empty cleanup. 3883 return false; 3884 3885 // We cannot kill the pad if it has multiple uses. This typically arises 3886 // from unreachable basic blocks. 3887 if (!CPInst->hasOneUse()) 3888 return false; 3889 3890 // Check that there are no other instructions except for benign intrinsics. 3891 BasicBlock::iterator I = CPInst->getIterator(), E = RI->getIterator(); 3892 while (++I != E) { 3893 auto *II = dyn_cast<IntrinsicInst>(I); 3894 if (!II) 3895 return false; 3896 3897 Intrinsic::ID IntrinsicID = II->getIntrinsicID(); 3898 switch (IntrinsicID) { 3899 case Intrinsic::dbg_declare: 3900 case Intrinsic::dbg_value: 3901 case Intrinsic::dbg_label: 3902 case Intrinsic::lifetime_end: 3903 break; 3904 default: 3905 return false; 3906 } 3907 } 3908 3909 // If the cleanup return we are simplifying unwinds to the caller, this will 3910 // set UnwindDest to nullptr. 3911 BasicBlock *UnwindDest = RI->getUnwindDest(); 3912 Instruction *DestEHPad = UnwindDest ? UnwindDest->getFirstNonPHI() : nullptr; 3913 3914 // We're about to remove BB from the control flow. Before we do, sink any 3915 // PHINodes into the unwind destination. Doing this before changing the 3916 // control flow avoids some potentially slow checks, since we can currently 3917 // be certain that UnwindDest and BB have no common predecessors (since they 3918 // are both EH pads). 3919 if (UnwindDest) { 3920 // First, go through the PHI nodes in UnwindDest and update any nodes that 3921 // reference the block we are removing 3922 for (BasicBlock::iterator I = UnwindDest->begin(), 3923 IE = DestEHPad->getIterator(); 3924 I != IE; ++I) { 3925 PHINode *DestPN = cast<PHINode>(I); 3926 3927 int Idx = DestPN->getBasicBlockIndex(BB); 3928 // Since BB unwinds to UnwindDest, it has to be in the PHI node. 3929 assert(Idx != -1); 3930 // This PHI node has an incoming value that corresponds to a control 3931 // path through the cleanup pad we are removing. If the incoming 3932 // value is in the cleanup pad, it must be a PHINode (because we 3933 // verified above that the block is otherwise empty). Otherwise, the 3934 // value is either a constant or a value that dominates the cleanup 3935 // pad being removed. 3936 // 3937 // Because BB and UnwindDest are both EH pads, all of their 3938 // predecessors must unwind to these blocks, and since no instruction 3939 // can have multiple unwind destinations, there will be no overlap in 3940 // incoming blocks between SrcPN and DestPN. 3941 Value *SrcVal = DestPN->getIncomingValue(Idx); 3942 PHINode *SrcPN = dyn_cast<PHINode>(SrcVal); 3943 3944 // Remove the entry for the block we are deleting. 3945 DestPN->removeIncomingValue(Idx, false); 3946 3947 if (SrcPN && SrcPN->getParent() == BB) { 3948 // If the incoming value was a PHI node in the cleanup pad we are 3949 // removing, we need to merge that PHI node's incoming values into 3950 // DestPN. 3951 for (unsigned SrcIdx = 0, SrcE = SrcPN->getNumIncomingValues(); 3952 SrcIdx != SrcE; ++SrcIdx) { 3953 DestPN->addIncoming(SrcPN->getIncomingValue(SrcIdx), 3954 SrcPN->getIncomingBlock(SrcIdx)); 3955 } 3956 } else { 3957 // Otherwise, the incoming value came from above BB and 3958 // so we can just reuse it. We must associate all of BB's 3959 // predecessors with this value. 3960 for (auto *pred : predecessors(BB)) { 3961 DestPN->addIncoming(SrcVal, pred); 3962 } 3963 } 3964 } 3965 3966 // Sink any remaining PHI nodes directly into UnwindDest. 3967 Instruction *InsertPt = DestEHPad; 3968 for (BasicBlock::iterator I = BB->begin(), 3969 IE = BB->getFirstNonPHI()->getIterator(); 3970 I != IE;) { 3971 // The iterator must be incremented here because the instructions are 3972 // being moved to another block. 3973 PHINode *PN = cast<PHINode>(I++); 3974 if (PN->use_empty()) 3975 // If the PHI node has no uses, just leave it. It will be erased 3976 // when we erase BB below. 3977 continue; 3978 3979 // Otherwise, sink this PHI node into UnwindDest. 3980 // Any predecessors to UnwindDest which are not already represented 3981 // must be back edges which inherit the value from the path through 3982 // BB. In this case, the PHI value must reference itself. 3983 for (auto *pred : predecessors(UnwindDest)) 3984 if (pred != BB) 3985 PN->addIncoming(PN, pred); 3986 PN->moveBefore(InsertPt); 3987 } 3988 } 3989 3990 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;) { 3991 // The iterator must be updated here because we are removing this pred. 3992 BasicBlock *PredBB = *PI++; 3993 if (UnwindDest == nullptr) { 3994 removeUnwindEdge(PredBB); 3995 } else { 3996 TerminatorInst *TI = PredBB->getTerminator(); 3997 TI->replaceUsesOfWith(BB, UnwindDest); 3998 } 3999 } 4000 4001 // The cleanup pad is now unreachable. Zap it. 4002 BB->eraseFromParent(); 4003 return true; 4004 } 4005 4006 // Try to merge two cleanuppads together. 4007 static bool mergeCleanupPad(CleanupReturnInst *RI) { 4008 // Skip any cleanuprets which unwind to caller, there is nothing to merge 4009 // with. 4010 BasicBlock *UnwindDest = RI->getUnwindDest(); 4011 if (!UnwindDest) 4012 return false; 4013 4014 // This cleanupret isn't the only predecessor of this cleanuppad, it wouldn't 4015 // be safe to merge without code duplication. 4016 if (UnwindDest->getSinglePredecessor() != RI->getParent()) 4017 return false; 4018 4019 // Verify that our cleanuppad's unwind destination is another cleanuppad. 4020 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->front()); 4021 if (!SuccessorCleanupPad) 4022 return false; 4023 4024 CleanupPadInst *PredecessorCleanupPad = RI->getCleanupPad(); 4025 // Replace any uses of the successor cleanupad with the predecessor pad 4026 // The only cleanuppad uses should be this cleanupret, it's cleanupret and 4027 // funclet bundle operands. 4028 SuccessorCleanupPad->replaceAllUsesWith(PredecessorCleanupPad); 4029 // Remove the old cleanuppad. 4030 SuccessorCleanupPad->eraseFromParent(); 4031 // Now, we simply replace the cleanupret with a branch to the unwind 4032 // destination. 4033 BranchInst::Create(UnwindDest, RI->getParent()); 4034 RI->eraseFromParent(); 4035 4036 return true; 4037 } 4038 4039 bool SimplifyCFGOpt::SimplifyCleanupReturn(CleanupReturnInst *RI) { 4040 // It is possible to transiantly have an undef cleanuppad operand because we 4041 // have deleted some, but not all, dead blocks. 4042 // Eventually, this block will be deleted. 4043 if (isa<UndefValue>(RI->getOperand(0))) 4044 return false; 4045 4046 if (mergeCleanupPad(RI)) 4047 return true; 4048 4049 if (removeEmptyCleanup(RI)) 4050 return true; 4051 4052 return false; 4053 } 4054 4055 bool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder) { 4056 BasicBlock *BB = RI->getParent(); 4057 if (!BB->getFirstNonPHIOrDbg()->isTerminator()) 4058 return false; 4059 4060 // Find predecessors that end with branches. 4061 SmallVector<BasicBlock *, 8> UncondBranchPreds; 4062 SmallVector<BranchInst *, 8> CondBranchPreds; 4063 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 4064 BasicBlock *P = *PI; 4065 TerminatorInst *PTI = P->getTerminator(); 4066 if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) { 4067 if (BI->isUnconditional()) 4068 UncondBranchPreds.push_back(P); 4069 else 4070 CondBranchPreds.push_back(BI); 4071 } 4072 } 4073 4074 // If we found some, do the transformation! 4075 if (!UncondBranchPreds.empty() && DupRet) { 4076 while (!UncondBranchPreds.empty()) { 4077 BasicBlock *Pred = UncondBranchPreds.pop_back_val(); 4078 LLVM_DEBUG(dbgs() << "FOLDING: " << *BB 4079 << "INTO UNCOND BRANCH PRED: " << *Pred); 4080 (void)FoldReturnIntoUncondBranch(RI, BB, Pred); 4081 } 4082 4083 // If we eliminated all predecessors of the block, delete the block now. 4084 if (pred_empty(BB)) { 4085 // We know there are no successors, so just nuke the block. 4086 BB->eraseFromParent(); 4087 if (LoopHeaders) 4088 LoopHeaders->erase(BB); 4089 } 4090 4091 return true; 4092 } 4093 4094 // Check out all of the conditional branches going to this return 4095 // instruction. If any of them just select between returns, change the 4096 // branch itself into a select/return pair. 4097 while (!CondBranchPreds.empty()) { 4098 BranchInst *BI = CondBranchPreds.pop_back_val(); 4099 4100 // Check to see if the non-BB successor is also a return block. 4101 if (isa<ReturnInst>(BI->getSuccessor(0)->getTerminator()) && 4102 isa<ReturnInst>(BI->getSuccessor(1)->getTerminator()) && 4103 SimplifyCondBranchToTwoReturns(BI, Builder)) 4104 return true; 4105 } 4106 return false; 4107 } 4108 4109 bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) { 4110 BasicBlock *BB = UI->getParent(); 4111 4112 bool Changed = false; 4113 4114 // If there are any instructions immediately before the unreachable that can 4115 // be removed, do so. 4116 while (UI->getIterator() != BB->begin()) { 4117 BasicBlock::iterator BBI = UI->getIterator(); 4118 --BBI; 4119 // Do not delete instructions that can have side effects which might cause 4120 // the unreachable to not be reachable; specifically, calls and volatile 4121 // operations may have this effect. 4122 if (isa<CallInst>(BBI) && !isa<DbgInfoIntrinsic>(BBI)) 4123 break; 4124 4125 if (BBI->mayHaveSideEffects()) { 4126 if (auto *SI = dyn_cast<StoreInst>(BBI)) { 4127 if (SI->isVolatile()) 4128 break; 4129 } else if (auto *LI = dyn_cast<LoadInst>(BBI)) { 4130 if (LI->isVolatile()) 4131 break; 4132 } else if (auto *RMWI = dyn_cast<AtomicRMWInst>(BBI)) { 4133 if (RMWI->isVolatile()) 4134 break; 4135 } else if (auto *CXI = dyn_cast<AtomicCmpXchgInst>(BBI)) { 4136 if (CXI->isVolatile()) 4137 break; 4138 } else if (isa<CatchPadInst>(BBI)) { 4139 // A catchpad may invoke exception object constructors and such, which 4140 // in some languages can be arbitrary code, so be conservative by 4141 // default. 4142 // For CoreCLR, it just involves a type test, so can be removed. 4143 if (classifyEHPersonality(BB->getParent()->getPersonalityFn()) != 4144 EHPersonality::CoreCLR) 4145 break; 4146 } else if (!isa<FenceInst>(BBI) && !isa<VAArgInst>(BBI) && 4147 !isa<LandingPadInst>(BBI)) { 4148 break; 4149 } 4150 // Note that deleting LandingPad's here is in fact okay, although it 4151 // involves a bit of subtle reasoning. If this inst is a LandingPad, 4152 // all the predecessors of this block will be the unwind edges of Invokes, 4153 // and we can therefore guarantee this block will be erased. 4154 } 4155 4156 // Delete this instruction (any uses are guaranteed to be dead) 4157 if (!BBI->use_empty()) 4158 BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); 4159 BBI->eraseFromParent(); 4160 Changed = true; 4161 } 4162 4163 // If the unreachable instruction is the first in the block, take a gander 4164 // at all of the predecessors of this instruction, and simplify them. 4165 if (&BB->front() != UI) 4166 return Changed; 4167 4168 SmallVector<BasicBlock *, 8> Preds(pred_begin(BB), pred_end(BB)); 4169 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 4170 TerminatorInst *TI = Preds[i]->getTerminator(); 4171 IRBuilder<> Builder(TI); 4172 if (auto *BI = dyn_cast<BranchInst>(TI)) { 4173 if (BI->isUnconditional()) { 4174 if (BI->getSuccessor(0) == BB) { 4175 new UnreachableInst(TI->getContext(), TI); 4176 TI->eraseFromParent(); 4177 Changed = true; 4178 } 4179 } else { 4180 if (BI->getSuccessor(0) == BB) { 4181 Builder.CreateBr(BI->getSuccessor(1)); 4182 EraseTerminatorInstAndDCECond(BI); 4183 } else if (BI->getSuccessor(1) == BB) { 4184 Builder.CreateBr(BI->getSuccessor(0)); 4185 EraseTerminatorInstAndDCECond(BI); 4186 Changed = true; 4187 } 4188 } 4189 } else if (auto *SI = dyn_cast<SwitchInst>(TI)) { 4190 for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) { 4191 if (i->getCaseSuccessor() != BB) { 4192 ++i; 4193 continue; 4194 } 4195 BB->removePredecessor(SI->getParent()); 4196 i = SI->removeCase(i); 4197 e = SI->case_end(); 4198 Changed = true; 4199 } 4200 } else if (auto *II = dyn_cast<InvokeInst>(TI)) { 4201 if (II->getUnwindDest() == BB) { 4202 removeUnwindEdge(TI->getParent()); 4203 Changed = true; 4204 } 4205 } else if (auto *CSI = dyn_cast<CatchSwitchInst>(TI)) { 4206 if (CSI->getUnwindDest() == BB) { 4207 removeUnwindEdge(TI->getParent()); 4208 Changed = true; 4209 continue; 4210 } 4211 4212 for (CatchSwitchInst::handler_iterator I = CSI->handler_begin(), 4213 E = CSI->handler_end(); 4214 I != E; ++I) { 4215 if (*I == BB) { 4216 CSI->removeHandler(I); 4217 --I; 4218 --E; 4219 Changed = true; 4220 } 4221 } 4222 if (CSI->getNumHandlers() == 0) { 4223 BasicBlock *CatchSwitchBB = CSI->getParent(); 4224 if (CSI->hasUnwindDest()) { 4225 // Redirect preds to the unwind dest 4226 CatchSwitchBB->replaceAllUsesWith(CSI->getUnwindDest()); 4227 } else { 4228 // Rewrite all preds to unwind to caller (or from invoke to call). 4229 SmallVector<BasicBlock *, 8> EHPreds(predecessors(CatchSwitchBB)); 4230 for (BasicBlock *EHPred : EHPreds) 4231 removeUnwindEdge(EHPred); 4232 } 4233 // The catchswitch is no longer reachable. 4234 new UnreachableInst(CSI->getContext(), CSI); 4235 CSI->eraseFromParent(); 4236 Changed = true; 4237 } 4238 } else if (isa<CleanupReturnInst>(TI)) { 4239 new UnreachableInst(TI->getContext(), TI); 4240 TI->eraseFromParent(); 4241 Changed = true; 4242 } 4243 } 4244 4245 // If this block is now dead, remove it. 4246 if (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()) { 4247 // We know there are no successors, so just nuke the block. 4248 BB->eraseFromParent(); 4249 if (LoopHeaders) 4250 LoopHeaders->erase(BB); 4251 return true; 4252 } 4253 4254 return Changed; 4255 } 4256 4257 static bool CasesAreContiguous(SmallVectorImpl<ConstantInt *> &Cases) { 4258 assert(Cases.size() >= 1); 4259 4260 array_pod_sort(Cases.begin(), Cases.end(), ConstantIntSortPredicate); 4261 for (size_t I = 1, E = Cases.size(); I != E; ++I) { 4262 if (Cases[I - 1]->getValue() != Cases[I]->getValue() + 1) 4263 return false; 4264 } 4265 return true; 4266 } 4267 4268 /// Turn a switch with two reachable destinations into an integer range 4269 /// comparison and branch. 4270 static bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder) { 4271 assert(SI->getNumCases() > 1 && "Degenerate switch?"); 4272 4273 bool HasDefault = 4274 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()); 4275 4276 // Partition the cases into two sets with different destinations. 4277 BasicBlock *DestA = HasDefault ? SI->getDefaultDest() : nullptr; 4278 BasicBlock *DestB = nullptr; 4279 SmallVector<ConstantInt *, 16> CasesA; 4280 SmallVector<ConstantInt *, 16> CasesB; 4281 4282 for (auto Case : SI->cases()) { 4283 BasicBlock *Dest = Case.getCaseSuccessor(); 4284 if (!DestA) 4285 DestA = Dest; 4286 if (Dest == DestA) { 4287 CasesA.push_back(Case.getCaseValue()); 4288 continue; 4289 } 4290 if (!DestB) 4291 DestB = Dest; 4292 if (Dest == DestB) { 4293 CasesB.push_back(Case.getCaseValue()); 4294 continue; 4295 } 4296 return false; // More than two destinations. 4297 } 4298 4299 assert(DestA && DestB && 4300 "Single-destination switch should have been folded."); 4301 assert(DestA != DestB); 4302 assert(DestB != SI->getDefaultDest()); 4303 assert(!CasesB.empty() && "There must be non-default cases."); 4304 assert(!CasesA.empty() || HasDefault); 4305 4306 // Figure out if one of the sets of cases form a contiguous range. 4307 SmallVectorImpl<ConstantInt *> *ContiguousCases = nullptr; 4308 BasicBlock *ContiguousDest = nullptr; 4309 BasicBlock *OtherDest = nullptr; 4310 if (!CasesA.empty() && CasesAreContiguous(CasesA)) { 4311 ContiguousCases = &CasesA; 4312 ContiguousDest = DestA; 4313 OtherDest = DestB; 4314 } else if (CasesAreContiguous(CasesB)) { 4315 ContiguousCases = &CasesB; 4316 ContiguousDest = DestB; 4317 OtherDest = DestA; 4318 } else 4319 return false; 4320 4321 // Start building the compare and branch. 4322 4323 Constant *Offset = ConstantExpr::getNeg(ContiguousCases->back()); 4324 Constant *NumCases = 4325 ConstantInt::get(Offset->getType(), ContiguousCases->size()); 4326 4327 Value *Sub = SI->getCondition(); 4328 if (!Offset->isNullValue()) 4329 Sub = Builder.CreateAdd(Sub, Offset, Sub->getName() + ".off"); 4330 4331 Value *Cmp; 4332 // If NumCases overflowed, then all possible values jump to the successor. 4333 if (NumCases->isNullValue() && !ContiguousCases->empty()) 4334 Cmp = ConstantInt::getTrue(SI->getContext()); 4335 else 4336 Cmp = Builder.CreateICmpULT(Sub, NumCases, "switch"); 4337 BranchInst *NewBI = Builder.CreateCondBr(Cmp, ContiguousDest, OtherDest); 4338 4339 // Update weight for the newly-created conditional branch. 4340 if (HasBranchWeights(SI)) { 4341 SmallVector<uint64_t, 8> Weights; 4342 GetBranchWeights(SI, Weights); 4343 if (Weights.size() == 1 + SI->getNumCases()) { 4344 uint64_t TrueWeight = 0; 4345 uint64_t FalseWeight = 0; 4346 for (size_t I = 0, E = Weights.size(); I != E; ++I) { 4347 if (SI->getSuccessor(I) == ContiguousDest) 4348 TrueWeight += Weights[I]; 4349 else 4350 FalseWeight += Weights[I]; 4351 } 4352 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) { 4353 TrueWeight /= 2; 4354 FalseWeight /= 2; 4355 } 4356 setBranchWeights(NewBI, TrueWeight, FalseWeight); 4357 } 4358 } 4359 4360 // Prune obsolete incoming values off the successors' PHI nodes. 4361 for (auto BBI = ContiguousDest->begin(); isa<PHINode>(BBI); ++BBI) { 4362 unsigned PreviousEdges = ContiguousCases->size(); 4363 if (ContiguousDest == SI->getDefaultDest()) 4364 ++PreviousEdges; 4365 for (unsigned I = 0, E = PreviousEdges - 1; I != E; ++I) 4366 cast<PHINode>(BBI)->removeIncomingValue(SI->getParent()); 4367 } 4368 for (auto BBI = OtherDest->begin(); isa<PHINode>(BBI); ++BBI) { 4369 unsigned PreviousEdges = SI->getNumCases() - ContiguousCases->size(); 4370 if (OtherDest == SI->getDefaultDest()) 4371 ++PreviousEdges; 4372 for (unsigned I = 0, E = PreviousEdges - 1; I != E; ++I) 4373 cast<PHINode>(BBI)->removeIncomingValue(SI->getParent()); 4374 } 4375 4376 // Drop the switch. 4377 SI->eraseFromParent(); 4378 4379 return true; 4380 } 4381 4382 /// Compute masked bits for the condition of a switch 4383 /// and use it to remove dead cases. 4384 static bool eliminateDeadSwitchCases(SwitchInst *SI, AssumptionCache *AC, 4385 const DataLayout &DL) { 4386 Value *Cond = SI->getCondition(); 4387 unsigned Bits = Cond->getType()->getIntegerBitWidth(); 4388 KnownBits Known = computeKnownBits(Cond, DL, 0, AC, SI); 4389 4390 // We can also eliminate cases by determining that their values are outside of 4391 // the limited range of the condition based on how many significant (non-sign) 4392 // bits are in the condition value. 4393 unsigned ExtraSignBits = ComputeNumSignBits(Cond, DL, 0, AC, SI) - 1; 4394 unsigned MaxSignificantBitsInCond = Bits - ExtraSignBits; 4395 4396 // Gather dead cases. 4397 SmallVector<ConstantInt *, 8> DeadCases; 4398 for (auto &Case : SI->cases()) { 4399 const APInt &CaseVal = Case.getCaseValue()->getValue(); 4400 if (Known.Zero.intersects(CaseVal) || !Known.One.isSubsetOf(CaseVal) || 4401 (CaseVal.getMinSignedBits() > MaxSignificantBitsInCond)) { 4402 DeadCases.push_back(Case.getCaseValue()); 4403 LLVM_DEBUG(dbgs() << "SimplifyCFG: switch case " << CaseVal 4404 << " is dead.\n"); 4405 } 4406 } 4407 4408 // If we can prove that the cases must cover all possible values, the 4409 // default destination becomes dead and we can remove it. If we know some 4410 // of the bits in the value, we can use that to more precisely compute the 4411 // number of possible unique case values. 4412 bool HasDefault = 4413 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()); 4414 const unsigned NumUnknownBits = 4415 Bits - (Known.Zero | Known.One).countPopulation(); 4416 assert(NumUnknownBits <= Bits); 4417 if (HasDefault && DeadCases.empty() && 4418 NumUnknownBits < 64 /* avoid overflow */ && 4419 SI->getNumCases() == (1ULL << NumUnknownBits)) { 4420 LLVM_DEBUG(dbgs() << "SimplifyCFG: switch default is dead.\n"); 4421 BasicBlock *NewDefault = 4422 SplitBlockPredecessors(SI->getDefaultDest(), SI->getParent(), ""); 4423 SI->setDefaultDest(&*NewDefault); 4424 SplitBlock(&*NewDefault, &NewDefault->front()); 4425 auto *OldTI = NewDefault->getTerminator(); 4426 new UnreachableInst(SI->getContext(), OldTI); 4427 EraseTerminatorInstAndDCECond(OldTI); 4428 return true; 4429 } 4430 4431 SmallVector<uint64_t, 8> Weights; 4432 bool HasWeight = HasBranchWeights(SI); 4433 if (HasWeight) { 4434 GetBranchWeights(SI, Weights); 4435 HasWeight = (Weights.size() == 1 + SI->getNumCases()); 4436 } 4437 4438 // Remove dead cases from the switch. 4439 for (ConstantInt *DeadCase : DeadCases) { 4440 SwitchInst::CaseIt CaseI = SI->findCaseValue(DeadCase); 4441 assert(CaseI != SI->case_default() && 4442 "Case was not found. Probably mistake in DeadCases forming."); 4443 if (HasWeight) { 4444 std::swap(Weights[CaseI->getCaseIndex() + 1], Weights.back()); 4445 Weights.pop_back(); 4446 } 4447 4448 // Prune unused values from PHI nodes. 4449 CaseI->getCaseSuccessor()->removePredecessor(SI->getParent()); 4450 SI->removeCase(CaseI); 4451 } 4452 if (HasWeight && Weights.size() >= 2) { 4453 SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end()); 4454 setBranchWeights(SI, MDWeights); 4455 } 4456 4457 return !DeadCases.empty(); 4458 } 4459 4460 /// If BB would be eligible for simplification by 4461 /// TryToSimplifyUncondBranchFromEmptyBlock (i.e. it is empty and terminated 4462 /// by an unconditional branch), look at the phi node for BB in the successor 4463 /// block and see if the incoming value is equal to CaseValue. If so, return 4464 /// the phi node, and set PhiIndex to BB's index in the phi node. 4465 static PHINode *FindPHIForConditionForwarding(ConstantInt *CaseValue, 4466 BasicBlock *BB, int *PhiIndex) { 4467 if (BB->getFirstNonPHIOrDbg() != BB->getTerminator()) 4468 return nullptr; // BB must be empty to be a candidate for simplification. 4469 if (!BB->getSinglePredecessor()) 4470 return nullptr; // BB must be dominated by the switch. 4471 4472 BranchInst *Branch = dyn_cast<BranchInst>(BB->getTerminator()); 4473 if (!Branch || !Branch->isUnconditional()) 4474 return nullptr; // Terminator must be unconditional branch. 4475 4476 BasicBlock *Succ = Branch->getSuccessor(0); 4477 4478 for (PHINode &PHI : Succ->phis()) { 4479 int Idx = PHI.getBasicBlockIndex(BB); 4480 assert(Idx >= 0 && "PHI has no entry for predecessor?"); 4481 4482 Value *InValue = PHI.getIncomingValue(Idx); 4483 if (InValue != CaseValue) 4484 continue; 4485 4486 *PhiIndex = Idx; 4487 return &PHI; 4488 } 4489 4490 return nullptr; 4491 } 4492 4493 /// Try to forward the condition of a switch instruction to a phi node 4494 /// dominated by the switch, if that would mean that some of the destination 4495 /// blocks of the switch can be folded away. Return true if a change is made. 4496 static bool ForwardSwitchConditionToPHI(SwitchInst *SI) { 4497 using ForwardingNodesMap = DenseMap<PHINode *, SmallVector<int, 4>>; 4498 4499 ForwardingNodesMap ForwardingNodes; 4500 BasicBlock *SwitchBlock = SI->getParent(); 4501 bool Changed = false; 4502 for (auto &Case : SI->cases()) { 4503 ConstantInt *CaseValue = Case.getCaseValue(); 4504 BasicBlock *CaseDest = Case.getCaseSuccessor(); 4505 4506 // Replace phi operands in successor blocks that are using the constant case 4507 // value rather than the switch condition variable: 4508 // switchbb: 4509 // switch i32 %x, label %default [ 4510 // i32 17, label %succ 4511 // ... 4512 // succ: 4513 // %r = phi i32 ... [ 17, %switchbb ] ... 4514 // --> 4515 // %r = phi i32 ... [ %x, %switchbb ] ... 4516 4517 for (PHINode &Phi : CaseDest->phis()) { 4518 // This only works if there is exactly 1 incoming edge from the switch to 4519 // a phi. If there is >1, that means multiple cases of the switch map to 1 4520 // value in the phi, and that phi value is not the switch condition. Thus, 4521 // this transform would not make sense (the phi would be invalid because 4522 // a phi can't have different incoming values from the same block). 4523 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock); 4524 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue && 4525 count(Phi.blocks(), SwitchBlock) == 1) { 4526 Phi.setIncomingValue(SwitchBBIdx, SI->getCondition()); 4527 Changed = true; 4528 } 4529 } 4530 4531 // Collect phi nodes that are indirectly using this switch's case constants. 4532 int PhiIdx; 4533 if (auto *Phi = FindPHIForConditionForwarding(CaseValue, CaseDest, &PhiIdx)) 4534 ForwardingNodes[Phi].push_back(PhiIdx); 4535 } 4536 4537 for (auto &ForwardingNode : ForwardingNodes) { 4538 PHINode *Phi = ForwardingNode.first; 4539 SmallVectorImpl<int> &Indexes = ForwardingNode.second; 4540 if (Indexes.size() < 2) 4541 continue; 4542 4543 for (int Index : Indexes) 4544 Phi->setIncomingValue(Index, SI->getCondition()); 4545 Changed = true; 4546 } 4547 4548 return Changed; 4549 } 4550 4551 /// Return true if the backend will be able to handle 4552 /// initializing an array of constants like C. 4553 static bool ValidLookupTableConstant(Constant *C, const TargetTransformInfo &TTI) { 4554 if (C->isThreadDependent()) 4555 return false; 4556 if (C->isDLLImportDependent()) 4557 return false; 4558 4559 if (!isa<ConstantFP>(C) && !isa<ConstantInt>(C) && 4560 !isa<ConstantPointerNull>(C) && !isa<GlobalValue>(C) && 4561 !isa<UndefValue>(C) && !isa<ConstantExpr>(C)) 4562 return false; 4563 4564 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { 4565 if (!CE->isGEPWithNoNotionalOverIndexing()) 4566 return false; 4567 if (!ValidLookupTableConstant(CE->getOperand(0), TTI)) 4568 return false; 4569 } 4570 4571 if (!TTI.shouldBuildLookupTablesForConstant(C)) 4572 return false; 4573 4574 return true; 4575 } 4576 4577 /// If V is a Constant, return it. Otherwise, try to look up 4578 /// its constant value in ConstantPool, returning 0 if it's not there. 4579 static Constant * 4580 LookupConstant(Value *V, 4581 const SmallDenseMap<Value *, Constant *> &ConstantPool) { 4582 if (Constant *C = dyn_cast<Constant>(V)) 4583 return C; 4584 return ConstantPool.lookup(V); 4585 } 4586 4587 /// Try to fold instruction I into a constant. This works for 4588 /// simple instructions such as binary operations where both operands are 4589 /// constant or can be replaced by constants from the ConstantPool. Returns the 4590 /// resulting constant on success, 0 otherwise. 4591 static Constant * 4592 ConstantFold(Instruction *I, const DataLayout &DL, 4593 const SmallDenseMap<Value *, Constant *> &ConstantPool) { 4594 if (SelectInst *Select = dyn_cast<SelectInst>(I)) { 4595 Constant *A = LookupConstant(Select->getCondition(), ConstantPool); 4596 if (!A) 4597 return nullptr; 4598 if (A->isAllOnesValue()) 4599 return LookupConstant(Select->getTrueValue(), ConstantPool); 4600 if (A->isNullValue()) 4601 return LookupConstant(Select->getFalseValue(), ConstantPool); 4602 return nullptr; 4603 } 4604 4605 SmallVector<Constant *, 4> COps; 4606 for (unsigned N = 0, E = I->getNumOperands(); N != E; ++N) { 4607 if (Constant *A = LookupConstant(I->getOperand(N), ConstantPool)) 4608 COps.push_back(A); 4609 else 4610 return nullptr; 4611 } 4612 4613 if (CmpInst *Cmp = dyn_cast<CmpInst>(I)) { 4614 return ConstantFoldCompareInstOperands(Cmp->getPredicate(), COps[0], 4615 COps[1], DL); 4616 } 4617 4618 return ConstantFoldInstOperands(I, COps, DL); 4619 } 4620 4621 /// Try to determine the resulting constant values in phi nodes 4622 /// at the common destination basic block, *CommonDest, for one of the case 4623 /// destionations CaseDest corresponding to value CaseVal (0 for the default 4624 /// case), of a switch instruction SI. 4625 static bool 4626 GetCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, 4627 BasicBlock **CommonDest, 4628 SmallVectorImpl<std::pair<PHINode *, Constant *>> &Res, 4629 const DataLayout &DL, const TargetTransformInfo &TTI) { 4630 // The block from which we enter the common destination. 4631 BasicBlock *Pred = SI->getParent(); 4632 4633 // If CaseDest is empty except for some side-effect free instructions through 4634 // which we can constant-propagate the CaseVal, continue to its successor. 4635 SmallDenseMap<Value *, Constant *> ConstantPool; 4636 ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal)); 4637 for (Instruction &I :CaseDest->instructionsWithoutDebug()) { 4638 if (TerminatorInst *T = dyn_cast<TerminatorInst>(&I)) { 4639 // If the terminator is a simple branch, continue to the next block. 4640 if (T->getNumSuccessors() != 1 || T->isExceptional()) 4641 return false; 4642 Pred = CaseDest; 4643 CaseDest = T->getSuccessor(0); 4644 } else if (Constant *C = ConstantFold(&I, DL, ConstantPool)) { 4645 // Instruction is side-effect free and constant. 4646 4647 // If the instruction has uses outside this block or a phi node slot for 4648 // the block, it is not safe to bypass the instruction since it would then 4649 // no longer dominate all its uses. 4650 for (auto &Use : I.uses()) { 4651 User *User = Use.getUser(); 4652 if (Instruction *I = dyn_cast<Instruction>(User)) 4653 if (I->getParent() == CaseDest) 4654 continue; 4655 if (PHINode *Phi = dyn_cast<PHINode>(User)) 4656 if (Phi->getIncomingBlock(Use) == CaseDest) 4657 continue; 4658 return false; 4659 } 4660 4661 ConstantPool.insert(std::make_pair(&I, C)); 4662 } else { 4663 break; 4664 } 4665 } 4666 4667 // If we did not have a CommonDest before, use the current one. 4668 if (!*CommonDest) 4669 *CommonDest = CaseDest; 4670 // If the destination isn't the common one, abort. 4671 if (CaseDest != *CommonDest) 4672 return false; 4673 4674 // Get the values for this case from phi nodes in the destination block. 4675 for (PHINode &PHI : (*CommonDest)->phis()) { 4676 int Idx = PHI.getBasicBlockIndex(Pred); 4677 if (Idx == -1) 4678 continue; 4679 4680 Constant *ConstVal = 4681 LookupConstant(PHI.getIncomingValue(Idx), ConstantPool); 4682 if (!ConstVal) 4683 return false; 4684 4685 // Be conservative about which kinds of constants we support. 4686 if (!ValidLookupTableConstant(ConstVal, TTI)) 4687 return false; 4688 4689 Res.push_back(std::make_pair(&PHI, ConstVal)); 4690 } 4691 4692 return Res.size() > 0; 4693 } 4694 4695 // Helper function used to add CaseVal to the list of cases that generate 4696 // Result. Returns the updated number of cases that generate this result. 4697 static uintptr_t MapCaseToResult(ConstantInt *CaseVal, 4698 SwitchCaseResultVectorTy &UniqueResults, 4699 Constant *Result) { 4700 for (auto &I : UniqueResults) { 4701 if (I.first == Result) { 4702 I.second.push_back(CaseVal); 4703 return I.second.size(); 4704 } 4705 } 4706 UniqueResults.push_back( 4707 std::make_pair(Result, SmallVector<ConstantInt *, 4>(1, CaseVal))); 4708 return 1; 4709 } 4710 4711 // Helper function that initializes a map containing 4712 // results for the PHI node of the common destination block for a switch 4713 // instruction. Returns false if multiple PHI nodes have been found or if 4714 // there is not a common destination block for the switch. 4715 static bool 4716 InitializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, 4717 SwitchCaseResultVectorTy &UniqueResults, 4718 Constant *&DefaultResult, const DataLayout &DL, 4719 const TargetTransformInfo &TTI, 4720 uintptr_t MaxUniqueResults, uintptr_t MaxCasesPerResult) { 4721 for (auto &I : SI->cases()) { 4722 ConstantInt *CaseVal = I.getCaseValue(); 4723 4724 // Resulting value at phi nodes for this case value. 4725 SwitchCaseResultsTy Results; 4726 if (!GetCaseResults(SI, CaseVal, I.getCaseSuccessor(), &CommonDest, Results, 4727 DL, TTI)) 4728 return false; 4729 4730 // Only one value per case is permitted. 4731 if (Results.size() > 1) 4732 return false; 4733 4734 // Add the case->result mapping to UniqueResults. 4735 const uintptr_t NumCasesForResult = 4736 MapCaseToResult(CaseVal, UniqueResults, Results.begin()->second); 4737 4738 // Early out if there are too many cases for this result. 4739 if (NumCasesForResult > MaxCasesPerResult) 4740 return false; 4741 4742 // Early out if there are too many unique results. 4743 if (UniqueResults.size() > MaxUniqueResults) 4744 return false; 4745 4746 // Check the PHI consistency. 4747 if (!PHI) 4748 PHI = Results[0].first; 4749 else if (PHI != Results[0].first) 4750 return false; 4751 } 4752 // Find the default result value. 4753 SmallVector<std::pair<PHINode *, Constant *>, 1> DefaultResults; 4754 BasicBlock *DefaultDest = SI->getDefaultDest(); 4755 GetCaseResults(SI, nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults, 4756 DL, TTI); 4757 // If the default value is not found abort unless the default destination 4758 // is unreachable. 4759 DefaultResult = 4760 DefaultResults.size() == 1 ? DefaultResults.begin()->second : nullptr; 4761 if ((!DefaultResult && 4762 !isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg()))) 4763 return false; 4764 4765 return true; 4766 } 4767 4768 // Helper function that checks if it is possible to transform a switch with only 4769 // two cases (or two cases + default) that produces a result into a select. 4770 // Example: 4771 // switch (a) { 4772 // case 10: %0 = icmp eq i32 %a, 10 4773 // return 10; %1 = select i1 %0, i32 10, i32 4 4774 // case 20: ----> %2 = icmp eq i32 %a, 20 4775 // return 2; %3 = select i1 %2, i32 2, i32 %1 4776 // default: 4777 // return 4; 4778 // } 4779 static Value *ConvertTwoCaseSwitch(const SwitchCaseResultVectorTy &ResultVector, 4780 Constant *DefaultResult, Value *Condition, 4781 IRBuilder<> &Builder) { 4782 assert(ResultVector.size() == 2 && 4783 "We should have exactly two unique results at this point"); 4784 // If we are selecting between only two cases transform into a simple 4785 // select or a two-way select if default is possible. 4786 if (ResultVector[0].second.size() == 1 && 4787 ResultVector[1].second.size() == 1) { 4788 ConstantInt *const FirstCase = ResultVector[0].second[0]; 4789 ConstantInt *const SecondCase = ResultVector[1].second[0]; 4790 4791 bool DefaultCanTrigger = DefaultResult; 4792 Value *SelectValue = ResultVector[1].first; 4793 if (DefaultCanTrigger) { 4794 Value *const ValueCompare = 4795 Builder.CreateICmpEQ(Condition, SecondCase, "switch.selectcmp"); 4796 SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first, 4797 DefaultResult, "switch.select"); 4798 } 4799 Value *const ValueCompare = 4800 Builder.CreateICmpEQ(Condition, FirstCase, "switch.selectcmp"); 4801 return Builder.CreateSelect(ValueCompare, ResultVector[0].first, 4802 SelectValue, "switch.select"); 4803 } 4804 4805 return nullptr; 4806 } 4807 4808 // Helper function to cleanup a switch instruction that has been converted into 4809 // a select, fixing up PHI nodes and basic blocks. 4810 static void RemoveSwitchAfterSelectConversion(SwitchInst *SI, PHINode *PHI, 4811 Value *SelectValue, 4812 IRBuilder<> &Builder) { 4813 BasicBlock *SelectBB = SI->getParent(); 4814 while (PHI->getBasicBlockIndex(SelectBB) >= 0) 4815 PHI->removeIncomingValue(SelectBB); 4816 PHI->addIncoming(SelectValue, SelectBB); 4817 4818 Builder.CreateBr(PHI->getParent()); 4819 4820 // Remove the switch. 4821 for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) { 4822 BasicBlock *Succ = SI->getSuccessor(i); 4823 4824 if (Succ == PHI->getParent()) 4825 continue; 4826 Succ->removePredecessor(SelectBB); 4827 } 4828 SI->eraseFromParent(); 4829 } 4830 4831 /// If the switch is only used to initialize one or more 4832 /// phi nodes in a common successor block with only two different 4833 /// constant values, replace the switch with select. 4834 static bool switchToSelect(SwitchInst *SI, IRBuilder<> &Builder, 4835 const DataLayout &DL, 4836 const TargetTransformInfo &TTI) { 4837 Value *const Cond = SI->getCondition(); 4838 PHINode *PHI = nullptr; 4839 BasicBlock *CommonDest = nullptr; 4840 Constant *DefaultResult; 4841 SwitchCaseResultVectorTy UniqueResults; 4842 // Collect all the cases that will deliver the same value from the switch. 4843 if (!InitializeUniqueCases(SI, PHI, CommonDest, UniqueResults, DefaultResult, 4844 DL, TTI, 2, 1)) 4845 return false; 4846 // Selects choose between maximum two values. 4847 if (UniqueResults.size() != 2) 4848 return false; 4849 assert(PHI != nullptr && "PHI for value select not found"); 4850 4851 Builder.SetInsertPoint(SI); 4852 Value *SelectValue = 4853 ConvertTwoCaseSwitch(UniqueResults, DefaultResult, Cond, Builder); 4854 if (SelectValue) { 4855 RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, Builder); 4856 return true; 4857 } 4858 // The switch couldn't be converted into a select. 4859 return false; 4860 } 4861 4862 namespace { 4863 4864 /// This class represents a lookup table that can be used to replace a switch. 4865 class SwitchLookupTable { 4866 public: 4867 /// Create a lookup table to use as a switch replacement with the contents 4868 /// of Values, using DefaultValue to fill any holes in the table. 4869 SwitchLookupTable( 4870 Module &M, uint64_t TableSize, ConstantInt *Offset, 4871 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values, 4872 Constant *DefaultValue, const DataLayout &DL, const StringRef &FuncName); 4873 4874 /// Build instructions with Builder to retrieve the value at 4875 /// the position given by Index in the lookup table. 4876 Value *BuildLookup(Value *Index, IRBuilder<> &Builder); 4877 4878 /// Return true if a table with TableSize elements of 4879 /// type ElementType would fit in a target-legal register. 4880 static bool WouldFitInRegister(const DataLayout &DL, uint64_t TableSize, 4881 Type *ElementType); 4882 4883 private: 4884 // Depending on the contents of the table, it can be represented in 4885 // different ways. 4886 enum { 4887 // For tables where each element contains the same value, we just have to 4888 // store that single value and return it for each lookup. 4889 SingleValueKind, 4890 4891 // For tables where there is a linear relationship between table index 4892 // and values. We calculate the result with a simple multiplication 4893 // and addition instead of a table lookup. 4894 LinearMapKind, 4895 4896 // For small tables with integer elements, we can pack them into a bitmap 4897 // that fits into a target-legal register. Values are retrieved by 4898 // shift and mask operations. 4899 BitMapKind, 4900 4901 // The table is stored as an array of values. Values are retrieved by load 4902 // instructions from the table. 4903 ArrayKind 4904 } Kind; 4905 4906 // For SingleValueKind, this is the single value. 4907 Constant *SingleValue = nullptr; 4908 4909 // For BitMapKind, this is the bitmap. 4910 ConstantInt *BitMap = nullptr; 4911 IntegerType *BitMapElementTy = nullptr; 4912 4913 // For LinearMapKind, these are the constants used to derive the value. 4914 ConstantInt *LinearOffset = nullptr; 4915 ConstantInt *LinearMultiplier = nullptr; 4916 4917 // For ArrayKind, this is the array. 4918 GlobalVariable *Array = nullptr; 4919 }; 4920 4921 } // end anonymous namespace 4922 4923 SwitchLookupTable::SwitchLookupTable( 4924 Module &M, uint64_t TableSize, ConstantInt *Offset, 4925 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values, 4926 Constant *DefaultValue, const DataLayout &DL, const StringRef &FuncName) { 4927 assert(Values.size() && "Can't build lookup table without values!"); 4928 assert(TableSize >= Values.size() && "Can't fit values in table!"); 4929 4930 // If all values in the table are equal, this is that value. 4931 SingleValue = Values.begin()->second; 4932 4933 Type *ValueType = Values.begin()->second->getType(); 4934 4935 // Build up the table contents. 4936 SmallVector<Constant *, 64> TableContents(TableSize); 4937 for (size_t I = 0, E = Values.size(); I != E; ++I) { 4938 ConstantInt *CaseVal = Values[I].first; 4939 Constant *CaseRes = Values[I].second; 4940 assert(CaseRes->getType() == ValueType); 4941 4942 uint64_t Idx = (CaseVal->getValue() - Offset->getValue()).getLimitedValue(); 4943 TableContents[Idx] = CaseRes; 4944 4945 if (CaseRes != SingleValue) 4946 SingleValue = nullptr; 4947 } 4948 4949 // Fill in any holes in the table with the default result. 4950 if (Values.size() < TableSize) { 4951 assert(DefaultValue && 4952 "Need a default value to fill the lookup table holes."); 4953 assert(DefaultValue->getType() == ValueType); 4954 for (uint64_t I = 0; I < TableSize; ++I) { 4955 if (!TableContents[I]) 4956 TableContents[I] = DefaultValue; 4957 } 4958 4959 if (DefaultValue != SingleValue) 4960 SingleValue = nullptr; 4961 } 4962 4963 // If each element in the table contains the same value, we only need to store 4964 // that single value. 4965 if (SingleValue) { 4966 Kind = SingleValueKind; 4967 return; 4968 } 4969 4970 // Check if we can derive the value with a linear transformation from the 4971 // table index. 4972 if (isa<IntegerType>(ValueType)) { 4973 bool LinearMappingPossible = true; 4974 APInt PrevVal; 4975 APInt DistToPrev; 4976 assert(TableSize >= 2 && "Should be a SingleValue table."); 4977 // Check if there is the same distance between two consecutive values. 4978 for (uint64_t I = 0; I < TableSize; ++I) { 4979 ConstantInt *ConstVal = dyn_cast<ConstantInt>(TableContents[I]); 4980 if (!ConstVal) { 4981 // This is an undef. We could deal with it, but undefs in lookup tables 4982 // are very seldom. It's probably not worth the additional complexity. 4983 LinearMappingPossible = false; 4984 break; 4985 } 4986 const APInt &Val = ConstVal->getValue(); 4987 if (I != 0) { 4988 APInt Dist = Val - PrevVal; 4989 if (I == 1) { 4990 DistToPrev = Dist; 4991 } else if (Dist != DistToPrev) { 4992 LinearMappingPossible = false; 4993 break; 4994 } 4995 } 4996 PrevVal = Val; 4997 } 4998 if (LinearMappingPossible) { 4999 LinearOffset = cast<ConstantInt>(TableContents[0]); 5000 LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev); 5001 Kind = LinearMapKind; 5002 ++NumLinearMaps; 5003 return; 5004 } 5005 } 5006 5007 // If the type is integer and the table fits in a register, build a bitmap. 5008 if (WouldFitInRegister(DL, TableSize, ValueType)) { 5009 IntegerType *IT = cast<IntegerType>(ValueType); 5010 APInt TableInt(TableSize * IT->getBitWidth(), 0); 5011 for (uint64_t I = TableSize; I > 0; --I) { 5012 TableInt <<= IT->getBitWidth(); 5013 // Insert values into the bitmap. Undef values are set to zero. 5014 if (!isa<UndefValue>(TableContents[I - 1])) { 5015 ConstantInt *Val = cast<ConstantInt>(TableContents[I - 1]); 5016 TableInt |= Val->getValue().zext(TableInt.getBitWidth()); 5017 } 5018 } 5019 BitMap = ConstantInt::get(M.getContext(), TableInt); 5020 BitMapElementTy = IT; 5021 Kind = BitMapKind; 5022 ++NumBitMaps; 5023 return; 5024 } 5025 5026 // Store the table in an array. 5027 ArrayType *ArrayTy = ArrayType::get(ValueType, TableSize); 5028 Constant *Initializer = ConstantArray::get(ArrayTy, TableContents); 5029 5030 Array = new GlobalVariable(M, ArrayTy, /*constant=*/true, 5031 GlobalVariable::PrivateLinkage, Initializer, 5032 "switch.table." + FuncName); 5033 Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); 5034 Kind = ArrayKind; 5035 } 5036 5037 Value *SwitchLookupTable::BuildLookup(Value *Index, IRBuilder<> &Builder) { 5038 switch (Kind) { 5039 case SingleValueKind: 5040 return SingleValue; 5041 case LinearMapKind: { 5042 // Derive the result value from the input value. 5043 Value *Result = Builder.CreateIntCast(Index, LinearMultiplier->getType(), 5044 false, "switch.idx.cast"); 5045 if (!LinearMultiplier->isOne()) 5046 Result = Builder.CreateMul(Result, LinearMultiplier, "switch.idx.mult"); 5047 if (!LinearOffset->isZero()) 5048 Result = Builder.CreateAdd(Result, LinearOffset, "switch.offset"); 5049 return Result; 5050 } 5051 case BitMapKind: { 5052 // Type of the bitmap (e.g. i59). 5053 IntegerType *MapTy = BitMap->getType(); 5054 5055 // Cast Index to the same type as the bitmap. 5056 // Note: The Index is <= the number of elements in the table, so 5057 // truncating it to the width of the bitmask is safe. 5058 Value *ShiftAmt = Builder.CreateZExtOrTrunc(Index, MapTy, "switch.cast"); 5059 5060 // Multiply the shift amount by the element width. 5061 ShiftAmt = Builder.CreateMul( 5062 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()), 5063 "switch.shiftamt"); 5064 5065 // Shift down. 5066 Value *DownShifted = 5067 Builder.CreateLShr(BitMap, ShiftAmt, "switch.downshift"); 5068 // Mask off. 5069 return Builder.CreateTrunc(DownShifted, BitMapElementTy, "switch.masked"); 5070 } 5071 case ArrayKind: { 5072 // Make sure the table index will not overflow when treated as signed. 5073 IntegerType *IT = cast<IntegerType>(Index->getType()); 5074 uint64_t TableSize = 5075 Array->getInitializer()->getType()->getArrayNumElements(); 5076 if (TableSize > (1ULL << (IT->getBitWidth() - 1))) 5077 Index = Builder.CreateZExt( 5078 Index, IntegerType::get(IT->getContext(), IT->getBitWidth() + 1), 5079 "switch.tableidx.zext"); 5080 5081 Value *GEPIndices[] = {Builder.getInt32(0), Index}; 5082 Value *GEP = Builder.CreateInBoundsGEP(Array->getValueType(), Array, 5083 GEPIndices, "switch.gep"); 5084 return Builder.CreateLoad(GEP, "switch.load"); 5085 } 5086 } 5087 llvm_unreachable("Unknown lookup table kind!"); 5088 } 5089 5090 bool SwitchLookupTable::WouldFitInRegister(const DataLayout &DL, 5091 uint64_t TableSize, 5092 Type *ElementType) { 5093 auto *IT = dyn_cast<IntegerType>(ElementType); 5094 if (!IT) 5095 return false; 5096 // FIXME: If the type is wider than it needs to be, e.g. i8 but all values 5097 // are <= 15, we could try to narrow the type. 5098 5099 // Avoid overflow, fitsInLegalInteger uses unsigned int for the width. 5100 if (TableSize >= UINT_MAX / IT->getBitWidth()) 5101 return false; 5102 return DL.fitsInLegalInteger(TableSize * IT->getBitWidth()); 5103 } 5104 5105 /// Determine whether a lookup table should be built for this switch, based on 5106 /// the number of cases, size of the table, and the types of the results. 5107 static bool 5108 ShouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, 5109 const TargetTransformInfo &TTI, const DataLayout &DL, 5110 const SmallDenseMap<PHINode *, Type *> &ResultTypes) { 5111 if (SI->getNumCases() > TableSize || TableSize >= UINT64_MAX / 10) 5112 return false; // TableSize overflowed, or mul below might overflow. 5113 5114 bool AllTablesFitInRegister = true; 5115 bool HasIllegalType = false; 5116 for (const auto &I : ResultTypes) { 5117 Type *Ty = I.second; 5118 5119 // Saturate this flag to true. 5120 HasIllegalType = HasIllegalType || !TTI.isTypeLegal(Ty); 5121 5122 // Saturate this flag to false. 5123 AllTablesFitInRegister = 5124 AllTablesFitInRegister && 5125 SwitchLookupTable::WouldFitInRegister(DL, TableSize, Ty); 5126 5127 // If both flags saturate, we're done. NOTE: This *only* works with 5128 // saturating flags, and all flags have to saturate first due to the 5129 // non-deterministic behavior of iterating over a dense map. 5130 if (HasIllegalType && !AllTablesFitInRegister) 5131 break; 5132 } 5133 5134 // If each table would fit in a register, we should build it anyway. 5135 if (AllTablesFitInRegister) 5136 return true; 5137 5138 // Don't build a table that doesn't fit in-register if it has illegal types. 5139 if (HasIllegalType) 5140 return false; 5141 5142 // The table density should be at least 40%. This is the same criterion as for 5143 // jump tables, see SelectionDAGBuilder::handleJTSwitchCase. 5144 // FIXME: Find the best cut-off. 5145 return SI->getNumCases() * 10 >= TableSize * 4; 5146 } 5147 5148 /// Try to reuse the switch table index compare. Following pattern: 5149 /// \code 5150 /// if (idx < tablesize) 5151 /// r = table[idx]; // table does not contain default_value 5152 /// else 5153 /// r = default_value; 5154 /// if (r != default_value) 5155 /// ... 5156 /// \endcode 5157 /// Is optimized to: 5158 /// \code 5159 /// cond = idx < tablesize; 5160 /// if (cond) 5161 /// r = table[idx]; 5162 /// else 5163 /// r = default_value; 5164 /// if (cond) 5165 /// ... 5166 /// \endcode 5167 /// Jump threading will then eliminate the second if(cond). 5168 static void reuseTableCompare( 5169 User *PhiUser, BasicBlock *PhiBlock, BranchInst *RangeCheckBranch, 5170 Constant *DefaultValue, 5171 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) { 5172 ICmpInst *CmpInst = dyn_cast<ICmpInst>(PhiUser); 5173 if (!CmpInst) 5174 return; 5175 5176 // We require that the compare is in the same block as the phi so that jump 5177 // threading can do its work afterwards. 5178 if (CmpInst->getParent() != PhiBlock) 5179 return; 5180 5181 Constant *CmpOp1 = dyn_cast<Constant>(CmpInst->getOperand(1)); 5182 if (!CmpOp1) 5183 return; 5184 5185 Value *RangeCmp = RangeCheckBranch->getCondition(); 5186 Constant *TrueConst = ConstantInt::getTrue(RangeCmp->getType()); 5187 Constant *FalseConst = ConstantInt::getFalse(RangeCmp->getType()); 5188 5189 // Check if the compare with the default value is constant true or false. 5190 Constant *DefaultConst = ConstantExpr::getICmp(CmpInst->getPredicate(), 5191 DefaultValue, CmpOp1, true); 5192 if (DefaultConst != TrueConst && DefaultConst != FalseConst) 5193 return; 5194 5195 // Check if the compare with the case values is distinct from the default 5196 // compare result. 5197 for (auto ValuePair : Values) { 5198 Constant *CaseConst = ConstantExpr::getICmp(CmpInst->getPredicate(), 5199 ValuePair.second, CmpOp1, true); 5200 if (!CaseConst || CaseConst == DefaultConst || isa<UndefValue>(CaseConst)) 5201 return; 5202 assert((CaseConst == TrueConst || CaseConst == FalseConst) && 5203 "Expect true or false as compare result."); 5204 } 5205 5206 // Check if the branch instruction dominates the phi node. It's a simple 5207 // dominance check, but sufficient for our needs. 5208 // Although this check is invariant in the calling loops, it's better to do it 5209 // at this late stage. Practically we do it at most once for a switch. 5210 BasicBlock *BranchBlock = RangeCheckBranch->getParent(); 5211 for (auto PI = pred_begin(PhiBlock), E = pred_end(PhiBlock); PI != E; ++PI) { 5212 BasicBlock *Pred = *PI; 5213 if (Pred != BranchBlock && Pred->getUniquePredecessor() != BranchBlock) 5214 return; 5215 } 5216 5217 if (DefaultConst == FalseConst) { 5218 // The compare yields the same result. We can replace it. 5219 CmpInst->replaceAllUsesWith(RangeCmp); 5220 ++NumTableCmpReuses; 5221 } else { 5222 // The compare yields the same result, just inverted. We can replace it. 5223 Value *InvertedTableCmp = BinaryOperator::CreateXor( 5224 RangeCmp, ConstantInt::get(RangeCmp->getType(), 1), "inverted.cmp", 5225 RangeCheckBranch); 5226 CmpInst->replaceAllUsesWith(InvertedTableCmp); 5227 ++NumTableCmpReuses; 5228 } 5229 } 5230 5231 /// If the switch is only used to initialize one or more phi nodes in a common 5232 /// successor block with different constant values, replace the switch with 5233 /// lookup tables. 5234 static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, 5235 const DataLayout &DL, 5236 const TargetTransformInfo &TTI) { 5237 assert(SI->getNumCases() > 1 && "Degenerate switch?"); 5238 5239 Function *Fn = SI->getParent()->getParent(); 5240 // Only build lookup table when we have a target that supports it or the 5241 // attribute is not set. 5242 if (!TTI.shouldBuildLookupTables() || 5243 (Fn->getFnAttribute("no-jump-tables").getValueAsString() == "true")) 5244 return false; 5245 5246 // FIXME: If the switch is too sparse for a lookup table, perhaps we could 5247 // split off a dense part and build a lookup table for that. 5248 5249 // FIXME: This creates arrays of GEPs to constant strings, which means each 5250 // GEP needs a runtime relocation in PIC code. We should just build one big 5251 // string and lookup indices into that. 5252 5253 // Ignore switches with less than three cases. Lookup tables will not make 5254 // them faster, so we don't analyze them. 5255 if (SI->getNumCases() < 3) 5256 return false; 5257 5258 // Figure out the corresponding result for each case value and phi node in the 5259 // common destination, as well as the min and max case values. 5260 assert(SI->case_begin() != SI->case_end()); 5261 SwitchInst::CaseIt CI = SI->case_begin(); 5262 ConstantInt *MinCaseVal = CI->getCaseValue(); 5263 ConstantInt *MaxCaseVal = CI->getCaseValue(); 5264 5265 BasicBlock *CommonDest = nullptr; 5266 5267 using ResultListTy = SmallVector<std::pair<ConstantInt *, Constant *>, 4>; 5268 SmallDenseMap<PHINode *, ResultListTy> ResultLists; 5269 5270 SmallDenseMap<PHINode *, Constant *> DefaultResults; 5271 SmallDenseMap<PHINode *, Type *> ResultTypes; 5272 SmallVector<PHINode *, 4> PHIs; 5273 5274 for (SwitchInst::CaseIt E = SI->case_end(); CI != E; ++CI) { 5275 ConstantInt *CaseVal = CI->getCaseValue(); 5276 if (CaseVal->getValue().slt(MinCaseVal->getValue())) 5277 MinCaseVal = CaseVal; 5278 if (CaseVal->getValue().sgt(MaxCaseVal->getValue())) 5279 MaxCaseVal = CaseVal; 5280 5281 // Resulting value at phi nodes for this case value. 5282 using ResultsTy = SmallVector<std::pair<PHINode *, Constant *>, 4>; 5283 ResultsTy Results; 5284 if (!GetCaseResults(SI, CaseVal, CI->getCaseSuccessor(), &CommonDest, 5285 Results, DL, TTI)) 5286 return false; 5287 5288 // Append the result from this case to the list for each phi. 5289 for (const auto &I : Results) { 5290 PHINode *PHI = I.first; 5291 Constant *Value = I.second; 5292 if (!ResultLists.count(PHI)) 5293 PHIs.push_back(PHI); 5294 ResultLists[PHI].push_back(std::make_pair(CaseVal, Value)); 5295 } 5296 } 5297 5298 // Keep track of the result types. 5299 for (PHINode *PHI : PHIs) { 5300 ResultTypes[PHI] = ResultLists[PHI][0].second->getType(); 5301 } 5302 5303 uint64_t NumResults = ResultLists[PHIs[0]].size(); 5304 APInt RangeSpread = MaxCaseVal->getValue() - MinCaseVal->getValue(); 5305 uint64_t TableSize = RangeSpread.getLimitedValue() + 1; 5306 bool TableHasHoles = (NumResults < TableSize); 5307 5308 // If the table has holes, we need a constant result for the default case 5309 // or a bitmask that fits in a register. 5310 SmallVector<std::pair<PHINode *, Constant *>, 4> DefaultResultsList; 5311 bool HasDefaultResults = 5312 GetCaseResults(SI, nullptr, SI->getDefaultDest(), &CommonDest, 5313 DefaultResultsList, DL, TTI); 5314 5315 bool NeedMask = (TableHasHoles && !HasDefaultResults); 5316 if (NeedMask) { 5317 // As an extra penalty for the validity test we require more cases. 5318 if (SI->getNumCases() < 4) // FIXME: Find best threshold value (benchmark). 5319 return false; 5320 if (!DL.fitsInLegalInteger(TableSize)) 5321 return false; 5322 } 5323 5324 for (const auto &I : DefaultResultsList) { 5325 PHINode *PHI = I.first; 5326 Constant *Result = I.second; 5327 DefaultResults[PHI] = Result; 5328 } 5329 5330 if (!ShouldBuildLookupTable(SI, TableSize, TTI, DL, ResultTypes)) 5331 return false; 5332 5333 // Create the BB that does the lookups. 5334 Module &Mod = *CommonDest->getParent()->getParent(); 5335 BasicBlock *LookupBB = BasicBlock::Create( 5336 Mod.getContext(), "switch.lookup", CommonDest->getParent(), CommonDest); 5337 5338 // Compute the table index value. 5339 Builder.SetInsertPoint(SI); 5340 Value *TableIndex; 5341 if (MinCaseVal->isNullValue()) 5342 TableIndex = SI->getCondition(); 5343 else 5344 TableIndex = Builder.CreateSub(SI->getCondition(), MinCaseVal, 5345 "switch.tableidx"); 5346 5347 // Compute the maximum table size representable by the integer type we are 5348 // switching upon. 5349 unsigned CaseSize = MinCaseVal->getType()->getPrimitiveSizeInBits(); 5350 uint64_t MaxTableSize = CaseSize > 63 ? UINT64_MAX : 1ULL << CaseSize; 5351 assert(MaxTableSize >= TableSize && 5352 "It is impossible for a switch to have more entries than the max " 5353 "representable value of its input integer type's size."); 5354 5355 // If the default destination is unreachable, or if the lookup table covers 5356 // all values of the conditional variable, branch directly to the lookup table 5357 // BB. Otherwise, check that the condition is within the case range. 5358 const bool DefaultIsReachable = 5359 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()); 5360 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize); 5361 BranchInst *RangeCheckBranch = nullptr; 5362 5363 if (!DefaultIsReachable || GeneratingCoveredLookupTable) { 5364 Builder.CreateBr(LookupBB); 5365 // Note: We call removeProdecessor later since we need to be able to get the 5366 // PHI value for the default case in case we're using a bit mask. 5367 } else { 5368 Value *Cmp = Builder.CreateICmpULT( 5369 TableIndex, ConstantInt::get(MinCaseVal->getType(), TableSize)); 5370 RangeCheckBranch = 5371 Builder.CreateCondBr(Cmp, LookupBB, SI->getDefaultDest()); 5372 } 5373 5374 // Populate the BB that does the lookups. 5375 Builder.SetInsertPoint(LookupBB); 5376 5377 if (NeedMask) { 5378 // Before doing the lookup, we do the hole check. The LookupBB is therefore 5379 // re-purposed to do the hole check, and we create a new LookupBB. 5380 BasicBlock *MaskBB = LookupBB; 5381 MaskBB->setName("switch.hole_check"); 5382 LookupBB = BasicBlock::Create(Mod.getContext(), "switch.lookup", 5383 CommonDest->getParent(), CommonDest); 5384 5385 // Make the mask's bitwidth at least 8-bit and a power-of-2 to avoid 5386 // unnecessary illegal types. 5387 uint64_t TableSizePowOf2 = NextPowerOf2(std::max(7ULL, TableSize - 1ULL)); 5388 APInt MaskInt(TableSizePowOf2, 0); 5389 APInt One(TableSizePowOf2, 1); 5390 // Build bitmask; fill in a 1 bit for every case. 5391 const ResultListTy &ResultList = ResultLists[PHIs[0]]; 5392 for (size_t I = 0, E = ResultList.size(); I != E; ++I) { 5393 uint64_t Idx = (ResultList[I].first->getValue() - MinCaseVal->getValue()) 5394 .getLimitedValue(); 5395 MaskInt |= One << Idx; 5396 } 5397 ConstantInt *TableMask = ConstantInt::get(Mod.getContext(), MaskInt); 5398 5399 // Get the TableIndex'th bit of the bitmask. 5400 // If this bit is 0 (meaning hole) jump to the default destination, 5401 // else continue with table lookup. 5402 IntegerType *MapTy = TableMask->getType(); 5403 Value *MaskIndex = 5404 Builder.CreateZExtOrTrunc(TableIndex, MapTy, "switch.maskindex"); 5405 Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex, "switch.shifted"); 5406 Value *LoBit = Builder.CreateTrunc( 5407 Shifted, Type::getInt1Ty(Mod.getContext()), "switch.lobit"); 5408 Builder.CreateCondBr(LoBit, LookupBB, SI->getDefaultDest()); 5409 5410 Builder.SetInsertPoint(LookupBB); 5411 AddPredecessorToBlock(SI->getDefaultDest(), MaskBB, SI->getParent()); 5412 } 5413 5414 if (!DefaultIsReachable || GeneratingCoveredLookupTable) { 5415 // We cached PHINodes in PHIs. To avoid accessing deleted PHINodes later, 5416 // do not delete PHINodes here. 5417 SI->getDefaultDest()->removePredecessor(SI->getParent(), 5418 /*DontDeleteUselessPHIs=*/true); 5419 } 5420 5421 bool ReturnedEarly = false; 5422 for (PHINode *PHI : PHIs) { 5423 const ResultListTy &ResultList = ResultLists[PHI]; 5424 5425 // If using a bitmask, use any value to fill the lookup table holes. 5426 Constant *DV = NeedMask ? ResultLists[PHI][0].second : DefaultResults[PHI]; 5427 StringRef FuncName = Fn->getName(); 5428 SwitchLookupTable Table(Mod, TableSize, MinCaseVal, ResultList, DV, DL, 5429 FuncName); 5430 5431 Value *Result = Table.BuildLookup(TableIndex, Builder); 5432 5433 // If the result is used to return immediately from the function, we want to 5434 // do that right here. 5435 if (PHI->hasOneUse() && isa<ReturnInst>(*PHI->user_begin()) && 5436 PHI->user_back() == CommonDest->getFirstNonPHIOrDbg()) { 5437 Builder.CreateRet(Result); 5438 ReturnedEarly = true; 5439 break; 5440 } 5441 5442 // Do a small peephole optimization: re-use the switch table compare if 5443 // possible. 5444 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) { 5445 BasicBlock *PhiBlock = PHI->getParent(); 5446 // Search for compare instructions which use the phi. 5447 for (auto *User : PHI->users()) { 5448 reuseTableCompare(User, PhiBlock, RangeCheckBranch, DV, ResultList); 5449 } 5450 } 5451 5452 PHI->addIncoming(Result, LookupBB); 5453 } 5454 5455 if (!ReturnedEarly) 5456 Builder.CreateBr(CommonDest); 5457 5458 // Remove the switch. 5459 for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) { 5460 BasicBlock *Succ = SI->getSuccessor(i); 5461 5462 if (Succ == SI->getDefaultDest()) 5463 continue; 5464 Succ->removePredecessor(SI->getParent()); 5465 } 5466 SI->eraseFromParent(); 5467 5468 ++NumLookupTables; 5469 if (NeedMask) 5470 ++NumLookupTablesHoles; 5471 return true; 5472 } 5473 5474 static bool isSwitchDense(ArrayRef<int64_t> Values) { 5475 // See also SelectionDAGBuilder::isDense(), which this function was based on. 5476 uint64_t Diff = (uint64_t)Values.back() - (uint64_t)Values.front(); 5477 uint64_t Range = Diff + 1; 5478 uint64_t NumCases = Values.size(); 5479 // 40% is the default density for building a jump table in optsize/minsize mode. 5480 uint64_t MinDensity = 40; 5481 5482 return NumCases * 100 >= Range * MinDensity; 5483 } 5484 5485 /// Try to transform a switch that has "holes" in it to a contiguous sequence 5486 /// of cases. 5487 /// 5488 /// A switch such as: switch(i) {case 5: case 9: case 13: case 17:} can be 5489 /// range-reduced to: switch ((i-5) / 4) {case 0: case 1: case 2: case 3:}. 5490 /// 5491 /// This converts a sparse switch into a dense switch which allows better 5492 /// lowering and could also allow transforming into a lookup table. 5493 static bool ReduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, 5494 const DataLayout &DL, 5495 const TargetTransformInfo &TTI) { 5496 auto *CondTy = cast<IntegerType>(SI->getCondition()->getType()); 5497 if (CondTy->getIntegerBitWidth() > 64 || 5498 !DL.fitsInLegalInteger(CondTy->getIntegerBitWidth())) 5499 return false; 5500 // Only bother with this optimization if there are more than 3 switch cases; 5501 // SDAG will only bother creating jump tables for 4 or more cases. 5502 if (SI->getNumCases() < 4) 5503 return false; 5504 5505 // This transform is agnostic to the signedness of the input or case values. We 5506 // can treat the case values as signed or unsigned. We can optimize more common 5507 // cases such as a sequence crossing zero {-4,0,4,8} if we interpret case values 5508 // as signed. 5509 SmallVector<int64_t,4> Values; 5510 for (auto &C : SI->cases()) 5511 Values.push_back(C.getCaseValue()->getValue().getSExtValue()); 5512 llvm::sort(Values.begin(), Values.end()); 5513 5514 // If the switch is already dense, there's nothing useful to do here. 5515 if (isSwitchDense(Values)) 5516 return false; 5517 5518 // First, transform the values such that they start at zero and ascend. 5519 int64_t Base = Values[0]; 5520 for (auto &V : Values) 5521 V -= (uint64_t)(Base); 5522 5523 // Now we have signed numbers that have been shifted so that, given enough 5524 // precision, there are no negative values. Since the rest of the transform 5525 // is bitwise only, we switch now to an unsigned representation. 5526 uint64_t GCD = 0; 5527 for (auto &V : Values) 5528 GCD = GreatestCommonDivisor64(GCD, (uint64_t)V); 5529 5530 // This transform can be done speculatively because it is so cheap - it results 5531 // in a single rotate operation being inserted. This can only happen if the 5532 // factor extracted is a power of 2. 5533 // FIXME: If the GCD is an odd number we can multiply by the multiplicative 5534 // inverse of GCD and then perform this transform. 5535 // FIXME: It's possible that optimizing a switch on powers of two might also 5536 // be beneficial - flag values are often powers of two and we could use a CLZ 5537 // as the key function. 5538 if (GCD <= 1 || !isPowerOf2_64(GCD)) 5539 // No common divisor found or too expensive to compute key function. 5540 return false; 5541 5542 unsigned Shift = Log2_64(GCD); 5543 for (auto &V : Values) 5544 V = (int64_t)((uint64_t)V >> Shift); 5545 5546 if (!isSwitchDense(Values)) 5547 // Transform didn't create a dense switch. 5548 return false; 5549 5550 // The obvious transform is to shift the switch condition right and emit a 5551 // check that the condition actually cleanly divided by GCD, i.e. 5552 // C & (1 << Shift - 1) == 0 5553 // inserting a new CFG edge to handle the case where it didn't divide cleanly. 5554 // 5555 // A cheaper way of doing this is a simple ROTR(C, Shift). This performs the 5556 // shift and puts the shifted-off bits in the uppermost bits. If any of these 5557 // are nonzero then the switch condition will be very large and will hit the 5558 // default case. 5559 5560 auto *Ty = cast<IntegerType>(SI->getCondition()->getType()); 5561 Builder.SetInsertPoint(SI); 5562 auto *ShiftC = ConstantInt::get(Ty, Shift); 5563 auto *Sub = Builder.CreateSub(SI->getCondition(), ConstantInt::get(Ty, Base)); 5564 auto *LShr = Builder.CreateLShr(Sub, ShiftC); 5565 auto *Shl = Builder.CreateShl(Sub, Ty->getBitWidth() - Shift); 5566 auto *Rot = Builder.CreateOr(LShr, Shl); 5567 SI->replaceUsesOfWith(SI->getCondition(), Rot); 5568 5569 for (auto Case : SI->cases()) { 5570 auto *Orig = Case.getCaseValue(); 5571 auto Sub = Orig->getValue() - APInt(Ty->getBitWidth(), Base); 5572 Case.setValue( 5573 cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(ShiftC->getValue())))); 5574 } 5575 return true; 5576 } 5577 5578 bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) { 5579 BasicBlock *BB = SI->getParent(); 5580 5581 if (isValueEqualityComparison(SI)) { 5582 // If we only have one predecessor, and if it is a branch on this value, 5583 // see if that predecessor totally determines the outcome of this switch. 5584 if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 5585 if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder)) 5586 return simplifyCFG(BB, TTI, Options) | true; 5587 5588 Value *Cond = SI->getCondition(); 5589 if (SelectInst *Select = dyn_cast<SelectInst>(Cond)) 5590 if (SimplifySwitchOnSelect(SI, Select)) 5591 return simplifyCFG(BB, TTI, Options) | true; 5592 5593 // If the block only contains the switch, see if we can fold the block 5594 // away into any preds. 5595 if (SI == &*BB->instructionsWithoutDebug().begin()) 5596 if (FoldValueComparisonIntoPredecessors(SI, Builder)) 5597 return simplifyCFG(BB, TTI, Options) | true; 5598 } 5599 5600 // Try to transform the switch into an icmp and a branch. 5601 if (TurnSwitchRangeIntoICmp(SI, Builder)) 5602 return simplifyCFG(BB, TTI, Options) | true; 5603 5604 // Remove unreachable cases. 5605 if (eliminateDeadSwitchCases(SI, Options.AC, DL)) 5606 return simplifyCFG(BB, TTI, Options) | true; 5607 5608 if (switchToSelect(SI, Builder, DL, TTI)) 5609 return simplifyCFG(BB, TTI, Options) | true; 5610 5611 if (Options.ForwardSwitchCondToPhi && ForwardSwitchConditionToPHI(SI)) 5612 return simplifyCFG(BB, TTI, Options) | true; 5613 5614 // The conversion from switch to lookup tables results in difficult-to-analyze 5615 // code and makes pruning branches much harder. This is a problem if the 5616 // switch expression itself can still be restricted as a result of inlining or 5617 // CVP. Therefore, only apply this transformation during late stages of the 5618 // optimisation pipeline. 5619 if (Options.ConvertSwitchToLookupTable && 5620 SwitchToLookupTable(SI, Builder, DL, TTI)) 5621 return simplifyCFG(BB, TTI, Options) | true; 5622 5623 if (ReduceSwitchRange(SI, Builder, DL, TTI)) 5624 return simplifyCFG(BB, TTI, Options) | true; 5625 5626 return false; 5627 } 5628 5629 bool SimplifyCFGOpt::SimplifyIndirectBr(IndirectBrInst *IBI) { 5630 BasicBlock *BB = IBI->getParent(); 5631 bool Changed = false; 5632 5633 // Eliminate redundant destinations. 5634 SmallPtrSet<Value *, 8> Succs; 5635 for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { 5636 BasicBlock *Dest = IBI->getDestination(i); 5637 if (!Dest->hasAddressTaken() || !Succs.insert(Dest).second) { 5638 Dest->removePredecessor(BB); 5639 IBI->removeDestination(i); 5640 --i; 5641 --e; 5642 Changed = true; 5643 } 5644 } 5645 5646 if (IBI->getNumDestinations() == 0) { 5647 // If the indirectbr has no successors, change it to unreachable. 5648 new UnreachableInst(IBI->getContext(), IBI); 5649 EraseTerminatorInstAndDCECond(IBI); 5650 return true; 5651 } 5652 5653 if (IBI->getNumDestinations() == 1) { 5654 // If the indirectbr has one successor, change it to a direct branch. 5655 BranchInst::Create(IBI->getDestination(0), IBI); 5656 EraseTerminatorInstAndDCECond(IBI); 5657 return true; 5658 } 5659 5660 if (SelectInst *SI = dyn_cast<SelectInst>(IBI->getAddress())) { 5661 if (SimplifyIndirectBrOnSelect(IBI, SI)) 5662 return simplifyCFG(BB, TTI, Options) | true; 5663 } 5664 return Changed; 5665 } 5666 5667 /// Given an block with only a single landing pad and a unconditional branch 5668 /// try to find another basic block which this one can be merged with. This 5669 /// handles cases where we have multiple invokes with unique landing pads, but 5670 /// a shared handler. 5671 /// 5672 /// We specifically choose to not worry about merging non-empty blocks 5673 /// here. That is a PRE/scheduling problem and is best solved elsewhere. In 5674 /// practice, the optimizer produces empty landing pad blocks quite frequently 5675 /// when dealing with exception dense code. (see: instcombine, gvn, if-else 5676 /// sinking in this file) 5677 /// 5678 /// This is primarily a code size optimization. We need to avoid performing 5679 /// any transform which might inhibit optimization (such as our ability to 5680 /// specialize a particular handler via tail commoning). We do this by not 5681 /// merging any blocks which require us to introduce a phi. Since the same 5682 /// values are flowing through both blocks, we don't lose any ability to 5683 /// specialize. If anything, we make such specialization more likely. 5684 /// 5685 /// TODO - This transformation could remove entries from a phi in the target 5686 /// block when the inputs in the phi are the same for the two blocks being 5687 /// merged. In some cases, this could result in removal of the PHI entirely. 5688 static bool TryToMergeLandingPad(LandingPadInst *LPad, BranchInst *BI, 5689 BasicBlock *BB) { 5690 auto Succ = BB->getUniqueSuccessor(); 5691 assert(Succ); 5692 // If there's a phi in the successor block, we'd likely have to introduce 5693 // a phi into the merged landing pad block. 5694 if (isa<PHINode>(*Succ->begin())) 5695 return false; 5696 5697 for (BasicBlock *OtherPred : predecessors(Succ)) { 5698 if (BB == OtherPred) 5699 continue; 5700 BasicBlock::iterator I = OtherPred->begin(); 5701 LandingPadInst *LPad2 = dyn_cast<LandingPadInst>(I); 5702 if (!LPad2 || !LPad2->isIdenticalTo(LPad)) 5703 continue; 5704 for (++I; isa<DbgInfoIntrinsic>(I); ++I) 5705 ; 5706 BranchInst *BI2 = dyn_cast<BranchInst>(I); 5707 if (!BI2 || !BI2->isIdenticalTo(BI)) 5708 continue; 5709 5710 // We've found an identical block. Update our predecessors to take that 5711 // path instead and make ourselves dead. 5712 SmallPtrSet<BasicBlock *, 16> Preds; 5713 Preds.insert(pred_begin(BB), pred_end(BB)); 5714 for (BasicBlock *Pred : Preds) { 5715 InvokeInst *II = cast<InvokeInst>(Pred->getTerminator()); 5716 assert(II->getNormalDest() != BB && II->getUnwindDest() == BB && 5717 "unexpected successor"); 5718 II->setUnwindDest(OtherPred); 5719 } 5720 5721 // The debug info in OtherPred doesn't cover the merged control flow that 5722 // used to go through BB. We need to delete it or update it. 5723 for (auto I = OtherPred->begin(), E = OtherPred->end(); I != E;) { 5724 Instruction &Inst = *I; 5725 I++; 5726 if (isa<DbgInfoIntrinsic>(Inst)) 5727 Inst.eraseFromParent(); 5728 } 5729 5730 SmallPtrSet<BasicBlock *, 16> Succs; 5731 Succs.insert(succ_begin(BB), succ_end(BB)); 5732 for (BasicBlock *Succ : Succs) { 5733 Succ->removePredecessor(BB); 5734 } 5735 5736 IRBuilder<> Builder(BI); 5737 Builder.CreateUnreachable(); 5738 BI->eraseFromParent(); 5739 return true; 5740 } 5741 return false; 5742 } 5743 5744 bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI, 5745 IRBuilder<> &Builder) { 5746 BasicBlock *BB = BI->getParent(); 5747 BasicBlock *Succ = BI->getSuccessor(0); 5748 5749 // If the Terminator is the only non-phi instruction, simplify the block. 5750 // If LoopHeader is provided, check if the block or its successor is a loop 5751 // header. (This is for early invocations before loop simplify and 5752 // vectorization to keep canonical loop forms for nested loops. These blocks 5753 // can be eliminated when the pass is invoked later in the back-end.) 5754 // Note that if BB has only one predecessor then we do not introduce new 5755 // backedge, so we can eliminate BB. 5756 bool NeedCanonicalLoop = 5757 Options.NeedCanonicalLoop && 5758 (LoopHeaders && pred_size(BB) > 1 && 5759 (LoopHeaders->count(BB) || LoopHeaders->count(Succ))); 5760 BasicBlock::iterator I = BB->getFirstNonPHIOrDbg()->getIterator(); 5761 if (I->isTerminator() && BB != &BB->getParent()->getEntryBlock() && 5762 !NeedCanonicalLoop && TryToSimplifyUncondBranchFromEmptyBlock(BB)) 5763 return true; 5764 5765 // If the only instruction in the block is a seteq/setne comparison against a 5766 // constant, try to simplify the block. 5767 if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) 5768 if (ICI->isEquality() && isa<ConstantInt>(ICI->getOperand(1))) { 5769 for (++I; isa<DbgInfoIntrinsic>(I); ++I) 5770 ; 5771 if (I->isTerminator() && 5772 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder, DL, TTI, Options)) 5773 return true; 5774 } 5775 5776 // See if we can merge an empty landing pad block with another which is 5777 // equivalent. 5778 if (LandingPadInst *LPad = dyn_cast<LandingPadInst>(I)) { 5779 for (++I; isa<DbgInfoIntrinsic>(I); ++I) 5780 ; 5781 if (I->isTerminator() && TryToMergeLandingPad(LPad, BI, BB)) 5782 return true; 5783 } 5784 5785 // If this basic block is ONLY a compare and a branch, and if a predecessor 5786 // branches to us and our successor, fold the comparison into the 5787 // predecessor and use logical operations to update the incoming value 5788 // for PHI nodes in common successor. 5789 if (FoldBranchToCommonDest(BI, Options.BonusInstThreshold)) 5790 return simplifyCFG(BB, TTI, Options) | true; 5791 return false; 5792 } 5793 5794 static BasicBlock *allPredecessorsComeFromSameSource(BasicBlock *BB) { 5795 BasicBlock *PredPred = nullptr; 5796 for (auto *P : predecessors(BB)) { 5797 BasicBlock *PPred = P->getSinglePredecessor(); 5798 if (!PPred || (PredPred && PredPred != PPred)) 5799 return nullptr; 5800 PredPred = PPred; 5801 } 5802 return PredPred; 5803 } 5804 5805 bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) { 5806 BasicBlock *BB = BI->getParent(); 5807 const Function *Fn = BB->getParent(); 5808 if (Fn && Fn->hasFnAttribute(Attribute::OptForFuzzing)) 5809 return false; 5810 5811 // Conditional branch 5812 if (isValueEqualityComparison(BI)) { 5813 // If we only have one predecessor, and if it is a branch on this value, 5814 // see if that predecessor totally determines the outcome of this 5815 // switch. 5816 if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 5817 if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder)) 5818 return simplifyCFG(BB, TTI, Options) | true; 5819 5820 // This block must be empty, except for the setcond inst, if it exists. 5821 // Ignore dbg intrinsics. 5822 auto I = BB->instructionsWithoutDebug().begin(); 5823 if (&*I == BI) { 5824 if (FoldValueComparisonIntoPredecessors(BI, Builder)) 5825 return simplifyCFG(BB, TTI, Options) | true; 5826 } else if (&*I == cast<Instruction>(BI->getCondition())) { 5827 ++I; 5828 if (&*I == BI && FoldValueComparisonIntoPredecessors(BI, Builder)) 5829 return simplifyCFG(BB, TTI, Options) | true; 5830 } 5831 } 5832 5833 // Try to turn "br (X == 0 | X == 1), T, F" into a switch instruction. 5834 if (SimplifyBranchOnICmpChain(BI, Builder, DL)) 5835 return true; 5836 5837 // If this basic block has a single dominating predecessor block and the 5838 // dominating block's condition implies BI's condition, we know the direction 5839 // of the BI branch. 5840 if (BasicBlock *Dom = BB->getSinglePredecessor()) { 5841 auto *PBI = dyn_cast_or_null<BranchInst>(Dom->getTerminator()); 5842 if (PBI && PBI->isConditional() && 5843 PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 5844 assert(PBI->getSuccessor(0) == BB || PBI->getSuccessor(1) == BB); 5845 bool CondIsTrue = PBI->getSuccessor(0) == BB; 5846 Optional<bool> Implication = isImpliedCondition( 5847 PBI->getCondition(), BI->getCondition(), DL, CondIsTrue); 5848 if (Implication) { 5849 // Turn this into a branch on constant. 5850 auto *OldCond = BI->getCondition(); 5851 ConstantInt *CI = *Implication 5852 ? ConstantInt::getTrue(BB->getContext()) 5853 : ConstantInt::getFalse(BB->getContext()); 5854 BI->setCondition(CI); 5855 RecursivelyDeleteTriviallyDeadInstructions(OldCond); 5856 return simplifyCFG(BB, TTI, Options) | true; 5857 } 5858 } 5859 } 5860 5861 // If this basic block is ONLY a compare and a branch, and if a predecessor 5862 // branches to us and one of our successors, fold the comparison into the 5863 // predecessor and use logical operations to pick the right destination. 5864 if (FoldBranchToCommonDest(BI, Options.BonusInstThreshold)) 5865 return simplifyCFG(BB, TTI, Options) | true; 5866 5867 // We have a conditional branch to two blocks that are only reachable 5868 // from BI. We know that the condbr dominates the two blocks, so see if 5869 // there is any identical code in the "then" and "else" blocks. If so, we 5870 // can hoist it up to the branching block. 5871 if (BI->getSuccessor(0)->getSinglePredecessor()) { 5872 if (BI->getSuccessor(1)->getSinglePredecessor()) { 5873 if (HoistThenElseCodeToIf(BI, TTI)) 5874 return simplifyCFG(BB, TTI, Options) | true; 5875 } else { 5876 // If Successor #1 has multiple preds, we may be able to conditionally 5877 // execute Successor #0 if it branches to Successor #1. 5878 TerminatorInst *Succ0TI = BI->getSuccessor(0)->getTerminator(); 5879 if (Succ0TI->getNumSuccessors() == 1 && 5880 Succ0TI->getSuccessor(0) == BI->getSuccessor(1)) 5881 if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0), TTI)) 5882 return simplifyCFG(BB, TTI, Options) | true; 5883 } 5884 } else if (BI->getSuccessor(1)->getSinglePredecessor()) { 5885 // If Successor #0 has multiple preds, we may be able to conditionally 5886 // execute Successor #1 if it branches to Successor #0. 5887 TerminatorInst *Succ1TI = BI->getSuccessor(1)->getTerminator(); 5888 if (Succ1TI->getNumSuccessors() == 1 && 5889 Succ1TI->getSuccessor(0) == BI->getSuccessor(0)) 5890 if (SpeculativelyExecuteBB(BI, BI->getSuccessor(1), TTI)) 5891 return simplifyCFG(BB, TTI, Options) | true; 5892 } 5893 5894 // If this is a branch on a phi node in the current block, thread control 5895 // through this block if any PHI node entries are constants. 5896 if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition())) 5897 if (PN->getParent() == BI->getParent()) 5898 if (FoldCondBranchOnPHI(BI, DL, Options.AC)) 5899 return simplifyCFG(BB, TTI, Options) | true; 5900 5901 // Scan predecessor blocks for conditional branches. 5902 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 5903 if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 5904 if (PBI != BI && PBI->isConditional()) 5905 if (SimplifyCondBranchToCondBranch(PBI, BI, DL)) 5906 return simplifyCFG(BB, TTI, Options) | true; 5907 5908 // Look for diamond patterns. 5909 if (MergeCondStores) 5910 if (BasicBlock *PrevBB = allPredecessorsComeFromSameSource(BB)) 5911 if (BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator())) 5912 if (PBI != BI && PBI->isConditional()) 5913 if (mergeConditionalStores(PBI, BI, DL)) 5914 return simplifyCFG(BB, TTI, Options) | true; 5915 5916 return false; 5917 } 5918 5919 /// Check if passing a value to an instruction will cause undefined behavior. 5920 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I) { 5921 Constant *C = dyn_cast<Constant>(V); 5922 if (!C) 5923 return false; 5924 5925 if (I->use_empty()) 5926 return false; 5927 5928 if (C->isNullValue() || isa<UndefValue>(C)) { 5929 // Only look at the first use, avoid hurting compile time with long uselists 5930 User *Use = *I->user_begin(); 5931 5932 // Now make sure that there are no instructions in between that can alter 5933 // control flow (eg. calls) 5934 for (BasicBlock::iterator 5935 i = ++BasicBlock::iterator(I), 5936 UI = BasicBlock::iterator(dyn_cast<Instruction>(Use)); 5937 i != UI; ++i) 5938 if (i == I->getParent()->end() || i->mayHaveSideEffects()) 5939 return false; 5940 5941 // Look through GEPs. A load from a GEP derived from NULL is still undefined 5942 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Use)) 5943 if (GEP->getPointerOperand() == I) 5944 return passingValueIsAlwaysUndefined(V, GEP); 5945 5946 // Look through bitcasts. 5947 if (BitCastInst *BC = dyn_cast<BitCastInst>(Use)) 5948 return passingValueIsAlwaysUndefined(V, BC); 5949 5950 // Load from null is undefined. 5951 if (LoadInst *LI = dyn_cast<LoadInst>(Use)) 5952 if (!LI->isVolatile()) 5953 return !NullPointerIsDefined(LI->getFunction(), 5954 LI->getPointerAddressSpace()); 5955 5956 // Store to null is undefined. 5957 if (StoreInst *SI = dyn_cast<StoreInst>(Use)) 5958 if (!SI->isVolatile()) 5959 return (!NullPointerIsDefined(SI->getFunction(), 5960 SI->getPointerAddressSpace())) && 5961 SI->getPointerOperand() == I; 5962 5963 // A call to null is undefined. 5964 if (auto CS = CallSite(Use)) 5965 return !NullPointerIsDefined(CS->getFunction()) && 5966 CS.getCalledValue() == I; 5967 } 5968 return false; 5969 } 5970 5971 /// If BB has an incoming value that will always trigger undefined behavior 5972 /// (eg. null pointer dereference), remove the branch leading here. 5973 static bool removeUndefIntroducingPredecessor(BasicBlock *BB) { 5974 for (PHINode &PHI : BB->phis()) 5975 for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) 5976 if (passingValueIsAlwaysUndefined(PHI.getIncomingValue(i), &PHI)) { 5977 TerminatorInst *T = PHI.getIncomingBlock(i)->getTerminator(); 5978 IRBuilder<> Builder(T); 5979 if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 5980 BB->removePredecessor(PHI.getIncomingBlock(i)); 5981 // Turn uncoditional branches into unreachables and remove the dead 5982 // destination from conditional branches. 5983 if (BI->isUnconditional()) 5984 Builder.CreateUnreachable(); 5985 else 5986 Builder.CreateBr(BI->getSuccessor(0) == BB ? BI->getSuccessor(1) 5987 : BI->getSuccessor(0)); 5988 BI->eraseFromParent(); 5989 return true; 5990 } 5991 // TODO: SwitchInst. 5992 } 5993 5994 return false; 5995 } 5996 5997 bool SimplifyCFGOpt::run(BasicBlock *BB) { 5998 bool Changed = false; 5999 6000 assert(BB && BB->getParent() && "Block not embedded in function!"); 6001 assert(BB->getTerminator() && "Degenerate basic block encountered!"); 6002 6003 // Remove basic blocks that have no predecessors (except the entry block)... 6004 // or that just have themself as a predecessor. These are unreachable. 6005 if ((pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()) || 6006 BB->getSinglePredecessor() == BB) { 6007 LLVM_DEBUG(dbgs() << "Removing BB: \n" << *BB); 6008 DeleteDeadBlock(BB); 6009 return true; 6010 } 6011 6012 // Check to see if we can constant propagate this terminator instruction 6013 // away... 6014 Changed |= ConstantFoldTerminator(BB, true); 6015 6016 // Check for and eliminate duplicate PHI nodes in this block. 6017 Changed |= EliminateDuplicatePHINodes(BB); 6018 6019 // Check for and remove branches that will always cause undefined behavior. 6020 Changed |= removeUndefIntroducingPredecessor(BB); 6021 6022 // Merge basic blocks into their predecessor if there is only one distinct 6023 // pred, and if there is only one distinct successor of the predecessor, and 6024 // if there are no PHI nodes. 6025 if (MergeBlockIntoPredecessor(BB)) 6026 return true; 6027 6028 if (SinkCommon && Options.SinkCommonInsts) 6029 Changed |= SinkCommonCodeFromPredecessors(BB); 6030 6031 IRBuilder<> Builder(BB); 6032 6033 // If there is a trivial two-entry PHI node in this basic block, and we can 6034 // eliminate it, do so now. 6035 if (auto *PN = dyn_cast<PHINode>(BB->begin())) 6036 if (PN->getNumIncomingValues() == 2) 6037 Changed |= FoldTwoEntryPHINode(PN, TTI, DL); 6038 6039 Builder.SetInsertPoint(BB->getTerminator()); 6040 if (auto *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 6041 if (BI->isUnconditional()) { 6042 if (SimplifyUncondBranch(BI, Builder)) 6043 return true; 6044 } else { 6045 if (SimplifyCondBranch(BI, Builder)) 6046 return true; 6047 } 6048 } else if (auto *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 6049 if (SimplifyReturn(RI, Builder)) 6050 return true; 6051 } else if (auto *RI = dyn_cast<ResumeInst>(BB->getTerminator())) { 6052 if (SimplifyResume(RI, Builder)) 6053 return true; 6054 } else if (auto *RI = dyn_cast<CleanupReturnInst>(BB->getTerminator())) { 6055 if (SimplifyCleanupReturn(RI)) 6056 return true; 6057 } else if (auto *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { 6058 if (SimplifySwitch(SI, Builder)) 6059 return true; 6060 } else if (auto *UI = dyn_cast<UnreachableInst>(BB->getTerminator())) { 6061 if (SimplifyUnreachable(UI)) 6062 return true; 6063 } else if (auto *IBI = dyn_cast<IndirectBrInst>(BB->getTerminator())) { 6064 if (SimplifyIndirectBr(IBI)) 6065 return true; 6066 } 6067 6068 return Changed; 6069 } 6070 6071 bool llvm::simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, 6072 const SimplifyCFGOptions &Options, 6073 SmallPtrSetImpl<BasicBlock *> *LoopHeaders) { 6074 return SimplifyCFGOpt(TTI, BB->getModule()->getDataLayout(), LoopHeaders, 6075 Options) 6076 .run(BB); 6077 } 6078