| //===-- LoopPredication.cpp - Guard based loop predication pass -----------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // The LoopPredication pass tries to convert loop variant range checks to loop |
| // invariant by widening checks across loop iterations. For example, it will |
| // convert |
| // |
| // for (i = 0; i < n; i++) { |
| // guard(i < len); |
| // ... |
| // } |
| // |
| // to |
| // |
| // for (i = 0; i < n; i++) { |
| // guard(n - 1 < len); |
| // ... |
| // } |
| // |
| // After this transformation the condition of the guard is loop invariant, so |
| // loop-unswitch can later unswitch the loop by this condition which basically |
| // predicates the loop by the widened condition: |
| // |
| // if (n - 1 < len) |
| // for (i = 0; i < n; i++) { |
| // ... |
| // } |
| // else |
| // deoptimize |
| // |
| // It's tempting to rely on SCEV here, but it has proven to be problematic. |
| // Generally the facts SCEV provides about the increment step of add |
| // recurrences are true if the backedge of the loop is taken, which implicitly |
| // assumes that the guard doesn't fail. Using these facts to optimize the |
| // guard results in a circular logic where the guard is optimized under the |
| // assumption that it never fails. |
| // |
| // For example, in the loop below the induction variable will be marked as nuw |
| // basing on the guard. Basing on nuw the guard predicate will be considered |
| // monotonic. Given a monotonic condition it's tempting to replace the induction |
| // variable in the condition with its value on the last iteration. But this |
| // transformation is not correct, e.g. e = 4, b = 5 breaks the loop. |
| // |
| // for (int i = b; i != e; i++) |
| // guard(i u< len) |
| // |
| // One of the ways to reason about this problem is to use an inductive proof |
| // approach. Given the loop: |
| // |
| // if (B(0)) { |
| // do { |
| // I = PHI(0, I.INC) |
| // I.INC = I + Step |
| // guard(G(I)); |
| // } while (B(I)); |
| // } |
| // |
| // where B(x) and G(x) are predicates that map integers to booleans, we want a |
| // loop invariant expression M such the following program has the same semantics |
| // as the above: |
| // |
| // if (B(0)) { |
| // do { |
| // I = PHI(0, I.INC) |
| // I.INC = I + Step |
| // guard(G(0) && M); |
| // } while (B(I)); |
| // } |
| // |
| // One solution for M is M = forall X . (G(X) && B(X)) => G(X + Step) |
| // |
| // Informal proof that the transformation above is correct: |
| // |
| // By the definition of guards we can rewrite the guard condition to: |
| // G(I) && G(0) && M |
| // |
| // Let's prove that for each iteration of the loop: |
| // G(0) && M => G(I) |
| // And the condition above can be simplified to G(Start) && M. |
| // |
| // Induction base. |
| // G(0) && M => G(0) |
| // |
| // Induction step. Assuming G(0) && M => G(I) on the subsequent |
| // iteration: |
| // |
| // B(I) is true because it's the backedge condition. |
| // G(I) is true because the backedge is guarded by this condition. |
| // |
| // So M = forall X . (G(X) && B(X)) => G(X + Step) implies G(I + Step). |
| // |
| // Note that we can use anything stronger than M, i.e. any condition which |
| // implies M. |
| // |
| // When S = 1 (i.e. forward iterating loop), the transformation is supported |
| // when: |
| // * The loop has a single latch with the condition of the form: |
| // B(X) = latchStart + X <pred> latchLimit, |
| // where <pred> is u<, u<=, s<, or s<=. |
| // * The guard condition is of the form |
| // G(X) = guardStart + X u< guardLimit |
| // |
| // For the ult latch comparison case M is: |
| // forall X . guardStart + X u< guardLimit && latchStart + X <u latchLimit => |
| // guardStart + X + 1 u< guardLimit |
| // |
| // The only way the antecedent can be true and the consequent can be false is |
| // if |
| // X == guardLimit - 1 - guardStart |
| // (and guardLimit is non-zero, but we won't use this latter fact). |
| // If X == guardLimit - 1 - guardStart then the second half of the antecedent is |
| // latchStart + guardLimit - 1 - guardStart u< latchLimit |
| // and its negation is |
| // latchStart + guardLimit - 1 - guardStart u>= latchLimit |
| // |
| // In other words, if |
| // latchLimit u<= latchStart + guardLimit - 1 - guardStart |
| // then: |
| // (the ranges below are written in ConstantRange notation, where [A, B) is the |
| // set for (I = A; I != B; I++ /*maywrap*/) yield(I);) |
| // |
| // forall X . guardStart + X u< guardLimit && |
| // latchStart + X u< latchLimit => |
| // guardStart + X + 1 u< guardLimit |
| // == forall X . guardStart + X u< guardLimit && |
| // latchStart + X u< latchStart + guardLimit - 1 - guardStart => |
| // guardStart + X + 1 u< guardLimit |
| // == forall X . (guardStart + X) in [0, guardLimit) && |
| // (latchStart + X) in [0, latchStart + guardLimit - 1 - guardStart) => |
| // (guardStart + X + 1) in [0, guardLimit) |
| // == forall X . X in [-guardStart, guardLimit - guardStart) && |
| // X in [-latchStart, guardLimit - 1 - guardStart) => |
| // X in [-guardStart - 1, guardLimit - guardStart - 1) |
| // == true |
| // |
| // So the widened condition is: |
| // guardStart u< guardLimit && |
| // latchStart + guardLimit - 1 - guardStart u>= latchLimit |
| // Similarly for ule condition the widened condition is: |
| // guardStart u< guardLimit && |
| // latchStart + guardLimit - 1 - guardStart u> latchLimit |
| // For slt condition the widened condition is: |
| // guardStart u< guardLimit && |
| // latchStart + guardLimit - 1 - guardStart s>= latchLimit |
| // For sle condition the widened condition is: |
| // guardStart u< guardLimit && |
| // latchStart + guardLimit - 1 - guardStart s> latchLimit |
| // |
| // When S = -1 (i.e. reverse iterating loop), the transformation is supported |
| // when: |
| // * The loop has a single latch with the condition of the form: |
| // B(X) = X <pred> latchLimit, where <pred> is u>, u>=, s>, or s>=. |
| // * The guard condition is of the form |
| // G(X) = X - 1 u< guardLimit |
| // |
| // For the ugt latch comparison case M is: |
| // forall X. X-1 u< guardLimit and X u> latchLimit => X-2 u< guardLimit |
| // |
| // The only way the antecedent can be true and the consequent can be false is if |
| // X == 1. |
| // If X == 1 then the second half of the antecedent is |
| // 1 u> latchLimit, and its negation is latchLimit u>= 1. |
| // |
| // So the widened condition is: |
| // guardStart u< guardLimit && latchLimit u>= 1. |
| // Similarly for sgt condition the widened condition is: |
| // guardStart u< guardLimit && latchLimit s>= 1. |
| // For uge condition the widened condition is: |
| // guardStart u< guardLimit && latchLimit u> 1. |
| // For sge condition the widened condition is: |
| // guardStart u< guardLimit && latchLimit s> 1. |
| //===----------------------------------------------------------------------===// |
| |
| #include "llvm/Transforms/Scalar/LoopPredication.h" |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/Analysis/AliasAnalysis.h" |
| #include "llvm/Analysis/BranchProbabilityInfo.h" |
| #include "llvm/Analysis/GuardUtils.h" |
| #include "llvm/Analysis/LoopInfo.h" |
| #include "llvm/Analysis/LoopPass.h" |
| #include "llvm/Analysis/MemorySSA.h" |
| #include "llvm/Analysis/MemorySSAUpdater.h" |
| #include "llvm/Analysis/ScalarEvolution.h" |
| #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
| #include "llvm/IR/Function.h" |
| #include "llvm/IR/GlobalValue.h" |
| #include "llvm/IR/IntrinsicInst.h" |
| #include "llvm/IR/Module.h" |
| #include "llvm/IR/PatternMatch.h" |
| #include "llvm/InitializePasses.h" |
| #include "llvm/Pass.h" |
| #include "llvm/Support/CommandLine.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Transforms/Scalar.h" |
| #include "llvm/Transforms/Utils/GuardUtils.h" |
| #include "llvm/Transforms/Utils/Local.h" |
| #include "llvm/Transforms/Utils/LoopUtils.h" |
| #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" |
| |
| #define DEBUG_TYPE "loop-predication" |
| |
| STATISTIC(TotalConsidered, "Number of guards considered"); |
| STATISTIC(TotalWidened, "Number of checks widened"); |
| |
| using namespace llvm; |
| |
| static cl::opt<bool> EnableIVTruncation("loop-predication-enable-iv-truncation", |
| cl::Hidden, cl::init(true)); |
| |
| static cl::opt<bool> EnableCountDownLoop("loop-predication-enable-count-down-loop", |
| cl::Hidden, cl::init(true)); |
| |
| static cl::opt<bool> |
| SkipProfitabilityChecks("loop-predication-skip-profitability-checks", |
| cl::Hidden, cl::init(false)); |
| |
| // This is the scale factor for the latch probability. We use this during |
| // profitability analysis to find other exiting blocks that have a much higher |
| // probability of exiting the loop instead of loop exiting via latch. |
| // This value should be greater than 1 for a sane profitability check. |
| static cl::opt<float> LatchExitProbabilityScale( |
| "loop-predication-latch-probability-scale", cl::Hidden, cl::init(2.0), |
| cl::desc("scale factor for the latch probability. Value should be greater " |
| "than 1. Lower values are ignored")); |
| |
| static cl::opt<bool> PredicateWidenableBranchGuards( |
| "loop-predication-predicate-widenable-branches-to-deopt", cl::Hidden, |
| cl::desc("Whether or not we should predicate guards " |
| "expressed as widenable branches to deoptimize blocks"), |
| cl::init(true)); |
| |
| namespace { |
| /// Represents an induction variable check: |
| /// icmp Pred, <induction variable>, <loop invariant limit> |
| struct LoopICmp { |
| ICmpInst::Predicate Pred; |
| const SCEVAddRecExpr *IV; |
| const SCEV *Limit; |
| LoopICmp(ICmpInst::Predicate Pred, const SCEVAddRecExpr *IV, |
| const SCEV *Limit) |
| : Pred(Pred), IV(IV), Limit(Limit) {} |
| LoopICmp() {} |
| void dump() { |
| dbgs() << "LoopICmp Pred = " << Pred << ", IV = " << *IV |
| << ", Limit = " << *Limit << "\n"; |
| } |
| }; |
| |
| class LoopPredication { |
| AliasAnalysis *AA; |
| DominatorTree *DT; |
| ScalarEvolution *SE; |
| LoopInfo *LI; |
| MemorySSAUpdater *MSSAU; |
| |
| Loop *L; |
| const DataLayout *DL; |
| BasicBlock *Preheader; |
| LoopICmp LatchCheck; |
| |
| bool isSupportedStep(const SCEV* Step); |
| Optional<LoopICmp> parseLoopICmp(ICmpInst *ICI); |
| Optional<LoopICmp> parseLoopLatchICmp(); |
| |
| /// Return an insertion point suitable for inserting a safe to speculate |
| /// instruction whose only user will be 'User' which has operands 'Ops'. A |
| /// trivial result would be the at the User itself, but we try to return a |
| /// loop invariant location if possible. |
| Instruction *findInsertPt(Instruction *User, ArrayRef<Value*> Ops); |
| /// Same as above, *except* that this uses the SCEV definition of invariant |
| /// which is that an expression *can be made* invariant via SCEVExpander. |
| /// Thus, this version is only suitable for finding an insert point to be be |
| /// passed to SCEVExpander! |
| Instruction *findInsertPt(Instruction *User, ArrayRef<const SCEV*> Ops); |
| |
| /// Return true if the value is known to produce a single fixed value across |
| /// all iterations on which it executes. Note that this does not imply |
| /// speculation safety. That must be established separately. |
| bool isLoopInvariantValue(const SCEV* S); |
| |
| Value *expandCheck(SCEVExpander &Expander, Instruction *Guard, |
| ICmpInst::Predicate Pred, const SCEV *LHS, |
| const SCEV *RHS); |
| |
| Optional<Value *> widenICmpRangeCheck(ICmpInst *ICI, SCEVExpander &Expander, |
| Instruction *Guard); |
| Optional<Value *> widenICmpRangeCheckIncrementingLoop(LoopICmp LatchCheck, |
| LoopICmp RangeCheck, |
| SCEVExpander &Expander, |
| Instruction *Guard); |
| Optional<Value *> widenICmpRangeCheckDecrementingLoop(LoopICmp LatchCheck, |
| LoopICmp RangeCheck, |
| SCEVExpander &Expander, |
| Instruction *Guard); |
| unsigned collectChecks(SmallVectorImpl<Value *> &Checks, Value *Condition, |
| SCEVExpander &Expander, Instruction *Guard); |
| bool widenGuardConditions(IntrinsicInst *II, SCEVExpander &Expander); |
| bool widenWidenableBranchGuardConditions(BranchInst *Guard, SCEVExpander &Expander); |
| // If the loop always exits through another block in the loop, we should not |
| // predicate based on the latch check. For example, the latch check can be a |
| // very coarse grained check and there can be more fine grained exit checks |
| // within the loop. |
| bool isLoopProfitableToPredicate(); |
| |
| bool predicateLoopExits(Loop *L, SCEVExpander &Rewriter); |
| |
| public: |
| LoopPredication(AliasAnalysis *AA, DominatorTree *DT, ScalarEvolution *SE, |
| LoopInfo *LI, MemorySSAUpdater *MSSAU) |
| : AA(AA), DT(DT), SE(SE), LI(LI), MSSAU(MSSAU){}; |
| bool runOnLoop(Loop *L); |
| }; |
| |
| class LoopPredicationLegacyPass : public LoopPass { |
| public: |
| static char ID; |
| LoopPredicationLegacyPass() : LoopPass(ID) { |
| initializeLoopPredicationLegacyPassPass(*PassRegistry::getPassRegistry()); |
| } |
| |
| void getAnalysisUsage(AnalysisUsage &AU) const override { |
| AU.addRequired<BranchProbabilityInfoWrapperPass>(); |
| getLoopAnalysisUsage(AU); |
| AU.addPreserved<MemorySSAWrapperPass>(); |
| } |
| |
| bool runOnLoop(Loop *L, LPPassManager &LPM) override { |
| if (skipLoop(L)) |
| return false; |
| auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); |
| auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); |
| auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
| auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>(); |
| std::unique_ptr<MemorySSAUpdater> MSSAU; |
| if (MSSAWP) |
| MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAWP->getMSSA()); |
| auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); |
| LoopPredication LP(AA, DT, SE, LI, MSSAU ? MSSAU.get() : nullptr); |
| return LP.runOnLoop(L); |
| } |
| }; |
| |
| char LoopPredicationLegacyPass::ID = 0; |
| } // end namespace |
| |
| INITIALIZE_PASS_BEGIN(LoopPredicationLegacyPass, "loop-predication", |
| "Loop predication", false, false) |
| INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass) |
| INITIALIZE_PASS_DEPENDENCY(LoopPass) |
| INITIALIZE_PASS_END(LoopPredicationLegacyPass, "loop-predication", |
| "Loop predication", false, false) |
| |
| Pass *llvm::createLoopPredicationPass() { |
| return new LoopPredicationLegacyPass(); |
| } |
| |
| PreservedAnalyses LoopPredicationPass::run(Loop &L, LoopAnalysisManager &AM, |
| LoopStandardAnalysisResults &AR, |
| LPMUpdater &U) { |
| std::unique_ptr<MemorySSAUpdater> MSSAU; |
| if (AR.MSSA) |
| MSSAU = std::make_unique<MemorySSAUpdater>(AR.MSSA); |
| LoopPredication LP(&AR.AA, &AR.DT, &AR.SE, &AR.LI, |
| MSSAU ? MSSAU.get() : nullptr); |
| if (!LP.runOnLoop(&L)) |
| return PreservedAnalyses::all(); |
| |
| auto PA = getLoopPassPreservedAnalyses(); |
| if (AR.MSSA) |
| PA.preserve<MemorySSAAnalysis>(); |
| return PA; |
| } |
| |
| Optional<LoopICmp> |
| LoopPredication::parseLoopICmp(ICmpInst *ICI) { |
| auto Pred = ICI->getPredicate(); |
| auto *LHS = ICI->getOperand(0); |
| auto *RHS = ICI->getOperand(1); |
| |
| const SCEV *LHSS = SE->getSCEV(LHS); |
| if (isa<SCEVCouldNotCompute>(LHSS)) |
| return None; |
| const SCEV *RHSS = SE->getSCEV(RHS); |
| if (isa<SCEVCouldNotCompute>(RHSS)) |
| return None; |
| |
| // Canonicalize RHS to be loop invariant bound, LHS - a loop computable IV |
| if (SE->isLoopInvariant(LHSS, L)) { |
| std::swap(LHS, RHS); |
| std::swap(LHSS, RHSS); |
| Pred = ICmpInst::getSwappedPredicate(Pred); |
| } |
| |
| const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHSS); |
| if (!AR || AR->getLoop() != L) |
| return None; |
| |
| return LoopICmp(Pred, AR, RHSS); |
| } |
| |
| Value *LoopPredication::expandCheck(SCEVExpander &Expander, |
| Instruction *Guard, |
| ICmpInst::Predicate Pred, const SCEV *LHS, |
| const SCEV *RHS) { |
| Type *Ty = LHS->getType(); |
| assert(Ty == RHS->getType() && "expandCheck operands have different types?"); |
| |
| if (SE->isLoopInvariant(LHS, L) && SE->isLoopInvariant(RHS, L)) { |
| IRBuilder<> Builder(Guard); |
| if (SE->isLoopEntryGuardedByCond(L, Pred, LHS, RHS)) |
| return Builder.getTrue(); |
| if (SE->isLoopEntryGuardedByCond(L, ICmpInst::getInversePredicate(Pred), |
| LHS, RHS)) |
| return Builder.getFalse(); |
| } |
| |
| Value *LHSV = Expander.expandCodeFor(LHS, Ty, findInsertPt(Guard, {LHS})); |
| Value *RHSV = Expander.expandCodeFor(RHS, Ty, findInsertPt(Guard, {RHS})); |
| IRBuilder<> Builder(findInsertPt(Guard, {LHSV, RHSV})); |
| return Builder.CreateICmp(Pred, LHSV, RHSV); |
| } |
| |
| |
| // Returns true if its safe to truncate the IV to RangeCheckType. |
| // When the IV type is wider than the range operand type, we can still do loop |
| // predication, by generating SCEVs for the range and latch that are of the |
| // same type. We achieve this by generating a SCEV truncate expression for the |
| // latch IV. This is done iff truncation of the IV is a safe operation, |
| // without loss of information. |
| // Another way to achieve this is by generating a wider type SCEV for the |
| // range check operand, however, this needs a more involved check that |
| // operands do not overflow. This can lead to loss of information when the |
| // range operand is of the form: add i32 %offset, %iv. We need to prove that |
| // sext(x + y) is same as sext(x) + sext(y). |
| // This function returns true if we can safely represent the IV type in |
| // the RangeCheckType without loss of information. |
| static bool isSafeToTruncateWideIVType(const DataLayout &DL, |
| ScalarEvolution &SE, |
| const LoopICmp LatchCheck, |
| Type *RangeCheckType) { |
| if (!EnableIVTruncation) |
| return false; |
| assert(DL.getTypeSizeInBits(LatchCheck.IV->getType()).getFixedSize() > |
| DL.getTypeSizeInBits(RangeCheckType).getFixedSize() && |
| "Expected latch check IV type to be larger than range check operand " |
| "type!"); |
| // The start and end values of the IV should be known. This is to guarantee |
| // that truncating the wide type will not lose information. |
| auto *Limit = dyn_cast<SCEVConstant>(LatchCheck.Limit); |
| auto *Start = dyn_cast<SCEVConstant>(LatchCheck.IV->getStart()); |
| if (!Limit || !Start) |
| return false; |
| // This check makes sure that the IV does not change sign during loop |
| // iterations. Consider latchType = i64, LatchStart = 5, Pred = ICMP_SGE, |
| // LatchEnd = 2, rangeCheckType = i32. If it's not a monotonic predicate, the |
| // IV wraps around, and the truncation of the IV would lose the range of |
| // iterations between 2^32 and 2^64. |
| if (!SE.getMonotonicPredicateType(LatchCheck.IV, LatchCheck.Pred)) |
| return false; |
| // The active bits should be less than the bits in the RangeCheckType. This |
| // guarantees that truncating the latch check to RangeCheckType is a safe |
| // operation. |
| auto RangeCheckTypeBitSize = |
| DL.getTypeSizeInBits(RangeCheckType).getFixedSize(); |
| return Start->getAPInt().getActiveBits() < RangeCheckTypeBitSize && |
| Limit->getAPInt().getActiveBits() < RangeCheckTypeBitSize; |
| } |
| |
| |
| // Return an LoopICmp describing a latch check equivlent to LatchCheck but with |
| // the requested type if safe to do so. May involve the use of a new IV. |
| static Optional<LoopICmp> generateLoopLatchCheck(const DataLayout &DL, |
| ScalarEvolution &SE, |
| const LoopICmp LatchCheck, |
| Type *RangeCheckType) { |
| |
| auto *LatchType = LatchCheck.IV->getType(); |
| if (RangeCheckType == LatchType) |
| return LatchCheck; |
| // For now, bail out if latch type is narrower than range type. |
| if (DL.getTypeSizeInBits(LatchType).getFixedSize() < |
| DL.getTypeSizeInBits(RangeCheckType).getFixedSize()) |
| return None; |
| if (!isSafeToTruncateWideIVType(DL, SE, LatchCheck, RangeCheckType)) |
| return None; |
| // We can now safely identify the truncated version of the IV and limit for |
| // RangeCheckType. |
| LoopICmp NewLatchCheck; |
| NewLatchCheck.Pred = LatchCheck.Pred; |
| NewLatchCheck.IV = dyn_cast<SCEVAddRecExpr>( |
| SE.getTruncateExpr(LatchCheck.IV, RangeCheckType)); |
| if (!NewLatchCheck.IV) |
| return None; |
| NewLatchCheck.Limit = SE.getTruncateExpr(LatchCheck.Limit, RangeCheckType); |
| LLVM_DEBUG(dbgs() << "IV of type: " << *LatchType |
| << "can be represented as range check type:" |
| << *RangeCheckType << "\n"); |
| LLVM_DEBUG(dbgs() << "LatchCheck.IV: " << *NewLatchCheck.IV << "\n"); |
| LLVM_DEBUG(dbgs() << "LatchCheck.Limit: " << *NewLatchCheck.Limit << "\n"); |
| return NewLatchCheck; |
| } |
| |
| bool LoopPredication::isSupportedStep(const SCEV* Step) { |
| return Step->isOne() || (Step->isAllOnesValue() && EnableCountDownLoop); |
| } |
| |
| Instruction *LoopPredication::findInsertPt(Instruction *Use, |
| ArrayRef<Value*> Ops) { |
| for (Value *Op : Ops) |
| if (!L->isLoopInvariant(Op)) |
| return Use; |
| return Preheader->getTerminator(); |
| } |
| |
| Instruction *LoopPredication::findInsertPt(Instruction *Use, |
| ArrayRef<const SCEV*> Ops) { |
| // Subtlety: SCEV considers things to be invariant if the value produced is |
| // the same across iterations. This is not the same as being able to |
| // evaluate outside the loop, which is what we actually need here. |
| for (const SCEV *Op : Ops) |
| if (!SE->isLoopInvariant(Op, L) || |
| !isSafeToExpandAt(Op, Preheader->getTerminator(), *SE)) |
| return Use; |
| return Preheader->getTerminator(); |
| } |
| |
| bool LoopPredication::isLoopInvariantValue(const SCEV* S) { |
| // Handling expressions which produce invariant results, but *haven't* yet |
| // been removed from the loop serves two important purposes. |
| // 1) Most importantly, it resolves a pass ordering cycle which would |
| // otherwise need us to iteration licm, loop-predication, and either |
| // loop-unswitch or loop-peeling to make progress on examples with lots of |
| // predicable range checks in a row. (Since, in the general case, we can't |
| // hoist the length checks until the dominating checks have been discharged |
| // as we can't prove doing so is safe.) |
| // 2) As a nice side effect, this exposes the value of peeling or unswitching |
| // much more obviously in the IR. Otherwise, the cost modeling for other |
| // transforms would end up needing to duplicate all of this logic to model a |
| // check which becomes predictable based on a modeled peel or unswitch. |
| // |
| // The cost of doing so in the worst case is an extra fill from the stack in |
| // the loop to materialize the loop invariant test value instead of checking |
| // against the original IV which is presumable in a register inside the loop. |
| // Such cases are presumably rare, and hint at missing oppurtunities for |
| // other passes. |
| |
| if (SE->isLoopInvariant(S, L)) |
| // Note: This the SCEV variant, so the original Value* may be within the |
| // loop even though SCEV has proven it is loop invariant. |
| return true; |
| |
| // Handle a particular important case which SCEV doesn't yet know about which |
| // shows up in range checks on arrays with immutable lengths. |
| // TODO: This should be sunk inside SCEV. |
| if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) |
| if (const auto *LI = dyn_cast<LoadInst>(U->getValue())) |
| if (LI->isUnordered() && L->hasLoopInvariantOperands(LI)) |
| if (AA->pointsToConstantMemory(LI->getOperand(0)) || |
| LI->hasMetadata(LLVMContext::MD_invariant_load)) |
| return true; |
| return false; |
| } |
| |
| Optional<Value *> LoopPredication::widenICmpRangeCheckIncrementingLoop( |
| LoopICmp LatchCheck, LoopICmp RangeCheck, |
| SCEVExpander &Expander, Instruction *Guard) { |
| auto *Ty = RangeCheck.IV->getType(); |
| // Generate the widened condition for the forward loop: |
| // guardStart u< guardLimit && |
| // latchLimit <pred> guardLimit - 1 - guardStart + latchStart |
| // where <pred> depends on the latch condition predicate. See the file |
| // header comment for the reasoning. |
| // guardLimit - guardStart + latchStart - 1 |
| const SCEV *GuardStart = RangeCheck.IV->getStart(); |
| const SCEV *GuardLimit = RangeCheck.Limit; |
| const SCEV *LatchStart = LatchCheck.IV->getStart(); |
| const SCEV *LatchLimit = LatchCheck.Limit; |
| // Subtlety: We need all the values to be *invariant* across all iterations, |
| // but we only need to check expansion safety for those which *aren't* |
| // already guaranteed to dominate the guard. |
| if (!isLoopInvariantValue(GuardStart) || |
| !isLoopInvariantValue(GuardLimit) || |
| !isLoopInvariantValue(LatchStart) || |
| !isLoopInvariantValue(LatchLimit)) { |
| LLVM_DEBUG(dbgs() << "Can't expand limit check!\n"); |
| return None; |
| } |
| if (!isSafeToExpandAt(LatchStart, Guard, *SE) || |
| !isSafeToExpandAt(LatchLimit, Guard, *SE)) { |
| LLVM_DEBUG(dbgs() << "Can't expand limit check!\n"); |
| return None; |
| } |
| |
| // guardLimit - guardStart + latchStart - 1 |
| const SCEV *RHS = |
| SE->getAddExpr(SE->getMinusSCEV(GuardLimit, GuardStart), |
| SE->getMinusSCEV(LatchStart, SE->getOne(Ty))); |
| auto LimitCheckPred = |
| ICmpInst::getFlippedStrictnessPredicate(LatchCheck.Pred); |
| |
| LLVM_DEBUG(dbgs() << "LHS: " << *LatchLimit << "\n"); |
| LLVM_DEBUG(dbgs() << "RHS: " << *RHS << "\n"); |
| LLVM_DEBUG(dbgs() << "Pred: " << LimitCheckPred << "\n"); |
| |
| auto *LimitCheck = |
| expandCheck(Expander, Guard, LimitCheckPred, LatchLimit, RHS); |
| auto *FirstIterationCheck = expandCheck(Expander, Guard, RangeCheck.Pred, |
| GuardStart, GuardLimit); |
| IRBuilder<> Builder(findInsertPt(Guard, {FirstIterationCheck, LimitCheck})); |
| return Builder.CreateAnd(FirstIterationCheck, LimitCheck); |
| } |
| |
| Optional<Value *> LoopPredication::widenICmpRangeCheckDecrementingLoop( |
| LoopICmp LatchCheck, LoopICmp RangeCheck, |
| SCEVExpander &Expander, Instruction *Guard) { |
| auto *Ty = RangeCheck.IV->getType(); |
| const SCEV *GuardStart = RangeCheck.IV->getStart(); |
| const SCEV *GuardLimit = RangeCheck.Limit; |
| const SCEV *LatchStart = LatchCheck.IV->getStart(); |
| const SCEV *LatchLimit = LatchCheck.Limit; |
| // Subtlety: We need all the values to be *invariant* across all iterations, |
| // but we only need to check expansion safety for those which *aren't* |
| // already guaranteed to dominate the guard. |
| if (!isLoopInvariantValue(GuardStart) || |
| !isLoopInvariantValue(GuardLimit) || |
| !isLoopInvariantValue(LatchStart) || |
| !isLoopInvariantValue(LatchLimit)) { |
| LLVM_DEBUG(dbgs() << "Can't expand limit check!\n"); |
| return None; |
| } |
| if (!isSafeToExpandAt(LatchStart, Guard, *SE) || |
| !isSafeToExpandAt(LatchLimit, Guard, *SE)) { |
| LLVM_DEBUG(dbgs() << "Can't expand limit check!\n"); |
| return None; |
| } |
| // The decrement of the latch check IV should be the same as the |
| // rangeCheckIV. |
| auto *PostDecLatchCheckIV = LatchCheck.IV->getPostIncExpr(*SE); |
| if (RangeCheck.IV != PostDecLatchCheckIV) { |
| LLVM_DEBUG(dbgs() << "Not the same. PostDecLatchCheckIV: " |
| << *PostDecLatchCheckIV |
| << " and RangeCheckIV: " << *RangeCheck.IV << "\n"); |
| return None; |
| } |
| |
| // Generate the widened condition for CountDownLoop: |
| // guardStart u< guardLimit && |
| // latchLimit <pred> 1. |
| // See the header comment for reasoning of the checks. |
| auto LimitCheckPred = |
| ICmpInst::getFlippedStrictnessPredicate(LatchCheck.Pred); |
| auto *FirstIterationCheck = expandCheck(Expander, Guard, |
| ICmpInst::ICMP_ULT, |
| GuardStart, GuardLimit); |
| auto *LimitCheck = expandCheck(Expander, Guard, LimitCheckPred, LatchLimit, |
| SE->getOne(Ty)); |
| IRBuilder<> Builder(findInsertPt(Guard, {FirstIterationCheck, LimitCheck})); |
| return Builder.CreateAnd(FirstIterationCheck, LimitCheck); |
| } |
| |
| static void normalizePredicate(ScalarEvolution *SE, Loop *L, |
| LoopICmp& RC) { |
| // LFTR canonicalizes checks to the ICMP_NE/EQ form; normalize back to the |
| // ULT/UGE form for ease of handling by our caller. |
| if (ICmpInst::isEquality(RC.Pred) && |
| RC.IV->getStepRecurrence(*SE)->isOne() && |
| SE->isKnownPredicate(ICmpInst::ICMP_ULE, RC.IV->getStart(), RC.Limit)) |
| RC.Pred = RC.Pred == ICmpInst::ICMP_NE ? |
| ICmpInst::ICMP_ULT : ICmpInst::ICMP_UGE; |
| } |
| |
| |
| /// If ICI can be widened to a loop invariant condition emits the loop |
| /// invariant condition in the loop preheader and return it, otherwise |
| /// returns None. |
| Optional<Value *> LoopPredication::widenICmpRangeCheck(ICmpInst *ICI, |
| SCEVExpander &Expander, |
| Instruction *Guard) { |
| LLVM_DEBUG(dbgs() << "Analyzing ICmpInst condition:\n"); |
| LLVM_DEBUG(ICI->dump()); |
| |
| // parseLoopStructure guarantees that the latch condition is: |
| // ++i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=. |
| // We are looking for the range checks of the form: |
| // i u< guardLimit |
| auto RangeCheck = parseLoopICmp(ICI); |
| if (!RangeCheck) { |
| LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n"); |
| return None; |
| } |
| LLVM_DEBUG(dbgs() << "Guard check:\n"); |
| LLVM_DEBUG(RangeCheck->dump()); |
| if (RangeCheck->Pred != ICmpInst::ICMP_ULT) { |
| LLVM_DEBUG(dbgs() << "Unsupported range check predicate(" |
| << RangeCheck->Pred << ")!\n"); |
| return None; |
| } |
| auto *RangeCheckIV = RangeCheck->IV; |
| if (!RangeCheckIV->isAffine()) { |
| LLVM_DEBUG(dbgs() << "Range check IV is not affine!\n"); |
| return None; |
| } |
| auto *Step = RangeCheckIV->getStepRecurrence(*SE); |
| // We cannot just compare with latch IV step because the latch and range IVs |
| // may have different types. |
| if (!isSupportedStep(Step)) { |
| LLVM_DEBUG(dbgs() << "Range check and latch have IVs different steps!\n"); |
| return None; |
| } |
| auto *Ty = RangeCheckIV->getType(); |
| auto CurrLatchCheckOpt = generateLoopLatchCheck(*DL, *SE, LatchCheck, Ty); |
| if (!CurrLatchCheckOpt) { |
| LLVM_DEBUG(dbgs() << "Failed to generate a loop latch check " |
| "corresponding to range type: " |
| << *Ty << "\n"); |
| return None; |
| } |
| |
| LoopICmp CurrLatchCheck = *CurrLatchCheckOpt; |
| // At this point, the range and latch step should have the same type, but need |
| // not have the same value (we support both 1 and -1 steps). |
| assert(Step->getType() == |
| CurrLatchCheck.IV->getStepRecurrence(*SE)->getType() && |
| "Range and latch steps should be of same type!"); |
| if (Step != CurrLatchCheck.IV->getStepRecurrence(*SE)) { |
| LLVM_DEBUG(dbgs() << "Range and latch have different step values!\n"); |
| return None; |
| } |
| |
| if (Step->isOne()) |
| return widenICmpRangeCheckIncrementingLoop(CurrLatchCheck, *RangeCheck, |
| Expander, Guard); |
| else { |
| assert(Step->isAllOnesValue() && "Step should be -1!"); |
| return widenICmpRangeCheckDecrementingLoop(CurrLatchCheck, *RangeCheck, |
| Expander, Guard); |
| } |
| } |
| |
| unsigned LoopPredication::collectChecks(SmallVectorImpl<Value *> &Checks, |
| Value *Condition, |
| SCEVExpander &Expander, |
| Instruction *Guard) { |
| unsigned NumWidened = 0; |
| // The guard condition is expected to be in form of: |
| // cond1 && cond2 && cond3 ... |
| // Iterate over subconditions looking for icmp conditions which can be |
| // widened across loop iterations. Widening these conditions remember the |
| // resulting list of subconditions in Checks vector. |
| SmallVector<Value *, 4> Worklist(1, Condition); |
| SmallPtrSet<Value *, 4> Visited; |
| Value *WideableCond = nullptr; |
| do { |
| Value *Condition = Worklist.pop_back_val(); |
| if (!Visited.insert(Condition).second) |
| continue; |
| |
| Value *LHS, *RHS; |
| using namespace llvm::PatternMatch; |
| if (match(Condition, m_And(m_Value(LHS), m_Value(RHS)))) { |
| Worklist.push_back(LHS); |
| Worklist.push_back(RHS); |
| continue; |
| } |
| |
| if (match(Condition, |
| m_Intrinsic<Intrinsic::experimental_widenable_condition>())) { |
| // Pick any, we don't care which |
| WideableCond = Condition; |
| continue; |
| } |
| |
| if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) { |
| if (auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander, |
| Guard)) { |
| Checks.push_back(NewRangeCheck.getValue()); |
| NumWidened++; |
| continue; |
| } |
| } |
| |
| // Save the condition as is if we can't widen it |
| Checks.push_back(Condition); |
| } while (!Worklist.empty()); |
| // At the moment, our matching logic for wideable conditions implicitly |
| // assumes we preserve the form: (br (and Cond, WC())). FIXME |
| // Note that if there were multiple calls to wideable condition in the |
| // traversal, we only need to keep one, and which one is arbitrary. |
| if (WideableCond) |
| Checks.push_back(WideableCond); |
| return NumWidened; |
| } |
| |
| bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard, |
| SCEVExpander &Expander) { |
| LLVM_DEBUG(dbgs() << "Processing guard:\n"); |
| LLVM_DEBUG(Guard->dump()); |
| |
| TotalConsidered++; |
| SmallVector<Value *, 4> Checks; |
| unsigned NumWidened = collectChecks(Checks, Guard->getOperand(0), Expander, |
| Guard); |
| if (NumWidened == 0) |
| return false; |
| |
| TotalWidened += NumWidened; |
| |
| // Emit the new guard condition |
| IRBuilder<> Builder(findInsertPt(Guard, Checks)); |
| Value *AllChecks = Builder.CreateAnd(Checks); |
| auto *OldCond = Guard->getOperand(0); |
| Guard->setOperand(0, AllChecks); |
| RecursivelyDeleteTriviallyDeadInstructions(OldCond, nullptr /* TLI */, MSSAU); |
| |
| LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n"); |
| return true; |
| } |
| |
| bool LoopPredication::widenWidenableBranchGuardConditions( |
| BranchInst *BI, SCEVExpander &Expander) { |
| assert(isGuardAsWidenableBranch(BI) && "Must be!"); |
| LLVM_DEBUG(dbgs() << "Processing guard:\n"); |
| LLVM_DEBUG(BI->dump()); |
| |
| TotalConsidered++; |
| SmallVector<Value *, 4> Checks; |
| unsigned NumWidened = collectChecks(Checks, BI->getCondition(), |
| Expander, BI); |
| if (NumWidened == 0) |
| return false; |
| |
| TotalWidened += NumWidened; |
| |
| // Emit the new guard condition |
| IRBuilder<> Builder(findInsertPt(BI, Checks)); |
| Value *AllChecks = Builder.CreateAnd(Checks); |
| auto *OldCond = BI->getCondition(); |
| BI->setCondition(AllChecks); |
| RecursivelyDeleteTriviallyDeadInstructions(OldCond, nullptr /* TLI */, MSSAU); |
| assert(isGuardAsWidenableBranch(BI) && |
| "Stopped being a guard after transform?"); |
| |
| LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n"); |
| return true; |
| } |
| |
| Optional<LoopICmp> LoopPredication::parseLoopLatchICmp() { |
| using namespace PatternMatch; |
| |
| BasicBlock *LoopLatch = L->getLoopLatch(); |
| if (!LoopLatch) { |
| LLVM_DEBUG(dbgs() << "The loop doesn't have a single latch!\n"); |
| return None; |
| } |
| |
| auto *BI = dyn_cast<BranchInst>(LoopLatch->getTerminator()); |
| if (!BI || !BI->isConditional()) { |
| LLVM_DEBUG(dbgs() << "Failed to match the latch terminator!\n"); |
| return None; |
| } |
| BasicBlock *TrueDest = BI->getSuccessor(0); |
| assert( |
| (TrueDest == L->getHeader() || BI->getSuccessor(1) == L->getHeader()) && |
| "One of the latch's destinations must be the header"); |
| |
| auto *ICI = dyn_cast<ICmpInst>(BI->getCondition()); |
| if (!ICI) { |
| LLVM_DEBUG(dbgs() << "Failed to match the latch condition!\n"); |
| return None; |
| } |
| auto Result = parseLoopICmp(ICI); |
| if (!Result) { |
| LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n"); |
| return None; |
| } |
| |
| if (TrueDest != L->getHeader()) |
| Result->Pred = ICmpInst::getInversePredicate(Result->Pred); |
| |
| // Check affine first, so if it's not we don't try to compute the step |
| // recurrence. |
| if (!Result->IV->isAffine()) { |
| LLVM_DEBUG(dbgs() << "The induction variable is not affine!\n"); |
| return None; |
| } |
| |
| auto *Step = Result->IV->getStepRecurrence(*SE); |
| if (!isSupportedStep(Step)) { |
| LLVM_DEBUG(dbgs() << "Unsupported loop stride(" << *Step << ")!\n"); |
| return None; |
| } |
| |
| auto IsUnsupportedPredicate = [](const SCEV *Step, ICmpInst::Predicate Pred) { |
| if (Step->isOne()) { |
| return Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_SLT && |
| Pred != ICmpInst::ICMP_ULE && Pred != ICmpInst::ICMP_SLE; |
| } else { |
| assert(Step->isAllOnesValue() && "Step should be -1!"); |
| return Pred != ICmpInst::ICMP_UGT && Pred != ICmpInst::ICMP_SGT && |
| Pred != ICmpInst::ICMP_UGE && Pred != ICmpInst::ICMP_SGE; |
| } |
| }; |
| |
| normalizePredicate(SE, L, *Result); |
| if (IsUnsupportedPredicate(Step, Result->Pred)) { |
| LLVM_DEBUG(dbgs() << "Unsupported loop latch predicate(" << Result->Pred |
| << ")!\n"); |
| return None; |
| } |
| |
| return Result; |
| } |
| |
| |
| bool LoopPredication::isLoopProfitableToPredicate() { |
| if (SkipProfitabilityChecks) |
| return true; |
| |
| SmallVector<std::pair<BasicBlock *, BasicBlock *>, 8> ExitEdges; |
| L->getExitEdges(ExitEdges); |
| // If there is only one exiting edge in the loop, it is always profitable to |
| // predicate the loop. |
| if (ExitEdges.size() == 1) |
| return true; |
| |
| // Calculate the exiting probabilities of all exiting edges from the loop, |
| // starting with the LatchExitProbability. |
| // Heuristic for profitability: If any of the exiting blocks' probability of |
| // exiting the loop is larger than exiting through the latch block, it's not |
| // profitable to predicate the loop. |
| auto *LatchBlock = L->getLoopLatch(); |
| assert(LatchBlock && "Should have a single latch at this point!"); |
| auto *LatchTerm = LatchBlock->getTerminator(); |
| assert(LatchTerm->getNumSuccessors() == 2 && |
| "expected to be an exiting block with 2 succs!"); |
| unsigned LatchBrExitIdx = |
| LatchTerm->getSuccessor(0) == L->getHeader() ? 1 : 0; |
| // We compute branch probabilities without BPI. We do not rely on BPI since |
| // Loop predication is usually run in an LPM and BPI is only preserved |
| // lossily within loop pass managers, while BPI has an inherent notion of |
| // being complete for an entire function. |
| |
| // If the latch exits into a deoptimize or an unreachable block, do not |
| // predicate on that latch check. |
| auto *LatchExitBlock = LatchTerm->getSuccessor(LatchBrExitIdx); |
| if (isa<UnreachableInst>(LatchTerm) || |
| LatchExitBlock->getTerminatingDeoptimizeCall()) |
| return false; |
| |
| auto IsValidProfileData = [](MDNode *ProfileData, const Instruction *Term) { |
| if (!ProfileData || !ProfileData->getOperand(0)) |
| return false; |
| if (MDString *MDS = dyn_cast<MDString>(ProfileData->getOperand(0))) |
| if (!MDS->getString().equals("branch_weights")) |
| return false; |
| if (ProfileData->getNumOperands() != 1 + Term->getNumSuccessors()) |
| return false; |
| return true; |
| }; |
| MDNode *LatchProfileData = LatchTerm->getMetadata(LLVMContext::MD_prof); |
| // Latch terminator has no valid profile data, so nothing to check |
| // profitability on. |
| if (!IsValidProfileData(LatchProfileData, LatchTerm)) |
| return true; |
| |
| auto ComputeBranchProbability = |
| [&](const BasicBlock *ExitingBlock, |
| const BasicBlock *ExitBlock) -> BranchProbability { |
| auto *Term = ExitingBlock->getTerminator(); |
| MDNode *ProfileData = Term->getMetadata(LLVMContext::MD_prof); |
| unsigned NumSucc = Term->getNumSuccessors(); |
| if (IsValidProfileData(ProfileData, Term)) { |
| uint64_t Numerator = 0, Denominator = 0, ProfVal = 0; |
| for (unsigned i = 0; i < NumSucc; i++) { |
| ConstantInt *CI = |
| mdconst::extract<ConstantInt>(ProfileData->getOperand(i + 1)); |
| ProfVal = CI->getValue().getZExtValue(); |
| if (Term->getSuccessor(i) == ExitBlock) |
| Numerator += ProfVal; |
| Denominator += ProfVal; |
| } |
| return BranchProbability::getBranchProbability(Numerator, Denominator); |
| } else { |
| assert(LatchBlock != ExitingBlock && |
| "Latch term should always have profile data!"); |
| // No profile data, so we choose the weight as 1/num_of_succ(Src) |
| return BranchProbability::getBranchProbability(1, NumSucc); |
| } |
| }; |
| |
| BranchProbability LatchExitProbability = |
| ComputeBranchProbability(LatchBlock, LatchExitBlock); |
| |
| // Protect against degenerate inputs provided by the user. Providing a value |
| // less than one, can invert the definition of profitable loop predication. |
| float ScaleFactor = LatchExitProbabilityScale; |
| if (ScaleFactor < 1) { |
| LLVM_DEBUG( |
| dbgs() |
| << "Ignored user setting for loop-predication-latch-probability-scale: " |
| << LatchExitProbabilityScale << "\n"); |
| LLVM_DEBUG(dbgs() << "The value is set to 1.0\n"); |
| ScaleFactor = 1.0; |
| } |
| const auto LatchProbabilityThreshold = LatchExitProbability * ScaleFactor; |
| |
| for (const auto &ExitEdge : ExitEdges) { |
| BranchProbability ExitingBlockProbability = |
| ComputeBranchProbability(ExitEdge.first, ExitEdge.second); |
| // Some exiting edge has higher probability than the latch exiting edge. |
| // No longer profitable to predicate. |
| if (ExitingBlockProbability > LatchProbabilityThreshold) |
| return false; |
| } |
| |
| // We have concluded that the most probable way to exit from the |
| // loop is through the latch (or there's no profile information and all |
| // exits are equally likely). |
| return true; |
| } |
| |
| /// If we can (cheaply) find a widenable branch which controls entry into the |
| /// loop, return it. |
| static BranchInst *FindWidenableTerminatorAboveLoop(Loop *L, LoopInfo &LI) { |
| // Walk back through any unconditional executed blocks and see if we can find |
| // a widenable condition which seems to control execution of this loop. Note |
| // that we predict that maythrow calls are likely untaken and thus that it's |
| // profitable to widen a branch before a maythrow call with a condition |
| // afterwards even though that may cause the slow path to run in a case where |
| // it wouldn't have otherwise. |
| BasicBlock *BB = L->getLoopPreheader(); |
| if (!BB) |
| return nullptr; |
| do { |
| if (BasicBlock *Pred = BB->getSinglePredecessor()) |
| if (BB == Pred->getSingleSuccessor()) { |
| BB = Pred; |
| continue; |
| } |
| break; |
| } while (true); |
| |
| if (BasicBlock *Pred = BB->getSinglePredecessor()) { |
| auto *Term = Pred->getTerminator(); |
| |
| Value *Cond, *WC; |
| BasicBlock *IfTrueBB, *IfFalseBB; |
| if (parseWidenableBranch(Term, Cond, WC, IfTrueBB, IfFalseBB) && |
| IfTrueBB == BB) |
| return cast<BranchInst>(Term); |
| } |
| return nullptr; |
| } |
| |
| /// Return the minimum of all analyzeable exit counts. This is an upper bound |
| /// on the actual exit count. If there are not at least two analyzeable exits, |
| /// returns SCEVCouldNotCompute. |
| static const SCEV *getMinAnalyzeableBackedgeTakenCount(ScalarEvolution &SE, |
| DominatorTree &DT, |
| Loop *L) { |
| SmallVector<BasicBlock *, 16> ExitingBlocks; |
| L->getExitingBlocks(ExitingBlocks); |
| |
| SmallVector<const SCEV *, 4> ExitCounts; |
| for (BasicBlock *ExitingBB : ExitingBlocks) { |
| const SCEV *ExitCount = SE.getExitCount(L, ExitingBB); |
| if (isa<SCEVCouldNotCompute>(ExitCount)) |
| continue; |
| assert(DT.dominates(ExitingBB, L->getLoopLatch()) && |
| "We should only have known counts for exiting blocks that " |
| "dominate latch!"); |
| ExitCounts.push_back(ExitCount); |
| } |
| if (ExitCounts.size() < 2) |
| return SE.getCouldNotCompute(); |
| return SE.getUMinFromMismatchedTypes(ExitCounts); |
| } |
| |
| /// This implements an analogous, but entirely distinct transform from the main |
| /// loop predication transform. This one is phrased in terms of using a |
| /// widenable branch *outside* the loop to allow us to simplify loop exits in a |
| /// following loop. This is close in spirit to the IndVarSimplify transform |
| /// of the same name, but is materially different widening loosens legality |
| /// sharply. |
| bool LoopPredication::predicateLoopExits(Loop *L, SCEVExpander &Rewriter) { |
| // The transformation performed here aims to widen a widenable condition |
| // above the loop such that all analyzeable exit leading to deopt are dead. |
| // It assumes that the latch is the dominant exit for profitability and that |
| // exits branching to deoptimizing blocks are rarely taken. It relies on the |
| // semantics of widenable expressions for legality. (i.e. being able to fall |
| // down the widenable path spuriously allows us to ignore exit order, |
| // unanalyzeable exits, side effects, exceptional exits, and other challenges |
| // which restrict the applicability of the non-WC based version of this |
| // transform in IndVarSimplify.) |
| // |
| // NOTE ON POISON/UNDEF - We're hoisting an expression above guards which may |
| // imply flags on the expression being hoisted and inserting new uses (flags |
| // are only correct for current uses). The result is that we may be |
| // inserting a branch on the value which can be either poison or undef. In |
| // this case, the branch can legally go either way; we just need to avoid |
| // introducing UB. This is achieved through the use of the freeze |
| // instruction. |
| |
| SmallVector<BasicBlock *, 16> ExitingBlocks; |
| L->getExitingBlocks(ExitingBlocks); |
| |
| if (ExitingBlocks.empty()) |
| return false; // Nothing to do. |
| |
| auto *Latch = L->getLoopLatch(); |
| if (!Latch) |
| return false; |
| |
| auto *WidenableBR = FindWidenableTerminatorAboveLoop(L, *LI); |
| if (!WidenableBR) |
| return false; |
| |
| const SCEV *LatchEC = SE->getExitCount(L, Latch); |
| if (isa<SCEVCouldNotCompute>(LatchEC)) |
| return false; // profitability - want hot exit in analyzeable set |
| |
| // At this point, we have found an analyzeable latch, and a widenable |
| // condition above the loop. If we have a widenable exit within the loop |
| // (for which we can't compute exit counts), drop the ability to further |
| // widen so that we gain ability to analyze it's exit count and perform this |
| // transform. TODO: It'd be nice to know for sure the exit became |
| // analyzeable after dropping widenability. |
| bool ChangedLoop = false; |
| |
| for (auto *ExitingBB : ExitingBlocks) { |
| if (LI->getLoopFor(ExitingBB) != L) |
| continue; |
| |
| auto *BI = dyn_cast<BranchInst>(ExitingBB->getTerminator()); |
| if (!BI) |
| continue; |
| |
| Use *Cond, *WC; |
| BasicBlock *IfTrueBB, *IfFalseBB; |
| if (parseWidenableBranch(BI, Cond, WC, IfTrueBB, IfFalseBB) && |
| L->contains(IfTrueBB)) { |
| WC->set(ConstantInt::getTrue(IfTrueBB->getContext())); |
| ChangedLoop = true; |
| } |
| } |
| if (ChangedLoop) |
| SE->forgetLoop(L); |
| |
| // The use of umin(all analyzeable exits) instead of latch is subtle, but |
| // important for profitability. We may have a loop which hasn't been fully |
| // canonicalized just yet. If the exit we chose to widen is provably never |
| // taken, we want the widened form to *also* be provably never taken. We |
| // can't guarantee this as a current unanalyzeable exit may later become |
| // analyzeable, but we can at least avoid the obvious cases. |
| const SCEV *MinEC = getMinAnalyzeableBackedgeTakenCount(*SE, *DT, L); |
| if (isa<SCEVCouldNotCompute>(MinEC) || MinEC->getType()->isPointerTy() || |
| !SE->isLoopInvariant(MinEC, L) || |
| !isSafeToExpandAt(MinEC, WidenableBR, *SE)) |
| return ChangedLoop; |
| |
| // Subtlety: We need to avoid inserting additional uses of the WC. We know |
| // that it can only have one transitive use at the moment, and thus moving |
| // that use to just before the branch and inserting code before it and then |
| // modifying the operand is legal. |
| auto *IP = cast<Instruction>(WidenableBR->getCondition()); |
| // Here we unconditionally modify the IR, so after this point we should return |
| // only `true`! |
| IP->moveBefore(WidenableBR); |
| if (MSSAU) |
| if (auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(IP)) |
| MSSAU->moveToPlace(MUD, WidenableBR->getParent(), |
| MemorySSA::BeforeTerminator); |
| Rewriter.setInsertPoint(IP); |
| IRBuilder<> B(IP); |
| |
| bool InvalidateLoop = false; |
| Value *MinECV = nullptr; // lazily generated if needed |
| for (BasicBlock *ExitingBB : ExitingBlocks) { |
| // If our exiting block exits multiple loops, we can only rewrite the |
| // innermost one. Otherwise, we're changing how many times the innermost |
| // loop runs before it exits. |
| if (LI->getLoopFor(ExitingBB) != L) |
| continue; |
| |
| // Can't rewrite non-branch yet. |
| auto *BI = dyn_cast<BranchInst>(ExitingBB->getTerminator()); |
| if (!BI) |
| continue; |
| |
| // If already constant, nothing to do. |
| if (isa<Constant>(BI->getCondition())) |
| continue; |
| |
| const SCEV *ExitCount = SE->getExitCount(L, ExitingBB); |
| if (isa<SCEVCouldNotCompute>(ExitCount) || |
| ExitCount->getType()->isPointerTy() || |
| !isSafeToExpandAt(ExitCount, WidenableBR, *SE)) |
| continue; |
| |
| const bool ExitIfTrue = !L->contains(*succ_begin(ExitingBB)); |
| BasicBlock *ExitBB = BI->getSuccessor(ExitIfTrue ? 0 : 1); |
| if (!ExitBB->getPostdominatingDeoptimizeCall()) |
| continue; |
| |
| /// Here we can be fairly sure that executing this exit will most likely |
| /// lead to executing llvm.experimental.deoptimize. |
| /// This is a profitability heuristic, not a legality constraint. |
| |
| // If we found a widenable exit condition, do two things: |
| // 1) fold the widened exit test into the widenable condition |
| // 2) fold the branch to untaken - avoids infinite looping |
| |
| Value *ECV = Rewriter.expandCodeFor(ExitCount); |
| if (!MinECV) |
| MinECV = Rewriter.expandCodeFor(MinEC); |
| Value *RHS = MinECV; |
| if (ECV->getType() != RHS->getType()) { |
| Type *WiderTy = SE->getWiderType(ECV->getType(), RHS->getType()); |
| ECV = B.CreateZExt(ECV, WiderTy); |
| RHS = B.CreateZExt(RHS, WiderTy); |
| } |
| assert(!Latch || DT->dominates(ExitingBB, Latch)); |
| Value *NewCond = B.CreateICmp(ICmpInst::ICMP_UGT, ECV, RHS); |
| // Freeze poison or undef to an arbitrary bit pattern to ensure we can |
| // branch without introducing UB. See NOTE ON POISON/UNDEF above for |
| // context. |
| NewCond = B.CreateFreeze(NewCond); |
| |
| widenWidenableBranch(WidenableBR, NewCond); |
| |
| Value *OldCond = BI->getCondition(); |
| BI->setCondition(ConstantInt::get(OldCond->getType(), !ExitIfTrue)); |
| InvalidateLoop = true; |
| } |
| |
| if (InvalidateLoop) |
| // We just mutated a bunch of loop exits changing there exit counts |
| // widely. We need to force recomputation of the exit counts given these |
| // changes. Note that all of the inserted exits are never taken, and |
| // should be removed next time the CFG is modified. |
| SE->forgetLoop(L); |
| |
| // Always return `true` since we have moved the WidenableBR's condition. |
| return true; |
| } |
| |
| bool LoopPredication::runOnLoop(Loop *Loop) { |
| L = Loop; |
| |
| LLVM_DEBUG(dbgs() << "Analyzing "); |
| LLVM_DEBUG(L->dump()); |
| |
| Module *M = L->getHeader()->getModule(); |
| |
| // There is nothing to do if the module doesn't use guards |
| auto *GuardDecl = |
| M->getFunction(Intrinsic::getName(Intrinsic::experimental_guard)); |
| bool HasIntrinsicGuards = GuardDecl && !GuardDecl->use_empty(); |
| auto *WCDecl = M->getFunction( |
| Intrinsic::getName(Intrinsic::experimental_widenable_condition)); |
| bool HasWidenableConditions = |
| PredicateWidenableBranchGuards && WCDecl && !WCDecl->use_empty(); |
| if (!HasIntrinsicGuards && !HasWidenableConditions) |
| return false; |
| |
| DL = &M->getDataLayout(); |
| |
| Preheader = L->getLoopPreheader(); |
| if (!Preheader) |
| return false; |
| |
| auto LatchCheckOpt = parseLoopLatchICmp(); |
| if (!LatchCheckOpt) |
| return false; |
| LatchCheck = *LatchCheckOpt; |
| |
| LLVM_DEBUG(dbgs() << "Latch check:\n"); |
| LLVM_DEBUG(LatchCheck.dump()); |
| |
| if (!isLoopProfitableToPredicate()) { |
| LLVM_DEBUG(dbgs() << "Loop not profitable to predicate!\n"); |
| return false; |
| } |
| // Collect all the guards into a vector and process later, so as not |
| // to invalidate the instruction iterator. |
| SmallVector<IntrinsicInst *, 4> Guards; |
| SmallVector<BranchInst *, 4> GuardsAsWidenableBranches; |
| for (const auto BB : L->blocks()) { |
| for (auto &I : *BB) |
| if (isGuard(&I)) |
| Guards.push_back(cast<IntrinsicInst>(&I)); |
| if (PredicateWidenableBranchGuards && |
| isGuardAsWidenableBranch(BB->getTerminator())) |
| GuardsAsWidenableBranches.push_back( |
| cast<BranchInst>(BB->getTerminator())); |
| } |
| |
| SCEVExpander Expander(*SE, *DL, "loop-predication"); |
| bool Changed = false; |
| for (auto *Guard : Guards) |
| Changed |= widenGuardConditions(Guard, Expander); |
| for (auto *Guard : GuardsAsWidenableBranches) |
| Changed |= widenWidenableBranchGuardConditions(Guard, Expander); |
| Changed |= predicateLoopExits(L, Expander); |
| |
| if (MSSAU && VerifyMemorySSA) |
| MSSAU->getMemorySSA()->verifyMemorySSA(); |
| return Changed; |
| } |