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