Lines Matching defs:AddRec
216 cl::desc("Max coefficients in AddRec during evolving"),
1332 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
1334 for (const SCEV *Op : AddRec->operands())
1336 return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap);
1439 // allows normalizing a sign/zero extended AddRec as such: {sext/zext(Step +
1516 // Get the normalized zero or sign extended expression for this AddRec's Start.
1629 // Finds an integer D for an affine AddRec expression {C,+,x} such that the top
1751 // Cache knowledge of AR NUW, which is propagated to this AddRec.
1769 // Cache knowledge of AR NW, which is propagated to this AddRec.
1802 // AddRec.
1817 // AddRec. Negative step causes unsigned wrap, but it
2095 // Cache knowledge of AR NSW, which is propagated to this AddRec.
2154 // Cache knowledge of AR NSW, then propagate NSW to the wide AddRec.
2704 const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
2705 const Loop *AddRecLoop = AddRec->getLoop();
2716 LIOps.push_back(AddRec->getStart());
2718 SmallVector<const SCEV *, 4> AddRecOps(AddRec->op_begin(),
2719 AddRec->op_end());
2728 Flags = AddRec->getNoWrapFlags(setFlags(Flags, SCEV::FlagNW));
2734 // Otherwise, add the folded AddRec by the non-invariant parts.
2736 if (Ops[i] == AddRec) {
2744 // there are multiple AddRec's with the same loop induction variable being
2753 AddRec->getLoop()->getHeader()) &&
2757 SmallVector<const SCEV *, 4> AddRecOps(AddRec->op_begin(),
2758 AddRec->op_end());
2990 } else if (const auto *AddRec = dyn_cast<SCEVAddRecExpr>(Ops[1])) {
2993 for (const SCEV *AddRecOp : AddRec->operands())
2997 return getAddRecExpr(Operands, AddRec->getLoop(),
2998 AddRec->getNoWrapFlags(SCEV::FlagNW));
3042 const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
3043 const Loop *AddRecLoop = AddRec->getLoop();
3055 NewOps.reserve(AddRec->getNumOperands());
3057 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
3058 NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i),
3066 Flags = AddRec->getNoWrapFlags(clearFlags(Flags, SCEV::FlagNW));
3072 // Otherwise, multiply the folded AddRec by the non-invariant parts.
3074 if (Ops[i] == AddRec) {
3082 // if there are multiple AddRec's with the same loop induction variable
3106 if (AddRec->getNumOperands() + OtherAddRec->getNumOperands() - 1 >
3107 MaxAddRecSize || isHugeExpression(AddRec) ||
3112 Type *Ty = AddRec->getType();
3115 for (int x = 0, xe = AddRec->getNumOperands() +
3120 for (int z = std::max(y-x, y-(int)AddRec->getNumOperands()+1),
3130 const SCEV *Term1 = AddRec->getOperand(y-z);
3147 AddRec = dyn_cast<SCEVAddRecExpr>(NewAddRec);
3148 if (!AddRec)
4239 /// Takes SCEV S and Loop L. For each AddRec sub-expression, use its start
4241 /// if IgnoreOtherLoops is true then use AddRec itself
4284 /// Takes SCEV S and Loop L. For each AddRec sub-expression, use its post
4286 /// use AddRec itself.
4701 // return an AddRec expression under some predicate.
4770 // can return an AddRec expression under the following predicates:
4919 // Analysis was done before and failed to create an AddRec:
4922 // Analysis was done before and succeeded to create an AddRec under
4924 assert(isa<SCEVAddRecExpr>(Rewrite.first) && "Expected an AddRec");
4968 /// This function tries to find an AddRec expression for the simplest (yet most
4971 /// technique for finding the AddRec expression.
5047 // First, try to find AddRec expression without creating a fictituos symbolic
5667 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
5670 if (AddRec->hasNoUnsignedWrap()) {
5671 APInt UnsignedMinValue = getUnsignedRangeMin(AddRec->getStart());
5682 if (AddRec->hasNoSignedWrap()) {
5685 for (unsigned i = 1, e = AddRec->getNumOperands(); i != e; ++i) {
5686 if (!isKnownNonNegative(AddRec->getOperand(i)))
5688 if (!isKnownNonPositive(AddRec->getOperand(i)))
5693 ConstantRange::getNonEmpty(getSignedRangeMin(AddRec->getStart()),
5700 getSignedRangeMax(AddRec->getStart()) + 1),
5705 if (AddRec->isAffine()) {
5706 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(AddRec->getLoop());
5710 AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount,
5717 AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount,
5725 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6059 if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
6065 if (!isLoopInvariant(OtherOp, AddRec->getLoop())) {
6072 isGuaranteedToExecuteForEveryIteration(I, AddRec->getLoop()))
6498 // more likely to preserve NSW and allow later AddRec optimisations.
7461 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
7462 if (AddRec->getLoop() == L) {
7467 const SCEV *Ret = AddRec->getNumIterationsInRange(CompRange, *this);
7541 EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C,
7544 const SCEV *Val = AddRec->evaluateAtIteration(InVal, SE);
7597 // particular, only affine AddRec's like {C1,+,C2}.
8367 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
8371 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
8372 const SCEV *OpAtScope = getSCEVAtScope(AddRec->getOperand(i), L);
8373 if (OpAtScope == AddRec->getOperand(i))
8378 SmallVector<const SCEV *, 8> NewOps(AddRec->op_begin(),
8379 AddRec->op_begin()+i);
8382 NewOps.push_back(getSCEVAtScope(AddRec->getOperand(i), L));
8385 getAddRecExpr(NewOps, AddRec->getLoop(),
8386 AddRec->getNoWrapFlags(SCEV::FlagNW));
8387 AddRec = dyn_cast<SCEVAddRecExpr>(FoldedRec);
8391 if (!AddRec)
8398 if (!AddRec->getLoop()->contains(L)) {
8399 // To evaluate this recurrence, we need to know how many times the AddRec
8401 const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
8402 if (BackedgeTakenCount == getCouldNotCompute()) return AddRec;
8404 // Then, evaluate the AddRec.
8405 return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
8408 return AddRec;
8504 GetQuadraticEquation(const SCEVAddRecExpr *AddRec) {
8505 assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!");
8506 const SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
8507 const SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
8508 const SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
8510 << *AddRec << '\n');
8604 SolveQuadraticAddRecExact(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) {
8607 auto T = GetQuadraticEquation(AddRec);
8618 ConstantInt *V = EvaluateConstantChrecAtConstant(AddRec, CX, SE);
8636 SolveQuadraticAddRecRange(const SCEVAddRecExpr *AddRec,
8638 assert(AddRec->getOperand(0)->isZero() &&
8641 << Range << ", addrec " << *AddRec << '\n');
8644 assert(Range.contains(APInt(SE.getTypeSizeInBits(AddRec->getType()), 0)) &&
8649 auto T = GetQuadraticEquation(AddRec);
8681 ConstantInt *V0 = EvaluateConstantChrecAtConstant(AddRec, C0, SE);
8686 ConstantInt *V1 = EvaluateConstantChrecAtConstant(AddRec, C1, SE);
8780 const SCEVAddRecExpr *AddRec =
8783 if (!AddRec && AllowPredicates)
8784 // Try to make this an AddRec using runtime tests, in the first X
8787 AddRec = convertSCEVToAddRecWithPredicates(V, L, Predicates);
8789 if (!AddRec || AddRec->getLoop() != L)
8792 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of
8794 if (AddRec->isQuadratic() && AddRec->getType()->isIntegerTy()) {
8798 if (auto S = SolveQuadraticAddRecExact(AddRec, *this)) {
8806 if (!AddRec->isAffine())
8821 const SCEV *Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
8822 const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop());
8826 // TODO: Handle a nonconstant Step given AddRec<NUW>. If the
8827 // AddRec is NUW, then (in an unsigned sense) it cannot be counting up to wrap
8872 if (ControlsExit && AddRec->hasNoSelfWrap() &&
8873 loopHasNoAbnormalExits(AddRec->getLoop())) {
10142 // AddRec. It means that there is a loop which has both AddRec and Unknown
10143 // PHIs, for it we can compare incoming values of AddRec from above the loop
10150 assert(Predecessor && "Loop with AddRec with no predecessor?");
10155 assert(Latch && "Loop with AddRec with no latch?");
10653 // Try to make this an AddRec using runtime tests, in the first X
10795 // Try to make this an AddRec using runtime tests, in the first X
10931 assert(getNumOperands() > 1 && "AddRec with zero step?");
10934 // AddRec because SCEV does not have a fixed point where it stops
10946 // the returned value will be an AddRec.
11034 // that contains the AddRec {0, +, 1}_loop. %p * %q are likely to be array size
11086 /// 1) The strides of AddRec expressions.
11087 /// 2) Unknowns that are multiplied with AddRec expressions.
11348 /// the delinearization input is the following AddRec SCEV:
11350 /// AddRec: {{{%A,+,(8 * %m * %o)}<%for.i>,+,(8 * %o)}<%for.j>,+,8}<%for.k>
12254 // as an AddRec, possibly under a predicate (PHISCEVPred). If it is possible
12255 // to add this predicate as a runtime overflow check, we return the AddRec.
12257 // couldn't create an AddRec for it, or couldn't add the predicate), we just
12296 auto *AddRec = dyn_cast<SCEVAddRecExpr>(S);
12298 if (!AddRec)
12306 return AddRec;