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