Lines Matching defs:AddRec
553 // Compare addrec loop depths.
562 // Addrec complexity grows with operand count.
884 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
886 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
887 Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty));
888 return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap);
950 // If we have special knowledge that this addrec won't overflow,
971 // the addrec's type. The count is always unsigned.
989 // Cache knowledge of AR NUW, which is propagated to this AddRec.
991 // Return the expression with the addrec on the outside.
1003 // Cache knowledge of AR NW, which is propagated to this AddRec.
1006 // Return the expression with the addrec on the outside.
1014 // the addrec is safe. Also, if the entry is guarded by a comparison
1016 // with the post-inc value, the addrec is safe.
1024 // Cache knowledge of AR NUW, which is propagated to this AddRec.
1026 // Return the expression with the addrec on the outside.
1038 // Cache knowledge of AR NW, which is propagated to this AddRec.
1041 // Return the expression with the addrec on the outside.
1081 // or postincrement sibling. This allows normalizing a sign extended AddRec as
1145 // Get the normalized sign-extended expression for this AddRec's Start.
1232 // If we have special knowledge that this addrec won't overflow,
1253 // the addrec's type. The count is always unsigned.
1271 // Cache knowledge of AR NSW, which is propagated to this AddRec.
1273 // Return the expression with the addrec on the outside.
1285 // Cache knowledge of AR NSW, which is propagated to this AddRec.
1287 // Return the expression with the addrec on the outside.
1295 // the addrec is safe. Also, if the entry is guarded by a comparison
1297 // with the post-inc value, the addrec is safe.
1305 // Cache knowledge of AR NSW, then propagate NSW to the wide AddRec.
1373 // Force the cast to be folded into the operands of an addrec.
1768 const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
1769 const Loop *AddRecLoop = AddRec->getLoop();
1780 LIOps.push_back(AddRec->getStart());
1782 SmallVector<const SCEV *, 4> AddRecOps(AddRec->op_begin(),
1783 AddRec->op_end());
1786 // Build the new addrec. Propagate the NUW and NSW flags if both the
1787 // outer add and the inner addrec are guaranteed to have no overflow.
1789 Flags = AddRec->getNoWrapFlags(setFlags(Flags, SCEV::FlagNW));
1795 // Otherwise, add the folded AddRec by the non-invariant parts.
1797 if (Ops[i] == AddRec) {
1805 // there are multiple AddRec's with the same loop induction variable being
1812 SmallVector<const SCEV *, 4> AddRecOps(AddRec->op_begin(),
1813 AddRec->op_end());
1973 AddRec = dyn_cast<SCEVAddRecExpr>(Ops[1])) {
1976 for (SCEVAddRecExpr::op_iterator I = AddRec->op_begin(),
1977 E = AddRec->op_end(); I != E; ++I) {
1980 return getAddRecExpr(Operands, AddRec->getLoop(),
1981 AddRec->getNoWrapFlags(SCEV::FlagNW));
2023 const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
2024 const Loop *AddRecLoop = AddRec->getLoop();
2036 NewOps.reserve(AddRec->getNumOperands());
2038 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
2039 NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i)));
2041 // Build the new addrec. Propagate the NUW and NSW flags if both the
2042 // outer mul and the inner addrec are guaranteed to have no overflow.
2046 Flags = AddRec->getNoWrapFlags(clearFlags(Flags, SCEV::FlagNW));
2052 // Otherwise, multiply the folded AddRec by the non-invariant parts.
2054 if (Ops[i] == AddRec) {
2062 // there are multiple AddRec's with the same loop induction variable being
2078 // addrec's are of different length (mathematically, it's equivalent to
2089 Type *Ty = AddRec->getType();
2092 for (int x = 0, xe = AddRec->getNumOperands() +
2097 for (int z = std::max(y-x, y-(int)AddRec->getNumOperands()+1),
2107 const SCEV *Term1 = AddRec->getOperand(y-z);
2115 const SCEV *NewAddRec = getAddRecExpr(AddRecOps, AddRec->getLoop(),
2121 AddRec = dyn_cast<SCEVAddRecExpr>(NewAddRec);
2122 if (!AddRec)
2453 // Okay, it looks like we really DO need an addrec expr. Check to see if we
3123 // this phi as an addrec if it has a unique entry value and a unique
3177 // This is not a valid addrec if the step amount is varying each
3178 // loop iteration, but is not itself an addrec in this loop.
3184 // If the increment doesn't overflow, then neither the addrec nor
3230 } else if (const SCEVAddRecExpr *AddRec =
3236 // i really is an addrec evolution.
3237 if (AddRec->getLoop() == L && AddRec->isAffine()) {
3241 // initial step of the addrec evolution.
3242 if (StartVal == getMinusSCEV(AddRec->getOperand(0),
3243 AddRec->getOperand(1))) {
3247 getAddRecExpr(StartVal, AddRec->getOperand(1), L,
3481 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
3484 if (AddRec->getNoWrapFlags(SCEV::FlagNUW))
3485 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(AddRec->getStart()))
3491 // TODO: non-affine addrec
3492 if (AddRec->isAffine()) {
3493 Type *Ty = AddRec->getType();
3494 const SCEV *MaxBECount = getMaxBackedgeTakenCount(AddRec->getLoop());
3499 const SCEV *Start = AddRec->getStart();
3500 const SCEV *Step = AddRec->getStepRecurrence(*this);
3518 return setUnsignedRange(AddRec, ConservativeResult);
3525 return setUnsignedRange(AddRec, ConservativeResult);
3526 return setUnsignedRange(AddRec,
3531 return setUnsignedRange(AddRec, ConservativeResult);
3622 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
3625 if (AddRec->getNoWrapFlags(SCEV::FlagNSW)) {
3628 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
3629 if (!isKnownNonNegative(AddRec->getOperand(i))) AllNonNeg = false;
3630 if (!isKnownNonPositive(AddRec->getOperand(i))) AllNonPos = false;
3642 // TODO: non-affine addrec
3643 if (AddRec->isAffine()) {
3644 Type *Ty = AddRec->getType();
3645 const SCEV *MaxBECount = getMaxBackedgeTakenCount(AddRec->getLoop());
3650 const SCEV *Start = AddRec->getStart();
3651 const SCEV *Step = AddRec->getStepRecurrence(*this);
3669 return setSignedRange(AddRec, ConservativeResult);
3676 return setSignedRange(AddRec, ConservativeResult);
3677 return setSignedRange(AddRec,
3682 return setSignedRange(AddRec, ConservativeResult);
3828 // If the LHS of the add was an addrec and it has no-wrap flags,
4749 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
4750 if (AddRec->getLoop() == L) {
4755 const SCEV *Ret = AddRec->getNumIterationsInRange(CompRange, *this);
4825 EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C,
4828 const SCEV *Val = AddRec->evaluateAtIteration(InVal, SE);
4883 // particular, only affine AddRec's like {C1,+,C2}.
5489 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
5493 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
5494 const SCEV *OpAtScope = getSCEVAtScope(AddRec->getOperand(i), L);
5495 if (OpAtScope == AddRec->getOperand(i))
5500 SmallVector<const SCEV *, 8> NewOps(AddRec->op_begin(),
5501 AddRec->op_begin()+i);
5504 NewOps.push_back(getSCEVAtScope(AddRec->getOperand(i), L));
5507 getAddRecExpr(NewOps, AddRec->getLoop(),
5508 AddRec->getNoWrapFlags(SCEV::FlagNW));
5509 AddRec = dyn_cast<SCEVAddRecExpr>(FoldedRec);
5510 // The addrec may be folded to a nonrecurrence, for example, if the
5513 if (!AddRec)
5518 // If the scope is outside the addrec's loop, evaluate it by using the
5519 // loop exit value of the addrec.
5520 if (!AddRec->getLoop()->contains(L)) {
5521 // To evaluate this recurrence, we need to know how many times the AddRec
5523 const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
5524 if (BackedgeTakenCount == getCouldNotCompute()) return AddRec;
5526 // Then, evaluate the AddRec.
5527 return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
5530 return AddRec;
5616 SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) {
5617 assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!");
5618 const SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
5619 const SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
5620 const SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
5698 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
5699 if (!AddRec || AddRec->getLoop() != L)
5702 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of
5704 if (AddRec->isQuadratic() && AddRec->getType()->isIntegerTy()) {
5706 SolveQuadraticEquation(AddRec, *this);
5725 const SCEV *Val = AddRec->evaluateAtIteration(R1, *this);
5734 if (!AddRec->isAffine())
5749 const SCEV *Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
5750 const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop());
5754 // TODO: Handle a nonconstant Step given AddRec<NUW>. If the
5755 // AddRec is NUW, then (in an unsigned sense) it cannot be counting up to wrap
5801 if (!IsSubExpr && AddRec->getNoWrapFlags(SCEV::FlagNW)) {
5920 // If we're comparing an addrec with a value which is loop-invariant in the
5921 // addrec's loop, put the addrec on the left. Also make a dominance check,
6196 // If LHS or RHS is an addrec, check to see if the condition is true in
6198 // If LHS and RHS are both addrec, both conditions must be true in
6833 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of the
6843 // Next, solve the constructed addrec
7518 /// the delinearization input is the following AddRec SCEV:
7520 /// AddRec: {{{%A,+,(8 * %m * %o)}<%for.i>,+,(8 * %o)}<%for.j>,+,8}<%for.k>
7803 // If L is the addrec's loop, it's computable.
7909 // produces the addrec's value is a PHI, and a PHI effectively properly
