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