Lines Matching +full:local +full:- +full:bd +full:- +full:address +full:- +full:broken
1 //===- ScalarEvolution.cpp - Scalar Evolution Analysis --------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
17 // pointer-comparisons for equality are legal.
31 // higher-level code, such as the code that recognizes PHI nodes of various
37 //===----------------------------------------------------------------------===//
41 // Chains of recurrences -- a method to expedite the evaluation
42 // of closed-form functions
58 //===----------------------------------------------------------------------===//
84 #include "llvm/Config/llvm-config.h"
137 #define DEBUG_TYPE "scalar-evolution"
153 MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,
160 "verify-scev", cl::Hidden, cl::location(VerifySCEV),
163 "verify-scev-strict", cl::Hidden,
164 cl::desc("Enable stricter verification with -verify-scev is passed"));
167 "scev-verify-ir", cl::Hidden,
172 "scev-mulops-inline-threshold", cl::Hidden,
177 "scev-addops-inline-threshold", cl::Hidden,
182 "scalar-evolution-max-scev-compare-depth", cl::Hidden,
187 "scalar-evolution-max-scev-operations-implication-depth", cl::Hidden,
192 "scalar-evolution-max-value-compare-depth", cl::Hidden,
197 MaxArithDepth("scalar-evolution-max-arith-depth", cl::Hidden,
202 "scalar-evolution-max-constant-evolving-depth", cl::Hidden,
206 MaxCastDepth("scalar-evolution-max-cast-depth", cl::Hidden,
211 MaxAddRecSize("scalar-evolution-max-add-rec-size", cl::Hidden,
216 HugeExprThreshold("scalar-evolution-huge-expr-threshold", cl::Hidden,
221 "scev-range-iter-threshold", cl::Hidden,
226 ClassifyExpressions("scalar-evolution-classify-expressions",
231 "scalar-evolution-use-expensive-range-sharpening", cl::Hidden,
237 "scalar-evolution-max-scc-analysis-depth", cl::Hidden,
243 EnableFiniteLoopControl("scalar-evolution-finite-loop", cl::Hidden,
248 "scalar-evolution-use-context-for-no-wrap-flag-strenghening", cl::Hidden,
252 //===----------------------------------------------------------------------===//
254 //===----------------------------------------------------------------------===//
256 //===----------------------------------------------------------------------===//
270 cast<SCEVConstant>(this)->getValue()->printAsOperand(OS, false);
277 const SCEV *Op = PtrToInt->getOperand();
278 OS << "(ptrtoint " << *Op->getType() << " " << *Op << " to "
279 << *PtrToInt->getType() << ")";
284 const SCEV *Op = Trunc->getOperand();
285 OS << "(trunc " << *Op->getType() << " " << *Op << " to "
286 << *Trunc->getType() << ")";
291 const SCEV *Op = ZExt->getOperand();
292 OS << "(zext " << *Op->getType() << " " << *Op << " to "
293 << *ZExt->getType() << ")";
298 const SCEV *Op = SExt->getOperand();
299 OS << "(sext " << *Op->getType() << " " << *Op << " to "
300 << *SExt->getType() << ")";
305 OS << "{" << *AR->getOperand(0);
306 for (unsigned i = 1, e = AR->getNumOperands(); i != e; ++i)
307 OS << ",+," << *AR->getOperand(i);
309 if (AR->hasNoUnsignedWrap())
311 if (AR->hasNoSignedWrap())
313 if (AR->hasNoSelfWrap() &&
314 !AR->getNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)))
316 AR->getLoop()->getHeader()->printAsOperand(OS, /*PrintType=*/false);
329 switch (NAry->getSCEVType()) {
348 for (const SCEV *Op : NAry->operands())
351 switch (NAry->getSCEVType()) {
354 if (NAry->hasNoUnsignedWrap())
356 if (NAry->hasNoSignedWrap())
367 OS << "(" << *UDiv->getLHS() << " /u " << *UDiv->getRHS() << ")";
371 cast<SCEVUnknown>(this)->getValue()->printAsOperand(OS, false);
383 return cast<SCEVConstant>(this)->getType();
385 return cast<SCEVVScale>(this)->getType();
390 return cast<SCEVCastExpr>(this)->getType();
392 return cast<SCEVAddRecExpr>(this)->getType();
394 return cast<SCEVMulExpr>(this)->getType();
399 return cast<SCEVMinMaxExpr>(this)->getType();
401 return cast<SCEVSequentialMinMaxExpr>(this)->getType();
403 return cast<SCEVAddExpr>(this)->getType();
405 return cast<SCEVUDivExpr>(this)->getType();
407 return cast<SCEVUnknown>(this)->getType();
424 return cast<SCEVCastExpr>(this)->operands();
433 return cast<SCEVNAryExpr>(this)->operands();
435 return cast<SCEVUDivExpr>(this)->operands();
444 return SC->getValue()->isZero();
450 return SC->getValue()->isOne();
456 return SC->getValue()->isMinusOne();
465 const SCEVConstant *SC = dyn_cast<SCEVConstant>(Mul->getOperand(0));
468 // Return true if the value is negative, this matches things like (-42 * V).
469 return SC->getAPInt().isNegative();
476 return S->getSCEVType() == scCouldNotCompute;
526 assert(getOperand()->getType()->isPointerTy() && Ty->isIntegerTy() &&
527 "Must be a non-bit-width-changing pointer-to-integer cast!");
538 assert(getOperand()->getType()->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
539 "Cannot truncate non-integer value!");
545 assert(getOperand()->getType()->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
546 "Cannot zero extend non-integer value!");
552 assert(getOperand()->getType()->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
553 "Cannot sign extend non-integer value!");
558 SE->forgetMemoizedResults(this);
561 SE->UniqueSCEVs.RemoveNode(this);
569 SE->forgetMemoizedResults(this);
572 SE->UniqueSCEVs.RemoveNode(this);
578 //===----------------------------------------------------------------------===//
580 //===----------------------------------------------------------------------===//
583 /// "complexity" is a partial (and somewhat ad-hoc) relation used to order
609 bool LIsPointer = LV->getType()->isPointerTy(),
610 RIsPointer = RV->getType()->isPointerTy();
612 return (int)LIsPointer - (int)RIsPointer;
615 unsigned LID = LV->getValueID(), RID = RV->getValueID();
617 return (int)LID - (int)RID;
622 unsigned LArgNo = LA->getArgNo(), RArgNo = RA->getArgNo();
623 return (int)LArgNo - (int)RArgNo;
630 auto LT = GV->getLinkage();
638 return LGV->getName().compare(RGV->getName());
647 const BasicBlock *LParent = LInst->getParent(),
648 *RParent = RInst->getParent();
650 unsigned LDepth = LI->getLoopDepth(LParent),
651 RDepth = LI->getLoopDepth(RParent);
653 return (int)LDepth - (int)RDepth;
657 unsigned LNumOps = LInst->getNumOperands(),
658 RNumOps = RInst->getNumOperands();
660 return (int)LNumOps - (int)RNumOps;
664 CompareValueComplexity(EqCacheValue, LI, LInst->getOperand(Idx),
665 RInst->getOperand(Idx), Depth + 1);
676 // than RHS, respectively. A three-way result allows recursive comparisons to be
685 // Fast-path: SCEVs are uniqued so we can do a quick equality check.
690 SCEVTypes LType = LHS->getSCEVType(), RType = RHS->getSCEVType();
692 return (int)LType - (int)RType;
708 int X = CompareValueComplexity(EqCacheValue, LI, LU->getValue(),
709 RU->getValue(), Depth + 1);
720 const APInt &LA = LC->getAPInt();
721 const APInt &RA = RC->getAPInt();
724 return (int)LBitWidth - (int)RBitWidth;
725 return LA.ult(RA) ? -1 : 1;
729 const auto *LTy = cast<IntegerType>(cast<SCEVVScale>(LHS)->getType());
730 const auto *RTy = cast<IntegerType>(cast<SCEVVScale>(RHS)->getType());
731 return LTy->getBitWidth() - RTy->getBitWidth();
741 const Loop *LLoop = LA->getLoop(), *RLoop = RA->getLoop();
743 const BasicBlock *LHead = LLoop->getHeader(), *RHead = RLoop->getHeader();
749 return -1;
767 ArrayRef<const SCEV *> LOps = LHS->operands();
768 ArrayRef<const SCEV *> ROps = RHS->operands();
770 // Lexicographically compare n-ary-like expressions.
773 return (int)LNumOps - (int)RNumOps;
831 for (unsigned i = 0, e = Ops.size(); i != e-2; ++i) {
833 unsigned Complexity = S->getSCEVType();
837 for (unsigned j = i+1; j != e && Ops[j]->getSCEVType() == Complexity; ++j) {
842 if (i == e-2) return; // Done!
852 return S->getExpressionSize() >= HugeExprThreshold;
856 //===----------------------------------------------------------------------===//
858 //===----------------------------------------------------------------------===//
870 // BC(It, K) = (It * (It - 1) * ... * (It - K + 1)) / K!
882 // BC(It, K) = (It * (It - 1) * ... * (It - K + 1)) / 2^T / (K! / 2^T)
913 // It/2*(It+(It*INT_MIN/INT_MIN)+-1). However, it requires
952 const SCEV *S = SE.getMinusSCEV(It, SE.getConstant(It->getType(), i));
988 const SCEV *Coeff = BinomialCoefficient(It, i, SE, Result->getType());
997 //===----------------------------------------------------------------------===//
999 //===----------------------------------------------------------------------===//
1004 "getLosslessPtrToIntExpr() should self-recurse at most once.");
1006 // We could be called with an integer-typed operands during SCEV rewrites.
1008 if (!Op->getType()->isPointerTy())
1023 // for non-integral pointers.
1024 if (getDataLayout().isNonIntegralPointerType(Op->getType()))
1027 Type *IntPtrTy = getDataLayout().getIntPtrType(Op->getType());
1033 if (getDataLayout().getTypeSizeInBits(getEffectiveSCEVType(Op->getType())) !=
1041 // left as-is), but produce a zero constant.
1043 if (isa<ConstantPointerNull>(U->getValue()))
1056 assert(Depth == 0 && "getLosslessPtrToIntExpr() should not self-recurse for "
1057 "non-SCEVUnknown's.");
1062 // only, and the expressions must otherwise be integer-typed.
1066 /// which computes a pointer-typed value, and rewrites the whole expression
1068 /// pointer-typed operands in the expression are SCEVUnknown.
1082 Type *STy = S->getType();
1083 // If the expression is not pointer-typed, just keep it as-is.
1084 if (!STy->isPointerTy())
1093 for (const auto *Op : Expr->operands()) {
1097 return !Changed ? Expr : SE.getAddExpr(Operands, Expr->getNoWrapFlags());
1103 for (const auto *Op : Expr->operands()) {
1107 return !Changed ? Expr : SE.getMulExpr(Operands, Expr->getNoWrapFlags());
1111 assert(Expr->getType()->isPointerTy() &&
1112 "Should only reach pointer-typed SCEVUnknown's.");
1119 assert(IntOp->getType()->isIntegerTy() &&
1121 "and ending up with an integer-typed expression!");
1126 assert(Ty->isIntegerTy() && "Target type must be an integer type!");
1137 assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) &&
1141 assert(!Op->getType()->isPointerTy() && "Can't truncate pointer!");
1154 cast<ConstantInt>(ConstantExpr::getTrunc(SC->getValue(), Ty)));
1156 // trunc(trunc(x)) --> trunc(x)
1158 return getTruncateExpr(ST->getOperand(), Ty, Depth + 1);
1160 // trunc(sext(x)) --> sext(x) if widening or trunc(x) if narrowing
1162 return getTruncateOrSignExtend(SS->getOperand(), Ty, Depth + 1);
1164 // trunc(zext(x)) --> zext(x) if widening or trunc(x) if narrowing
1166 return getTruncateOrZeroExtend(SZ->getOperand(), Ty, Depth + 1);
1176 // trunc(x1 + ... + xN) --> trunc(x1) + ... + trunc(xN) and
1177 // trunc(x1 * ... * xN) --> trunc(x1) * ... * trunc(xN),
1184 for (unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1186 const SCEV *S = getTruncateExpr(CommOp->getOperand(i), Ty, Depth + 1);
1187 if (!isa<SCEVIntegralCastExpr>(CommOp->getOperand(i)) &&
1209 for (const SCEV *Op : AddRec->operands())
1211 return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap);
1235 unsigned BitWidth = SE->getTypeSizeInBits(Step->getType());
1236 if (SE->isKnownPositive(Step)) {
1238 return SE->getConstant(APInt::getSignedMinValue(BitWidth) -
1239 SE->getSignedRangeMax(Step));
1241 if (SE->isKnownNegative(Step)) {
1243 return SE->getConstant(APInt::getSignedMaxValue(BitWidth) -
1244 SE->getSignedRangeMin(Step));
1255 unsigned BitWidth = SE->getTypeSizeInBits(Step->getType());
1258 return SE->getConstant(APInt::getMinValue(BitWidth) -
1259 SE->getUnsignedRangeMax(Step));
1329 const Loop *L = AR->getLoop();
1330 const SCEV *Start = AR->getStart();
1331 const SCEV *Step = AR->getStepRecurrence(*SE);
1342 SmallVector<const SCEV *, 4> DiffOps(SA->operands());
1349 if (DiffOps.size() == SA->getNumOperands())
1357 ScalarEvolution::maskFlags(SA->getNoWrapFlags(), SCEV::FlagNUW);
1358 const SCEV *PreStart = SE->getAddExpr(DiffOps, PreStartFlags);
1360 SE->getAddRecExpr(PreStart, Step, L, SCEV::FlagAnyWrap));
1363 // "S+X does not sign/unsign-overflow".
1366 const SCEV *BECount = SE->getBackedgeTakenCount(L);
1367 if (PreAR && PreAR->getNoWrapFlags(WrapType) &&
1368 !isa<SCEVCouldNotCompute>(BECount) && SE->isKnownPositive(BECount))
1372 unsigned BitWidth = SE->getTypeSizeInBits(AR->getType());
1373 Type *WideTy = IntegerType::get(SE->getContext(), BitWidth * 2);
1375 SE->getAddExpr((SE->*GetExtendExpr)(PreStart, WideTy, Depth),
1376 (SE->*GetExtendExpr)(Step, WideTy, Depth));
1377 if ((SE->*GetExtendExpr)(Start, WideTy, Depth) == OperandExtendedStart) {
1378 if (PreAR && AR->getNoWrapFlags(WrapType)) {
1382 SE->setNoWrapFlags(const_cast<SCEVAddRecExpr *>(PreAR), WrapType);
1393 SE->isLoopEntryGuardedByCond(L, Pred, PreStart, OverflowLimit))
1408 return (SE->*GetExtendExpr)(AR->getStart(), Ty, Depth);
1410 return SE->getAddExpr((SE->*GetExtendExpr)(AR->getStepRecurrence(*SE), Ty,
1412 (SE->*GetExtendExpr)(PreStart, Ty, Depth));
1416 // motivating example for this rule: if we know `{0,+,4}` is `ult` `-1` and it
1421 // {S,+,X} == {S-T,+,X} + T
1422 // => Ext({S,+,X}) == Ext({S-T,+,X} + T)
1424 // If ({S-T,+,X} + T) does not overflow ... (1)
1426 // RHS == Ext({S-T,+,X} + T) == Ext({S-T,+,X}) + Ext(T)
1428 // If {S-T,+,X} does not overflow ... (2)
1430 // RHS == Ext({S-T,+,X}) + Ext(T) == {Ext(S-T),+,Ext(X)} + Ext(T)
1431 // == {Ext(S-T)+Ext(T),+,Ext(X)}
1433 // If (S-T)+T does not overflow ... (3)
1435 // RHS == {Ext(S-T)+Ext(T),+,Ext(X)} == {Ext(S-T+T),+,Ext(X)}
1441 // (3) is implied by (1) -- "(S-T)+T does not overflow" is simply "({S-T,+,X}+T)
1455 // non-constant `Start` and do a general SCEV subtraction to compute
1461 APInt StartAI = StartC->getAPInt();
1463 for (unsigned Delta : {-2, -1, 1, 2}) {
1464 const SCEV *PreStart = getConstant(StartAI - Delta);
1477 if (PreAR && PreAR->getNoWrapFlags(WrapType)) { // proves (2)
1478 const SCEV *DeltaS = getConstant(StartC->getType(), Delta);
1491 // level addition in (D + (C - D + x + y + ...)) would not wrap (signed or
1492 // unsigned) and the number of trailing zeros of (C - D + x + y + ...) is
1498 const APInt &C = ConstantTerm->getAPInt();
1502 for (unsigned I = 1, E = WholeAddExpr->getNumOperands(); I < E && TZ; ++I)
1503 TZ = std::min(TZ, SE.getMinTrailingZeros(WholeAddExpr->getOperand(I)));
1506 // guaranteeing that adding D to (C - D + x + y + ...) won't cause a wrap:
1513 // level addition in (D + {C-D,+,x}) would not wrap (signed or unsigned) and the
1514 // number of trailing zeros of (C - D + x * n) is maximized, where C is the \p
1536 auto &UserIDs = FoldCacheUser[I.first->second];
1544 I.first->second = S;
1547 R.first->second.push_back(ID);
1552 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
1556 assert(!Op->getType()->isPointerTy() && "Can't extend pointer!");
1562 return Iter->second;
1572 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
1575 assert(!Op->getType()->isPointerTy() && "Can't extend pointer!");
1579 return getConstant(SC->getAPInt().zext(getTypeSizeInBits(Ty)));
1581 // zext(zext(x)) --> zext(x)
1583 return getZeroExtendExpr(SZ->getOperand(), Ty, Depth + 1);
1601 // zext(trunc(x)) --> zext(x) or x or trunc(x)
1605 const SCEV *X = ST->getOperand();
1607 unsigned TruncBits = getTypeSizeInBits(ST->getType());
1619 if (AR->isAffine()) {
1620 const SCEV *Start = AR->getStart();
1621 const SCEV *Step = AR->getStepRecurrence(*this);
1622 unsigned BitWidth = getTypeSizeInBits(AR->getType());
1623 const Loop *L = AR->getLoop();
1627 if (AR->hasNoUnsignedWrap()) {
1631 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
1634 // Check whether the backedge-taken count is SCEVCouldNotCompute.
1637 // being called from within backedge-taken count analysis, such that
1638 // attempting to ask for the backedge-taken count would likely result
1646 // Check whether the backedge-taken count can be losslessly casted to
1649 getTruncateOrZeroExtend(MaxBECount, Start->getType(), Depth);
1651 CastedMaxBECount, MaxBECount->getType(), Depth);
1677 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
1689 // Negative step causes unsigned wrap, but it still can't self-wrap.
1695 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
1700 // Normally, in the cases we can prove no-overflow via a
1703 // guards present in the loop -- SCEV is not great at exploiting
1712 if (AR->hasNoUnsignedWrap()) {
1713 // Same as nuw case above - duplicated here to avoid a compile time
1720 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
1726 const SCEV *N = getConstant(APInt::getMaxValue(BitWidth) -
1732 // still can't self-wrap.
1738 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
1743 // zext({C,+,Step}) --> (zext(D) + zext({C-D,+,Step}))<nuw><nsw>
1744 // if D + (C - D + Step * n) could be proven to not unsigned wrap
1745 // where D maximizes the number of trailing zeros of (C - D + Step * n)
1747 const APInt &C = SC->getAPInt();
1752 getAddRecExpr(getConstant(C - D), Step, L, AR->getNoWrapFlags());
1765 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
1769 // zext(A % B) --> zext(A) % zext(B)
1778 // zext(A / B) --> zext(A) / zext(B).
1780 return getUDivExpr(getZeroExtendExpr(Div->getLHS(), Ty, Depth + 1),
1781 getZeroExtendExpr(Div->getRHS(), Ty, Depth + 1));
1784 // zext((A + B + ...)<nuw>) --> (zext(A) + zext(B) + ...)<nuw>
1785 if (SA->hasNoUnsignedWrap()) {
1789 for (const auto *Op : SA->operands())
1794 // zext(C + x + y + ...) --> (zext(D) + zext((C - D) + x + y + ...))
1795 // if D + (C - D + x + y + ...) could be proven to not unsigned wrap
1796 // where D maximizes the number of trailing zeros of (C - D + x + y + ...)
1798 // Often address arithmetics contain expressions like
1802 if (const auto *SC = dyn_cast<SCEVConstant>(SA->getOperand(0))) {
1807 getAddExpr(getConstant(-D), SA, SCEV::FlagAnyWrap, Depth);
1817 // zext((A * B * ...)<nuw>) --> (zext(A) * zext(B) * ...)<nuw>
1818 if (SM->hasNoUnsignedWrap()) {
1822 for (const auto *Op : SM->operands())
1827 // zext(2^K * (trunc X to iN)) to iM ->
1828 // 2^K * (zext(trunc X to i{N-K}) to iM)<nuw>
1834 // = zext((trunc X to i{N-K}) << K)<nuw> to iM
1836 // = zext((2^K * (trunc X to i{N-K}))<nuw>) to iM
1837 // = (2^K * (zext(trunc X to i{N-K}) to iM))<nuw>.
1839 if (SM->getNumOperands() == 2)
1840 if (auto *MulLHS = dyn_cast<SCEVConstant>(SM->getOperand(0)))
1841 if (MulLHS->getAPInt().isPowerOf2())
1842 if (auto *TruncRHS = dyn_cast<SCEVTruncateExpr>(SM->getOperand(1))) {
1843 int NewTruncBits = getTypeSizeInBits(TruncRHS->getType()) -
1844 MulLHS->getAPInt().logBase2();
1849 getTruncateExpr(TruncRHS->getOperand(), NewTruncTy), Ty),
1854 // zext(umin(x, y)) -> umin(zext(x), zext(y))
1855 // zext(umax(x, y)) -> umax(zext(x), zext(y))
1859 for (auto *Operand : MinMax->operands())
1866 // zext(umin_seq(x, y)) -> umin_seq(zext(x), zext(y))
1870 for (auto *Operand : MinMax->operands())
1887 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
1891 assert(!Op->getType()->isPointerTy() && "Can't extend pointer!");
1897 return Iter->second;
1907 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
1910 assert(!Op->getType()->isPointerTy() && "Can't extend pointer!");
1915 return getConstant(SC->getAPInt().sext(getTypeSizeInBits(Ty)));
1917 // sext(sext(x)) --> sext(x)
1919 return getSignExtendExpr(SS->getOperand(), Ty, Depth + 1);
1921 // sext(zext(x)) --> zext(x)
1923 return getZeroExtendExpr(SZ->getOperand(), Ty, Depth + 1);
1942 // sext(trunc(x)) --> sext(x) or x or trunc(x)
1946 const SCEV *X = ST->getOperand();
1948 unsigned TruncBits = getTypeSizeInBits(ST->getType());
1956 // sext((A + B + ...)<nsw>) --> (sext(A) + sext(B) + ...)<nsw>
1957 if (SA->hasNoSignedWrap()) {
1961 for (const auto *Op : SA->operands())
1966 // sext(C + x + y + ...) --> (sext(D) + sext((C - D) + x + y + ...))
1967 // if D + (C - D + x + y + ...) could be proven to not signed wrap
1968 // where D maximizes the number of trailing zeros of (C - D + x + y + ...)
1975 if (const auto *SC = dyn_cast<SCEVConstant>(SA->getOperand(0))) {
1980 getAddExpr(getConstant(-D), SA, SCEV::FlagAnyWrap, Depth);
1993 if (AR->isAffine()) {
1994 const SCEV *Start = AR->getStart();
1995 const SCEV *Step = AR->getStepRecurrence(*this);
1996 unsigned BitWidth = getTypeSizeInBits(AR->getType());
1997 const Loop *L = AR->getLoop();
2001 if (AR->hasNoSignedWrap()) {
2008 // Check whether the backedge-taken count is SCEVCouldNotCompute.
2011 // being called from within backedge-taken count analysis, such that
2012 // attempting to ask for the backedge-taken count would likely result
2021 // Check whether the backedge-taken count can be losslessly casted to
2024 getTruncateOrZeroExtend(MaxBECount, Start->getType(), Depth);
2026 CastedMaxBECount, MaxBECount->getType(), Depth);
2052 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
2065 // abs(Step) * MaxBECount > unsigned-max(AR->getType())
2077 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
2084 if (AR->hasNoSignedWrap()) {
2085 // Same as nsw case above - duplicated here to avoid a compile time
2092 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
2095 // sext({C,+,Step}) --> (sext(D) + sext({C-D,+,Step}))<nuw><nsw>
2096 // if D + (C - D + Step * n) could be proven to not signed wrap
2097 // where D maximizes the number of trailing zeros of (C - D + Step * n)
2099 const APInt &C = SC->getAPInt();
2104 getAddRecExpr(getConstant(C - D), Step, L, AR->getNoWrapFlags());
2117 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
2126 // sext(smin(x, y)) -> smin(sext(x), sext(y))
2127 // sext(smax(x, y)) -> smax(sext(x), sext(y))
2131 for (auto *Operand : MinMax->operands())
2164 /// getAnyExtendExpr - Return a SCEV for the given operand extended with
2168 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
2174 // Sign-extend negative constants.
2176 if (SC->getAPInt().isNegative())
2181 const SCEV *NewOp = T->getOperand();
2182 if (getTypeSizeInBits(NewOp->getType()) < getTypeSizeInBits(Ty))
2200 for (const SCEV *Op : AR->operands())
2202 return getAddRecExpr(Ops, AR->getLoop(), SCEV::FlagNW);
2218 /// m + n + 13 + (A * (o + p + (B * (q + m + 29)))) + r + (-1 * r)
2233 /// may be exposed. This helps getAddRecExpr short-circuit extra work in
2249 if (Scale != 1 || AccumulatedConstant != 0 || C->getValue()->isZero())
2251 AccumulatedConstant += Scale * C->getAPInt();
2258 if (Mul && isa<SCEVConstant>(Mul->getOperand(0))) {
2260 Scale * cast<SCEVConstant>(Mul->getOperand(0))->getAPInt();
2261 if (Mul->getNumOperands() == 2 && isa<SCEVAddExpr>(Mul->getOperand(1))) {
2263 const SCEVAddExpr *Add = cast<SCEVAddExpr>(Mul->getOperand(1));
2266 Add->operands(), NewScale, SE);
2270 SmallVector<const SCEV *, 4> MulOps(drop_begin(Mul->operands()));
2274 NewOps.push_back(Pair.first->first);
2276 Pair.first->second += NewScale;
2287 NewOps.push_back(Pair.first->first);
2289 Pair.first->second += Scale;
2324 auto *NarrowTy = cast<IntegerType>(LHS->getType());
2326 IntegerType::get(NarrowTy->getContext(), NarrowTy->getBitWidth() * 2);
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);
2345 APInt C = RHSC->getAPInt();
2357 Magnitude = -C;
2368 // To avoid overflow up, we need to make sure that LHS <= MAX - Magnitude.
2371 APInt Limit = Max - Magnitude;
2380 if (OBO->hasNoUnsignedWrap() && OBO->hasNoSignedWrap())
2385 if (OBO->hasNoUnsignedWrap())
2387 if (OBO->hasNoSignedWrap())
2392 if (OBO->getOpcode() != Instruction::Add &&
2393 OBO->getOpcode() != Instruction::Sub &&
2394 OBO->getOpcode() != Instruction::Mul)
2397 const SCEV *LHS = getSCEV(OBO->getOperand(0));
2398 const SCEV *RHS = getSCEV(OBO->getOperand(1));
2402 if (!OBO->hasNoUnsignedWrap() &&
2403 willNotOverflow((Instruction::BinaryOps)OBO->getOpcode(),
2409 if (!OBO->hasNoSignedWrap() &&
2410 willNotOverflow((Instruction::BinaryOps)OBO->getOpcode(),
2422 // `OldFlags' as can't-wrap behavior. Infer a more aggressive set of
2423 // can't-overflow flags for the operation if possible.
2441 // If FlagNSW is true and all the operands are non-negative, infer FlagNUW.
2443 return SE->isKnownNonNegative(S);
2467 const APInt &C = cast<SCEVConstant>(Ops[0])->getAPInt();
2469 // (A <opcode> C) --> (A <opcode> C)<nsw> if the op doesn't sign overflow.
2473 if (NSWRegion.contains(SE->getSignedRange(Ops[1])))
2477 // (A <opcode> C) --> (A <opcode> C)<nuw> if the op doesn't unsign overflow.
2481 if (NUWRegion.contains(SE->getUnsignedRange(Ops[1])))
2490 Ops[0]->isZero() && IsKnownNonNegative(Ops[1]))
2497 if (UDiv->getOperand(1) == Ops[1])
2500 if (UDiv->getOperand(1) == Ops[0])
2508 return isLoopInvariant(S, L) && properlyDominates(S, L->getHeader());
2520 Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
2522 assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
2525 Ops, [](const SCEV *Op) { return Op->getType()->isPointerTy(); });
2539 Ops[0] = getConstant(LHSC->getAPInt() + RHSC->getAPInt());
2546 if (LHSC->getValue()->isZero()) {
2548 --Idx;
2566 if (Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2567 Add->setNoWrapFlags(ComputeFlags(Ops));
2574 Type *Ty = Ops[0]->getType();
2576 for (unsigned i = 0, e = Ops.size(); i != e-1; ++i)
2577 if (Ops[i] == Ops[i+1]) { // X + Y + Y --> X + Y*2
2589 --i; e -= Count - 1;
2597 // folded. eg., n*trunc(x) + m*trunc(y) --> trunc(trunc(m)*x + trunc(n)*y)
2599 auto FindTruncSrcType = [&]() -> Type * {
2605 return T->getOperand()->getType();
2607 const auto *LastOp = Mul->getOperand(Mul->getNumOperands() - 1);
2609 return T->getOperand()->getType();
2620 if (T->getOperand()->getType() != SrcType) {
2624 LargeOps.push_back(T->getOperand());
2629 for (unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2631 dyn_cast<SCEVTruncateExpr>(M->getOperand(j))) {
2632 if (T->getOperand()->getType() != SrcType) {
2636 LargeMulOps.push_back(T->getOperand());
2637 } else if (const auto *C = dyn_cast<SCEVConstant>(M->getOperand(j))) {
2661 // Check if we have an expression of the form ((X + C1) - C2), where C1 and
2668 if (AddExpr && C && isa<SCEVConstant>(AddExpr->getOperand(0))) {
2669 auto C1 = cast<SCEVConstant>(AddExpr->getOperand(0))->getAPInt();
2670 auto C2 = C->getAPInt();
2674 auto AddFlags = AddExpr->getNoWrapFlags();
2692 SmallVector<const SCEV *, 4> NewOps(AddExpr->operands());
2699 // Canonicalize (-1 * urem X, Y) + X --> (Y * X/Y)
2702 if (Mul && Mul->getNumOperands() == 2 &&
2703 Mul->getOperand(0)->isAllOnesValue()) {
2706 if (matchURem(Mul->getOperand(1), X, Y) && X == Ops[1]) {
2713 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddExpr)
2725 Add->getNumOperands() > AddOpsInlineThreshold)
2730 append_range(Ops, Add->operands());
2732 CommonFlags = maskFlags(CommonFlags, Add->getNoWrapFlags());
2743 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
2762 // re-generate the operands list. Group the operands by constant scale,
2766 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2767 // Re-generate the operands list.
2794 for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) {
2795 const SCEV *MulOpSCEV = Mul->getOperand(MulOp);
2800 // Fold W + X + (X * Y * Z) --> W + (X * ((Y*Z)+1))
2801 const SCEV *InnerMul = Mul->getOperand(MulOp == 0);
2802 if (Mul->getNumOperands() != 2) {
2806 Mul->operands().take_front(MulOp));
2807 append_range(MulOps, Mul->operands().drop_front(MulOp + 1));
2817 Ops.erase(Ops.begin()+Idx-1);
2820 Ops.erase(Ops.begin()+AddOp-1);
2833 for (unsigned OMulOp = 0, e = OtherMul->getNumOperands();
2835 if (OtherMul->getOperand(OMulOp) == MulOpSCEV) {
2836 // Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E))
2837 const SCEV *InnerMul1 = Mul->getOperand(MulOp == 0);
2838 if (Mul->getNumOperands() != 2) {
2840 Mul->operands().take_front(MulOp));
2841 append_range(MulOps, Mul->operands().drop_front(MulOp+1));
2844 const SCEV *InnerMul2 = OtherMul->getOperand(OMulOp == 0);
2845 if (OtherMul->getNumOperands() != 2) {
2847 OtherMul->operands().take_front(OMulOp));
2848 append_range(MulOps, OtherMul->operands().drop_front(OMulOp+1));
2858 Ops.erase(Ops.begin()+OtherMulIdx-1);
2869 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
2878 const Loop *AddRecLoop = AddRec->getLoop();
2883 --i; --e;
2888 // Compute nowrap flags for the addition of the loop-invariant ops and
2895 // NLI + LI + {Start,+,Step} --> NLI + {LI+Start,+,Step}
2896 LIOps.push_back(AddRec->getStart());
2898 SmallVector<const SCEV *, 4> AddRecOps(AddRec->operands());
2913 auto *ReachI = &*AddRecLoop->getHeader()->begin();
2922 Flags = AddRec->getNoWrapFlags(setFlags(Flags, SCEV::FlagNW));
2928 // Otherwise, add the folded AddRec by the non-invariant parts.
2946 cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop()->getHeader(),
2947 AddRec->getLoop()->getHeader()) &&
2949 if (AddRecLoop == cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop()) {
2950 // Other + {A,+,B}<L> + {C,+,D}<L> --> Other + {A+C,+,B+D}<L>
2951 SmallVector<const SCEV *, 4> AddRecOps(AddRec->operands());
2955 if (OtherAddRec->getLoop() == AddRecLoop) {
2956 for (unsigned i = 0, e = OtherAddRec->getNumOperands();
2959 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2963 AddRecOps[i], OtherAddRec->getOperand(i)};
2966 Ops.erase(Ops.begin() + OtherIdx); --OtherIdx;
2969 // Step size has changed, so we cannot guarantee no self-wraparound.
3002 S->setNoWrapFlags(Flags);
3048 S->setNoWrapFlags(Flags);
3063 // n(n-1)(n-2)...(n-(k-1)) / k(k-1)(k-2)...1 .
3064 // At each iteration, we take the n-th term of the numeral and divide by the
3065 // (k-n)th term of the denominator. This division will always produce an
3074 k = n-k;
3078 r = umul_ov(r, n-(i-1), Overflow);
3115 Type *ETy = Ops[0]->getType();
3116 assert(!ETy->isPointerTy());
3118 assert(Ops[i]->getType() == ETy &&
3132 Ops[0] = getConstant(LHSC->getAPInt() * RHSC->getAPInt());
3139 if (LHSC->getValue()->isZero())
3143 if (LHSC->getValue()->isOne()) {
3145 --Idx;
3164 if (Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3165 Mul->setNoWrapFlags(ComputeFlags(Ops));
3171 // C1*(C2+V) -> C1*C2 + C1*V
3179 if (Add->getNumOperands() == 2 && containsConstantInAddMulChain(Add)) {
3180 const SCEV *LHS = getMulExpr(LHSC, Add->getOperand(0),
3182 const SCEV *RHS = getMulExpr(LHSC, Add->getOperand(1),
3187 if (Ops[0]->isAllOnesValue()) {
3188 // If we have a mul by -1 of an add, try distributing the -1 among the
3193 for (const SCEV *AddOp : Add->operands()) {
3202 // Negation preserves a recurrence's no self-wrap property.
3204 for (const SCEV *AddRecOp : AddRec->operands())
3208 // multiplied by -1 can have signed overflow if and only if it takes a
3209 // value of M: M * (-1) would stay M and (M + 1) * (-1) would be the
3213 if (hasFlags(AddRec->getNoWrapFlags(), SCEV::FlagNSW)) {
3215 APInt::getSignedMinValue(getTypeSizeInBits(AddRec->getType()));
3219 return getAddRecExpr(Operands, AddRec->getLoop(),
3220 AddRec->getNoWrapFlags(FlagsMask));
3227 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
3239 append_range(Ops, Mul->operands());
3253 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
3263 if (isAvailableAtLoopEntry(Ops[i], AddRec->getLoop())) {
3266 --i; --e;
3271 // NLI * LI * {Start,+,Step} --> NLI * {LI*Start,+,LI*Step}
3273 NewOps.reserve(AddRec->getNumOperands());
3281 AddRec->getNoWrapFlags(ComputeFlags({Scale, AddRec}));
3283 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
3284 NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i),
3291 if (!NSWRegion.contains(getSignedRange(AddRec->getOperand(i))))
3296 const SCEV *NewRec = getAddRecExpr(NewOps, AddRec->getLoop(), Flags);
3301 // Otherwise, multiply the folded AddRec by the non-invariant parts.
3315 // = {x=1 in [ sum y=x..2x [ sum z=max(y-x, y-n)..min(x,n) [
3316 // choose(x, 2x)*choose(2x-y, x-z)*A_{y-z}*B_z
3330 if (!OtherAddRec || OtherAddRec->getLoop() != AddRec->getLoop())
3335 if (AddRec->getNumOperands() + OtherAddRec->getNumOperands() - 1 >
3340 Type *Ty = AddRec->getType();
3343 for (int x = 0, xe = AddRec->getNumOperands() +
3344 OtherAddRec->getNumOperands() - 1; x != xe && !Overflow; ++x) {
3347 uint64_t Coeff1 = Choose(x, 2*x - y, Overflow);
3348 for (int z = std::max(y-x, y-(int)AddRec->getNumOperands()+1),
3349 ze = std::min(x+1, (int)OtherAddRec->getNumOperands());
3351 uint64_t Coeff2 = Choose(2*x - y, x-z, Overflow);
3358 const SCEV *Term1 = AddRec->getOperand(y-z);
3359 const SCEV *Term2 = OtherAddRec->getOperand(z);
3369 const SCEV *NewAddRec = getAddRecExpr(AddRecOps, AddRec->getLoop(),
3373 Ops.erase(Ops.begin() + OtherIdx); --OtherIdx;
3395 assert(getEffectiveSCEVType(LHS->getType()) ==
3396 getEffectiveSCEVType(RHS->getType()) &&
3399 // Short-circuit easy cases
3402 if (RHSC->getValue()->isOne())
3403 return getZero(LHS->getType()); // X urem 1 --> 0
3406 if (RHSC->getAPInt().isPowerOf2()) {
3407 Type *FullTy = LHS->getType();
3409 IntegerType::get(getContext(), RHSC->getAPInt().logBase2());
3414 // Fallback to %a == %x urem %y == %x -<nuw> ((%x udiv %y) *<nuw> %y)
3424 assert(!LHS->getType()->isPointerTy() &&
3426 assert(LHS->getType() == RHS->getType() &&
3439 if (LHSC->getValue()->isZero())
3443 if (RHSC->getValue()->isOne())
3444 return LHS; // X udiv 1 --> x
3448 if (!RHSC->getValue()->isZero()) {
3451 // TODO: Generalize this to non-constants by using known-bits information.
3452 Type *Ty = LHS->getType();
3453 unsigned LZ = RHSC->getAPInt().countl_zero();
3454 unsigned MaxShiftAmt = getTypeSizeInBits(Ty) - LZ - 1;
3455 // For non-power-of-two values, effectively round the value up to the
3457 if (!RHSC->getAPInt().isPowerOf2())
3463 dyn_cast<SCEVConstant>(AR->getStepRecurrence(*this))) {
3464 // {X,+,N}/C --> {X/C,+,N/C} if safe and N/C can be folded.
3465 const APInt &StepInt = Step->getAPInt();
3466 const APInt &DivInt = RHSC->getAPInt();
3469 getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy),
3471 AR->getLoop(), SCEV::FlagAnyWrap)) {
3473 for (const SCEV *Op : AR->operands())
3475 return getAddRecExpr(Operands, AR->getLoop(), SCEV::FlagNW);
3478 /// {X,+,N}/C => {Y,+,N}/C where Y=X-(X%N). Safe when C%N=0.
3480 const SCEVConstant *StartC = dyn_cast<SCEVConstant>(AR->getStart());
3483 getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy),
3485 AR->getLoop(), SCEV::FlagAnyWrap)) {
3486 const APInt &StartInt = StartC->getAPInt();
3490 getAddRecExpr(getConstant(StartInt - StartRem), Step,
3491 AR->getLoop(), SCEV::FlagNW);
3508 // (A*B)/C --> A*(B/C) if safe and B/C can be folded.
3511 for (const SCEV *Op : M->operands())
3515 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3516 const SCEV *Op = M->getOperand(i);
3519 Operands = SmallVector<const SCEV *, 4>(M->operands());
3526 // (A/B)/C --> A/(B*C) if safe and B*C can be folded.
3529 dyn_cast<SCEVConstant>(OtherDiv->getRHS())) {
3532 DivisorConstant->getAPInt().umul_ov(RHSC->getAPInt(), Overflow);
3534 return getConstant(RHSC->getType(), 0, false);
3536 return getUDivExpr(OtherDiv->getLHS(), getConstant(NewRHS));
3540 // (A+B)/C --> (A/C + B/C) if safe and A/C and B/C can be folded.
3543 for (const SCEV *Op : A->operands())
3547 for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) {
3548 const SCEV *Op = getUDivExpr(A->getOperand(i), RHS);
3550 getMulExpr(Op, RHS) != A->getOperand(i))
3554 if (Operands.size() == A->getNumOperands())
3561 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3577 APInt A = C1->getAPInt().abs();
3578 APInt B = C2->getAPInt().abs();
3601 if (!Mul || !Mul->hasNoUnsignedWrap())
3607 if (const auto *LHSCst = dyn_cast<SCEVConstant>(Mul->getOperand(0))) {
3609 SmallVector<const SCEV *, 2> Operands(drop_begin(Mul->operands()));
3619 cast<SCEVConstant>(getConstant(LHSCst->getAPInt().udiv(Factor)));
3621 cast<SCEVConstant>(getConstant(RHSCst->getAPInt().udiv(Factor)));
3624 append_range(Operands, Mul->operands().drop_front());
3634 for (int i = 0, e = Mul->getNumOperands(); i != e; ++i) {
3635 if (Mul->getOperand(i) == RHS) {
3637 append_range(Operands, Mul->operands().take_front(i));
3638 append_range(Operands, Mul->operands().drop_front(i + 1));
3654 if (StepChrec->getLoop() == L) {
3655 append_range(Operands, StepChrec->operands());
3670 Type *ETy = getEffectiveSCEVType(Operands[0]->getType());
3672 assert(getEffectiveSCEVType(Op->getType()) == ETy &&
3674 assert(!Op->getType()->isPointerTy() && "Step must be integer");
3681 if (Operands.back()->isZero()) {
3683 return getAddRecExpr(Operands, L, SCEV::FlagAnyWrap); // {X,+,0} --> X
3696 const Loop *NestedLoop = NestedAR->getLoop();
3697 if (L->contains(NestedLoop)
3698 ? (L->getLoopDepth() < NestedLoop->getLoopDepth())
3699 : (!NestedLoop->contains(L) &&
3700 DT.dominates(L->getHeader(), NestedLoop->getHeader()))) {
3701 SmallVector<const SCEV *, 4> NestedOperands(NestedAR->operands());
3702 Operands[0] = NestedAR->getStart();
3703 // AddRecs require their operands be loop-invariant with respect to their
3715 maskFlags(Flags, SCEV::FlagNW | NestedAR->getNoWrapFlags());
3728 maskFlags(NestedAR->getNoWrapFlags(), SCEV::FlagNW | Flags);
3745 const SCEV *BaseExpr = getSCEV(GEP->getPointerOperand());
3746 // getSCEV(Base)->getType() has the same address space as Base->getType()
3747 // because SCEV::getType() preserves the address space.
3748 Type *IntIdxTy = getEffectiveSCEVType(BaseExpr->getType());
3749 GEPNoWrapFlags NW = GEP->getNoWrapFlags();
3754 // TODO: non-instructions have global scope. We might be able to prove
3767 Type *CurTy = GEP->getType();
3774 ConstantInt *Index = cast<SCEVConstant>(IndexExpr)->getValue();
3775 unsigned FieldNo = Index->getZExtValue();
3780 CurTy = STy->getTypeAtIndex(Index);
3786 CurTy = GEP->getSourceElementType();
3808 // Add the base address and the offset. We cannot use the nsw flag, as the
3809 // base address is unsigned. However, if we know that the offset is
3810 // non-negative, we can use nuw.
3815 assert(BaseExpr->getType() == GEPExpr->getType() &&
3816 "GEP should not change type mid-flight.");
3841 Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
3843 assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
3845 assert(Ops[0]->getType()->isPointerTy() ==
3846 Ops[i]->getType()->isPointerTy() &&
3885 getContext(), FoldOp(LHSC->getAPInt(), RHSC->getAPInt()));
3892 bool IsMinV = LHSC->getValue()->isMinValue(IsSigned);
3893 bool IsMaxV = LHSC->getValue()->isMaxValue(IsSigned);
3896 // If we are left with a constant minimum(/maximum)-int, strip it off.
3898 --Idx;
3900 // If we have a max(/min) with a constant maximum(/minimum)-int,
3909 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < Kind)
3916 while (Ops[Idx]->getSCEVType() == Kind) {
3919 append_range(Ops, SMME->operands());
3936 for (unsigned i = 0, e = Ops.size() - 1; i != e; ++i) {
3939 // X op Y op Y --> X op Y
3940 // X op Y --> X, if we know X, Y are ordered appropriately
3942 --i;
3943 --e;
3946 // X op Y --> Y, if we know X, Y are ordered appropriately
3948 --i;
3949 --e;
3987 const SCEVTypes NonSequentialRootKind; // Non-sequential variant of RootKind.
3999 SCEVTypes Kind = S->getSCEVType();
4006 bool Changed = visit(Kind, NAry->operands(), NewOps);
4131 // introduce poison -- they encode guaranteed, non-speculated knowledge.
4144 !scevUnconditionallyPropagatesPoisonFromOperands(S->getSCEVType()))
4148 if (!isGuaranteedNotToBePoison(SU->getValue()))
4160 // We need to look through potentially poison-blocking operations here,
4172 // as well. We cannot look through potentially poison-blocking operations
4189 Result.insert(SU->getValue());
4200 // poison-contributors of S, and then check whether I has any additional
4201 // poison-contributors. Poison that is contributed through poison-generating
4231 if (PDI->isDisjoint())
4238 II && II->getIntrinsicID() == Intrinsic::vscale)
4245 if (I->hasPoisonGeneratingAnnotations())
4248 for (Value *Op : I->operands())
4263 Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
4265 assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
4267 assert(Ops[0]->getType()->isPointerTy() ==
4268 Ops[i]->getType()->isPointerTy() &&
4296 if (Ops[Idx]->getSCEVType() != Kind) {
4302 Ops.insert(Ops.begin() + Idx, SMME->operands().begin(),
4303 SMME->operands().end());
4315 SaturationPoint = getZero(Ops[0]->getType());
4326 if (::impliesPoison(Ops[i], Ops[i - 1]) ||
4327 isKnownViaNonRecursiveReasoning(ICmpInst::ICMP_NE, Ops[i - 1],
4329 SmallVector<const SCEV *> SeqOps = {Ops[i - 1], Ops[i]};
4330 Ops[i - 1] = getMinMaxExpr(
4338 if (isKnownViaNonRecursiveReasoning(Pred, Ops[i - 1], Ops[i])) {
4424 // We can bypass creating a target-independent constant expression and then
4425 // folding it back into a ConstantInt. This is just a compile-time
4428 assert(!SL->getSizeInBits().isScalable() &&
4430 return getConstant(IntTy, SL->getElementOffset(FieldNo));
4444 assert(cast<SCEVUnknown>(S)->getValue() == V &&
4455 //===----------------------------------------------------------------------===//
4462 /// target-specific information.
4465 return Ty->isIntOrPtrTy();
4472 if (Ty->isPointerTy())
4483 if (Ty->isIntegerTy())
4487 assert(Ty->isPointerTy() && "Unexpected non-pointer non-integer type!");
4516 return SU && SU->getValue() == nullptr;
4525 return I->second;
4539 return SI->second.getArrayRef();
4548 auto EVIt = ExprValueMap.find(I->second);
4549 bool Removed = EVIt->second.remove(V);
4570 assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
4578 assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
4582 const SCEV *S = I->second;
4590 /// Return a SCEV corresponding to -V = -1*V
4595 cast<ConstantInt>(ConstantExpr::getNeg(VC->getValue())));
4597 Type *Ty = V->getType();
4605 if (!Add || Add->getNumOperands() != 2 ||
4606 !Add->getOperand(0)->isAllOnesValue())
4609 const SCEVMulExpr *AddRHS = dyn_cast<SCEVMulExpr>(Add->getOperand(1));
4610 if (!AddRHS || AddRHS->getNumOperands() != 2 ||
4611 !AddRHS->getOperand(0)->isAllOnesValue())
4614 return AddRHS->getOperand(1);
4617 /// Return a SCEV corresponding to ~V = -1-V
4619 assert(!V->getType()->isPointerTy() && "Can't negate pointer");
4623 cast<ConstantInt>(ConstantExpr::getNot(VC->getValue())));
4629 for (const SCEV *Operand : MME->operands()) {
4635 return getMinMaxExpr(SCEVMinMaxExpr::negate(MME->getSCEVType()),
4642 Type *Ty = V->getType();
4648 assert(P->getType()->isPointerTy());
4652 SmallVector<const SCEV *> Ops{AddRec->operands()};
4656 return getAddRecExpr(Ops, AddRec->getLoop(), SCEV::FlagAnyWrap);
4660 SmallVector<const SCEV *> Ops{Add->operands()};
4663 if (AddOp->getType()->isPointerTy()) {
4674 return getZero(P->getType());
4680 // Fast path: X - X --> 0.
4682 return getZero(LHS->getType());
4687 if (RHS->getType()->isPointerTy()) {
4688 if (!LHS->getType()->isPointerTy() ||
4695 // We represent LHS - RHS as LHS + (-1)*RHS. This transformation
4701 // Let M be the minimum representable signed value. Then (-1)*RHS
4702 // signed-wraps if and only if RHS is M. That can happen even for
4703 // a NSW subtraction because e.g. (-1)*M signed-wraps even though
4704 // -1 - M does not. So to transfer NSW from LHS - RHS to LHS +
4705 // (-1)*RHS, we need to prove that RHS != M.
4707 // If LHS is non-negative and we know that LHS - RHS does not
4708 // signed-wrap, then RHS cannot be M. So we can rule out signed-wrap
4715 // FIXME: Find a correct way to transfer NSW to (-1)*M when LHS -
4720 // not in RHS. Applying NSW to (-1)*M may then let the NSW have a
4729 Type *SrcTy = V->getType();
4730 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4731 "Cannot truncate or zero extend with non-integer arguments!");
4741 Type *SrcTy = V->getType();
4742 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4743 "Cannot truncate or zero extend with non-integer arguments!");
4753 Type *SrcTy = V->getType();
4754 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4755 "Cannot noop or zero extend with non-integer arguments!");
4765 Type *SrcTy = V->getType();
4766 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4767 "Cannot noop or sign extend with non-integer arguments!");
4777 Type *SrcTy = V->getType();
4778 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4779 "Cannot noop or any extend with non-integer arguments!");
4789 Type *SrcTy = V->getType();
4790 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4791 "Cannot truncate or noop with non-integer arguments!");
4804 if (getTypeSizeInBits(LHS->getType()) > getTypeSizeInBits(RHS->getType()))
4805 PromotedRHS = getZeroExtendExpr(RHS, LHS->getType());
4807 PromotedLHS = getNoopOrZeroExtend(LHS, RHS->getType());
4831 MaxType = getWiderType(MaxType, S->getType());
4833 MaxType = S->getType();
4847 if (!V->getType()->isPointerTy())
4852 V = AddRec->getStart();
4855 for (const SCEV *AddOp : Add->operands()) {
4856 if (AddOp->getType()->isPointerTy()) {
4872 // Push the def-use children onto the Worklist stack.
4873 for (User *U : I->users()) {
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.
4907 // Only re-write AddRecExprs for this loop.
4908 if (Expr->getLoop() == L)
4909 return Expr->getStart();
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.
4948 // Only re-write AddRecExprs for this loop.
4949 if (Expr->getLoop() == L)
4950 return Expr->getPostIncExpr(SE);
4978 if (BasicBlock *Latch = L->getLoopLatch()) {
4979 BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
4980 if (BI && BI->isConditional()) {
4981 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
4983 BECond = BI->getCondition();
4984 IsPosBECond = BI->getSuccessor(0) == L->getHeader();
4998 Instruction *I = cast<Instruction>(Expr->getValue());
4999 switch (I->getOpcode()) {
5003 compareWithBackedgeCondition(SI->getCondition());
5005 bool IsOne = cast<SCEVConstant>(*Res)->getValue()->isOne();
5006 Result = SE.getSCEV(IsOne ? SI->getTrueValue() : SI->getFalseValue());
5065 if (Expr->getLoop() == L && Expr->isAffine())
5066 return SE.getMinusSCEV(Expr, Expr->getStepRecurrence(SE));
5085 if (!AR->isAffine())
5092 if (!AR->hasNoSelfWrap()) {
5093 const SCEV *BECount = getConstantMaxBackedgeTakenCount(AR->getLoop());
5095 ConstantRange StepCR = getSignedRange(AR->getStepRecurrence(*this));
5096 const APInt &BECountAP = BECountMax->getAPInt();
5099 if (NoOverflowBitWidth <= getTypeSizeInBits(AR->getType()))
5104 if (!AR->hasNoSignedWrap()) {
5106 ConstantRange IncRange = getSignedRange(AR->getStepRecurrence(*this));
5114 if (!AR->hasNoUnsignedWrap()) {
5116 ConstantRange IncRange = getUnsignedRange(AR->getStepRecurrence(*this));
5129 SCEV::NoWrapFlags Result = AR->getNoWrapFlags();
5131 if (AR->hasNoSignedWrap())
5134 if (!AR->isAffine())
5141 const SCEV *Step = AR->getStepRecurrence(*this);
5142 const Loop *L = AR->getLoop();
5144 // Check whether the backedge-taken count is SCEVCouldNotCompute.
5147 // being called from within backedge-taken count analysis, such that
5148 // attempting to ask for the backedge-taken count would likely result
5154 // Normally, in the cases we can prove no-overflow via a
5157 // guards present in the loop -- SCEV is not great at exploiting
5166 // If the backedge is guarded by a comparison with the pre-inc value the
5168 // start value and the backedge is guarded by a comparison with the post-inc
5182 SCEV::NoWrapFlags Result = AR->getNoWrapFlags();
5184 if (AR->hasNoUnsignedWrap())
5187 if (!AR->isAffine())
5194 const SCEV *Step = AR->getStepRecurrence(*this);
5195 unsigned BitWidth = getTypeSizeInBits(AR->getType());
5196 const Loop *L = AR->getLoop();
5198 // Check whether the backedge-taken count is SCEVCouldNotCompute.
5201 // being called from within backedge-taken count analysis, such that
5202 // attempting to ask for the backedge-taken count would likely result
5208 // Normally, in the cases we can prove no-overflow via a
5211 // guards present in the loop -- SCEV is not great at exploiting
5220 // If the backedge is guarded by a comparison with the pre-inc value the
5222 // start value and the backedge is guarded by a comparison with the post-inc
5225 const SCEV *N = getConstant(APInt::getMinValue(BitWidth) -
5253 : Opcode(Op->getOpcode()), LHS(Op->getOperand(0)), RHS(Op->getOperand(1)),
5256 IsNSW = OBO->hasNoSignedWrap();
5257 IsNUW = OBO->hasNoUnsignedWrap();
5278 // creating new SCEV expressions -- our caller knowns tricks to avoid creating
5281 switch (Op->getOpcode()) {
5294 if (cast<PossiblyDisjointInst>(Op)->isDisjoint())
5295 return BinaryOp(Instruction::Add, Op->getOperand(0), Op->getOperand(1),
5301 if (auto *RHSC = dyn_cast<ConstantInt>(Op->getOperand(1)))
5304 if (RHSC->getValue().isSignMask())
5305 return BinaryOp(Instruction::Add, Op->getOperand(0), Op->getOperand(1));
5306 // Binary `xor` is a bit-wise `add`.
5307 if (V->getType()->isIntegerTy(1))
5308 return BinaryOp(Instruction::Add, Op->getOperand(0), Op->getOperand(1));
5313 if (ConstantInt *SA = dyn_cast<ConstantInt>(Op->getOperand(1))) {
5314 uint32_t BitWidth = cast<IntegerType>(Op->getType())->getBitWidth();
5320 if (SA->getValue().ult(BitWidth)) {
5322 ConstantInt::get(SA->getContext(),
5323 APInt::getOneBitSet(BitWidth, SA->getZExtValue()));
5324 return BinaryOp(Instruction::UDiv, Op->getOperand(0), X);
5331 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5334 auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand());
5338 Instruction::BinaryOps BinOp = WO->getBinaryOp();
5339 bool Signed = WO->isSigned();
5342 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5344 // Now that we know that all uses of the arithmetic-result component of
5346 // that the arithmetic is non-overflowing.
5347 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5358 if (II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5359 return BinaryOp(Instruction::Sub, II->getOperand(0), II->getOperand(1));
5390 unsigned SourceBits = SE.getTypeSizeInBits(SymbolicPHI->getType());
5391 unsigned NewBits = SE.getTypeSizeInBits(Op->getType());
5400 SExt ? dyn_cast<SCEVTruncateExpr>(SExt->getOperand())
5401 : dyn_cast<SCEVTruncateExpr>(ZExt->getOperand());
5404 const SCEV *X = Trunc->getOperand();
5408 return Trunc->getType();
5412 if (!PN->getType()->isIntegerTy())
5414 const Loop *L = LI.getLoopFor(PN->getParent());
5415 if (!L || L->getHeader() != PN->getParent())
5423 // which correspond to a phi->trunc->sext/zext->add->phi update chain.
5433 // It will visitMul->visitAdd->visitSExt->visitTrunc->visitUnknown(%X),
5463 // inductions where the sext-trunc / zext-trunc operations (partly) occur
5467 // which correspond to a phi->add->trunc->sext/zext->phi update chain.
5470 // which correspond to a phi->trunc->add->sext/zext->phi update chain.
5477 // *** Part1: Analyze if we have a phi-with-cast pattern for which we can
5480 auto *PN = cast<PHINode>(SymbolicPHI->getValue());
5488 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5489 Value *V = PN->getIncomingValue(i);
5490 if (L->contains(PN->getIncomingBlock(i))) {
5518 unsigned FoundIndex = Add->getNumOperands();
5521 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
5523 isSimpleCastedPHI(Add->getOperand(i), SymbolicPHI, Signed, *this)))
5529 if (FoundIndex == Add->getNumOperands())
5534 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
5536 Ops.push_back(Add->getOperand(i));
5546 // Analysis was successful: we have a phi-with-cast pattern for which we
5550 // fits within the truncated type (does not overflow) for i = 0 to n-1.
5569 // Expr(i) = (Ext ix (Trunc iy (Expr(i-1)) to ix) to iy) + Accum
5576 // = (Ext ix (Trunc iy (Expr(i-1)) to ix) to iy) + Accum + Accum
5579 // = (Ext ix (Trunc iy (Start + (i-1)*Accum) to ix) to iy) + Accum + Accum
5581 // = (Ext ix (Trunc iy (Start + (i-1)*Accum) to ix) to iy)
5585 // = (Ext ix (Trunc iy ((Start + (i-1)*Accum) + Accum) to ix) to iy)
5624 bool CreateSignExtend) -> const SCEV * {
5628 CreateSignExtend ? getSignExtendExpr(TruncatedExpr, Expr->getType())
5629 : getZeroExtendExpr(TruncatedExpr, Expr->getType());
5639 const SCEV *ExtendedExpr) -> bool {
5646 LLVM_DEBUG(dbgs() << "P2 is compile-time false\n";);
5654 LLVM_DEBUG(dbgs() << "P3 is compile-time false\n";);
5659 const SCEV *ExtendedExpr) -> void {
5686 auto *PN = cast<PHINode>(SymbolicPHI->getValue());
5695 I->second;
5730 auto areExprsEqual = [&](const SCEV *Expr1, const SCEV *Expr2) -> bool {
5731 if (Expr1 != Expr2 && !Preds->implies(SE.getEqualPredicate(Expr1, Expr2)) &&
5732 !Preds->implies(SE.getEqualPredicate(Expr2, Expr1)))
5737 if (!areExprsEqual(AR1->getStart(), AR2->getStart()) ||
5738 !areExprsEqual(AR1->getStepRecurrence(SE), AR2->getStepRecurrence(SE)))
5752 const Loop *L = LI.getLoopFor(PN->getParent());
5753 assert(L && L->getHeader() == PN->getParent());
5760 if (BO->Opcode != Instruction::Add)
5764 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5765 Accum = getSCEV(BO->RHS);
5766 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5767 Accum = getSCEV(BO->LHS);
5773 if (BO->IsNUW)
5775 if (BO->IsNSW)
5784 (SCEV::NoWrapFlags)(AR->getNoWrapFlags() |
5788 // We can add Flags to the post-inc expression only if we
5802 const Loop *L = LI.getLoopFor(PN->getParent());
5803 if (!L || L->getHeader() != PN->getParent())
5810 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5811 Value *V = PN->getIncomingValue(i);
5812 if (L->contains(PN->getIncomingBlock(i))) {
5842 // the back-edge.
5853 unsigned FoundIndex = Add->getNumOperands();
5854 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
5855 if (Add->getOperand(i) == SymbolicName)
5861 if (FoundIndex != Add->getNumOperands()) {
5864 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
5866 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(Add->getOperand(i),
5874 cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
5878 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5879 if (BO->IsNUW)
5881 if (BO->IsNSW)
5885 if (GEP->getOperand(0) == PN) {
5886 GEPNoWrapFlags NW = GEP->getNoWrapFlags();
5887 // If the increment has any nowrap flags, then we know the address
5891 // If the GEP is nuw or nusw with non-negative offset, we know that
5900 // operations -- sub nuw X, Y is not the same as add nuw X, -Y
5915 (SCEV::NoWrapFlags)(AR->getNoWrapFlags() |
5919 // We can add Flags to the post-inc expression only if we
5933 // Because the other in-value of i (0) fits the evolution of BEValue
5938 // PHI(f(0), f({1,+,1})) --> f({0,+,1})
5969 C = BI->getCondition();
5971 BasicBlockEdge LeftEdge(BI->getParent(), BI->getSuccessor(0));
5972 BasicBlockEdge RightEdge(BI->getParent(), BI->getSuccessor(1));
5979 Use &LeftUse = Merge->getOperandUse(0);
5980 Use &RightUse = Merge->getOperandUse(1);
6000 if (PN->getNumIncomingValues() == 2 && all_of(PN->blocks(), IsReachable)) {
6013 BasicBlock *IDom = DT[PN->getParent()]->getIDom()->getBlock();
6016 auto *BI = dyn_cast<BranchInst>(IDom->getTerminator());
6019 if (BI && BI->isConditional() &&
6021 properlyDominates(getSCEV(LHS), PN->getParent()) &&
6022 properlyDominates(getSCEV(RHS), PN->getParent()))
6048 const SCEVTypes NonSequentialRootKind; // Non-seq variant of RootKind.
6054 // as the type of our root SCEV expression, and into zero-extensions.
6068 return !isDone() && canRecurseInto(S->getSCEVType());
6087 Value *LHS = ICI->getOperand(0);
6088 Value *RHS = ICI->getOperand(1);
6090 switch (ICI->getPredicate()) {
6101 // a > b ? a+x : b+x -> max(a, b)+x
6102 // a > b ? b+x : a+x -> min(a, b)+x
6103 if (getTypeSizeInBits(LHS->getType()) <= getTypeSizeInBits(Ty)) {
6104 bool Signed = ICI->isSigned();
6109 if (LA->getType()->isPointerTy()) {
6118 auto CoerceOperand = [&](const SCEV *Op) -> const SCEV * {
6119 if (Op->getType()->isPointerTy()) {
6147 // x != 0 ? x+y : C+y -> x == 0 ? C+y : x+y
6151 // x == 0 ? C+y : x+y -> umax(x, C)+y iff C u<= 1
6152 if (getTypeSizeInBits(LHS->getType()) <= getTypeSizeInBits(Ty) &&
6153 isa<ConstantInt>(RHS) && cast<ConstantInt>(RHS)->isZero()) {
6157 const SCEV *Y = getMinusSCEV(FalseValExpr, X); // y = (x+y)-x
6158 const SCEV *C = getMinusSCEV(TrueValExpr, Y); // C = (C+y)-y
6159 if (isa<SCEVConstant>(C) && cast<SCEVConstant>(C)->getAPInt().ule(1))
6162 // x == 0 ? 0 : umin (..., x, ...) -> umin_seq(x, umin (...))
6163 // x == 0 ? 0 : umin_seq(..., x, ...) -> umin_seq(x, umin_seq(...))
6165 // -> umin_seq(x, umin (..., umin_seq(...), ...))
6166 if (isa<ConstantInt>(RHS) && cast<ConstantInt>(RHS)->isZero() &&
6167 isa<ConstantInt>(TrueVal) && cast<ConstantInt>(TrueVal)->isZero()) {
6170 X = ZExt->getOperand();
6171 if (getTypeSizeInBits(X->getType()) <= getTypeSizeInBits(Ty)) {
6189 assert(CondExpr->getType()->isIntegerTy(1) &&
6190 TrueExpr->getType() == FalseExpr->getType() &&
6191 TrueExpr->getType()->isIntegerTy(1) &&
6194 // i1 cond ? i1 x : i1 C --> C + (i1 cond ? (i1 x - i1 C) : i1 0)
6195 // --> C + (umin_seq cond, x - C)
6197 // i1 cond ? i1 C : i1 x --> C + (i1 cond ? i1 0 : (i1 x - i1 C))
6198 // --> C + (i1 ~cond ? (i1 x - i1 C) : i1 0)
6199 // --> C + (umin_seq ~cond, x - C)
6208 CondExpr = SE->getNotSCEV(CondExpr);
6215 return SE->getAddExpr(C, SE->getUMinExpr(CondExpr, SE->getMinusSCEV(X, C),
6225 const auto *SECond = SE->getSCEV(Cond);
6226 const auto *SETrue = SE->getSCEV(TrueVal);
6227 const auto *SEFalse = SE->getSCEV(FalseVal);
6233 assert(Cond->getType()->isIntegerTy(1) && "Select condition is not an i1?");
6234 assert(TrueVal->getType() == FalseVal->getType() &&
6235 V->getType() == TrueVal->getType() &&
6238 // For now, only deal with i1-typed `select`s.
6239 if (!V->getType()->isIntegerTy(1))
6255 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6260 createNodeForSelectOrPHIInstWithICmpInstCond(I->getType(), ICI,
6272 assert(GEP->getSourceElementType()->isSized() &&
6276 for (Value *Index : GEP->indices())
6282 uint64_t BitWidth = getTypeSizeInBits(S->getType());
6290 APInt Res = getConstantMultiple(N->getOperand(0));
6291 for (unsigned I = 1, E = N->getNumOperands(); I < E && Res != 1; ++I)
6293 Res, getConstantMultiple(N->getOperand(I)));
6297 switch (S->getSCEVType()) {
6299 return cast<SCEVConstant>(S)->getAPInt();
6301 return getConstantMultiple(cast<SCEVPtrToIntExpr>(S)->getOperand());
6308 uint32_t TZ = getMinTrailingZeros(T->getOperand());
6313 return getConstantMultiple(Z->getOperand()).zext(BitWidth);
6318 uint32_t TZ = getMinTrailingZeros(E->getOperand());
6323 if (M->hasNoUnsignedWrap()) {
6325 APInt Res = getConstantMultiple(M->getOperand(0));
6326 for (const SCEV *Operand : M->operands().drop_front())
6334 for (const SCEV *Operand : M->operands())
6341 if (N->hasNoUnsignedWrap())
6344 uint32_t TZ = getMinTrailingZeros(N->getOperand(0));
6345 for (const SCEV *Operand : N->operands().drop_front())
6359 computeKnownBits(U->getValue(), getDataLayout(), 0, &AC, nullptr, &DT)
6372 return I->second;
6377 return InsertPair.first->second;
6387 (unsigned)getTypeSizeInBits(S->getType()));
6393 if (MDNode *MD = I->getMetadata(LLVMContext::MD_range))
6396 if (std::optional<ConstantRange> Range = CB->getRange())
6400 if (std::optional<ConstantRange> Range = A->getRange())
6408 if (AddRec->getNoWrapFlags(Flags) != Flags) {
6409 AddRec->setNoWrapFlags(Flags);
6420 unsigned BitWidth = getTypeSizeInBits(U->getType());
6429 // and other addrecs in the same loop (for non-affine addrecs). The code
6431 auto *P = dyn_cast<PHINode>(U->getValue());
6437 // and this leads to false-positive recurrence test.
6438 for (auto *Pred : predecessors(P->getParent()))
6449 auto *L = LI.getLoopFor(P->getParent());
6450 assert(L && L->getHeader() == P->getParent());
6451 if (!L->contains(BO->getParent()))
6460 switch (BO->getOpcode()) {
6469 if (BO->getOperand(0) != P)
6484 APInt TCAP(BitWidth, TC-1);
6490 switch (BO->getOpcode()) {
6496 // saturation => 0 or -1
6544 // Add Expr to the worklist, if Expr is either an N-ary expression or a
6551 switch (Expr->getSCEVType()) {
6553 if (!isa<PHINode>(cast<SCEVUnknown>(Expr)->getValue()))
6579 // Build worklist by queuing operands of N-ary expressions and phi nodes.
6585 for (const SCEV *Op : P->operands())
6590 if (const PHINode *P = dyn_cast<PHINode>(UnknownS->getValue())) {
6593 for (auto &Op : reverse(P->operands()))
6606 if (const PHINode *P = dyn_cast<PHINode>(UnknownS->getValue()))
6629 return I->second;
6632 return setRange(C, SignHint, ConstantRange(C->getAPInt()));
6639 unsigned BitWidth = getTypeSizeInBits(S->getType());
6651 APInt::getMaxValue(BitWidth) - Remainder + 1);
6662 switch (S->getSCEVType()) {
6669 ConstantRange X = getRangeRef(Trunc->getOperand(), SignHint, Depth + 1);
6676 ConstantRange X = getRangeRef(ZExt->getOperand(), SignHint, Depth + 1);
6683 ConstantRange X = getRangeRef(SExt->getOperand(), SignHint, Depth + 1);
6690 ConstantRange X = getRangeRef(PtrToInt->getOperand(), SignHint, Depth + 1);
6695 ConstantRange X = getRangeRef(Add->getOperand(0), SignHint, Depth + 1);
6697 if (Add->hasNoSignedWrap())
6699 if (Add->hasNoUnsignedWrap())
6701 for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i)
6702 X = X.addWithNoWrap(getRangeRef(Add->getOperand(i), SignHint, Depth + 1),
6709 ConstantRange X = getRangeRef(Mul->getOperand(0), SignHint, Depth + 1);
6710 for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i)
6711 X = X.multiply(getRangeRef(Mul->getOperand(i), SignHint, Depth + 1));
6717 ConstantRange X = getRangeRef(UDiv->getLHS(), SignHint, Depth + 1);
6718 ConstantRange Y = getRangeRef(UDiv->getRHS(), SignHint, Depth + 1);
6726 if (AddRec->hasNoUnsignedWrap()) {
6727 APInt UnsignedMinValue = getUnsignedRangeMin(AddRec->getStart());
6738 if (AddRec->hasNoSignedWrap()) {
6741 for (unsigned i = 1, e = AddRec->getNumOperands(); i != e; ++i) {
6742 if (!isKnownNonNegative(AddRec->getOperand(i)))
6744 if (!isKnownNonPositive(AddRec->getOperand(i)))
6749 ConstantRange::getNonEmpty(getSignedRangeMin(AddRec->getStart()),
6755 getSignedRangeMax(AddRec->getStart()) +
6760 // TODO: non-affine addrec
6761 if (AddRec->isAffine()) {
6763 getConstantMaxBackedgeTakenCount(AddRec->getLoop());
6765 APInt MaxBECount = cast<SCEVConstant>(MaxBEScev)->getAPInt();
6777 AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount);
6782 AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount);
6791 getSymbolicMaxBackedgeTakenCount(AddRec->getLoop());
6793 getTypeSizeInBits(MaxBEScev->getType()) <= BitWidth &&
6794 AddRec->hasNoSelfWrap()) {
6811 switch (S->getSCEVType()) {
6830 ConstantRange X = getRangeRef(NAry->getOperand(0), SignHint, Depth + 1);
6831 for (unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6833 ID, {X, getRangeRef(NAry->getOperand(i), SignHint, Depth + 1)});
6839 Value *V = U->getValue();
6862 if (U->getType()->isPointerTy()) {
6865 unsigned ptrSize = DL.getPointerTypeSizeInBits(U->getType());
6866 int ptrIdxDiff = ptrSize - BitWidth;
6868 NS -= ptrIdxDiff;
6885 ConstantRange(APInt::getSignedMinValue(BitWidth).ashr(NS - 1),
6886 APInt::getSignedMaxValue(BitWidth).ashr(NS - 1) + 1),
6889 if (U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6899 // The highest address the object can start is ObjSize bytes before the
6903 // because if they would there's no possible start address for the
6905 APInt MaxVal = APInt::getMaxValue(BitWidth) - APInt(BitWidth, ObjSize);
6906 uint64_t Align = U->getValue()->getPointerAlignment(DL).value();
6908 MaxVal -= APInt(BitWidth, Rem);
6923 for (const auto &Op : Phi->operands()) {
6940 if (II->getIntrinsicID() == Intrinsic::vscale) {
6982 // abs(INT_SMIN) = abs(-128) = abs(0x80) = -0x80 = 0x80 = 128.
6983 // This equations hold true due to the well-defined wrap-around behavior of
7001 APInt StartUpper = StartRange.getUpper() - 1;
7002 APInt MovedBoundary = Descending ? (StartLower - std::move(Offset))
7024 assert(getTypeSizeInBits(Start->getType()) ==
7025 getTypeSizeInBits(Step->getType()) &&
7026 getTypeSizeInBits(Start->getType()) == MaxBECount.getBitWidth() &&
7053 assert(AddRec->isAffine() && "Non-affine AddRecs are not suppored!\n");
7054 assert(AddRec->hasNoSelfWrap() &&
7055 "This only works for non-self-wrapping AddRecs!");
7057 const SCEV *Step = AddRec->getStepRecurrence(*this);
7061 // Let's make sure that we can prove that we do not self-wrap during
7066 if (getTypeSizeInBits(MaxBECount->getType()) >
7067 getTypeSizeInBits(AddRec->getType()))
7069 MaxBECount = getNoopOrZeroExtend(MaxBECount, AddRec->getType());
7070 const SCEV *RangeWidth = getMinusOne(AddRec->getType());
7081 const SCEV *End = AddRec->evaluateAtIteration(MaxBECount, *this);
7083 // We know that there is no self-wrap. Let's take Start and End values and
7095 const SCEV *Start = applyLoopGuards(AddRec->getStart(), AddRec->getLoop());
7125 assert(getTypeSizeInBits(Start->getType()) == BitWidth &&
7126 getTypeSizeInBits(Step->getType()) == BitWidth &&
7139 assert(SE.getTypeSizeInBits(S->getType()) == BitWidth &&
7146 if (SA->getNumOperands() != 2 || !isa<SCEVConstant>(SA->getOperand(0)))
7149 Offset = cast<SCEVConstant>(SA->getOperand(0))->getAPInt();
7150 S = SA->getOperand(1);
7155 CastOp = SCast->getSCEVType();
7156 S = SCast->getOperand();
7164 !match(SU->getValue(), m_Select(m_Value(Condition), m_APInt(TrueVal),
7173 // Re-apply the cast we peeled off earlier
7193 // Re-apply the constant offset we peeled off earlier
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);
7230 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount);
7232 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount);
7243 if (BinOp->hasNoUnsignedWrap())
7245 if (BinOp->hasNoSignedWrap())
7256 return &*AddRec->getLoop()->getHeader()->begin();
7258 if (auto *I = dyn_cast<Instruction>(U->getValue()))
7291 for (const auto *Op : S->operands())
7306 if (A->getParent() == B->getParent() &&
7307 isGuaranteedToTransferExecutionToSuccessor(A->getIterator(),
7308 B->getIterator()))
7311 auto *BLoop = LI.getLoopFor(B->getParent());
7312 if (BLoop && BLoop->getHeader() == B->getParent() &&
7313 BLoop->getLoopPreheader() == A->getParent() &&
7314 isGuaranteedToTransferExecutionToSuccessor(A->getIterator(),
7315 A->getParent()->end()) &&
7316 isGuaranteedToTransferExecutionToSuccessor(B->getParent()->begin(),
7317 B->getIterator()))
7340 for (const Use &Op : I->operands()) {
7343 if (isSCEVable(Op->getType()))
7363 auto *ExitingBB = L->getExitingBlock();
7370 // We start by assuming \c I, the post-inc add recurrence, is poison. Only
7379 for (const Use &U : Poison->uses()) {
7382 DT.dominates(PoisonUser->getParent(), ExitingBB))
7385 if (propagatesPoison(U) && L->contains(PoisonUser))
7402 return !SI->isSimple();
7404 return I->mayThrow() || I->mayWriteToMemory();
7410 for (auto *BB : L->getBlocks())
7425 return Itr->second;
7478 if (!isSCEVable(V->getType()))
7486 if (!DT.isReachableFromEntry(I->getParent()))
7487 return getUnknown(PoisonValue::get(V->getType()));
7498 bool IsConstArg = isa<ConstantInt>(BO->RHS);
7499 switch (BO->Opcode) {
7506 if (BO->Op) {
7507 if (BO->Op != V && getExistingSCEV(BO->Op)) {
7508 Ops.push_back(BO->Op);
7512 Ops.push_back(BO->RHS);
7513 auto NewBO = MatchBinaryOp(BO->LHS, getDataLayout(), AC, DT,
7516 (BO->Opcode == Instruction::Add &&
7517 (NewBO->Opcode != Instruction::Add &&
7518 NewBO->Opcode != Instruction::Sub)) ||
7519 (BO->Opcode == Instruction::Mul &&
7520 NewBO->Opcode != Instruction::Mul)) {
7521 Ops.push_back(BO->LHS);
7526 if (BO->Op && (BO->IsNSW || BO->IsNUW)) {
7527 auto *I = dyn_cast<Instruction>(BO->Op);
7529 Ops.push_back(BO->LHS);
7549 if (!IsConstArg && !BO->LHS->getType()->isIntegerTy(1))
7559 Ops.push_back(BO->LHS);
7560 Ops.push_back(BO->RHS);
7564 switch (U->getOpcode()) {
7569 Ops.push_back(U->getOperand(0));
7573 if (isSCEVable(U->getType()) && isSCEVable(U->getOperand(0)->getType())) {
7574 Ops.push_back(U->getOperand(0));
7581 Ops.push_back(U->getOperand(0));
7582 Ops.push_back(U->getOperand(1));
7586 assert(cast<GEPOperator>(U)->getSourceElementType()->isSized() &&
7588 for (Value *Index : U->operands())
7602 if (U->getType()->isIntegerTy(1) || isa<ConstantInt>(U->getOperand(0)))
7605 auto *ICI = dyn_cast<ICmpInst>(U->getOperand(0));
7608 Value *LHS = ICI->getOperand(0);
7609 Value *RHS = ICI->getOperand(1);
7610 if (ICI->getPredicate() == CmpInst::ICMP_EQ ||
7611 ICI->getPredicate() == CmpInst::ICMP_NE) {
7612 if (!(isa<ConstantInt>(RHS) && cast<ConstantInt>(RHS)->isZero()))
7614 } else if (getTypeSizeInBits(LHS->getType()) >
7615 getTypeSizeInBits(U->getType()))
7622 for (Value *Inc : U->operands())
7629 if (Value *RV = cast<CallBase>(U)->getReturnedArgOperand()) {
7635 switch (II->getIntrinsicID()) {
7637 Ops.push_back(II->getArgOperand(0));
7645 Ops.push_back(II->getArgOperand(0));
7646 Ops.push_back(II->getArgOperand(1));
7651 Ops.push_back(II->getArgOperand(0));
7664 if (!isSCEVable(V->getType()))
7672 if (!DT.isReachableFromEntry(I->getParent()))
7673 return getUnknown(PoisonValue::get(V->getType()));
7687 switch (BO->Opcode) {
7692 // because it leads to N-1 getAddExpr calls for N ultimate operands.
7697 if (BO->Op) {
7698 if (auto *OpSCEV = getExistingSCEV(BO->Op)) {
7708 // addition - they may not apply to other additions that can be
7710 const SCEV *RHS = getSCEV(BO->RHS);
7711 SCEV::NoWrapFlags Flags = getNoWrapFlagsFromUB(BO->Op);
7713 const SCEV *LHS = getSCEV(BO->LHS);
7714 if (BO->Opcode == Instruction::Sub)
7722 if (BO->Opcode == Instruction::Sub)
7723 AddOps.push_back(getNegativeSCEV(getSCEV(BO->RHS)));
7725 AddOps.push_back(getSCEV(BO->RHS));
7727 auto NewBO = MatchBinaryOp(BO->LHS, getDataLayout(), AC, DT,
7729 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7730 NewBO->Opcode != Instruction::Sub)) {
7731 AddOps.push_back(getSCEV(BO->LHS));
7743 if (BO->Op) {
7744 if (auto *OpSCEV = getExistingSCEV(BO->Op)) {
7749 SCEV::NoWrapFlags Flags = getNoWrapFlagsFromUB(BO->Op);
7751 LHS = getSCEV(BO->LHS);
7752 RHS = getSCEV(BO->RHS);
7758 MulOps.push_back(getSCEV(BO->RHS));
7759 auto NewBO = MatchBinaryOp(BO->LHS, getDataLayout(), AC, DT,
7761 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7762 MulOps.push_back(getSCEV(BO->LHS));
7771 LHS = getSCEV(BO->LHS);
7772 RHS = getSCEV(BO->RHS);
7775 LHS = getSCEV(BO->LHS);
7776 RHS = getSCEV(BO->RHS);
7780 if (BO->Op)
7781 Flags = getNoWrapFlagsFromUB(BO->Op);
7782 LHS = getSCEV(BO->LHS);
7783 RHS = getSCEV(BO->RHS);
7789 if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->RHS)) {
7790 if (CI->isZero())
7791 return getSCEV(BO->RHS);
7792 if (CI->isMinusOne())
7793 return getSCEV(BO->LHS);
7794 const APInt &A = CI->getValue();
7797 // constants, obscuring what would otherwise be a low-bits mask.
7799 // knew about to reconstruct a low-bits mask value.
7804 computeKnownBits(BO->LHS, Known, getDataLayout(),
7808 APInt::getLowBitsSet(BitWidth, BitWidth - LZ - TZ).shl(TZ);
7811 const SCEV *LHS = getSCEV(BO->LHS);
7814 if (auto *OpC = dyn_cast<SCEVConstant>(LHSMul->getOperand(0))) {
7816 unsigned MulZeros = OpC->getAPInt().countr_zero();
7818 APInt DivAmt = APInt::getOneBitSet(BitWidth, TZ - GCD);
7820 MulOps.push_back(getConstant(OpC->getAPInt().lshr(GCD)));
7821 append_range(MulOps, LHSMul->operands().drop_front());
7822 auto *NewMul = getMulExpr(MulOps, LHSMul->getNoWrapFlags());
7831 IntegerType::get(getContext(), BitWidth - LZ - TZ)),
7832 BO->LHS->getType()),
7836 // Binary `and` is a bit-wise `umin`.
7837 if (BO->LHS->getType()->isIntegerTy(1)) {
7838 LHS = getSCEV(BO->LHS);
7839 RHS = getSCEV(BO->RHS);
7845 // Binary `or` is a bit-wise `umax`.
7846 if (BO->LHS->getType()->isIntegerTy(1)) {
7847 LHS = getSCEV(BO->LHS);
7848 RHS = getSCEV(BO->RHS);
7854 if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->RHS)) {
7855 // If the RHS of xor is -1, then this is a not operation.
7856 if (CI->isMinusOne())
7857 return getNotSCEV(getSCEV(BO->LHS));
7859 // Model xor(and(x, C), C) as and(~x, C), if C is a low-bits mask.
7860 // This is a variant of the check for xor with -1, and it handles
7861 // the case where instcombine has trimmed non-demanded bits out
7862 // of an xor with -1.
7863 if (auto *LBO = dyn_cast<BinaryOperator>(BO->LHS))
7864 if (ConstantInt *LCI = dyn_cast<ConstantInt>(LBO->getOperand(1)))
7865 if (LBO->getOpcode() == Instruction::And &&
7866 LCI->getValue() == CI->getValue())
7868 dyn_cast<SCEVZeroExtendExpr>(getSCEV(BO->LHS))) {
7869 Type *UTy = BO->LHS->getType();
7870 const SCEV *Z0 = Z->getOperand();
7871 Type *Z0Ty = Z0->getType();
7874 // If C is a low-bits mask, the zero extend is serving to
7876 // re-apply the zext.
7877 if (CI->getValue().isMask(Z0TySize))
7880 // If C is a single bit, it may be in the sign-bit position
7881 // before the zero-extend. In this case, represent the xor
7882 // using an add, which is equivalent, and re-apply the zext.
7883 APInt Trunc = CI->getValue().trunc(Z0TySize);
7884 if (Trunc.zext(getTypeSizeInBits(UTy)) == CI->getValue() &&
7894 if (ConstantInt *SA = dyn_cast<ConstantInt>(BO->RHS)) {
7895 uint32_t BitWidth = cast<IntegerType>(SA->getType())->getBitWidth();
7901 if (SA->getValue().uge(BitWidth))
7907 // left shifting by bitwidth - 1.
7909 if (BO->Op) {
7910 auto MulFlags = getNoWrapFlagsFromUB(BO->Op);
7912 ((MulFlags & SCEV::FlagNUW) || SA->getValue().ult(BitWidth - 1)))
7919 getContext(), APInt::getOneBitSet(BitWidth, SA->getZExtValue()));
7920 return getMulExpr(getSCEV(BO->LHS), getConstant(X), Flags);
7926 ConstantInt *CI = dyn_cast<ConstantInt>(BO->RHS);
7930 Type *OuterTy = BO->LHS->getType();
7936 if (CI->getValue().uge(BitWidth))
7939 if (CI->isZero())
7940 return getSCEV(BO->LHS); // shift by zero --> noop
7942 uint64_t AShrAmt = CI->getZExtValue();
7943 Type *TruncTy = IntegerType::get(getContext(), BitWidth - AShrAmt);
7945 Operator *L = dyn_cast<Operator>(BO->LHS);
7950 if (L && L->getOpcode() == Instruction::Add) {
7956 Operator *LShift = dyn_cast<Operator>(L->getOperand(0));
7957 ConstantInt *AddOperandCI = dyn_cast<ConstantInt>(L->getOperand(1));
7958 if (LShift && LShift->getOpcode() == Instruction::Shl) {
7960 const SCEV *ShlOp0SCEV = getSCEV(LShift->getOperand(0));
7961 ShlAmtCI = dyn_cast<ConstantInt>(LShift->getOperand(1));
7965 APInt AddOperand = AddOperandCI->getValue().ashr(AShrAmt);
7966 AddConstant = getConstant(AddOperand.trunc(BitWidth - AShrAmt));
7973 } else if (L && L->getOpcode() == Instruction::Shl) {
7978 const SCEV *ShlOp0SCEV = getSCEV(L->getOperand(0));
7979 ShlAmtCI = dyn_cast<ConstantInt>(L->getOperand(1));
7988 // 1) For a two-shift sext-inreg, i.e. n = m,
7991 // 2) When n > m, use sext(mul(trunc(x), 2^(n-m)))) as the SCEV
7993 // the multiplier, 1 << (ShlAmt - AShrAmt), fits into TruncTy as
7994 // ShlAmt - AShrAmt < Amt.
7995 const APInt &ShlAmt = ShlAmtCI->getValue();
7997 APInt Mul = APInt::getOneBitSet(BitWidth - AShrAmt,
7998 ShlAmtCI->getZExtValue() - AShrAmt);
8001 if (L->getOpcode() != Instruction::Shl)
8011 switch (U->getOpcode()) {
8013 return getTruncateExpr(getSCEV(U->getOperand(0)), U->getType());
8016 return getZeroExtendExpr(getSCEV(U->getOperand(0)), U->getType());
8019 if (auto BO = MatchBinaryOp(U->getOperand(0), getDataLayout(), AC, DT,
8022 // A + (-1)*B. By pushing sign extension onto its operands we are much
8026 // sext((A + B + ...)<nsw>) --> (sext(A) + sext(B) + ...)<nsw>
8028 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8029 Type *Ty = U->getType();
8030 auto *V1 = getSignExtendExpr(getSCEV(BO->LHS), Ty);
8031 auto *V2 = getSignExtendExpr(getSCEV(BO->RHS), Ty);
8035 return getSignExtendExpr(getSCEV(U->getOperand(0)), U->getType());
8038 // BitCasts are no-op casts so we just eliminate the cast.
8039 if (isSCEVable(U->getType()) && isSCEVable(U->getOperand(0)->getType()))
8040 return getSCEV(U->getOperand(0));
8044 // Pointer to integer cast is straight-forward, so do model it.
8045 const SCEV *Op = getSCEV(U->getOperand(0));
8046 Type *DstIntTy = U->getType();
8059 // If both operands are non-negative, this is just an udiv.
8060 if (isKnownNonNegative(getSCEV(U->getOperand(0))) &&
8061 isKnownNonNegative(getSCEV(U->getOperand(1))))
8062 return getUDivExpr(getSCEV(U->getOperand(0)), getSCEV(U->getOperand(1)));
8066 // If both operands are non-negative, this is just an urem.
8067 if (isKnownNonNegative(getSCEV(U->getOperand(0))) &&
8068 isKnownNonNegative(getSCEV(U->getOperand(1))))
8069 return getURemExpr(getSCEV(U->getOperand(0)), getSCEV(U->getOperand(1)));
8079 return createNodeForSelectOrPHI(U, U->getOperand(0), U->getOperand(1),
8080 U->getOperand(2));
8084 if (Value *RV = cast<CallBase>(U)->getReturnedArgOperand())
8088 switch (II->getIntrinsicID()) {
8091 getSCEV(II->getArgOperand(0)),
8092 /*IsNSW=*/cast<ConstantInt>(II->getArgOperand(1))->isOne());
8094 LHS = getSCEV(II->getArgOperand(0));
8095 RHS = getSCEV(II->getArgOperand(1));
8098 LHS = getSCEV(II->getArgOperand(0));
8099 RHS = getSCEV(II->getArgOperand(1));
8102 LHS = getSCEV(II->getArgOperand(0));
8103 RHS = getSCEV(II->getArgOperand(1));
8106 LHS = getSCEV(II->getArgOperand(0));
8107 RHS = getSCEV(II->getArgOperand(1));
8110 const SCEV *X = getSCEV(II->getArgOperand(0));
8111 const SCEV *Y = getSCEV(II->getArgOperand(1));
8116 const SCEV *X = getSCEV(II->getArgOperand(0));
8117 const SCEV *Y = getSCEV(II->getArgOperand(1));
8126 return getSCEV(II->getArgOperand(0));
8128 return getVScale(II->getType());
8139 //===----------------------------------------------------------------------===//
8147 auto *ExitCountType = ExitCount->getType();
8148 assert(ExitCountType->isIntegerTy());
8149 auto *EvalTy = Type::getIntNTy(ExitCountType->getContext(),
8150 1 + ExitCountType->getScalarSizeInBits());
8160 unsigned ExitCountSize = getTypeSizeInBits(ExitCount->getType());
8161 unsigned EvalSize = EvalTy->getPrimitiveSizeInBits();
8170 getMinusOne(ExitCount->getType()));
8178 getAddExpr(ExitCount, getOne(ExitCount->getType())), EvalTy);
8188 ConstantInt *ExitConst = ExitCount->getValue();
8191 if (ExitConst->getValue().getActiveBits() > 32)
8195 return ((unsigned)ExitConst->getZExtValue()) + 1;
8206 assert(ExitingBlock && "Must pass a non-null exiting block!");
8207 assert(L->isLoopExiting(ExitingBlock) &&
8222 L->getExitingBlocks(ExitingBlocks);
8265 assert(ExitingBlock && "Must pass a non-null exiting block!");
8266 assert(L->isLoopExiting(ExitingBlock) &&
8318 BasicBlock *Header = L->getHeader();
8320 // Push all Loop-header PHIs onto the Worklist stack.
8321 for (PHINode &PN : Header->phis())
8335 return Pair.first->second;
8340 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8346 // succeeds, proceed to actually compute a backedge-taken count and
8349 // backedge-taken count, which could result in infinite recursion.
8353 return Pair.first->second;
8370 append_range(ToForget, LoopUsersIt->second);
8373 // Invalidate constant-evolved loop header phis.
8374 for (PHINode &PN : L->getHeader()->phis())
8378 // Re-lookup the insert position, since the call to
8383 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8389 // - The trip counts of all loops have changed arbitrarily
8390 // - Every llvm::Value has been updated in place to produce a different
8417 if (!isSCEVable(I->getType()) && !isa<WithOverflowInst>(I))
8423 eraseValueFromMap(It->first);
8424 ToForget.push_back(It->second);
8439 // Iterate over all the loops and sub-loops to drop SCEV information.
8450 std::pair<const SCEV *, const Loop *> Entry = I->first;
8459 ToForget.insert(ToForget.end(), LoopUsersItr->second.begin(),
8460 LoopUsersItr->second.end());
8463 // Drop information about expressions based on loop-header PHIs.
8470 LoopWorklist.append(CurrL->begin(), CurrL->end());
8476 forgetLoop(L->getOutermostLoop());
8483 // Drop information about expressions based on loop-header PHIs.
8495 if (!isSCEVable(V->getType()))
8511 if (auto *I = dyn_cast<Instruction>(SU->getValue()))
8512 if (L->contains(I))
8515 if (L->contains(AddRec->getLoop()))
8543 if (!isSCEVable(V->getType()))
8552 // loop-invariant, if S changes to loop invariant), so also invalidate
8564 for (const auto *User : Users->second)
8581 return SE->getCouldNotCompute();
8583 const BasicBlock *Latch = L->getLoopLatch();
8586 return SE->getCouldNotCompute();
8593 assert(BECount != SE->getCouldNotCompute() && "Bad exit SCEV!");
8594 assert(SE->DT.dominates(ENT.ExitingBlock, Latch) &&
8602 Preds->push_back(P);
8611 return SE->getUMinFromMismatchedTypes(Ops, /* Sequential */ true);
8622 return SE->getCouldNotCompute();
8631 return SE->getCouldNotCompute();
8640 return SE->getCouldNotCompute();
8643 /// getConstantMax - Get the constant max backedge taken count for the loop.
8651 return SE->getCouldNotCompute();
8655 "No point in having a non-constant max backedge taken count!");
8672 assert(SE->DT.dominates(ENT.ExitingBlock, L->getLoopLatch()) &&
8678 Predicates->push_back(P);
8685 SymbolicMax = SE->getCouldNotCompute();
8688 SE->getUMinFromMismatchedTypes(ExitCounts, /*Sequential*/ true);
8713 if (ConstantMaxNotTaken->isZero()) {
8714 this->ExactNotTaken = E = ConstantMaxNotTaken;
8715 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8729 "No point in having a non-constant max backedge taken count!");
8733 assert((isa<SCEVCouldNotCompute>(E) || !E->getType()->isPointerTy()) &&
8736 !ConstantMaxNotTaken->getType()->isPointerTy()) &&
8747 /// Allocate memory for BackedgeTakenInfo and copy the not-taken count of each
8767 "No point in having a non-constant max backedge taken count!");
8775 L->getExitingBlocks(ExitingBlocks);
8781 BasicBlock *Latch = L->getLoopLatch(); // may be NULL.
8794 if (auto *BI = dyn_cast<BranchInst>(ExitBB->getTerminator()))
8795 if (auto *CI = dyn_cast<ConstantInt>(BI->getCondition())) {
8796 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
8797 if (ExitIfTrue == CI->isZero())
8825 // non-exiting iterations. Partition the loop exits into two kinds:
8860 // We only care about non-constant SCEVs here, so we can ignore
8877 assert(L->contains(ExitingBlock) && "Exit count for non-loop block?");
8880 const BasicBlock *Latch = L->getLoopLatch();
8884 Instruction *Term = ExitingBlock->getTerminator();
8886 assert(BI->isConditional() && "If unconditional, it can't be in loop!");
8887 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
8888 assert(ExitIfTrue == L->contains(BI->getSuccessor(1)) &&
8891 return computeExitLimitFromCond(L, BI->getCondition(), ExitIfTrue,
8900 if (!L->contains(SBB)) {
8925 (void)this->L;
8926 (void)this->ExitIfTrue;
8927 (void)this->AllowPredicates;
8929 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
8930 this->AllowPredicates == AllowPredicates &&
8935 return Itr->second;
8943 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
8944 this->AllowPredicates == AllowPredicates &&
8975 // With an icmp, it may be feasible to compute an exact backedge-taken count.
8994 if (ExitIfTrue == !CI->getZExtValue())
8998 return getZero(CI->getType());
9007 match(WO->getRHS(), m_APInt(C))) {
9009 ConstantRange::makeExactNoWrapRegion(WO->getBinaryOp(), *C,
9010 WO->getNoWrapKind());
9016 auto *LHS = getSCEV(WO->getLHS());
9055 const Constant *NeutralElement = ConstantInt::get(ExitCond->getType(), IsAnd);
9116 Pred = ExitCond->getPredicate();
9118 Pred = ExitCond->getInversePredicate();
9121 const SCEV *LHS = getSCEV(ExitCond->getOperand(0));
9122 const SCEV *RHS = getSCEV(ExitCond->getOperand(1));
9135 return computeShiftCompareExitLimit(ExitCond->getOperand(0),
9136 ExitCond->getOperand(1), L, OriginalPred);
9149 // If there is a loop-invariant, force it into the RHS.
9163 if (AddRec->getLoop() == L) {
9166 ConstantRange::makeExactICmpRegion(Pred, RHSC->getAPInt());
9168 const SCEV *Ret = AddRec->getNumIterationsInRange(CompRange, *this);
9174 // the same values on self-wrap of the IV, then we can infer that IV
9182 InnerLHS = ZExt->getOperand();
9184 auto *StrideC = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*this));
9185 if (!AR->hasNoSelfWrap() && AR->getLoop() == L && AR->isAffine() &&
9186 StrideC && StrideC->getAPInt().isPowerOf2()) {
9187 auto Flags = AR->getNoWrapFlags();
9189 SmallVector<const SCEV*> Operands{AR->operands()};
9198 // Convert to: while (X-Y != 0)
9199 if (LHS->getType()->isPointerTy()) {
9204 if (RHS->getType()->isPointerTy()) {
9216 // Convert to: while (X-Y == 0)
9217 if (LHS->getType()->isPointerTy()) {
9222 if (RHS->getType()->isPointerTy()) {
9240 auto *OldType = dyn_cast<IntegerType>(LHS->getType());
9246 Type::getIntNTy(OldType->getContext(), OldType->getBitWidth() * 2);
9255 RHS = getAddExpr(getOne(RHS->getType()), RHS);
9273 RHS = getAddExpr(getMinusOne(RHS->getType()), RHS);
9296 assert(!L->contains(ExitingBlock) && "Not an exiting block!");
9299 if (Switch->getDefaultDest() == ExitingBlock)
9302 assert(L->contains(Switch->getDefaultDest()) &&
9304 const SCEV *LHS = getSCEVAtScope(Switch->getCondition(), L);
9305 const SCEV *RHS = getConstant(Switch->findCaseDest(ExitingBlock));
9307 // while (X != Y) --> while (X-Y != 0)
9319 const SCEV *Val = AddRec->evaluateAtIteration(InVal, SE);
9322 return cast<SCEVConstant>(Val)->getValue();
9331 const BasicBlock *Latch = L->getLoopLatch();
9335 const BasicBlock *Predecessor = L->getLoopPredecessor();
9356 return ShiftAmt->getValue().isStrictlyPositive();
9382 // really care about it being the same *kind* of shift instruction --
9391 if (!PNOut || PNOut->getParent() != L->getHeader())
9394 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9418 // recurrences, the value of the recurrence "stabilizes" to either 0 or -1
9430 // {K,ashr,<positive-constant>} stabilizes to signum(K) in at most
9432 Value *FirstValue = PN->getIncomingValueForBlock(Predecessor);
9434 Predecessor->getTerminator(), &DT);
9435 auto *Ty = cast<IntegerType>(RHS->getType());
9439 StableValue = ConstantInt::get(Ty, -1, true);
9447 // Both {K,lshr,<positive-constant>} and {K,shl,<positive-constant>}
9449 StableValue = ConstantInt::get(cast<IntegerType>(RHS->getType()), 0);
9455 assert(Result->getType()->isIntegerTy(1) &&
9458 if (Result->isZeroValue()) {
9459 unsigned BitWidth = getTypeSizeInBits(RHS->getType());
9461 getConstant(getEffectiveSCEVType(RHS->getType()), BitWidth);
9477 if (const Function *F = CI->getCalledFunction())
9486 if (!L->contains(I)) return false;
9491 return L->getHeader() == I->getParent();
9499 /// getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by
9511 for (Value *Op : UseInst->operands()) {
9539 /// getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node
9551 // Record non-constant instructions contained by the loop.
9556 /// EvaluateExpression - Given an expression that passes the
9580 std::vector<Constant*> Operands(I->getNumOperands());
9582 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
9583 Instruction *Operand = dyn_cast<Instruction>(I->getOperand(i));
9585 Operands[i] = dyn_cast<Constant>(I->getOperand(i));
9605 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
9606 if (PN->getIncomingBlock(i) == BB)
9609 auto *CurrentVal = dyn_cast<Constant>(PN->getIncomingValue(i));
9623 /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
9633 return I->second;
9641 BasicBlock *Header = L->getHeader();
9642 assert(PN->getParent() == Header && "Can't evaluate PHI not in loop header!");
9644 BasicBlock *Latch = L->getLoopLatch();
9648 for (PHINode &PHI : Header->phis()) {
9655 Value *BEValue = PN->getIncomingValueForBlock(Latch);
9669 // EvaluateExpression adds non-phi values to the CurrentIterVals map.
9685 if (!PHI || PHI == PN || PHI->getParent() != Header) continue;
9694 Value *BEValue = PHI->getIncomingValueForBlock(Latch);
9718 if (PN->getNumIncomingValues() != 2) return getCouldNotCompute();
9721 BasicBlock *Header = L->getHeader();
9722 assert(PN->getParent() == Header && "Can't evaluate PHI not in loop header!");
9724 BasicBlock *Latch = L->getLoopLatch();
9727 for (PHINode &PHI : Header->phis()) {
9746 if (CondVal->getValue() == uint64_t(ExitWhen)) {
9760 if (!PHI || PHI->getParent() != Header) continue;
9767 Value *BEValue = PHI->getIncomingValueForBlock(Latch);
9804 switch (V->getSCEVType()) {
9810 return cast<SCEVConstant>(V)->getValue();
9812 return dyn_cast<Constant>(cast<SCEVUnknown>(V)->getValue());
9815 if (Constant *CastOp = BuildConstantFromSCEV(P2I->getOperand()))
9816 return ConstantExpr::getPtrToInt(CastOp, P2I->getType());
9822 if (Constant *CastOp = BuildConstantFromSCEV(ST->getOperand()))
9823 return ConstantExpr::getTrunc(CastOp, ST->getType());
9829 for (const SCEV *Op : SA->operands()) {
9837 assert(!C->getType()->isPointerTy() &&
9839 if (OpC->getType()->isPointerTy()) {
9842 C = ConstantExpr::getGetElementPtr(Type::getInt8Ty(C->getContext()),
9867 switch (S->getSCEVType()) {
9872 return getCastExpr(S->getSCEVType(), NewOps[0], S->getType());
9875 return getAddRecExpr(NewOps, AddRec->getLoop(), AddRec->getNoWrapFlags());
9878 return getAddExpr(NewOps, cast<SCEVAddExpr>(S)->getNoWrapFlags());
9880 return getMulExpr(NewOps, cast<SCEVMulExpr>(S)->getNoWrapFlags());
9887 return getMinMaxExpr(S->getSCEVType(), NewOps);
9889 return getSequentialMinMaxExpr(S->getSCEVType(), NewOps);
9901 switch (V->getSCEVType()) {
9910 // Avoid performing the look-up in the common case where the specified
9911 // expression has no loop-variant portions.
9912 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
9913 const SCEV *OpAtScope = getSCEVAtScope(AddRec->getOperand(i), L);
9914 if (OpAtScope == AddRec->getOperand(i))
9920 NewOps.reserve(AddRec->getNumOperands());
9921 append_range(NewOps, AddRec->operands().take_front(i));
9924 NewOps.push_back(getSCEVAtScope(AddRec->getOperand(i), L));
9927 NewOps, AddRec->getLoop(), AddRec->getNoWrapFlags(SCEV::FlagNW));
9939 if (!AddRec->getLoop()->contains(L)) {
9942 const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
9947 return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
9964 ArrayRef<const SCEV *> Ops = V->operands();
9965 // Avoid performing the look-up in the common case where the specified
9966 // expression has no loop-variant portions.
9989 // If this instruction is evolved from a constant-evolving PHI, compute the
9992 Instruction *I = dyn_cast<Instruction>(SU->getValue());
9997 const Loop *CurrLoop = this->LI[I->getParent()];
9999 if (CurrLoop && CurrLoop->getParentLoop() == L &&
10000 PN->getParent() == CurrLoop->getHeader()) {
10002 // to see if the loop that contains it has a known backedge-taken
10008 if (BackedgeTakenCount->isZero()) {
10011 for (unsigned i = 0; i < PN->getNumIncomingValues(); i++) {
10012 if (!CurrLoop->contains(PN->getIncomingBlock(i))) {
10014 InitValue = PN->getIncomingValue(i);
10015 else if (InitValue != PN->getIncomingValue(i)) {
10028 PN->getNumIncomingValues() == 2) {
10031 CurrLoop->contains(PN->getIncomingBlock(0)) ? 0 : 1;
10032 Value *BackedgeVal = PN->getIncomingValue(InLoopPred);
10033 if (CurrLoop->isLoopInvariant(BackedgeVal))
10041 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10056 Operands.reserve(I->getNumOperands());
10058 for (Value *Op : I->operands()) {
10064 // If any of the operands is non-constant and if they are
10065 // non-integer and non-pointer, don't even try to analyze them
10067 if (!isSCEVable(Op->getType()))
10077 assert(C->getType() == Op->getType() && "Type mismatch");
10105 return stripInjectiveFunctions(ZExt->getOperand());
10107 return stripInjectiveFunctions(SExt->getOperand());
10122 assert(BW == SE.getTypeSizeInBits(B->getType()));
10123 assert(A != 0 && "A must be non-zero.");
10145 APInt AD = A.lshr(Mult2).trunc(BW - Mult2); // AD = A / D
10164 /// compile- time constants.
10167 assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!");
10168 const SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
10169 const SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
10170 const SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
10180 APInt L = LC->getAPInt();
10181 APInt M = MC->getAPInt();
10182 APInt N = NC->getAPInt();
10185 unsigned BitWidth = LC->getAPInt().getBitWidth();
10189 // The sign-extension (as opposed to a zero-extension) here matches the
10198 // After n iterations the accumulated value Acc is L + nM + n(n-1)/2 N.
10201 // L + nM + n(n-1)/2 N = 0, or 2L + 2M n + n(n-1) N = 0.
10203 // N n^2 + (2M-N) n + 2L = 0.
10206 APInt B = 2 * M - A;
10222 unsigned W = std::max(X->getBitWidth(), Y->getBitWidth());
10223 APInt XW = X->sext(W);
10224 APInt YW = Y->sext(W);
10233 /// When solving addrec-related equations, it is preferable to return a value
10247 unsigned W = X->getBitWidth();
10248 if (BitWidth > 1 && BitWidth < W && X->isIntN(BitWidth))
10249 return X->trunc(BitWidth);
10258 /// If the calculated value is a BW-bit integer (for BW > 1), it will be
10284 if (!V->isZero())
10294 /// while c(n-1) does.
10303 assert(AddRec->getOperand(0)->isZero() &&
10309 assert(Range.contains(APInt(SE.getTypeSizeInBits(AddRec->getType()), 0)) &&
10327 [&](APInt Bound) -> std::pair<std::optional<APInt>, bool> {
10338 SO = APIntOps::SolveQuadraticEquationWrap(A, B, -Bound, BitWidth);
10343 APIntOps::SolveQuadraticEquationWrap(A, B, -Bound, BitWidth + 1);
10348 if (Range.contains(V0->getValue()))
10350 // X should be at least 1, so X-1 is non-negative.
10351 ConstantInt *C1 = ConstantInt::get(SE.getContext(), X-1);
10353 if (Range.contains(V1->getValue()))
10379 APInt Lower = Range.getLower().sext(A.getBitWidth()) - 1;
10435 // is now expressed as a single expression, V = x-y. So the exit test is
10443 if (C->getValue()->isZero()) return C;
10456 if (!AddRec || AddRec->getLoop() != L)
10459 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of
10461 if (AddRec->isQuadratic() && AddRec->getType()->isIntegerTy()) {
10473 if (!AddRec->isAffine())
10483 // Step*N = -Start (mod 2^BW)
10488 const SCEV *Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
10489 const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop());
10500 // N = -Start/Step (as unsigned)
10502 // N = Start/-Step
10510 // 1*N = -Start; -1*N = Start (mod 2^BW), so:
10513 (StepC->getValue()->isOne() || StepC->getValue()->isMinusOne())) {
10518 // we end up with a loop whose backedge-taken count is n - 1. Detect this
10522 // isn't context-sensitive; it doesn't know that we only care about the
10524 const SCEV *Zero = getZero(Distance->getType());
10525 const SCEV *One = getOne(Distance->getType());
10529 // as "unsigned_max(Distance + 1) - 1".
10531 MaxBECount = APIntOps::umin(MaxBECount, CR.getUnsignedMax() - 1);
10538 // is true) and the addition is no-wrap we can use unsigned divide to
10542 if (ControlsOnlyExit && AddRec->hasNoSelfWrap() &&
10543 loopHasNoAbnormalExits(AddRec->getLoop())) {
10565 if (!StepC || StepC->getValue()->isZero())
10567 const SCEV *E = SolveLinEquationWithOverflow(StepC->getAPInt(),
10585 // If the value is a constant, check to see if it is known to be non-zero
10588 if (!C->getValue()->isZero())
10589 return getZero(C->getType());
10604 if (const BasicBlock *Pred = BB->getSinglePredecessor())
10611 return {L->getLoopPredecessor(), L->getHeader()};
10619 /// front-end may have replicated the controlling expression.
10628 return A->isIdenticalTo(B) && (isa<BinaryOperator>(A) || isa<GetElementPtrInst>(A));
10635 if (const Instruction *AI = dyn_cast<Instruction>(AU->getValue()))
10636 if (const Instruction *BI = dyn_cast<Instruction>(BU->getValue()))
10646 if (!Add || Add->getNumOperands() != 2)
10648 if (auto *ME = dyn_cast<SCEVMulExpr>(Add->getOperand(0));
10649 ME && ME->getNumOperands() == 2 && ME->getOperand(0)->isAllOnesValue()) {
10650 LHS = Add->getOperand(1);
10651 RHS = ME->getOperand(1);
10654 if (auto *ME = dyn_cast<SCEVMulExpr>(Add->getOperand(1));
10655 ME && ME->getNumOperands() == 2 && ME->getOperand(0)->isAllOnesValue()) {
10656 LHS = Add->getOperand(0);
10657 RHS = ME->getOperand(1);
10682 if (!ICmpInst::compare(LHSC->getAPInt(), RHSC->getAPInt(), Pred))
10692 // If we're comparing an addrec with a value which is loop-invariant in the
10694 // as both operands could be addrecs loop-invariant in each other's loop.
10696 const Loop *L = AR->getLoop();
10697 if (isLoopInvariant(LHS, L) && properlyDominates(LHS, L->getHeader())) {
10705 // cases, and canonicalize *-or-equal comparisons to regular comparisons.
10707 const APInt &RA = RC->getAPInt();
10735 // Fold ((-1) * %a) + %b == 0 (equivalent to %b-%a == 0) into %a == %b.
10748 RHS = getConstant(RA - 1);
10760 RHS = getConstant(RA - 1);
10786 RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS,
10791 LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS,
10799 RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS,
10804 LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS,
10812 RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS,
10817 LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS);
10824 RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS);
10828 LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS,
10868 return isKnownNonZero(SExt->getOperand(0));
10898 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
10899 DT.dominates(L2->getHeader(), L1->getHeader())) &&
10905 return DT.properlyDominates(L1->getHeader(), L2->getHeader());
10910 // if LHS contains unknown non-invariant SCEV then bail out.
10916 // if RHS contains unknown non-invariant SCEV then bail out.
10964 isBasicBlockEntryGuardedByCond(CtxI->getParent(), Pred, LHS, RHS);
10974 if (isBasicBlockEntryGuardedByCond(CtxI->getParent(), Pred, LHS, RHS))
10976 if (isBasicBlockEntryGuardedByCond(CtxI->getParent(),
10986 const Loop *L = LHS->getLoop();
10987 return isLoopEntryGuardedByCond(L, Pred, LHS->getStart(), RHS) &&
10988 isLoopBackedgeGuardedByCond(L, Pred, LHS->getPostIncExpr(*this), RHS);
11034 if (!LHS->hasNoUnsignedWrap())
11040 if (!LHS->hasNoSignedWrap())
11043 const SCEV *Step = LHS->getStepRecurrence(*this);
11059 // If there is a loop-invariant, force it into the RHS, otherwise bail out.
11069 if (!ArLHS || ArLHS->getLoop() != L)
11096 return ScalarEvolution::LoopInvariantPredicate(Pred, ArLHS->getStart(),
11108 assert(ArLHS->hasNoUnsignedWrap() && "Is a requirement of monotonicity!");
11112 // - Positive step; (TODO: lift this limitation)
11113 // - nuw - does not cross zero boundary;
11114 // - nsw - does not cross SINT_MAX boundary;
11121 // - ArLHS is always negative. It means that ArLHS <u RHS is always false;
11122 // - ArLHS is always non-negative. Because of (3) RHS is also non-negative.
11128 if (ArLHS->hasNoSignedWrap() && ArLHS->isAffine() &&
11129 isKnownPositive(ArLHS->getStepRecurrence(*this)) &&
11132 return ScalarEvolution::LoopInvariantPredicate(Pred, ArLHS->getStart(),
11153 for (auto *Op : UMin->operands())
11165 // - The predicate is monotonic in the iteration space.
11166 // - If the check does not fail on the 1st iteration:
11167 // - No overflow will happen during first MaxIter iterations;
11168 // - It will not fail on the MaxIter'th iteration.
11172 // If there is a loop-invariant, force it into the RHS, otherwise bail out.
11182 if (!AR || AR->getLoop() != L)
11189 // TODO: Support steps other than +/- 1.
11190 const SCEV *Step = AR->getStepRecurrence(*this);
11191 auto *One = getOne(Step->getType());
11199 if (AR->getType() != MaxIter->getType())
11203 const SCEV *Last = AR->evaluateAtIteration(MaxIter, *this);
11207 // Because step is +/- 1 and MaxIter has same type as Start (i.e. it does
11211 // Start <= Last for step = 1 or Start >= Last for step = -1.
11216 const SCEV *Start = AR->getStart();
11282 XConstOp = getZero(X->getType());
11291 YConstOp = getZero(Y->getType());
11303 OutC1 = cast<SCEVConstant>(XConstOp)->getAPInt();
11304 OutC2 = cast<SCEVConstant>(YConstOp)->getAPInt();
11377 isKnownPredicate(CmpInst::ICMP_SGE, LHS, getZero(LHS->getType())) &&
11398 /// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is
11408 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11412 assert(!verifyFunction(*L->getHeader()->getParent(), &dbgs()) &&
11413 "This cannot be done on broken IR!");
11419 BasicBlock *Latch = L->getLoopLatch();
11424 dyn_cast<BranchInst>(Latch->getTerminator());
11425 if (LoopContinuePredicate && LoopContinuePredicate->isConditional() &&
11427 LoopContinuePredicate->getCondition(),
11428 LoopContinuePredicate->getSuccessor(0) != L->getHeader()))
11432 // -- that can lead to O(n!) time complexity.
11445 Type *Ty = LatchBECount->getType();
11459 if (!DT.dominates(CI, Latch->getTerminator()))
11462 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0), false))
11469 for (DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11470 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11473 BasicBlock *BB = DTN->getBlock();
11477 BasicBlock *PBB = BB->getSinglePredecessor();
11481 BranchInst *ContinuePredicate = dyn_cast<BranchInst>(PBB->getTerminator());
11482 if (!ContinuePredicate || !ContinuePredicate->isConditional())
11485 Value *Condition = ContinuePredicate->getCondition();
11499 BB != ContinuePredicate->getSuccessor(0)))
11515 assert(!verifyFunction(*BB->getParent(), &dbgs()) &&
11516 "This cannot be done on broken IR!");
11520 // non-strict comparison is known from ranges and non-equality is known from
11522 // to prove non-equality and non-strict comparison separately.
11529 [&](std::function<bool(ICmpInst::Predicate)> Fn) -> bool {
11549 const Instruction *CtxI = &BB->front();
11567 if (ContainingLoop && ContainingLoop->getHeader() == BB)
11568 PredBB = ContainingLoop->getLoopPredecessor();
11570 PredBB = BB->getSinglePredecessor();
11574 dyn_cast<BranchInst>(Pair.first->getTerminator());
11575 if (!BlockEntryPredicate || BlockEntryPredicate->isUnconditional())
11578 if (ProveViaCond(BlockEntryPredicate->getCondition(),
11579 BlockEntryPredicate->getSuccessor(0) != Pair.second))
11591 if (ProveViaCond(CI->getArgOperand(0), false))
11596 auto *GuardDecl = F.getParent()->getFunction(
11599 for (const auto *GU : GuardDecl->users())
11601 if (Guard->getFunction() == BB->getParent() && DT.dominates(Guard, BB))
11602 if (ProveViaCond(Guard->getArgOperand(0), false))
11625 return isBasicBlockEntryGuardedByCond(L->getHeader(), Pred, LHS, RHS);
11634 ConstantInt::getBool(FoundCondValue->getContext(), Inverse))
11662 FoundPred = ICI->getInversePredicate();
11664 FoundPred = ICI->getPredicate();
11666 const SCEV *FoundLHS = getSCEV(ICI->getOperand(0));
11667 const SCEV *FoundRHS = getSCEV(ICI->getOperand(1));
11678 if (getTypeSizeInBits(LHS->getType()) <
11679 getTypeSizeInBits(FoundLHS->getType())) {
11683 if (!CmpInst::isSigned(FoundPred) && !FoundLHS->getType()->isPointerTy() &&
11684 !FoundRHS->getType()->isPointerTy()) {
11685 auto *NarrowType = LHS->getType();
11686 auto *WideType = FoundLHS->getType();
11702 if (LHS->getType()->isPointerTy() || RHS->getType()->isPointerTy())
11705 LHS = getSignExtendExpr(LHS, FoundLHS->getType());
11706 RHS = getSignExtendExpr(RHS, FoundLHS->getType());
11708 LHS = getZeroExtendExpr(LHS, FoundLHS->getType());
11709 RHS = getZeroExtendExpr(RHS, FoundLHS->getType());
11711 } else if (getTypeSizeInBits(LHS->getType()) >
11712 getTypeSizeInBits(FoundLHS->getType())) {
11713 if (FoundLHS->getType()->isPointerTy() || FoundRHS->getType()->isPointerTy())
11716 FoundLHS = getSignExtendExpr(FoundLHS, LHS->getType());
11717 FoundRHS = getSignExtendExpr(FoundRHS, LHS->getType());
11719 FoundLHS = getZeroExtendExpr(FoundLHS, LHS->getType());
11720 FoundRHS = getZeroExtendExpr(FoundRHS, LHS->getType());
11731 assert(getTypeSizeInBits(LHS->getType()) ==
11732 getTypeSizeInBits(FoundLHS->getType()) &&
11762 // 0. LHS Pred RHS <- FoundLHS SwapPred FoundRHS
11764 // 1. LHS Pred RHS <- FoundRHS Pred FoundLHS
11765 // 2. RHS SwapPred LHS <- FoundLHS SwapPred FoundRHS
11766 // 3. LHS Pred RHS <- ~FoundLHS Pred ~FoundRHS
11767 // 4. ~LHS SwapPred ~RHS <- FoundLHS SwapPred FoundRHS
11779 if (!LHS->getType()->isPointerTy() && !RHS->getType()->isPointerTy() &&
11784 if (!FoundLHS->getType()->isPointerTy() &&
11785 !FoundRHS->getType()->isPointerTy() &&
11801 // operands are non-negative or negative.
11805 // Create local copies that we can freely swap and canonicalize our
11823 // x <u y && y >=s 0 --> x <s y.
11830 // x <s y && y <s 0 --> x <u y.
11860 if (Min == C->getAPInt()) {
11862 // This is true even if (Min + 1) wraps around -- in case of
11935 if (!AE || AE->getNumOperands() != 2)
11938 L = AE->getOperand(0);
11939 R = AE->getOperand(1);
11940 Flags = AE->getNoWrapFlags();
11949 // X - X = 0.
11951 return APInt(getTypeSizeInBits(More->getType()), 0);
11957 if (LAR->getLoop() != MAR->getLoop())
11962 if (!LAR->isAffine() || !MAR->isAffine())
11965 if (LAR->getStepRecurrence(*this) != MAR->getStepRecurrence(*this))
11968 Less = LAR->getStart();
11969 More = MAR->getStart();
11975 const auto &M = cast<SCEVConstant>(More)->getAPInt();
11976 const auto &L = cast<SCEVConstant>(Less)->getAPInt();
11977 return M - L;
11988 return -(C1->getAPInt());
11994 return C2->getAPInt();
11998 return C2->getAPInt() - C1->getAPInt();
12021 const BasicBlock *ContextBB = CtxI->getParent();
12024 const Loop *L = AR->getLoop();
12027 if (!L->contains(ContextBB) || !DT.dominates(ContextBB, L->getLoopLatch()))
12029 if (!isAvailableAtLoopEntry(FoundRHS, AR->getLoop()))
12031 return isImpliedCondOperands(Pred, LHS, RHS, AR->getStart(), FoundRHS);
12035 const Loop *L = AR->getLoop();
12038 if (!L->contains(ContextBB) || !DT.dominates(ContextBB, L->getLoopLatch()))
12040 if (!isAvailableAtLoopEntry(FoundLHS, AR->getLoop()))
12042 return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, AR->getStart());
12066 const Loop *L = AddRecFoundLHS->getLoop();
12067 if (L != AddRecLHS->getLoop())
12070 // FoundLHS u< FoundRHS u< -C => (FoundLHS + C) u< (FoundRHS + C) ... (1)
12072 // FoundLHS s< FoundRHS s< INT_MIN - C => (FoundLHS + C) s< (FoundRHS + C)
12081 // FoundLHS s< FoundRHS s< INT_MIN - C
12082 // <=> (FoundLHS + INT_MIN) u< (FoundRHS + INT_MIN) u< -C [ using (3) ]
12095 // Despite (2), "FoundRHS s< INT_MIN - C" does not mean that "FoundRHS + C"
12096 // will not sign underflow. For instance, say FoundLHS = (i8 -128), FoundRHS
12097 // = (i8 -127) and C = (i8 -100). Then INT_MIN - C = (i8 -28), and FoundRHS
12098 // s< (INT_MIN - C). Lack of sign overflow / underflow in "FoundRHS + C" is
12107 if (LDiff->isMinValue())
12113 FoundRHSLimit = -(*RDiff);
12116 FoundRHSLimit = APInt::getSignedMinValue(getTypeSizeInBits(RHS->getType())) - *RDiff;
12146 if (auto *Phi = dyn_cast<PHINode>(LU->getValue())) {
12152 if (auto *Phi = dyn_cast<PHINode>(RU->getValue())) {
12179 const BasicBlock *LBB = LPhi->getParent();
12188 if (RPhi && RPhi->getParent() == LBB) {
12194 const SCEV *L = getSCEV(LPhi->getIncomingValueForBlock(IncBB));
12195 const SCEV *R = getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12199 } else if (RAR && RAR->getLoop()->getHeader() == LBB) {
12205 if (LPhi->getNumIncomingValues() != 2) return false;
12207 auto *RLoop = RAR->getLoop();
12208 auto *Predecessor = RLoop->getLoopPredecessor();
12210 const SCEV *L1 = getSCEV(LPhi->getIncomingValueForBlock(Predecessor));
12211 if (!ProvedEasily(L1, RAR->getStart()))
12213 auto *Latch = RLoop->getLoopLatch();
12215 const SCEV *L2 = getSCEV(LPhi->getIncomingValueForBlock(Latch));
12216 if (!ProvedEasily(L2, RAR->getPostIncExpr(*this)))
12221 // At this point RHS is either a non-Phi, or it is a Phi from some block
12227 const SCEV *L = getSCEV(LPhi->getIncomingValueForBlock(IncBB));
12261 if (match(SUFoundRHS->getValue(),
12265 // LHS <u (shiftee >> shiftvalue) && shiftee <=u RHS ---> LHS <u RHS
12266 // LHS <=u (shiftee >> shiftvalue) && shiftee <=u RHS ---> LHS <=u RHS
12268 // ---> LHS <s RHS
12270 // ---> LHS <=s RHS
12311 return is_contained(MinMaxExpr->operands(), Candidate);
12330 if (LAR->getLoop() != RAR->getLoop())
12332 if (!LAR->isAffine() || !RAR->isAffine())
12335 if (LAR->getStepRecurrence(SE) != RAR->getStepRecurrence(SE))
12340 if (!LAR->getNoWrapFlags(NW) || !RAR->getNoWrapFlags(NW))
12343 return SE.isKnownPredicate(Pred, LAR->getStart(), RAR->getStart());
12385 assert(getTypeSizeInBits(LHS->getType()) ==
12386 getTypeSizeInBits(RHS->getType()) &&
12388 assert(getTypeSizeInBits(FoundLHS->getType()) ==
12389 getTypeSizeInBits(FoundRHS->getType()) &&
12405 // involved values are non-negative.
12408 // Knowing that both FoundLHS and FoundRHS are non-negative, and knowing
12410 // use this fact to prove that LHS and RHS are non-negative.
12411 const SCEV *MinusOne = getMinusOne(LHS->getType());
12424 return Ext->getOperand();
12444 // We want to avoid creation of any new non-constant SCEV. Since we are
12449 if (getTypeSizeInBits(LHS->getType()) != getTypeSizeInBits(RHS->getType()))
12453 if (!LHSAddExpr->hasNoSignedWrap())
12456 auto *LL = LHSAddExpr->getOperand(0);
12457 auto *LR = LHSAddExpr->getOperand(1);
12458 auto *MinusOne = getMinusOne(RHS->getType());
12475 if (match(LHSUnknownExpr->getValue(), m_SDiv(m_Value(LL), m_Value(LR)))) {
12492 if (!Numerator || Numerator->getType() != FoundLHS->getType())
12500 auto *DTy = Denominator->getType();
12501 auto *FRHSTy = FoundRHS->getType();
12502 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
12516 // (FoundRHS > Denominator - 2) && (RHS <= 0) => (LHS > RHS).
12525 // (FoundRHS > -1 - Denominator) && (RHS < 0) => (LHS > RHS).
12526 // For example, given that FoundLHS > -3. Then FoundLHS is at least -2.
12529 // 2. If FoundLHS is non-negative, then the result is non-negative.
12530 // Anyways, the result is non-negative.
12559 if (SExt && ZExt && SExt->getOperand() == ZExt->getOperand())
12570 if (SExt && ZExt && SExt->getOperand() == ZExt->getOperand())
12642 // The restriction on `FoundRHS` be lifted easily -- it exists only to
12650 const APInt &ConstFoundRHS = cast<SCEVConstant>(FoundRHS)->getAPInt();
12662 const APInt &ConstRHS = cast<SCEVConstant>(RHS)->getAPInt();
12672 unsigned BitWidth = getTypeSizeInBits(RHS->getType());
12673 const SCEV *One = getOne(Stride->getType());
12681 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
12689 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
12695 unsigned BitWidth = getTypeSizeInBits(RHS->getType());
12696 const SCEV *One = getOne(Stride->getType());
12703 // SMinRHS - SMaxStrideMinusOne < SMinValue => overflow!
12711 // UMinRHS - UMaxStrideMinusOne < UMinValue => overflow!
12716 // umin(N, 1) + floor((N - umin(N, 1)) / D)
12717 // This is equivalent to "1 + floor((N - 1) / D)" for N != 0. The umin
12719 const SCEV *MinNOne = getUMinExpr(N, getOne(N->getType()));
12730 // If we can't, the backedge-taken count must be zero.
12732 return getZero(Stride->getType());
12748 // We assume either the stride is positive, or the backedge-taken count
12756 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
12760 // in the other case (End - Start) is zero, leading to a zero maximum backedge
12765 // MaxBECount = ceil((max(MaxEnd, MinStart) - MinStart) / Stride)
12769 return getUDivCeilSCEV(getConstant(MaxEnd - MinStart) /* Delta */,
12796 // premise and can conclude the IV did not in fact self-wrap.
12800 auto *StrideC = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*this));
12801 if (!StrideC || !StrideC->getAPInt().isPowerOf2())
12812 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(ZExt->getOperand());
12813 if (AR && AR->getLoop() == L && AR->isAffine()) {
12815 // We can use the comparison to infer no-wrap flags only if it fully
12823 if (!isKnownNonZero(AR->getStepRecurrence(*this)))
12828 const unsigned InnerBitWidth = getTypeSizeInBits(AR->getType());
12829 const unsigned OuterBitWidth = getTypeSizeInBits(RHS->getType());
12836 APInt StrideMax = getUnsignedRangeMax(AR->getStepRecurrence(*this));
12837 APInt Limit = APInt::getMaxValue(InnerBitWidth) - (StrideMax - 1);
12841 auto Flags = AR->getNoWrapFlags();
12846 if (AR->hasNoUnsignedWrap()) {
12849 const SCEV *Step = AR->getStepRecurrence(*this);
12850 Type *Ty = ZExt->getType();
12853 getZeroExtendExpr(Step, Ty, 0), L, AR->getNoWrapFlags());
12870 if (!IV || IV->getLoop() != L || !IV->isAffine())
12884 bool NoWrap = ControlsOnlyExit && IV->getNoWrapFlags(WrapType);
12887 const SCEV *Stride = IV->getStepRecurrence(*this);
12895 // effects. Here's the loop structure we are trying to handle -
12903 // The backedge taken count for such loops is evaluated as -
12904 // (max(end, start + stride) - start - 1) /u stride
12907 // of the above formula is as follows -
12941 // pick an arbitrary non-zero value for the denominator (e.g. stride)
12950 // Note: The (Start - Stride) term is used to get the start' term from
12953 auto *StartIfZero = getMinusSCEV(IV->getStart(), Stride);
12957 Stride = getUMaxExpr(Stride, getOne(Stride->getType()));
12960 } else if (!Stride->isOne() && !NoWrap) {
12962 // From no-self-wrap, we need to then prove no-(un)signed-wrap. This
12963 // follows trivially from the fact that every (un)signed-wrapped, but
12964 // not self-wrapped value must be LT than the last value before
12971 // count will not generate any unsigned overflow. Relaxed no-overflow
12987 const SCEV *Start = IV->getStart();
12989 // Preserve pointer-typed Start/RHS to pass to isLoopEntryGuardedByCond.
12991 // Use integer-typed versions for actual computation; we can't subtract
12995 if (Start->getType()->isPointerTy()) {
13000 if (RHS->getType()->isPointerTy()) {
13010 if (PositiveStride && RHSAddRec != nullptr && RHSAddRec->getLoop() == L &&
13011 RHSAddRec->getNoWrapFlags()) {
13024 const SCEV *RHSStart = RHSAddRec->getStart();
13025 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*this);
13027 // If Stride - RHSStride is positive and does not overflow, we can write
13028 // backedge count as ->
13029 // ceil((End - Start) /u (Stride - RHSStride))
13032 // Check if RHSStride < 0 and Stride - RHSStride will not overflow.
13057 Start, Stride, RHS, getTypeSizeInBits(LHS->getType()), IsSigned);
13062 // We use the expression (max(End,Start)-Start)/Stride to describe the
13070 // Can we prove (max(RHS,Start) > Start - Stride?
13075 // "End-Start /uceiling Stride" where "End = max(RHS,Start)"
13077 // "((End - 1) - (Start - Stride)) /u Stride"
13079 // our precondition that max(RHS,Start) > Start - Stride.
13080 // * For RHS <= Start, the backedge-taken count must be zero.
13081 // "((End - 1) - (Start - Stride)) /u Stride" reduces to
13082 // "((Start - 1) - (Start - Stride)) /u Stride" which simplies to
13083 // "Stride - 1 /u Stride" which is indeed zero for all non-zero values
13086 // * For RHS >= Start, the backedge count must be "RHS-Start /uceil
13088 // "((End - 1) - (Start - Stride)) /u Stride" reduces to
13089 // "((RHS - 1) - (Start - Stride)) /u Stride" reassociates to
13090 // "((RHS - (Start - Stride) - 1) /u Stride".
13092 const SCEV *MinusOne = getMinusOne(Stride->getType());
13108 // (RHS > Start - 1) implies RHS >= Start.
13109 // * "RHS >= Start" is trivially equivalent to "RHS > Start - 1" if
13110 // "Start - 1" doesn't overflow.
13111 // * For signed comparison, if Start - 1 does overflow, it's equal
13113 // * For unsigned comparison, if Start - 1 does overflow, it's equal
13119 getAddExpr(OrigStart, getMinusOne(OrigStart->getType()));
13129 // general, we can write the backedge-taken count as:
13131 // RHS >= Start ? ceil(RHS - Start) / Stride : 0
13135 // ceil(max(RHS, Start) - Start) / Stride
13154 // "(Start - End) + (Stride - 1)" has unsigned overflow.
13155 const SCEV *One = getOne(Stride->getType());
13158 if (StrideC->getAPInt().isPowerOf2()) {
13171 // End - Start <= Stride * N <= UMAX - Start
13173 // Since Start is unsigned, UMAX - Start <= UMAX. Therefore:
13175 // End - Start <= Stride * N <= UMAX
13179 // End - Start <= Stride * N <= UMAX - (UMAX mod Stride)
13182 // Stride. Therefore, UMAX mod Stride == Stride - 1. So we can
13185 // End - Start <= Stride * N <= UMAX - Stride - 1
13189 // End - Start <= UMAX - Stride - 1
13191 // Adding Stride - 1 to both sides:
13193 // (End - Start) + (Stride - 1) <= UMAX
13198 // Just rewrite steps before "End - Start <= Stride * N <= UMAX"
13205 // If Start is equal to Stride, (End - Start) + (Stride - 1) == End
13206 // - 1. If !IsSigned, 0 <u Stride == Start <=u End; so 0 <u End - 1
13207 // <u End. If IsSigned, 0 <s Stride == Start <=s End; so 0 <s End -
13210 // If Start is equal to Stride - 1, (End - Start) + Stride - 1 ==
13219 // floor((D + (S - 1)) / S)
13243 Start, Stride, RHS, getTypeSizeInBits(LHS->getType()), IsSigned);
13272 if (!IV || IV->getLoop() != L || !IV->isAffine())
13276 bool NoWrap = ControlsOnlyExit && IV->getNoWrapFlags(WrapType);
13279 const SCEV *Stride = getNegativeSCEV(IV->getStepRecurrence(*this));
13286 // will not generate any unsigned overflow. Relaxed no-overflow conditions
13289 if (!Stride->isOne() && !NoWrap)
13293 const SCEV *Start = IV->getStart();
13305 if (Start->getType()->isPointerTy()) {
13310 if (End->getType()->isPointerTy()) {
13316 // Compute ((Start - End) + (Stride - 1)) / Stride.
13319 const SCEV *One = getOne(Stride->getType());
13329 unsigned BitWidth = getTypeSizeInBits(LHS->getType());
13330 APInt Limit = IsSigned ? APInt::getSignedMinValue(BitWidth) + (MinStride - 1)
13331 : APInt::getMinValue(BitWidth) + (MinStride - 1);
13334 // the case End = RHS. This is safe because in the other case (Start - End)
13343 : getUDivCeilSCEV(getConstant(MaxStart - MinEnd),
13360 // If the start is a non-zero constant, shift the range to simplify things.
13362 if (!SC->getValue()->isZero()) {
13364 Operands[0] = SE.getZero(SC->getType());
13368 return ShiftedAddRec->getNumIterationsInRange(
13369 Range.subtract(SC->getAPInt()), SE);
13396 APInt A = cast<SCEVConstant>(getOperand(1))->getAPInt();
13397 APInt End = A.sge(1) ? (Range.getUpper() - 1) : Range.getLower();
13407 if (Range.contains(Val->getValue()))
13413 ConstantInt::get(SE.getContext(), ExitVal - 1), SE)->getValue()) &&
13438 for (unsigned i = 0, e = getNumOperands() - 1; i < e; ++i)
13444 const SCEV *Last = getOperand(getNumOperands() - 1);
13445 assert(!Last->isZero() && "Recurrency with zero step?");
13455 return isa<UndefValue>(SU->getValue());
13464 return SU->getValue() == nullptr;
13473 Ty = Store->getValueOperand()->getType();
13475 Ty = Load->getType();
13483 //===----------------------------------------------------------------------===//
13485 //===----------------------------------------------------------------------===//
13490 SE->ConstantEvolutionLoopExitValue.erase(PN);
13491 SE->eraseValueFromMap(getValPtr());
13501 SE->forgetValue(getValPtr());
13508 //===----------------------------------------------------------------------===//
13510 //===----------------------------------------------------------------------===//
13528 auto *GuardDecl = F.getParent()->getFunction(
13530 HasGuards = GuardDecl && !GuardDecl->use_empty();
13569 U = U->Next;
13570 Tmp->~SCEVUnknown();
13591 /// When printing a top-level SCEV for trip counts, it's helpful to include
13595 OS << *S->getType() << " ";
13606 L->getHeader()->printAsOperand(OS, /*PrintType=*/false);
13610 L->getExitingBlocks(ExitingBlocks);
13614 auto *BTC = SE->getBackedgeTakenCount(L);
13616 OS << "backedge-taken count is ";
13619 OS << "Unpredictable backedge-taken count.";
13624 OS << " exit count for " << ExitingBlock->getName() << ": ";
13625 PrintSCEVWithTypeHint(OS, SE->getExitCount(L, ExitingBlock));
13630 L->getHeader()->printAsOperand(OS, /*PrintType=*/false);
13633 auto *ConstantBTC = SE->getConstantMaxBackedgeTakenCount(L);
13635 OS << "constant max backedge-taken count is ";
13637 if (SE->isBackedgeTakenCountMaxOrZero(L))
13640 OS << "Unpredictable constant max backedge-taken count. ";
13645 L->getHeader()->printAsOperand(OS, /*PrintType=*/false);
13648 auto *SymbolicBTC = SE->getSymbolicMaxBackedgeTakenCount(L);
13650 OS << "symbolic max backedge-taken count is ";
13652 if (SE->isBackedgeTakenCountMaxOrZero(L))
13655 OS << "Unpredictable symbolic max backedge-taken count. ";
13661 OS << " symbolic max exit count for " << ExitingBlock->getName() << ": ";
13662 auto *ExitBTC = SE->getExitCount(L, ExitingBlock,
13669 auto *PBT = SE->getPredicatedBackedgeTakenCount(L, Preds);
13672 L->getHeader()->printAsOperand(OS, /*PrintType=*/false);
13675 OS << "Predicated backedge-taken count is ";
13678 OS << "Unpredictable predicated backedge-taken count.";
13682 P->print(OS, 4);
13687 SE->getPredicatedSymbolicMaxBackedgeTakenCount(L, Preds);
13690 L->getHeader()->printAsOperand(OS, /*PrintType=*/false);
13693 OS << "Predicated symbolic max backedge-taken count is ";
13696 OS << "Unpredictable predicated symbolic max backedge-taken count.";
13700 P->print(OS, 4);
13703 if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
13705 L->getHeader()->printAsOperand(OS, /*PrintType=*/false);
13707 OS << "Trip multiple is " << SE->getSmallConstantTripMultiple(L) << "\n";
13727 raw_ostream &operator<<(raw_ostream &OS, ScalarEvolution::BlockDisposition BD) {
13728 switch (BD) {
13759 OS << " --> ";
13761 SV->print(OS);
13773 OS << " --> ";
13774 AtUse->print(OS);
13785 const SCEV *ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop());
13793 for (const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
13801 Iter->getHeader()->printAsOperand(OS, /*PrintType=*/false);
13815 InnerL->getHeader()->printAsOperand(OS, /*PrintType=*/false);
13854 switch (S->getSCEVType()) {
13862 if (AR->getLoop() == L)
13865 // Add recurrences are never invariant in the function-body (null loop).
13870 if (DT.dominates(L->getHeader(), AR->getLoop()->getHeader()))
13872 assert(!L->contains(AR->getLoop()) && "Containing loop's header does not"
13876 if (AR->getLoop()->contains(L))
13881 for (const auto *Op : AR->operands())
13885 // Otherwise it's loop-invariant.
13901 for (const auto *Op : S->operands()) {
13911 // All non-instruction values are loop invariant. All instructions are loop
13915 if (auto *I = dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue()))
13916 return (L && !L->contains(I)) ? LoopInvariant : LoopVariant;
13953 switch (S->getSCEVType()) {
13963 if (!DT.dominates(AR->getLoop()->getHeader(), BB))
13982 for (const SCEV *NAryOp : S->operands()) {
13993 dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue())) {
13994 if (I->getParent() == BB)
13996 if (DT.properlyDominates(I->getParent(), BB))
14025 for (const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14030 UserIt->second.erase({L, Predicated});
14046 for (const auto *User : Users->second)
14056 std::pair<const SCEV *, const Loop *> Entry = I->first;
14079 for (Value *V : ExprIt->second) {
14089 for (const auto &Pair : ScopeIt->second)
14098 for (const auto &Pair : ScopeUserIt->second)
14106 auto Copy = BEUsersIt->second;
14114 for (auto &KV : FoldUser->second)
14128 LoopsUsed.insert(AR->getLoop());
14150 if (match(BB->getTerminator(), m_Br(m_Value(Cond), m_BasicBlock(TrueBB),
14153 Worklist.push_back(C->isOne() ? TrueBB : FalseBB);
14158 const SCEV *L = getSCEV(Cmp->getOperand(0));
14159 const SCEV *R = getSCEV(Cmp->getOperand(1));
14160 if (isKnownPredicateViaConstantRanges(Cmp->getPredicate(), L, R)) {
14164 if (isKnownPredicateViaConstantRanges(Cmp->getInversePredicate(), L,
14187 return SE.getConstant(Constant->getAPInt());
14191 return SE.getUnknown(Expr->getValue());
14203 auto GetDelta = [&](const SCEV *Old, const SCEV *New) -> const SCEV * {
14227 if (!ReachableBlocks.contains(L->getHeader()))
14237 SCM.visit(It->second.getExact(L, const_cast<ScalarEvolution *>(this)));
14242 // NB! This situation is legal, but is very suspicious -- whatever pass
14244 // computable or vice-versa *should have* invalidated SCEV. However, we
14250 if (SE.getTypeSizeInBits(CurBECount->getType()) >
14251 SE.getTypeSizeInBits(NewBECount->getType()))
14252 NewBECount = SE2.getZeroExtendExpr(NewBECount, CurBECount->getType());
14253 else if (SE.getTypeSizeInBits(CurBECount->getType()) <
14254 SE.getTypeSizeInBits(NewBECount->getType()))
14255 CurBECount = SE2.getZeroExtendExpr(CurBECount, NewBECount->getType());
14258 if (Delta && !Delta->isZero()) {
14273 Worklist.append(L->begin(), L->end());
14279 assert(ValidLoops.contains(AR->getLoop()) &&
14286 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14293 if (!ReachableBlocks.contains(I->getParent()))
14298 if (Delta && !Delta->isZero()) {
14316 if (It->second != KV.first) {
14317 dbgs() << "Value " << *V << " mapped to " << *It->second
14331 if (It != SCEVUsers.end() && It->second.count(&S))
14348 is_contained(It->second, std::make_pair(L, Value)))
14365 is_contained(It->second, std::make_pair(L, ValueAtScope)))
14383 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14415 << BB->getName() << " is incorrect: cached " << CachedDisposition
14430 if (!is_contained(I->second, FoldID)) {
14443 if (I->second != Expr) {
14445 << *I->second << " != " << *Expr << "!\n";
14500 // For compatibility with opt's -analyze feature under legacy pass manager
14509 INITIALIZE_PASS_BEGIN(ScalarEvolutionWrapperPass, "scalar-evolution",
14515 INITIALIZE_PASS_END(ScalarEvolutionWrapperPass, "scalar-evolution",
14536 SE->print(OS);
14543 SE->verify();
14563 assert(LHS->getType() == RHS->getType() &&
14604 /// If \p Pred is non-null, the SCEV expression is rewritten to respect the
14607 /// If \p NewPreds is non-null, rewrite is free to add further predicates to
14619 for (const auto *Pred : U->getPredicates())
14621 if (IPred->getLHS() == Expr &&
14622 IPred->getPredicate() == ICmpInst::ICMP_EQ)
14623 return IPred->getRHS();
14625 if (IPred->getLHS() == Expr &&
14626 IPred->getPredicate() == ICmpInst::ICMP_EQ)
14627 return IPred->getRHS();
14634 const SCEV *Operand = visit(Expr->getOperand());
14636 if (AR && AR->getLoop() == L && AR->isAffine()) {
14639 const SCEV *Step = AR->getStepRecurrence(SE);
14640 Type *Ty = Expr->getType();
14642 return SE.getAddRecExpr(SE.getZeroExtendExpr(AR->getStart(), Ty),
14644 AR->getNoWrapFlags());
14646 return SE.getZeroExtendExpr(Operand, Expr->getType());
14650 const SCEV *Operand = visit(Expr->getOperand());
14652 if (AR && AR->getLoop() == L && AR->isAffine()) {
14655 const SCEV *Step = AR->getStepRecurrence(SE);
14656 Type *Ty = Expr->getType();
14658 return SE.getAddRecExpr(SE.getSignExtendExpr(AR->getStart(), Ty),
14660 AR->getNoWrapFlags());
14662 return SE.getSignExtendExpr(Operand, Expr->getType());
14674 return Pred && Pred->implies(P);
14676 NewPreds->insert(P);
14693 if (!isa<PHINode>(Expr->getValue()))
14700 for (const auto *P : PredicatedRewrite->second){
14703 if (L != WP->getExpr()->getLoop())
14709 return PredicatedRewrite->first;
14752 assert(LHS->getType() == RHS->getType() && "LHS and RHS types don't match");
14765 return Op->LHS == LHS && Op->RHS == RHS;
14789 return Op && Op->AR == AR && setFlags(Flags, Op->Flags) == Flags;
14793 SCEV::NoWrapFlags ScevFlags = AR->getNoWrapFlags();
14815 SCEV::NoWrapFlags StaticFlags = AR->getNoWrapFlags();
14824 if (const auto *Step = dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE)))
14825 if (Step->getValue()->getValue().isNonNegative())
14841 [](const SCEVPredicate *I) { return I->isAlwaysTrue(); });
14846 return all_of(Set->Preds,
14847 [this](const SCEVPredicate *I) { return this->implies(I); });
14850 [N](const SCEVPredicate *I) { return I->implies(N); });
14855 Pred->print(OS, Depth);
14860 for (const auto *Pred : Set->Preds)
14928 if (Preds->implies(&Pred))
14931 auto &OldPreds = Preds->getPredicates();
14965 II.first->second = SCEVWrapPredicate::setFlags(Flags, II.first->second);
14979 Flags = SCEVWrapPredicate::clearFlags(Flags, II->second);
14985 const SCEV *Expr = this->getSCEV(V);
15002 Preds(std::make_unique<SCEVUnionPredicate>(Init.Preds->getPredicates())),
15022 if (II->second.second == Expr)
15027 OS.indent(Depth + 2) << "--> " << *II->second.second << "\n";
15031 // Match the mathematical pattern A - (A / B) * B, where A and B can be
15033 // for URem with constant power-of-2 second operands.
15038 if (Expr->getType()->isPointerTy())
15042 // for URem with constant power-of-2 second operands. Make sure the size of
15045 if (const auto *Trunc = dyn_cast<SCEVTruncateExpr>(ZExt->getOperand(0))) {
15046 LHS = Trunc->getOperand();
15049 if (getTypeSizeInBits(LHS->getType()) >
15050 getTypeSizeInBits(Expr->getType()))
15052 if (LHS->getType() != Expr->getType())
15053 LHS = getZeroExtendExpr(LHS, Expr->getType());
15054 RHS = getConstant(APInt(getTypeSizeInBits(Expr->getType()), 1)
15055 << getTypeSizeInBits(Trunc->getType()));
15059 if (Add == nullptr || Add->getNumOperands() != 2)
15062 const SCEV *A = Add->getOperand(1);
15063 const auto *Mul = dyn_cast<SCEVMulExpr>(Add->getOperand(0));
15069 // (SomeExpr + (-(SomeExpr / B) * B)).
15078 // (SomeExpr + (-1 * (SomeExpr / B) * B)).
15079 if (Mul->getNumOperands() == 3 && isa<SCEVConstant>(Mul->getOperand(0)))
15080 return MatchURemWithDivisor(Mul->getOperand(1)) ||
15081 MatchURemWithDivisor(Mul->getOperand(2));
15083 // (SomeExpr + ((-SomeExpr / B) * B)) or (SomeExpr + ((SomeExpr / B) * -B)).
15084 if (Mul->getNumOperands() == 2)
15085 return MatchURemWithDivisor(Mul->getOperand(1)) ||
15086 MatchURemWithDivisor(Mul->getOperand(0)) ||
15087 MatchURemWithDivisor(getNegativeSCEV(Mul->getOperand(1))) ||
15088 MatchURemWithDivisor(getNegativeSCEV(Mul->getOperand(0)));
15111 // Check for a condition of the form (-C1 + X < C2). InstCombine will
15117 if (!AddExpr || AddExpr->getNumOperands() != 2)
15120 auto *C1 = dyn_cast<SCEVConstant>(AddExpr->getOperand(0));
15121 auto *LHSUnknown = dyn_cast<SCEVUnknown>(AddExpr->getOperand(1));
15127 ConstantRange::makeExactICmpRegion(Predicate, C2->getAPInt())
15128 .sub(C1->getAPInt());
15130 // Bail out, unless we have a non-wrapping, monotonic range.
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
15147 // the non-constant operand and in \p LHS the constant operand.
15152 if (MinMax->getNumOperands() != 2)
15154 if (auto *C = dyn_cast<SCEVConstant>(MinMax->getOperand(0))) {
15155 if (C->getAPInt().isNegative())
15157 SCTy = MinMax->getSCEVType();
15158 LHS = MinMax->getOperand(0);
15159 RHS = MinMax->getOperand(1);
15166 // Checks whether Expr is a non-negative constant, and Divisor is a positive
15174 ExprVal = ConstExpr->getAPInt();
15175 DivisorVal = ConstDivisor->getAPInt();
15190 // return the SCEV: Expr + Divisor - Expr % Divisor
15191 return SE.getConstant(ExprVal + DivisorVal - Rem);
15205 // return the SCEV: Expr - Expr % Divisor
15206 return SE.getConstant(ExprVal - Rem);
15223 "Expected non-negative operand!");
15236 RHSC->getValue()->isNullValue()) {
15245 I != RewriteMap.end() ? I->second : LHSUnknown;
15266 // Puts rewrite rule \p From -> \p To into the rewrite map. Also if \p From
15282 return I != RewriteMap.end() ? I->second : S;
15295 if (Mul->getNumOperands() != 2)
15297 auto *MulLHS = Mul->getOperand(0);
15298 auto *MulRHS = Mul->getOperand(1);
15302 if (Div->getOperand(1) == MulRHS) {
15308 return HasDivisibiltyInfo(MinMax->getOperand(0), DividesBy) ||
15309 HasDivisibiltyInfo(MinMax->getOperand(1), DividesBy);
15316 if (SE.getURemExpr(Expr, DividesBy)->isZero())
15319 return IsKnownToDivideBy(MinMax->getOperand(0), DividesBy) &&
15320 IsKnownToDivideBy(MinMax->getOperand(1), DividesBy);
15334 // 'min(a, b) >= c' -> '(a >= c) and (b >= c)',
15335 // 'min(a, b) > c' -> '(a > c) and (b > c)',
15336 // 'max(a, b) <= c' -> '(a <= c) and (b <= c)',
15337 // 'max(a, b) < c' -> '(a < c) and (b < c)'.
15340 // with non-strict ones against plus or minus one of RHS depending on the
15342 const SCEV *One = SE.getOne(RHS->getType());
15345 if (RHS->getType()->isPointerTy())
15375 append_range(Worklist, S->operands());
15418 cast<SCEVConstant>(RHS)->getValue()->isNullValue()) {
15433 BasicBlock *Header = L->getHeader();
15442 Terms.emplace_back(AssumeI->getOperand(0), true);
15446 auto *GuardDecl = SE.F.getParent()->getFunction(
15449 for (const auto *GU : GuardDecl->users())
15451 if (Guard->getFunction() == Header->getParent() &&
15453 Terms.emplace_back(Guard->getArgOperand(0), true);
15461 L->getLoopPredecessor(), Header);
15466 dyn_cast<BranchInst>(Pair.first->getTerminator());
15467 if (!LoopEntryPredicate || LoopEntryPredicate->isUnconditional())
15470 Terms.emplace_back(LoopEntryPredicate->getCondition(),
15471 LoopEntryPredicate->getSuccessor(0) == Pair.second);
15489 EnterIfTrue ? Cmp->getPredicate() : Cmp->getInversePredicate();
15490 const auto *LHS = SE.getSCEV(Cmp->getOperand(0));
15491 const auto *RHS = SE.getSCEV(Cmp->getOperand(1));
15520 // sub-expressions.
15557 return I->second;
15565 Type *Ty = Expr->getType();
15566 const SCEV *Op = Expr->getOperand(0);
15567 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
15569 Bitwidth > Op->getType()->getScalarSizeInBits()) {
15574 return SE.getZeroExtendExpr(I->second, Ty);
15581 return I->second;
15589 return I->second;
15596 return I->second;
15603 return I->second;
15609 for (const auto *Op : Expr->operands()) {
15619 Expr->getNoWrapFlags(), FlagMask));
15625 for (const auto *Op : Expr->operands()) {
15635 Expr->getNoWrapFlags(), FlagMask));