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