Lines Matching defs:AddRec
214 cl::desc("Max coefficients in AddRec during evolving"),
1222 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
1224 for (const SCEV *Op : AddRec->operands())
1226 return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap);
1334 // allows normalizing a sign/zero extended AddRec as such: {sext/zext(Step +
1414 // Get the normalized zero or sign extended expression for this AddRec's Start.
1527 // Finds an integer D for an affine AddRec expression {C,+,x} such that the top
1685 // Cache knowledge of AR NUW, which is propagated to this AddRec.
1702 // Cache knowledge of AR NW, which is propagated to this AddRec.
1745 // AddRec. Negative step causes unsigned wrap, but it
2060 // Cache knowledge of AR NSW, which is propagated to this AddRec.
2876 const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
2877 const Loop *AddRecLoop = AddRec->getLoop();
2890 LIOps.push_back(AddRec);
2895 LIOps.push_back(AddRec->getStart());
2897 SmallVector<const SCEV *, 4> AddRecOps(AddRec->operands());
2921 Flags = AddRec->getNoWrapFlags(setFlags(Flags, SCEV::FlagNW));
2927 // Otherwise, add the folded AddRec by the non-invariant parts.
2929 if (Ops[i] == AddRec) {
2937 // there are multiple AddRec's with the same loop induction variable being
2946 AddRec->getLoop()->getHeader()) &&
2950 SmallVector<const SCEV *, 4> AddRecOps(AddRec->operands());
3178 } else if (const auto *AddRec = dyn_cast<SCEVAddRecExpr>(Ops[1])) {
3181 for (const SCEV *AddRecOp : AddRec->operands())
3184 // Let M be the minimum representable signed value. AddRec with nsw
3190 if (hasFlags(AddRec->getNoWrapFlags(), SCEV::FlagNSW)) {
3192 APInt::getSignedMinValue(getTypeSizeInBits(AddRec->getType()));
3193 if (getSignedRangeMin(AddRec) != MinInt)
3196 return getAddRecExpr(Operands, AddRec->getLoop(),
3197 AddRec->getNoWrapFlags(FlagsMask));
3239 const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
3241 if (isAvailableAtLoopEntry(Ops[i], AddRec->getLoop())) {
3251 NewOps.reserve(AddRec->getNumOperands());
3259 AddRec->getNoWrapFlags(ComputeFlags({Scale, AddRec}));
3261 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
3262 NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i),
3269 if (!NSWRegion.contains(getSignedRange(AddRec->getOperand(i))))
3274 const SCEV *NewRec = getAddRecExpr(NewOps, AddRec->getLoop(), Flags);
3279 // Otherwise, multiply the folded AddRec by the non-invariant parts.
3281 if (Ops[i] == AddRec) {
3289 // if there are multiple AddRec's with the same loop induction variable
3308 if (!OtherAddRec || OtherAddRec->getLoop() != AddRec->getLoop())
3313 if (AddRec->getNumOperands() + OtherAddRec->getNumOperands() - 1 >
3314 MaxAddRecSize || hasHugeExpression({AddRec, OtherAddRec}))
3318 Type *Ty = AddRec->getType();
3321 for (int x = 0, xe = AddRec->getNumOperands() +
3326 for (int z = std::max(y-x, y-(int)AddRec->getNumOperands()+1),
3336 const SCEV *Term1 = AddRec->getOperand(y-z);
3347 const SCEV *NewAddRec = getAddRecExpr(AddRecOps, AddRec->getLoop(),
3353 AddRec = dyn_cast<SCEVAddRecExpr>(NewAddRec);
3354 if (!AddRec)
4628 if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(P)) {
4629 // The base of an AddRec is the first operand.
4630 SmallVector<const SCEV *> Ops{AddRec->operands()};
4633 // (for example, if pointer operand of the AddRec is a SCEVUnknown).
4634 return getAddRecExpr(Ops, AddRec->getLoop(), SCEV::FlagAnyWrap);
4829 if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
4830 V = AddRec->getStart();
4860 /// Takes SCEV S and Loop L. For each AddRec sub-expression, use its start
4862 /// if IgnoreOtherLoops is true then use AddRec itself
4905 /// Takes SCEV S and Loop L. For each AddRec sub-expression, use its post
4907 /// use AddRec itself.
5115 // This function can be expensive, only try to prove NSW once per AddRec.
5168 // This function can be expensive, only try to prove NUW once per AddRec.
5456 // return an AddRec expression under some predicate.
5525 // can return an AddRec expression under the following predicates:
5674 // Analysis was done before and failed to create an AddRec:
5677 // Analysis was done before and succeeded to create an AddRec under
5679 assert(isa<SCEVAddRecExpr>(Rewrite.first) && "Expected an AddRec");
5724 /// This function tries to find an AddRec expression for the simplest (yet most
5727 /// technique for finding the AddRec expression.
5811 // First, try to find AddRec expression without creating a fictituos symbolic
6430 void ScalarEvolution::setNoWrapFlags(SCEVAddRecExpr *AddRec,
6432 if (AddRec->getNoWrapFlags(Flags) != Flags) {
6433 AddRec->setNoWrapFlags(Flags);
6434 UnsignedRanges.erase(AddRec);
6435 SignedRanges.erase(AddRec);
6436 ConstantMultipleCache.erase(AddRec);
6451 // the one used by AddRec (and thus most of this file). Step is allowed to
6452 // be arbitrarily loop varying here, where AddRec allows only loop invariant
6747 const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(S);
6750 if (AddRec->hasNoUnsignedWrap()) {
6751 APInt UnsignedMinValue = getUnsignedRangeMin(AddRec->getStart());
6762 if (AddRec->hasNoSignedWrap()) {
6765 for (unsigned i = 1, e = AddRec->getNumOperands(); i != e; ++i) {
6766 if (!isKnownNonNegative(AddRec->getOperand(i)))
6768 if (!isKnownNonPositive(AddRec->getOperand(i)))
6773 ConstantRange::getNonEmpty(getSignedRangeMin(AddRec->getStart()),
6779 getSignedRangeMax(AddRec->getStart()) +
6785 if (AddRec->isAffine()) {
6787 getConstantMaxBackedgeTakenCount(AddRec->getLoop());
6791 // Adjust MaxBECount to the same bitwidth as AddRec. We can truncate if
6792 // MaxBECount's active bits are all <= AddRec's bit width.
6801 AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount);
6806 AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount);
6815 getSymbolicMaxBackedgeTakenCount(AddRec->getLoop());
6818 AddRec->hasNoSelfWrap()) {
6820 AddRec, SymbolicMaxBECount, BitWidth, SignHint);
6827 return setRange(AddRec, SignHint, std::move(ConservativeResult));
7073 const SCEVAddRecExpr *AddRec, const SCEV *MaxBECount, unsigned BitWidth,
7075 assert(AddRec->isAffine() && "Non-affine AddRecs are not suppored!\n");
7076 assert(AddRec->hasNoSelfWrap() &&
7079 const SCEV *Step = AddRec->getStepRecurrence(*this);
7089 getTypeSizeInBits(AddRec->getType()))
7091 MaxBECount = getNoopOrZeroExtend(MaxBECount, AddRec->getType());
7092 const SCEV *RangeWidth = getMinusOne(AddRec->getType());
7103 const SCEV *End = AddRec->evaluateAtIteration(MaxBECount, *this);
7117 const SCEV *Start = applyLoopGuards(AddRec->getStart(), AddRec->getLoop());
7277 if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(S))
7278 return &*AddRec->getLoop()->getHeader()->begin();
8060 // more likely to preserve NSW and allow later AddRec optimisations.
8575 } else if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
8576 if (L->contains(AddRec->getLoop()))
9220 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
9221 if (AddRec->getLoop() == L) {
9226 const SCEV *Ret = AddRec->getNumIterationsInRange(CompRange, *this);
9393 EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C,
9396 const SCEV *Val = AddRec->evaluateAtIteration(InVal, SE);
9951 auto *AddRec = cast<SCEVAddRecExpr>(S);
9952 return getAddRecExpr(NewOps, AddRec->getLoop(), AddRec->getNoWrapFlags());
9985 const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(V);
9989 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
9990 const SCEV *OpAtScope = getSCEVAtScope(AddRec->getOperand(i), L);
9991 if (OpAtScope == AddRec->getOperand(i))
9997 NewOps.reserve(AddRec->getNumOperands());
9998 append_range(NewOps, AddRec->operands().take_front(i));
10001 NewOps.push_back(getSCEVAtScope(AddRec->getOperand(i), L));
10004 NewOps, AddRec->getLoop(), AddRec->getNoWrapFlags(SCEV::FlagNW));
10005 AddRec = dyn_cast<SCEVAddRecExpr>(FoldedRec);
10009 if (!AddRec)
10016 if (!AddRec->getLoop()->contains(L)) {
10017 // To evaluate this recurrence, we need to know how many times the AddRec
10019 const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
10021 return AddRec;
10023 // Then, evaluate the AddRec.
10024 return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
10027 return AddRec;
10260 GetQuadraticEquation(const SCEVAddRecExpr *AddRec) {
10261 assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!");
10262 const SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
10263 const SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
10264 const SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
10266 << *AddRec << '\n');
10362 SolveQuadraticAddRecExact(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) {
10365 auto T = GetQuadraticEquation(AddRec);
10377 ConstantInt *V = EvaluateConstantChrecAtConstant(AddRec, CX, SE);
10395 SolveQuadraticAddRecRange(const SCEVAddRecExpr *AddRec,
10397 assert(AddRec->getOperand(0)->isZero() &&
10400 << Range << ", addrec " << *AddRec << '\n');
10403 assert(Range.contains(APInt(SE.getTypeSizeInBits(AddRec->getType()), 0)) &&
10408 auto T = GetQuadraticEquation(AddRec);
10441 ConstantInt *V0 = EvaluateConstantChrecAtConstant(AddRec, C0, SE);
10446 ConstantInt *V1 = EvaluateConstantChrecAtConstant(AddRec, C1, SE);
10541 const SCEVAddRecExpr *AddRec =
10544 if (!AddRec && AllowPredicates)
10545 // Try to make this an AddRec using runtime tests, in the first X
10548 AddRec = convertSCEVToAddRecWithPredicates(V, L, Predicates);
10550 if (!AddRec || AddRec->getLoop() != L)
10553 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of
10555 if (AddRec->isQuadratic() && AddRec->getType()->isIntegerTy()) {
10559 if (auto S = SolveQuadraticAddRecExact(AddRec, *this)) {
10567 if (!AddRec->isAffine())
10582 const SCEV *Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
10583 const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop());
10635 if (ControlsOnlyExit && AddRec->hasNoSelfWrap() &&
10636 loopHasNoAbnormalExits(AddRec->getLoop())) {
12374 // AddRec. It means that there is a loop which has both AddRec and Unknown
12375 // PHIs, for it we can compare incoming values of AddRec from above the loop
12382 assert(Predecessor && "Loop with AddRec with no predecessor?");
12387 assert(Latch && "Loop with AddRec with no latch?");
12998 // Try to make this an AddRec using runtime tests, in the first X
13389 // Try to make this an AddRec using runtime tests, in the first X
13551 assert(getNumOperands() > 1 && "AddRec with zero step?");
13554 // AddRec because SCEV does not have a fixed point where it stops
13566 // the returned value will be an AddRec.
14454 "AddRec references invalid loop");
14862 // as an AddRec, possibly under a predicate (PHISCEVPred). If it is possible
14863 // to add this predicate as a runtime overflow check, we return the AddRec.
14865 // couldn't create an AddRec for it, or couldn't add the predicate), we just
14905 auto *AddRec = dyn_cast<SCEVAddRecExpr>(S);
14907 if (!AddRec)
14914 return AddRec;
15560 // Do not apply information for constants or if RHS contains an AddRec.
15853 /// replacement is loop invariant in the loop of the AddRec.