Lines Matching refs: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);
513 const SCEV *op, Type *ty)
514 : SCEV(ID, SCEVTy, computeExpressionSize(op)), Op(op), Ty(ty) {}
516 SCEVPtrToIntExpr::SCEVPtrToIntExpr(const FoldingSetNodeIDRef ID, const SCEV *Op,
524 SCEVTypes SCEVTy, const SCEV *op,
528 SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeIDRef ID, const SCEV *op,
536 const SCEV *op, Type *ty)
543 const SCEV *op, Type *ty)
572 // SCEV Utilities
577 /// operands in SCEV expressions. \p EqCache is a set of pairs of values that
674 CompareSCEVComplexity(EquivalenceClasses<const SCEV *> &EqCacheSCEV,
676 const LoopInfo *const LI, const SCEV *LHS,
677 const SCEV *RHS, DominatorTree &DT, unsigned Depth = 0) {
731 // There is always a dominance between two recs that are used by one SCEV,
741 "No dominance between recurrences used by one SCEV?");
760 ArrayRef<const SCEV *> LOps = LHS->operands();
761 ArrayRef<const SCEV *> ROps = RHS->operands();
781 llvm_unreachable("Unknown SCEV kind!");
784 /// Given a list of SCEV objects, order them by their complexity, and group
791 /// this to depend on where the addresses of various SCEV objects happened to
793 static void GroupByComplexity(SmallVectorImpl<const SCEV *> &Ops,
797 EquivalenceClasses<const SCEV *> EqCacheSCEV;
801 auto IsLessComplex = [&](const SCEV *LHS, const SCEV *RHS) {
809 const SCEV *&LHS = Ops[0], *&RHS = Ops[1];
816 llvm::stable_sort(Ops, [&](const SCEV *LHS, const SCEV *RHS) {
825 const SCEV *S = Ops[i];
841 /// Returns true if \p Ops contains a huge SCEV (the subtree of S contains at
843 static bool hasHugeExpression(ArrayRef<const SCEV *> Ops) {
844 return any_of(Ops, [](const SCEV *S) {
850 // Simple SCEV method implementations
854 static const SCEV *BinomialCoefficient(const SCEV *It, unsigned K,
948 const SCEV *Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy);
950 const SCEV *S = SE.getMinusSCEV(It, SE.getConstant(It->getType(), i));
956 const SCEV *DivResult = SE.getUDivExpr(Dividend, SE.getConstant(DivFactor));
972 const SCEV *SCEVAddRecExpr::evaluateAtIteration(const SCEV *It,
977 const SCEV *
978 SCEVAddRecExpr::evaluateAtIteration(ArrayRef<const SCEV *> Operands,
979 const SCEV *It, ScalarEvolution &SE) {
981 const SCEV *Result = Operands[0];
986 const SCEV *Coeff = BinomialCoefficient(It, i, SE, Result->getType());
996 // SCEV Expression folder implementations
999 const SCEV *ScalarEvolution::getLosslessPtrToIntExpr(const SCEV *Op,
1004 // We could be called with an integer-typed operands during SCEV rewrites.
1009 // What would be an ID for such a SCEV cast expression?
1017 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
1027 // We can only trivially model ptrtoint if SCEV's effective (integer) type
1029 // We could theoretically teach SCEV to truncate wider pointers, but
1038 // is a null pointer, don't create a ptr2int SCEV expression (that will be
1047 SCEV *S = new (SCEVAllocator)
1074 static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE) {
1079 const SCEV *visit(const SCEV *S) {
1088 const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
1089 SmallVector<const SCEV *, 2> Operands;
1098 const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
1099 SmallVector<const SCEV *, 2> Operands;
1108 const SCEV *visitUnknown(const SCEVUnknown *Expr) {
1116 const SCEV *IntOp = SCEVPtrToIntSinkingRewriter::rewrite(Op, *this);
1123 const SCEV *ScalarEvolution::getPtrToIntExpr(const SCEV *Op, Type *Ty) {
1126 const SCEV *IntOp = getLosslessPtrToIntExpr(Op);
1133 const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, Type *Ty,
1147 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1167 SCEV *S =
1180 SmallVector<const SCEV *, 4> Operands;
1184 const SCEV *S = getTruncateExpr(CommOp->getOperand(i), Ty, Depth + 1);
1195 llvm_unreachable("Unexpected SCEV type for Op.");
1200 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
1206 SmallVector<const SCEV *, 4> Operands;
1207 for (const SCEV *Op : AddRec->operands())
1209 return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap);
1220 SCEV *S = new (SCEVAllocator) SCEVTruncateExpr(ID.Intern(SCEVAllocator),
1230 static const SCEV *getSignedOverflowLimitForStep(const SCEV *Step,
1250 static const SCEV *getUnsignedOverflowLimitForStep(const SCEV *Step,
1263 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(const SCEV *, Type *,
1271 // static const SCEV::NoWrapFlags WrapType;
1275 // static const SCEV *getOverflowLimitForStep(const SCEV *Step,
1282 static const SCEV::NoWrapFlags WrapType = SCEV::FlagNSW;
1286 static const SCEV *getOverflowLimitForStep(const SCEV *Step,
1298 static const SCEV::NoWrapFlags WrapType = SCEV::FlagNUW;
1302 static const SCEV *getOverflowLimitForStep(const SCEV *Step,
1322 static const SCEV *getPreStartForExtend(const SCEVAddRecExpr *AR, Type *Ty,
1328 const SCEV *Start = AR->getStart();
1329 const SCEV *Step = AR->getStepRecurrence(*SE);
1336 // Create an AddExpr for "PreStart" after subtracting Step. Full SCEV
1340 SmallVector<const SCEV *, 4> DiffOps(SA->operands());
1350 // Try to prove `WrapType` (SCEV::FlagNSW or SCEV::FlagNUW) on `PreStart` +
1355 ScalarEvolution::maskFlags(SA->getNoWrapFlags(), SCEV::FlagNUW);
1356 const SCEV *PreStart = SE->getAddExpr(DiffOps, PreStartFlags);
1358 SE->getAddRecExpr(PreStart, Step, L, SCEV::FlagAnyWrap));
1364 const SCEV *BECount = SE->getBackedgeTakenCount(L);
1372 const SCEV *OperandExtendedStart =
1387 const SCEV *OverflowLimit =
1399 static const SCEV *getExtendAddRecStart(const SCEVAddRecExpr *AR, Type *Ty,
1404 const SCEV *PreStart = getPreStartForExtend<ExtendOpTy>(AR, Ty, SE, Depth);
1446 bool ScalarEvolution::proveNoWrapByVaryingStart(const SCEV *Start,
1447 const SCEV *Step,
1451 // We restrict `Start` to a constant to prevent SCEV from spending too much
1453 // non-constant `Start` and do a general SCEV subtraction to compute
1462 const SCEV *PreStart = getConstant(StartAI - Delta);
1476 const SCEV *DeltaS = getConstant(StartC->getType(), Delta);
1478 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1516 const SCEV *Step) {
1526 const ScalarEvolution::FoldID &ID, const SCEV *S,
1527 DenseMap<ScalarEvolution::FoldID, const SCEV *> &FoldCache,
1528 DenseMap<const SCEV *, SmallVector<ScalarEvolution::FoldID, 2>>
1548 const SCEV *
1549 ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) {
1562 const SCEV *S = getZeroExtendExprImpl(Op, Ty, Depth);
1568 const SCEV *ScalarEvolution::getZeroExtendExprImpl(const SCEV *Op, Type *Ty,
1584 // computed a SCEV for this Op and Ty.
1590 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1592 SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator),
1603 const SCEV *X = ST->getOperand();
1618 const SCEV *Start = AR->getStart();
1619 const SCEV *Step = AR->getStepRecurrence(*this);
1640 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L);
1646 const SCEV *CastedMaxBECount =
1648 const SCEV *RecastedMaxBECount = getTruncateOrZeroExtend(
1653 const SCEV *ZMul = getMulExpr(CastedMaxBECount, Step,
1654 SCEV::FlagAnyWrap, Depth + 1);
1655 const SCEV *ZAdd = getZeroExtendExpr(getAddExpr(Start, ZMul,
1656 SCEV::FlagAnyWrap,
1659 const SCEV *WideStart = getZeroExtendExpr(Start, WideTy, Depth + 1);
1660 const SCEV *WideMaxBECount =
1662 const SCEV *OperandExtendedAdd =
1666 SCEV::FlagAnyWrap, Depth + 1),
1667 SCEV::FlagAnyWrap, Depth + 1);
1670 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNUW);
1683 SCEV::FlagAnyWrap, Depth + 1),
1684 SCEV::FlagAnyWrap, Depth + 1);
1688 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNW);
1701 // guards present in the loop -- SCEV is not great at exploiting
1724 const SCEV *N = getConstant(APInt::getMaxValue(BitWidth) -
1731 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNW);
1748 const SCEV *SZExtD = getZeroExtendExpr(getConstant(D), Ty, Depth);
1749 const SCEV *SResidual =
1751 const SCEV *SZExtR = getZeroExtendExpr(SResidual, Ty, Depth + 1);
1753 (SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNUW),
1759 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNUW);
1769 const SCEV *LHS;
1770 const SCEV *RHS;
1786 SmallVector<const SCEV *, 4> Ops;
1789 return getAddExpr(Ops, SCEV::FlagNUW, Depth + 1);
1803 const SCEV *SZExtD = getZeroExtendExpr(getConstant(D), Ty, Depth);
1804 const SCEV *SResidual =
1805 getAddExpr(getConstant(-D), SA, SCEV::FlagAnyWrap, Depth);
1806 const SCEV *SZExtR = getZeroExtendExpr(SResidual, Ty, Depth + 1);
1808 (SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNUW),
1819 SmallVector<const SCEV *, 4> Ops;
1822 return getMulExpr(Ops, SCEV::FlagNUW, Depth + 1);
1848 SCEV::FlagNUW, Depth + 1);
1856 SmallVector<const SCEV *, 4> Operands;
1867 SmallVector<const SCEV *, 4> Operands;
1875 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1876 SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator),
1883 const SCEV *
1884 ScalarEvolution::getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) {
1897 const SCEV *S = getSignExtendExprImpl(Op, Ty, Depth);
1903 const SCEV *ScalarEvolution::getSignExtendExprImpl(const SCEV *Op, Type *Ty,
1924 // computed a SCEV for this Op and Ty.
1930 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1933 SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator),
1944 const SCEV *X = ST->getOperand();
1958 SmallVector<const SCEV *, 4> Ops;
1961 return getAddExpr(Ops, SCEV::FlagNSW, Depth + 1);
1976 const SCEV *SSExtD = getSignExtendExpr(getConstant(D), Ty, Depth);
1977 const SCEV *SResidual =
1978 getAddExpr(getConstant(-D), SA, SCEV::FlagAnyWrap, Depth);
1979 const SCEV *SSExtR = getSignExtendExpr(SResidual, Ty, Depth + 1);
1981 (SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNUW),
1992 const SCEV *Start = AR->getStart();
1993 const SCEV *Step = AR->getStepRecurrence(*this);
2003 return getAddRecExpr(Start, Step, L, SCEV::FlagNSW);
2014 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L);
2021 const SCEV *CastedMaxBECount =
2023 const SCEV *RecastedMaxBECount = getTruncateOrZeroExtend(
2028 const SCEV *SMul = getMulExpr(CastedMaxBECount, Step,
2029 SCEV::FlagAnyWrap, Depth + 1);
2030 const SCEV *SAdd = getSignExtendExpr(getAddExpr(Start, SMul,
2031 SCEV::FlagAnyWrap,
2034 const SCEV *WideStart = getSignExtendExpr(Start, WideTy, Depth + 1);
2035 const SCEV *WideMaxBECount =
2037 const SCEV *OperandExtendedAdd =
2041 SCEV::FlagAnyWrap, Depth + 1),
2042 SCEV::FlagAnyWrap, Depth + 1);
2045 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNSW);
2058 SCEV::FlagAnyWrap, Depth + 1),
2059 SCEV::FlagAnyWrap, Depth + 1);
2069 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNW);
2100 const SCEV *SSExtD = getSignExtendExpr(getConstant(D), Ty, Depth);
2101 const SCEV *SResidual =
2103 const SCEV *SSExtR = getSignExtendExpr(SResidual, Ty, Depth + 1);
2105 (SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNUW),
2111 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNSW);
2128 SmallVector<const SCEV *, 4> Operands;
2138 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
2139 SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator),
2146 const SCEV *ScalarEvolution::getCastExpr(SCEVTypes Kind, const SCEV *Op,
2158 llvm_unreachable("Not a SCEV cast expression!");
2162 /// getAnyExtendExpr - Return a SCEV for the given operand extended with
2164 const SCEV *ScalarEvolution::getAnyExtendExpr(const SCEV *Op,
2179 const SCEV *NewOp = T->getOperand();
2186 const SCEV *ZExt = getZeroExtendExpr(Op, Ty);
2191 const SCEV *SExt = getSignExtendExpr(Op, Ty);
2197 SmallVector<const SCEV *, 4> Ops;
2198 for (const SCEV *Op : AR->operands())
2200 return getAddRecExpr(Ops, AR->getLoop(), SCEV::FlagNW);
2235 CollectAddOperandsWithScales(DenseMap<const SCEV *, APInt> &M,
2236 SmallVectorImpl<const SCEV *> &NewOps,
2238 ArrayRef<const SCEV *> Ops, const APInt &Scale,
2268 SmallVector<const SCEV *, 4> MulOps(drop_begin(Mul->operands()));
2269 const SCEV *Key = SE.getMulExpr(MulOps);
2282 std::pair<DenseMap<const SCEV *, APInt>::iterator, bool> Pair =
2299 const SCEV *LHS, const SCEV *RHS,
2301 const SCEV *(ScalarEvolution::*Operation)(const SCEV *, const SCEV *,
2302 SCEV::NoWrapFlags, unsigned);
2317 const SCEV *(ScalarEvolution::*Extension)(const SCEV *, Type *, unsigned) =
2326 const SCEV *A = (this->*Extension)(
2327 (this->*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0), WideTy, 0);
2328 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2329 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2330 const SCEV *B = (this->*Operation)(LHSB, RHSB, SCEV::FlagAnyWrap, 0);
2374 std::optional<SCEV::NoWrapFlags>
2381 SCEV::NoWrapFlags Flags = SCEV::NoWrapFlags::FlagAnyWrap;
2384 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
2386 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW);
2395 const SCEV *LHS = getSCEV(OBO->getOperand(0));
2396 const SCEV *RHS = getSCEV(OBO->getOperand(1));
2403 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
2410 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW);
2419 // We're trying to construct a SCEV of type `Type' with `Ops' as operands and
2422 static SCEV::NoWrapFlags
2424 const ArrayRef<const SCEV *> Ops,
2425 SCEV::NoWrapFlags Flags) {
2435 int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW;
2436 SCEV::NoWrapFlags SignOrUnsignWrap =
2440 auto IsKnownNonNegative = [&](const SCEV *S) {
2444 if (SignOrUnsignWrap == SCEV::FlagNSW && all_of(Ops, IsKnownNonNegative))
2446 ScalarEvolution::setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask);
2461 llvm_unreachable("Unexpected SCEV op.");
2468 if (!(SignOrUnsignWrap & SCEV::FlagNSW)) {
2472 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW);
2476 if (!(SignOrUnsignWrap & SCEV::FlagNUW)) {
2480 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
2486 if (Type == scAddRecExpr && ScalarEvolution::hasFlags(Flags, SCEV::FlagNW) &&
2487 !ScalarEvolution::hasFlags(Flags, SCEV::FlagNUW) && Ops.size() == 2 &&
2489 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
2492 if (Type == scMulExpr && !ScalarEvolution::hasFlags(Flags, SCEV::FlagNUW) &&
2496 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
2499 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
2505 bool ScalarEvolution::isAvailableAtLoopEntry(const SCEV *S, const Loop *L) {
2510 const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
2511 SCEV::NoWrapFlags OrigFlags,
2513 assert(!(OrigFlags & ~(SCEV::FlagNUW | SCEV::FlagNSW)) &&
2523 Ops, [](const SCEV *Op) { return Op->getType()->isPointerTy(); });
2553 auto ComputeFlags = [this, OrigFlags](const ArrayRef<const SCEV *> Ops) {
2561 if (SCEV *S = findExistingSCEVInCache(scAddExpr, Ops)) {
2581 const SCEV *Scale = getConstant(Ty, Count);
2582 const SCEV *Mul = getMulExpr(Scale, Ops[i], SCEV::FlagAnyWrap, Depth + 1);
2599 // constants and truncs, so if we find any other types of SCEV
2612 SmallVector<const SCEV *, 8> LargeOps;
2626 SmallVector<const SCEV *, 8> LargeMulOps;
2643 LargeOps.push_back(getMulExpr(LargeMulOps, SCEV::FlagAnyWrap, Depth + 1));
2651 const SCEV *Fold = getAddExpr(LargeOps, SCEV::FlagAnyWrap, Depth + 1);
2662 const SCEV *A = Ops[0];
2663 const SCEV *B = Ops[1];
2669 SCEV::NoWrapFlags PreservedFlags = SCEV::FlagAnyWrap;
2674 if (ScalarEvolution::hasFlags(AddFlags, SCEV::FlagNUW) &&
2677 ScalarEvolution::setFlags(PreservedFlags, SCEV::FlagNUW);
2682 if (ScalarEvolution::hasFlags(AddFlags, SCEV::FlagNSW) &&
2686 ScalarEvolution::setFlags(PreservedFlags, SCEV::FlagNSW);
2689 if (PreservedFlags != SCEV::FlagAnyWrap) {
2690 SmallVector<const SCEV *, 4> NewOps(AddExpr->operands());
2702 const SCEV *X;
2703 const SCEV *Y;
2720 SCEV::NoWrapFlags CommonFlags = maskFlags(OrigFlags, SCEV::FlagNUW);
2748 DenseMap<const SCEV *, APInt> M;
2749 SmallVector<const SCEV *, 8> NewOps;
2762 std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists;
2763 for (const SCEV *NewOp : NewOps)
2771 Ops.push_back(getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1));
2775 getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1),
2776 SCEV::FlagAnyWrap, Depth + 1));
2783 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
2793 const SCEV *MulOpSCEV = Mul->getOperand(MulOp);
2799 const SCEV *InnerMul = Mul->getOperand(MulOp == 0);
2803 SmallVector<const SCEV *, 4> MulOps(
2806 InnerMul = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1);
2808 SmallVector<const SCEV *, 2> TwoOps = {getOne(Ty), InnerMul};
2809 const SCEV *AddOne = getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1);
2810 const SCEV *OuterMul = getMulExpr(AddOne, MulOpSCEV,
2811 SCEV::FlagAnyWrap, Depth + 1);
2821 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
2835 const SCEV *InnerMul1 = Mul->getOperand(MulOp == 0);
2837 SmallVector<const SCEV *, 4> MulOps(
2840 InnerMul1 = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1);
2842 const SCEV *InnerMul2 = OtherMul->getOperand(OMulOp == 0);
2844 SmallVector<const SCEV *, 4> MulOps(
2847 InnerMul2 = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1);
2849 SmallVector<const SCEV *, 2> TwoOps = {InnerMul1, InnerMul2};
2850 const SCEV *InnerMulSum =
2851 getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1);
2852 const SCEV *OuterMul = getMulExpr(MulOpSCEV, InnerMulSum,
2853 SCEV::FlagAnyWrap, Depth + 1);
2858 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
2874 SmallVector<const SCEV *, 8> LIOps;
2890 SCEV::NoWrapFlags Flags = ComputeFlags(LIOps);
2896 SmallVector<const SCEV *, 4> AddRecOps(AddRec->operands());
2908 SCEV::NoWrapFlags AddFlags = Flags;
2909 if (AddFlags != SCEV::FlagAnyWrap) {
2913 AddFlags = SCEV::FlagAnyWrap;
2920 Flags = AddRec->getNoWrapFlags(setFlags(Flags, SCEV::FlagNW));
2921 const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRecLoop, Flags);
2932 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
2949 SmallVector<const SCEV *, 4> AddRecOps(AddRec->operands());
2960 SmallVector<const SCEV *, 2> TwoOps = {
2962 AddRecOps[i] = getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1);
2968 Ops[Idx] = getAddRecExpr(AddRecOps, AddRecLoop, SCEV::FlagAnyWrap);
2969 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
2982 const SCEV *
2983 ScalarEvolution::getOrCreateAddExpr(ArrayRef<const SCEV *> Ops,
2984 SCEV::NoWrapFlags Flags) {
2987 for (const SCEV *Op : Ops)
2993 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
3004 const SCEV *
3005 ScalarEvolution::getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops,
3006 const Loop *L, SCEV::NoWrapFlags Flags) {
3009 for (const SCEV *Op : Ops)
3016 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
3028 const SCEV *
3029 ScalarEvolution::getOrCreateMulExpr(ArrayRef<const SCEV *> Ops,
3030 SCEV::NoWrapFlags Flags) {
3033 for (const SCEV *Op : Ops)
3039 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
3082 /// Determine if any of the operands in this SCEV are a constant or if
3083 /// any of the add or multiply expressions in this SCEV contain a constant.
3084 static bool containsConstantInAddMulChain(const SCEV *StartExpr) {
3088 bool follow(const SCEV *S) {
3105 const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
3106 SCEV::NoWrapFlags OrigFlags,
3108 assert(OrigFlags == maskFlags(OrigFlags, SCEV::FlagNUW | SCEV::FlagNSW) &&
3151 auto ComputeFlags = [this, OrigFlags](const ArrayRef<const SCEV *> Ops) {
3159 if (SCEV *S = findExistingSCEVInCache(scMulExpr, Ops)) {
3178 const SCEV *LHS = getMulExpr(LHSC, Add->getOperand(0),
3179 SCEV::FlagAnyWrap, Depth + 1);
3180 const SCEV *RHS = getMulExpr(LHSC, Add->getOperand(1),
3181 SCEV::FlagAnyWrap, Depth + 1);
3182 return getAddExpr(LHS, RHS, SCEV::FlagAnyWrap, Depth + 1);
3189 SmallVector<const SCEV *, 4> NewOps;
3191 for (const SCEV *AddOp : Add->operands()) {
3192 const SCEV *Mul = getMulExpr(Ops[0], AddOp, SCEV::FlagAnyWrap,
3198 return getAddExpr(NewOps, SCEV::FlagAnyWrap, Depth + 1);
3201 SmallVector<const SCEV *, 4> Operands;
3202 for (const SCEV *AddRecOp : AddRec->operands())
3203 Operands.push_back(getMulExpr(Ops[0], AddRecOp, SCEV::FlagAnyWrap,
3210 auto FlagsMask = SCEV::FlagNW;
3211 if (hasFlags(AddRec->getNoWrapFlags(), SCEV::FlagNSW)) {
3215 FlagsMask = setFlags(FlagsMask, SCEV::FlagNSW);
3245 return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
3258 SmallVector<const SCEV *, 8> LIOps;
3270 SmallVector<const SCEV *, 4> NewOps;
3272 const SCEV *Scale = getMulExpr(LIOps, SCEV::FlagAnyWrap, Depth + 1);
3278 SCEV::NoWrapFlags Flags =
3283 SCEV::FlagAnyWrap, Depth + 1));
3285 if (hasFlags(Flags, SCEV::FlagNSW) && !hasFlags(Flags, SCEV::FlagNUW)) {
3290 Flags = clearFlags(Flags, SCEV::FlagNSW);
3294 const SCEV *NewRec = getAddRecExpr(NewOps, AddRec->getLoop(), Flags);
3305 return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
3317 // known at compile time, never SCEV objects.
3340 SmallVector<const SCEV*, 7> AddRecOps;
3343 SmallVector <const SCEV *, 7> SumOps;
3355 const SCEV *CoeffTerm = getConstant(Ty, Coeff);
3356 const SCEV *Term1 = AddRec->getOperand(y-z);
3357 const SCEV *Term2 = OtherAddRec->getOperand(z);
3359 SCEV::FlagAnyWrap, Depth + 1));
3364 AddRecOps.push_back(getAddExpr(SumOps, SCEV::FlagAnyWrap, Depth + 1));
3367 const SCEV *NewAddRec = getAddRecExpr(AddRecOps, AddRec->getLoop(),
3368 SCEV::FlagAnyWrap);
3379 return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
3391 const SCEV *ScalarEvolution::getURemExpr(const SCEV *LHS,
3392 const SCEV *RHS) {
3413 const SCEV *UDiv = getUDivExpr(LHS, RHS);
3414 const SCEV *Mult = getMulExpr(UDiv, RHS, SCEV::FlagNUW);
3415 return getMinusSCEV(LHS, Mult, SCEV::FlagNUW);
3420 const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS,
3421 const SCEV *RHS) {
3432 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
3469 AR->getLoop(), SCEV::FlagAnyWrap)) {
3470 SmallVector<const SCEV *, 4> Operands;
3471 for (const SCEV *Op : AR->operands())
3473 return getAddRecExpr(Operands, AR->getLoop(), SCEV::FlagNW);
3483 AR->getLoop(), SCEV::FlagAnyWrap)) {
3487 const SCEV *NewLHS =
3489 AR->getLoop(), SCEV::FlagNW);
3500 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
3508 SmallVector<const SCEV *, 4> Operands;
3509 for (const SCEV *Op : M->operands())
3514 const SCEV *Op = M->getOperand(i);
3515 const SCEV *Div = getUDivExpr(Op, RHSC);
3517 Operands = SmallVector<const SCEV *, 4>(M->operands());
3540 SmallVector<const SCEV *, 4> Operands;
3541 for (const SCEV *Op : A->operands())
3546 const SCEV *Op = getUDivExpr(A->getOperand(i), RHS);
3566 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
3567 SCEV *S = new (SCEVAllocator) SCEVUDivExpr(ID.Intern(SCEVAllocator),
3589 /// possible. There is no representation for an exact udiv in SCEV IR, but we
3592 const SCEV *ScalarEvolution::getUDivExactExpr(const SCEV *LHS,
3593 const SCEV *RHS) {
3607 SmallVector<const SCEV *, 2> Operands(drop_begin(Mul->operands()));
3620 SmallVector<const SCEV *, 2> Operands;
3634 SmallVector<const SCEV *, 2> Operands;
3646 const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, const SCEV *Step,
3648 SCEV::NoWrapFlags Flags) {
3649 SmallVector<const SCEV *, 4> Operands;
3654 return getAddRecExpr(Operands, L, maskFlags(Flags, SCEV::FlagNW));
3663 const SCEV *
3664 ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
3665 const Loop *L, SCEV::NoWrapFlags Flags) {
3681 return getAddRecExpr(Operands, L, SCEV::FlagAnyWrap); // {X,+,0} --> X
3699 SmallVector<const SCEV *, 4> NestedOperands(NestedAR->operands());
3705 Operands, [&](const SCEV *Op) { return isLoopInvariant(Op, L); });
3712 SCEV::NoWrapFlags OuterFlags =
3713 maskFlags(Flags, SCEV::FlagNW | NestedAR->getNoWrapFlags());
3716 AllInvariant = all_of(NestedOperands, [&](const SCEV *Op) {
3725 SCEV::NoWrapFlags InnerFlags =
3726 maskFlags(NestedAR->getNoWrapFlags(), SCEV::FlagNW | Flags);
3740 const SCEV *
3742 const SmallVectorImpl<const SCEV *> &IndexExprs) {
3743 const SCEV *BaseExpr = getSCEV(GEP->getPointerOperand());
3745 // 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.
3760 SCEV::NoWrapFlags OffsetWrap =
3761 AssumeInBoundsFlags ? SCEV::FlagNSW : SCEV::FlagAnyWrap;
3765 SmallVector<const SCEV *, 4> Offsets;
3766 for (const SCEV *IndexExpr : IndexExprs) {
3772 const SCEV *FieldOffset = getOffsetOfExpr(IntIdxTy, STy, FieldNo);
3788 const SCEV *ElementSize = getSizeOfExpr(IntIdxTy, CurTy);
3793 const SCEV *LocalOffset = getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3803 const SCEV *Offset = getAddExpr(Offsets, OffsetWrap);
3807 SCEV::NoWrapFlags BaseWrap = AssumeInBoundsFlags && isKnownNonNegative(Offset)
3808 ? SCEV::FlagNUW : SCEV::FlagAnyWrap;
3815 SCEV *ScalarEvolution::findExistingSCEVInCache(SCEVTypes SCEVType,
3816 ArrayRef<const SCEV *> Ops) {
3819 for (const SCEV *Op : Ops)
3825 const SCEV *ScalarEvolution::getAbsExpr(const SCEV *Op, bool IsNSW) {
3826 SCEV::NoWrapFlags Flags = IsNSW ? SCEV::FlagNSW : SCEV::FlagAnyWrap;
3830 const SCEV *ScalarEvolution::getMinMaxExpr(SCEVTypes Kind,
3831 SmallVectorImpl<const SCEV *> &Ops) {
3853 if (const SCEV *S = findExistingSCEVInCache(Kind, Ops)) {
3873 llvm_unreachable("Unknown SCEV min/max opcode");
3959 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
3962 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
3964 SCEV *S = new (SCEVAllocator)
3976 std::optional<const SCEV *>> {
3977 using RetVal = std::optional<const SCEV *>;
3983 SmallPtrSet<const SCEV *, 16> SeenOps;
3986 // We can only recurse into the SCEV expression of the same effective type
3987 // as the type of our root SCEV expression.
3991 RetVal visitAnyMinMaxExpr(const SCEV *S) {
4000 SmallVector<const SCEV *> NewOps;
4013 RetVal visit(const SCEV *S) {
4028 bool /*Changed*/ visit(SCEVTypes Kind, ArrayRef<const SCEV *> OrigOps,
4029 SmallVectorImpl<const SCEV *> &NewOps) {
4031 SmallVector<const SCEV *> Ops;
4034 for (const SCEV *Op : OrigOps) {
4119 llvm_unreachable("Unknown SCEV kind!");
4123 // The only way poison may be introduced in a SCEV expression is from a
4125 // not SCEVConstant). Notably, nowrap flags in SCEV nodes can *not*
4128 // Additionally, all SCEV nodes propagate poison from inputs to outputs,
4137 bool follow(const SCEV *S) {
4153 static bool impliesPoison(const SCEV *AssumedPoison, const SCEV *S) {
4162 // is true. Don't bother walking the other SCEV in this case.
4172 // Make sure that no matter which SCEV in PC1.MaybePoison is actually poison,
4180 SmallPtrSetImpl<const Value *> &Result, const SCEV *S) {
4188 const SCEV *S, Instruction *I,
4222 // Disjoint or instructions are interpreted as adds by SCEV. However, we
4230 // because SCEV currently assumes it can't be poison. Remove this special
4249 const SCEV *
4251 SmallVectorImpl<const SCEV *> &Ops) {
4272 if (const SCEV *S = findExistingSCEVInCache(Kind, Ops))
4306 const SCEV *SaturationPoint;
4324 SmallVector<const SCEV *> SeqOps = {Ops[i - 1], Ops[i]};
4346 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
4350 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
4352 SCEV *S = new (SCEVAllocator)
4360 const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS, const SCEV *RHS) {
4361 SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
4365 const SCEV *ScalarEvolution::getSMaxExpr(SmallVectorImpl<const SCEV *> &Ops) {
4369 const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS, const SCEV *RHS) {
4370 SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
4374 const SCEV *ScalarEvolution::getUMaxExpr(SmallVectorImpl<const SCEV *> &Ops) {
4378 const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS,
4379 const SCEV *RHS) {
4380 SmallVector<const SCEV *, 2> Ops = { LHS, RHS };
4384 const SCEV *ScalarEvolution::getSMinExpr(SmallVectorImpl<const SCEV *> &Ops) {
4388 const SCEV *ScalarEvolution::getUMinExpr(const SCEV *LHS, const SCEV *RHS,
4390 SmallVector<const SCEV *, 2> Ops = { LHS, RHS };
4394 const SCEV *ScalarEvolution::getUMinExpr(SmallVectorImpl<const SCEV *> &Ops,
4400 const SCEV *
4402 const SCEV *Res = getConstant(IntTy, Size.getKnownMinValue());
4408 const SCEV *ScalarEvolution::getSizeOfExpr(Type *IntTy, Type *AllocTy) {
4412 const SCEV *ScalarEvolution::getStoreSizeOfExpr(Type *IntTy, Type *StoreTy) {
4416 const SCEV *ScalarEvolution::getOffsetOfExpr(Type *IntTy,
4428 const SCEV *ScalarEvolution::getUnknown(Value *V) {
4432 // is doing so in order to hide a value from SCEV canonicalization.
4438 if (SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) {
4443 SCEV *S = new (SCEVAllocator) SCEVUnknown(ID.Intern(SCEVAllocator), V, this,
4451 // Basic SCEV Analysis and PHI Idiom Recognition Code
4454 /// Test if values of the given type are analyzable within the SCEV
4473 /// how SCEV will treat the given type, for which isSCEVable must return
4490 bool ScalarEvolution::instructionCouldExistWithOperands(const SCEV *A,
4491 const SCEV *B) {
4504 const SCEV *ScalarEvolution::getCouldNotCompute() {
4508 bool ScalarEvolution::checkValidity(const SCEV *S) const {
4509 bool ContainsNulls = SCEVExprContains(S, [](const SCEV *S) {
4517 bool ScalarEvolution::containsAddRecurrence(const SCEV *S) {
4523 SCEVExprContains(S, [](const SCEV *S) { return isa<SCEVAddRecExpr>(S); });
4530 ArrayRef<Value *> ScalarEvolution::getSCEVValues(const SCEV *S) {
4551 void ScalarEvolution::insertValueToMap(Value *V, const SCEV *S) {
4552 // A recursive query may have already computed the SCEV. It should be
4562 /// Return an existing SCEV if it exists, otherwise analyze the expression and
4564 const SCEV *ScalarEvolution::getSCEV(Value *V) {
4567 if (const SCEV *S = getExistingSCEV(V))
4572 const SCEV *ScalarEvolution::getExistingSCEV(Value *V) {
4577 const SCEV *S = I->second;
4579 "existing SCEV has not been properly invalidated");
4585 /// Return a SCEV corresponding to -V = -1*V
4586 const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V,
4587 SCEV::NoWrapFlags Flags) {
4598 static const SCEV *MatchNotExpr(const SCEV *Expr) {
4612 /// Return a SCEV corresponding to ~V = -1-V
4613 const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) {
4623 SmallVector<const SCEV *, 2> MatchedOperands;
4624 for (const SCEV *Operand : MME->operands()) {
4625 const SCEV *Matched = MatchNotExpr(Operand);
4627 return (const SCEV *)nullptr;
4633 if (const SCEV *Replaced = MatchMinMaxNegation(MME))
4642 const SCEV *ScalarEvolution::removePointerBase(const SCEV *P) {
4647 SmallVector<const SCEV *> Ops{AddRec->operands()};
4651 return getAddRecExpr(Ops, AddRec->getLoop(), SCEV::FlagAnyWrap);
4655 SmallVector<const SCEV *> Ops{Add->operands()};
4656 const SCEV **PtrOp = nullptr;
4657 for (const SCEV *&AddOp : Ops) {
4672 const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
4673 SCEV::NoWrapFlags Flags,
4692 auto AddFlags = SCEV::FlagAnyWrap;
4695 if (hasFlags(Flags, SCEV::FlagNSW)) {
4706 AddFlags = SCEV::FlagNSW;
4717 auto NegFlags = RHSIsNotMinSigned ? SCEV::FlagNSW : SCEV::FlagAnyWrap;
4722 const SCEV *ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V, Type *Ty,
4734 const SCEV *ScalarEvolution::getTruncateOrSignExtend(const SCEV *V, Type *Ty,
4746 const SCEV *
4747 ScalarEvolution::getNoopOrZeroExtend(const SCEV *V, Type *Ty) {
4758 const SCEV *
4759 ScalarEvolution::getNoopOrSignExtend(const SCEV *V, Type *Ty) {
4770 const SCEV *
4771 ScalarEvolution::getNoopOrAnyExtend(const SCEV *V, Type *Ty) {
4782 const SCEV *
4783 ScalarEvolution::getTruncateOrNoop(const SCEV *V, Type *Ty) {
4794 const SCEV *ScalarEvolution::getUMaxFromMismatchedTypes(const SCEV *LHS,
4795 const SCEV *RHS) {
4796 const SCEV *PromotedLHS = LHS;
4797 const SCEV *PromotedRHS = RHS;
4807 const SCEV *ScalarEvolution::getUMinFromMismatchedTypes(const SCEV *LHS,
4808 const SCEV *RHS,
4810 SmallVector<const SCEV *, 2> Ops = { LHS, RHS };
4814 const SCEV *
4815 ScalarEvolution::getUMinFromMismatchedTypes(SmallVectorImpl<const SCEV *> &Ops,
4832 SmallVector<const SCEV *, 2> PromotedOps;
4840 const SCEV *ScalarEvolution::getPointerBase(const SCEV *V) {
4849 const SCEV *PtrOp = nullptr;
4850 for (const SCEV *AddOp : Add->operands()) {
4877 /// Takes SCEV S and Loop L. For each AddRec sub-expression, use its start
4881 /// If SCEV contains non-invariant unknown SCEV rewrite cannot be done.
4884 static const SCEV *rewrite(const SCEV *S, const Loop *L, ScalarEvolution &SE,
4887 const SCEV *Result = Rewriter.visit(S);
4895 const SCEV *visitUnknown(const SCEVUnknown *Expr) {
4901 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
4922 /// Takes SCEV S and Loop L. For each AddRec sub-expression, use its post
4925 /// If SCEV contains non-invariant unknown SCEV rewrite cannot be done.
4928 static const SCEV *rewrite(const SCEV *S, const Loop *L, ScalarEvolution &SE) {
4930 const SCEV *Result = Rewriter.visit(S);
4936 const SCEV *visitUnknown(const SCEVUnknown *Expr) {
4942 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
4965 /// for the condition while building SCEV nodes.
4969 static const SCEV *rewrite(const SCEV *S, const Loop *L,
4988 const SCEV *visitUnknown(const SCEVUnknown *Expr) {
4989 const SCEV *Result = Expr;
4997 std::optional<const SCEV *> Res =
5006 std::optional<const SCEV *> Res = compareWithBackedgeCondition(I);
5022 std::optional<const SCEV *> compareWithBackedgeCondition(Value *IC);
5031 std::optional<const SCEV *>
5045 static const SCEV *rewrite(const SCEV *S, const Loop *L,
5048 const SCEV *Result = Rewriter.visit(S);
5052 const SCEV *visitUnknown(const SCEVUnknown *Expr) {
5059 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
5078 SCEV::NoWrapFlags
5081 return SCEV::FlagAnyWrap;
5085 SCEV::NoWrapFlags Result = SCEV::FlagAnyWrap;
5088 const SCEV *BECount = getConstantMaxBackedgeTakenCount(AR->getLoop());
5095 Result = ScalarEvolution::setFlags(Result, SCEV::FlagNW);
5106 Result = ScalarEvolution::setFlags(Result, SCEV::FlagNSW);
5116 Result = ScalarEvolution::setFlags(Result, SCEV::FlagNUW);
5122 SCEV::NoWrapFlags
5124 SCEV::NoWrapFlags Result = AR->getNoWrapFlags();
5136 const SCEV *Step = AR->getStepRecurrence(*this);
5147 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L);
5152 // guards present in the loop -- SCEV is not great at exploiting
5166 const SCEV *OverflowLimit =
5171 Result = setFlags(Result, SCEV::FlagNSW);
5175 SCEV::NoWrapFlags
5177 SCEV::NoWrapFlags Result = AR->getNoWrapFlags();
5189 const SCEV *Step = AR->getStepRecurrence(*this);
5201 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L);
5206 // guards present in the loop -- SCEV is not great at exploiting
5220 const SCEV *N = getConstant(APInt::getMinValue(BitWidth) -
5224 Result = setFlags(Result, SCEV::FlagNUW);
5273 // creating new SCEV expressions -- our caller knowns tricks to avoid creating
5274 // SCEV expressions when possible, and we should not break that.
5360 /// node whose symbolic (unknown) SCEV is \p SymbolicPHI, which is updated via
5366 /// If the SCEV expression of \p Op conforms with one of the expected patterns
5370 static Type *isSimpleCastedPHI(const SCEV *Op, const SCEVUnknown *SymbolicPHI,
5399 const SCEV *X = Trunc->getOperand();
5415 // Analyze \p SymbolicPHI, a SCEV expression of a phi node, and check if the
5424 // Say the Rewriter is called for the following SCEV:
5432 // the following SCEV:
5468 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5502 const SCEV *BEValue = getSCEV(BEValueV);
5528 SmallVector<const SCEV *, 8> Ops;
5532 const SCEV *Accum = getAddExpr(Ops);
5590 const SCEV *StartVal = getSCEV(StartValueV);
5591 const SCEV *PHISCEV =
5593 getTruncateExpr(Accum, TruncTy), L, SCEV::FlagAnyWrap);
5616 // Construct the extended SCEV: (Ext ix (Trunc iy (Expr) to ix) to iy)
5618 auto getExtendedExpr = [&](const SCEV *Expr,
5619 bool CreateSignExtend) -> const SCEV * {
5621 const SCEV *TruncatedExpr = getTruncateExpr(Expr, TruncTy);
5622 const SCEV *ExtendedExpr =
5633 auto PredIsKnownFalse = [&](const SCEV *Expr,
5634 const SCEV *ExtendedExpr) -> bool {
5639 const SCEV *StartExtended = getExtendedExpr(StartVal, Signed);
5647 const SCEV *AccumExtended = getExtendedExpr(Accum, /*CreateSignExtend=*/true);
5653 auto AppendPredicate = [&](const SCEV *Expr,
5654 const SCEV *ExtendedExpr) -> void {
5670 auto *NewAR = getAddRecExpr(StartVal, Accum, L, SCEV::FlagAnyWrap);
5672 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5674 // Remember the result of the analysis for this SCEV at this locayyytion.
5679 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5689 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5701 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5725 auto areExprsEqual = [&](const SCEV *Expr1, const SCEV *Expr2) -> bool {
5744 const SCEV *ScalarEvolution::createSimpleAffineAddRec(PHINode *PN,
5758 const SCEV *Accum = nullptr;
5767 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
5769 Flags = setFlags(Flags, SCEV::FlagNUW);
5771 Flags = setFlags(Flags, SCEV::FlagNSW);
5773 const SCEV *StartVal = getSCEV(StartValueV);
5774 const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags);
5779 (SCEV::NoWrapFlags)(AR->getNoWrapFlags() |
5796 const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) {
5833 const SCEV *SymbolicName = getUnknown(PN);
5838 const SCEV *BEValue = getSCEV(BEValueV);
5858 SmallVector<const SCEV *, 8> Ops;
5863 const SCEV *Accum = getAddExpr(Ops);
5870 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
5875 Flags = setFlags(Flags, SCEV::FlagNUW);
5877 Flags = setFlags(Flags, SCEV::FlagNSW);
5887 Flags = setFlags(Flags, SCEV::FlagNW);
5889 Flags = setFlags(Flags, SCEV::FlagNUW);
5897 const SCEV *StartVal = getSCEV(StartValueV);
5898 const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags);
5908 (SCEV::NoWrapFlags)(AR->getNoWrapFlags() |
5932 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *this);
5933 const SCEV *Start = SCEVInitRewriter::rewrite(Shifted, L, *this, false);
5936 const SCEV *StartVal = getSCEV(StartValueV);
5948 // Remove the temporary PHI node SCEV that has been inserted while intending
5950 // as it will prevent later (possibly simpler) SCEV expressions to be added
5990 const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(PHINode *PN) {
6022 const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) {
6023 if (const SCEV *S = createAddRecFromPHI(PN))
6029 if (const SCEV *S = createNodeFromSelectLikePHI(PN))
6036 bool SCEVMinMaxExprContains(const SCEV *Root, const SCEV *OperandToFind,
6039 const SCEV *OperandToFind;
6046 // We can only recurse into the SCEV expression of the same effective type
6047 // as the type of our root SCEV expression, and into zero-extensions.
6052 FindClosure(const SCEV *OperandToFind, SCEVTypes RootKind)
6058 bool follow(const SCEV *S) {
6072 std::optional<const SCEV *>
6098 const SCEV *LA = getSCEV(TrueVal);
6099 const SCEV *RA = getSCEV(FalseVal);
6100 const SCEV *LS = getSCEV(LHS);
6101 const SCEV *RS = getSCEV(RHS);
6111 auto CoerceOperand = [&](const SCEV *Op) -> const SCEV * {
6127 const SCEV *LDiff = getMinusSCEV(LA, LS);
6128 const SCEV *RDiff = getMinusSCEV(RA, RS);
6147 const SCEV *X = getNoopOrZeroExtend(getSCEV(LHS), Ty);
6148 const SCEV *TrueValExpr = getSCEV(TrueVal); // C+y
6149 const SCEV *FalseValExpr = getSCEV(FalseVal); // x+y
6150 const SCEV *Y = getMinusSCEV(FalseValExpr, X); // y = (x+y)-x
6151 const SCEV *C = getMinusSCEV(TrueValExpr, Y); // C = (C+y)-y
6161 const SCEV *X = getSCEV(LHS);
6165 const SCEV *FalseValExpr = getSCEV(FalseVal);
6179 static std::optional<const SCEV *>
6180 createNodeForSelectViaUMinSeq(ScalarEvolution *SE, const SCEV *CondExpr,
6181 const SCEV *TrueExpr, const SCEV *FalseExpr) {
6199 const SCEV *X, *C;
6212 static std::optional<const SCEV *>
6224 const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6235 if (std::optional<const SCEV *> S =
6242 const SCEV *ScalarEvolution::createNodeForSelectOrPHI(Value *V, Value *Cond,
6252 if (std::optional<const SCEV *> S =
6263 /// to be analyzed by regular SCEV code.
6264 const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) {
6268 SmallVector<const SCEV *, 4> IndexExprs;
6274 APInt ScalarEvolution::getConstantMultipleImpl(const SCEV *S) {
6317 for (const SCEV *Operand : M->operands().drop_front())
6325 for (const SCEV *Operand : M->operands())
6336 for (const SCEV *Operand : N->operands().drop_front())
6357 llvm_unreachable("Unknown SCEV kind!");
6360 APInt ScalarEvolution::getConstantMultiple(const SCEV *S) {
6371 APInt ScalarEvolution::getNonZeroConstantMultiple(const SCEV *S) {
6376 uint32_t ScalarEvolution::getMinTrailingZeros(const SCEV *S) {
6391 SCEV::NoWrapFlags Flags) {
6437 // the condition here exposes a case where LoopFusion is querying SCEV
6520 ScalarEvolution::getRangeRefIter(const SCEV *S,
6522 DenseMap<const SCEV *, ConstantRange> &Cache =
6525 SmallVector<const SCEV *> WorkList;
6526 SmallPtrSet<const SCEV *, 8> Seen;
6530 auto AddToWorklist = [&WorkList, &Seen, &Cache](const SCEV *Expr) {
6565 const SCEV *P = WorkList[I];
6569 for (const SCEV *Op : P->operands())
6586 for (const SCEV *P : reverse(drop_begin(WorkList))) {
6598 /// Determine the range for a particular SCEV. If SignHint is
6602 const SCEV *S, ScalarEvolution::RangeSignHint SignHint, unsigned Depth) {
6603 DenseMap<const SCEV *, ConstantRange> &Cache =
6611 DenseMap<const SCEV *, ConstantRange>::iterator I = Cache.find(S);
6746 const SCEV *MaxBEScev =
6774 const SCEV *SymbolicMaxBECount =
7005 ConstantRange ScalarEvolution::getRangeForAffineAR(const SCEV *Start,
7006 const SCEV *Step,
7035 const SCEVAddRecExpr *AddRec, const SCEV *MaxBECount, unsigned BitWidth,
7041 const SCEV *Step = AddRec->getStepRecurrence(*this);
7054 const SCEV *RangeWidth = getMinusOne(AddRec->getType());
7055 const SCEV *StepAbs = getUMinExpr(Step, getNegativeSCEV(Step));
7056 const SCEV *MaxItersWithoutWrap = getUDivExpr(RangeWidth, StepAbs);
7065 const SCEV *End = AddRec->evaluateAtIteration(MaxBECount, *this);
7079 const SCEV *Start = applyLoopGuards(AddRec->getStart(), AddRec->getLoop());
7102 ConstantRange ScalarEvolution::getRangeViaFactoring(const SCEV *Start,
7103 const SCEV *Step,
7119 const SCEV *S) {
7161 llvm_unreachable("Unknown SCEV cast type!");
7201 // construct arbitrary general SCEV expressions here. This function is called
7208 const SCEV *TrueStart = this->getConstant(StartPattern.TrueValue);
7209 const SCEV *TrueStep = this->getConstant(StepPattern.TrueValue);
7210 const SCEV *FalseStart = this->getConstant(StartPattern.FalseValue);
7211 const SCEV *FalseStep = this->getConstant(StepPattern.FalseValue);
7221 SCEV::NoWrapFlags ScalarEvolution::getNoWrapFlagsFromUB(const Value *V) {
7222 if (isa<ConstantExpr>(V)) return SCEV::FlagAnyWrap;
7225 // Return early if there are no flags to propagate to the SCEV.
7226 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
7228 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
7230 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW);
7231 if (Flags == SCEV::FlagAnyWrap)
7232 return SCEV::FlagAnyWrap;
7234 return isSCEVExprNeverPoison(BinOp) ? Flags : SCEV::FlagAnyWrap;
7238 ScalarEvolution::getNonTrivialDefiningScopeBound(const SCEV *S) {
7248 ScalarEvolution::getDefiningScopeBound(ArrayRef<const SCEV *> Ops,
7252 SmallSet<const SCEV *, 16> Visited;
7253 SmallVector<const SCEV *> Worklist;
7254 auto pushOp = [&](const SCEV *S) {
7283 ScalarEvolution::getDefiningScopeBound(ArrayRef<const SCEV *> Ops) {
7315 // instructions can map to the same SCEV. If we apply NSW or NUW from I to
7316 // the SCEV, we must guarantee no wrapping for that SCEV also when it is
7317 // derived from other instructions that map to the same SCEV. We cannot make
7319 // upper bound on the defining scope for the SCEV, and prove that I is
7323 SmallVector<const SCEV *> SCEVOps;
7419 const SCEV *ScalarEvolution::createSCEVIter(Value *V) {
7435 const SCEV *CreatedSCEV = nullptr;
7436 // If all operands have been visited already, create the SCEV.
7440 // Otherwise get the operands we need to create SCEV's for before creating
7441 // the SCEV for CurV. If the SCEV for CurV can be constructed trivially,
7449 // Queue CurV for SCEV creation, followed by its's operands which need to
7460 const SCEV *
7487 // can potentially create a single SCEV, to reduce the number of
7509 // requires a SCEV for the LHS.
7647 const SCEV *ScalarEvolution::createSCEV(Value *V) {
7665 const SCEV *LHS;
7666 const SCEV *RHS;
7679 SmallVector<const SCEV *, 4> AddOps;
7687 // If a NUW or NSW flag can be applied to the SCEV for this
7688 // addition, then compute the SCEV for this addition by itself
7694 const SCEV *RHS = getSCEV(BO->RHS);
7695 SCEV::NoWrapFlags Flags = getNoWrapFlagsFromUB(BO->Op);
7696 if (Flags != SCEV::FlagAnyWrap) {
7697 const SCEV *LHS = getSCEV(BO->LHS);
7725 SmallVector<const SCEV *, 4> MulOps;
7733 SCEV::NoWrapFlags Flags = getNoWrapFlagsFromUB(BO->Op);
7734 if (Flags != SCEV::FlagAnyWrap) {
7763 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
7772 // use zext(trunc(x)) as the SCEV expression.
7794 const SCEV *MulCount = getConstant(APInt::getOneBitSet(BitWidth, TZ));
7795 const SCEV *LHS = getSCEV(BO->LHS);
7796 const SCEV *ShiftedLHS = nullptr;
7803 SmallVector<const SCEV*, 4> MulOps;
7854 const SCEV *Z0 = Z->getOperand();
7892 auto Flags = SCEV::FlagAnyWrap;
7895 if ((MulFlags & SCEV::FlagNSW) &&
7896 ((MulFlags & SCEV::FlagNUW) || SA->getValue().ult(BitWidth - 1)))
7897 Flags = (SCEV::NoWrapFlags)(Flags | SCEV::FlagNSW);
7898 if (MulFlags & SCEV::FlagNUW)
7899 Flags = (SCEV::NoWrapFlags)(Flags | SCEV::FlagNUW);
7930 const SCEV *AddTruncateExpr = nullptr;
7932 const SCEV *AddConstant = nullptr;
7944 const SCEV *ShlOp0SCEV = getSCEV(LShift->getOperand(0));
7962 const SCEV *ShlOp0SCEV = getSCEV(L->getOperand(0));
7968 // We can merge the two given cases into a single SCEV statement,
7973 // use sext(trunc(x)) as the SCEV expression.
7975 // 2) When n > m, use sext(mul(trunc(x), 2^(n-m)))) as the SCEV
7983 const SCEV *CompositeExpr =
8016 return getMinusSCEV(V1, V2, SCEV::FlagNSW);
8029 const SCEV *Op = getSCEV(U->getOperand(0));
8031 // But only if effective SCEV (integer) type is wide enough to represent
8033 const SCEV *IntOp = getPtrToIntExpr(Op, DstIntTy);
8094 const SCEV *X = getSCEV(II->getArgOperand(0));
8095 const SCEV *Y = getSCEV(II->getArgOperand(1));
8096 const SCEV *ClampedY = getUMinExpr(X, Y);
8097 return getMinusSCEV(X, ClampedY, SCEV::FlagNUW);
8100 const SCEV *X = getSCEV(II->getArgOperand(0));
8101 const SCEV *Y = getSCEV(II->getArgOperand(1));
8102 const SCEV *ClampedX = getUMinExpr(X, getNotSCEV(Y));
8103 return getAddExpr(ClampedX, Y, SCEV::FlagNUW);
8109 // just eqivalent to the first operand for SCEV purposes.
8127 const SCEV *ScalarEvolution::getTripCountFromExitCount(const SCEV *ExitCount) {
8138 const SCEV *ScalarEvolution::getTripCountFromExitCount(const SCEV *ExitCount,
8219 const SCEV *ExitCount) {
8224 const SCEV *TCExpr = getTripCountFromExitCount(applyLoopGuards(ExitCount, L));
8252 const SCEV *ExitCount = getExitCount(L, ExitingBlock);
8256 const SCEV *ScalarEvolution::getExitCount(const Loop *L,
8270 const SCEV *
8276 const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L,
8326 // update the value. The temporary CouldNotCompute value tells SCEV
8340 // existing SCEV values for PHI nodes in this loop since they are only
8346 SmallVector<const SCEV *, 8> ToForget;
8393 SmallVectorImpl<const SCEV *> &ToForget) {
8416 SmallVector<const SCEV *, 16> ToForget;
8418 // Iterate over all the loops and sub-loops to drop SCEV information.
8426 // Drop information about predicated SCEV rewrites for this loop.
8429 std::pair<const SCEV *, const Loop *> Entry = I->first;
8465 SmallVector<const SCEV *, 8> ToForget;
8477 // If SCEV looked through a trivial LCSSA phi node, we might have SCEV's
8480 // AddRecs defined in the loop and invalidate any SCEV's making use of them.
8481 if (const SCEV *S = getExistingSCEV(V)) {
8484 SmallVector<const SCEV *, 8> Roots;
8488 bool follow(const SCEV *S) {
8525 const SCEV *S = getExistingSCEV(V);
8533 SmallVector<const SCEV *, 8> Worklist = {S};
8534 SmallPtrSet<const SCEV *, 8> Seen = {S};
8536 const SCEV *Curr = Worklist.pop_back_val();
8555 const SCEV *
8569 SmallVector<const SCEV *, 2> Ops;
8571 const SCEV *BECount = ENT.ExactNotTaken;
8572 assert(BECount != SE->getCouldNotCompute() && "Bad exit SCEV!");
8594 const SCEV *
8604 const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8613 const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8623 const SCEV *
8638 const SCEV *
8654 ScalarEvolution::ExitLimit::ExitLimit(const SCEV *E)
8658 const SCEV *E, const SCEV *ConstantMaxNotTaken,
8659 const SCEV *SymbolicMaxNotTaken, bool MaxOrZero,
8694 const SCEV *E, const SCEV *ConstantMaxNotTaken,
8695 const SCEV *SymbolicMaxNotTaken, bool MaxOrZero,
8704 bool IsComplete, const SCEV *ConstantMax, bool MaxOrZero)
8735 const SCEV *MustExitMaxBECount = nullptr;
8736 const SCEV *MayExitMaxBECount = nullptr;
8807 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
8939 // Try again, but use SCEV predicates this time.
9017 const SCEV *BECount = getCouldNotCompute();
9018 const SCEV *ConstantMaxBECount = getCouldNotCompute();
9019 const SCEV *SymbolicMaxBECount = getCouldNotCompute();
9077 const SCEV *LHS = getSCEV(ExitCond->getOperand(0));
9078 const SCEV *RHS = getSCEV(ExitCond->getOperand(1));
9095 const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
9124 const SCEV *Ret = AddRec->getNumIterationsInRange(CompRange, *this);
9144 Flags = setFlags(Flags, SCEV::FlagNW);
9145 SmallVector<const SCEV*> Operands{AR->operands()};
9243 const SCEV *LHS = getSCEVAtScope(Switch->getCondition(), L);
9244 const SCEV *RHS = getConstant(Switch->findCaseDest(ExitingBlock));
9257 const SCEV *InVal = SE.getConstant(C);
9258 const SCEV *Val = AddRec->evaluateAtIteration(InVal, SE);
9260 "Evaluation of SCEV at constant didn't fold correctly?");
9399 const SCEV *UpperBound =
9648 const SCEV *ScalarEvolution::computeExitCountExhaustively(const Loop *L,
9715 const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) {
9716 SmallVector<std::pair<const Loop *, const SCEV *>, 2> &Values =
9726 const SCEV *C = computeSCEVAtScope(V, L);
9740 /// Returns NULL if the SCEV isn't representable as a Constant.
9741 static Constant *BuildConstantFromSCEV(const SCEV *V) {
9767 for (const SCEV *Op : SA->operands()) {
9799 llvm_unreachable("Unknown SCEV kind!");
9802 const SCEV *
9803 ScalarEvolution::getWithOperands(const SCEV *S,
9804 SmallVectorImpl<const SCEV *> &NewOps) {
9835 llvm_unreachable("Unknown SCEV kind!");
9838 const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) {
9851 const SCEV *OpAtScope = getSCEVAtScope(AddRec->getOperand(i), L);
9857 SmallVector<const SCEV *, 8> NewOps;
9864 const SCEV *FoldedRec = getAddRecExpr(
9865 NewOps, AddRec->getLoop(), AddRec->getNoWrapFlags(SCEV::FlagNW));
9880 const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
9902 ArrayRef<const SCEV *> Ops = V->operands();
9906 const SCEV *OpAtScope = getSCEVAtScope(Ops[i], L);
9910 SmallVector<const SCEV *, 8> NewOps;
9943 const SCEV *BackedgeTakenCount = getBackedgeTakenCount(CurrLoop);
9987 // into a SCEV. Check to see if it's possible to symbolically evaluate
10008 const SCEV *OrigV = getSCEV(Op);
10009 const SCEV *OpV = getSCEVAtScope(OrigV, L);
10033 llvm_unreachable("Unknown SCEV type!");
10036 const SCEV *ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) {
10040 const SCEV *ScalarEvolution::stripInjectiveFunctions(const SCEV *S) const {
10056 static const SCEV *SolveLinEquationWithOverflow(const APInt &A, const SCEV *B,
10091 const SCEV *D = SE.getConstant(APInt::getOneBitSet(BW, Mult2));
10368 ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(const SCEV *V,
10391 // iterations of this loop, where X is the SCEV expression found by the
10427 const SCEV *Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
10428 const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop());
10446 const SCEV *Distance = CountDown ? Start : getNegativeSCEV(Start);
10462 const SCEV *Zero = getZero(Distance->getType());
10463 const SCEV *One = getOne(Distance->getType());
10464 const SCEV *DistancePlusOne = getAddExpr(Distance, One);
10482 const SCEV *Exact =
10484 const SCEV *ConstantMax = getCouldNotCompute();
10490 const SCEV *SymbolicMax =
10496 const SCEV *E = SolveLinEquationWithOverflow(StepC->getAPInt(),
10499 const SCEV *M = E;
10509 ScalarEvolution::howFarToNonZero(const SCEV *V, const Loop *L) {
10545 /// SCEV structural equivalence is usually sufficient for testing whether two
10549 static bool HasSameValue(const SCEV *A, const SCEV *B) {
10550 // Quick check to see if they are the same SCEV.
10574 const SCEV *&LHS, const SCEV *&RHS,
10708 SCEV::FlagNSW);
10713 SCEV::FlagNSW);
10721 SCEV::FlagNSW);
10726 SCEV::FlagNSW);
10734 SCEV::FlagNUW);
10750 SCEV::FlagNUW);
10769 bool ScalarEvolution::isKnownNegative(const SCEV *S) {
10773 bool ScalarEvolution::isKnownPositive(const SCEV *S) {
10777 bool ScalarEvolution::isKnownNonNegative(const SCEV *S) {
10781 bool ScalarEvolution::isKnownNonPositive(const SCEV *S) {
10785 bool ScalarEvolution::isKnownNonZero(const SCEV *S) {
10793 std::pair<const SCEV *, const SCEV *>
10794 ScalarEvolution::SplitIntoInitAndPostInc(const Loop *L, const SCEV *S) {
10795 // Compute SCEV on entry of loop L.
10796 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *this);
10799 // Compute post increment SCEV for loop L.
10800 const SCEV *PostInc = SCEVPostIncRewriter::rewrite(S, L, *this);
10806 const SCEV *LHS, const SCEV *RHS) {
10832 // if LHS contains unknown non-invariant SCEV then bail out.
10838 // if RHS contains unknown non-invariant SCEV then bail out.
10842 // It is possible that init SCEV contains an invariant load but it does
10857 const SCEV *LHS, const SCEV *RHS) {
10872 const SCEV *LHS,
10873 const SCEV *RHS) {
10882 const SCEV *LHS, const SCEV *RHS,
10890 ScalarEvolution::evaluatePredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS,
10891 const SCEV *RHS, const Instruction *CtxI) {
10907 const SCEV *RHS) {
10943 // where SCEV can prove X >= 0 but not prove X > 0, so it is helpful to be
10965 const SCEV *Step = LHS->getStepRecurrence(*this);
10978 const SCEV *LHS, const SCEV *RHS,
11064 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L,
11065 const Instruction *CtxI, const SCEV *MaxIter) {
11084 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L,
11085 const Instruction *CtxI, const SCEV *MaxIter) {
11112 const SCEV *Step = AR->getStepRecurrence(*this);
11125 const SCEV *Last = AR->evaluateAtIteration(MaxIter, *this);
11138 const SCEV *Start = AR->getStart();
11147 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS) {
11189 const SCEV *LHS,
11190 const SCEV *RHS) {
11195 auto MatchBinaryAddToConst = [this](const SCEV *X, const SCEV *Y,
11197 SCEV::NoWrapFlags ExpectedFlags) {
11198 const SCEV *XNonConstOp, *XConstOp;
11199 const SCEV *YNonConstOp, *YConstOp;
11200 SCEV::NoWrapFlags XFlagsPresent;
11201 SCEV::NoWrapFlags YFlagsPresent;
11243 if (MatchBinaryAddToConst(LHS, RHS, C1, C2, SCEV::FlagNSW) && C1.sle(C2))
11253 if (MatchBinaryAddToConst(LHS, RHS, C1, C2, SCEV::FlagNSW) && C1.slt(C2))
11263 if (MatchBinaryAddToConst(RHS, LHS, C2, C1, SCEV::FlagNUW) && C1.ule(C2))
11273 if (MatchBinaryAddToConst(RHS, LHS, C2, C1, SCEV::FlagNUW) && C1.ult(C2))
11282 const SCEV *LHS,
11283 const SCEV *RHS) {
11305 const SCEV *LHS, const SCEV *RHS) {
11326 const SCEV *LHS, const SCEV *RHS) {
11362 const SCEV *LatchBECount = BETakenInfo.getExact(Latch, this);
11368 auto NoWrapFlags = SCEV::NoWrapFlags(SCEV::FlagNUW | SCEV::FlagNW);
11369 const SCEV *LoopCounter =
11431 const SCEV *LHS,
11432 const SCEV *RHS) {
11531 const SCEV *LHS,
11532 const SCEV *RHS) {
11550 bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS,
11551 const SCEV *RHS,
11588 const SCEV *FoundLHS = getSCEV(ICI->getOperand(0));
11589 const SCEV *FoundRHS = getSCEV(ICI->getOperand(1));
11594 bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS,
11595 const SCEV *RHS,
11597 const SCEV *FoundLHS, const SCEV *FoundRHS,
11610 const SCEV *MaxValue = getZeroExtendExpr(
11616 const SCEV *TruncFoundLHS = getTruncateExpr(FoundLHS, NarrowType);
11617 const SCEV *TruncFoundRHS = getTruncateExpr(FoundRHS, NarrowType);
11650 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
11651 ICmpInst::Predicate FoundPred, const SCEV *FoundLHS, const SCEV *FoundRHS,
11730 const SCEV *CanonicalLHS = LHS, *CanonicalRHS = RHS,
11764 const SCEV *V = nullptr;
11853 bool ScalarEvolution::splitBinaryAdd(const SCEV *Expr,
11854 const SCEV *&L, const SCEV *&R,
11855 SCEV::NoWrapFlags &Flags) {
11867 ScalarEvolution::computeConstantDifference(const SCEV *More, const SCEV *Less) {
11902 SCEV::NoWrapFlags Flags;
11903 const SCEV *LLess = nullptr, *RLess = nullptr;
11904 const SCEV *LMore = nullptr, *RMore = nullptr;
11926 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
11927 const SCEV *FoundLHS, const SCEV *FoundRHS, const Instruction *CtxI) {
11971 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
11972 const SCEV *FoundLHS, const SCEV *FoundRHS) {
11984 // We'd like to let SCEV reason about control dependencies, so we constrain
12048 const SCEV *LHS, const SCEV *RHS,
12049 const SCEV *FoundLHS,
12050 const SCEV *FoundRHS, unsigned Depth) {
12104 auto ProvedEasily = [&](const SCEV *S1, const SCEV *S2) {
12116 const SCEV *L = getSCEV(LPhi->getIncomingValueForBlock(IncBB));
12117 const SCEV *R = getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12132 const SCEV *L1 = getSCEV(LPhi->getIncomingValueForBlock(Predecessor));
12137 const SCEV *L2 = getSCEV(LPhi->getIncomingValueForBlock(Latch));
12149 const SCEV *L = getSCEV(LPhi->getIncomingValueForBlock(IncBB));
12162 const SCEV *LHS,
12163 const SCEV *RHS,
12164 const SCEV *FoundLHS,
12165 const SCEV *FoundRHS) {
12204 const SCEV *LHS, const SCEV *RHS,
12205 const SCEV *FoundLHS,
12206 const SCEV *FoundRHS,
12227 static bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr,
12228 const SCEV *Candidate) {
12238 const SCEV *LHS, const SCEV *RHS) {
12260 SCEV::NoWrapFlags NW = ICmpInst::isSigned(Pred) ?
12261 SCEV::FlagNSW : SCEV::FlagNUW;
12272 const SCEV *LHS, const SCEV *RHS) {
12303 const SCEV *LHS, const SCEV *RHS,
12304 const SCEV *FoundLHS,
12305 const SCEV *FoundRHS,
12333 const SCEV *MinusOne = getMinusOne(LHS->getType());
12344 auto GetOpFromSExt = [&](const SCEV *S) {
12359 auto IsSGTViaContext = [&](const SCEV *S1, const SCEV *S2) {
12366 // We want to avoid creation of any new non-constant SCEV. Since we are
12383 auto IsSumGreaterThanRHS = [&](const SCEV *S1, const SCEV *S2) {
12400 // derivative expressions. In general case, creating a SCEV for it may
12412 // then a SCEV for the numerator already exists and matches with FoundLHS.
12471 const SCEV *LHS, const SCEV *RHS) {
12504 const SCEV *LHS, const SCEV *RHS) {
12514 const SCEV *LHS, const SCEV *RHS,
12515 const SCEV *FoundLHS,
12516 const SCEV *FoundRHS) {
12558 const SCEV *LHS,
12559 const SCEV *RHS,
12561 const SCEV *FoundLHS,
12562 const SCEV *FoundRHS) {
12590 bool ScalarEvolution::canIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride,
12595 const SCEV *One = getOne(Stride->getType());
12614 bool ScalarEvolution::canIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride,
12618 const SCEV *One = getOne(Stride->getType());
12637 const SCEV *ScalarEvolution::getUDivCeilSCEV(const SCEV *N, const SCEV *D) {
12641 const SCEV *MinNOne = getUMinExpr(N, getOne(N->getType()));
12642 const SCEV *NMinusOne = getMinusSCEV(N, MinNOne);
12646 const SCEV *ScalarEvolution::computeMaxBECountForLT(const SCEV *Start,
12647 const SCEV *Stride,
12648 const SCEV *End,
12696 ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,
12764 if (!hasFlags(Flags, SCEV::FlagNUW) && canProveNUW())
12765 Flags = setFlags(Flags, SCEV::FlagNUW);
12771 const SCEV *Step = AR->getStepRecurrence(*this);
12785 // iterations of this loop, where X is the SCEV expression found by the
12805 auto WrapType = IsSigned ? SCEV::FlagNSW : SCEV::FlagNUW;
12809 const SCEV *Stride = IV->getStepRecurrence(*this);
12909 const SCEV *Start = IV->getStart();
12915 const SCEV *OrigStart = Start;
12916 const SCEV *OrigRHS = RHS;
12934 const SCEV *MaxBECount = computeMaxBECountForLT(
12944 const SCEV *BECount = nullptr;
12970 const SCEV *MinusOne = getMinusOne(Stride->getType());
12971 const SCEV *Numerator =
12976 const SCEV *BECountIfBackedgeTaken = nullptr;
12980 const SCEV *GuardedRHS = applyLoopGuards(OrigRHS, L);
12981 const SCEV *GuardedStart = applyLoopGuards(OrigStart, L);
13004 const SCEV *End;
13013 // We convert it to the following to make it more convenient for SCEV:
13034 const SCEV *One = getOne(Stride->getType());
13093 const SCEV *Delta = getMinusSCEV(End, Start);
13104 const SCEV *ConstantMaxBECount;
13124 const SCEV *SymbolicMaxBECount =
13131 const SCEV *LHS, const SCEV *RHS, const Loop *L, bool IsSigned,
13141 // iterations of this loop, where X is the SCEV expression found by the
13149 auto WrapType = IsSigned ? SCEV::FlagNSW : SCEV::FlagNUW;
13153 const SCEV *Stride = getNegativeSCEV(IV->getStepRecurrence(*this));
13167 const SCEV *Start = IV->getStart();
13168 const SCEV *End = RHS;
13193 const SCEV *One = getOne(Stride->getType());
13194 const SCEV *BECount = getUDivExpr(
13214 const SCEV *ConstantMaxBECount =
13222 const SCEV *SymbolicMaxBECount =
13229 const SCEV *SCEVAddRecExpr::getNumIterationsInRange(const ConstantRange &Range,
13237 SmallVector<const SCEV *, 4> Operands(operands());
13239 const SCEV *Shifted = SE.getAddRecExpr(Operands, getLoop(),
13250 if (any_of(operands(), [](const SCEV *Op) { return !isa<SCEVConstant>(Op); }))
13305 // AddRec because SCEV does not have a fixed point where it stops
13309 SmallVector<const SCEV *, 3> Ops;
13318 const SCEV *Last = getOperand(getNumOperands() - 1);
13322 SCEV::FlagAnyWrap));
13326 bool ScalarEvolution::containsUndefs(const SCEV *S) const {
13327 return SCEVExprContains(S, [](const SCEV *S) {
13335 bool ScalarEvolution::containsErasedValue(const SCEV *S) const {
13336 return SCEVExprContains(S, [](const SCEV *S) {
13344 const SCEV *ScalarEvolution::getElementSize(Instruction *Inst) {
13583 // out SCEV values of all instructions that are interesting. Doing
13584 // this potentially causes it to create new SCEV objects though,
13598 const SCEV *SV = SE.getSCEV(&I);
13609 const SCEV *AtUse = SE.getSCEVAtScope(SV, L);
13623 const SCEV *ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop());
13672 ScalarEvolution::getLoopDisposition(const SCEV *S, const Loop *L) {
13691 ScalarEvolution::computeLoopDisposition(const SCEV *S, const Loop *L) {
13759 llvm_unreachable("Unknown SCEV kind!");
13762 bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) {
13766 bool ScalarEvolution::hasComputableLoopEvolution(const SCEV *S, const Loop *L) {
13771 ScalarEvolution::getBlockDisposition(const SCEV *S, const BasicBlock *BB) {
13790 ScalarEvolution::computeBlockDisposition(const SCEV *S, const BasicBlock *BB) {
13820 for (const SCEV *NAryOp : S->operands()) {
13842 llvm_unreachable("Unknown SCEV kind!");
13845 bool ScalarEvolution::dominates(const SCEV *S, const BasicBlock *BB) {
13849 bool ScalarEvolution::properlyDominates(const SCEV *S, const BasicBlock *BB) {
13853 bool ScalarEvolution::hasOperand(const SCEV *S, const SCEV *Op) const {
13854 return SCEVExprContains(S, [&](const SCEV *Expr) { return Expr == Op; });
13864 for (const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
13876 void ScalarEvolution::forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs) {
13877 SmallPtrSet<const SCEV *, 8> ToForget(SCEVs.begin(), SCEVs.end());
13878 SmallVector<const SCEV *, 8> Worklist(ToForget.begin(), ToForget.end());
13881 const SCEV *Curr = Worklist.pop_back_val();
13894 std::pair<const SCEV *, const Loop *> Entry = I->first;
13902 void ScalarEvolution::forgetMemoizedResultsImpl(const SCEV *S) {
13958 ScalarEvolution::getUsedLoops(const SCEV *S,
13964 bool follow(const SCEV *S) {
13996 const SCEV *L = getSCEV(Cmp->getOperand(0));
13997 const SCEV *R = getSCEV(Cmp->getOperand(1));
14020 // Map's SCEV expressions from one ScalarEvolution "universe" to another.
14024 const SCEV *visitConstant(const SCEVConstant *Constant) {
14028 const SCEV *visitUnknown(const SCEVUnknown *Expr) {
14032 const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
14041 auto GetDelta = [&](const SCEV *Old, const SCEV *New) -> const SCEV * {
14043 // SCEV treats "undef" as an unknown but consistent value (i.e. it does
14047 // result is "undef", but SCEV thinks the value increased by 1.
14052 const SCEV *Delta = SE2.getMinusSCEV(Old, New);
14069 // results of subsequent SCEV uses.
14082 // computable or vice-versa *should have* invalidated SCEV. However, we
14095 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14115 // Check for SCEV expressions referencing invalid/deleted loops.
14133 const SCEV *OldSCEV = SCM.visit(KV.second);
14134 const SCEV *NewSCEV = SE2.getSCEV(I);
14135 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14137 dbgs() << "SCEV for value " << *I << " changed!\n"
14162 // Verify integrity of SCEV users.
14179 const SCEV *Value = ValueAndVec.first;
14182 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
14196 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14199 const SCEV *Value = LoopAndValue.second;
14217 for (const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14392 const SCEVPredicate *ScalarEvolution::getEqualPredicate(const SCEV *LHS,
14393 const SCEV *RHS) {
14399 const SCEV *LHS, const SCEV *RHS) {
14439 /// Rewrites \p S in the context of a loop L and the SCEV predication
14442 /// If \p Pred is non-null, the SCEV expression is rewritten to respect the
14447 static const SCEV *rewrite(const SCEV *S, const Loop *L, ScalarEvolution &SE,
14454 const SCEV *visitUnknown(const SCEVUnknown *Expr) {
14471 const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
14472 const SCEV *Operand = visit(Expr->getOperand());
14477 const SCEV *Step = AR->getStepRecurrence(SE);
14487 const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
14488 const SCEV *Operand = visit(Expr->getOperand());
14493 const SCEV *Step = AR->getStepRecurrence(SE);
14530 const SCEV *convertToAddRecWithPreds(const SCEVUnknown *Expr) {
14534 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
14557 const SCEV *
14558 ScalarEvolution::rewriteUsingPredicate(const SCEV *S, const Loop *L,
14564 const SCEV *S, const Loop *L,
14573 // Since the transformation was successful, we can now transfer the SCEV
14581 /// SCEV predicates
14588 const SCEV *LHS, const SCEV *RHS)
14591 assert(LHS != RHS && "LHS and RHS are the same SCEV");
14631 SCEV::NoWrapFlags ScevFlags = AR->getNoWrapFlags();
14634 if (ScalarEvolution::setFlags(ScevFlags, SCEV::FlagNSW) == ScevFlags)
14653 SCEV::NoWrapFlags StaticFlags = AR->getNoWrapFlags();
14656 if (ScalarEvolution::setFlags(StaticFlags, SCEV::FlagNSW) == StaticFlags)
14659 if (ScalarEvolution::setFlags(StaticFlags, SCEV::FlagNUW) == StaticFlags) {
14660 // If the increment is positive, the SCEV NUW flag will also imply the
14713 void ScalarEvolution::registerUser(const SCEV *User,
14714 ArrayRef<const SCEV *> Ops) {
14723 const SCEV *PredicatedScalarEvolution::getSCEV(Value *V) {
14724 const SCEV *Expr = SE.getSCEV(V);
14736 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
14742 const SCEV *PredicatedScalarEvolution::getBackedgeTakenCount() {
14771 const SCEV *Rewritten = II.second.second;
14779 const SCEV *Expr = getSCEV(V);
14795 const SCEV *Expr = getSCEV(V);
14810 const SCEV *Expr = this->getSCEV(V);
14861 bool ScalarEvolution::matchURem(const SCEV *Expr, const SCEV *&LHS,
14862 const SCEV *&RHS) {
14884 const SCEV *A = Add->getOperand(1);
14890 const auto MatchURemWithDivisor = [&](const SCEV *B) {
14914 const SCEV *
14922 SmallVector<const SCEV*, 4> ExitCounts;
14924 const SCEV *ExitCount =
14938 /// A rewriter to replace SCEV expressions in Map with the corresponding entry
14942 const DenseMap<const SCEV *, const SCEV *> ⤅
14946 DenseMap<const SCEV *, const SCEV *> &M)
14949 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { return Expr; }
14951 const SCEV *visitUnknown(const SCEVUnknown *Expr) {
14958 const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
14964 const SCEV *Op = Expr->getOperand(0);
14982 const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
14990 const SCEV *visitUMinExpr(const SCEVUMinExpr *Expr) {
14997 const SCEV *visitSMinExpr(const SCEVSMinExpr *Expr) {
15005 const SCEV *ScalarEvolution::applyLoopGuards(const SCEV *Expr, const Loop *L) {
15006 SmallVector<const SCEV *> ExprsToRewrite;
15007 auto CollectCondition = [&](ICmpInst::Predicate Predicate, const SCEV *LHS,
15008 const SCEV *RHS,
15009 DenseMap<const SCEV *, const SCEV *>
15012 // replacement SCEV which isn't directly implied by the structure of that
15013 // SCEV. In particular, using contextual facts to imply flags is *NOT*
15045 const SCEV *RewrittenLHS = I != RewriteMap.end() ? I->second : LHSUnknown;
15055 // Return true if \p Expr is a MinMax SCEV expression with a non-negative
15056 // constant operand. If so, return in \p SCTy the SCEV type and in \p RHS
15059 [&](const SCEV *Expr, SCEVTypes &SCTy, const SCEV *&LHS,
15060 const SCEV *&RHS) {
15078 auto GetNonNegExprAndPosDivisor = [&](const SCEV *Expr, const SCEV *Divisor,
15089 // Return a new SCEV that modifies \p Expr to the closest number divides by
15092 auto GetNextSCEVDividesByDivisor = [&](const SCEV *Expr,
15093 const SCEV *Divisor) {
15100 // return the SCEV: Expr + Divisor - Expr % Divisor
15105 // Return a new SCEV that modifies \p Expr to the closest number divides by
15108 auto GetPreviousSCEVDividesByDivisor = [&](const SCEV *Expr,
15109 const SCEV *Divisor) {
15115 // return the SCEV: Expr - Expr % Divisor
15122 std::function<const SCEV *(const SCEV *, const SCEV *)>
15123 ApplyDivisibiltyOnMinMaxExpr = [&](const SCEV *MinMaxExpr,
15124 const SCEV *Divisor) {
15125 const SCEV *MinMaxLHS = nullptr, *MinMaxRHS = nullptr;
15137 SmallVector<const SCEV *> Ops = {
15143 // SCEV %v which we can rewrite %v to express explicitly.
15149 const SCEV *URemLHS = nullptr;
15150 const SCEV *URemRHS = nullptr;
15154 const SCEV *RewrittenLHS =
15180 auto AddRewrite = [&](const SCEV *From, const SCEV *FromRewritten,
15181 const SCEV *To) {
15190 auto GetMaybeRewritten = [&](const SCEV *S) {
15195 // Check for the SCEV expression (A /u B) * B while B is a constant, inside
15197 // be a composition of Min/Max SCEVs. Return whether the SCEV expression (A
15200 // (A /u 8) * 8 matched the pattern, and return the constant SCEV 8 in \p
15202 std::function<bool(const SCEV *, const SCEV *&)> HasDivisibiltyInfo =
15203 [&](const SCEV *Expr, const SCEV *&DividesBy) {
15224 std::function<bool(const SCEV *, const SCEV *&)> IsKnownToDivideBy =
15225 [&](const SCEV *Expr, const SCEV *DividesBy) {
15234 const SCEV *RewrittenLHS = GetMaybeRewritten(LHS);
15235 const SCEV *DividesBy = nullptr;
15249 // We cannot express strict predicates in SCEV, so instead we replace them
15252 const SCEV *One = getOne(RHS->getType());
15281 SmallVector<const SCEV *, 16> Worklist(1, LHS);
15282 SmallPtrSet<const SCEV *, 16> Visited;
15289 const SCEV *From = Worklist.pop_back_val();
15294 const SCEV *FromRewritten = GetMaybeRewritten(From);
15295 const SCEV *To = nullptr;
15329 const SCEV *OneAlignedUp =
15386 DenseMap<const SCEV *, const SCEV *> RewriteMap;
15421 for (const SCEV *Expr : ExprsToRewrite) {
15422 const SCEV *RewriteTo = RewriteMap[Expr];