Lines Matching defs:AddRec
212 cl::desc("Max coefficients in AddRec during evolving"),
1207 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
1209 for (const SCEV *Op : AddRec->operands())
1211 return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap);
1319 // allows normalizing a sign/zero extended AddRec as such: {sext/zext(Step +
1399 // Get the normalized zero or sign extended expression for this AddRec's Start.
1512 // Finds an integer D for an affine AddRec expression {C,+,x} such that the top
1671 // Cache knowledge of AR NUW, which is propagated to this AddRec.
1688 // Cache knowledge of AR NW, which is propagated to this AddRec.
1731 // AddRec. Negative step causes unsigned wrap, but it
2046 // Cache knowledge of AR NSW, which is propagated to this AddRec.
2877 const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
2878 const Loop *AddRecLoop = AddRec->getLoop();
2891 LIOps.push_back(AddRec);
2896 LIOps.push_back(AddRec->getStart());
2898 SmallVector<const SCEV *, 4> AddRecOps(AddRec->operands());
2922 Flags = AddRec->getNoWrapFlags(setFlags(Flags, SCEV::FlagNW));
2928 // Otherwise, add the folded AddRec by the non-invariant parts.
2930 if (Ops[i] == AddRec) {
2938 // there are multiple AddRec's with the same loop induction variable being
2947 AddRec->getLoop()->getHeader()) &&
2951 SmallVector<const SCEV *, 4> AddRecOps(AddRec->operands());
3201 } else if (const auto *AddRec = dyn_cast<SCEVAddRecExpr>(Ops[1])) {
3204 for (const SCEV *AddRecOp : AddRec->operands())
3207 // Let M be the minimum representable signed value. AddRec with nsw
3213 if (hasFlags(AddRec->getNoWrapFlags(), SCEV::FlagNSW)) {
3215 APInt::getSignedMinValue(getTypeSizeInBits(AddRec->getType()));
3216 if (getSignedRangeMin(AddRec) != MinInt)
3219 return getAddRecExpr(Operands, AddRec->getLoop(),
3220 AddRec->getNoWrapFlags(FlagsMask));
3261 const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
3263 if (isAvailableAtLoopEntry(Ops[i], AddRec->getLoop())) {
3273 NewOps.reserve(AddRec->getNumOperands());
3281 AddRec->getNoWrapFlags(ComputeFlags({Scale, AddRec}));
3283 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
3284 NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i),
3291 if (!NSWRegion.contains(getSignedRange(AddRec->getOperand(i))))
3296 const SCEV *NewRec = getAddRecExpr(NewOps, AddRec->getLoop(), Flags);
3301 // Otherwise, multiply the folded AddRec by the non-invariant parts.
3303 if (Ops[i] == AddRec) {
3311 // if there are multiple AddRec's with the same loop induction variable
3330 if (!OtherAddRec || OtherAddRec->getLoop() != AddRec->getLoop())
3335 if (AddRec->getNumOperands() + OtherAddRec->getNumOperands() - 1 >
3336 MaxAddRecSize || hasHugeExpression({AddRec, OtherAddRec}))
3340 Type *Ty = AddRec->getType();
3343 for (int x = 0, xe = AddRec->getNumOperands() +
3348 for (int z = std::max(y-x, y-(int)AddRec->getNumOperands()+1),
3358 const SCEV *Term1 = AddRec->getOperand(y-z);
3369 const SCEV *NewAddRec = getAddRecExpr(AddRecOps, AddRec->getLoop(),
3375 AddRec = dyn_cast<SCEVAddRecExpr>(NewAddRec);
3376 if (!AddRec)
4650 if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(P)) {
4651 // The base of an AddRec is the first operand.
4652 SmallVector<const SCEV *> Ops{AddRec->operands()};
4655 // (for example, if pointer operand of the AddRec is a SCEVUnknown).
4656 return getAddRecExpr(Ops, AddRec->getLoop(), SCEV::FlagAnyWrap);
4851 if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
4852 V = AddRec->getStart();
4882 /// Takes SCEV S and Loop L. For each AddRec sub-expression, use its start
4884 /// if IgnoreOtherLoops is true then use AddRec itself
4927 /// Takes SCEV S and Loop L. For each AddRec sub-expression, use its post
4929 /// use AddRec itself.
5137 // This function can be expensive, only try to prove NSW once per AddRec.
5190 // This function can be expensive, only try to prove NUW once per AddRec.
5478 // return an AddRec expression under some predicate.
5547 // can return an AddRec expression under the following predicates:
5696 // Analysis was done before and failed to create an AddRec:
5699 // Analysis was done before and succeeded to create an AddRec under
5701 assert(isa<SCEVAddRecExpr>(Rewrite.first) && "Expected an AddRec");
5745 /// This function tries to find an AddRec expression for the simplest (yet most
5748 /// technique for finding the AddRec expression.
5832 // First, try to find AddRec expression without creating a fictituos symbolic
6406 void ScalarEvolution::setNoWrapFlags(SCEVAddRecExpr *AddRec,
6408 if (AddRec->getNoWrapFlags(Flags) != Flags) {
6409 AddRec->setNoWrapFlags(Flags);
6410 UnsignedRanges.erase(AddRec);
6411 SignedRanges.erase(AddRec);
6412 ConstantMultipleCache.erase(AddRec);
6427 // the one used by AddRec (and thus most of this file). Step is allowed to
6428 // be arbitrarily loop varying here, where AddRec allows only loop invariant
6723 const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(S);
6726 if (AddRec->hasNoUnsignedWrap()) {
6727 APInt UnsignedMinValue = getUnsignedRangeMin(AddRec->getStart());
6738 if (AddRec->hasNoSignedWrap()) {
6741 for (unsigned i = 1, e = AddRec->getNumOperands(); i != e; ++i) {
6742 if (!isKnownNonNegative(AddRec->getOperand(i)))
6744 if (!isKnownNonPositive(AddRec->getOperand(i)))
6749 ConstantRange::getNonEmpty(getSignedRangeMin(AddRec->getStart()),
6755 getSignedRangeMax(AddRec->getStart()) +
6761 if (AddRec->isAffine()) {
6763 getConstantMaxBackedgeTakenCount(AddRec->getLoop());
6767 // Adjust MaxBECount to the same bitwidth as AddRec. We can truncate if
6768 // MaxBECount's active bits are all <= AddRec's bit width.
6777 AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount);
6782 AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount);
6791 getSymbolicMaxBackedgeTakenCount(AddRec->getLoop());
6794 AddRec->hasNoSelfWrap()) {
6796 AddRec, SymbolicMaxBECount, BitWidth, SignHint);
6803 return setRange(AddRec, SignHint, std::move(ConservativeResult));
7051 const SCEVAddRecExpr *AddRec, const SCEV *MaxBECount, unsigned BitWidth,
7053 assert(AddRec->isAffine() && "Non-affine AddRecs are not suppored!\n");
7054 assert(AddRec->hasNoSelfWrap() &&
7057 const SCEV *Step = AddRec->getStepRecurrence(*this);
7067 getTypeSizeInBits(AddRec->getType()))
7069 MaxBECount = getNoopOrZeroExtend(MaxBECount, AddRec->getType());
7070 const SCEV *RangeWidth = getMinusOne(AddRec->getType());
7081 const SCEV *End = AddRec->evaluateAtIteration(MaxBECount, *this);
7095 const SCEV *Start = applyLoopGuards(AddRec->getStart(), AddRec->getLoop());
7255 if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(S))
7256 return &*AddRec->getLoop()->getHeader()->begin();
8023 // more likely to preserve NSW and allow later AddRec optimisations.
8514 } else if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
8515 if (L->contains(AddRec->getLoop()))
9162 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
9163 if (AddRec->getLoop() == L) {
9168 const SCEV *Ret = AddRec->getNumIterationsInRange(CompRange, *this);
9316 EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C,
9319 const SCEV *Val = AddRec->evaluateAtIteration(InVal, SE);
9874 auto *AddRec = cast<SCEVAddRecExpr>(S);
9875 return getAddRecExpr(NewOps, AddRec->getLoop(), AddRec->getNoWrapFlags());
9908 const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(V);
9912 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
9913 const SCEV *OpAtScope = getSCEVAtScope(AddRec->getOperand(i), L);
9914 if (OpAtScope == AddRec->getOperand(i))
9920 NewOps.reserve(AddRec->getNumOperands());
9921 append_range(NewOps, AddRec->operands().take_front(i));
9924 NewOps.push_back(getSCEVAtScope(AddRec->getOperand(i), L));
9927 NewOps, AddRec->getLoop(), AddRec->getNoWrapFlags(SCEV::FlagNW));
9928 AddRec = dyn_cast<SCEVAddRecExpr>(FoldedRec);
9932 if (!AddRec)
9939 if (!AddRec->getLoop()->contains(L)) {
9940 // To evaluate this recurrence, we need to know how many times the AddRec
9942 const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
9944 return AddRec;
9946 // Then, evaluate the AddRec.
9947 return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
9950 return AddRec;
10166 GetQuadraticEquation(const SCEVAddRecExpr *AddRec) {
10167 assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!");
10168 const SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
10169 const SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
10170 const SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
10172 << *AddRec << '\n');
10268 SolveQuadraticAddRecExact(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) {
10271 auto T = GetQuadraticEquation(AddRec);
10283 ConstantInt *V = EvaluateConstantChrecAtConstant(AddRec, CX, SE);
10301 SolveQuadraticAddRecRange(const SCEVAddRecExpr *AddRec,
10303 assert(AddRec->getOperand(0)->isZero() &&
10306 << Range << ", addrec " << *AddRec << '\n');
10309 assert(Range.contains(APInt(SE.getTypeSizeInBits(AddRec->getType()), 0)) &&
10314 auto T = GetQuadraticEquation(AddRec);
10347 ConstantInt *V0 = EvaluateConstantChrecAtConstant(AddRec, C0, SE);
10352 ConstantInt *V1 = EvaluateConstantChrecAtConstant(AddRec, C1, SE);
10447 const SCEVAddRecExpr *AddRec =
10450 if (!AddRec && AllowPredicates)
10451 // Try to make this an AddRec using runtime tests, in the first X
10454 AddRec = convertSCEVToAddRecWithPredicates(V, L, Predicates);
10456 if (!AddRec || AddRec->getLoop() != L)
10459 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of
10461 if (AddRec->isQuadratic() && AddRec->getType()->isIntegerTy()) {
10465 if (auto S = SolveQuadraticAddRecExact(AddRec, *this)) {
10473 if (!AddRec->isAffine())
10488 const SCEV *Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
10489 const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop());
10542 if (ControlsOnlyExit && AddRec->hasNoSelfWrap() &&
10543 loopHasNoAbnormalExits(AddRec->getLoop())) {
12201 // AddRec. It means that there is a loop which has both AddRec and Unknown
12202 // PHIs, for it we can compare incoming values of AddRec from above the loop
12209 assert(Predecessor && "Loop with AddRec with no predecessor?");
12214 assert(Latch && "Loop with AddRec with no latch?");
12862 // Try to make this an AddRec using runtime tests, in the first X
13266 // Try to make this an AddRec using runtime tests, in the first X
13428 assert(getNumOperands() > 1 && "AddRec with zero step?");
13431 // AddRec because SCEV does not have a fixed point where it stops
13443 // the returned value will be an AddRec.
14280 "AddRec references invalid loop");
14687 // as an AddRec, possibly under a predicate (PHISCEVPred). If it is possible
14688 // to add this predicate as a runtime overflow check, we return the AddRec.
14690 // couldn't create an AddRec for it, or couldn't add the predicate), we just
14730 auto *AddRec = dyn_cast<SCEVAddRecExpr>(S);
14732 if (!AddRec)
14740 return AddRec;
15256 // Do not apply information for constants or if RHS contains an AddRec.
15534 /// replacement is loop invariant in the loop of the AddRec.