Lines Matching defs:SE
144 static bool parseRangeCheckICmp(Loop *L, ICmpInst *ICI, ScalarEvolution &SE,
149 extractRangeChecksFromCond(Loop *L, ScalarEvolution &SE, Use &ConditionUse,
154 ICmpInst::Predicate Pred, ScalarEvolution &SE,
159 ICmpInst::Predicate Pred, ScalarEvolution &SE,
202 bool isEmpty(ScalarEvolution &SE, bool IsSigned) const {
206 return SE.isKnownPredicate(ICmpInst::ICMP_SGE, Begin, End);
208 return SE.isKnownPredicate(ICmpInst::ICMP_UGE, Begin, End);
219 std::optional<Range> computeSafeIterationSpace(ScalarEvolution &SE,
229 BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo *BPI,
235 ScalarEvolution &SE;
250 InductiveRangeCheckElimination(ScalarEvolution &SE,
253 : SE(SE), BPI(BPI), DT(DT), LI(LI), GetBFI(GetBFI) {}
265 ScalarEvolution &SE,
268 auto IsLoopInvariant = [&SE, L](Value *V) {
269 return SE.isLoopInvariant(SE.getSCEV(V), L);
287 if (parseIvAgaisntLimit(L, LHS, RHS, Pred, SE, Index, End))
290 if (reassociateSubLHS(L, LHS, RHS, Pred, SE, Index, End))
300 ScalarEvolution &SE,
306 return SE.getConstant(APInt::getSignedMaxValue(BitWidth));
309 const auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(LHS));
340 End = SE.getSCEV(RHS);
345 const SCEV *One = SE.getOne(RHS->getType());
346 const SCEV *RHSS = SE.getSCEV(RHS);
348 if (SE.willNotOverflow(Instruction::BinaryOps::Add, Signed, RHSS, One)) {
350 End = SE.getAddExpr(RHSS, One);
363 ScalarEvolution &SE, const SCEVAddRecExpr *&Index, const SCEV *&End) {
368 const SCEV *IV = SE.getSCEV(LHS);
369 const SCEV *Offset = SE.getSCEV(RHS);
370 const SCEV *Limit = SE.getSCEV(InvariantRHS);
373 if (SE.isLoopInvariant(IV, L))
376 else if (SE.isLoopInvariant(Offset, L))
440 if (SE.willNotOverflow(BinOp, ICmpInst::isSigned(Pred), LHS, RHS,
442 return (SE.*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0);
451 return (SE.*Operation)(SE.getSignExtendExpr(LHS, WideTy),
452 SE.getSignExtendExpr(RHS, WideTy), SCEV::FlagAnyWrap,
469 SE.getOne(Limit->getType()));
480 Loop *L, ScalarEvolution &SE, Use &ConditionUse,
489 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(0),
491 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(1),
502 if (!parseRangeCheckICmp(L, ICI, SE, IndexAddRec, End))
514 IRC.Step = IndexAddRec->getStepRecurrence(SE);
520 BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo *BPI,
567 InductiveRangeCheck::extractRangeChecksFromCond(L, SE, BI->getOperandUse(0),
573 static const SCEV *NoopOrExtend(const SCEV *S, Type *Ty, ScalarEvolution &SE,
575 return Signed ? SE.getNoopOrSignExtend(S, Ty) : SE.getNoopOrZeroExtend(S, Ty);
582 calculateSubRanges(ScalarEvolution &SE, const Loop &L,
598 const SCEV *Start = NoopOrExtend(SE.getSCEV(MainLoopStructure.IndVarStart),
599 RTy, SE, IsSignedPredicate);
600 const SCEV *End = NoopOrExtend(SE.getSCEV(MainLoopStructure.LoopExitAt), RTy,
601 SE, IsSignedPredicate);
611 const SCEV *One = SE.getOne(RTy);
616 GreatestSeen = SE.getMinusSCEV(End, One);
633 Smallest = SE.getAddExpr(End, One);
634 Greatest = SE.getAddExpr(Start, One);
638 auto Clamp = [&SE, Smallest, Greatest, IsSignedPredicate](const SCEV *S) {
640 ? SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S))
641 : SE.getUMaxExpr(Smallest, SE.getUMinExpr(Greatest, S));
651 SE.isKnownPredicate(PredLE, Range.getBegin(), Smallest);
656 SE.isKnownPredicate(PredLT, GreatestSeen, Range.getEnd());
667 InductiveRangeCheck::computeSafeIterationSpace(ScalarEvolution &SE,
704 const SCEV *A = NoopOrExtend(IndVar->getStart(), RCType, SE, IsLatchSigned);
706 NoopOrExtend(IndVar->getStepRecurrence(SE), RCType, SE, IsLatchSigned));
718 const SCEV *SIntMax = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
719 const SCEV *SIntMin = SE.getConstant(APInt::getSignedMinValue(BitWidth));
749 const SCEV *XMinusSIntMax = SE.getMinusSCEV(X, SIntMax);
750 return SE.getMinusSCEV(X, SE.getSMaxExpr(Y, XMinusSIntMax),
763 return SE.getMinusSCEV(X, SE.getSMinExpr(X, Y), SCEV::FlagNUW);
765 const SCEV *M = SE.getMinusSCEV(C, A);
766 const SCEV *Zero = SE.getZero(M->getType());
771 const SCEV *Zero = SE.getZero(X->getType());
772 const SCEV *One = SE.getOne(X->getType());
774 if (isKnownNonNegativeInLoop(X, L, SE))
776 else if (isKnownNegativeInLoop(X, L, SE))
780 const SCEV *NegOne = SE.getNegativeSCEV(One);
781 return SE.getAddExpr(SE.getSMaxExpr(SE.getSMinExpr(X, Zero), NegOne), One);
789 const SCEV *SIntMaxExt = SE.getSignExtendExpr(SIntMax, X->getType());
791 SCEVCheckNonNegative(SE.getMinusSCEV(SIntMaxExt, X));
795 const SCEV *SIntMinExt = SE.getSignExtendExpr(SIntMin, X->getType());
797 SCEVCheckNonNegative(SE.getMinusSCEV(X, SIntMinExt));
799 return SE.getMulExpr(OverflowCheck, UnderflowCheck);
811 const SCEV *EndWillNotOverflow = SE.getOne(RCType);
831 SE.getTruncateExpr(SCEVCheckWillNotOverflow(REnd), RCType);
832 REnd = SE.getTruncateExpr(REnd, RCType);
836 SE.getMulExpr(SCEVCheckNonNegative(REnd), EndWillNotOverflow);
837 const SCEV *Begin = SE.getMulExpr(ClampedSubtract(Zero, M), RuntimeChecks);
838 const SCEV *End = SE.getMulExpr(ClampedSubtract(REnd, M), RuntimeChecks);
844 IntersectSignedRange(ScalarEvolution &SE,
847 if (R2.isEmpty(SE, /* IsSigned */ true))
854 assert(!R1Value.isEmpty(SE, /* IsSigned */ true) &&
862 const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin());
863 const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd());
867 if (Ret.isEmpty(SE, /* IsSigned */ true))
873 IntersectUnsignedRange(ScalarEvolution &SE,
876 if (R2.isEmpty(SE, /* IsSigned */ false))
883 assert(!R1Value.isEmpty(SE, /* IsSigned */ false) &&
891 const SCEV *NewBegin = SE.getUMaxExpr(R1Value.getBegin(), R2.getBegin());
892 const SCEV *NewEnd = SE.getUMinExpr(R1Value.getEnd(), R2.getEnd());
896 if (Ret.isEmpty(SE, /* IsSigned */ false))
908 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
916 InductiveRangeCheckElimination IRCE(SE, &BPI, DT, LI, { getBFI });
922 CFGChanged |= simplifyLoop(L, &DT, &LI, &SE, nullptr, nullptr,
924 Changed |= formLCSSARecursively(*L, DT, &LI, &SE);
1018 TBI, L, SE, BPI, EstimatedTripCount, RangeChecks, Changed);
1038 LoopStructure::parseLoopStructure(SE, *L, AllowUnsignedLatchCondition,
1047 cast<SCEVAddRecExpr>(SE.getMinusSCEV(SE.getSCEV(LS.IndVarBase), SE.getSCEV(LS.IndVarStep)));
1060 auto Result = IRC.computeSafeIterationSpace(SE, IndVar,
1063 auto MaybeSafeIterRange = IntersectRange(SE, SafeIterRange, *Result);
1065 assert(!MaybeSafeIterRange->isEmpty(SE, LS.IsSignedPredicate) &&
1077 calculateSubRanges(SE, *L, *SafeIterRange, LS);
1083 LoopConstrainer LC(*L, LI, LPMAddNewLoop, LS, SE, DT,