Index: lib/Transforms/Scalar/LoopPredication.cpp =================================================================== --- lib/Transforms/Scalar/LoopPredication.cpp +++ lib/Transforms/Scalar/LoopPredication.cpp @@ -189,6 +189,10 @@ 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 @@ 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 @@ 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 @@ 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 @@ 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 @@ 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 @@ // 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 @@ 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 @@ } 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 @@ 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;