Lines Matching defs:Step
1229 // Get the limit of a recurrence such that incrementing by Step cannot cause
1232 static const SCEV *getSignedOverflowLimitForStep(const SCEV *Step,
1235 unsigned BitWidth = SE->getTypeSizeInBits(Step->getType());
1236 if (SE->isKnownPositive(Step)) {
1239 SE->getSignedRangeMax(Step));
1241 if (SE->isKnownNegative(Step)) {
1244 SE->getSignedRangeMin(Step));
1249 // Get the limit of a recurrence such that incrementing by Step cannot cause
1252 static const SCEV *getUnsignedOverflowLimitForStep(const SCEV *Step,
1255 unsigned BitWidth = SE->getTypeSizeInBits(Step->getType());
1259 SE->getUnsignedRangeMax(Step));
1277 // static const SCEV *getOverflowLimitForStep(const SCEV *Step,
1288 static const SCEV *getOverflowLimitForStep(const SCEV *Step,
1291 return getSignedOverflowLimitForStep(Step, Pred, SE);
1304 static const SCEV *getOverflowLimitForStep(const SCEV *Step,
1307 return getUnsignedOverflowLimitForStep(Step, Pred, SE);
1319 // allows normalizing a sign/zero extended AddRec as such: {sext/zext(Step +
1320 // Start),+,Step} => {(Step + sext/zext(Start),+,Step} As a result, the
1321 // expression "Step + sext/zext(PreIncAR)" is congruent with
1331 const SCEV *Step = AR->getStepRecurrence(*SE);
1338 // Create an AddExpr for "PreStart" after subtracting Step. Full SCEV
1340 // difference, by checking for Step in the operand list. Note, that
1344 if (*It == Step) {
1353 // `Step`:
1360 SE->getAddRecExpr(PreStart, Step, L, SCEV::FlagAnyWrap));
1376 (SE->*GetExtendExpr)(Step, WideTy, Depth));
1379 // If we know `AR` == {`PreStart`+`Step`,+,`Step`} is `WrapType` (FlagNSW
1380 // or FlagNUW) and that `PreStart` + `Step` is `WrapType` too, then
1381 // `PreAR` == {`PreStart`,+,`Step`} is also `WrapType`. Cache this fact.
1390 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1445 // In the current context, S is `Start`, X is `Step`, Ext is `ExtendOpTy` and T
1449 const SCEV *Step,
1469 ID.AddPointer(Step);
1515 // ConstantStart, x is an arbitrary \p Step, and n is the loop trip count.
1518 const SCEV *Step) {
1520 const uint32_t TZ = SE.getMinTrailingZeros(Step);
1621 const SCEV *Step = AR->getStepRecurrence(*this);
1630 Step = getZeroExtendExpr(Step, Ty, Depth + 1);
1631 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
1654 // Check whether Start+Step*MaxBECount has no unsigned overflow.
1655 const SCEV *ZMul = getMulExpr(CastedMaxBECount, Step,
1667 getZeroExtendExpr(Step, WideTy, Depth + 1),
1676 Step = getZeroExtendExpr(Step, Ty, Depth + 1);
1677 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
1684 getSignExtendExpr(Step, WideTy, Depth + 1),
1694 Step = getSignExtendExpr(Step, Ty, Depth + 1);
1695 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
1719 Step = getZeroExtendExpr(Step, Ty, Depth + 1);
1720 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
1725 if (isKnownNegative(Step)) {
1727 getSignedRangeMin(Step));
1737 Step = getSignExtendExpr(Step, Ty, Depth + 1);
1738 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
1743 // zext({C,+,Step}) --> (zext(D) + zext({C-D,+,Step}))<nuw><nsw>
1744 // if D + (C - D + Step * n) could be proven to not unsigned wrap
1745 // where D maximizes the number of trailing zeros of (C - D + Step * n)
1748 const APInt &D = extractConstantWithoutWrapping(*this, C, Step);
1752 getAddRecExpr(getConstant(C - D), Step, L, AR->getNoWrapFlags());
1760 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1764 Step = getZeroExtendExpr(Step, Ty, Depth + 1);
1765 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
1995 const SCEV *Step = AR->getStepRecurrence(*this);
2004 Step = getSignExtendExpr(Step, Ty, Depth + 1);
2005 return getAddRecExpr(Start, Step, L, SCEV::FlagNSW);
2029 // Check whether Start+Step*MaxBECount has no signed overflow.
2030 const SCEV *SMul = getMulExpr(CastedMaxBECount, Step,
2042 getSignExtendExpr(Step, WideTy, Depth + 1),
2051 Step = getSignExtendExpr(Step, Ty, Depth + 1);
2052 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
2059 getZeroExtendExpr(Step, WideTy, Depth + 1),
2065 // abs(Step) * MaxBECount > unsigned-max(AR->getType())
2076 Step = getZeroExtendExpr(Step, Ty, Depth + 1);
2077 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
2091 Step = getSignExtendExpr(Step, Ty, Depth + 1);
2092 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
2095 // sext({C,+,Step}) --> (sext(D) + sext({C-D,+,Step}))<nuw><nsw>
2096 // if D + (C - D + Step * n) could be proven to not signed wrap
2097 // where D maximizes the number of trailing zeros of (C - D + Step * n)
2100 const APInt &D = extractConstantWithoutWrapping(*this, C, Step);
2104 getAddRecExpr(getConstant(C - D), Step, L, AR->getNoWrapFlags());
2112 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2116 Step = getSignExtendExpr(Step, Ty, Depth + 1);
2117 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
2895 // NLI + LI + {Start,+,Step} --> NLI + {LI+Start,+,Step}
2969 // Step size has changed, so we cannot guarantee no self-wraparound.
3271 // NLI * LI * {Start,+,Step} --> NLI * {LI*Start,+,LI*Step}
3462 if (const SCEVConstant *Step =
3465 const APInt &StepInt = Step->getAPInt();
3470 getZeroExtendExpr(Step, ExtTy),
3484 getZeroExtendExpr(Step, ExtTy),
3490 getAddRecExpr(getConstant(StartInt - StartRem), Step,
3648 const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, const SCEV *Step,
3653 if (const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
3659 Operands.push_back(Step);
3674 assert(!Op->getType()->isPointerTy() && "Step must be integer");
5141 const SCEV *Step = AR->getStepRecurrence(*this);
5172 getSignedOverflowLimitForStep(Step, &Pred, this);
5194 const SCEV *Step = AR->getStepRecurrence(*this);
5224 if (isKnownPositive(Step)) {
5226 getUnsignedRangeMax(Step));
5430 // 8 * ((sext i32 (trunc i64 %X to i32) to i64) + %Step)
5438 // BEValue = ((sext i32 (trunc i64 %X to i32) to i64) + %Step)
5441 // NewAddRec = {%Start,+,%Step}
5443 // P1(WrapPred): AR: {trunc(%Start),+,(trunc %Step)}<nsw> Flags: <nssw>
5445 // P3(EqualPred): %Step == (sext i32 (trunc i64 %Step to i32) to i64)
5650 // The Step is always Signed (because the overflow checks are either
6423 // Match a simple recurrence of the form: <start, ShiftOp, Step>, and then
6427 // the one used by AddRec (and thus most of this file). Step is allowed to
6443 Value *Start, *Step;
6444 if (!matchSimpleRecurrence(P, BO, Start, Step))
6478 auto KnownStep = computeKnownBits(Step, DL, 0, &AC, nullptr, &DT);
6954 // Given a StartRange, Step and MaxBECount for an expression compute a range of
6956 // from StartRange and then is changed by Step up to MaxBECount times. Signed
6957 // argument defines if we treat Step as signed or unsigned.
6958 static ConstantRange getRangeForAffineARHelper(APInt Step,
6962 unsigned BitWidth = Step.getBitWidth();
6965 // If either Step or MaxBECount is 0, then the expression won't change, and we
6967 if (Step == 0 || MaxBECount == 0)
6976 // If Step is signed and negative, then we use its absolute value, but we also
6978 bool Descending = Signed && Step.isNegative();
6985 Step = Step.abs();
6989 if (APInt::getMaxValue(StartRange.getBitWidth()).udiv(Step).ult(MaxBECount))
6994 APInt Offset = Step * MaxBECount;
7022 const SCEV *Step,
7025 getTypeSizeInBits(Step->getType()) &&
7031 ConstantRange StepSRange = getSignedRange(Step);
7033 // If Step can be both positive and negative, we need to find ranges for the
7043 getUnsignedRangeMax(Step), getUnsignedRange(Start), MaxBECount,
7057 const SCEV *Step = AddRec->getStepRecurrence(*this);
7059 if (!isa<SCEVConstant>(Step))
7071 const SCEV *StepAbs = getUMinExpr(Step, getNegativeSCEV(Step));
7109 if (isKnownPositive(Step) &&
7112 if (isKnownNegative(Step) &&
7119 const SCEV *Step,
7126 getTypeSizeInBits(Step->getType()) == BitWidth &&
7145 // {Start+Step,+,Step} too.
7205 SelectPattern StepPattern(*this, BitWidth, Step);
10479 // Start + Step*N = 0 (mod 2^BW)
10483 // Step*N = -Start (mod 2^BW)
10485 // where BW is the common bit width of Start and Step.
10489 const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop());
10490 const SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step);
10492 if (!isLoopInvariant(Step, L))
10497 const SCEV *StepWLG = applyLoopGuards(Step, Guards);
10500 // N = -Start/Step (as unsigned)
10502 // N = Start/-Step
10503 // First compute the unsigned distance from zero in the direction of Step.
10552 getUDivExpr(Distance, CountDown ? getNegativeSCEV(Step) : Step);
11043 const SCEV *Step = LHS->getStepRecurrence(*this);
11045 if (isKnownNonNegative(Step))
11048 if (isKnownNonPositive(Step))
11190 const SCEV *Step = AR->getStepRecurrence(*this);
11191 auto *One = getOne(Step->getType());
11193 if (Step != One && Step != MinusOne)
11214 if (Step == MinusOne)
12770 getConstant(StrideForMaxBECount) /* Step */);
12831 // defined by AR (e.g. {Start,+,Step}) such that V >u RHS, and
12849 const SCEV *Step = AR->getStepRecurrence(*this);
12853 getZeroExtendExpr(Step, Ty, 0), L, AR->getNoWrapFlags());
13437 // (this + Step) is {A+B,+,B+C,+...,+,N}.
14639 const SCEV *Step = AR->getStepRecurrence(SE);
14643 SE.getSignExtendExpr(Step, Ty), L,
14655 const SCEV *Step = AR->getStepRecurrence(SE);
14659 SE.getSignExtendExpr(Step, Ty), L,
14824 if (const auto *Step = dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE)))
14825 if (Step->getValue()->getValue().isNonNegative())