1 //===-- LoopPredication.cpp - Guard based loop predication pass -----------===// 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 // The LoopPredication pass tries to convert loop variant range checks to loop 10 // invariant by widening checks across loop iterations. For example, it will 11 // convert 12 // 13 // for (i = 0; i < n; i++) { 14 // guard(i < len); 15 // ... 16 // } 17 // 18 // to 19 // 20 // for (i = 0; i < n; i++) { 21 // guard(n - 1 < len); 22 // ... 23 // } 24 // 25 // After this transformation the condition of the guard is loop invariant, so 26 // loop-unswitch can later unswitch the loop by this condition which basically 27 // predicates the loop by the widened condition: 28 // 29 // if (n - 1 < len) 30 // for (i = 0; i < n; i++) { 31 // ... 32 // } 33 // else 34 // deoptimize 35 // 36 // It's tempting to rely on SCEV here, but it has proven to be problematic. 37 // Generally the facts SCEV provides about the increment step of add 38 // recurrences are true if the backedge of the loop is taken, which implicitly 39 // assumes that the guard doesn't fail. Using these facts to optimize the 40 // guard results in a circular logic where the guard is optimized under the 41 // assumption that it never fails. 42 // 43 // For example, in the loop below the induction variable will be marked as nuw 44 // basing on the guard. Basing on nuw the guard predicate will be considered 45 // monotonic. Given a monotonic condition it's tempting to replace the induction 46 // variable in the condition with its value on the last iteration. But this 47 // transformation is not correct, e.g. e = 4, b = 5 breaks the loop. 48 // 49 // for (int i = b; i != e; i++) 50 // guard(i u< len) 51 // 52 // One of the ways to reason about this problem is to use an inductive proof 53 // approach. Given the loop: 54 // 55 // if (B(0)) { 56 // do { 57 // I = PHI(0, I.INC) 58 // I.INC = I + Step 59 // guard(G(I)); 60 // } while (B(I)); 61 // } 62 // 63 // where B(x) and G(x) are predicates that map integers to booleans, we want a 64 // loop invariant expression M such the following program has the same semantics 65 // as the above: 66 // 67 // if (B(0)) { 68 // do { 69 // I = PHI(0, I.INC) 70 // I.INC = I + Step 71 // guard(G(0) && M); 72 // } while (B(I)); 73 // } 74 // 75 // One solution for M is M = forall X . (G(X) && B(X)) => G(X + Step) 76 // 77 // Informal proof that the transformation above is correct: 78 // 79 // By the definition of guards we can rewrite the guard condition to: 80 // G(I) && G(0) && M 81 // 82 // Let's prove that for each iteration of the loop: 83 // G(0) && M => G(I) 84 // And the condition above can be simplified to G(Start) && M. 85 // 86 // Induction base. 87 // G(0) && M => G(0) 88 // 89 // Induction step. Assuming G(0) && M => G(I) on the subsequent 90 // iteration: 91 // 92 // B(I) is true because it's the backedge condition. 93 // G(I) is true because the backedge is guarded by this condition. 94 // 95 // So M = forall X . (G(X) && B(X)) => G(X + Step) implies G(I + Step). 96 // 97 // Note that we can use anything stronger than M, i.e. any condition which 98 // implies M. 99 // 100 // When S = 1 (i.e. forward iterating loop), the transformation is supported 101 // when: 102 // * The loop has a single latch with the condition of the form: 103 // B(X) = latchStart + X <pred> latchLimit, 104 // where <pred> is u<, u<=, s<, or s<=. 105 // * The guard condition is of the form 106 // G(X) = guardStart + X u< guardLimit 107 // 108 // For the ult latch comparison case M is: 109 // forall X . guardStart + X u< guardLimit && latchStart + X <u latchLimit => 110 // guardStart + X + 1 u< guardLimit 111 // 112 // The only way the antecedent can be true and the consequent can be false is 113 // if 114 // X == guardLimit - 1 - guardStart 115 // (and guardLimit is non-zero, but we won't use this latter fact). 116 // If X == guardLimit - 1 - guardStart then the second half of the antecedent is 117 // latchStart + guardLimit - 1 - guardStart u< latchLimit 118 // and its negation is 119 // latchStart + guardLimit - 1 - guardStart u>= latchLimit 120 // 121 // In other words, if 122 // latchLimit u<= latchStart + guardLimit - 1 - guardStart 123 // then: 124 // (the ranges below are written in ConstantRange notation, where [A, B) is the 125 // set for (I = A; I != B; I++ /*maywrap*/) yield(I);) 126 // 127 // forall X . guardStart + X u< guardLimit && 128 // latchStart + X u< latchLimit => 129 // guardStart + X + 1 u< guardLimit 130 // == forall X . guardStart + X u< guardLimit && 131 // latchStart + X u< latchStart + guardLimit - 1 - guardStart => 132 // guardStart + X + 1 u< guardLimit 133 // == forall X . (guardStart + X) in [0, guardLimit) && 134 // (latchStart + X) in [0, latchStart + guardLimit - 1 - guardStart) => 135 // (guardStart + X + 1) in [0, guardLimit) 136 // == forall X . X in [-guardStart, guardLimit - guardStart) && 137 // X in [-latchStart, guardLimit - 1 - guardStart) => 138 // X in [-guardStart - 1, guardLimit - guardStart - 1) 139 // == true 140 // 141 // So the widened condition is: 142 // guardStart u< guardLimit && 143 // latchStart + guardLimit - 1 - guardStart u>= latchLimit 144 // Similarly for ule condition the widened condition is: 145 // guardStart u< guardLimit && 146 // latchStart + guardLimit - 1 - guardStart u> latchLimit 147 // For slt condition the widened condition is: 148 // guardStart u< guardLimit && 149 // latchStart + guardLimit - 1 - guardStart s>= latchLimit 150 // For sle condition the widened condition is: 151 // guardStart u< guardLimit && 152 // latchStart + guardLimit - 1 - guardStart s> latchLimit 153 // 154 // When S = -1 (i.e. reverse iterating loop), the transformation is supported 155 // when: 156 // * The loop has a single latch with the condition of the form: 157 // B(X) = X <pred> latchLimit, where <pred> is u>, u>=, s>, or s>=. 158 // * The guard condition is of the form 159 // G(X) = X - 1 u< guardLimit 160 // 161 // For the ugt latch comparison case M is: 162 // forall X. X-1 u< guardLimit and X u> latchLimit => X-2 u< guardLimit 163 // 164 // The only way the antecedent can be true and the consequent can be false is if 165 // X == 1. 166 // If X == 1 then the second half of the antecedent is 167 // 1 u> latchLimit, and its negation is latchLimit u>= 1. 168 // 169 // So the widened condition is: 170 // guardStart u< guardLimit && latchLimit u>= 1. 171 // Similarly for sgt condition the widened condition is: 172 // guardStart u< guardLimit && latchLimit s>= 1. 173 // For uge condition the widened condition is: 174 // guardStart u< guardLimit && latchLimit u> 1. 175 // For sge condition the widened condition is: 176 // guardStart u< guardLimit && latchLimit s> 1. 177 //===----------------------------------------------------------------------===// 178 179 #include "llvm/Transforms/Scalar/LoopPredication.h" 180 #include "llvm/ADT/Statistic.h" 181 #include "llvm/Analysis/AliasAnalysis.h" 182 #include "llvm/Analysis/BranchProbabilityInfo.h" 183 #include "llvm/Analysis/GuardUtils.h" 184 #include "llvm/Analysis/LoopInfo.h" 185 #include "llvm/Analysis/LoopPass.h" 186 #include "llvm/Analysis/MemorySSA.h" 187 #include "llvm/Analysis/MemorySSAUpdater.h" 188 #include "llvm/Analysis/ScalarEvolution.h" 189 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 190 #include "llvm/IR/Function.h" 191 #include "llvm/IR/IntrinsicInst.h" 192 #include "llvm/IR/Module.h" 193 #include "llvm/IR/PatternMatch.h" 194 #include "llvm/IR/ProfDataUtils.h" 195 #include "llvm/InitializePasses.h" 196 #include "llvm/Pass.h" 197 #include "llvm/Support/CommandLine.h" 198 #include "llvm/Support/Debug.h" 199 #include "llvm/Transforms/Scalar.h" 200 #include "llvm/Transforms/Utils/GuardUtils.h" 201 #include "llvm/Transforms/Utils/Local.h" 202 #include "llvm/Transforms/Utils/LoopUtils.h" 203 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" 204 #include <optional> 205 206 #define DEBUG_TYPE "loop-predication" 207 208 STATISTIC(TotalConsidered, "Number of guards considered"); 209 STATISTIC(TotalWidened, "Number of checks widened"); 210 211 using namespace llvm; 212 213 static cl::opt<bool> EnableIVTruncation("loop-predication-enable-iv-truncation", 214 cl::Hidden, cl::init(true)); 215 216 static cl::opt<bool> EnableCountDownLoop("loop-predication-enable-count-down-loop", 217 cl::Hidden, cl::init(true)); 218 219 static cl::opt<bool> 220 SkipProfitabilityChecks("loop-predication-skip-profitability-checks", 221 cl::Hidden, cl::init(false)); 222 223 // This is the scale factor for the latch probability. We use this during 224 // profitability analysis to find other exiting blocks that have a much higher 225 // probability of exiting the loop instead of loop exiting via latch. 226 // This value should be greater than 1 for a sane profitability check. 227 static cl::opt<float> LatchExitProbabilityScale( 228 "loop-predication-latch-probability-scale", cl::Hidden, cl::init(2.0), 229 cl::desc("scale factor for the latch probability. Value should be greater " 230 "than 1. Lower values are ignored")); 231 232 static cl::opt<bool> PredicateWidenableBranchGuards( 233 "loop-predication-predicate-widenable-branches-to-deopt", cl::Hidden, 234 cl::desc("Whether or not we should predicate guards " 235 "expressed as widenable branches to deoptimize blocks"), 236 cl::init(true)); 237 238 static cl::opt<bool> InsertAssumesOfPredicatedGuardsConditions( 239 "loop-predication-insert-assumes-of-predicated-guards-conditions", 240 cl::Hidden, 241 cl::desc("Whether or not we should insert assumes of conditions of " 242 "predicated guards"), 243 cl::init(true)); 244 245 namespace { 246 /// Represents an induction variable check: 247 /// icmp Pred, <induction variable>, <loop invariant limit> 248 struct LoopICmp { 249 ICmpInst::Predicate Pred; 250 const SCEVAddRecExpr *IV; 251 const SCEV *Limit; 252 LoopICmp(ICmpInst::Predicate Pred, const SCEVAddRecExpr *IV, 253 const SCEV *Limit) 254 : Pred(Pred), IV(IV), Limit(Limit) {} 255 LoopICmp() = default; 256 void dump() { 257 dbgs() << "LoopICmp Pred = " << Pred << ", IV = " << *IV 258 << ", Limit = " << *Limit << "\n"; 259 } 260 }; 261 262 class LoopPredication { 263 AliasAnalysis *AA; 264 DominatorTree *DT; 265 ScalarEvolution *SE; 266 LoopInfo *LI; 267 MemorySSAUpdater *MSSAU; 268 269 Loop *L; 270 const DataLayout *DL; 271 BasicBlock *Preheader; 272 LoopICmp LatchCheck; 273 274 bool isSupportedStep(const SCEV* Step); 275 std::optional<LoopICmp> parseLoopICmp(ICmpInst *ICI); 276 std::optional<LoopICmp> parseLoopLatchICmp(); 277 278 /// Return an insertion point suitable for inserting a safe to speculate 279 /// instruction whose only user will be 'User' which has operands 'Ops'. A 280 /// trivial result would be the at the User itself, but we try to return a 281 /// loop invariant location if possible. 282 Instruction *findInsertPt(Instruction *User, ArrayRef<Value*> Ops); 283 /// Same as above, *except* that this uses the SCEV definition of invariant 284 /// which is that an expression *can be made* invariant via SCEVExpander. 285 /// Thus, this version is only suitable for finding an insert point to be be 286 /// passed to SCEVExpander! 287 Instruction *findInsertPt(const SCEVExpander &Expander, Instruction *User, 288 ArrayRef<const SCEV *> Ops); 289 290 /// Return true if the value is known to produce a single fixed value across 291 /// all iterations on which it executes. Note that this does not imply 292 /// speculation safety. That must be established separately. 293 bool isLoopInvariantValue(const SCEV* S); 294 295 Value *expandCheck(SCEVExpander &Expander, Instruction *Guard, 296 ICmpInst::Predicate Pred, const SCEV *LHS, 297 const SCEV *RHS); 298 299 std::optional<Value *> widenICmpRangeCheck(ICmpInst *ICI, 300 SCEVExpander &Expander, 301 Instruction *Guard); 302 std::optional<Value *> 303 widenICmpRangeCheckIncrementingLoop(LoopICmp LatchCheck, LoopICmp RangeCheck, 304 SCEVExpander &Expander, 305 Instruction *Guard); 306 std::optional<Value *> 307 widenICmpRangeCheckDecrementingLoop(LoopICmp LatchCheck, LoopICmp RangeCheck, 308 SCEVExpander &Expander, 309 Instruction *Guard); 310 unsigned collectChecks(SmallVectorImpl<Value *> &Checks, Value *Condition, 311 SCEVExpander &Expander, Instruction *Guard); 312 bool widenGuardConditions(IntrinsicInst *II, SCEVExpander &Expander); 313 bool widenWidenableBranchGuardConditions(BranchInst *Guard, SCEVExpander &Expander); 314 // If the loop always exits through another block in the loop, we should not 315 // predicate based on the latch check. For example, the latch check can be a 316 // very coarse grained check and there can be more fine grained exit checks 317 // within the loop. 318 bool isLoopProfitableToPredicate(); 319 320 bool predicateLoopExits(Loop *L, SCEVExpander &Rewriter); 321 322 public: 323 LoopPredication(AliasAnalysis *AA, DominatorTree *DT, ScalarEvolution *SE, 324 LoopInfo *LI, MemorySSAUpdater *MSSAU) 325 : AA(AA), DT(DT), SE(SE), LI(LI), MSSAU(MSSAU){}; 326 bool runOnLoop(Loop *L); 327 }; 328 329 class LoopPredicationLegacyPass : public LoopPass { 330 public: 331 static char ID; 332 LoopPredicationLegacyPass() : LoopPass(ID) { 333 initializeLoopPredicationLegacyPassPass(*PassRegistry::getPassRegistry()); 334 } 335 336 void getAnalysisUsage(AnalysisUsage &AU) const override { 337 AU.addRequired<BranchProbabilityInfoWrapperPass>(); 338 getLoopAnalysisUsage(AU); 339 AU.addPreserved<MemorySSAWrapperPass>(); 340 } 341 342 bool runOnLoop(Loop *L, LPPassManager &LPM) override { 343 if (skipLoop(L)) 344 return false; 345 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 346 auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 347 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 348 auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>(); 349 std::unique_ptr<MemorySSAUpdater> MSSAU; 350 if (MSSAWP) 351 MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAWP->getMSSA()); 352 auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); 353 LoopPredication LP(AA, DT, SE, LI, MSSAU ? MSSAU.get() : nullptr); 354 return LP.runOnLoop(L); 355 } 356 }; 357 358 char LoopPredicationLegacyPass::ID = 0; 359 } // end namespace 360 361 INITIALIZE_PASS_BEGIN(LoopPredicationLegacyPass, "loop-predication", 362 "Loop predication", false, false) 363 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass) 364 INITIALIZE_PASS_DEPENDENCY(LoopPass) 365 INITIALIZE_PASS_END(LoopPredicationLegacyPass, "loop-predication", 366 "Loop predication", false, false) 367 368 Pass *llvm::createLoopPredicationPass() { 369 return new LoopPredicationLegacyPass(); 370 } 371 372 PreservedAnalyses LoopPredicationPass::run(Loop &L, LoopAnalysisManager &AM, 373 LoopStandardAnalysisResults &AR, 374 LPMUpdater &U) { 375 std::unique_ptr<MemorySSAUpdater> MSSAU; 376 if (AR.MSSA) 377 MSSAU = std::make_unique<MemorySSAUpdater>(AR.MSSA); 378 LoopPredication LP(&AR.AA, &AR.DT, &AR.SE, &AR.LI, 379 MSSAU ? MSSAU.get() : nullptr); 380 if (!LP.runOnLoop(&L)) 381 return PreservedAnalyses::all(); 382 383 auto PA = getLoopPassPreservedAnalyses(); 384 if (AR.MSSA) 385 PA.preserve<MemorySSAAnalysis>(); 386 return PA; 387 } 388 389 std::optional<LoopICmp> LoopPredication::parseLoopICmp(ICmpInst *ICI) { 390 auto Pred = ICI->getPredicate(); 391 auto *LHS = ICI->getOperand(0); 392 auto *RHS = ICI->getOperand(1); 393 394 const SCEV *LHSS = SE->getSCEV(LHS); 395 if (isa<SCEVCouldNotCompute>(LHSS)) 396 return std::nullopt; 397 const SCEV *RHSS = SE->getSCEV(RHS); 398 if (isa<SCEVCouldNotCompute>(RHSS)) 399 return std::nullopt; 400 401 // Canonicalize RHS to be loop invariant bound, LHS - a loop computable IV 402 if (SE->isLoopInvariant(LHSS, L)) { 403 std::swap(LHS, RHS); 404 std::swap(LHSS, RHSS); 405 Pred = ICmpInst::getSwappedPredicate(Pred); 406 } 407 408 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHSS); 409 if (!AR || AR->getLoop() != L) 410 return std::nullopt; 411 412 return LoopICmp(Pred, AR, RHSS); 413 } 414 415 Value *LoopPredication::expandCheck(SCEVExpander &Expander, 416 Instruction *Guard, 417 ICmpInst::Predicate Pred, const SCEV *LHS, 418 const SCEV *RHS) { 419 Type *Ty = LHS->getType(); 420 assert(Ty == RHS->getType() && "expandCheck operands have different types?"); 421 422 if (SE->isLoopInvariant(LHS, L) && SE->isLoopInvariant(RHS, L)) { 423 IRBuilder<> Builder(Guard); 424 if (SE->isLoopEntryGuardedByCond(L, Pred, LHS, RHS)) 425 return Builder.getTrue(); 426 if (SE->isLoopEntryGuardedByCond(L, ICmpInst::getInversePredicate(Pred), 427 LHS, RHS)) 428 return Builder.getFalse(); 429 } 430 431 Value *LHSV = 432 Expander.expandCodeFor(LHS, Ty, findInsertPt(Expander, Guard, {LHS})); 433 Value *RHSV = 434 Expander.expandCodeFor(RHS, Ty, findInsertPt(Expander, Guard, {RHS})); 435 IRBuilder<> Builder(findInsertPt(Guard, {LHSV, RHSV})); 436 return Builder.CreateICmp(Pred, LHSV, RHSV); 437 } 438 439 // Returns true if its safe to truncate the IV to RangeCheckType. 440 // When the IV type is wider than the range operand type, we can still do loop 441 // predication, by generating SCEVs for the range and latch that are of the 442 // same type. We achieve this by generating a SCEV truncate expression for the 443 // latch IV. This is done iff truncation of the IV is a safe operation, 444 // without loss of information. 445 // Another way to achieve this is by generating a wider type SCEV for the 446 // range check operand, however, this needs a more involved check that 447 // operands do not overflow. This can lead to loss of information when the 448 // range operand is of the form: add i32 %offset, %iv. We need to prove that 449 // sext(x + y) is same as sext(x) + sext(y). 450 // This function returns true if we can safely represent the IV type in 451 // the RangeCheckType without loss of information. 452 static bool isSafeToTruncateWideIVType(const DataLayout &DL, 453 ScalarEvolution &SE, 454 const LoopICmp LatchCheck, 455 Type *RangeCheckType) { 456 if (!EnableIVTruncation) 457 return false; 458 assert(DL.getTypeSizeInBits(LatchCheck.IV->getType()).getFixedValue() > 459 DL.getTypeSizeInBits(RangeCheckType).getFixedValue() && 460 "Expected latch check IV type to be larger than range check operand " 461 "type!"); 462 // The start and end values of the IV should be known. This is to guarantee 463 // that truncating the wide type will not lose information. 464 auto *Limit = dyn_cast<SCEVConstant>(LatchCheck.Limit); 465 auto *Start = dyn_cast<SCEVConstant>(LatchCheck.IV->getStart()); 466 if (!Limit || !Start) 467 return false; 468 // This check makes sure that the IV does not change sign during loop 469 // iterations. Consider latchType = i64, LatchStart = 5, Pred = ICMP_SGE, 470 // LatchEnd = 2, rangeCheckType = i32. If it's not a monotonic predicate, the 471 // IV wraps around, and the truncation of the IV would lose the range of 472 // iterations between 2^32 and 2^64. 473 if (!SE.getMonotonicPredicateType(LatchCheck.IV, LatchCheck.Pred)) 474 return false; 475 // The active bits should be less than the bits in the RangeCheckType. This 476 // guarantees that truncating the latch check to RangeCheckType is a safe 477 // operation. 478 auto RangeCheckTypeBitSize = 479 DL.getTypeSizeInBits(RangeCheckType).getFixedValue(); 480 return Start->getAPInt().getActiveBits() < RangeCheckTypeBitSize && 481 Limit->getAPInt().getActiveBits() < RangeCheckTypeBitSize; 482 } 483 484 485 // Return an LoopICmp describing a latch check equivlent to LatchCheck but with 486 // the requested type if safe to do so. May involve the use of a new IV. 487 static std::optional<LoopICmp> generateLoopLatchCheck(const DataLayout &DL, 488 ScalarEvolution &SE, 489 const LoopICmp LatchCheck, 490 Type *RangeCheckType) { 491 492 auto *LatchType = LatchCheck.IV->getType(); 493 if (RangeCheckType == LatchType) 494 return LatchCheck; 495 // For now, bail out if latch type is narrower than range type. 496 if (DL.getTypeSizeInBits(LatchType).getFixedValue() < 497 DL.getTypeSizeInBits(RangeCheckType).getFixedValue()) 498 return std::nullopt; 499 if (!isSafeToTruncateWideIVType(DL, SE, LatchCheck, RangeCheckType)) 500 return std::nullopt; 501 // We can now safely identify the truncated version of the IV and limit for 502 // RangeCheckType. 503 LoopICmp NewLatchCheck; 504 NewLatchCheck.Pred = LatchCheck.Pred; 505 NewLatchCheck.IV = dyn_cast<SCEVAddRecExpr>( 506 SE.getTruncateExpr(LatchCheck.IV, RangeCheckType)); 507 if (!NewLatchCheck.IV) 508 return std::nullopt; 509 NewLatchCheck.Limit = SE.getTruncateExpr(LatchCheck.Limit, RangeCheckType); 510 LLVM_DEBUG(dbgs() << "IV of type: " << *LatchType 511 << "can be represented as range check type:" 512 << *RangeCheckType << "\n"); 513 LLVM_DEBUG(dbgs() << "LatchCheck.IV: " << *NewLatchCheck.IV << "\n"); 514 LLVM_DEBUG(dbgs() << "LatchCheck.Limit: " << *NewLatchCheck.Limit << "\n"); 515 return NewLatchCheck; 516 } 517 518 bool LoopPredication::isSupportedStep(const SCEV* Step) { 519 return Step->isOne() || (Step->isAllOnesValue() && EnableCountDownLoop); 520 } 521 522 Instruction *LoopPredication::findInsertPt(Instruction *Use, 523 ArrayRef<Value*> Ops) { 524 for (Value *Op : Ops) 525 if (!L->isLoopInvariant(Op)) 526 return Use; 527 return Preheader->getTerminator(); 528 } 529 530 Instruction *LoopPredication::findInsertPt(const SCEVExpander &Expander, 531 Instruction *Use, 532 ArrayRef<const SCEV *> Ops) { 533 // Subtlety: SCEV considers things to be invariant if the value produced is 534 // the same across iterations. This is not the same as being able to 535 // evaluate outside the loop, which is what we actually need here. 536 for (const SCEV *Op : Ops) 537 if (!SE->isLoopInvariant(Op, L) || 538 !Expander.isSafeToExpandAt(Op, Preheader->getTerminator())) 539 return Use; 540 return Preheader->getTerminator(); 541 } 542 543 bool LoopPredication::isLoopInvariantValue(const SCEV* S) { 544 // Handling expressions which produce invariant results, but *haven't* yet 545 // been removed from the loop serves two important purposes. 546 // 1) Most importantly, it resolves a pass ordering cycle which would 547 // otherwise need us to iteration licm, loop-predication, and either 548 // loop-unswitch or loop-peeling to make progress on examples with lots of 549 // predicable range checks in a row. (Since, in the general case, we can't 550 // hoist the length checks until the dominating checks have been discharged 551 // as we can't prove doing so is safe.) 552 // 2) As a nice side effect, this exposes the value of peeling or unswitching 553 // much more obviously in the IR. Otherwise, the cost modeling for other 554 // transforms would end up needing to duplicate all of this logic to model a 555 // check which becomes predictable based on a modeled peel or unswitch. 556 // 557 // The cost of doing so in the worst case is an extra fill from the stack in 558 // the loop to materialize the loop invariant test value instead of checking 559 // against the original IV which is presumable in a register inside the loop. 560 // Such cases are presumably rare, and hint at missing oppurtunities for 561 // other passes. 562 563 if (SE->isLoopInvariant(S, L)) 564 // Note: This the SCEV variant, so the original Value* may be within the 565 // loop even though SCEV has proven it is loop invariant. 566 return true; 567 568 // Handle a particular important case which SCEV doesn't yet know about which 569 // shows up in range checks on arrays with immutable lengths. 570 // TODO: This should be sunk inside SCEV. 571 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) 572 if (const auto *LI = dyn_cast<LoadInst>(U->getValue())) 573 if (LI->isUnordered() && L->hasLoopInvariantOperands(LI)) 574 if (!isModSet(AA->getModRefInfoMask(LI->getOperand(0))) || 575 LI->hasMetadata(LLVMContext::MD_invariant_load)) 576 return true; 577 return false; 578 } 579 580 std::optional<Value *> LoopPredication::widenICmpRangeCheckIncrementingLoop( 581 LoopICmp LatchCheck, LoopICmp RangeCheck, SCEVExpander &Expander, 582 Instruction *Guard) { 583 auto *Ty = RangeCheck.IV->getType(); 584 // Generate the widened condition for the forward loop: 585 // guardStart u< guardLimit && 586 // latchLimit <pred> guardLimit - 1 - guardStart + latchStart 587 // where <pred> depends on the latch condition predicate. See the file 588 // header comment for the reasoning. 589 // guardLimit - guardStart + latchStart - 1 590 const SCEV *GuardStart = RangeCheck.IV->getStart(); 591 const SCEV *GuardLimit = RangeCheck.Limit; 592 const SCEV *LatchStart = LatchCheck.IV->getStart(); 593 const SCEV *LatchLimit = LatchCheck.Limit; 594 // Subtlety: We need all the values to be *invariant* across all iterations, 595 // but we only need to check expansion safety for those which *aren't* 596 // already guaranteed to dominate the guard. 597 if (!isLoopInvariantValue(GuardStart) || 598 !isLoopInvariantValue(GuardLimit) || 599 !isLoopInvariantValue(LatchStart) || 600 !isLoopInvariantValue(LatchLimit)) { 601 LLVM_DEBUG(dbgs() << "Can't expand limit check!\n"); 602 return std::nullopt; 603 } 604 if (!Expander.isSafeToExpandAt(LatchStart, Guard) || 605 !Expander.isSafeToExpandAt(LatchLimit, Guard)) { 606 LLVM_DEBUG(dbgs() << "Can't expand limit check!\n"); 607 return std::nullopt; 608 } 609 610 // guardLimit - guardStart + latchStart - 1 611 const SCEV *RHS = 612 SE->getAddExpr(SE->getMinusSCEV(GuardLimit, GuardStart), 613 SE->getMinusSCEV(LatchStart, SE->getOne(Ty))); 614 auto LimitCheckPred = 615 ICmpInst::getFlippedStrictnessPredicate(LatchCheck.Pred); 616 617 LLVM_DEBUG(dbgs() << "LHS: " << *LatchLimit << "\n"); 618 LLVM_DEBUG(dbgs() << "RHS: " << *RHS << "\n"); 619 LLVM_DEBUG(dbgs() << "Pred: " << LimitCheckPred << "\n"); 620 621 auto *LimitCheck = 622 expandCheck(Expander, Guard, LimitCheckPred, LatchLimit, RHS); 623 auto *FirstIterationCheck = expandCheck(Expander, Guard, RangeCheck.Pred, 624 GuardStart, GuardLimit); 625 IRBuilder<> Builder(findInsertPt(Guard, {FirstIterationCheck, LimitCheck})); 626 return Builder.CreateAnd(FirstIterationCheck, LimitCheck); 627 } 628 629 std::optional<Value *> LoopPredication::widenICmpRangeCheckDecrementingLoop( 630 LoopICmp LatchCheck, LoopICmp RangeCheck, SCEVExpander &Expander, 631 Instruction *Guard) { 632 auto *Ty = RangeCheck.IV->getType(); 633 const SCEV *GuardStart = RangeCheck.IV->getStart(); 634 const SCEV *GuardLimit = RangeCheck.Limit; 635 const SCEV *LatchStart = LatchCheck.IV->getStart(); 636 const SCEV *LatchLimit = LatchCheck.Limit; 637 // Subtlety: We need all the values to be *invariant* across all iterations, 638 // but we only need to check expansion safety for those which *aren't* 639 // already guaranteed to dominate the guard. 640 if (!isLoopInvariantValue(GuardStart) || 641 !isLoopInvariantValue(GuardLimit) || 642 !isLoopInvariantValue(LatchStart) || 643 !isLoopInvariantValue(LatchLimit)) { 644 LLVM_DEBUG(dbgs() << "Can't expand limit check!\n"); 645 return std::nullopt; 646 } 647 if (!Expander.isSafeToExpandAt(LatchStart, Guard) || 648 !Expander.isSafeToExpandAt(LatchLimit, Guard)) { 649 LLVM_DEBUG(dbgs() << "Can't expand limit check!\n"); 650 return std::nullopt; 651 } 652 // The decrement of the latch check IV should be the same as the 653 // rangeCheckIV. 654 auto *PostDecLatchCheckIV = LatchCheck.IV->getPostIncExpr(*SE); 655 if (RangeCheck.IV != PostDecLatchCheckIV) { 656 LLVM_DEBUG(dbgs() << "Not the same. PostDecLatchCheckIV: " 657 << *PostDecLatchCheckIV 658 << " and RangeCheckIV: " << *RangeCheck.IV << "\n"); 659 return std::nullopt; 660 } 661 662 // Generate the widened condition for CountDownLoop: 663 // guardStart u< guardLimit && 664 // latchLimit <pred> 1. 665 // See the header comment for reasoning of the checks. 666 auto LimitCheckPred = 667 ICmpInst::getFlippedStrictnessPredicate(LatchCheck.Pred); 668 auto *FirstIterationCheck = expandCheck(Expander, Guard, 669 ICmpInst::ICMP_ULT, 670 GuardStart, GuardLimit); 671 auto *LimitCheck = expandCheck(Expander, Guard, LimitCheckPred, LatchLimit, 672 SE->getOne(Ty)); 673 IRBuilder<> Builder(findInsertPt(Guard, {FirstIterationCheck, LimitCheck})); 674 return Builder.CreateAnd(FirstIterationCheck, LimitCheck); 675 } 676 677 static void normalizePredicate(ScalarEvolution *SE, Loop *L, 678 LoopICmp& RC) { 679 // LFTR canonicalizes checks to the ICMP_NE/EQ form; normalize back to the 680 // ULT/UGE form for ease of handling by our caller. 681 if (ICmpInst::isEquality(RC.Pred) && 682 RC.IV->getStepRecurrence(*SE)->isOne() && 683 SE->isKnownPredicate(ICmpInst::ICMP_ULE, RC.IV->getStart(), RC.Limit)) 684 RC.Pred = RC.Pred == ICmpInst::ICMP_NE ? 685 ICmpInst::ICMP_ULT : ICmpInst::ICMP_UGE; 686 } 687 688 /// If ICI can be widened to a loop invariant condition emits the loop 689 /// invariant condition in the loop preheader and return it, otherwise 690 /// returns std::nullopt. 691 std::optional<Value *> 692 LoopPredication::widenICmpRangeCheck(ICmpInst *ICI, SCEVExpander &Expander, 693 Instruction *Guard) { 694 LLVM_DEBUG(dbgs() << "Analyzing ICmpInst condition:\n"); 695 LLVM_DEBUG(ICI->dump()); 696 697 // parseLoopStructure guarantees that the latch condition is: 698 // ++i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=. 699 // We are looking for the range checks of the form: 700 // i u< guardLimit 701 auto RangeCheck = parseLoopICmp(ICI); 702 if (!RangeCheck) { 703 LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n"); 704 return std::nullopt; 705 } 706 LLVM_DEBUG(dbgs() << "Guard check:\n"); 707 LLVM_DEBUG(RangeCheck->dump()); 708 if (RangeCheck->Pred != ICmpInst::ICMP_ULT) { 709 LLVM_DEBUG(dbgs() << "Unsupported range check predicate(" 710 << RangeCheck->Pred << ")!\n"); 711 return std::nullopt; 712 } 713 auto *RangeCheckIV = RangeCheck->IV; 714 if (!RangeCheckIV->isAffine()) { 715 LLVM_DEBUG(dbgs() << "Range check IV is not affine!\n"); 716 return std::nullopt; 717 } 718 auto *Step = RangeCheckIV->getStepRecurrence(*SE); 719 // We cannot just compare with latch IV step because the latch and range IVs 720 // may have different types. 721 if (!isSupportedStep(Step)) { 722 LLVM_DEBUG(dbgs() << "Range check and latch have IVs different steps!\n"); 723 return std::nullopt; 724 } 725 auto *Ty = RangeCheckIV->getType(); 726 auto CurrLatchCheckOpt = generateLoopLatchCheck(*DL, *SE, LatchCheck, Ty); 727 if (!CurrLatchCheckOpt) { 728 LLVM_DEBUG(dbgs() << "Failed to generate a loop latch check " 729 "corresponding to range type: " 730 << *Ty << "\n"); 731 return std::nullopt; 732 } 733 734 LoopICmp CurrLatchCheck = *CurrLatchCheckOpt; 735 // At this point, the range and latch step should have the same type, but need 736 // not have the same value (we support both 1 and -1 steps). 737 assert(Step->getType() == 738 CurrLatchCheck.IV->getStepRecurrence(*SE)->getType() && 739 "Range and latch steps should be of same type!"); 740 if (Step != CurrLatchCheck.IV->getStepRecurrence(*SE)) { 741 LLVM_DEBUG(dbgs() << "Range and latch have different step values!\n"); 742 return std::nullopt; 743 } 744 745 if (Step->isOne()) 746 return widenICmpRangeCheckIncrementingLoop(CurrLatchCheck, *RangeCheck, 747 Expander, Guard); 748 else { 749 assert(Step->isAllOnesValue() && "Step should be -1!"); 750 return widenICmpRangeCheckDecrementingLoop(CurrLatchCheck, *RangeCheck, 751 Expander, Guard); 752 } 753 } 754 755 unsigned LoopPredication::collectChecks(SmallVectorImpl<Value *> &Checks, 756 Value *Condition, 757 SCEVExpander &Expander, 758 Instruction *Guard) { 759 unsigned NumWidened = 0; 760 // The guard condition is expected to be in form of: 761 // cond1 && cond2 && cond3 ... 762 // Iterate over subconditions looking for icmp conditions which can be 763 // widened across loop iterations. Widening these conditions remember the 764 // resulting list of subconditions in Checks vector. 765 SmallVector<Value *, 4> Worklist(1, Condition); 766 SmallPtrSet<Value *, 4> Visited; 767 Visited.insert(Condition); 768 Value *WideableCond = nullptr; 769 do { 770 Value *Condition = Worklist.pop_back_val(); 771 Value *LHS, *RHS; 772 using namespace llvm::PatternMatch; 773 if (match(Condition, m_And(m_Value(LHS), m_Value(RHS)))) { 774 if (Visited.insert(LHS).second) 775 Worklist.push_back(LHS); 776 if (Visited.insert(RHS).second) 777 Worklist.push_back(RHS); 778 continue; 779 } 780 781 if (match(Condition, 782 m_Intrinsic<Intrinsic::experimental_widenable_condition>())) { 783 // Pick any, we don't care which 784 WideableCond = Condition; 785 continue; 786 } 787 788 if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) { 789 if (auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander, 790 Guard)) { 791 Checks.push_back(*NewRangeCheck); 792 NumWidened++; 793 continue; 794 } 795 } 796 797 // Save the condition as is if we can't widen it 798 Checks.push_back(Condition); 799 } while (!Worklist.empty()); 800 // At the moment, our matching logic for wideable conditions implicitly 801 // assumes we preserve the form: (br (and Cond, WC())). FIXME 802 // Note that if there were multiple calls to wideable condition in the 803 // traversal, we only need to keep one, and which one is arbitrary. 804 if (WideableCond) 805 Checks.push_back(WideableCond); 806 return NumWidened; 807 } 808 809 bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard, 810 SCEVExpander &Expander) { 811 LLVM_DEBUG(dbgs() << "Processing guard:\n"); 812 LLVM_DEBUG(Guard->dump()); 813 814 TotalConsidered++; 815 SmallVector<Value *, 4> Checks; 816 unsigned NumWidened = collectChecks(Checks, Guard->getOperand(0), Expander, 817 Guard); 818 if (NumWidened == 0) 819 return false; 820 821 TotalWidened += NumWidened; 822 823 // Emit the new guard condition 824 IRBuilder<> Builder(findInsertPt(Guard, Checks)); 825 Value *AllChecks = Builder.CreateAnd(Checks); 826 auto *OldCond = Guard->getOperand(0); 827 Guard->setOperand(0, AllChecks); 828 if (InsertAssumesOfPredicatedGuardsConditions) { 829 Builder.SetInsertPoint(&*++BasicBlock::iterator(Guard)); 830 Builder.CreateAssumption(OldCond); 831 } 832 RecursivelyDeleteTriviallyDeadInstructions(OldCond, nullptr /* TLI */, MSSAU); 833 834 LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n"); 835 return true; 836 } 837 838 bool LoopPredication::widenWidenableBranchGuardConditions( 839 BranchInst *BI, SCEVExpander &Expander) { 840 assert(isGuardAsWidenableBranch(BI) && "Must be!"); 841 LLVM_DEBUG(dbgs() << "Processing guard:\n"); 842 LLVM_DEBUG(BI->dump()); 843 844 Value *Cond, *WC; 845 BasicBlock *IfTrueBB, *IfFalseBB; 846 bool Parsed = parseWidenableBranch(BI, Cond, WC, IfTrueBB, IfFalseBB); 847 assert(Parsed && "Must be able to parse widenable branch"); 848 (void)Parsed; 849 850 TotalConsidered++; 851 SmallVector<Value *, 4> Checks; 852 unsigned NumWidened = collectChecks(Checks, BI->getCondition(), 853 Expander, BI); 854 if (NumWidened == 0) 855 return false; 856 857 TotalWidened += NumWidened; 858 859 // Emit the new guard condition 860 IRBuilder<> Builder(findInsertPt(BI, Checks)); 861 Value *AllChecks = Builder.CreateAnd(Checks); 862 auto *OldCond = BI->getCondition(); 863 BI->setCondition(AllChecks); 864 if (InsertAssumesOfPredicatedGuardsConditions) { 865 Builder.SetInsertPoint(IfTrueBB, IfTrueBB->getFirstInsertionPt()); 866 Builder.CreateAssumption(Cond); 867 } 868 RecursivelyDeleteTriviallyDeadInstructions(OldCond, nullptr /* TLI */, MSSAU); 869 assert(isGuardAsWidenableBranch(BI) && 870 "Stopped being a guard after transform?"); 871 872 LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n"); 873 return true; 874 } 875 876 std::optional<LoopICmp> LoopPredication::parseLoopLatchICmp() { 877 using namespace PatternMatch; 878 879 BasicBlock *LoopLatch = L->getLoopLatch(); 880 if (!LoopLatch) { 881 LLVM_DEBUG(dbgs() << "The loop doesn't have a single latch!\n"); 882 return std::nullopt; 883 } 884 885 auto *BI = dyn_cast<BranchInst>(LoopLatch->getTerminator()); 886 if (!BI || !BI->isConditional()) { 887 LLVM_DEBUG(dbgs() << "Failed to match the latch terminator!\n"); 888 return std::nullopt; 889 } 890 BasicBlock *TrueDest = BI->getSuccessor(0); 891 assert( 892 (TrueDest == L->getHeader() || BI->getSuccessor(1) == L->getHeader()) && 893 "One of the latch's destinations must be the header"); 894 895 auto *ICI = dyn_cast<ICmpInst>(BI->getCondition()); 896 if (!ICI) { 897 LLVM_DEBUG(dbgs() << "Failed to match the latch condition!\n"); 898 return std::nullopt; 899 } 900 auto Result = parseLoopICmp(ICI); 901 if (!Result) { 902 LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n"); 903 return std::nullopt; 904 } 905 906 if (TrueDest != L->getHeader()) 907 Result->Pred = ICmpInst::getInversePredicate(Result->Pred); 908 909 // Check affine first, so if it's not we don't try to compute the step 910 // recurrence. 911 if (!Result->IV->isAffine()) { 912 LLVM_DEBUG(dbgs() << "The induction variable is not affine!\n"); 913 return std::nullopt; 914 } 915 916 auto *Step = Result->IV->getStepRecurrence(*SE); 917 if (!isSupportedStep(Step)) { 918 LLVM_DEBUG(dbgs() << "Unsupported loop stride(" << *Step << ")!\n"); 919 return std::nullopt; 920 } 921 922 auto IsUnsupportedPredicate = [](const SCEV *Step, ICmpInst::Predicate Pred) { 923 if (Step->isOne()) { 924 return Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_SLT && 925 Pred != ICmpInst::ICMP_ULE && Pred != ICmpInst::ICMP_SLE; 926 } else { 927 assert(Step->isAllOnesValue() && "Step should be -1!"); 928 return Pred != ICmpInst::ICMP_UGT && Pred != ICmpInst::ICMP_SGT && 929 Pred != ICmpInst::ICMP_UGE && Pred != ICmpInst::ICMP_SGE; 930 } 931 }; 932 933 normalizePredicate(SE, L, *Result); 934 if (IsUnsupportedPredicate(Step, Result->Pred)) { 935 LLVM_DEBUG(dbgs() << "Unsupported loop latch predicate(" << Result->Pred 936 << ")!\n"); 937 return std::nullopt; 938 } 939 940 return Result; 941 } 942 943 bool LoopPredication::isLoopProfitableToPredicate() { 944 if (SkipProfitabilityChecks) 945 return true; 946 947 SmallVector<std::pair<BasicBlock *, BasicBlock *>, 8> ExitEdges; 948 L->getExitEdges(ExitEdges); 949 // If there is only one exiting edge in the loop, it is always profitable to 950 // predicate the loop. 951 if (ExitEdges.size() == 1) 952 return true; 953 954 // Calculate the exiting probabilities of all exiting edges from the loop, 955 // starting with the LatchExitProbability. 956 // Heuristic for profitability: If any of the exiting blocks' probability of 957 // exiting the loop is larger than exiting through the latch block, it's not 958 // profitable to predicate the loop. 959 auto *LatchBlock = L->getLoopLatch(); 960 assert(LatchBlock && "Should have a single latch at this point!"); 961 auto *LatchTerm = LatchBlock->getTerminator(); 962 assert(LatchTerm->getNumSuccessors() == 2 && 963 "expected to be an exiting block with 2 succs!"); 964 unsigned LatchBrExitIdx = 965 LatchTerm->getSuccessor(0) == L->getHeader() ? 1 : 0; 966 // We compute branch probabilities without BPI. We do not rely on BPI since 967 // Loop predication is usually run in an LPM and BPI is only preserved 968 // lossily within loop pass managers, while BPI has an inherent notion of 969 // being complete for an entire function. 970 971 // If the latch exits into a deoptimize or an unreachable block, do not 972 // predicate on that latch check. 973 auto *LatchExitBlock = LatchTerm->getSuccessor(LatchBrExitIdx); 974 if (isa<UnreachableInst>(LatchTerm) || 975 LatchExitBlock->getTerminatingDeoptimizeCall()) 976 return false; 977 978 // Latch terminator has no valid profile data, so nothing to check 979 // profitability on. 980 if (!hasValidBranchWeightMD(*LatchTerm)) 981 return true; 982 983 auto ComputeBranchProbability = 984 [&](const BasicBlock *ExitingBlock, 985 const BasicBlock *ExitBlock) -> BranchProbability { 986 auto *Term = ExitingBlock->getTerminator(); 987 unsigned NumSucc = Term->getNumSuccessors(); 988 if (MDNode *ProfileData = getValidBranchWeightMDNode(*Term)) { 989 SmallVector<uint32_t> Weights; 990 extractBranchWeights(ProfileData, Weights); 991 uint64_t Numerator = 0, Denominator = 0; 992 for (auto [i, Weight] : llvm::enumerate(Weights)) { 993 if (Term->getSuccessor(i) == ExitBlock) 994 Numerator += Weight; 995 Denominator += Weight; 996 } 997 return BranchProbability::getBranchProbability(Numerator, Denominator); 998 } else { 999 assert(LatchBlock != ExitingBlock && 1000 "Latch term should always have profile data!"); 1001 // No profile data, so we choose the weight as 1/num_of_succ(Src) 1002 return BranchProbability::getBranchProbability(1, NumSucc); 1003 } 1004 }; 1005 1006 BranchProbability LatchExitProbability = 1007 ComputeBranchProbability(LatchBlock, LatchExitBlock); 1008 1009 // Protect against degenerate inputs provided by the user. Providing a value 1010 // less than one, can invert the definition of profitable loop predication. 1011 float ScaleFactor = LatchExitProbabilityScale; 1012 if (ScaleFactor < 1) { 1013 LLVM_DEBUG( 1014 dbgs() 1015 << "Ignored user setting for loop-predication-latch-probability-scale: " 1016 << LatchExitProbabilityScale << "\n"); 1017 LLVM_DEBUG(dbgs() << "The value is set to 1.0\n"); 1018 ScaleFactor = 1.0; 1019 } 1020 const auto LatchProbabilityThreshold = LatchExitProbability * ScaleFactor; 1021 1022 for (const auto &ExitEdge : ExitEdges) { 1023 BranchProbability ExitingBlockProbability = 1024 ComputeBranchProbability(ExitEdge.first, ExitEdge.second); 1025 // Some exiting edge has higher probability than the latch exiting edge. 1026 // No longer profitable to predicate. 1027 if (ExitingBlockProbability > LatchProbabilityThreshold) 1028 return false; 1029 } 1030 1031 // We have concluded that the most probable way to exit from the 1032 // loop is through the latch (or there's no profile information and all 1033 // exits are equally likely). 1034 return true; 1035 } 1036 1037 /// If we can (cheaply) find a widenable branch which controls entry into the 1038 /// loop, return it. 1039 static BranchInst *FindWidenableTerminatorAboveLoop(Loop *L, LoopInfo &LI) { 1040 // Walk back through any unconditional executed blocks and see if we can find 1041 // a widenable condition which seems to control execution of this loop. Note 1042 // that we predict that maythrow calls are likely untaken and thus that it's 1043 // profitable to widen a branch before a maythrow call with a condition 1044 // afterwards even though that may cause the slow path to run in a case where 1045 // it wouldn't have otherwise. 1046 BasicBlock *BB = L->getLoopPreheader(); 1047 if (!BB) 1048 return nullptr; 1049 do { 1050 if (BasicBlock *Pred = BB->getSinglePredecessor()) 1051 if (BB == Pred->getSingleSuccessor()) { 1052 BB = Pred; 1053 continue; 1054 } 1055 break; 1056 } while (true); 1057 1058 if (BasicBlock *Pred = BB->getSinglePredecessor()) { 1059 auto *Term = Pred->getTerminator(); 1060 1061 Value *Cond, *WC; 1062 BasicBlock *IfTrueBB, *IfFalseBB; 1063 if (parseWidenableBranch(Term, Cond, WC, IfTrueBB, IfFalseBB) && 1064 IfTrueBB == BB) 1065 return cast<BranchInst>(Term); 1066 } 1067 return nullptr; 1068 } 1069 1070 /// Return the minimum of all analyzeable exit counts. This is an upper bound 1071 /// on the actual exit count. If there are not at least two analyzeable exits, 1072 /// returns SCEVCouldNotCompute. 1073 static const SCEV *getMinAnalyzeableBackedgeTakenCount(ScalarEvolution &SE, 1074 DominatorTree &DT, 1075 Loop *L) { 1076 SmallVector<BasicBlock *, 16> ExitingBlocks; 1077 L->getExitingBlocks(ExitingBlocks); 1078 1079 SmallVector<const SCEV *, 4> ExitCounts; 1080 for (BasicBlock *ExitingBB : ExitingBlocks) { 1081 const SCEV *ExitCount = SE.getExitCount(L, ExitingBB); 1082 if (isa<SCEVCouldNotCompute>(ExitCount)) 1083 continue; 1084 assert(DT.dominates(ExitingBB, L->getLoopLatch()) && 1085 "We should only have known counts for exiting blocks that " 1086 "dominate latch!"); 1087 ExitCounts.push_back(ExitCount); 1088 } 1089 if (ExitCounts.size() < 2) 1090 return SE.getCouldNotCompute(); 1091 return SE.getUMinFromMismatchedTypes(ExitCounts); 1092 } 1093 1094 /// This implements an analogous, but entirely distinct transform from the main 1095 /// loop predication transform. This one is phrased in terms of using a 1096 /// widenable branch *outside* the loop to allow us to simplify loop exits in a 1097 /// following loop. This is close in spirit to the IndVarSimplify transform 1098 /// of the same name, but is materially different widening loosens legality 1099 /// sharply. 1100 bool LoopPredication::predicateLoopExits(Loop *L, SCEVExpander &Rewriter) { 1101 // The transformation performed here aims to widen a widenable condition 1102 // above the loop such that all analyzeable exit leading to deopt are dead. 1103 // It assumes that the latch is the dominant exit for profitability and that 1104 // exits branching to deoptimizing blocks are rarely taken. It relies on the 1105 // semantics of widenable expressions for legality. (i.e. being able to fall 1106 // down the widenable path spuriously allows us to ignore exit order, 1107 // unanalyzeable exits, side effects, exceptional exits, and other challenges 1108 // which restrict the applicability of the non-WC based version of this 1109 // transform in IndVarSimplify.) 1110 // 1111 // NOTE ON POISON/UNDEF - We're hoisting an expression above guards which may 1112 // imply flags on the expression being hoisted and inserting new uses (flags 1113 // are only correct for current uses). The result is that we may be 1114 // inserting a branch on the value which can be either poison or undef. In 1115 // this case, the branch can legally go either way; we just need to avoid 1116 // introducing UB. This is achieved through the use of the freeze 1117 // instruction. 1118 1119 SmallVector<BasicBlock *, 16> ExitingBlocks; 1120 L->getExitingBlocks(ExitingBlocks); 1121 1122 if (ExitingBlocks.empty()) 1123 return false; // Nothing to do. 1124 1125 auto *Latch = L->getLoopLatch(); 1126 if (!Latch) 1127 return false; 1128 1129 auto *WidenableBR = FindWidenableTerminatorAboveLoop(L, *LI); 1130 if (!WidenableBR) 1131 return false; 1132 1133 const SCEV *LatchEC = SE->getExitCount(L, Latch); 1134 if (isa<SCEVCouldNotCompute>(LatchEC)) 1135 return false; // profitability - want hot exit in analyzeable set 1136 1137 // At this point, we have found an analyzeable latch, and a widenable 1138 // condition above the loop. If we have a widenable exit within the loop 1139 // (for which we can't compute exit counts), drop the ability to further 1140 // widen so that we gain ability to analyze it's exit count and perform this 1141 // transform. TODO: It'd be nice to know for sure the exit became 1142 // analyzeable after dropping widenability. 1143 bool ChangedLoop = false; 1144 1145 for (auto *ExitingBB : ExitingBlocks) { 1146 if (LI->getLoopFor(ExitingBB) != L) 1147 continue; 1148 1149 auto *BI = dyn_cast<BranchInst>(ExitingBB->getTerminator()); 1150 if (!BI) 1151 continue; 1152 1153 Use *Cond, *WC; 1154 BasicBlock *IfTrueBB, *IfFalseBB; 1155 if (parseWidenableBranch(BI, Cond, WC, IfTrueBB, IfFalseBB) && 1156 L->contains(IfTrueBB)) { 1157 WC->set(ConstantInt::getTrue(IfTrueBB->getContext())); 1158 ChangedLoop = true; 1159 } 1160 } 1161 if (ChangedLoop) 1162 SE->forgetLoop(L); 1163 1164 // The use of umin(all analyzeable exits) instead of latch is subtle, but 1165 // important for profitability. We may have a loop which hasn't been fully 1166 // canonicalized just yet. If the exit we chose to widen is provably never 1167 // taken, we want the widened form to *also* be provably never taken. We 1168 // can't guarantee this as a current unanalyzeable exit may later become 1169 // analyzeable, but we can at least avoid the obvious cases. 1170 const SCEV *MinEC = getMinAnalyzeableBackedgeTakenCount(*SE, *DT, L); 1171 if (isa<SCEVCouldNotCompute>(MinEC) || MinEC->getType()->isPointerTy() || 1172 !SE->isLoopInvariant(MinEC, L) || 1173 !Rewriter.isSafeToExpandAt(MinEC, WidenableBR)) 1174 return ChangedLoop; 1175 1176 // Subtlety: We need to avoid inserting additional uses of the WC. We know 1177 // that it can only have one transitive use at the moment, and thus moving 1178 // that use to just before the branch and inserting code before it and then 1179 // modifying the operand is legal. 1180 auto *IP = cast<Instruction>(WidenableBR->getCondition()); 1181 // Here we unconditionally modify the IR, so after this point we should return 1182 // only `true`! 1183 IP->moveBefore(WidenableBR); 1184 if (MSSAU) 1185 if (auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(IP)) 1186 MSSAU->moveToPlace(MUD, WidenableBR->getParent(), 1187 MemorySSA::BeforeTerminator); 1188 Rewriter.setInsertPoint(IP); 1189 IRBuilder<> B(IP); 1190 1191 bool InvalidateLoop = false; 1192 Value *MinECV = nullptr; // lazily generated if needed 1193 for (BasicBlock *ExitingBB : ExitingBlocks) { 1194 // If our exiting block exits multiple loops, we can only rewrite the 1195 // innermost one. Otherwise, we're changing how many times the innermost 1196 // loop runs before it exits. 1197 if (LI->getLoopFor(ExitingBB) != L) 1198 continue; 1199 1200 // Can't rewrite non-branch yet. 1201 auto *BI = dyn_cast<BranchInst>(ExitingBB->getTerminator()); 1202 if (!BI) 1203 continue; 1204 1205 // If already constant, nothing to do. 1206 if (isa<Constant>(BI->getCondition())) 1207 continue; 1208 1209 const SCEV *ExitCount = SE->getExitCount(L, ExitingBB); 1210 if (isa<SCEVCouldNotCompute>(ExitCount) || 1211 ExitCount->getType()->isPointerTy() || 1212 !Rewriter.isSafeToExpandAt(ExitCount, WidenableBR)) 1213 continue; 1214 1215 const bool ExitIfTrue = !L->contains(*succ_begin(ExitingBB)); 1216 BasicBlock *ExitBB = BI->getSuccessor(ExitIfTrue ? 0 : 1); 1217 if (!ExitBB->getPostdominatingDeoptimizeCall()) 1218 continue; 1219 1220 /// Here we can be fairly sure that executing this exit will most likely 1221 /// lead to executing llvm.experimental.deoptimize. 1222 /// This is a profitability heuristic, not a legality constraint. 1223 1224 // If we found a widenable exit condition, do two things: 1225 // 1) fold the widened exit test into the widenable condition 1226 // 2) fold the branch to untaken - avoids infinite looping 1227 1228 Value *ECV = Rewriter.expandCodeFor(ExitCount); 1229 if (!MinECV) 1230 MinECV = Rewriter.expandCodeFor(MinEC); 1231 Value *RHS = MinECV; 1232 if (ECV->getType() != RHS->getType()) { 1233 Type *WiderTy = SE->getWiderType(ECV->getType(), RHS->getType()); 1234 ECV = B.CreateZExt(ECV, WiderTy); 1235 RHS = B.CreateZExt(RHS, WiderTy); 1236 } 1237 assert(!Latch || DT->dominates(ExitingBB, Latch)); 1238 Value *NewCond = B.CreateICmp(ICmpInst::ICMP_UGT, ECV, RHS); 1239 // Freeze poison or undef to an arbitrary bit pattern to ensure we can 1240 // branch without introducing UB. See NOTE ON POISON/UNDEF above for 1241 // context. 1242 NewCond = B.CreateFreeze(NewCond); 1243 1244 widenWidenableBranch(WidenableBR, NewCond); 1245 1246 Value *OldCond = BI->getCondition(); 1247 BI->setCondition(ConstantInt::get(OldCond->getType(), !ExitIfTrue)); 1248 InvalidateLoop = true; 1249 } 1250 1251 if (InvalidateLoop) 1252 // We just mutated a bunch of loop exits changing there exit counts 1253 // widely. We need to force recomputation of the exit counts given these 1254 // changes. Note that all of the inserted exits are never taken, and 1255 // should be removed next time the CFG is modified. 1256 SE->forgetLoop(L); 1257 1258 // Always return `true` since we have moved the WidenableBR's condition. 1259 return true; 1260 } 1261 1262 bool LoopPredication::runOnLoop(Loop *Loop) { 1263 L = Loop; 1264 1265 LLVM_DEBUG(dbgs() << "Analyzing "); 1266 LLVM_DEBUG(L->dump()); 1267 1268 Module *M = L->getHeader()->getModule(); 1269 1270 // There is nothing to do if the module doesn't use guards 1271 auto *GuardDecl = 1272 M->getFunction(Intrinsic::getName(Intrinsic::experimental_guard)); 1273 bool HasIntrinsicGuards = GuardDecl && !GuardDecl->use_empty(); 1274 auto *WCDecl = M->getFunction( 1275 Intrinsic::getName(Intrinsic::experimental_widenable_condition)); 1276 bool HasWidenableConditions = 1277 PredicateWidenableBranchGuards && WCDecl && !WCDecl->use_empty(); 1278 if (!HasIntrinsicGuards && !HasWidenableConditions) 1279 return false; 1280 1281 DL = &M->getDataLayout(); 1282 1283 Preheader = L->getLoopPreheader(); 1284 if (!Preheader) 1285 return false; 1286 1287 auto LatchCheckOpt = parseLoopLatchICmp(); 1288 if (!LatchCheckOpt) 1289 return false; 1290 LatchCheck = *LatchCheckOpt; 1291 1292 LLVM_DEBUG(dbgs() << "Latch check:\n"); 1293 LLVM_DEBUG(LatchCheck.dump()); 1294 1295 if (!isLoopProfitableToPredicate()) { 1296 LLVM_DEBUG(dbgs() << "Loop not profitable to predicate!\n"); 1297 return false; 1298 } 1299 // Collect all the guards into a vector and process later, so as not 1300 // to invalidate the instruction iterator. 1301 SmallVector<IntrinsicInst *, 4> Guards; 1302 SmallVector<BranchInst *, 4> GuardsAsWidenableBranches; 1303 for (const auto BB : L->blocks()) { 1304 for (auto &I : *BB) 1305 if (isGuard(&I)) 1306 Guards.push_back(cast<IntrinsicInst>(&I)); 1307 if (PredicateWidenableBranchGuards && 1308 isGuardAsWidenableBranch(BB->getTerminator())) 1309 GuardsAsWidenableBranches.push_back( 1310 cast<BranchInst>(BB->getTerminator())); 1311 } 1312 1313 SCEVExpander Expander(*SE, *DL, "loop-predication"); 1314 bool Changed = false; 1315 for (auto *Guard : Guards) 1316 Changed |= widenGuardConditions(Guard, Expander); 1317 for (auto *Guard : GuardsAsWidenableBranches) 1318 Changed |= widenWidenableBranchGuardConditions(Guard, Expander); 1319 Changed |= predicateLoopExits(L, Expander); 1320 1321 if (MSSAU && VerifyMemorySSA) 1322 MSSAU->getMemorySSA()->verifyMemorySSA(); 1323 return Changed; 1324 } 1325