| //===-- LoopPredication.cpp - Guard based loop predication pass -----------===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // 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 |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "llvm/Transforms/Scalar/LoopPredication.h" |
| #include "llvm/Analysis/LoopInfo.h" |
| #include "llvm/Analysis/LoopPass.h" |
| #include "llvm/Analysis/ScalarEvolution.h" |
| #include "llvm/Analysis/ScalarEvolutionExpander.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/Pass.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Transforms/Scalar.h" |
| #include "llvm/Transforms/Utils/LoopUtils.h" |
| |
| #define DEBUG_TYPE "loop-predication" |
| |
| using namespace llvm; |
| |
| namespace { |
| class LoopPredication { |
| /// 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() {} |
| }; |
| |
| ScalarEvolution *SE; |
| |
| Loop *L; |
| const DataLayout *DL; |
| BasicBlock *Preheader; |
| |
| Optional<LoopICmp> parseLoopICmp(ICmpInst *ICI); |
| |
| Value *expandCheck(SCEVExpander &Expander, IRBuilder<> &Builder, |
| ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, |
| Instruction *InsertAt); |
| |
| Optional<Value *> widenICmpRangeCheck(ICmpInst *ICI, SCEVExpander &Expander, |
| IRBuilder<> &Builder); |
| bool widenGuardConditions(IntrinsicInst *II, SCEVExpander &Expander); |
| |
| public: |
| LoopPredication(ScalarEvolution *SE) : SE(SE){}; |
| bool runOnLoop(Loop *L); |
| }; |
| |
| class LoopPredicationLegacyPass : public LoopPass { |
| public: |
| static char ID; |
| LoopPredicationLegacyPass() : LoopPass(ID) { |
| initializeLoopPredicationLegacyPassPass(*PassRegistry::getPassRegistry()); |
| } |
| |
| void getAnalysisUsage(AnalysisUsage &AU) const override { |
| getLoopAnalysisUsage(AU); |
| } |
| |
| bool runOnLoop(Loop *L, LPPassManager &LPM) override { |
| if (skipLoop(L)) |
| return false; |
| auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); |
| LoopPredication LP(SE); |
| return LP.runOnLoop(L); |
| } |
| }; |
| |
| char LoopPredicationLegacyPass::ID = 0; |
| } // end namespace llvm |
| |
| INITIALIZE_PASS_BEGIN(LoopPredicationLegacyPass, "loop-predication", |
| "Loop predication", false, false) |
| 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) { |
| LoopPredication LP(&AR.SE); |
| if (!LP.runOnLoop(&L)) |
| return PreservedAnalyses::all(); |
| |
| return getLoopPassPreservedAnalyses(); |
| } |
| |
| Optional<LoopPredication::LoopICmp> |
| LoopPredication::parseLoopICmp(ICmpInst *ICI) { |
| ICmpInst::Predicate Pred = ICI->getPredicate(); |
| |
| Value *LHS = ICI->getOperand(0); |
| Value *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, |
| IRBuilder<> &Builder, |
| ICmpInst::Predicate Pred, const SCEV *LHS, |
| const SCEV *RHS, Instruction *InsertAt) { |
| Type *Ty = LHS->getType(); |
| assert(Ty == RHS->getType() && "expandCheck operands have different types?"); |
| Value *LHSV = Expander.expandCodeFor(LHS, Ty, InsertAt); |
| Value *RHSV = Expander.expandCodeFor(RHS, Ty, InsertAt); |
| return Builder.CreateICmp(Pred, LHSV, RHSV); |
| } |
| |
| /// 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, |
| IRBuilder<> &Builder) { |
| DEBUG(dbgs() << "Analyzing ICmpInst condition:\n"); |
| DEBUG(ICI->dump()); |
| |
| auto RangeCheck = parseLoopICmp(ICI); |
| if (!RangeCheck) { |
| DEBUG(dbgs() << "Failed to parse the loop latch condition!\n"); |
| return None; |
| } |
| |
| ICmpInst::Predicate Pred = RangeCheck->Pred; |
| const SCEVAddRecExpr *IndexAR = RangeCheck->IV; |
| const SCEV *RHSS = RangeCheck->Limit; |
| |
| auto CanExpand = [this](const SCEV *S) { |
| return SE->isLoopInvariant(S, L) && isSafeToExpand(S, *SE); |
| }; |
| if (!CanExpand(RHSS)) |
| return None; |
| |
| DEBUG(dbgs() << "IndexAR: "); |
| DEBUG(IndexAR->dump()); |
| |
| bool IsIncreasing = false; |
| if (!SE->isMonotonicPredicate(IndexAR, Pred, IsIncreasing)) |
| return None; |
| |
| // If the predicate is increasing the condition can change from false to true |
| // as the loop progresses, in this case take the value on the first iteration |
| // for the widened check. Otherwise the condition can change from true to |
| // false as the loop progresses, so take the value on the last iteration. |
| const SCEV *NewLHSS = IsIncreasing |
| ? IndexAR->getStart() |
| : SE->getSCEVAtScope(IndexAR, L->getParentLoop()); |
| if (NewLHSS == IndexAR) { |
| DEBUG(dbgs() << "Can't compute NewLHSS!\n"); |
| return None; |
| } |
| |
| DEBUG(dbgs() << "NewLHSS: "); |
| DEBUG(NewLHSS->dump()); |
| |
| if (!CanExpand(NewLHSS)) |
| return None; |
| |
| DEBUG(dbgs() << "NewLHSS is loop invariant and safe to expand. Expand!\n"); |
| |
| Instruction *InsertAt = Preheader->getTerminator(); |
| return expandCheck(Expander, Builder, Pred, NewLHSS, RHSS, InsertAt); |
| } |
| |
| bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard, |
| SCEVExpander &Expander) { |
| DEBUG(dbgs() << "Processing guard:\n"); |
| DEBUG(Guard->dump()); |
| |
| IRBuilder<> Builder(cast<Instruction>(Preheader->getTerminator())); |
| |
| // The guard condition is expected to be in form of: |
| // cond1 && cond2 && cond3 ... |
| // Iterate over subconditions looking for 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, Guard->getOperand(0)); |
| SmallPtrSet<Value *, 4> Visited; |
| |
| SmallVector<Value *, 4> Checks; |
| |
| unsigned NumWidened = 0; |
| 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 (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) { |
| if (auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander, Builder)) { |
| Checks.push_back(NewRangeCheck.getValue()); |
| NumWidened++; |
| continue; |
| } |
| } |
| |
| // Save the condition as is if we can't widen it |
| Checks.push_back(Condition); |
| } while (Worklist.size() != 0); |
| |
| if (NumWidened == 0) |
| return false; |
| |
| // Emit the new guard condition |
| Builder.SetInsertPoint(Guard); |
| Value *LastCheck = nullptr; |
| for (auto *Check : Checks) |
| if (!LastCheck) |
| LastCheck = Check; |
| else |
| LastCheck = Builder.CreateAnd(LastCheck, Check); |
| Guard->setOperand(0, LastCheck); |
| |
| DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n"); |
| return true; |
| } |
| |
| bool LoopPredication::runOnLoop(Loop *Loop) { |
| L = Loop; |
| |
| DEBUG(dbgs() << "Analyzing "); |
| 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)); |
| if (!GuardDecl || GuardDecl->use_empty()) |
| return false; |
| |
| DL = &M->getDataLayout(); |
| |
| Preheader = L->getLoopPreheader(); |
| if (!Preheader) |
| return false; |
| |
| // Collect all the guards into a vector and process later, so as not |
| // to invalidate the instruction iterator. |
| SmallVector<IntrinsicInst *, 4> Guards; |
| for (const auto BB : L->blocks()) |
| for (auto &I : *BB) |
| if (auto *II = dyn_cast<IntrinsicInst>(&I)) |
| if (II->getIntrinsicID() == Intrinsic::experimental_guard) |
| Guards.push_back(II); |
| |
| if (Guards.empty()) |
| return false; |
| |
| SCEVExpander Expander(*SE, *DL, "loop-predication"); |
| |
| bool Changed = false; |
| for (auto *Guard : Guards) |
| Changed |= widenGuardConditions(Guard, Expander); |
| |
| return Changed; |
| } |