From 68797214533e898b1e596a873304e7398d9d4a73 Mon Sep 17 00:00:00 2001 From: Anna Thomas Date: Fri, 3 Nov 2017 14:25:39 +0000 Subject: [PATCH] [LoopPredication] NFC: Refactored code to separate out functions being reused Summary: Refactored the code to separate out common functions that are being reused. This is to reduce the changes for changes coming up wrt loop predication with reverse loops. This refactoring is what we have in our downstream code. llvm-svn: 317324 --- llvm/lib/Transforms/Scalar/LoopPredication.cpp | 154 +++++++++++++++---------- 1 file changed, 92 insertions(+), 62 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/LoopPredication.cpp b/llvm/lib/Transforms/Scalar/LoopPredication.cpp index e680fbe..52dea32 100644 --- a/llvm/lib/Transforms/Scalar/LoopPredication.cpp +++ b/llvm/lib/Transforms/Scalar/LoopPredication.cpp @@ -189,6 +189,10 @@ class LoopPredication { const SCEV *Limit) : Pred(Pred), IV(IV), Limit(Limit) {} LoopICmp() {} + void dump() { + dbgs() << "LoopICmp Pred = " << Pred << ", IV = " << *IV + << ", Limit = " << *Limit << "\n"; + } }; ScalarEvolution *SE; @@ -198,6 +202,7 @@ class LoopPredication { BasicBlock *Preheader; LoopICmp LatchCheck; + bool isSupportedStep(const SCEV* Step); Optional parseLoopICmp(ICmpInst *ICI) { return parseLoopICmp(ICI->getPredicate(), ICI->getOperand(0), ICI->getOperand(1)); @@ -207,12 +212,18 @@ class LoopPredication { Optional parseLoopLatchICmp(); + bool CanExpand(const SCEV* S); Value *expandCheck(SCEVExpander &Expander, IRBuilder<> &Builder, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, Instruction *InsertAt); Optional widenICmpRangeCheck(ICmpInst *ICI, SCEVExpander &Expander, IRBuilder<> &Builder); + Optional widenICmpRangeCheckIncrementingLoop(LoopICmp LatchCheck, + LoopICmp RangeCheck, + SCEVExpander &Expander, + IRBuilder<> &Builder); + bool widenGuardConditions(IntrinsicInst *II, SCEVExpander &Expander); // When the IV type is wider than the range operand type, we can still do loop @@ -348,6 +359,67 @@ LoopPredication::generateLoopLatchCheck(Type *RangeCheckType) { return NewLatchCheck; } +bool LoopPredication::isSupportedStep(const SCEV* Step) { + return Step->isOne(); +} + +bool LoopPredication::CanExpand(const SCEV* S) { + return SE->isLoopInvariant(S, L) && isSafeToExpand(S, *SE); +} + +Optional LoopPredication::widenICmpRangeCheckIncrementingLoop( + LoopPredication::LoopICmp LatchCheck, LoopPredication::LoopICmp RangeCheck, + SCEVExpander &Expander, IRBuilder<> &Builder) { + auto *Ty = RangeCheck.IV->getType(); + // Generate the widened condition for the forward loop: + // guardStart u< guardLimit && + // latchLimit guardLimit - 1 - guardStart + latchStart + // where 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; + + // guardLimit - guardStart + latchStart - 1 + const SCEV *RHS = + SE->getAddExpr(SE->getMinusSCEV(GuardLimit, GuardStart), + SE->getMinusSCEV(LatchStart, SE->getOne(Ty))); + if (!CanExpand(GuardStart) || !CanExpand(GuardLimit) || + !CanExpand(LatchLimit) || !CanExpand(RHS)) { + DEBUG(dbgs() << "Can't expand limit check!\n"); + return None; + } + ICmpInst::Predicate LimitCheckPred; + switch (LatchCheck.Pred) { + case ICmpInst::ICMP_ULT: + LimitCheckPred = ICmpInst::ICMP_ULE; + break; + case ICmpInst::ICMP_ULE: + LimitCheckPred = ICmpInst::ICMP_ULT; + break; + case ICmpInst::ICMP_SLT: + LimitCheckPred = ICmpInst::ICMP_SLE; + break; + case ICmpInst::ICMP_SLE: + LimitCheckPred = ICmpInst::ICMP_SLT; + break; + default: + llvm_unreachable("Unsupported loop latch!"); + } + + DEBUG(dbgs() << "LHS: " << *LatchLimit << "\n"); + DEBUG(dbgs() << "RHS: " << *RHS << "\n"); + DEBUG(dbgs() << "Pred: " << LimitCheckPred << "\n"); + + Instruction *InsertAt = Preheader->getTerminator(); + auto *LimitCheck = + expandCheck(Expander, Builder, LimitCheckPred, LatchLimit, RHS, InsertAt); + auto *FirstIterationCheck = expandCheck(Expander, Builder, RangeCheck.Pred, + GuardStart, GuardLimit, InsertAt); + return Builder.CreateAnd(FirstIterationCheck, LimitCheck); +} /// 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. @@ -366,6 +438,8 @@ Optional LoopPredication::widenICmpRangeCheck(ICmpInst *ICI, DEBUG(dbgs() << "Failed to parse the loop latch condition!\n"); return None; } + DEBUG(dbgs() << "Guard check:\n"); + DEBUG(RangeCheck->dump()); if (RangeCheck->Pred != ICmpInst::ICMP_ULT) { DEBUG(dbgs() << "Unsupported range check predicate(" << RangeCheck->Pred << ")!\n"); @@ -379,7 +453,7 @@ Optional LoopPredication::widenICmpRangeCheck(ICmpInst *ICI, auto *Step = RangeCheckIV->getStepRecurrence(*SE); // We cannot just compare with latch IV step because the latch and range IVs // may have different types. - if (!Step->isOne()) { + if (!isSupportedStep(Step)) { DEBUG(dbgs() << "Range check and latch have IVs different steps!\n"); return None; } @@ -397,58 +471,9 @@ Optional LoopPredication::widenICmpRangeCheck(ICmpInst *ICI, // value and type. assert(Step == CurrLatchCheck.IV->getStepRecurrence(*SE) && "Range and latch should have same step recurrence!"); - // Generate the widened condition: - // guardStart u< guardLimit && - // latchLimit guardLimit - 1 - guardStart + latchStart - // where depends on the latch condition predicate. See the file - // header comment for the reasoning. - const SCEV *GuardStart = RangeCheckIV->getStart(); - const SCEV *GuardLimit = RangeCheck->Limit; - const SCEV *LatchStart = CurrLatchCheck.IV->getStart(); - const SCEV *LatchLimit = CurrLatchCheck.Limit; - - // guardLimit - guardStart + latchStart - 1 - const SCEV *RHS = - SE->getAddExpr(SE->getMinusSCEV(GuardLimit, GuardStart), - SE->getMinusSCEV(LatchStart, SE->getOne(Ty))); - - ICmpInst::Predicate LimitCheckPred; - switch (CurrLatchCheck.Pred) { - case ICmpInst::ICMP_ULT: - LimitCheckPred = ICmpInst::ICMP_ULE; - break; - case ICmpInst::ICMP_ULE: - LimitCheckPred = ICmpInst::ICMP_ULT; - break; - case ICmpInst::ICMP_SLT: - LimitCheckPred = ICmpInst::ICMP_SLE; - break; - case ICmpInst::ICMP_SLE: - LimitCheckPred = ICmpInst::ICMP_SLT; - break; - default: - llvm_unreachable("Unsupported loop latch!"); - } - DEBUG(dbgs() << "LHS: " << *LatchLimit << "\n"); - DEBUG(dbgs() << "RHS: " << *RHS << "\n"); - DEBUG(dbgs() << "Pred: " << LimitCheckPred << "\n"); - - auto CanExpand = [this](const SCEV *S) { - return SE->isLoopInvariant(S, L) && isSafeToExpand(S, *SE); - }; - if (!CanExpand(GuardStart) || !CanExpand(GuardLimit) || - !CanExpand(LatchLimit) || !CanExpand(RHS)) { - DEBUG(dbgs() << "Can't expand limit check!\n"); - return None; - } - - Instruction *InsertAt = Preheader->getTerminator(); - auto *LimitCheck = - expandCheck(Expander, Builder, LimitCheckPred, LatchLimit, RHS, InsertAt); - auto *FirstIterationCheck = expandCheck(Expander, Builder, RangeCheck->Pred, - GuardStart, GuardLimit, InsertAt); - return Builder.CreateAnd(FirstIterationCheck, LimitCheck); + return widenICmpRangeCheckIncrementingLoop(CurrLatchCheck, *RangeCheck, + Expander, Builder); } bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard, @@ -541,15 +566,6 @@ Optional LoopPredication::parseLoopLatchICmp() { return None; } - if (Result->Pred != ICmpInst::ICMP_ULT && - Result->Pred != ICmpInst::ICMP_SLT && - Result->Pred != ICmpInst::ICMP_ULE && - Result->Pred != ICmpInst::ICMP_SLE) { - DEBUG(dbgs() << "Unsupported loop latch predicate(" << Result->Pred - << ")!\n"); - return None; - } - // Check affine first, so if it's not we don't try to compute the step // recurrence. if (!Result->IV->isAffine()) { @@ -558,11 +574,22 @@ Optional LoopPredication::parseLoopLatchICmp() { } auto *Step = Result->IV->getStepRecurrence(*SE); - if (!Step->isOne()) { + if (!isSupportedStep(Step)) { DEBUG(dbgs() << "Unsupported loop stride(" << *Step << ")!\n"); return None; } + auto IsUnsupportedPredicate = [](const SCEV *Step, ICmpInst::Predicate Pred) { + assert(Step->isOne() && "expected Step to be one!"); + return Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_SLT && + Pred != ICmpInst::ICMP_ULE && Pred != ICmpInst::ICMP_SLE; + }; + + if (IsUnsupportedPredicate(Step, Result->Pred)) { + DEBUG(dbgs() << "Unsupported loop latch predicate(" << Result->Pred + << ")!\n"); + return None; + } return Result; } @@ -621,6 +648,9 @@ bool LoopPredication::runOnLoop(Loop *Loop) { return false; LatchCheck = *LatchCheckOpt; + DEBUG(dbgs() << "Latch check:\n"); + DEBUG(LatchCheck.dump()); + // Collect all the guards into a vector and process later, so as not // to invalidate the instruction iterator. SmallVector Guards; -- 2.7.4