Lines Matching defs:SE
152 static bool parseRangeCheckICmp(Loop *L, ICmpInst *ICI, ScalarEvolution &SE,
157 extractRangeChecksFromCond(Loop *L, ScalarEvolution &SE, Use &ConditionUse,
162 ICmpInst::Predicate Pred, ScalarEvolution &SE,
167 ICmpInst::Predicate Pred, ScalarEvolution &SE,
210 bool isEmpty(ScalarEvolution &SE, bool IsSigned) const {
214 return SE.isKnownPredicate(ICmpInst::ICMP_SGE, Begin, End);
216 return SE.isKnownPredicate(ICmpInst::ICMP_UGE, Begin, End);
227 std::optional<Range> computeSafeIterationSpace(ScalarEvolution &SE,
237 BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo *BPI,
242 ScalarEvolution &SE;
256 InductiveRangeCheckElimination(ScalarEvolution &SE,
259 : SE(SE), BPI(BPI), DT(DT), LI(LI), GetBFI(GetBFI) {}
271 ScalarEvolution &SE,
274 auto IsLoopInvariant = [&SE, L](Value *V) {
275 return SE.isLoopInvariant(SE.getSCEV(V), L);
293 if (parseIvAgaisntLimit(L, LHS, RHS, Pred, SE, Index, End))
296 if (reassociateSubLHS(L, LHS, RHS, Pred, SE, Index, End))
306 ScalarEvolution &SE,
312 return SE.getConstant(APInt::getSignedMaxValue(BitWidth));
315 const auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(LHS));
346 End = SE.getSCEV(RHS);
351 const SCEV *One = SE.getOne(RHS->getType());
352 const SCEV *RHSS = SE.getSCEV(RHS);
354 if (SE.willNotOverflow(Instruction::BinaryOps::Add, Signed, RHSS, One)) {
356 End = SE.getAddExpr(RHSS, One);
369 ScalarEvolution &SE, const SCEVAddRecExpr *&Index, const SCEV *&End) {
374 const SCEV *IV = SE.getSCEV(LHS);
375 const SCEV *Offset = SE.getSCEV(RHS);
376 const SCEV *Limit = SE.getSCEV(InvariantRHS);
379 if (SE.isLoopInvariant(IV, L))
382 else if (SE.isLoopInvariant(Offset, L))
446 if (SE.willNotOverflow(BinOp, ICmpInst::isSigned(Pred), LHS, RHS,
448 return (SE.*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0);
457 return (SE.*Operation)(SE.getSignExtendExpr(LHS, WideTy),
458 SE.getSignExtendExpr(RHS, WideTy), SCEV::FlagAnyWrap,
475 SE.getOne(Limit->getType()));
486 Loop *L, ScalarEvolution &SE, Use &ConditionUse,
495 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(0),
497 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(1),
508 if (!parseRangeCheckICmp(L, ICI, SE, IndexAddRec, End))
520 IRC.Step = IndexAddRec->getStepRecurrence(SE);
526 BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo *BPI,
551 InductiveRangeCheck::extractRangeChecksFromCond(L, SE, BI->getOperandUse(0),
557 static const SCEV *NoopOrExtend(const SCEV *S, Type *Ty, ScalarEvolution &SE,
559 return Signed ? SE.getNoopOrSignExtend(S, Ty) : SE.getNoopOrZeroExtend(S, Ty);
566 calculateSubRanges(ScalarEvolution &SE, const Loop &L,
582 const SCEV *Start = NoopOrExtend(SE.getSCEV(MainLoopStructure.IndVarStart),
583 RTy, SE, IsSignedPredicate);
584 const SCEV *End = NoopOrExtend(SE.getSCEV(MainLoopStructure.LoopExitAt), RTy,
585 SE, IsSignedPredicate);
595 const SCEV *One = SE.getOne(RTy);
600 GreatestSeen = SE.getMinusSCEV(End, One);
617 Smallest = SE.getAddExpr(End, One);
618 Greatest = SE.getAddExpr(Start, One);
622 auto Clamp = [&SE, Smallest, Greatest, IsSignedPredicate](const SCEV *S) {
624 ? SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S))
625 : SE.getUMaxExpr(Smallest, SE.getUMinExpr(Greatest, S));
635 SE.isKnownPredicate(PredLE, Range.getBegin(), Smallest);
640 SE.isKnownPredicate(PredLT, GreatestSeen, Range.getEnd());
651 InductiveRangeCheck::computeSafeIterationSpace(ScalarEvolution &SE,
688 const SCEV *A = NoopOrExtend(IndVar->getStart(), RCType, SE, IsLatchSigned);
690 NoopOrExtend(IndVar->getStepRecurrence(SE), RCType, SE, IsLatchSigned));
702 const SCEV *SIntMax = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
703 const SCEV *SIntMin = SE.getConstant(APInt::getSignedMinValue(BitWidth));
733 const SCEV *XMinusSIntMax = SE.getMinusSCEV(X, SIntMax);
734 return SE.getMinusSCEV(X, SE.getSMaxExpr(Y, XMinusSIntMax),
747 return SE.getMinusSCEV(X, SE.getSMinExpr(X, Y), SCEV::FlagNUW);
749 const SCEV *M = SE.getMinusSCEV(C, A);
750 const SCEV *Zero = SE.getZero(M->getType());
755 const SCEV *Zero = SE.getZero(X->getType());
756 const SCEV *One = SE.getOne(X->getType());
758 if (isKnownNonNegativeInLoop(X, L, SE))
760 else if (isKnownNegativeInLoop(X, L, SE))
764 const SCEV *NegOne = SE.getNegativeSCEV(One);
765 return SE.getAddExpr(SE.getSMaxExpr(SE.getSMinExpr(X, Zero), NegOne), One);
773 const SCEV *SIntMaxExt = SE.getSignExtendExpr(SIntMax, X->getType());
775 SCEVCheckNonNegative(SE.getMinusSCEV(SIntMaxExt, X));
779 const SCEV *SIntMinExt = SE.getSignExtendExpr(SIntMin, X->getType());
781 SCEVCheckNonNegative(SE.getMinusSCEV(X, SIntMinExt));
783 return SE.getMulExpr(OverflowCheck, UnderflowCheck);
795 const SCEV *EndWillNotOverflow = SE.getOne(RCType);
815 SE.getTruncateExpr(SCEVCheckWillNotOverflow(REnd), RCType);
816 REnd = SE.getTruncateExpr(REnd, RCType);
820 SE.getMulExpr(SCEVCheckNonNegative(REnd), EndWillNotOverflow);
821 const SCEV *Begin = SE.getMulExpr(ClampedSubtract(Zero, M), RuntimeChecks);
822 const SCEV *End = SE.getMulExpr(ClampedSubtract(REnd, M), RuntimeChecks);
828 IntersectSignedRange(ScalarEvolution &SE,
831 if (R2.isEmpty(SE, /* IsSigned */ true))
838 assert(!R1Value.isEmpty(SE, /* IsSigned */ true) &&
846 const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin());
847 const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd());
851 if (Ret.isEmpty(SE, /* IsSigned */ true))
857 IntersectUnsignedRange(ScalarEvolution &SE,
860 if (R2.isEmpty(SE, /* IsSigned */ false))
867 assert(!R1Value.isEmpty(SE, /* IsSigned */ false) &&
875 const SCEV *NewBegin = SE.getUMaxExpr(R1Value.getBegin(), R2.getBegin());
876 const SCEV *NewEnd = SE.getUMinExpr(R1Value.getEnd(), R2.getEnd());
880 if (Ret.isEmpty(SE, /* IsSigned */ false))
892 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
900 InductiveRangeCheckElimination IRCE(SE, &BPI, DT, LI, { getBFI });
906 CFGChanged |= simplifyLoop(L, &DT, &LI, &SE, nullptr, nullptr,
908 Changed |= formLCSSARecursively(*L, DT, &LI, &SE);
993 InductiveRangeCheck::extractRangeChecksFromBranch(TBI, L, SE, BPI,
1014 LoopStructure::parseLoopStructure(SE, *L, AllowUnsignedLatchCondition,
1025 cast<SCEVAddRecExpr>(SE.getMinusSCEV(SE.getSCEV(LS.IndVarBase), SE.getSCEV(LS.IndVarStep)));
1038 auto Result = IRC.computeSafeIterationSpace(SE, IndVar,
1041 auto MaybeSafeIterRange = IntersectRange(SE, SafeIterRange, *Result);
1043 assert(!MaybeSafeIterRange->isEmpty(SE, LS.IsSignedPredicate) &&
1055 calculateSubRanges(SE, *L, *SafeIterRange, LS);
1061 LoopConstrainer LC(*L, LI, LPMAddNewLoop, LS, SE, DT,