Lines Matching defs:SCEV
14 // scalar expressions, which are represented as subclasses of the SCEV class.
16 // can handle. We only create one SCEV of a particular shape, so
19 // One important aspect of the SCEV objects is that they are never cyclic, even
154 cl::desc("Maximum number of iterations SCEV will "
168 cl::desc("Verify IR correctness when making sensitive SCEV queries (slow)"),
173 cl::desc("Threshold for inlining multiplication operands into a SCEV"),
178 cl::desc("Threshold for inlining addition operands into a SCEV"),
183 cl::desc("Maximum depth of recursive SCEV complexity comparisons"),
188 cl::desc("Maximum depth of recursive SCEV operations implication analysis"),
222 cl::desc("Threshold for switching to iteratively computing SCEV ranges"),
253 // SCEV class definitions
257 // Implementation of the SCEV class.
261 LLVM_DUMP_METHOD void SCEV::dump() const {
267 void SCEV::print(raw_ostream &OS) const {
277 const SCEV *Op = PtrToInt->getOperand();
284 const SCEV *Op = Trunc->getOperand();
291 const SCEV *Op = ZExt->getOperand();
298 const SCEV *Op = SExt->getOperand();
348 for (const SCEV *Op : NAry->operands())
377 llvm_unreachable("Unknown SCEV kind!");
380 Type *SCEV::getType() const {
411 llvm_unreachable("Unknown SCEV kind!");
414 ArrayRef<const SCEV *> SCEV::operands() const {
439 llvm_unreachable("Unknown SCEV kind!");
442 bool SCEV::isZero() const {
448 bool SCEV::isOne() const {
454 bool SCEV::isAllOnesValue() const {
460 bool SCEV::isNonConstantNegative() const {
473 SCEV(FoldingSetNodeIDRef(), scCouldNotCompute, 0) {}
475 bool SCEVCouldNotCompute::classof(const SCEV *S) {
479 const SCEV *ScalarEvolution::getConstant(ConstantInt *V) {
484 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
485 SCEV *S = new (SCEVAllocator) SCEVConstant(ID.Intern(SCEVAllocator), V);
490 const SCEV *ScalarEvolution::getConstant(const APInt &Val) {
494 const SCEV *
500 const SCEV *ScalarEvolution::getVScale(Type *Ty) {
505 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
507 SCEV *S = new (SCEVAllocator) SCEVVScale(ID.Intern(SCEVAllocator), Ty);
512 const SCEV *ScalarEvolution::getElementCount(Type *Ty, ElementCount EC) {
513 const SCEV *Res = getConstant(Ty, EC.getKnownMinValue());
520 const SCEV *op, Type *ty)
521 : SCEV(ID, SCEVTy, computeExpressionSize(op)), Op(op), Ty(ty) {}
523 SCEVPtrToIntExpr::SCEVPtrToIntExpr(const FoldingSetNodeIDRef ID, const SCEV *Op,
531 SCEVTypes SCEVTy, const SCEV *op,
535 SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeIDRef ID, const SCEV *op,
543 const SCEV *op, Type *ty)
550 const SCEV *op, Type *ty)
579 // SCEV Utilities
584 /// operands in SCEV expressions. \p EqCache is a set of pairs of values that
681 CompareSCEVComplexity(EquivalenceClasses<const SCEV *> &EqCacheSCEV,
683 const LoopInfo *const LI, const SCEV *LHS,
684 const SCEV *RHS, DominatorTree &DT, unsigned Depth = 0) {
738 // There is always a dominance between two recs that are used by one SCEV,
748 "No dominance between recurrences used by one SCEV?");
767 ArrayRef<const SCEV *> LOps = LHS->operands();
768 ArrayRef<const SCEV *> ROps = RHS->operands();
788 llvm_unreachable("Unknown SCEV kind!");
791 /// Given a list of SCEV objects, order them by their complexity, and group
798 /// this to depend on where the addresses of various SCEV objects happened to
800 static void GroupByComplexity(SmallVectorImpl<const SCEV *> &Ops,
804 EquivalenceClasses<const SCEV *> EqCacheSCEV;
808 auto IsLessComplex = [&](const SCEV *LHS, const SCEV *RHS) {
816 const SCEV *&LHS = Ops[0], *&RHS = Ops[1];
823 llvm::stable_sort(Ops, [&](const SCEV *LHS, const SCEV *RHS) {
832 const SCEV *S = Ops[i];
848 /// Returns true if \p Ops contains a huge SCEV (the subtree of S contains at
850 static bool hasHugeExpression(ArrayRef<const SCEV *> Ops) {
851 return any_of(Ops, [](const SCEV *S) {
857 // Simple SCEV method implementations
861 static const SCEV *BinomialCoefficient(const SCEV *It, unsigned K,
950 const SCEV *Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy);
952 const SCEV *S = SE.getMinusSCEV(It, SE.getConstant(It->getType(), i));
958 const SCEV *DivResult = SE.getUDivExpr(Dividend, SE.getConstant(DivFactor));
974 const SCEV *SCEVAddRecExpr::evaluateAtIteration(const SCEV *It,
979 const SCEV *
980 SCEVAddRecExpr::evaluateAtIteration(ArrayRef<const SCEV *> Operands,
981 const SCEV *It, ScalarEvolution &SE) {
983 const SCEV *Result = Operands[0];
988 const SCEV *Coeff = BinomialCoefficient(It, i, SE, Result->getType());
998 // SCEV Expression folder implementations
1001 const SCEV *ScalarEvolution::getLosslessPtrToIntExpr(const SCEV *Op,
1006 // We could be called with an integer-typed operands during SCEV rewrites.
1011 // What would be an ID for such a SCEV cast expression?
1019 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
1029 // We can only trivially model ptrtoint if SCEV's effective (integer) type
1031 // We could theoretically teach SCEV to truncate wider pointers, but
1040 // is a null pointer, don't create a ptr2int SCEV expression (that will be
1049 SCEV *S = new (SCEVAllocator)
1076 static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE) {
1081 const SCEV *visit(const SCEV *S) {
1090 const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
1091 SmallVector<const SCEV *, 2> Operands;
1100 const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
1101 SmallVector<const SCEV *, 2> Operands;
1110 const SCEV *visitUnknown(const SCEVUnknown *Expr) {
1118 const SCEV *IntOp = SCEVPtrToIntSinkingRewriter::rewrite(Op, *this);
1125 const SCEV *ScalarEvolution::getPtrToIntExpr(const SCEV *Op, Type *Ty) {
1128 const SCEV *IntOp = getLosslessPtrToIntExpr(Op);
1135 const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, Type *Ty,
1149 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1169 SCEV *S =
1182 SmallVector<const SCEV *, 4> Operands;
1186 const SCEV *S = getTruncateExpr(CommOp->getOperand(i), Ty, Depth + 1);
1197 llvm_unreachable("Unexpected SCEV type for Op.");
1202 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
1208 SmallVector<const SCEV *, 4> Operands;
1209 for (const SCEV *Op : AddRec->operands())
1211 return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap);
1222 SCEV *S = new (SCEVAllocator) SCEVTruncateExpr(ID.Intern(SCEVAllocator),
1232 static const SCEV *getSignedOverflowLimitForStep(const SCEV *Step,
1252 static const SCEV *getUnsignedOverflowLimitForStep(const SCEV *Step,
1265 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(const SCEV *, Type *,
1273 // static const SCEV::NoWrapFlags WrapType;
1277 // static const SCEV *getOverflowLimitForStep(const SCEV *Step,
1284 static const SCEV::NoWrapFlags WrapType = SCEV::FlagNSW;
1288 static const SCEV *getOverflowLimitForStep(const SCEV *Step,
1300 static const SCEV::NoWrapFlags WrapType = SCEV::FlagNUW;
1304 static const SCEV *getOverflowLimitForStep(const SCEV *Step,
1324 static const SCEV *getPreStartForExtend(const SCEVAddRecExpr *AR, Type *Ty,
1330 const SCEV *Start = AR->getStart();
1331 const SCEV *Step = AR->getStepRecurrence(*SE);
1338 // Create an AddExpr for "PreStart" after subtracting Step. Full SCEV
1342 SmallVector<const SCEV *, 4> DiffOps(SA->operands());
1352 // Try to prove `WrapType` (SCEV::FlagNSW or SCEV::FlagNUW) on `PreStart` +
1357 ScalarEvolution::maskFlags(SA->getNoWrapFlags(), SCEV::FlagNUW);
1358 const SCEV *PreStart = SE->getAddExpr(DiffOps, PreStartFlags);
1360 SE->getAddRecExpr(PreStart, Step, L, SCEV::FlagAnyWrap));
1366 const SCEV *BECount = SE->getBackedgeTakenCount(L);
1374 const SCEV *OperandExtendedStart =
1389 const SCEV *OverflowLimit =
1401 static const SCEV *getExtendAddRecStart(const SCEVAddRecExpr *AR, Type *Ty,
1406 const SCEV *PreStart = getPreStartForExtend<ExtendOpTy>(AR, Ty, SE, Depth);
1448 bool ScalarEvolution::proveNoWrapByVaryingStart(const SCEV *Start,
1449 const SCEV *Step,
1453 // We restrict `Start` to a constant to prevent SCEV from spending too much
1455 // non-constant `Start` and do a general SCEV subtraction to compute
1464 const SCEV *PreStart = getConstant(StartAI - Delta);
1478 const SCEV *DeltaS = getConstant(StartC->getType(), Delta);
1480 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1518 const SCEV *Step) {
1528 const ScalarEvolution::FoldID &ID, const SCEV *S,
1529 DenseMap<ScalarEvolution::FoldID, const SCEV *> &FoldCache,
1530 DenseMap<const SCEV *, SmallVector<ScalarEvolution::FoldID, 2>>
1550 const SCEV *
1551 ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) {
1564 const SCEV *S = getZeroExtendExprImpl(Op, Ty, Depth);
1570 const SCEV *ScalarEvolution::getZeroExtendExprImpl(const SCEV *Op, Type *Ty,
1586 // computed a SCEV for this Op and Ty.
1592 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1594 SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator),
1605 const SCEV *X = ST->getOperand();
1620 const SCEV *Start = AR->getStart();
1621 const SCEV *Step = AR->getStepRecurrence(*this);
1642 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L);
1648 const SCEV *CastedMaxBECount =
1650 const SCEV *RecastedMaxBECount = getTruncateOrZeroExtend(
1655 const SCEV *ZMul = getMulExpr(CastedMaxBECount, Step,
1656 SCEV::FlagAnyWrap, Depth + 1);
1657 const SCEV *ZAdd = getZeroExtendExpr(getAddExpr(Start, ZMul,
1658 SCEV::FlagAnyWrap,
1661 const SCEV *WideStart = getZeroExtendExpr(Start, WideTy, Depth + 1);
1662 const SCEV *WideMaxBECount =
1664 const SCEV *OperandExtendedAdd =
1668 SCEV::FlagAnyWrap, Depth + 1),
1669 SCEV::FlagAnyWrap, Depth + 1);
1672 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNUW);
1685 SCEV::FlagAnyWrap, Depth + 1),
1686 SCEV::FlagAnyWrap, Depth + 1);
1690 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNW);
1703 // guards present in the loop -- SCEV is not great at exploiting
1726 const SCEV *N = getConstant(APInt::getMaxValue(BitWidth) -
1733 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNW);
1750 const SCEV *SZExtD = getZeroExtendExpr(getConstant(D), Ty, Depth);
1751 const SCEV *SResidual =
1753 const SCEV *SZExtR = getZeroExtendExpr(SResidual, Ty, Depth + 1);
1755 (SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNUW),
1761 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNUW);
1771 const SCEV *LHS;
1772 const SCEV *RHS;
1788 SmallVector<const SCEV *, 4> Ops;
1791 return getAddExpr(Ops, SCEV::FlagNUW, Depth + 1);
1805 const SCEV *SZExtD = getZeroExtendExpr(getConstant(D), Ty, Depth);
1806 const SCEV *SResidual =
1807 getAddExpr(getConstant(-D), SA, SCEV::FlagAnyWrap, Depth);
1808 const SCEV *SZExtR = getZeroExtendExpr(SResidual, Ty, Depth + 1);
1810 (SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNUW),
1821 SmallVector<const SCEV *, 4> Ops;
1824 return getMulExpr(Ops, SCEV::FlagNUW, Depth + 1);
1850 SCEV::FlagNUW, Depth + 1);
1858 SmallVector<const SCEV *, 4> Operands;
1869 SmallVector<const SCEV *, 4> Operands;
1877 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1878 SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator),
1885 const SCEV *
1886 ScalarEvolution::getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) {
1899 const SCEV *S = getSignExtendExprImpl(Op, Ty, Depth);
1905 const SCEV *ScalarEvolution::getSignExtendExprImpl(const SCEV *Op, Type *Ty,
1926 // computed a SCEV for this Op and Ty.
1932 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1935 SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator),
1946 const SCEV *X = ST->getOperand();
1960 SmallVector<const SCEV *, 4> Ops;
1963 return getAddExpr(Ops, SCEV::FlagNSW, Depth + 1);
1978 const SCEV *SSExtD = getSignExtendExpr(getConstant(D), Ty, Depth);
1979 const SCEV *SResidual =
1980 getAddExpr(getConstant(-D), SA, SCEV::FlagAnyWrap, Depth);
1981 const SCEV *SSExtR = getSignExtendExpr(SResidual, Ty, Depth + 1);
1983 (SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNUW),
1994 const SCEV *Start = AR->getStart();
1995 const SCEV *Step = AR->getStepRecurrence(*this);
2005 return getAddRecExpr(Start, Step, L, SCEV::FlagNSW);
2016 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L);
2023 const SCEV *CastedMaxBECount =
2025 const SCEV *RecastedMaxBECount = getTruncateOrZeroExtend(
2030 const SCEV *SMul = getMulExpr(CastedMaxBECount, Step,
2031 SCEV::FlagAnyWrap, Depth + 1);
2032 const SCEV *SAdd = getSignExtendExpr(getAddExpr(Start, SMul,
2033 SCEV::FlagAnyWrap,
2036 const SCEV *WideStart = getSignExtendExpr(Start, WideTy, Depth + 1);
2037 const SCEV *WideMaxBECount =
2039 const SCEV *OperandExtendedAdd =
2043 SCEV::FlagAnyWrap, Depth + 1),
2044 SCEV::FlagAnyWrap, Depth + 1);
2047 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNSW);
2060 SCEV::FlagAnyWrap, Depth + 1),
2061 SCEV::FlagAnyWrap, Depth + 1);
2071 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNW);
2102 const SCEV *SSExtD = getSignExtendExpr(getConstant(D), Ty, Depth);
2103 const SCEV *SResidual =
2105 const SCEV *SSExtR = getSignExtendExpr(SResidual, Ty, Depth + 1);
2107 (SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNUW),
2113 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNSW);
2130 SmallVector<const SCEV *, 4> Operands;
2140 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
2141 SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator),
2148 const SCEV *ScalarEvolution::getCastExpr(SCEVTypes Kind, const SCEV *Op,
2160 llvm_unreachable("Not a SCEV cast expression!");
2164 /// getAnyExtendExpr - Return a SCEV for the given operand extended with
2166 const SCEV *ScalarEvolution::getAnyExtendExpr(const SCEV *Op,
2181 const SCEV *NewOp = T->getOperand();
2188 const SCEV *ZExt = getZeroExtendExpr(Op, Ty);
2193 const SCEV *SExt = getSignExtendExpr(Op, Ty);
2199 SmallVector<const SCEV *, 4> Ops;
2200 for (const SCEV *Op : AR->operands())
2202 return getAddRecExpr(Ops, AR->getLoop(), SCEV::FlagNW);
2237 CollectAddOperandsWithScales(DenseMap<const SCEV *, APInt> &M,
2238 SmallVectorImpl<const SCEV *> &NewOps,
2240 ArrayRef<const SCEV *> Ops, const APInt &Scale,
2270 SmallVector<const SCEV *, 4> MulOps(drop_begin(Mul->operands()));
2271 const SCEV *Key = SE.getMulExpr(MulOps);
2284 std::pair<DenseMap<const SCEV *, APInt>::iterator, bool> Pair =
2301 const SCEV *LHS, const SCEV *RHS,
2303 const SCEV *(ScalarEvolution::*Operation)(const SCEV *, const SCEV *,
2304 SCEV::NoWrapFlags, unsigned);
2319 const SCEV *(ScalarEvolution::*Extension)(const SCEV *, Type *, unsigned) =
2328 const SCEV *A = (this->*Extension)(
2329 (this->*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0), WideTy, 0);
2330 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2331 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2332 const SCEV *B = (this->*Operation)(LHSB, RHSB, SCEV::FlagAnyWrap, 0);
2376 std::optional<SCEV::NoWrapFlags>
2383 SCEV::NoWrapFlags Flags = SCEV::NoWrapFlags::FlagAnyWrap;
2386 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
2388 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW);
2397 const SCEV *LHS = getSCEV(OBO->getOperand(0));
2398 const SCEV *RHS = getSCEV(OBO->getOperand(1));
2405 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
2412 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW);
2421 // We're trying to construct a SCEV of type `Type' with `Ops' as operands and
2424 static SCEV::NoWrapFlags
2426 const ArrayRef<const SCEV *> Ops,
2427 SCEV::NoWrapFlags Flags) {
2437 int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW;
2438 SCEV::NoWrapFlags SignOrUnsignWrap =
2442 auto IsKnownNonNegative = [&](const SCEV *S) {
2446 if (SignOrUnsignWrap == SCEV::FlagNSW && all_of(Ops, IsKnownNonNegative))
2448 ScalarEvolution::setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask);
2463 llvm_unreachable("Unexpected SCEV op.");
2470 if (!(SignOrUnsignWrap & SCEV::FlagNSW)) {
2474 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW);
2478 if (!(SignOrUnsignWrap & SCEV::FlagNUW)) {
2482 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
2488 if (Type == scAddRecExpr && ScalarEvolution::hasFlags(Flags, SCEV::FlagNW) &&
2489 !ScalarEvolution::hasFlags(Flags, SCEV::FlagNUW) && Ops.size() == 2 &&
2491 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
2494 if (Type == scMulExpr && !ScalarEvolution::hasFlags(Flags, SCEV::FlagNUW) &&
2498 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
2501 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
2507 bool ScalarEvolution::isAvailableAtLoopEntry(const SCEV *S, const Loop *L) {
2512 const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
2513 SCEV::NoWrapFlags OrigFlags,
2515 assert(!(OrigFlags & ~(SCEV::FlagNUW | SCEV::FlagNSW)) &&
2525 Ops, [](const SCEV *Op) { return Op->getType()->isPointerTy(); });
2555 auto ComputeFlags = [this, OrigFlags](const ArrayRef<const SCEV *> Ops) {
2563 if (SCEV *S = findExistingSCEVInCache(scAddExpr, Ops)) {
2583 const SCEV *Scale = getConstant(Ty, Count);
2584 const SCEV *Mul = getMulExpr(Scale, Ops[i], SCEV::FlagAnyWrap, Depth + 1);
2601 // constants and truncs, so if we find any other types of SCEV
2614 SmallVector<const SCEV *, 8> LargeOps;
2618 for (const SCEV *Op : Ops) {
2628 SmallVector<const SCEV *, 8> LargeMulOps;
2645 LargeOps.push_back(getMulExpr(LargeMulOps, SCEV::FlagAnyWrap, Depth + 1));
2653 const SCEV *Fold = getAddExpr(LargeOps, SCEV::FlagAnyWrap, Depth + 1);
2664 const SCEV *A = Ops[0];
2665 const SCEV *B = Ops[1];
2671 SCEV::NoWrapFlags PreservedFlags = SCEV::FlagAnyWrap;
2676 if (ScalarEvolution::hasFlags(AddFlags, SCEV::FlagNUW) &&
2679 ScalarEvolution::setFlags(PreservedFlags, SCEV::FlagNUW);
2684 if (ScalarEvolution::hasFlags(AddFlags, SCEV::FlagNSW) &&
2688 ScalarEvolution::setFlags(PreservedFlags, SCEV::FlagNSW);
2691 if (PreservedFlags != SCEV::FlagAnyWrap) {
2692 SmallVector<const SCEV *, 4> NewOps(AddExpr->operands());
2704 const SCEV *X;
2705 const SCEV *Y;
2722 SCEV::NoWrapFlags CommonFlags = maskFlags(OrigFlags, SCEV::FlagNUW);
2750 DenseMap<const SCEV *, APInt> M;
2751 SmallVector<const SCEV *, 8> NewOps;
2764 std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists;
2765 for (const SCEV *NewOp : NewOps)
2773 Ops.push_back(getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1));
2777 getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1),
2778 SCEV::FlagAnyWrap, Depth + 1));
2785 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
2795 const SCEV *MulOpSCEV = Mul->getOperand(MulOp);
2801 const SCEV *InnerMul = Mul->getOperand(MulOp == 0);
2805 SmallVector<const SCEV *, 4> MulOps(
2808 InnerMul = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1);
2810 SmallVector<const SCEV *, 2> TwoOps = {getOne(Ty), InnerMul};
2811 const SCEV *AddOne = getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1);
2812 const SCEV *OuterMul = getMulExpr(AddOne, MulOpSCEV,
2813 SCEV::FlagAnyWrap, Depth + 1);
2823 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
2837 const SCEV *InnerMul1 = Mul->getOperand(MulOp == 0);
2839 SmallVector<const SCEV *, 4> MulOps(
2842 InnerMul1 = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1);
2844 const SCEV *InnerMul2 = OtherMul->getOperand(OMulOp == 0);
2846 SmallVector<const SCEV *, 4> MulOps(
2849 InnerMul2 = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1);
2851 SmallVector<const SCEV *, 2> TwoOps = {InnerMul1, InnerMul2};
2852 const SCEV *InnerMulSum =
2853 getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1);
2854 const SCEV *OuterMul = getMulExpr(MulOpSCEV, InnerMulSum,
2855 SCEV::FlagAnyWrap, Depth + 1);
2860 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
2876 SmallVector<const SCEV *, 8> LIOps;
2892 SCEV::NoWrapFlags Flags = ComputeFlags(LIOps);
2898 SmallVector<const SCEV *, 4> AddRecOps(AddRec->operands());
2910 SCEV::NoWrapFlags AddFlags = Flags;
2911 if (AddFlags != SCEV::FlagAnyWrap) {
2915 AddFlags = SCEV::FlagAnyWrap;
2922 Flags = AddRec->getNoWrapFlags(setFlags(Flags, SCEV::FlagNW));
2923 const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRecLoop, Flags);
2934 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
2951 SmallVector<const SCEV *, 4> AddRecOps(AddRec->operands());
2962 SmallVector<const SCEV *, 2> TwoOps = {
2964 AddRecOps[i] = getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1);
2970 Ops[Idx] = getAddRecExpr(AddRecOps, AddRecLoop, SCEV::FlagAnyWrap);
2971 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
2984 const SCEV *
2985 ScalarEvolution::getOrCreateAddExpr(ArrayRef<const SCEV *> Ops,
2986 SCEV::NoWrapFlags Flags) {
2989 for (const SCEV *Op : Ops)
2995 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
3006 const SCEV *
3007 ScalarEvolution::getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops,
3008 const Loop *L, SCEV::NoWrapFlags Flags) {
3011 for (const SCEV *Op : Ops)
3018 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
3030 const SCEV *
3031 ScalarEvolution::getOrCreateMulExpr(ArrayRef<const SCEV *> Ops,
3032 SCEV::NoWrapFlags Flags) {
3035 for (const SCEV *Op : Ops)
3041 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
3084 /// Determine if any of the operands in this SCEV are a constant or if
3085 /// any of the add or multiply expressions in this SCEV contain a constant.
3086 static bool containsConstantInAddMulChain(const SCEV *StartExpr) {
3090 bool follow(const SCEV *S) {
3107 const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
3108 SCEV::NoWrapFlags OrigFlags,
3110 assert(OrigFlags == maskFlags(OrigFlags, SCEV::FlagNUW | SCEV::FlagNSW) &&
3153 auto ComputeFlags = [this, OrigFlags](const ArrayRef<const SCEV *> Ops) {
3161 if (SCEV *S = findExistingSCEVInCache(scMulExpr, Ops)) {
3180 const SCEV *LHS = getMulExpr(LHSC, Add->getOperand(0),
3181 SCEV::FlagAnyWrap, Depth + 1);
3182 const SCEV *RHS = getMulExpr(LHSC, Add->getOperand(1),
3183 SCEV::FlagAnyWrap, Depth + 1);
3184 return getAddExpr(LHS, RHS, SCEV::FlagAnyWrap, Depth + 1);
3191 SmallVector<const SCEV *, 4> NewOps;
3193 for (const SCEV *AddOp : Add->operands()) {
3194 const SCEV *Mul = getMulExpr(Ops[0], AddOp, SCEV::FlagAnyWrap,
3200 return getAddExpr(NewOps, SCEV::FlagAnyWrap, Depth + 1);
3203 SmallVector<const SCEV *, 4> Operands;
3204 for (const SCEV *AddRecOp : AddRec->operands())
3205 Operands.push_back(getMulExpr(Ops[0], AddRecOp, SCEV::FlagAnyWrap,
3212 auto FlagsMask = SCEV::FlagNW;
3213 if (hasFlags(AddRec->getNoWrapFlags(), SCEV::FlagNSW)) {
3217 FlagsMask = setFlags(FlagsMask, SCEV::FlagNSW);
3247 return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
3260 SmallVector<const SCEV *, 8> LIOps;
3272 SmallVector<const SCEV *, 4> NewOps;
3274 const SCEV *Scale = getMulExpr(LIOps, SCEV::FlagAnyWrap, Depth + 1);
3280 SCEV::NoWrapFlags Flags =
3285 SCEV::FlagAnyWrap, Depth + 1));
3287 if (hasFlags(Flags, SCEV::FlagNSW) && !hasFlags(Flags, SCEV::FlagNUW)) {
3292 Flags = clearFlags(Flags, SCEV::FlagNSW);
3296 const SCEV *NewRec = getAddRecExpr(NewOps, AddRec->getLoop(), Flags);
3307 return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
3319 // known at compile time, never SCEV objects.
3342 SmallVector<const SCEV*, 7> AddRecOps;
3345 SmallVector <const SCEV *, 7> SumOps;
3357 const SCEV *CoeffTerm = getConstant(Ty, Coeff);
3358 const SCEV *Term1 = AddRec->getOperand(y-z);
3359 const SCEV *Term2 = OtherAddRec->getOperand(z);
3361 SCEV::FlagAnyWrap, Depth + 1));
3366 AddRecOps.push_back(getAddExpr(SumOps, SCEV::FlagAnyWrap, Depth + 1));
3369 const SCEV *NewAddRec = getAddRecExpr(AddRecOps, AddRec->getLoop(),
3370 SCEV::FlagAnyWrap);
3381 return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
3393 const SCEV *ScalarEvolution::getURemExpr(const SCEV *LHS,
3394 const SCEV *RHS) {
3415 const SCEV *UDiv = getUDivExpr(LHS, RHS);
3416 const SCEV *Mult = getMulExpr(UDiv, RHS, SCEV::FlagNUW);
3417 return getMinusSCEV(LHS, Mult, SCEV::FlagNUW);
3422 const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS,
3423 const SCEV *RHS) {
3434 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
3471 AR->getLoop(), SCEV::FlagAnyWrap)) {
3472 SmallVector<const SCEV *, 4> Operands;
3473 for (const SCEV *Op : AR->operands())
3475 return getAddRecExpr(Operands, AR->getLoop(), SCEV::FlagNW);
3485 AR->getLoop(), SCEV::FlagAnyWrap)) {
3489 const SCEV *NewLHS =
3491 AR->getLoop(), SCEV::FlagNW);
3502 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
3510 SmallVector<const SCEV *, 4> Operands;
3511 for (const SCEV *Op : M->operands())
3516 const SCEV *Op = M->getOperand(i);
3517 const SCEV *Div = getUDivExpr(Op, RHSC);
3519 Operands = SmallVector<const SCEV *, 4>(M->operands());
3542 SmallVector<const SCEV *, 4> Operands;
3543 for (const SCEV *Op : A->operands())
3548 const SCEV *Op = getUDivExpr(A->getOperand(i), RHS);
3568 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
3569 SCEV *S = new (SCEVAllocator) SCEVUDivExpr(ID.Intern(SCEVAllocator),
3591 /// possible. There is no representation for an exact udiv in SCEV IR, but we
3594 const SCEV *ScalarEvolution::getUDivExactExpr(const SCEV *LHS,
3595 const SCEV *RHS) {
3609 SmallVector<const SCEV *, 2> Operands(drop_begin(Mul->operands()));
3622 SmallVector<const SCEV *, 2> Operands;
3636 SmallVector<const SCEV *, 2> Operands;
3648 const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, const SCEV *Step,
3650 SCEV::NoWrapFlags Flags) {
3651 SmallVector<const SCEV *, 4> Operands;
3656 return getAddRecExpr(Operands, L, maskFlags(Flags, SCEV::FlagNW));
3665 const SCEV *
3666 ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
3667 const Loop *L, SCEV::NoWrapFlags Flags) {
3671 for (const SCEV *Op : llvm::drop_begin(Operands)) {
3676 for (const SCEV *Op : Operands)
3683 return getAddRecExpr(Operands, L, SCEV::FlagAnyWrap); // {X,+,0} --> X
3701 SmallVector<const SCEV *, 4> NestedOperands(NestedAR->operands());
3707 Operands, [&](const SCEV *Op) { return isLoopInvariant(Op, L); });
3714 SCEV::NoWrapFlags OuterFlags =
3715 maskFlags(Flags, SCEV::FlagNW | NestedAR->getNoWrapFlags());
3718 AllInvariant = all_of(NestedOperands, [&](const SCEV *Op) {
3727 SCEV::NoWrapFlags InnerFlags =
3728 maskFlags(NestedAR->getNoWrapFlags(), SCEV::FlagNW | Flags);
3742 const SCEV *
3744 const SmallVectorImpl<const SCEV *> &IndexExprs) {
3745 const SCEV *BaseExpr = getSCEV(GEP->getPointerOperand());
3747 // because SCEV::getType() preserves the address space.
3751 // We'd like to propagate flags from the IR to the corresponding SCEV nodes,
3753 // defined scope of the SCEV.
3761 SCEV::NoWrapFlags OffsetWrap = SCEV::FlagAnyWrap;
3763 OffsetWrap = setFlags(OffsetWrap, SCEV::FlagNSW);
3765 OffsetWrap = setFlags(OffsetWrap, SCEV::FlagNUW);
3769 SmallVector<const SCEV *, 4> Offsets;
3770 for (const SCEV *IndexExpr : IndexExprs) {
3776 const SCEV *FieldOffset = getOffsetOfExpr(IntIdxTy, STy, FieldNo);
3792 const SCEV *ElementSize = getSizeOfExpr(IntIdxTy, CurTy);
3797 const SCEV *LocalOffset = getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3807 const SCEV *Offset = getAddExpr(Offsets, OffsetWrap);
3813 SCEV::NoWrapFlags BaseWrap = NUW ? SCEV::FlagNUW : SCEV::FlagAnyWrap;
3820 SCEV *ScalarEvolution::findExistingSCEVInCache(SCEVTypes SCEVType,
3821 ArrayRef<const SCEV *> Ops) {
3824 for (const SCEV *Op : Ops)
3830 const SCEV *ScalarEvolution::getAbsExpr(const SCEV *Op, bool IsNSW) {
3831 SCEV::NoWrapFlags Flags = IsNSW ? SCEV::FlagNSW : SCEV::FlagAnyWrap;
3835 const SCEV *ScalarEvolution::getMinMaxExpr(SCEVTypes Kind,
3836 SmallVectorImpl<const SCEV *> &Ops) {
3858 if (const SCEV *S = findExistingSCEVInCache(Kind, Ops)) {
3878 llvm_unreachable("Unknown SCEV min/max opcode");
3961 for (const SCEV *Op : Ops)
3964 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
3967 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
3969 SCEV *S = new (SCEVAllocator)
3981 std::optional<const SCEV *>> {
3982 using RetVal = std::optional<const SCEV *>;
3988 SmallPtrSet<const SCEV *, 16> SeenOps;
3991 // We can only recurse into the SCEV expression of the same effective type
3992 // as the type of our root SCEV expression.
3996 RetVal visitAnyMinMaxExpr(const SCEV *S) {
4005 SmallVector<const SCEV *> NewOps;
4018 RetVal visit(const SCEV *S) {
4033 bool /*Changed*/ visit(SCEVTypes Kind, ArrayRef<const SCEV *> OrigOps,
4034 SmallVectorImpl<const SCEV *> &NewOps) {
4036 SmallVector<const SCEV *> Ops;
4039 for (const SCEV *Op : OrigOps) {
4124 llvm_unreachable("Unknown SCEV kind!");
4128 // The only way poison may be introduced in a SCEV expression is from a
4130 // not SCEVConstant). Notably, nowrap flags in SCEV nodes can *not*
4133 // Additionally, all SCEV nodes propagate poison from inputs to outputs,
4142 bool follow(const SCEV *S) {
4158 static bool impliesPoison(const SCEV *AssumedPoison, const SCEV *S) {
4167 // is true. Don't bother walking the other SCEV in this case.
4177 // Make sure that no matter which SCEV in PC1.MaybePoison is actually poison,
4185 SmallPtrSetImpl<const Value *> &Result, const SCEV *S) {
4193 const SCEV *S, Instruction *I,
4227 // Disjoint or instructions are interpreted as adds by SCEV. However, we
4235 // because SCEV currently assumes it can't be poison. Remove this special
4254 const SCEV *
4256 SmallVectorImpl<const SCEV *> &Ops) {
4277 if (const SCEV *S = findExistingSCEVInCache(Kind, Ops))
4311 const SCEV *SaturationPoint;
4329 SmallVector<const SCEV *> SeqOps = {Ops[i - 1], Ops[i]};
4348 for (const SCEV *Op : Ops)
4351 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
4355 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
4357 SCEV *S = new (SCEVAllocator)
4365 const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS, const SCEV *RHS) {
4366 SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
4370 const SCEV *ScalarEvolution::getSMaxExpr(SmallVectorImpl<const SCEV *> &Ops) {
4374 const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS, const SCEV *RHS) {
4375 SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
4379 const SCEV *ScalarEvolution::getUMaxExpr(SmallVectorImpl<const SCEV *> &Ops) {
4383 const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS,
4384 const SCEV *RHS) {
4385 SmallVector<const SCEV *, 2> Ops = { LHS, RHS };
4389 const SCEV *ScalarEvolution::getSMinExpr(SmallVectorImpl<const SCEV *> &Ops) {
4393 const SCEV *ScalarEvolution::getUMinExpr(const SCEV *LHS, const SCEV *RHS,
4395 SmallVector<const SCEV *, 2> Ops = { LHS, RHS };
4399 const SCEV *ScalarEvolution::getUMinExpr(SmallVectorImpl<const SCEV *> &Ops,
4405 const SCEV *
4407 const SCEV *Res = getConstant(IntTy, Size.getKnownMinValue());
4413 const SCEV *ScalarEvolution::getSizeOfExpr(Type *IntTy, Type *AllocTy) {
4417 const SCEV *ScalarEvolution::getStoreSizeOfExpr(Type *IntTy, Type *StoreTy) {
4421 const SCEV *ScalarEvolution::getOffsetOfExpr(Type *IntTy,
4433 const SCEV *ScalarEvolution::getUnknown(Value *V) {
4437 // is doing so in order to hide a value from SCEV canonicalization.
4443 if (SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) {
4448 SCEV *S = new (SCEVAllocator) SCEVUnknown(ID.Intern(SCEVAllocator), V, this,
4456 // Basic SCEV Analysis and PHI Idiom Recognition Code
4459 /// Test if values of the given type are analyzable within the SCEV
4478 /// how SCEV will treat the given type, for which isSCEVable must return
4495 bool ScalarEvolution::instructionCouldExistWithOperands(const SCEV *A,
4496 const SCEV *B) {
4509 const SCEV *ScalarEvolution::getCouldNotCompute() {
4513 bool ScalarEvolution::checkValidity(const SCEV *S) const {
4514 bool ContainsNulls = SCEVExprContains(S, [](const SCEV *S) {
4522 bool ScalarEvolution::containsAddRecurrence(const SCEV *S) {
4528 SCEVExprContains(S, [](const SCEV *S) { return isa<SCEVAddRecExpr>(S); });
4535 ArrayRef<Value *> ScalarEvolution::getSCEVValues(const SCEV *S) {
4556 void ScalarEvolution::insertValueToMap(Value *V, const SCEV *S) {
4557 // A recursive query may have already computed the SCEV. It should be
4567 /// Return an existing SCEV if it exists, otherwise analyze the expression and
4569 const SCEV *ScalarEvolution::getSCEV(Value *V) {
4572 if (const SCEV *S = getExistingSCEV(V))
4577 const SCEV *ScalarEvolution::getExistingSCEV(Value *V) {
4582 const SCEV *S = I->second;
4584 "existing SCEV has not been properly invalidated");
4590 /// Return a SCEV corresponding to -V = -1*V
4591 const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V,
4592 SCEV::NoWrapFlags Flags) {
4603 static const SCEV *MatchNotExpr(const SCEV *Expr) {
4617 /// Return a SCEV corresponding to ~V = -1-V
4618 const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) {
4628 SmallVector<const SCEV *, 2> MatchedOperands;
4629 for (const SCEV *Operand : MME->operands()) {
4630 const SCEV *Matched = MatchNotExpr(Operand);
4632 return (const SCEV *)nullptr;
4638 if (const SCEV *Replaced = MatchMinMaxNegation(MME))
4647 const SCEV *ScalarEvolution::removePointerBase(const SCEV *P) {
4652 SmallVector<const SCEV *> Ops{AddRec->operands()};
4656 return getAddRecExpr(Ops, AddRec->getLoop(), SCEV::FlagAnyWrap);
4660 SmallVector<const SCEV *> Ops{Add->operands()};
4661 const SCEV **PtrOp = nullptr;
4662 for (const SCEV *&AddOp : Ops) {
4677 const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
4678 SCEV::NoWrapFlags Flags,
4697 auto AddFlags = SCEV::FlagAnyWrap;
4700 if (hasFlags(Flags, SCEV::FlagNSW)) {
4711 AddFlags = SCEV::FlagNSW;
4722 auto NegFlags = RHSIsNotMinSigned ? SCEV::FlagNSW : SCEV::FlagAnyWrap;
4727 const SCEV *ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V, Type *Ty,
4739 const SCEV *ScalarEvolution::getTruncateOrSignExtend(const SCEV *V, Type *Ty,
4751 const SCEV *
4752 ScalarEvolution::getNoopOrZeroExtend(const SCEV *V, Type *Ty) {
4763 const SCEV *
4764 ScalarEvolution::getNoopOrSignExtend(const SCEV *V, Type *Ty) {
4775 const SCEV *
4776 ScalarEvolution::getNoopOrAnyExtend(const SCEV *V, Type *Ty) {
4787 const SCEV *
4788 ScalarEvolution::getTruncateOrNoop(const SCEV *V, Type *Ty) {
4799 const SCEV *ScalarEvolution::getUMaxFromMismatchedTypes(const SCEV *LHS,
4800 const SCEV *RHS) {
4801 const SCEV *PromotedLHS = LHS;
4802 const SCEV *PromotedRHS = RHS;
4812 const SCEV *ScalarEvolution::getUMinFromMismatchedTypes(const SCEV *LHS,
4813 const SCEV *RHS,
4815 SmallVector<const SCEV *, 2> Ops = { LHS, RHS };
4819 const SCEV *
4820 ScalarEvolution::getUMinFromMismatchedTypes(SmallVectorImpl<const SCEV *> &Ops,
4837 SmallVector<const SCEV *, 2> PromotedOps;
4845 const SCEV *ScalarEvolution::getPointerBase(const SCEV *V) {
4854 const SCEV *PtrOp = nullptr;
4855 for (const SCEV *AddOp : Add->operands()) {
4882 /// Takes SCEV S and Loop L. For each AddRec sub-expression, use its start
4886 /// If SCEV contains non-invariant unknown SCEV rewrite cannot be done.
4889 static const SCEV *rewrite(const SCEV *S, const Loop *L, ScalarEvolution &SE,
4892 const SCEV *Result = Rewriter.visit(S);
4900 const SCEV *visitUnknown(const SCEVUnknown *Expr) {
4906 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
4927 /// Takes SCEV S and Loop L. For each AddRec sub-expression, use its post
4930 /// If SCEV contains non-invariant unknown SCEV rewrite cannot be done.
4933 static const SCEV *rewrite(const SCEV *S, const Loop *L, ScalarEvolution &SE) {
4935 const SCEV *Result = Rewriter.visit(S);
4941 const SCEV *visitUnknown(const SCEVUnknown *Expr) {
4947 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
4970 /// for the condition while building SCEV nodes.
4974 static const SCEV *rewrite(const SCEV *S, const Loop *L,
4993 const SCEV *visitUnknown(const SCEVUnknown *Expr) {
4994 const SCEV *Result = Expr;
5002 std::optional<const SCEV *> Res =
5011 std::optional<const SCEV *> Res = compareWithBackedgeCondition(I);
5027 std::optional<const SCEV *> compareWithBackedgeCondition(Value *IC);
5036 std::optional<const SCEV *>
5050 static const SCEV *rewrite(const SCEV *S, const Loop *L,
5053 const SCEV *Result = Rewriter.visit(S);
5057 const SCEV *visitUnknown(const SCEVUnknown *Expr) {
5064 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
5083 SCEV::NoWrapFlags
5086 return SCEV::FlagAnyWrap;
5090 SCEV::NoWrapFlags Result = SCEV::FlagAnyWrap;
5093 const SCEV *BECount = getConstantMaxBackedgeTakenCount(AR->getLoop());
5100 Result = ScalarEvolution::setFlags(Result, SCEV::FlagNW);
5111 Result = ScalarEvolution::setFlags(Result, SCEV::FlagNSW);
5121 Result = ScalarEvolution::setFlags(Result, SCEV::FlagNUW);
5127 SCEV::NoWrapFlags
5129 SCEV::NoWrapFlags Result = AR->getNoWrapFlags();
5141 const SCEV *Step = AR->getStepRecurrence(*this);
5152 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L);
5157 // guards present in the loop -- SCEV is not great at exploiting
5171 const SCEV *OverflowLimit =
5176 Result = setFlags(Result, SCEV::FlagNSW);
5180 SCEV::NoWrapFlags
5182 SCEV::NoWrapFlags Result = AR->getNoWrapFlags();
5194 const SCEV *Step = AR->getStepRecurrence(*this);
5206 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L);
5211 // guards present in the loop -- SCEV is not great at exploiting
5225 const SCEV *N = getConstant(APInt::getMinValue(BitWidth) -
5229 Result = setFlags(Result, SCEV::FlagNUW);
5278 // creating new SCEV expressions -- our caller knowns tricks to avoid creating
5279 // SCEV expressions when possible, and we should not break that.
5365 /// node whose symbolic (unknown) SCEV is \p SymbolicPHI, which is updated via
5371 /// If the SCEV expression of \p Op conforms with one of the expected patterns
5375 static Type *isSimpleCastedPHI(const SCEV *Op, const SCEVUnknown *SymbolicPHI,
5404 const SCEV *X = Trunc->getOperand();
5420 // Analyze \p SymbolicPHI, a SCEV expression of a phi node, and check if the
5429 // Say the Rewriter is called for the following SCEV:
5437 // the following SCEV:
5473 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5507 const SCEV *BEValue = getSCEV(BEValueV);
5533 SmallVector<const SCEV *, 8> Ops;
5537 const SCEV *Accum = getAddExpr(Ops);
5595 const SCEV *StartVal = getSCEV(StartValueV);
5596 const SCEV *PHISCEV =
5598 getTruncateExpr(Accum, TruncTy), L, SCEV::FlagAnyWrap);
5621 // Construct the extended SCEV: (Ext ix (Trunc iy (Expr) to ix) to iy)
5623 auto getExtendedExpr = [&](const SCEV *Expr,
5624 bool CreateSignExtend) -> const SCEV * {
5626 const SCEV *TruncatedExpr = getTruncateExpr(Expr, TruncTy);
5627 const SCEV *ExtendedExpr =
5638 auto PredIsKnownFalse = [&](const SCEV *Expr,
5639 const SCEV *ExtendedExpr) -> bool {
5644 const SCEV *StartExtended = getExtendedExpr(StartVal, Signed);
5652 const SCEV *AccumExtended = getExtendedExpr(Accum, /*CreateSignExtend=*/true);
5658 auto AppendPredicate = [&](const SCEV *Expr,
5659 const SCEV *ExtendedExpr) -> void {
5675 auto *NewAR = getAddRecExpr(StartVal, Accum, L, SCEV::FlagAnyWrap);
5677 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5679 // Remember the result of the analysis for this SCEV at this locayyytion.
5684 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5694 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5706 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5730 auto areExprsEqual = [&](const SCEV *Expr1, const SCEV *Expr2) -> bool {
5749 const SCEV *ScalarEvolution::createSimpleAffineAddRec(PHINode *PN,
5763 const SCEV *Accum = nullptr;
5772 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
5774 Flags = setFlags(Flags, SCEV::FlagNUW);
5776 Flags = setFlags(Flags, SCEV::FlagNSW);
5778 const SCEV *StartVal = getSCEV(StartValueV);
5779 const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags);
5784 (SCEV::NoWrapFlags)(AR->getNoWrapFlags() |
5801 const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) {
5838 const SCEV *SymbolicName = getUnknown(PN);
5843 const SCEV *BEValue = getSCEV(BEValueV);
5863 SmallVector<const SCEV *, 8> Ops;
5868 const SCEV *Accum = getAddExpr(Ops);
5875 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
5880 Flags = setFlags(Flags, SCEV::FlagNUW);
5882 Flags = setFlags(Flags, SCEV::FlagNSW);
5890 Flags = setFlags(Flags, SCEV::FlagNW);
5896 Flags = setFlags(Flags, SCEV::FlagNUW);
5904 const SCEV *StartVal = getSCEV(StartValueV);
5905 const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags);
5915 (SCEV::NoWrapFlags)(AR->getNoWrapFlags() |
5939 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *this);
5940 const SCEV *Start = SCEVInitRewriter::rewrite(Shifted, L, *this, false);
5943 const SCEV *StartVal = getSCEV(StartValueV);
5955 // Remove the temporary PHI node SCEV that has been inserted while intending
5957 // as it will prevent later (possibly simpler) SCEV expressions to be added
5997 const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(PHINode *PN) {
6029 const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) {
6030 if (const SCEV *S = createAddRecFromPHI(PN))
6036 if (const SCEV *S = createNodeFromSelectLikePHI(PN))
6043 bool SCEVMinMaxExprContains(const SCEV *Root, const SCEV *OperandToFind,
6046 const SCEV *OperandToFind;
6053 // We can only recurse into the SCEV expression of the same effective type
6054 // as the type of our root SCEV expression, and into zero-extensions.
6059 FindClosure(const SCEV *OperandToFind, SCEVTypes RootKind)
6065 bool follow(const SCEV *S) {
6079 std::optional<const SCEV *>
6105 const SCEV *LA = getSCEV(TrueVal);
6106 const SCEV *RA = getSCEV(FalseVal);
6107 const SCEV *LS = getSCEV(LHS);
6108 const SCEV *RS = getSCEV(RHS);
6118 auto CoerceOperand = [&](const SCEV *Op) -> const SCEV * {
6134 const SCEV *LDiff = getMinusSCEV(LA, LS);
6135 const SCEV *RDiff = getMinusSCEV(RA, RS);
6154 const SCEV *X = getNoopOrZeroExtend(getSCEV(LHS), Ty);
6155 const SCEV *TrueValExpr = getSCEV(TrueVal); // C+y
6156 const SCEV *FalseValExpr = getSCEV(FalseVal); // x+y
6157 const SCEV *Y = getMinusSCEV(FalseValExpr, X); // y = (x+y)-x
6158 const SCEV *C = getMinusSCEV(TrueValExpr, Y); // C = (C+y)-y
6168 const SCEV *X = getSCEV(LHS);
6172 const SCEV *FalseValExpr = getSCEV(FalseVal);
6186 static std::optional<const SCEV *>
6187 createNodeForSelectViaUMinSeq(ScalarEvolution *SE, const SCEV *CondExpr,
6188 const SCEV *TrueExpr, const SCEV *FalseExpr) {
6206 const SCEV *X, *C;
6219 static std::optional<const SCEV *>
6231 const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6242 if (std::optional<const SCEV *> S =
6249 const SCEV *ScalarEvolution::createNodeForSelectOrPHI(Value *V, Value *Cond,
6259 if (std::optional<const SCEV *> S =
6270 /// to be analyzed by regular SCEV code.
6271 const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) {
6275 SmallVector<const SCEV *, 4> IndexExprs;
6281 APInt ScalarEvolution::getConstantMultipleImpl(const SCEV *S) {
6326 for (const SCEV *Operand : M->operands().drop_front())
6334 for (const SCEV *Operand : M->operands())
6345 for (const SCEV *Operand : N->operands().drop_front())
6366 llvm_unreachable("Unknown SCEV kind!");
6369 APInt ScalarEvolution::getConstantMultiple(const SCEV *S) {
6380 APInt ScalarEvolution::getNonZeroConstantMultiple(const SCEV *S) {
6385 uint32_t ScalarEvolution::getMinTrailingZeros(const SCEV *S) {
6407 SCEV::NoWrapFlags Flags) {
6453 // the condition here exposes a case where LoopFusion is querying SCEV
6536 ScalarEvolution::getRangeRefIter(const SCEV *S,
6538 DenseMap<const SCEV *, ConstantRange> &Cache =
6541 SmallVector<const SCEV *> WorkList;
6542 SmallPtrSet<const SCEV *, 8> Seen;
6546 auto AddToWorklist = [&WorkList, &Seen, &Cache](const SCEV *Expr) {
6581 const SCEV *P = WorkList[I];
6585 for (const SCEV *Op : P->operands())
6602 for (const SCEV *P : reverse(drop_begin(WorkList))) {
6614 /// Determine the range for a particular SCEV. If SignHint is
6618 const SCEV *S, ScalarEvolution::RangeSignHint SignHint, unsigned Depth) {
6619 DenseMap<const SCEV *, ConstantRange> &Cache =
6627 DenseMap<const SCEV *, ConstantRange>::iterator I = Cache.find(S);
6762 const SCEV *MaxBEScev =
6790 const SCEV *SymbolicMaxBECount =
7021 ConstantRange ScalarEvolution::getRangeForAffineAR(const SCEV *Start,
7022 const SCEV *Step,
7051 const SCEVAddRecExpr *AddRec, const SCEV *MaxBECount, unsigned BitWidth,
7057 const SCEV *Step = AddRec->getStepRecurrence(*this);
7070 const SCEV *RangeWidth = getMinusOne(AddRec->getType());
7071 const SCEV *StepAbs = getUMinExpr(Step, getNegativeSCEV(Step));
7072 const SCEV *MaxItersWithoutWrap = getUDivExpr(RangeWidth, StepAbs);
7081 const SCEV *End = AddRec->evaluateAtIteration(MaxBECount, *this);
7095 const SCEV *Start = applyLoopGuards(AddRec->getStart(), AddRec->getLoop());
7118 ConstantRange ScalarEvolution::getRangeViaFactoring(const SCEV *Start,
7119 const SCEV *Step,
7135 const SCEV *S) {
7177 llvm_unreachable("Unknown SCEV cast type!");
7217 // construct arbitrary general SCEV expressions here. This function is called
7224 const SCEV *TrueStart = this->getConstant(StartPattern.TrueValue);
7225 const SCEV *TrueStep = this->getConstant(StepPattern.TrueValue);
7226 const SCEV *FalseStart = this->getConstant(StartPattern.FalseValue);
7227 const SCEV *FalseStep = this->getConstant(StepPattern.FalseValue);
7237 SCEV::NoWrapFlags ScalarEvolution::getNoWrapFlagsFromUB(const Value *V) {
7238 if (isa<ConstantExpr>(V)) return SCEV::FlagAnyWrap;
7241 // Return early if there are no flags to propagate to the SCEV.
7242 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
7244 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
7246 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW);
7247 if (Flags == SCEV::FlagAnyWrap)
7248 return SCEV::FlagAnyWrap;
7250 return isSCEVExprNeverPoison(BinOp) ? Flags : SCEV::FlagAnyWrap;
7254 ScalarEvolution::getNonTrivialDefiningScopeBound(const SCEV *S) {
7264 ScalarEvolution::getDefiningScopeBound(ArrayRef<const SCEV *> Ops,
7268 SmallSet<const SCEV *, 16> Visited;
7269 SmallVector<const SCEV *> Worklist;
7270 auto pushOp = [&](const SCEV *S) {
7299 ScalarEvolution::getDefiningScopeBound(ArrayRef<const SCEV *> Ops) {
7331 // instructions can map to the same SCEV. If we apply NSW or NUW from I to
7332 // the SCEV, we must guarantee no wrapping for that SCEV also when it is
7333 // derived from other instructions that map to the same SCEV. We cannot make
7335 // upper bound on the defining scope for the SCEV, and prove that I is
7339 SmallVector<const SCEV *> SCEVOps;
7435 const SCEV *ScalarEvolution::createSCEVIter(Value *V) {
7451 const SCEV *CreatedSCEV = nullptr;
7452 // If all operands have been visited already, create the SCEV.
7456 // Otherwise get the operands we need to create SCEV's for before creating
7457 // the SCEV for CurV. If the SCEV for CurV can be constructed trivially,
7465 // Queue CurV for SCEV creation, followed by its's operands which need to
7476 const SCEV *
7503 // can potentially create a single SCEV, to reduce the number of
7525 // requires a SCEV for the LHS.
7663 const SCEV *ScalarEvolution::createSCEV(Value *V) {
7681 const SCEV *LHS;
7682 const SCEV *RHS;
7695 SmallVector<const SCEV *, 4> AddOps;
7703 // If a NUW or NSW flag can be applied to the SCEV for this
7704 // addition, then compute the SCEV for this addition by itself
7710 const SCEV *RHS = getSCEV(BO->RHS);
7711 SCEV::NoWrapFlags Flags = getNoWrapFlagsFromUB(BO->Op);
7712 if (Flags != SCEV::FlagAnyWrap) {
7713 const SCEV *LHS = getSCEV(BO->LHS);
7741 SmallVector<const SCEV *, 4> MulOps;
7749 SCEV::NoWrapFlags Flags = getNoWrapFlagsFromUB(BO->Op);
7750 if (Flags != SCEV::FlagAnyWrap) {
7779 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
7788 // use zext(trunc(x)) as the SCEV expression.
7810 const SCEV *MulCount = getConstant(APInt::getOneBitSet(BitWidth, TZ));
7811 const SCEV *LHS = getSCEV(BO->LHS);
7812 const SCEV *ShiftedLHS = nullptr;
7819 SmallVector<const SCEV*, 4> MulOps;
7870 const SCEV *Z0 = Z->getOperand();
7908 auto Flags = SCEV::FlagAnyWrap;
7911 if ((MulFlags & SCEV::FlagNSW) &&
7912 ((MulFlags & SCEV::FlagNUW) || SA->getValue().ult(BitWidth - 1)))
7913 Flags = (SCEV::NoWrapFlags)(Flags | SCEV::FlagNSW);
7914 if (MulFlags & SCEV::FlagNUW)
7915 Flags = (SCEV::NoWrapFlags)(Flags | SCEV::FlagNUW);
7946 const SCEV *AddTruncateExpr = nullptr;
7948 const SCEV *AddConstant = nullptr;
7960 const SCEV *ShlOp0SCEV = getSCEV(LShift->getOperand(0));
7978 const SCEV *ShlOp0SCEV = getSCEV(L->getOperand(0));
7984 // We can merge the two given cases into a single SCEV statement,
7989 // use sext(trunc(x)) as the SCEV expression.
7991 // 2) When n > m, use sext(mul(trunc(x), 2^(n-m)))) as the SCEV
7999 const SCEV *CompositeExpr =
8032 return getMinusSCEV(V1, V2, SCEV::FlagNSW);
8045 const SCEV *Op = getSCEV(U->getOperand(0));
8047 // But only if effective SCEV (integer) type is wide enough to represent
8049 const SCEV *IntOp = getPtrToIntExpr(Op, DstIntTy);
8110 const SCEV *X = getSCEV(II->getArgOperand(0));
8111 const SCEV *Y = getSCEV(II->getArgOperand(1));
8112 const SCEV *ClampedY = getUMinExpr(X, Y);
8113 return getMinusSCEV(X, ClampedY, SCEV::FlagNUW);
8116 const SCEV *X = getSCEV(II->getArgOperand(0));
8117 const SCEV *Y = getSCEV(II->getArgOperand(1));
8118 const SCEV *ClampedX = getUMinExpr(X, getNotSCEV(Y));
8119 return getAddExpr(ClampedX, Y, SCEV::FlagNUW);
8125 // just eqivalent to the first operand for SCEV purposes.
8143 const SCEV *ScalarEvolution::getTripCountFromExitCount(const SCEV *ExitCount) {
8154 const SCEV *ScalarEvolution::getTripCountFromExitCount(const SCEV *ExitCount,
8235 const SCEV *ExitCount) {
8240 const SCEV *TCExpr = getTripCountFromExitCount(applyLoopGuards(ExitCount, L));
8268 const SCEV *ExitCount = getExitCount(L, ExitingBlock);
8272 const SCEV *ScalarEvolution::getExitCount(const Loop *L,
8286 const SCEV *
8292 const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L,
8305 const SCEV *ScalarEvolution::getPredicatedSymbolicMaxBackedgeTakenCount(
8347 // update the value. The temporary CouldNotCompute value tells SCEV
8361 // existing SCEV values for PHI nodes in this loop since they are only
8367 SmallVector<const SCEV *, 8> ToForget;
8414 SmallVectorImpl<const SCEV *> &ToForget) {
8437 SmallVector<const SCEV *, 16> ToForget;
8439 // Iterate over all the loops and sub-loops to drop SCEV information.
8447 // Drop information about predicated SCEV rewrites for this loop.
8450 std::pair<const SCEV *, const Loop *> Entry = I->first;
8486 SmallVector<const SCEV *, 8> ToForget;
8498 // If SCEV looked through a trivial LCSSA phi node, we might have SCEV's
8501 // AddRecs defined in the loop and invalidate any SCEV's making use of them.
8502 if (const SCEV *S = getExistingSCEV(V)) {
8505 SmallVector<const SCEV *, 8> Roots;
8509 bool follow(const SCEV *S) {
8546 const SCEV *S = getExistingSCEV(V);
8554 SmallVector<const SCEV *, 8> Worklist = {S};
8555 SmallPtrSet<const SCEV *, 8> Seen = {S};
8557 const SCEV *Curr = Worklist.pop_back_val();
8576 const SCEV *
8590 SmallVector<const SCEV *, 2> Ops;
8592 const SCEV *BECount = ENT.ExactNotTaken;
8593 assert(BECount != SE->getCouldNotCompute() && "Bad exit SCEV!");
8615 const SCEV *
8625 const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8634 const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8644 const SCEV *
8659 const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8667 SmallVector<const SCEV *, 4> ExitCounts;
8670 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8701 ScalarEvolution::ExitLimit::ExitLimit(const SCEV *E)
8705 const SCEV *E, const SCEV *ConstantMaxNotTaken,
8706 const SCEV *SymbolicMaxNotTaken, bool MaxOrZero,
8741 const SCEV *E, const SCEV *ConstantMaxNotTaken,
8742 const SCEV *SymbolicMaxNotTaken, bool MaxOrZero,
8751 bool IsComplete, const SCEV *ConstantMax, bool MaxOrZero)
8782 const SCEV *MustExitMaxBECount = nullptr;
8783 const SCEV *MayExitMaxBECount = nullptr;
8853 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
8983 // Try again, but use SCEV predicates this time.
9061 const SCEV *BECount = getCouldNotCompute();
9062 const SCEV *ConstantMaxBECount = getCouldNotCompute();
9063 const SCEV *SymbolicMaxBECount = getCouldNotCompute();
9121 const SCEV *LHS = getSCEV(ExitCond->getOperand(0));
9122 const SCEV *RHS = getSCEV(ExitCond->getOperand(1));
9139 const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
9168 const SCEV *Ret = AddRec->getNumIterationsInRange(CompRange, *this);
9188 Flags = setFlags(Flags, SCEV::FlagNW);
9189 SmallVector<const SCEV*> Operands{AR->operands()};
9304 const SCEV *LHS = getSCEVAtScope(Switch->getCondition(), L);
9305 const SCEV *RHS = getConstant(Switch->findCaseDest(ExitingBlock));
9318 const SCEV *InVal = SE.getConstant(C);
9319 const SCEV *Val = AddRec->evaluateAtIteration(InVal, SE);
9321 "Evaluation of SCEV at constant didn't fold correctly?");
9460 const SCEV *UpperBound =
9710 const SCEV *ScalarEvolution::computeExitCountExhaustively(const Loop *L,
9777 const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) {
9778 SmallVector<std::pair<const Loop *, const SCEV *>, 2> &Values =
9788 const SCEV *C = computeSCEVAtScope(V, L);
9802 /// Returns NULL if the SCEV isn't representable as a Constant.
9803 static Constant *BuildConstantFromSCEV(const SCEV *V) {
9829 for (const SCEV *Op : SA->operands()) {
9861 llvm_unreachable("Unknown SCEV kind!");
9864 const SCEV *
9865 ScalarEvolution::getWithOperands(const SCEV *S,
9866 SmallVectorImpl<const SCEV *> &NewOps) {
9897 llvm_unreachable("Unknown SCEV kind!");
9900 const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) {
9913 const SCEV *OpAtScope = getSCEVAtScope(AddRec->getOperand(i), L);
9919 SmallVector<const SCEV *, 8> NewOps;
9926 const SCEV *FoldedRec = getAddRecExpr(
9927 NewOps, AddRec->getLoop(), AddRec->getNoWrapFlags(SCEV::FlagNW));
9942 const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
9964 ArrayRef<const SCEV *> Ops = V->operands();
9968 const SCEV *OpAtScope = getSCEVAtScope(Ops[i], L);
9972 SmallVector<const SCEV *, 8> NewOps;
10005 const SCEV *BackedgeTakenCount = getBackedgeTakenCount(CurrLoop);
10049 // into a SCEV. Check to see if it's possible to symbolically evaluate
10070 const SCEV *OrigV = getSCEV(Op);
10071 const SCEV *OpV = getSCEVAtScope(OrigV, L);
10096 llvm_unreachable("Unknown SCEV type!");
10099 const SCEV *ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) {
10103 const SCEV *ScalarEvolution::stripInjectiveFunctions(const SCEV *S) const {
10119 static const SCEV *SolveLinEquationWithOverflow(const APInt &A, const SCEV *B,
10152 const SCEV *D = SE.getConstant(APInt::getOneBitSet(BW, Mult2));
10429 ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(const SCEV *V,
10452 // iterations of this loop, where X is the SCEV expression found by the
10488 const SCEV *Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
10489 const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop());
10497 const SCEV *StepWLG = applyLoopGuards(Step, Guards);
10508 const SCEV *Distance = CountDown ? Start : getNegativeSCEV(Start);
10524 const SCEV *Zero = getZero(Distance->getType());
10525 const SCEV *One = getOne(Distance->getType());
10526 const SCEV *DistancePlusOne = getAddExpr(Distance, One);
10551 const SCEV *Exact =
10553 const SCEV *ConstantMax = getCouldNotCompute();
10559 const SCEV *SymbolicMax =
10567 const SCEV *E = SolveLinEquationWithOverflow(StepC->getAPInt(),
10570 const SCEV *M = E;
10580 ScalarEvolution::howFarToNonZero(const SCEV *V, const Loop *L) {
10616 /// SCEV structural equivalence is usually sufficient for testing whether two
10620 static bool HasSameValue(const SCEV *A, const SCEV *B) {
10621 // Quick check to see if they are the same SCEV.
10644 static bool MatchBinarySub(const SCEV *S, const SCEV *&LHS, const SCEV *&RHS) {
10664 const SCEV *&LHS, const SCEV *&RHS,
10787 SCEV::FlagNSW);
10792 SCEV::FlagNSW);
10800 SCEV::FlagNSW);
10805 SCEV::FlagNSW);
10813 SCEV::FlagNUW);
10829 SCEV::FlagNUW);
10848 bool ScalarEvolution::isKnownNegative(const SCEV *S) {
10852 bool ScalarEvolution::isKnownPositive(const SCEV *S) {
10856 bool ScalarEvolution::isKnownNonNegative(const SCEV *S) {
10860 bool ScalarEvolution::isKnownNonPositive(const SCEV *S) {
10864 bool ScalarEvolution::isKnownNonZero(const SCEV *S) {
10872 std::pair<const SCEV *, const SCEV *>
10873 ScalarEvolution::SplitIntoInitAndPostInc(const Loop *L, const SCEV *S) {
10874 // Compute SCEV on entry of loop L.
10875 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *this);
10878 // Compute post increment SCEV for loop L.
10879 const SCEV *PostInc = SCEVPostIncRewriter::rewrite(S, L, *this);
10885 const SCEV *LHS, const SCEV *RHS) {
10910 // if LHS contains unknown non-invariant SCEV then bail out.
10916 // if RHS contains unknown non-invariant SCEV then bail out.
10920 // It is possible that init SCEV contains an invariant load but it does
10935 const SCEV *LHS, const SCEV *RHS) {
10950 const SCEV *LHS,
10951 const SCEV *RHS) {
10960 const SCEV *LHS, const SCEV *RHS,
10968 ScalarEvolution::evaluatePredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS,
10969 const SCEV *RHS, const Instruction *CtxI) {
10985 const SCEV *RHS) {
11021 // where SCEV can prove X >= 0 but not prove X > 0, so it is helpful to be
11043 const SCEV *Step = LHS->getStepRecurrence(*this);
11056 const SCEV *LHS, const SCEV *RHS,
11142 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L,
11143 const Instruction *CtxI, const SCEV *MaxIter) {
11162 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L,
11163 const Instruction *CtxI, const SCEV *MaxIter) {
11190 const SCEV *Step = AR->getStepRecurrence(*this);
11203 const SCEV *Last = AR->evaluateAtIteration(MaxIter, *this);
11216 const SCEV *Start = AR->getStart();
11225 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS) {
11267 const SCEV *LHS,
11268 const SCEV *RHS) {
11273 auto MatchBinaryAddToConst = [this](const SCEV *X, const SCEV *Y,
11275 SCEV::NoWrapFlags ExpectedFlags) {
11276 const SCEV *XNonConstOp, *XConstOp;
11277 const SCEV *YNonConstOp, *YConstOp;
11278 SCEV::NoWrapFlags XFlagsPresent;
11279 SCEV::NoWrapFlags YFlagsPresent;
11321 if (MatchBinaryAddToConst(LHS, RHS, C1, C2, SCEV::FlagNSW) && C1.sle(C2))
11331 if (MatchBinaryAddToConst(LHS, RHS, C1, C2, SCEV::FlagNSW) && C1.slt(C2))
11341 if (MatchBinaryAddToConst(LHS, RHS, C1, C2, SCEV::FlagNUW) && C1.ule(C2))
11351 if (MatchBinaryAddToConst(LHS, RHS, C1, C2, SCEV::FlagNUW) && C1.ult(C2))
11360 const SCEV *LHS,
11361 const SCEV *RHS) {
11383 const SCEV *LHS, const SCEV *RHS) {
11404 const SCEV *LHS, const SCEV *RHS) {
11440 const SCEV *LatchBECount = BETakenInfo.getExact(Latch, this);
11446 auto NoWrapFlags = SCEV::NoWrapFlags(SCEV::FlagNUW | SCEV::FlagNW);
11447 const SCEV *LoopCounter =
11509 const SCEV *LHS,
11510 const SCEV *RHS) {
11609 const SCEV *LHS,
11610 const SCEV *RHS) {
11628 bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS,
11629 const SCEV *RHS,
11666 const SCEV *FoundLHS = getSCEV(ICI->getOperand(0));
11667 const SCEV *FoundRHS = getSCEV(ICI->getOperand(1));
11672 bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS,
11673 const SCEV *RHS,
11675 const SCEV *FoundLHS, const SCEV *FoundRHS,
11688 const SCEV *MaxValue = getZeroExtendExpr(
11694 const SCEV *TruncFoundLHS = getTruncateExpr(FoundLHS, NarrowType);
11695 const SCEV *TruncFoundRHS = getTruncateExpr(FoundRHS, NarrowType);
11728 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
11729 ICmpInst::Predicate FoundPred, const SCEV *FoundLHS, const SCEV *FoundRHS,
11808 const SCEV *CanonicalLHS = LHS, *CanonicalRHS = RHS,
11842 const SCEV *V = nullptr;
11931 bool ScalarEvolution::splitBinaryAdd(const SCEV *Expr,
11932 const SCEV *&L, const SCEV *&R,
11933 SCEV::NoWrapFlags &Flags) {
11945 ScalarEvolution::computeConstantDifference(const SCEV *More, const SCEV *Less) {
11980 SCEV::NoWrapFlags Flags;
11981 const SCEV *LLess = nullptr, *RLess = nullptr;
11982 const SCEV *LMore = nullptr, *RMore = nullptr;
12004 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
12005 const SCEV *FoundLHS, const SCEV *FoundRHS, const Instruction *CtxI) {
12049 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
12050 const SCEV *FoundLHS, const SCEV *FoundRHS) {
12062 // We'd like to let SCEV reason about control dependencies, so we constrain
12126 const SCEV *LHS, const SCEV *RHS,
12127 const SCEV *FoundLHS,
12128 const SCEV *FoundRHS, unsigned Depth) {
12182 auto ProvedEasily = [&](const SCEV *S1, const SCEV *S2) {
12194 const SCEV *L = getSCEV(LPhi->getIncomingValueForBlock(IncBB));
12195 const SCEV *R = getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12210 const SCEV *L1 = getSCEV(LPhi->getIncomingValueForBlock(Predecessor));
12215 const SCEV *L2 = getSCEV(LPhi->getIncomingValueForBlock(Latch));
12227 const SCEV *L = getSCEV(LPhi->getIncomingValueForBlock(IncBB));
12240 const SCEV *LHS,
12241 const SCEV *RHS,
12242 const SCEV *FoundLHS,
12243 const SCEV *FoundRHS) {
12282 const SCEV *LHS, const SCEV *RHS,
12283 const SCEV *FoundLHS,
12284 const SCEV *FoundRHS,
12305 static bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr,
12306 const SCEV *Candidate) {
12316 const SCEV *LHS, const SCEV *RHS) {
12338 SCEV::NoWrapFlags NW = ICmpInst::isSigned(Pred) ?
12339 SCEV::FlagNSW : SCEV::FlagNUW;
12350 const SCEV *LHS, const SCEV *RHS) {
12381 const SCEV *LHS, const SCEV *RHS,
12382 const SCEV *FoundLHS,
12383 const SCEV *FoundRHS,
12411 const SCEV *MinusOne = getMinusOne(LHS->getType());
12422 auto GetOpFromSExt = [&](const SCEV *S) {
12437 auto IsSGTViaContext = [&](const SCEV *S1, const SCEV *S2) {
12444 // We want to avoid creation of any new non-constant SCEV. Since we are
12461 auto IsSumGreaterThanRHS = [&](const SCEV *S1, const SCEV *S2) {
12478 // derivative expressions. In general case, creating a SCEV for it may
12490 // then a SCEV for the numerator already exists and matches with FoundLHS.
12549 const SCEV *LHS, const SCEV *RHS) {
12582 const SCEV *LHS, const SCEV *RHS) {
12592 const SCEV *LHS, const SCEV *RHS,
12593 const SCEV *FoundLHS,
12594 const SCEV *FoundRHS) {
12636 const SCEV *LHS,
12637 const SCEV *RHS,
12639 const SCEV *FoundLHS,
12640 const SCEV *FoundRHS) {
12668 bool ScalarEvolution::canIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride,
12673 const SCEV *One = getOne(Stride->getType());
12692 bool ScalarEvolution::canIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride,
12696 const SCEV *One = getOne(Stride->getType());
12715 const SCEV *ScalarEvolution::getUDivCeilSCEV(const SCEV *N, const SCEV *D) {
12719 const SCEV *MinNOne = getUMinExpr(N, getOne(N->getType()));
12720 const SCEV *NMinusOne = getMinusSCEV(N, MinNOne);
12724 const SCEV *ScalarEvolution::computeMaxBECountForLT(const SCEV *Start,
12725 const SCEV *Stride,
12726 const SCEV *End,
12774 ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,
12842 if (!hasFlags(Flags, SCEV::FlagNUW) && canProveNUW())
12843 Flags = setFlags(Flags, SCEV::FlagNUW);
12849 const SCEV *Step = AR->getStepRecurrence(*this);
12863 // iterations of this loop, where X is the SCEV expression found by the
12883 auto WrapType = IsSigned ? SCEV::FlagNSW : SCEV::FlagNUW;
12887 const SCEV *Stride = IV->getStepRecurrence(*this);
12987 const SCEV *Start = IV->getStart();
12993 const SCEV *OrigStart = Start;
12994 const SCEV *OrigRHS = RHS;
13006 const SCEV *End = nullptr, *BECount = nullptr,
13024 const SCEV *RHSStart = RHSAddRec->getStart();
13025 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*this);
13037 const SCEV *Denominator = getMinusSCEV(Stride, RHSStride);
13043 const SCEV *Delta = getMinusSCEV(End, Start);
13056 const SCEV *MaxBECount = computeMaxBECountForLT(
13092 const SCEV *MinusOne = getMinusOne(Stride->getType());
13093 const SCEV *Numerator =
13101 const SCEV *GuardedRHS = applyLoopGuards(OrigRHS, L);
13102 const SCEV *GuardedStart = applyLoopGuards(OrigStart, L);
13133 // We convert it to the following to make it more convenient for SCEV:
13155 const SCEV *One = getOne(Stride->getType());
13217 const SCEV *Delta = getMinusSCEV(End, Start);
13230 const SCEV *ConstantMaxBECount;
13250 const SCEV *SymbolicMaxBECount =
13257 const SCEV *LHS, const SCEV *RHS, const Loop *L, bool IsSigned,
13267 // iterations of this loop, where X is the SCEV expression found by the
13275 auto WrapType = IsSigned ? SCEV::FlagNSW : SCEV::FlagNUW;
13279 const SCEV *Stride = getNegativeSCEV(IV->getStepRecurrence(*this));
13293 const SCEV *Start = IV->getStart();
13294 const SCEV *End = RHS;
13319 const SCEV *One = getOne(Stride->getType());
13320 const SCEV *BECount = getUDivExpr(
13340 const SCEV *ConstantMaxBECount =
13348 const SCEV *SymbolicMaxBECount =
13355 const SCEV *SCEVAddRecExpr::getNumIterationsInRange(const ConstantRange &Range,
13363 SmallVector<const SCEV *, 4> Operands(operands());
13365 const SCEV *Shifted = SE.getAddRecExpr(Operands, getLoop(),
13376 if (any_of(operands(), [](const SCEV *Op) { return !isa<SCEVConstant>(Op); }))
13431 // AddRec because SCEV does not have a fixed point where it stops
13435 SmallVector<const SCEV *, 3> Ops;
13444 const SCEV *Last = getOperand(getNumOperands() - 1);
13448 SCEV::FlagAnyWrap));
13452 bool ScalarEvolution::containsUndefs(const SCEV *S) const {
13453 return SCEVExprContains(S, [](const SCEV *S) {
13461 bool ScalarEvolution::containsErasedValue(const SCEV *S) const {
13462 return SCEVExprContains(S, [](const SCEV *S) {
13470 const SCEV *ScalarEvolution::getElementSize(Instruction *Inst) {
13591 /// When printing a top-level SCEV for trip counts, it's helpful to include
13593 static void PrintSCEVWithTypeHint(raw_ostream &OS, const SCEV* S) {
13745 // out SCEV values of all instructions that are interesting. Doing
13746 // this potentially causes it to create new SCEV objects though,
13760 const SCEV *SV = SE.getSCEV(&I);
13771 const SCEV *AtUse = SE.getSCEVAtScope(SV, L);
13785 const SCEV *ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop());
13834 ScalarEvolution::getLoopDisposition(const SCEV *S, const Loop *L) {
13853 ScalarEvolution::computeLoopDisposition(const SCEV *S, const Loop *L) {
13921 llvm_unreachable("Unknown SCEV kind!");
13924 bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) {
13928 bool ScalarEvolution::hasComputableLoopEvolution(const SCEV *S, const Loop *L) {
13933 ScalarEvolution::getBlockDisposition(const SCEV *S, const BasicBlock *BB) {
13952 ScalarEvolution::computeBlockDisposition(const SCEV *S, const BasicBlock *BB) {
13982 for (const SCEV *NAryOp : S->operands()) {
14004 llvm_unreachable("Unknown SCEV kind!");
14007 bool ScalarEvolution::dominates(const SCEV *S, const BasicBlock *BB) {
14011 bool ScalarEvolution::properlyDominates(const SCEV *S, const BasicBlock *BB) {
14015 bool ScalarEvolution::hasOperand(const SCEV *S, const SCEV *Op) const {
14016 return SCEVExprContains(S, [&](const SCEV *Expr) { return Expr == Op; });
14026 for (const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14038 void ScalarEvolution::forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs) {
14039 SmallPtrSet<const SCEV *, 8> ToForget(SCEVs.begin(), SCEVs.end());
14040 SmallVector<const SCEV *, 8> Worklist(ToForget.begin(), ToForget.end());
14043 const SCEV *Curr = Worklist.pop_back_val();
14056 std::pair<const SCEV *, const Loop *> Entry = I->first;
14064 void ScalarEvolution::forgetMemoizedResultsImpl(const SCEV *S) {
14120 ScalarEvolution::getUsedLoops(const SCEV *S,
14126 bool follow(const SCEV *S) {
14158 const SCEV *L = getSCEV(Cmp->getOperand(0));
14159 const SCEV *R = getSCEV(Cmp->getOperand(1));
14182 // Map's SCEV expressions from one ScalarEvolution "universe" to another.
14186 const SCEV *visitConstant(const SCEVConstant *Constant) {
14190 const SCEV *visitUnknown(const SCEVUnknown *Expr) {
14194 const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
14203 auto GetDelta = [&](const SCEV *Old, const SCEV *New) -> const SCEV * {
14205 // SCEV treats "undef" as an unknown but consistent value (i.e. it does
14209 // result is "undef", but SCEV thinks the value increased by 1.
14214 const SCEV *Delta = SE2.getMinusSCEV(Old, New);
14231 // results of subsequent SCEV uses.
14244 // computable or vice-versa *should have* invalidated SCEV. However, we
14257 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14277 // Check for SCEV expressions referencing invalid/deleted loops.
14295 const SCEV *OldSCEV = SCM.visit(KV.second);
14296 const SCEV *NewSCEV = SE2.getSCEV(I);
14297 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14299 dbgs() << "SCEV for value " << *I << " changed!\n"
14324 // Verify integrity of SCEV users.
14341 const SCEV *Value = ValueAndVec.first;
14344 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
14358 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14361 const SCEV *Value = LoopAndValue.second;
14379 for (const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14554 const SCEVPredicate *ScalarEvolution::getEqualPredicate(const SCEV *LHS,
14555 const SCEV *RHS) {
14561 const SCEV *LHS, const SCEV *RHS) {
14601 /// Rewrites \p S in the context of a loop L and the SCEV predication
14604 /// If \p Pred is non-null, the SCEV expression is rewritten to respect the
14609 static const SCEV *rewrite(const SCEV *S, const Loop *L, ScalarEvolution &SE,
14616 const SCEV *visitUnknown(const SCEVUnknown *Expr) {
14633 const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
14634 const SCEV *Operand = visit(Expr->getOperand());
14639 const SCEV *Step = AR->getStepRecurrence(SE);
14649 const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
14650 const SCEV *Operand = visit(Expr->getOperand());
14655 const SCEV *Step = AR->getStepRecurrence(SE);
14692 const SCEV *convertToAddRecWithPreds(const SCEVUnknown *Expr) {
14696 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
14719 const SCEV *
14720 ScalarEvolution::rewriteUsingPredicate(const SCEV *S, const Loop *L,
14726 const SCEV *S, const Loop *L,
14735 // Since the transformation was successful, we can now transfer the SCEV
14743 /// SCEV predicates
14750 const SCEV *LHS, const SCEV *RHS)
14753 assert(LHS != RHS && "LHS and RHS are the same SCEV");
14793 SCEV::NoWrapFlags ScevFlags = AR->getNoWrapFlags();
14796 if (ScalarEvolution::setFlags(ScevFlags, SCEV::FlagNSW) == ScevFlags)
14815 SCEV::NoWrapFlags StaticFlags = AR->getNoWrapFlags();
14818 if (ScalarEvolution::setFlags(StaticFlags, SCEV::FlagNSW) == StaticFlags)
14821 if (ScalarEvolution::setFlags(StaticFlags, SCEV::FlagNUW) == StaticFlags) {
14822 // If the increment is positive, the SCEV NUW flag will also imply the
14877 void ScalarEvolution::registerUser(const SCEV *User,
14878 ArrayRef<const SCEV *> Ops) {
14887 const SCEV *PredicatedScalarEvolution::getSCEV(Value *V) {
14888 const SCEV *Expr = SE.getSCEV(V);
14900 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
14906 const SCEV *PredicatedScalarEvolution::getBackedgeTakenCount() {
14916 const SCEV *PredicatedScalarEvolution::getSymbolicMaxBackedgeTakenCount() {
14946 const SCEV *Rewritten = II.second.second;
14954 const SCEV *Expr = getSCEV(V);
14970 const SCEV *Expr = getSCEV(V);
14985 const SCEV *Expr = this->getSCEV(V);
15036 bool ScalarEvolution::matchURem(const SCEV *Expr, const SCEV *&LHS,
15037 const SCEV *&RHS) {
15062 const SCEV *A = Add->getOperand(1);
15068 const auto MatchURemWithDivisor = [&](const SCEV *B) {
15095 SmallVector<const SCEV *> ExprsToRewrite;
15096 auto CollectCondition = [&](ICmpInst::Predicate Predicate, const SCEV *LHS,
15097 const SCEV *RHS,
15098 DenseMap<const SCEV *, const SCEV *>
15101 // replacement SCEV which isn't directly implied by the structure of that
15102 // SCEV. In particular, using contextual facts to imply flags is *NOT*
15134 const SCEV *RewrittenLHS = I != RewriteMap.end() ? I->second : LHSUnknown;
15145 // Return true if \p Expr is a MinMax SCEV expression with a non-negative
15146 // constant operand. If so, return in \p SCTy the SCEV type and in \p RHS
15149 [&](const SCEV *Expr, SCEVTypes &SCTy, const SCEV *&LHS,
15150 const SCEV *&RHS) {
15168 auto GetNonNegExprAndPosDivisor = [&](const SCEV *Expr, const SCEV *Divisor,
15179 // Return a new SCEV that modifies \p Expr to the closest number divides by
15182 auto GetNextSCEVDividesByDivisor = [&](const SCEV *Expr,
15183 const SCEV *Divisor) {
15190 // return the SCEV: Expr + Divisor - Expr % Divisor
15195 // Return a new SCEV that modifies \p Expr to the closest number divides by
15198 auto GetPreviousSCEVDividesByDivisor = [&](const SCEV *Expr,
15199 const SCEV *Divisor) {
15205 // return the SCEV: Expr - Expr % Divisor
15212 std::function<const SCEV *(const SCEV *, const SCEV *)>
15213 ApplyDivisibiltyOnMinMaxExpr = [&](const SCEV *MinMaxExpr,
15214 const SCEV *Divisor) {
15215 const SCEV *MinMaxLHS = nullptr, *MinMaxRHS = nullptr;
15227 SmallVector<const SCEV *> Ops = {
15233 // SCEV %v which we can rewrite %v to express explicitly.
15239 const SCEV *URemLHS = nullptr;
15240 const SCEV *URemRHS = nullptr;
15244 const SCEV *RewrittenLHS =
15270 auto AddRewrite = [&](const SCEV *From, const SCEV *FromRewritten,
15271 const SCEV *To) {
15280 auto GetMaybeRewritten = [&](const SCEV *S) {
15285 // Check for the SCEV expression (A /u B) * B while B is a constant, inside
15287 // be a composition of Min/Max SCEVs. Return whether the SCEV expression (A
15290 // (A /u 8) * 8 matched the pattern, and return the constant SCEV 8 in \p
15292 std::function<bool(const SCEV *, const SCEV *&)> HasDivisibiltyInfo =
15293 [&](const SCEV *Expr, const SCEV *&DividesBy) {
15314 std::function<bool(const SCEV *, const SCEV *&)> IsKnownToDivideBy =
15315 [&](const SCEV *Expr, const SCEV *DividesBy) {
15324 const SCEV *RewrittenLHS = GetMaybeRewritten(LHS);
15325 const SCEV *DividesBy = nullptr;
15339 // We cannot express strict predicates in SCEV, so instead we replace them
15342 const SCEV *One = SE.getOne(RHS->getType());
15371 SmallVector<const SCEV *, 16> Worklist(1, LHS);
15372 SmallPtrSet<const SCEV *, 16> Visited;
15379 const SCEV *From = Worklist.pop_back_val();
15384 const SCEV *FromRewritten = GetMaybeRewritten(From);
15385 const SCEV *To = nullptr;
15419 const SCEV *OneAlignedUp =
15510 for (const SCEV *Expr : ExprsToRewrite) {
15511 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
15522 for (const SCEV *Expr : ExprsToRewrite) {
15523 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
15531 const SCEV *ScalarEvolution::LoopGuards::rewrite(const SCEV *Expr) const {
15532 /// A rewriter to replace SCEV expressions in Map with the corresponding entry
15537 const DenseMap<const SCEV *, const SCEV *> ⤅
15539 SCEV::NoWrapFlags FlagMask = SCEV::FlagAnyWrap;
15546 FlagMask = ScalarEvolution::setFlags(FlagMask, SCEV::FlagNUW);
15548 FlagMask = ScalarEvolution::setFlags(FlagMask, SCEV::FlagNSW);
15551 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { return Expr; }
15553 const SCEV *visitUnknown(const SCEVUnknown *Expr) {
15560 const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
15566 const SCEV *Op = Expr->getOperand(0);
15584 const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
15592 const SCEV *visitUMinExpr(const SCEVUMinExpr *Expr) {
15599 const SCEV *visitSMinExpr(const SCEVSMinExpr *Expr) {
15606 const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
15607 SmallVector<const SCEV *, 2> Operands;
15622 const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
15623 SmallVector<const SCEV *, 2> Operands;
15646 const SCEV *ScalarEvolution::applyLoopGuards(const SCEV *Expr, const Loop *L) {
15650 const SCEV *ScalarEvolution::applyLoopGuards(const SCEV *Expr,