Lines Matching refs:SCEV
15 // scalar expressions, which are represented as subclasses of the SCEV class.
17 // can handle. We only create one SCEV of a particular shape, so
20 // One important aspect of the SCEV objects is that they are never cyclic, even
103 cl::desc("Maximum number of iterations SCEV will "
118 // SCEV class definitions
122 // Implementation of the SCEV class.
125 void SCEV::dump() const {
130 void SCEV::print(raw_ostream &OS) const {
137 const SCEV *Op = Trunc->getOperand();
144 const SCEV *Op = ZExt->getOperand();
151 const SCEV *Op = SExt->getOperand();
238 llvm_unreachable("Unknown SCEV kind!");
241 Type *SCEV::getType() const {
263 llvm_unreachable("Unknown SCEV kind!");
267 bool SCEV::isZero() const {
273 bool SCEV::isOne() const {
279 bool SCEV::isAllOnesValue() const {
285 /// isNonConstantNegative - Return true if the specified scev is negated, but
287 bool SCEV::isNonConstantNegative() const {
300 SCEV(FoldingSetNodeIDRef(), scCouldNotCompute) {}
302 bool SCEVCouldNotCompute::classof(const SCEV *S) {
306 const SCEV *ScalarEvolution::getConstant(ConstantInt *V) {
311 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
312 SCEV *S = new (SCEVAllocator) SCEVConstant(ID.Intern(SCEVAllocator), V);
317 const SCEV *ScalarEvolution::getConstant(const APInt& Val) {
321 const SCEV *
328 unsigned SCEVTy, const SCEV *op, Type *ty)
329 : SCEV(ID, SCEVTy), Op(op), Ty(ty) {}
332 const SCEV *op, Type *ty)
340 const SCEV *op, Type *ty)
348 const SCEV *op, Type *ty)
444 // SCEV Utilities
457 bool operator()(const SCEV *LHS, const SCEV *RHS) const {
464 int compare(const SCEV *LHS, const SCEV *RHS) const {
612 llvm_unreachable("Unknown SCEV kind!");
618 /// GroupByComplexity - Given a list of SCEV objects, order them by their
625 /// this to depend on where the addresses of various SCEV objects happened to
628 static void GroupByComplexity(SmallVectorImpl<const SCEV *> &Ops,
634 const SCEV *&LHS = Ops[0], *&RHS = Ops[1];
648 const SCEV *S = Ops[i];
667 // Simple SCEV method implementations
672 static const SCEV *BinomialCoefficient(const SCEV *It, unsigned K,
766 const SCEV *Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy);
768 const SCEV *S = SE.getMinusSCEV(It, SE.getConstant(It->getType(), i));
774 const SCEV *DivResult = SE.getUDivExpr(Dividend, SE.getConstant(DivFactor));
791 const SCEV *SCEVAddRecExpr::evaluateAtIteration(const SCEV *It,
793 const SCEV *Result = getStart();
798 const SCEV *Coeff = BinomialCoefficient(It, i, SE, getType());
808 // SCEV Expression folder implementations
811 const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op,
824 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
847 SmallVector<const SCEV *, 4> Operands;
850 const SCEV *S = getTruncateExpr(SA->getOperand(i), Ty);
862 SmallVector<const SCEV *, 4> Operands;
865 const SCEV *S = getTruncateExpr(SM->getOperand(i), Ty);
874 // If the input value is a chrec scev, truncate the chrec's operands.
876 SmallVector<const SCEV *, 4> Operands;
879 return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap);
892 SCEV *S = new (SCEVAllocator) SCEVTruncateExpr(ID.Intern(SCEVAllocator),
898 const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op,
917 // computed a SCEV for this Op and Ty.
923 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
929 const SCEV *X = ST->getOperand();
938 // If the input value is a chrec scev, and we can prove that the value
944 const SCEV *Start = AR->getStart();
945 const SCEV *Step = AR->getStepRecurrence(*this);
951 if (AR->getNoWrapFlags(SCEV::FlagNUW))
964 const SCEV *MaxBECount = getMaxBackedgeTakenCount(L);
971 const SCEV *CastedMaxBECount =
973 const SCEV *RecastedMaxBECount =
978 const SCEV *ZMul = getMulExpr(CastedMaxBECount, Step);
979 const SCEV *Add = getAddExpr(Start, ZMul);
980 const SCEV *OperandExtendedAdd =
986 const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNUW);
994 const SCEV *SMul = getMulExpr(CastedMaxBECount, Step);
1003 const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNW);
1016 const SCEV *N = getConstant(APInt::getMinValue(BitWidth) -
1023 const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNUW);
1030 const SCEV *N = getConstant(APInt::getMaxValue(BitWidth) -
1038 const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNW);
1050 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1051 SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator),
1060 static const SCEV *getOverflowLimitForStep(const SCEV *Step,
1083 static const SCEV *getPreStartForSignExtend(const SCEVAddRecExpr *AR,
1087 const SCEV *Start = AR->getStart();
1088 const SCEV *Step = AR->getStepRecurrence(*SE);
1095 // Create an AddExpr for "PreStart" after subtracting Step. Full SCEV
1098 SmallVector<const SCEV *, 4> DiffOps;
1111 const SCEV *PreStart = SE->getAddExpr(DiffOps, SA->getNoWrapFlags());
1113 SE->getAddRecExpr(PreStart, Step, L, SCEV::FlagAnyWrap));
1115 if (PreAR && PreAR->getNoWrapFlags(SCEV::FlagNSW))
1121 const SCEV *OperandExtendedStart =
1127 const_cast<SCEVAddRecExpr *>(PreAR)->setNoWrapFlags(SCEV::FlagNSW);
1129 DEBUG(dbgs() << "SCEV: untested prestart overflow check\n");
1135 const SCEV *OverflowLimit = getOverflowLimitForStep(Step, &Pred, SE);
1145 static const SCEV *getSignExtendAddRecStart(const SCEVAddRecExpr *AR,
1148 const SCEV *PreStart = getPreStartForSignExtend(AR, Ty, SE);
1156 const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op,
1179 // computed a SCEV for this Op and Ty.
1185 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1195 const SCEV *X = ST->getOperand();
1204 // If the input value is a chrec scev, and we can prove that the value
1210 const SCEV *Start = AR->getStart();
1211 const SCEV *Step = AR->getStepRecurrence(*this);
1217 if (AR->getNoWrapFlags(SCEV::FlagNSW))
1220 L, SCEV::FlagNSW);
1230 const SCEV *MaxBECount = getMaxBackedgeTakenCount(L);
1237 const SCEV *CastedMaxBECount =
1239 const SCEV *RecastedMaxBECount =
1244 const SCEV *SMul = getMulExpr(CastedMaxBECount, Step);
1245 const SCEV *Add = getAddExpr(Start, SMul);
1246 const SCEV *OperandExtendedAdd =
1252 const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW);
1260 const SCEV *UMul = getMulExpr(CastedMaxBECount, Step);
1268 const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW);
1281 const SCEV *OverflowLimit = getOverflowLimitForStep(Step, &Pred, this);
1288 const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW);
1298 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1299 SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator),
1305 /// getAnyExtendExpr - Return a SCEV for the given operand extended with
1308 const SCEV *ScalarEvolution::getAnyExtendExpr(const SCEV *Op,
1323 const SCEV *NewOp = T->getOperand();
1330 const SCEV *ZExt = getZeroExtendExpr(Op, Ty);
1335 const SCEV *SExt = getSignExtendExpr(Op, Ty);
1341 SmallVector<const SCEV *, 4> Ops;
1345 return getAddRecExpr(Ops, AR->getLoop(), SCEV::FlagNW);
1389 CollectAddOperandsWithScales(DenseMap<const SCEV *, APInt> &M,
1390 SmallVector<const SCEV *, 8> &NewOps,
1392 const SCEV *const *Ops, size_t NumOperands,
1424 SmallVector<const SCEV *, 4> MulOps(Mul->op_begin()+1, Mul->op_end());
1425 const SCEV *Key = SE.getMulExpr(MulOps);
1426 std::pair<DenseMap<const SCEV *, APInt>::iterator, bool> Pair =
1439 std::pair<DenseMap<const SCEV *, APInt>::iterator, bool> Pair =
1465 const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
1466 SCEV::NoWrapFlags Flags) {
1467 assert(!(Flags & ~(SCEV::FlagNUW | SCEV::FlagNSW)) &&
1480 int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW;
1481 SCEV::NoWrapFlags SignOrUnsignWrap = maskFlags(Flags, SignOrUnsignMask);
1484 for (SmallVectorImpl<const SCEV *>::const_iterator I = Ops.begin(),
1490 if (All) Flags = setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask);
1531 const SCEV *Scale = getConstant(Ty, Count);
1532 const SCEV *Mul = getMulExpr(Scale, Ops[i]);
1551 SmallVector<const SCEV *, 8> LargeOps;
1565 SmallVector<const SCEV *, 8> LargeMulOps;
1591 const SCEV *Fold = getAddExpr(LargeOps, Flags);
1628 DenseMap<const SCEV *, APInt> M;
1629 SmallVector<const SCEV *, 8> NewOps;
1637 std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists;
1638 for (SmallVector<const SCEV *, 8>::const_iterator I = NewOps.begin(),
1645 for (std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare>::iterator
1664 const SCEV *MulOpSCEV = Mul->getOperand(MulOp);
1670 const SCEV *InnerMul = Mul->getOperand(MulOp == 0);
1674 SmallVector<const SCEV *, 4> MulOps(Mul->op_begin(),
1679 const SCEV *One = getConstant(Ty, 1);
1680 const SCEV *AddOne = getAddExpr(One, InnerMul);
1681 const SCEV *OuterMul = getMulExpr(AddOne, MulOpSCEV);
1705 const SCEV *InnerMul1 = Mul->getOperand(MulOp == 0);
1707 SmallVector<const SCEV *, 4> MulOps(Mul->op_begin(),
1712 const SCEV *InnerMul2 = OtherMul->getOperand(OMulOp == 0);
1714 SmallVector<const SCEV *, 4> MulOps(OtherMul->op_begin(),
1719 const SCEV *InnerMulSum = getAddExpr(InnerMul1,InnerMul2);
1720 const SCEV *OuterMul = getMulExpr(MulOpSCEV, InnerMulSum);
1741 SmallVector<const SCEV *, 8> LIOps;
1756 SmallVector<const SCEV *, 4> AddRecOps(AddRec->op_begin(),
1763 Flags = AddRec->getNoWrapFlags(setFlags(Flags, SCEV::FlagNW));
1764 const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRecLoop, Flags);
1786 SmallVector<const SCEV *, 4> AddRecOps(AddRec->op_begin(),
1806 Ops[Idx] = getAddRecExpr(AddRecOps, AddRecLoop, SCEV::FlagAnyWrap);
1824 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
1868 const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
1869 SCEV::NoWrapFlags Flags) {
1870 assert(Flags == maskFlags(Flags, SCEV::FlagNUW | SCEV::FlagNSW) &&
1883 int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW;
1884 SCEV::NoWrapFlags SignOrUnsignWrap = maskFlags(Flags, SignOrUnsignMask);
1887 for (SmallVectorImpl<const SCEV *>::const_iterator I = Ops.begin(),
1893 if (All) Flags = setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask);
1935 SmallVector<const SCEV *, 4> NewOps;
1939 const SCEV *Mul = getMulExpr(Ops[0], *I);
1949 SmallVector<const SCEV *, 4> Operands;
1955 AddRec->getNoWrapFlags(SCEV::FlagNW));
1996 SmallVector<const SCEV *, 8> LIOps;
2009 SmallVector<const SCEV *, 4> NewOps;
2011 const SCEV *Scale = getMulExpr(LIOps);
2020 Flags = AddRec->getNoWrapFlags(clearFlags(Flags, SCEV::FlagNW));
2021 const SCEV *NewRec = getAddRecExpr(NewOps, AddRecLoop, Flags);
2047 // known at compile time, never SCEV objects.
2061 SmallVector<const SCEV*, 7> AddRecOps;
2065 const SCEV *Term = getConstant(Ty, 0);
2077 const SCEV *CoeffTerm = getConstant(Ty, Coeff);
2078 const SCEV *Term1 = AddRec->getOperand(y-z);
2079 const SCEV *Term2 = OtherAddRec->getOperand(z);
2086 const SCEV *NewAddRec = getAddRecExpr(AddRecOps,
2088 SCEV::FlagAnyWrap);
2114 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
2126 const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS,
2127 const SCEV *RHS) {
2161 AR->getLoop(), SCEV::FlagAnyWrap)) {
2162 SmallVector<const SCEV *, 4> Operands;
2166 SCEV::FlagNW);
2176 AR->getLoop(), SCEV::FlagAnyWrap)) {
2181 AR->getLoop(), SCEV::FlagNW);
2186 SmallVector<const SCEV *, 4> Operands;
2192 const SCEV *Op = M->getOperand(i);
2193 const SCEV *Div = getUDivExpr(Op, RHSC);
2195 Operands = SmallVector<const SCEV *, 4>(M->op_begin(),
2204 SmallVector<const SCEV *, 4> Operands;
2210 const SCEV *Op = getUDivExpr(A->getOperand(i), RHS);
2236 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
2237 SCEV *S = new (SCEVAllocator) SCEVUDivExpr(ID.Intern(SCEVAllocator),
2246 const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, const SCEV *Step,
2248 SCEV::NoWrapFlags Flags) {
2249 SmallVector<const SCEV *, 4> Operands;
2254 return getAddRecExpr(Operands, L, maskFlags(Flags, SCEV::FlagNW));
2263 const SCEV *
2264 ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
2265 const Loop *L, SCEV::NoWrapFlags Flags) {
2279 return getAddRecExpr(Operands, L, SCEV::FlagAnyWrap); // {X,+,0} --> X
2290 int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW;
2291 SCEV::NoWrapFlags SignOrUnsignWrap = maskFlags(Flags, SignOrUnsignMask);
2294 for (SmallVectorImpl<const SCEV *>::const_iterator I = Operands.begin(),
2300 if (All) Flags = setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask);
2310 SmallVector<const SCEV *, 4> NestedOperands(NestedAR->op_begin(),
2327 SCEV::NoWrapFlags OuterFlags =
2328 maskFlags(Flags, SCEV::FlagNW | NestedAR->getNoWrapFlags());
2342 SCEV::NoWrapFlags InnerFlags =
2343 maskFlags(NestedAR->getNoWrapFlags(), SCEV::FlagNW | Flags);
2363 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Operands.size());
2373 const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS,
2374 const SCEV *RHS) {
2375 SmallVector<const SCEV *, 2> Ops;
2381 const SCEV *
2382 ScalarEvolution::getSMaxExpr(SmallVectorImpl<const SCEV *> &Ops) {
2468 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
2469 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
2471 SCEV *S = new (SCEVAllocator) SCEVSMaxExpr(ID.Intern(SCEVAllocator),
2477 const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS,
2478 const SCEV *RHS) {
2479 SmallVector<const SCEV *, 2> Ops;
2485 const SCEV *
2486 ScalarEvolution::getUMaxExpr(SmallVectorImpl<const SCEV *> &Ops) {
2572 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
2573 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
2575 SCEV *S = new (SCEVAllocator) SCEVUMaxExpr(ID.Intern(SCEVAllocator),
2581 const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS,
2582 const SCEV *RHS) {
2587 const SCEV *ScalarEvolution::getUMinExpr(const SCEV *LHS,
2588 const SCEV *RHS) {
2593 const SCEV *ScalarEvolution::getSizeOfExpr(Type *AllocTy) {
2609 const SCEV *ScalarEvolution::getAlignOfExpr(Type *AllocTy) {
2618 const SCEV *ScalarEvolution::getOffsetOfExpr(StructType *STy,
2635 const SCEV *ScalarEvolution::getOffsetOfExpr(Type *CTy,
2645 const SCEV *ScalarEvolution::getUnknown(Value *V) {
2649 // is doing so in order to hide a value from SCEV canonicalization.
2655 if (SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) {
2660 SCEV *S = new (SCEVAllocator) SCEVUnknown(ID.Intern(SCEVAllocator), V, this,
2668 // Basic SCEV Analysis and PHI Idiom Recognition Code
2672 /// the SCEV framework. This primarily includes integer types, and it
2700 /// the given type and which represents how SCEV will treat the given
2717 const SCEV *ScalarEvolution::getCouldNotCompute() {
2721 /// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
2723 const SCEV *ScalarEvolution::getSCEV(Value *V) {
2728 const SCEV *S = createSCEV(V);
2730 // The process of creating a SCEV for V may have caused other SCEVs
2738 /// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
2740 const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V) {
2751 /// getNotSCEV - Return a SCEV corresponding to ~V = -1-V
2752 const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) {
2759 const SCEV *AllOnes =
2764 /// getMinusSCEV - Return LHS-RHS. Minus is represented in SCEV as A+B*-1.
2765 const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
2766 SCEV::NoWrapFlags Flags) {
2767 assert(!maskFlags(Flags, SCEV::FlagNUW) && "subtraction does not have NUW");
2777 /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the
2780 const SCEV *
2781 ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V, Type *Ty) {
2793 /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion of the
2796 const SCEV *
2797 ScalarEvolution::getTruncateOrSignExtend(const SCEV *V,
2810 /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of the
2813 const SCEV *
2814 ScalarEvolution::getNoopOrZeroExtend(const SCEV *V, Type *Ty) {
2826 /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of the
2829 const SCEV *
2830 ScalarEvolution::getNoopOrSignExtend(const SCEV *V, Type *Ty) {
2842 /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of
2846 const SCEV *
2847 ScalarEvolution::getNoopOrAnyExtend(const SCEV *V, Type *Ty) {
2859 /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the
2861 const SCEV *
2862 ScalarEvolution::getTruncateOrNoop(const SCEV *V, Type *Ty) {
2877 const SCEV *ScalarEvolution::getUMaxFromMismatchedTypes(const SCEV *LHS,
2878 const SCEV *RHS) {
2879 const SCEV *PromotedLHS = LHS;
2880 const SCEV *PromotedRHS = RHS;
2893 const SCEV *ScalarEvolution::getUMinFromMismatchedTypes(const SCEV *LHS,
2894 const SCEV *RHS) {
2895 const SCEV *PromotedLHS = LHS;
2896 const SCEV *PromotedRHS = RHS;
2907 /// until reaching a SCEV that does not have a single pointer operand. This
2910 const SCEV *ScalarEvolution::getPointerBase(const SCEV *V) {
2919 const SCEV *PtrOp = 0;
2947 /// ForgetSymbolicValue - This looks up computed SCEV values for all
2952 ScalarEvolution::ForgetSymbolicName(Instruction *PN, const SCEV *SymName) {
2965 const SCEV *Old = It->second;
2994 const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) {
3019 const SCEV *SymbolicName = getUnknown(PN);
3026 const SCEV *BEValue = getSCEV(BEValueV);
3046 SmallVector<const SCEV *, 8> Ops;
3050 const SCEV *Accum = getAddExpr(Ops);
3057 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
3063 Flags = setFlags(Flags, SCEV::FlagNUW);
3065 Flags = setFlags(Flags, SCEV::FlagNSW);
3074 Flags = setFlags(Flags, SCEV::FlagNW);
3077 const SCEV *StartVal = getSCEV(StartValueV);
3078 const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags);
3102 const SCEV *StartVal = getSCEV(StartValueV);
3110 const SCEV *PHISCEV =
3112 SCEV::FlagAnyWrap);
3139 /// operations. This allows them to be analyzed by regular SCEV code.
3141 const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) {
3154 const SCEV *TotalOffset = getConstant(IntPtrTy, 0);
3164 const SCEV *FieldOffset = getOffsetOfExpr(STy, FieldNo);
3170 const SCEV *ElementSize = getSizeOfExpr(*GTI);
3171 const SCEV *IndexS = getSCEV(Index);
3176 const SCEV *LocalOffset = getMulExpr(IndexS, ElementSize,
3177 isInBounds ? SCEV::FlagNSW :
3178 SCEV::FlagAnyWrap);
3185 // Get the SCEV for the GEP base.
3186 const SCEV *BaseS = getSCEV(Base);
3190 isInBounds ? SCEV::FlagNSW : SCEV::FlagAnyWrap);
3198 ScalarEvolution::GetMinTrailingZeros(const SCEV *S) {
3273 /// getUnsignedRange - Determine the unsigned range for a particular SCEV.
3276 ScalarEvolution::getUnsignedRange(const SCEV *S) {
3278 DenseMap<const SCEV *, ConstantRange>::iterator I = UnsignedRanges.find(S);
3351 if (AddRec->getNoWrapFlags(SCEV::FlagNUW))
3361 const SCEV *MaxBECount = getMaxBackedgeTakenCount(AddRec->getLoop());
3366 const SCEV *Start = AddRec->getStart();
3367 const SCEV *Step = AddRec->getStepRecurrence(*this);
3414 /// getSignedRange - Determine the signed range for a particular SCEV.
3417 ScalarEvolution::getSignedRange(const SCEV *S) {
3419 DenseMap<const SCEV *, ConstantRange>::iterator I = SignedRanges.find(S);
3492 if (AddRec->getNoWrapFlags(SCEV::FlagNSW)) {
3512 const SCEV *MaxBECount = getMaxBackedgeTakenCount(AddRec->getLoop());
3517 const SCEV *Start = AddRec->getStart();
3518 const SCEV *Step = AddRec->getStepRecurrence(*this);
3567 /// createSCEV - We know that there is no SCEV for the specified value.
3570 const SCEV *ScalarEvolution::createSCEV(Value *V) {
3608 // mapped to the same SCEV expression, and it would be incorrect to transfer
3610 SmallVector<const SCEV *, 4> AddOps;
3617 const SCEV *Op1 = getSCEV(U->getOperand(1));
3628 SmallVector<const SCEV *, 4> MulOps;
3647 // use zext(trunc(x)) as the SCEV expression.
3682 const SCEV *LHS = getSCEV(U->getOperand(0));
3686 // Build a plain add SCEV.
3687 const SCEV *S = getAddExpr(LHS, getSCEV(CI));
3722 const SCEV *Z0 = Z->getOperand();
3781 // For a two-shift sext-inreg, use sext(trunc(x)) as the SCEV expression.
3848 const SCEV *LS = getSCEV(LHS);
3849 const SCEV *RS = getSCEV(RHS);
3850 const SCEV *LA = getSCEV(U->getOperand(1));
3851 const SCEV *RA = getSCEV(U->getOperand(2));
3852 const SCEV *LDiff = getMinusSCEV(LA, LS);
3853 const SCEV *RDiff = getMinusSCEV(RA, RS);
3871 const SCEV *LS = getSCEV(LHS);
3872 const SCEV *RS = getSCEV(RHS);
3873 const SCEV *LA = getSCEV(U->getOperand(1));
3874 const SCEV *RA = getSCEV(U->getOperand(2));
3875 const SCEV *LDiff = getMinusSCEV(LA, LS);
3876 const SCEV *RDiff = getMinusSCEV(RA, RS);
3890 const SCEV *One = getConstant(LHS->getType(), 1);
3891 const SCEV *LS = getSCEV(LHS);
3892 const SCEV *LA = getSCEV(U->getOperand(1));
3893 const SCEV *RA = getSCEV(U->getOperand(2));
3894 const SCEV *LDiff = getMinusSCEV(LA, LS);
3895 const SCEV *RDiff = getMinusSCEV(RA, One);
3905 const SCEV *One = getConstant(LHS->getType(), 1);
3906 const SCEV *LS = getSCEV(LHS);
3907 const SCEV *LA = getSCEV(U->getOperand(1));
3908 const SCEV *RA = getSCEV(U->getOperand(2));
3909 const SCEV *LDiff = getMinusSCEV(LA, One);
3910 const SCEV *RDiff = getMinusSCEV(RA, LS);
3974 const SCEV *ExitCount = getExitCount(L, ExitingBlock);
3979 const SCEV *TCMul = getAddExpr(ExitCount,
3981 // FIXME: SCEV distributes multiplication as V1*C1 + V2*C1. We could attempt
4002 const SCEV *ScalarEvolution::getExitCount(Loop *L, BasicBlock *ExitingBlock) {
4017 const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L) {
4022 /// return the least SCEV value that is known never to be less than the
4024 const SCEV *ScalarEvolution::getMaxBackedgeTakenCount(const Loop *L) {
4044 // update the value. The temporary CouldNotCompute value tells SCEV
4070 // existing SCEV values for PHI nodes in this loop since they are only
4086 const SCEV *Old = It->second;
4188 const SCEV *
4197 const SCEV *BECount = 0;
4201 assert(ENT->ExactNotTaken != SE->getCouldNotCompute() && "bad exit SCEV");
4213 const SCEV *
4226 const SCEV *
4234 SmallVectorImpl< std::pair<BasicBlock *, const SCEV *> > &ExitCounts,
4235 bool Complete, const SCEV *MaxCount) : Max(MaxCount) {
4273 const SCEV *MaxBECount = getCouldNotCompute();
4275 SmallVector<std::pair<BasicBlock *, const SCEV *>, 4> ExitCounts;
4381 const SCEV *BECount = getCouldNotCompute();
4382 const SCEV *MaxBECount = getCouldNotCompute();
4413 const SCEV *BECount = getCouldNotCompute();
4414 const SCEV *MaxBECount = getCouldNotCompute();
4490 const SCEV *LHS = getSCEV(ExitCond->getOperand(0));
4491 const SCEV *RHS = getSCEV(ExitCond->getOperand(1));
4517 const SCEV *Ret = AddRec->getNumIterationsInRange(CompRange, *this);
4573 const SCEV *InVal = SE.getConstant(C);
4574 const SCEV *Val = AddRec->evaluateAtIteration(InVal, SE);
4576 "Evaluation of SCEV at constant didn't fold correctly?");
4593 // TODO: Use SCEV instead of manually grubbing with GEPs.
4625 const SCEV *Idx = getSCEV(VarIdx);
4903 const SCEV *ScalarEvolution::ComputeExitCountExhaustively(const Loop *L,
4978 /// getSCEVAtScope - Return a SCEV expression for the specified value
4988 const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) {
4990 std::map<const Loop *, const SCEV *> &Values = ValuesAtScopes[V];
4991 std::pair<std::map<const Loop *, const SCEV *>::iterator, bool> Pair =
4992 Values.insert(std::make_pair(L, static_cast<const SCEV *>(0)));
4997 const SCEV *C = computeSCEVAtScope(V, L);
5005 /// Returns NULL if the SCEV isn't representable as a Constant.
5006 static Constant *BuildConstantFromSCEV(const SCEV *V) {
5094 const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) {
5109 const SCEV *BackedgeTakenCount = getBackedgeTakenCount(LI);
5123 // into a SCEV. Check to see if it's possible to symbolically evaluate
5138 // with scev techniques.
5142 const SCEV *OrigV = getSCEV(Op);
5143 const SCEV *OpV = getSCEVAtScope(OrigV, L);
5183 const SCEV *OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
5187 SmallVector<const SCEV *, 8> NewOps(Comm->op_begin(),
5203 llvm_unreachable("Unknown commutative SCEV type!");
5211 const SCEV *LHS = getSCEVAtScope(Div->getLHS(), L);
5212 const SCEV *RHS = getSCEVAtScope(Div->getRHS(), L);
5225 const SCEV *OpAtScope = getSCEVAtScope(AddRec->getOperand(i), L);
5231 SmallVector<const SCEV *, 8> NewOps(AddRec->op_begin(),
5237 const SCEV *FoldedRec =
5239 AddRec->getNoWrapFlags(SCEV::FlagNW));
5254 const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
5265 const SCEV *Op = getSCEVAtScope(Cast->getOperand(), L);
5272 const SCEV *Op = getSCEVAtScope(Cast->getOperand(), L);
5279 const SCEV *Op = getSCEVAtScope(Cast->getOperand(), L);
5285 llvm_unreachable("Unknown SCEV type!");
5290 const SCEV *ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) {
5303 static const SCEV *SolveLinEquationWithOverflow(const APInt &A, const APInt &B,
5346 static std::pair<const SCEV *,const SCEV *>
5355 const SCEV *CNC = SE.getCouldNotCompute();
5391 const SCEV *CNC = SE.getCouldNotCompute();
5415 ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) {
5430 std::pair<const SCEV *,const SCEV *> Roots =
5450 const SCEV *Val = AddRec->evaluateAtIteration(R1, *this);
5474 const SCEV *Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
5475 const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop());
5493 const SCEV *Distance = CountDown ? Start : getNegativeSCEV(Start);
5500 const SCEV *MaxBECount;
5522 if (AddRec->getNoWrapFlags(SCEV::FlagNW)) {
5538 ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) {
5578 /// HasSameValue - SCEV structural equivalence is usually sufficient for
5584 static bool HasSameValue(const SCEV *A, const SCEV *B) {
5585 // Quick check to see if they are the same SCEV.
5605 const SCEV *&LHS, const SCEV *&RHS) {
5791 SCEV::FlagNSW);
5796 SCEV::FlagNSW);
5804 SCEV::FlagNSW);
5809 SCEV::FlagNSW);
5817 SCEV::FlagNUW);
5822 SCEV::FlagNUW);
5830 SCEV::FlagNUW);
5835 SCEV::FlagNUW);
5861 bool ScalarEvolution::isKnownNegative(const SCEV *S) {
5865 bool ScalarEvolution::isKnownPositive(const SCEV *S) {
5869 bool ScalarEvolution::isKnownNonNegative(const SCEV *S) {
5873 bool ScalarEvolution::isKnownNonPositive(const SCEV *S) {
5877 bool ScalarEvolution::isKnownNonZero(const SCEV *S) {
5882 const SCEV *LHS, const SCEV *RHS) {
5907 const SCEV *LHS, const SCEV *RHS) {
5970 const SCEV *Diff = getMinusSCEV(LHS, RHS);
5989 const SCEV *LHS, const SCEV *RHS) {
6015 const SCEV *LHS, const SCEV *RHS) {
6046 const SCEV *LHS, const SCEV *RHS,
6082 const SCEV *FoundLHS = getSCEV(ICI->getOperand(0));
6083 const SCEV *FoundRHS = getSCEV(ICI->getOperand(1));
6150 const SCEV *LHS, const SCEV *RHS,
6151 const SCEV *FoundLHS,
6152 const SCEV *FoundRHS) {
6166 const SCEV *LHS, const SCEV *RHS,
6167 const SCEV *FoundLHS,
6168 const SCEV *FoundRHS) {
6208 const SCEV *ScalarEvolution::getBECount(const SCEV *Start,
6209 const SCEV *End,
6210 const SCEV *Step,
6218 // here because SCEV may not be able to determine that the unsigned division
6223 const SCEV *NegOne = getConstant(Ty, (uint64_t)-1);
6224 const SCEV *Diff = getMinusSCEV(End, Start);
6225 const SCEV *RoundUp = getAddExpr(Step, NegOne);
6229 const SCEV *Add = getAddExpr(Diff, RoundUp);
6236 const SCEV *EDiff = getZeroExtendExpr(Diff, WideTy);
6237 const SCEV *ERoundUp = getZeroExtendExpr(RoundUp, WideTy);
6238 const SCEV *OperandExtendedAdd = getAddExpr(EDiff, ERoundUp);
6250 ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
6261 AddRec->getNoWrapFlags((SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNW)) :
6262 AddRec->getNoWrapFlags((SCEV::NoWrapFlags)(SCEV::FlagNUW | SCEV::FlagNW));
6266 const SCEV *Step = AddRec->getStepRecurrence(*this);
6280 const SCEV *One = getConstant(Step->getType(), 1);
6302 const SCEV *Start = AddRec->getOperand(0);
6305 const SCEV *MinStart = getConstant(isSigned ?
6313 const SCEV *End = RHS;
6322 const SCEV *MaxEnd = getConstant(isSigned ?
6330 const SCEV *StepMinusOne = getMinusSCEV(Step,
6342 const SCEV *BECount = getBECount(Start, End, Step, NoWrap);
6347 const SCEV *MaxBECount = isa<SCEVConstant>(BECount) ? BECount
6368 const SCEV *SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range,
6376 SmallVector<const SCEV *, 4> Operands(op_begin(), op_end());
6378 const SCEV *Shifted = SE.getAddRecExpr(Operands, getLoop(),
6431 "Linear scev computation is off in a bad way!");
6438 SmallVector<const SCEV *, 4> NewOps(op_begin(), op_end());
6440 const SCEV *NewAddRec = SE.getAddRecExpr(NewOps, getLoop(),
6445 std::pair<const SCEV *,const SCEV *> Roots =
6634 // out SCEV values of all instructions that are interesting. Doing
6635 // this potentially causes it to create new SCEV objects though,
6648 const SCEV *SV = SE.getSCEV(&*I);
6653 const SCEV *AtUse = SE.getSCEVAtScope(SV, L);
6661 const SCEV *ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop());
6680 ScalarEvolution::getLoopDisposition(const SCEV *S, const Loop *L) {
6692 ScalarEvolution::computeLoopDisposition(const SCEV *S, const Loop *L) {
6766 default: llvm_unreachable("Unknown SCEV kind!");
6770 bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) {
6774 bool ScalarEvolution::hasComputableLoopEvolution(const SCEV *S, const Loop *L) {
6779 ScalarEvolution::getBlockDisposition(const SCEV *S, const BasicBlock *BB) {
6791 ScalarEvolution::computeBlockDisposition(const SCEV *S, const BasicBlock *BB) {
6827 const SCEV *LHS = UDiv->getLHS(), *RHS = UDiv->getRHS();
6850 llvm_unreachable("Unknown SCEV kind!");
6854 bool ScalarEvolution::dominates(const SCEV *S, const BasicBlock *BB) {
6858 bool ScalarEvolution::properlyDominates(const SCEV *S, const BasicBlock *BB) {
6862 SCEV *S, const SCEV *Op) const {
6870 const SCEV *CastOp = Cast->getOperand();
6881 const SCEV *NAryOp = *I;
6889 const SCEV *LHS = UDiv->getLHS(), *RHS = UDiv->getRHS();
6898 llvm_unreachable("Unknown SCEV kind!");
6902 void ScalarEvolution::forgetMemoizedResults(const SCEV *S) {
