Lines Matching +full:depth +full:- +full:wise
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 //===----------------------------------------------------------------------===//
85 #include "llvm/Config/llvm-config.h"
139 #define DEBUG_TYPE "scalar-evolution"
155 MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,
162 "verify-scev", cl::Hidden, cl::location(VerifySCEV),
165 "verify-scev-strict", cl::Hidden,
166 cl::desc("Enable stricter verification with -verify-scev is passed"));
169 "scev-verify-ir", cl::Hidden,
174 "scev-mulops-inline-threshold", cl::Hidden,
179 "scev-addops-inline-threshold", cl::Hidden,
184 "scalar-evolution-max-scev-compare-depth", cl::Hidden,
185 cl::desc("Maximum depth of recursive SCEV complexity comparisons"),
189 "scalar-evolution-max-scev-operations-implication-depth", cl::Hidden,
190 cl::desc("Maximum depth of recursive SCEV operations implication analysis"),
194 "scalar-evolution-max-value-compare-depth", cl::Hidden,
195 cl::desc("Maximum depth of recursive value complexity comparisons"),
199 MaxArithDepth("scalar-evolution-max-arith-depth", cl::Hidden,
200 cl::desc("Maximum depth of recursive arithmetics"),
204 "scalar-evolution-max-constant-evolving-depth", cl::Hidden,
205 cl::desc("Maximum depth of recursive constant evolving"), cl::init(32));
208 MaxCastDepth("scalar-evolution-max-cast-depth", cl::Hidden,
209 cl::desc("Maximum depth of recursive SExt/ZExt/Trunc"),
213 MaxAddRecSize("scalar-evolution-max-add-rec-size", cl::Hidden,
218 HugeExprThreshold("scalar-evolution-huge-expr-threshold", cl::Hidden,
223 "scev-range-iter-threshold", cl::Hidden,
228 "scalar-evolution-max-loop-guard-collection-depth", cl::Hidden,
229 cl::desc("Maximum depth for recursive loop guard collection"), cl::init(1));
232 ClassifyExpressions("scalar-evolution-classify-expressions",
237 "scalar-evolution-use-expensive-range-sharpening", cl::Hidden,
243 "scalar-evolution-max-scc-analysis-depth", cl::Hidden,
249 EnableFiniteLoopControl("scalar-evolution-finite-loop", cl::Hidden,
254 "scalar-evolution-use-context-for-no-wrap-flag-strenghening", cl::Hidden,
258 //===----------------------------------------------------------------------===//
260 //===----------------------------------------------------------------------===//
262 //===----------------------------------------------------------------------===//
276 cast<SCEVConstant>(this)->getValue()->printAsOperand(OS, false);
283 const SCEV *Op = PtrToInt->getOperand();
284 OS << "(ptrtoint " << *Op->getType() << " " << *Op << " to "
285 << *PtrToInt->getType() << ")";
290 const SCEV *Op = Trunc->getOperand();
291 OS << "(trunc " << *Op->getType() << " " << *Op << " to "
292 << *Trunc->getType() << ")";
297 const SCEV *Op = ZExt->getOperand();
298 OS << "(zext " << *Op->getType() << " " << *Op << " to "
299 << *ZExt->getType() << ")";
304 const SCEV *Op = SExt->getOperand();
305 OS << "(sext " << *Op->getType() << " " << *Op << " to "
306 << *SExt->getType() << ")";
311 OS << "{" << *AR->getOperand(0);
312 for (unsigned i = 1, e = AR->getNumOperands(); i != e; ++i)
313 OS << ",+," << *AR->getOperand(i);
315 if (AR->hasNoUnsignedWrap())
317 if (AR->hasNoSignedWrap())
319 if (AR->hasNoSelfWrap() &&
320 !AR->getNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)))
322 AR->getLoop()->getHeader()->printAsOperand(OS, /*PrintType=*/false);
335 switch (NAry->getSCEVType()) {
354 for (const SCEV *Op : NAry->operands())
357 switch (NAry->getSCEVType()) {
360 if (NAry->hasNoUnsignedWrap())
362 if (NAry->hasNoSignedWrap())
373 OS << "(" << *UDiv->getLHS() << " /u " << *UDiv->getRHS() << ")";
377 cast<SCEVUnknown>(this)->getValue()->printAsOperand(OS, false);
389 return cast<SCEVConstant>(this)->getType();
391 return cast<SCEVVScale>(this)->getType();
396 return cast<SCEVCastExpr>(this)->getType();
398 return cast<SCEVAddRecExpr>(this)->getType();
400 return cast<SCEVMulExpr>(this)->getType();
405 return cast<SCEVMinMaxExpr>(this)->getType();
407 return cast<SCEVSequentialMinMaxExpr>(this)->getType();
409 return cast<SCEVAddExpr>(this)->getType();
411 return cast<SCEVUDivExpr>(this)->getType();
413 return cast<SCEVUnknown>(this)->getType();
430 return cast<SCEVCastExpr>(this)->operands();
439 return cast<SCEVNAryExpr>(this)->operands();
441 return cast<SCEVUDivExpr>(this)->operands();
459 const SCEVConstant *SC = dyn_cast<SCEVConstant>(Mul->getOperand(0));
462 // Return true if the value is negative, this matches things like (-42 * V).
463 return SC->getAPInt().isNegative();
470 return S->getSCEVType() == scCouldNotCompute;
520 assert(getOperand()->getType()->isPointerTy() && Ty->isIntegerTy() &&
521 "Must be a non-bit-width-changing pointer-to-integer cast!");
532 assert(getOperand()->getType()->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
533 "Cannot truncate non-integer value!");
539 assert(getOperand()->getType()->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
540 "Cannot zero extend non-integer value!");
546 assert(getOperand()->getType()->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
547 "Cannot sign extend non-integer value!");
552 SE->forgetMemoizedResults(this);
555 SE->UniqueSCEVs.RemoveNode(this);
563 SE->forgetMemoizedResults(this);
566 SE->UniqueSCEVs.RemoveNode(this);
572 //===----------------------------------------------------------------------===//
574 //===----------------------------------------------------------------------===//
577 /// "complexity" is a partial (and somewhat ad-hoc) relation used to order
580 Value *RV, unsigned Depth) {
581 if (Depth > MaxValueCompareDepth)
586 bool LIsPointer = LV->getType()->isPointerTy(),
587 RIsPointer = RV->getType()->isPointerTy();
589 return (int)LIsPointer - (int)RIsPointer;
592 unsigned LID = LV->getValueID(), RID = RV->getValueID();
594 return (int)LID - (int)RID;
599 unsigned LArgNo = LA->getArgNo(), RArgNo = RA->getArgNo();
600 return (int)LArgNo - (int)RArgNo;
607 auto LT = GV->getLinkage();
615 return LGV->getName().compare(RGV->getName());
618 // For instructions, compare their loop depth, and their operand count. This
624 const BasicBlock *LParent = LInst->getParent(),
625 *RParent = RInst->getParent();
627 unsigned LDepth = LI->getLoopDepth(LParent),
628 RDepth = LI->getLoopDepth(RParent);
630 return (int)LDepth - (int)RDepth;
634 unsigned LNumOps = LInst->getNumOperands(),
635 RNumOps = RInst->getNumOperands();
637 return (int)LNumOps - (int)RNumOps;
640 int Result = CompareValueComplexity(LI, LInst->getOperand(Idx),
641 RInst->getOperand(Idx), Depth + 1);
651 // than RHS, respectively. A three-way result allows recursive comparisons to be
653 // If the max analysis depth was reached, return std::nullopt, assuming we do
658 const SCEV *RHS, DominatorTree &DT, unsigned Depth = 0) {
659 // Fast-path: SCEVs are uniqued so we can do a quick equality check.
664 SCEVTypes LType = LHS->getSCEVType(), RType = RHS->getSCEVType();
666 return (int)LType - (int)RType;
671 if (Depth > MaxSCEVCompareDepth)
683 CompareValueComplexity(LI, LU->getValue(), RU->getValue(), Depth + 1);
694 const APInt &LA = LC->getAPInt();
695 const APInt &RA = RC->getAPInt();
698 return (int)LBitWidth - (int)RBitWidth;
699 return LA.ult(RA) ? -1 : 1;
703 const auto *LTy = cast<IntegerType>(cast<SCEVVScale>(LHS)->getType());
704 const auto *RTy = cast<IntegerType>(cast<SCEVVScale>(RHS)->getType());
705 return LTy->getBitWidth() - RTy->getBitWidth();
715 const Loop *LLoop = LA->getLoop(), *RLoop = RA->getLoop();
717 const BasicBlock *LHead = LLoop->getHeader(), *RHead = RLoop->getHeader();
723 return -1;
741 ArrayRef<const SCEV *> LOps = LHS->operands();
742 ArrayRef<const SCEV *> ROps = RHS->operands();
744 // Lexicographically compare n-ary-like expressions.
747 return (int)LNumOps - (int)RNumOps;
751 Depth + 1);
803 for (unsigned i = 0, e = Ops.size(); i != e-2; ++i) {
805 unsigned Complexity = S->getSCEVType();
809 for (unsigned j = i+1; j != e && Ops[j]->getSCEVType() == Complexity; ++j) {
814 if (i == e-2) return; // Done!
824 return S->getExpressionSize() >= HugeExprThreshold;
849 SE.getConstant(Fold(Folded->getAPInt(), C->getAPInt())));
861 if (Folded && IsAbsorber(Folded->getAPInt()))
865 if (Folded && !IsIdentity(Folded->getAPInt()))
871 //===----------------------------------------------------------------------===//
873 //===----------------------------------------------------------------------===//
885 // BC(It, K) = (It * (It - 1) * ... * (It - K + 1)) / K!
897 // BC(It, K) = (It * (It - 1) * ... * (It - K + 1)) / 2^T / (K! / 2^T)
928 // It/2*(It+(It*INT_MIN/INT_MIN)+-1). However, it requires
967 const SCEV *S = SE.getMinusSCEV(It, SE.getConstant(It->getType(), i));
1003 const SCEV *Coeff = BinomialCoefficient(It, i, SE, Result->getType());
1012 //===----------------------------------------------------------------------===//
1014 //===----------------------------------------------------------------------===//
1017 unsigned Depth) {
1018 assert(Depth <= 1 &&
1019 "getLosslessPtrToIntExpr() should self-recurse at most once.");
1021 // We could be called with an integer-typed operands during SCEV rewrites.
1023 if (!Op->getType()->isPointerTy())
1038 // for non-integral pointers.
1039 if (getDataLayout().isNonIntegralPointerType(Op->getType()))
1042 Type *IntPtrTy = getDataLayout().getIntPtrType(Op->getType());
1048 if (getDataLayout().getTypeSizeInBits(getEffectiveSCEVType(Op->getType())) !=
1056 // left as-is), but produce a zero constant.
1058 if (isa<ConstantPointerNull>(U->getValue()))
1071 assert(Depth == 0 && "getLosslessPtrToIntExpr() should not self-recurse for "
1072 "non-SCEVUnknown's.");
1077 // only, and the expressions must otherwise be integer-typed.
1081 /// which computes a pointer-typed value, and rewrites the whole expression
1083 /// pointer-typed operands in the expression are SCEVUnknown.
1097 Type *STy = S->getType();
1098 // If the expression is not pointer-typed, just keep it as-is.
1099 if (!STy->isPointerTy())
1108 for (const auto *Op : Expr->operands()) {
1112 return !Changed ? Expr : SE.getAddExpr(Operands, Expr->getNoWrapFlags());
1118 for (const auto *Op : Expr->operands()) {
1122 return !Changed ? Expr : SE.getMulExpr(Operands, Expr->getNoWrapFlags());
1126 assert(Expr->getType()->isPointerTy() &&
1127 "Should only reach pointer-typed SCEVUnknown's.");
1128 return SE.getLosslessPtrToIntExpr(Expr, /*Depth=*/1);
1134 assert(IntOp->getType()->isIntegerTy() &&
1136 "and ending up with an integer-typed expression!");
1141 assert(Ty->isIntegerTy() && "Target type must be an integer type!");
1151 unsigned Depth) {
1152 assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) &&
1156 assert(!Op->getType()->isPointerTy() && "Can't truncate pointer!");
1169 cast<ConstantInt>(ConstantExpr::getTrunc(SC->getValue(), Ty)));
1171 // trunc(trunc(x)) --> trunc(x)
1173 return getTruncateExpr(ST->getOperand(), Ty, Depth + 1);
1175 // trunc(sext(x)) --> sext(x) if widening or trunc(x) if narrowing
1177 return getTruncateOrSignExtend(SS->getOperand(), Ty, Depth + 1);
1179 // trunc(zext(x)) --> zext(x) if widening or trunc(x) if narrowing
1181 return getTruncateOrZeroExtend(SZ->getOperand(), Ty, Depth + 1);
1183 if (Depth > MaxCastDepth) {
1191 // trunc(x1 + ... + xN) --> trunc(x1) + ... + trunc(xN) and
1192 // trunc(x1 * ... * xN) --> trunc(x1) * ... * trunc(xN),
1199 for (unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1201 const SCEV *S = getTruncateExpr(CommOp->getOperand(i), Ty, Depth + 1);
1202 if (!isa<SCEVIntegralCastExpr>(CommOp->getOperand(i)) &&
1224 for (const SCEV *Op : AddRec->operands())
1225 Operands.push_back(getTruncateExpr(Op, Ty, Depth + 1));
1226 return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap);
1250 unsigned BitWidth = SE->getTypeSizeInBits(Step->getType());
1251 if (SE->isKnownPositive(Step)) {
1253 return SE->getConstant(APInt::getSignedMinValue(BitWidth) -
1254 SE->getSignedRangeMax(Step));
1256 if (SE->isKnownNegative(Step)) {
1258 return SE->getConstant(APInt::getSignedMaxValue(BitWidth) -
1259 SE->getSignedRangeMin(Step));
1270 unsigned BitWidth = SE->getTypeSizeInBits(Step->getType());
1273 return SE->getConstant(APInt::getMinValue(BitWidth) -
1274 SE->getUnsignedRangeMax(Step));
1340 ScalarEvolution *SE, unsigned Depth) {
1344 const Loop *L = AR->getLoop();
1345 const SCEV *Start = AR->getStart();
1346 const SCEV *Step = AR->getStepRecurrence(*SE);
1357 SmallVector<const SCEV *, 4> DiffOps(SA->operands());
1364 if (DiffOps.size() == SA->getNumOperands())
1372 ScalarEvolution::maskFlags(SA->getNoWrapFlags(), SCEV::FlagNUW);
1373 const SCEV *PreStart = SE->getAddExpr(DiffOps, PreStartFlags);
1375 SE->getAddRecExpr(PreStart, Step, L, SCEV::FlagAnyWrap));
1378 // "S+X does not sign/unsign-overflow".
1381 const SCEV *BECount = SE->getBackedgeTakenCount(L);
1382 if (PreAR && PreAR->getNoWrapFlags(WrapType) &&
1383 !isa<SCEVCouldNotCompute>(BECount) && SE->isKnownPositive(BECount))
1387 unsigned BitWidth = SE->getTypeSizeInBits(AR->getType());
1388 Type *WideTy = IntegerType::get(SE->getContext(), BitWidth * 2);
1390 SE->getAddExpr((SE->*GetExtendExpr)(PreStart, WideTy, Depth),
1391 (SE->*GetExtendExpr)(Step, WideTy, Depth));
1392 if ((SE->*GetExtendExpr)(Start, WideTy, Depth) == OperandExtendedStart) {
1393 if (PreAR && AR->getNoWrapFlags(WrapType)) {
1397 SE->setNoWrapFlags(const_cast<SCEVAddRecExpr *>(PreAR), WrapType);
1408 SE->isLoopEntryGuardedByCond(L, Pred, PreStart, OverflowLimit))
1418 unsigned Depth) {
1421 const SCEV *PreStart = getPreStartForExtend<ExtendOpTy>(AR, Ty, SE, Depth);
1423 return (SE->*GetExtendExpr)(AR->getStart(), Ty, Depth);
1425 return SE->getAddExpr((SE->*GetExtendExpr)(AR->getStepRecurrence(*SE), Ty,
1426 Depth),
1427 (SE->*GetExtendExpr)(PreStart, Ty, Depth));
1431 // motivating example for this rule: if we know `{0,+,4}` is `ult` `-1` and it
1436 // {S,+,X} == {S-T,+,X} + T
1437 // => Ext({S,+,X}) == Ext({S-T,+,X} + T)
1439 // If ({S-T,+,X} + T) does not overflow ... (1)
1441 // RHS == Ext({S-T,+,X} + T) == Ext({S-T,+,X}) + Ext(T)
1443 // If {S-T,+,X} does not overflow ... (2)
1445 // RHS == Ext({S-T,+,X}) + Ext(T) == {Ext(S-T),+,Ext(X)} + Ext(T)
1446 // == {Ext(S-T)+Ext(T),+,Ext(X)}
1448 // If (S-T)+T does not overflow ... (3)
1450 // RHS == {Ext(S-T)+Ext(T),+,Ext(X)} == {Ext(S-T+T),+,Ext(X)}
1456 // (3) is implied by (1) -- "(S-T)+T does not overflow" is simply "({S-T,+,X}+T)
1470 // non-constant `Start` and do a general SCEV subtraction to compute
1476 APInt StartAI = StartC->getAPInt();
1478 for (unsigned Delta : {-2, -1, 1, 2}) {
1479 const SCEV *PreStart = getConstant(StartAI - Delta);
1492 if (PreAR && PreAR->getNoWrapFlags(WrapType)) { // proves (2)
1493 const SCEV *DeltaS = getConstant(StartC->getType(), Delta);
1506 // level addition in (D + (C - D + x + y + ...)) would not wrap (signed or
1507 // unsigned) and the number of trailing zeros of (C - D + x + y + ...) is
1513 const APInt &C = ConstantTerm->getAPInt();
1517 for (unsigned I = 1, E = WholeAddExpr->getNumOperands(); I < E && TZ; ++I)
1518 TZ = std::min(TZ, SE.getMinTrailingZeros(WholeAddExpr->getOperand(I)));
1521 // guaranteeing that adding D to (C - D + x + y + ...) won't cause a wrap:
1528 // level addition in (D + {C-D,+,x}) would not wrap (signed or unsigned) and the
1529 // number of trailing zeros of (C - D + x * n) is maximized, where C is the \p
1551 auto &UserIDs = FoldCacheUser[I.first->second];
1559 I.first->second = S;
1565 ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) {
1566 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
1570 assert(!Op->getType()->isPointerTy() && "Can't extend pointer!");
1576 return Iter->second;
1578 const SCEV *S = getZeroExtendExprImpl(Op, Ty, Depth);
1585 unsigned Depth) {
1586 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
1589 assert(!Op->getType()->isPointerTy() && "Can't extend pointer!");
1593 return getConstant(SC->getAPInt().zext(getTypeSizeInBits(Ty)));
1595 // zext(zext(x)) --> zext(x)
1597 return getZeroExtendExpr(SZ->getOperand(), Ty, Depth + 1);
1607 if (Depth > MaxCastDepth) {
1615 // zext(trunc(x)) --> zext(x) or x or trunc(x)
1619 const SCEV *X = ST->getOperand();
1621 unsigned TruncBits = getTypeSizeInBits(ST->getType());
1625 return getTruncateOrZeroExtend(X, Ty, Depth);
1633 if (AR->isAffine()) {
1634 const SCEV *Start = AR->getStart();
1635 const SCEV *Step = AR->getStepRecurrence(*this);
1636 unsigned BitWidth = getTypeSizeInBits(AR->getType());
1637 const Loop *L = AR->getLoop();
1641 if (AR->hasNoUnsignedWrap()) {
1643 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty, this, Depth + 1);
1644 Step = getZeroExtendExpr(Step, Ty, Depth + 1);
1645 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
1648 // Check whether the backedge-taken count is SCEVCouldNotCompute.
1651 // being called from within backedge-taken count analysis, such that
1652 // attempting to ask for the backedge-taken count would likely result
1660 // Check whether the backedge-taken count can be losslessly casted to
1663 getTruncateOrZeroExtend(MaxBECount, Start->getType(), Depth);
1665 CastedMaxBECount, MaxBECount->getType(), Depth);
1670 SCEV::FlagAnyWrap, Depth + 1);
1673 Depth + 1),
1674 WideTy, Depth + 1);
1675 const SCEV *WideStart = getZeroExtendExpr(Start, WideTy, Depth + 1);
1677 getZeroExtendExpr(CastedMaxBECount, WideTy, Depth + 1);
1681 getZeroExtendExpr(Step, WideTy, Depth + 1),
1682 SCEV::FlagAnyWrap, Depth + 1),
1683 SCEV::FlagAnyWrap, Depth + 1);
1689 Depth + 1);
1690 Step = getZeroExtendExpr(Step, Ty, Depth + 1);
1691 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
1698 getSignExtendExpr(Step, WideTy, Depth + 1),
1699 SCEV::FlagAnyWrap, Depth + 1),
1700 SCEV::FlagAnyWrap, Depth + 1);
1703 // Negative step causes unsigned wrap, but it still can't self-wrap.
1707 Depth + 1);
1708 Step = getSignExtendExpr(Step, Ty, Depth + 1);
1709 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
1714 // Normally, in the cases we can prove no-overflow via a
1717 // guards present in the loop -- SCEV is not great at exploiting
1726 if (AR->hasNoUnsignedWrap()) {
1727 // Same as nuw case above - duplicated here to avoid a compile time
1732 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty, this, Depth + 1);
1733 Step = getZeroExtendExpr(Step, Ty, Depth + 1);
1734 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
1740 const SCEV *N = getConstant(APInt::getMaxValue(BitWidth) -
1746 // still can't self-wrap.
1750 Depth + 1);
1751 Step = getSignExtendExpr(Step, Ty, Depth + 1);
1752 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
1757 // zext({C,+,Step}) --> (zext(D) + zext({C-D,+,Step}))<nuw><nsw>
1758 // if D + (C - D + Step * n) could be proven to not unsigned wrap
1759 // where D maximizes the number of trailing zeros of (C - D + Step * n)
1761 const APInt &C = SC->getAPInt();
1764 const SCEV *SZExtD = getZeroExtendExpr(getConstant(D), Ty, Depth);
1766 getAddRecExpr(getConstant(C - D), Step, L, AR->getNoWrapFlags());
1767 const SCEV *SZExtR = getZeroExtendExpr(SResidual, Ty, Depth + 1);
1770 Depth + 1);
1777 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty, this, Depth + 1);
1778 Step = getZeroExtendExpr(Step, Ty, Depth + 1);
1779 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
1783 // zext(A % B) --> zext(A) % zext(B)
1788 return getURemExpr(getZeroExtendExpr(LHS, Ty, Depth + 1),
1789 getZeroExtendExpr(RHS, Ty, Depth + 1));
1792 // zext(A / B) --> zext(A) / zext(B).
1794 return getUDivExpr(getZeroExtendExpr(Div->getLHS(), Ty, Depth + 1),
1795 getZeroExtendExpr(Div->getRHS(), Ty, Depth + 1));
1798 // zext((A + B + ...)<nuw>) --> (zext(A) + zext(B) + ...)<nuw>
1799 if (SA->hasNoUnsignedWrap()) {
1803 for (const auto *Op : SA->operands())
1804 Ops.push_back(getZeroExtendExpr(Op, Ty, Depth + 1));
1805 return getAddExpr(Ops, SCEV::FlagNUW, Depth + 1);
1808 // zext(C + x + y + ...) --> (zext(D) + zext((C - D) + x + y + ...))
1809 // if D + (C - D + x + y + ...) could be proven to not unsigned wrap
1810 // where D maximizes the number of trailing zeros of (C - D + x + y + ...)
1816 if (const auto *SC = dyn_cast<SCEVConstant>(SA->getOperand(0))) {
1819 const SCEV *SZExtD = getZeroExtendExpr(getConstant(D), Ty, Depth);
1821 getAddExpr(getConstant(-D), SA, SCEV::FlagAnyWrap, Depth);
1822 const SCEV *SZExtR = getZeroExtendExpr(SResidual, Ty, Depth + 1);
1825 Depth + 1);
1831 // zext((A * B * ...)<nuw>) --> (zext(A) * zext(B) * ...)<nuw>
1832 if (SM->hasNoUnsignedWrap()) {
1836 for (const auto *Op : SM->operands())
1837 Ops.push_back(getZeroExtendExpr(Op, Ty, Depth + 1));
1838 return getMulExpr(Ops, SCEV::FlagNUW, Depth + 1);
1841 // zext(2^K * (trunc X to iN)) to iM ->
1842 // 2^K * (zext(trunc X to i{N-K}) to iM)<nuw>
1848 // = zext((trunc X to i{N-K}) << K)<nuw> to iM
1850 // = zext((2^K * (trunc X to i{N-K}))<nuw>) to iM
1851 // = (2^K * (zext(trunc X to i{N-K}) to iM))<nuw>.
1853 if (SM->getNumOperands() == 2)
1854 if (auto *MulLHS = dyn_cast<SCEVConstant>(SM->getOperand(0)))
1855 if (MulLHS->getAPInt().isPowerOf2())
1856 if (auto *TruncRHS = dyn_cast<SCEVTruncateExpr>(SM->getOperand(1))) {
1857 int NewTruncBits = getTypeSizeInBits(TruncRHS->getType()) -
1858 MulLHS->getAPInt().logBase2();
1863 getTruncateExpr(TruncRHS->getOperand(), NewTruncTy), Ty),
1864 SCEV::FlagNUW, Depth + 1);
1868 // zext(umin(x, y)) -> umin(zext(x), zext(y))
1869 // zext(umax(x, y)) -> umax(zext(x), zext(y))
1873 for (auto *Operand : MinMax->operands())
1880 // zext(umin_seq(x, y)) -> umin_seq(zext(x), zext(y))
1884 for (auto *Operand : MinMax->operands())
1900 ScalarEvolution::getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) {
1901 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
1905 assert(!Op->getType()->isPointerTy() && "Can't extend pointer!");
1911 return Iter->second;
1913 const SCEV *S = getSignExtendExprImpl(Op, Ty, Depth);
1920 unsigned Depth) {
1921 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
1924 assert(!Op->getType()->isPointerTy() && "Can't extend pointer!");
1929 return getConstant(SC->getAPInt().sext(getTypeSizeInBits(Ty)));
1931 // sext(sext(x)) --> sext(x)
1933 return getSignExtendExpr(SS->getOperand(), Ty, Depth + 1);
1935 // sext(zext(x)) --> zext(x)
1937 return getZeroExtendExpr(SZ->getOperand(), Ty, Depth + 1);
1947 // Limit recursion depth.
1948 if (Depth > MaxCastDepth) {
1956 // sext(trunc(x)) --> sext(x) or x or trunc(x)
1960 const SCEV *X = ST->getOperand();
1962 unsigned TruncBits = getTypeSizeInBits(ST->getType());
1966 return getTruncateOrSignExtend(X, Ty, Depth);
1970 // sext((A + B + ...)<nsw>) --> (sext(A) + sext(B) + ...)<nsw>
1971 if (SA->hasNoSignedWrap()) {
1975 for (const auto *Op : SA->operands())
1976 Ops.push_back(getSignExtendExpr(Op, Ty, Depth + 1));
1977 return getAddExpr(Ops, SCEV::FlagNSW, Depth + 1);
1980 // sext(C + x + y + ...) --> (sext(D) + sext((C - D) + x + y + ...))
1981 // if D + (C - D + x + y + ...) could be proven to not signed wrap
1982 // where D maximizes the number of trailing zeros of (C - D + x + y + ...)
1989 if (const auto *SC = dyn_cast<SCEVConstant>(SA->getOperand(0))) {
1992 const SCEV *SSExtD = getSignExtendExpr(getConstant(D), Ty, Depth);
1994 getAddExpr(getConstant(-D), SA, SCEV::FlagAnyWrap, Depth);
1995 const SCEV *SSExtR = getSignExtendExpr(SResidual, Ty, Depth + 1);
1998 Depth + 1);
2007 if (AR->isAffine()) {
2008 const SCEV *Start = AR->getStart();
2009 const SCEV *Step = AR->getStepRecurrence(*this);
2010 unsigned BitWidth = getTypeSizeInBits(AR->getType());
2011 const Loop *L = AR->getLoop();
2015 if (AR->hasNoSignedWrap()) {
2017 getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty, this, Depth + 1);
2018 Step = getSignExtendExpr(Step, Ty, Depth + 1);
2022 // Check whether the backedge-taken count is SCEVCouldNotCompute.
2025 // being called from within backedge-taken count analysis, such that
2026 // attempting to ask for the backedge-taken count would likely result
2035 // Check whether the backedge-taken count can be losslessly casted to
2038 getTruncateOrZeroExtend(MaxBECount, Start->getType(), Depth);
2040 CastedMaxBECount, MaxBECount->getType(), Depth);
2045 SCEV::FlagAnyWrap, Depth + 1);
2048 Depth + 1),
2049 WideTy, Depth + 1);
2050 const SCEV *WideStart = getSignExtendExpr(Start, WideTy, Depth + 1);
2052 getZeroExtendExpr(CastedMaxBECount, WideTy, Depth + 1);
2056 getSignExtendExpr(Step, WideTy, Depth + 1),
2057 SCEV::FlagAnyWrap, Depth + 1),
2058 SCEV::FlagAnyWrap, Depth + 1);
2064 Depth + 1);
2065 Step = getSignExtendExpr(Step, Ty, Depth + 1);
2066 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
2073 getZeroExtendExpr(Step, WideTy, Depth + 1),
2074 SCEV::FlagAnyWrap, Depth + 1),
2075 SCEV::FlagAnyWrap, Depth + 1);
2079 // abs(Step) * MaxBECount > unsigned-max(AR->getType())
2089 Depth + 1);
2090 Step = getZeroExtendExpr(Step, Ty, Depth + 1);
2091 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
2098 if (AR->hasNoSignedWrap()) {
2099 // Same as nsw case above - duplicated here to avoid a compile time
2104 getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty, this, Depth + 1);
2105 Step = getSignExtendExpr(Step, Ty, Depth + 1);
2106 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
2109 // sext({C,+,Step}) --> (sext(D) + sext({C-D,+,Step}))<nuw><nsw>
2110 // if D + (C - D + Step * n) could be proven to not signed wrap
2111 // where D maximizes the number of trailing zeros of (C - D + Step * n)
2113 const APInt &C = SC->getAPInt();
2116 const SCEV *SSExtD = getSignExtendExpr(getConstant(D), Ty, Depth);
2118 getAddRecExpr(getConstant(C - D), Step, L, AR->getNoWrapFlags());
2119 const SCEV *SSExtR = getSignExtendExpr(SResidual, Ty, Depth + 1);
2122 Depth + 1);
2129 getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty, this, Depth + 1);
2130 Step = getSignExtendExpr(Step, Ty, Depth + 1);
2131 return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags());
2138 return getZeroExtendExpr(Op, Ty, Depth + 1);
2140 // sext(smin(x, y)) -> smin(sext(x), sext(y))
2141 // sext(smax(x, y)) -> smax(sext(x), sext(y))
2145 for (auto *Operand : MinMax->operands())
2178 /// getAnyExtendExpr - Return a SCEV for the given operand extended with
2182 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
2188 // Sign-extend negative constants.
2190 if (SC->getAPInt().isNegative())
2195 const SCEV *NewOp = T->getOperand();
2196 if (getTypeSizeInBits(NewOp->getType()) < getTypeSizeInBits(Ty))
2214 for (const SCEV *Op : AR->operands())
2216 return getAddRecExpr(Ops, AR->getLoop(), SCEV::FlagNW);
2232 /// m + n + 13 + (A * (o + p + (B * (q + m + 29)))) + r + (-1 * r)
2247 /// may be exposed. This helps getAddRecExpr short-circuit extra work in
2263 if (Scale != 1 || AccumulatedConstant != 0 || C->getValue()->isZero())
2265 AccumulatedConstant += Scale * C->getAPInt();
2272 if (Mul && isa<SCEVConstant>(Mul->getOperand(0))) {
2274 Scale * cast<SCEVConstant>(Mul->getOperand(0))->getAPInt();
2275 if (Mul->getNumOperands() == 2 && isa<SCEVAddExpr>(Mul->getOperand(1))) {
2277 const SCEVAddExpr *Add = cast<SCEVAddExpr>(Mul->getOperand(1));
2280 Add->operands(), NewScale, SE);
2284 SmallVector<const SCEV *, 4> MulOps(drop_begin(Mul->operands()));
2288 NewOps.push_back(Pair.first->first);
2290 Pair.first->second += NewScale;
2301 NewOps.push_back(Pair.first->first);
2303 Pair.first->second += Scale;
2338 auto *NarrowTy = cast<IntegerType>(LHS->getType());
2340 IntegerType::get(NarrowTy->getContext(), NarrowTy->getBitWidth() * 2);
2342 const SCEV *A = (this->*Extension)(
2343 (this->*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0), WideTy, 0);
2344 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2345 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2346 const SCEV *B = (this->*Operation)(LHSB, RHSB, SCEV::FlagAnyWrap, 0);
2359 APInt C = RHSC->getAPInt();
2371 Magnitude = -C;
2382 // To avoid overflow up, we need to make sure that LHS <= MAX - Magnitude.
2385 APInt Limit = Max - Magnitude;
2394 if (OBO->hasNoUnsignedWrap() && OBO->hasNoSignedWrap())
2399 if (OBO->hasNoUnsignedWrap())
2401 if (OBO->hasNoSignedWrap())
2406 if (OBO->getOpcode() != Instruction::Add &&
2407 OBO->getOpcode() != Instruction::Sub &&
2408 OBO->getOpcode() != Instruction::Mul)
2411 const SCEV *LHS = getSCEV(OBO->getOperand(0));
2412 const SCEV *RHS = getSCEV(OBO->getOperand(1));
2416 if (!OBO->hasNoUnsignedWrap() &&
2417 willNotOverflow((Instruction::BinaryOps)OBO->getOpcode(),
2423 if (!OBO->hasNoSignedWrap() &&
2424 willNotOverflow((Instruction::BinaryOps)OBO->getOpcode(),
2436 // `OldFlags' as can't-wrap behavior. Infer a more aggressive set of
2437 // can't-overflow flags for the operation if possible.
2455 // If FlagNSW is true and all the operands are non-negative, infer FlagNUW.
2457 return SE->isKnownNonNegative(S);
2481 const APInt &C = cast<SCEVConstant>(Ops[0])->getAPInt();
2483 // (A <opcode> C) --> (A <opcode> C)<nsw> if the op doesn't sign overflow.
2487 if (NSWRegion.contains(SE->getSignedRange(Ops[1])))
2491 // (A <opcode> C) --> (A <opcode> C)<nuw> if the op doesn't unsign overflow.
2495 if (NUWRegion.contains(SE->getUnsignedRange(Ops[1])))
2504 Ops[0]->isZero() && IsKnownNonNegative(Ops[1]))
2511 if (UDiv->getOperand(1) == Ops[1])
2514 if (UDiv->getOperand(1) == Ops[0])
2522 return isLoopInvariant(S, L) && properlyDominates(S, L->getHeader());
2528 unsigned Depth) {
2534 Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
2536 assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
2539 Ops, [](const SCEV *Op) { return Op->getType()->isPointerTy(); });
2558 // Limit recursion calls depth.
2559 if (Depth > MaxArithDepth || hasHugeExpression(Ops))
2565 if (Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2566 Add->setNoWrapFlags(ComputeFlags(Ops));
2573 Type *Ty = Ops[0]->getType();
2575 for (unsigned i = 0, e = Ops.size(); i != e-1; ++i)
2576 if (Ops[i] == Ops[i+1]) { // X + Y + Y --> X + Y*2
2583 const SCEV *Mul = getMulExpr(Scale, Ops[i], SCEV::FlagAnyWrap, Depth + 1);
2588 --i; e -= Count - 1;
2592 return getAddExpr(Ops, OrigFlags, Depth + 1);
2596 // folded. eg., n*trunc(x) + m*trunc(y) --> trunc(trunc(m)*x + trunc(n)*y)
2598 auto FindTruncSrcType = [&]() -> Type * {
2604 return T->getOperand()->getType();
2606 const auto *LastOp = Mul->getOperand(Mul->getNumOperands() - 1);
2608 return T->getOperand()->getType();
2619 if (T->getOperand()->getType() != SrcType) {
2623 LargeOps.push_back(T->getOperand());
2628 for (unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2630 dyn_cast<SCEVTruncateExpr>(M->getOperand(j))) {
2631 if (T->getOperand()->getType() != SrcType) {
2635 LargeMulOps.push_back(T->getOperand());
2636 } else if (const auto *C = dyn_cast<SCEVConstant>(M->getOperand(j))) {
2644 LargeOps.push_back(getMulExpr(LargeMulOps, SCEV::FlagAnyWrap, Depth + 1));
2652 const SCEV *Fold = getAddExpr(LargeOps, SCEV::FlagAnyWrap, Depth + 1);
2660 // Check if we have an expression of the form ((X + C1) - C2), where C1 and
2667 if (AddExpr && C && isa<SCEVConstant>(AddExpr->getOperand(0))) {
2668 auto C1 = cast<SCEVConstant>(AddExpr->getOperand(0))->getAPInt();
2669 auto C2 = C->getAPInt();
2673 auto AddFlags = AddExpr->getNoWrapFlags();
2691 SmallVector<const SCEV *, 4> NewOps(AddExpr->operands());
2698 // Canonicalize (-1 * urem X, Y) + X --> (Y * X/Y)
2701 if (Mul && Mul->getNumOperands() == 2 &&
2702 Mul->getOperand(0)->isAllOnesValue()) {
2705 if (matchURem(Mul->getOperand(1), X, Y) && X == Ops[1]) {
2712 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddExpr)
2724 Add->getNumOperands() > AddOpsInlineThreshold)
2729 append_range(Ops, Add->operands());
2731 CommonFlags = maskFlags(CommonFlags, Add->getNoWrapFlags());
2738 return getAddExpr(Ops, CommonFlags, Depth + 1);
2742 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
2761 // re-generate the operands list. Group the operands by constant scale,
2765 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2766 // Re-generate the operands list.
2772 Ops.push_back(getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1));
2776 getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1),
2777 SCEV::FlagAnyWrap, Depth + 1));
2784 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
2793 for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) {
2794 const SCEV *MulOpSCEV = Mul->getOperand(MulOp);
2799 // Fold W + X + (X * Y * Z) --> W + (X * ((Y*Z)+1))
2800 const SCEV *InnerMul = Mul->getOperand(MulOp == 0);
2801 if (Mul->getNumOperands() != 2) {
2805 Mul->operands().take_front(MulOp));
2806 append_range(MulOps, Mul->operands().drop_front(MulOp + 1));
2807 InnerMul = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1);
2810 const SCEV *AddOne = getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1);
2812 SCEV::FlagAnyWrap, Depth + 1);
2816 Ops.erase(Ops.begin()+Idx-1);
2819 Ops.erase(Ops.begin()+AddOp-1);
2822 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
2832 for (unsigned OMulOp = 0, e = OtherMul->getNumOperands();
2834 if (OtherMul->getOperand(OMulOp) == MulOpSCEV) {
2835 // Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E))
2836 const SCEV *InnerMul1 = Mul->getOperand(MulOp == 0);
2837 if (Mul->getNumOperands() != 2) {
2839 Mul->operands().take_front(MulOp));
2840 append_range(MulOps, Mul->operands().drop_front(MulOp+1));
2841 InnerMul1 = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1);
2843 const SCEV *InnerMul2 = OtherMul->getOperand(OMulOp == 0);
2844 if (OtherMul->getNumOperands() != 2) {
2846 OtherMul->operands().take_front(OMulOp));
2847 append_range(MulOps, OtherMul->operands().drop_front(OMulOp+1));
2848 InnerMul2 = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1);
2852 getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1);
2854 SCEV::FlagAnyWrap, Depth + 1);
2857 Ops.erase(Ops.begin()+OtherMulIdx-1);
2859 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
2868 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
2877 const Loop *AddRecLoop = AddRec->getLoop();
2882 --i; --e;
2887 // Compute nowrap flags for the addition of the loop-invariant ops and
2894 // NLI + LI + {Start,+,Step} --> NLI + {LI+Start,+,Step}
2895 LIOps.push_back(AddRec->getStart());
2897 SmallVector<const SCEV *, 4> AddRecOps(AddRec->operands());
2912 auto *ReachI = &*AddRecLoop->getHeader()->begin();
2916 AddRecOps[0] = getAddExpr(LIOps, AddFlags, Depth + 1);
2921 Flags = AddRec->getNoWrapFlags(setFlags(Flags, SCEV::FlagNW));
2927 // Otherwise, add the folded AddRec by the non-invariant parts.
2933 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
2945 cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop()->getHeader(),
2946 AddRec->getLoop()->getHeader()) &&
2948 if (AddRecLoop == cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop()) {
2949 // Other + {A,+,B}<L> + {C,+,D}<L> --> Other + {A+C,+,B+D}<L>
2950 SmallVector<const SCEV *, 4> AddRecOps(AddRec->operands());
2954 if (OtherAddRec->getLoop() == AddRecLoop) {
2955 for (unsigned i = 0, e = OtherAddRec->getNumOperands();
2958 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2962 AddRecOps[i], OtherAddRec->getOperand(i)};
2963 AddRecOps[i] = getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1);
2965 Ops.erase(Ops.begin() + OtherIdx); --OtherIdx;
2968 // Step size has changed, so we cannot guarantee no self-wraparound.
2970 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
3001 S->setNoWrapFlags(Flags);
3047 S->setNoWrapFlags(Flags);
3062 // n(n-1)(n-2)...(n-(k-1)) / k(k-1)(k-2)...1 .
3063 // At each iteration, we take the n-th term of the numeral and divide by the
3064 // (k-n)th term of the denominator. This division will always produce an
3073 k = n-k;
3077 r = umul_ov(r, n-(i-1), Overflow);
3108 unsigned Depth) {
3114 Type *ETy = Ops[0]->getType();
3115 assert(!ETy->isPointerTy());
3117 assert(Ops[i]->getType() == ETy &&
3134 // Limit recursion calls depth.
3135 if (Depth > MaxArithDepth || hasHugeExpression(Ops))
3141 if (Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3142 Mul->setNoWrapFlags(ComputeFlags(Ops));
3148 // C1*(C2+V) -> C1*C2 + C1*V
3156 if (Add->getNumOperands() == 2 && containsConstantInAddMulChain(Add)) {
3157 const SCEV *LHS = getMulExpr(LHSC, Add->getOperand(0),
3158 SCEV::FlagAnyWrap, Depth + 1);
3159 const SCEV *RHS = getMulExpr(LHSC, Add->getOperand(1),
3160 SCEV::FlagAnyWrap, Depth + 1);
3161 return getAddExpr(LHS, RHS, SCEV::FlagAnyWrap, Depth + 1);
3164 if (Ops[0]->isAllOnesValue()) {
3165 // If we have a mul by -1 of an add, try distributing the -1 among the
3170 for (const SCEV *AddOp : Add->operands()) {
3172 Depth + 1);
3177 return getAddExpr(NewOps, SCEV::FlagAnyWrap, Depth + 1);
3179 // Negation preserves a recurrence's no self-wrap property.
3181 for (const SCEV *AddRecOp : AddRec->operands())
3183 Depth + 1));
3185 // multiplied by -1 can have signed overflow if and only if it takes a
3186 // value of M: M * (-1) would stay M and (M + 1) * (-1) would be the
3190 if (hasFlags(AddRec->getNoWrapFlags(), SCEV::FlagNSW)) {
3192 APInt::getSignedMinValue(getTypeSizeInBits(AddRec->getType()));
3196 return getAddRecExpr(Operands, AddRec->getLoop(),
3197 AddRec->getNoWrapFlags(FlagsMask));
3205 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
3217 append_range(Ops, Mul->operands());
3225 return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
3231 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
3241 if (isAvailableAtLoopEntry(Ops[i], AddRec->getLoop())) {
3244 --i; --e;
3249 // NLI * LI * {Start,+,Step} --> NLI * {LI*Start,+,LI*Step}
3251 NewOps.reserve(AddRec->getNumOperands());
3252 const SCEV *Scale = getMulExpr(LIOps, SCEV::FlagAnyWrap, Depth + 1);
3259 AddRec->getNoWrapFlags(ComputeFlags({Scale, AddRec}));
3261 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
3262 NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i),
3263 SCEV::FlagAnyWrap, Depth + 1));
3269 if (!NSWRegion.contains(getSignedRange(AddRec->getOperand(i))))
3274 const SCEV *NewRec = getAddRecExpr(NewOps, AddRec->getLoop(), Flags);
3279 // Otherwise, multiply the folded AddRec by the non-invariant parts.
3285 return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
3293 // = {x=1 in [ sum y=x..2x [ sum z=max(y-x, y-n)..min(x,n) [
3294 // choose(x, 2x)*choose(2x-y, x-z)*A_{y-z}*B_z
3308 if (!OtherAddRec || OtherAddRec->getLoop() != AddRec->getLoop())
3313 if (AddRec->getNumOperands() + OtherAddRec->getNumOperands() - 1 >
3318 Type *Ty = AddRec->getType();
3321 for (int x = 0, xe = AddRec->getNumOperands() +
3322 OtherAddRec->getNumOperands() - 1; x != xe && !Overflow; ++x) {
3325 uint64_t Coeff1 = Choose(x, 2*x - y, Overflow);
3326 for (int z = std::max(y-x, y-(int)AddRec->getNumOperands()+1),
3327 ze = std::min(x+1, (int)OtherAddRec->getNumOperands());
3329 uint64_t Coeff2 = Choose(2*x - y, x-z, Overflow);
3336 const SCEV *Term1 = AddRec->getOperand(y-z);
3337 const SCEV *Term2 = OtherAddRec->getOperand(z);
3339 SCEV::FlagAnyWrap, Depth + 1));
3344 AddRecOps.push_back(getAddExpr(SumOps, SCEV::FlagAnyWrap, Depth + 1));
3347 const SCEV *NewAddRec = getAddRecExpr(AddRecOps, AddRec->getLoop(),
3351 Ops.erase(Ops.begin() + OtherIdx); --OtherIdx;
3359 return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
3373 assert(getEffectiveSCEVType(LHS->getType()) ==
3374 getEffectiveSCEVType(RHS->getType()) &&
3377 // Short-circuit easy cases
3380 if (RHSC->getValue()->isOne())
3381 return getZero(LHS->getType()); // X urem 1 --> 0
3384 if (RHSC->getAPInt().isPowerOf2()) {
3385 Type *FullTy = LHS->getType();
3387 IntegerType::get(getContext(), RHSC->getAPInt().logBase2());
3392 // Fallback to %a == %x urem %y == %x -<nuw> ((%x udiv %y) *<nuw> %y)
3402 assert(!LHS->getType()->isPointerTy() &&
3404 assert(LHS->getType() == RHS->getType() &&
3420 if (RHSC->getValue()->isOne())
3421 return LHS; // X udiv 1 --> x
3425 if (!RHSC->getValue()->isZero()) {
3428 // TODO: Generalize this to non-constants by using known-bits information.
3429 Type *Ty = LHS->getType();
3430 unsigned LZ = RHSC->getAPInt().countl_zero();
3431 unsigned MaxShiftAmt = getTypeSizeInBits(Ty) - LZ - 1;
3432 // For non-power-of-two values, effectively round the value up to the
3434 if (!RHSC->getAPInt().isPowerOf2())
3440 dyn_cast<SCEVConstant>(AR->getStepRecurrence(*this))) {
3441 // {X,+,N}/C --> {X/C,+,N/C} if safe and N/C can be folded.
3442 const APInt &StepInt = Step->getAPInt();
3443 const APInt &DivInt = RHSC->getAPInt();
3446 getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy),
3448 AR->getLoop(), SCEV::FlagAnyWrap)) {
3450 for (const SCEV *Op : AR->operands())
3452 return getAddRecExpr(Operands, AR->getLoop(), SCEV::FlagNW);
3455 /// {X,+,N}/C => {Y,+,N}/C where Y=X-(X%N). Safe when C%N=0.
3457 const SCEVConstant *StartC = dyn_cast<SCEVConstant>(AR->getStart());
3460 getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy),
3462 AR->getLoop(), SCEV::FlagAnyWrap)) {
3463 const APInt &StartInt = StartC->getAPInt();
3467 getAddRecExpr(getConstant(StartInt - StartRem), Step,
3468 AR->getLoop(), SCEV::FlagNW);
3485 // (A*B)/C --> A*(B/C) if safe and B/C can be folded.
3488 for (const SCEV *Op : M->operands())
3492 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3493 const SCEV *Op = M->getOperand(i);
3496 Operands = SmallVector<const SCEV *, 4>(M->operands());
3503 // (A/B)/C --> A/(B*C) if safe and B*C can be folded.
3506 dyn_cast<SCEVConstant>(OtherDiv->getRHS())) {
3509 DivisorConstant->getAPInt().umul_ov(RHSC->getAPInt(), Overflow);
3511 return getConstant(RHSC->getType(), 0, false);
3513 return getUDivExpr(OtherDiv->getLHS(), getConstant(NewRHS));
3517 // (A+B)/C --> (A/C + B/C) if safe and A/C and B/C can be folded.
3520 for (const SCEV *Op : A->operands())
3524 for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) {
3525 const SCEV *Op = getUDivExpr(A->getOperand(i), RHS);
3527 getMulExpr(Op, RHS) != A->getOperand(i))
3531 if (Operands.size() == A->getNumOperands())
3538 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3542 // ((-C + (C smax %x)) /u %x) evaluates to zero, for any positive constant C.
3544 AE && AE->getNumOperands() == 2) {
3545 if (const auto *VC = dyn_cast<SCEVConstant>(AE->getOperand(0))) {
3546 const APInt &NegC = VC->getAPInt();
3548 const auto *MME = dyn_cast<SCEVSMaxExpr>(AE->getOperand(1));
3549 if (MME && MME->getNumOperands() == 2 &&
3550 isa<SCEVConstant>(MME->getOperand(0)) &&
3551 cast<SCEVConstant>(MME->getOperand(0))->getAPInt() == -NegC &&
3552 MME->getOperand(1) == RHS)
3553 return getZero(LHS->getType());
3570 APInt A = C1->getAPInt().abs();
3571 APInt B = C2->getAPInt().abs();
3594 if (!Mul || !Mul->hasNoUnsignedWrap())
3600 if (const auto *LHSCst = dyn_cast<SCEVConstant>(Mul->getOperand(0))) {
3602 SmallVector<const SCEV *, 2> Operands(drop_begin(Mul->operands()));
3612 cast<SCEVConstant>(getConstant(LHSCst->getAPInt().udiv(Factor)));
3614 cast<SCEVConstant>(getConstant(RHSCst->getAPInt().udiv(Factor)));
3617 append_range(Operands, Mul->operands().drop_front());
3627 for (int i = 0, e = Mul->getNumOperands(); i != e; ++i) {
3628 if (Mul->getOperand(i) == RHS) {
3630 append_range(Operands, Mul->operands().take_front(i));
3631 append_range(Operands, Mul->operands().drop_front(i + 1));
3647 if (StepChrec->getLoop() == L) {
3648 append_range(Operands, StepChrec->operands());
3663 Type *ETy = getEffectiveSCEVType(Operands[0]->getType());
3665 assert(getEffectiveSCEVType(Op->getType()) == ETy &&
3667 assert(!Op->getType()->isPointerTy() && "Step must be integer");
3674 if (Operands.back()->isZero()) {
3676 return getAddRecExpr(Operands, L, SCEV::FlagAnyWrap); // {X,+,0} --> X
3687 // Canonicalize nested AddRecs in by nesting them in order of loop depth.
3689 const Loop *NestedLoop = NestedAR->getLoop();
3690 if (L->contains(NestedLoop)
3691 ? (L->getLoopDepth() < NestedLoop->getLoopDepth())
3692 : (!NestedLoop->contains(L) &&
3693 DT.dominates(L->getHeader(), NestedLoop->getHeader()))) {
3694 SmallVector<const SCEV *, 4> NestedOperands(NestedAR->operands());
3695 Operands[0] = NestedAR->getStart();
3696 // AddRecs require their operands be loop-invariant with respect to their
3708 maskFlags(Flags, SCEV::FlagNW | NestedAR->getNoWrapFlags());
3721 maskFlags(NestedAR->getNoWrapFlags(), SCEV::FlagNW | Flags);
3738 const SCEV *BaseExpr = getSCEV(GEP->getPointerOperand());
3739 // getSCEV(Base)->getType() has the same address space as Base->getType()
3741 Type *IntIdxTy = getEffectiveSCEVType(BaseExpr->getType());
3742 GEPNoWrapFlags NW = GEP->getNoWrapFlags();
3747 // TODO: non-instructions have global scope. We might be able to prove
3760 Type *CurTy = GEP->getType();
3767 ConstantInt *Index = cast<SCEVConstant>(IndexExpr)->getValue();
3768 unsigned FieldNo = Index->getZExtValue();
3773 CurTy = STy->getTypeAtIndex(Index);
3779 CurTy = GEP->getSourceElementType();
3803 // non-negative, we can use nuw.
3808 assert(BaseExpr->getType() == GEPExpr->getType() &&
3809 "GEP should not change type mid-flight.");
3834 Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
3836 assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
3838 assert(Ops[0]->getType()->isPointerTy() ==
3839 Ops[i]->getType()->isPointerTy() &&
3887 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < Kind)
3894 while (Ops[Idx]->getSCEVType() == Kind) {
3897 append_range(Ops, SMME->operands());
3914 for (unsigned i = 0, e = Ops.size() - 1; i != e; ++i) {
3917 // X op Y op Y --> X op Y
3918 // X op Y --> X, if we know X, Y are ordered appropriately
3920 --i;
3921 --e;
3924 // X op Y --> Y, if we know X, Y are ordered appropriately
3926 --i;
3927 --e;
3965 const SCEVTypes NonSequentialRootKind; // Non-sequential variant of RootKind.
3977 SCEVTypes Kind = S->getSCEVType();
3984 bool Changed = visit(Kind, NAry->operands(), NewOps);
4109 // introduce poison -- they encode guaranteed, non-speculated knowledge.
4122 !scevUnconditionallyPropagatesPoisonFromOperands(S->getSCEVType()))
4126 if (!isGuaranteedNotToBePoison(SU->getValue()))
4138 // We need to look through potentially poison-blocking operations here,
4150 // as well. We cannot look through potentially poison-blocking operations
4165 Result.insert(SU->getValue());
4176 // poison-contributors of S, and then check whether I has any additional
4177 // poison-contributors. Poison that is contributed through poison-generating
4207 if (PDI->isDisjoint())
4214 II && II->getIntrinsicID() == Intrinsic::vscale)
4221 if (I->hasPoisonGeneratingAnnotations())
4224 for (Value *Op : I->operands())
4239 Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
4241 assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
4243 assert(Ops[0]->getType()->isPointerTy() ==
4244 Ops[i]->getType()->isPointerTy() &&
4272 if (Ops[Idx]->getSCEVType() != Kind) {
4278 Ops.insert(Ops.begin() + Idx, SMME->operands().begin(),
4279 SMME->operands().end());
4291 SaturationPoint = getZero(Ops[0]->getType());
4304 if (::impliesPoison(Ops[i], Ops[i - 1]) ||
4305 isKnownViaNonRecursiveReasoning(ICmpInst::ICMP_NE, Ops[i - 1],
4307 SmallVector<const SCEV *> SeqOps = {Ops[i - 1], Ops[i]};
4308 Ops[i - 1] = getMinMaxExpr(
4316 if (isKnownViaNonRecursiveReasoning(Pred, Ops[i - 1], Ops[i])) {
4402 // We can bypass creating a target-independent constant expression and then
4403 // folding it back into a ConstantInt. This is just a compile-time
4406 assert(!SL->getSizeInBits().isScalable() &&
4408 return getConstant(IntTy, SL->getElementOffset(FieldNo));
4422 assert(cast<SCEVUnknown>(S)->getValue() == V &&
4433 //===----------------------------------------------------------------------===//
4440 /// target-specific information.
4443 return Ty->isIntOrPtrTy();
4450 if (Ty->isPointerTy())
4461 if (Ty->isIntegerTy())
4465 assert(Ty->isPointerTy() && "Unexpected non-pointer non-integer type!");
4494 return SU && SU->getValue() == nullptr;
4503 return I->second;
4517 return SI->second.getArrayRef();
4526 auto EVIt = ExprValueMap.find(I->second);
4527 bool Removed = EVIt->second.remove(V);
4548 assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
4556 assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
4560 const SCEV *S = I->second;
4568 /// Return a SCEV corresponding to -V = -1*V
4573 cast<ConstantInt>(ConstantExpr::getNeg(VC->getValue())));
4575 Type *Ty = V->getType();
4583 if (!Add || Add->getNumOperands() != 2 ||
4584 !Add->getOperand(0)->isAllOnesValue())
4587 const SCEVMulExpr *AddRHS = dyn_cast<SCEVMulExpr>(Add->getOperand(1));
4588 if (!AddRHS || AddRHS->getNumOperands() != 2 ||
4589 !AddRHS->getOperand(0)->isAllOnesValue())
4592 return AddRHS->getOperand(1);
4595 /// Return a SCEV corresponding to ~V = -1-V
4597 assert(!V->getType()->isPointerTy() && "Can't negate pointer");
4601 cast<ConstantInt>(ConstantExpr::getNot(VC->getValue())));
4607 for (const SCEV *Operand : MME->operands()) {
4613 return getMinMaxExpr(SCEVMinMaxExpr::negate(MME->getSCEVType()),
4620 Type *Ty = V->getType();
4626 assert(P->getType()->isPointerTy());
4630 SmallVector<const SCEV *> Ops{AddRec->operands()};
4634 return getAddRecExpr(Ops, AddRec->getLoop(), SCEV::FlagAnyWrap);
4638 SmallVector<const SCEV *> Ops{Add->operands()};
4641 if (AddOp->getType()->isPointerTy()) {
4652 return getZero(P->getType());
4657 unsigned Depth) {
4658 // Fast path: X - X --> 0.
4660 return getZero(LHS->getType());
4665 if (RHS->getType()->isPointerTy()) {
4666 if (!LHS->getType()->isPointerTy() ||
4673 // We represent LHS - RHS as LHS + (-1)*RHS. This transformation
4679 // Let M be the minimum representable signed value. Then (-1)*RHS
4680 // signed-wraps if and only if RHS is M. That can happen even for
4681 // a NSW subtraction because e.g. (-1)*M signed-wraps even though
4682 // -1 - M does not. So to transfer NSW from LHS - RHS to LHS +
4683 // (-1)*RHS, we need to prove that RHS != M.
4685 // If LHS is non-negative and we know that LHS - RHS does not
4686 // signed-wrap, then RHS cannot be M. So we can rule out signed-wrap
4693 // FIXME: Find a correct way to transfer NSW to (-1)*M when LHS -
4698 // not in RHS. Applying NSW to (-1)*M may then let the NSW have a
4702 return getAddExpr(LHS, getNegativeSCEV(RHS, NegFlags), AddFlags, Depth);
4706 unsigned Depth) {
4707 Type *SrcTy = V->getType();
4708 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4709 "Cannot truncate or zero extend with non-integer arguments!");
4713 return getTruncateExpr(V, Ty, Depth);
4714 return getZeroExtendExpr(V, Ty, Depth);
4718 unsigned Depth) {
4719 Type *SrcTy = V->getType();
4720 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4721 "Cannot truncate or zero extend with non-integer arguments!");
4725 return getTruncateExpr(V, Ty, Depth);
4726 return getSignExtendExpr(V, Ty, Depth);
4731 Type *SrcTy = V->getType();
4732 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4733 "Cannot noop or zero extend with non-integer arguments!");
4743 Type *SrcTy = V->getType();
4744 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4745 "Cannot noop or sign extend with non-integer arguments!");
4755 Type *SrcTy = V->getType();
4756 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4757 "Cannot noop or any extend with non-integer arguments!");
4767 Type *SrcTy = V->getType();
4768 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4769 "Cannot truncate or noop with non-integer arguments!");
4782 if (getTypeSizeInBits(LHS->getType()) > getTypeSizeInBits(RHS->getType()))
4783 PromotedRHS = getZeroExtendExpr(RHS, LHS->getType());
4785 PromotedLHS = getNoopOrZeroExtend(LHS, RHS->getType());
4809 MaxType = getWiderType(MaxType, S->getType());
4811 MaxType = S->getType();
4825 if (!V->getType()->isPointerTy())
4830 V = AddRec->getStart();
4833 for (const SCEV *AddOp : Add->operands()) {
4834 if (AddOp->getType()->isPointerTy()) {
4850 // Push the def-use children onto the Worklist stack.
4851 for (User *U : I->users()) {
4860 /// Takes SCEV S and Loop L. For each AddRec sub-expression, use its start
4864 /// If SCEV contains non-invariant unknown SCEV rewrite cannot be done.
4885 // Only re-write AddRecExprs for this loop.
4886 if (Expr->getLoop() == L)
4887 return Expr->getStart();
4905 /// Takes SCEV S and Loop L. For each AddRec sub-expression, use its post
4908 /// If SCEV contains non-invariant unknown SCEV rewrite cannot be done.
4926 // Only re-write AddRecExprs for this loop.
4927 if (Expr->getLoop() == L)
4928 return Expr->getPostIncExpr(SE);
4956 if (BasicBlock *Latch = L->getLoopLatch()) {
4957 BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
4958 if (BI && BI->isConditional()) {
4959 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
4961 BECond = BI->getCondition();
4962 IsPosBECond = BI->getSuccessor(0) == L->getHeader();
4976 Instruction *I = cast<Instruction>(Expr->getValue());
4977 switch (I->getOpcode()) {
4981 compareWithBackedgeCondition(SI->getCondition());
4983 bool IsOne = cast<SCEVConstant>(*Res)->getValue()->isOne();
4984 Result = SE.getSCEV(IsOne ? SI->getTrueValue() : SI->getFalseValue());
5043 if (Expr->getLoop() == L && Expr->isAffine())
5044 return SE.getMinusSCEV(Expr, Expr->getStepRecurrence(SE));
5063 if (!AR->isAffine())
5070 if (!AR->hasNoSelfWrap()) {
5071 const SCEV *BECount = getConstantMaxBackedgeTakenCount(AR->getLoop());
5073 ConstantRange StepCR = getSignedRange(AR->getStepRecurrence(*this));
5074 const APInt &BECountAP = BECountMax->getAPInt();
5077 if (NoOverflowBitWidth <= getTypeSizeInBits(AR->getType()))
5082 if (!AR->hasNoSignedWrap()) {
5084 ConstantRange IncRange = getSignedRange(AR->getStepRecurrence(*this));
5092 if (!AR->hasNoUnsignedWrap()) {
5094 ConstantRange IncRange = getUnsignedRange(AR->getStepRecurrence(*this));
5107 SCEV::NoWrapFlags Result = AR->getNoWrapFlags();
5109 if (AR->hasNoSignedWrap())
5112 if (!AR->isAffine())
5119 const SCEV *Step = AR->getStepRecurrence(*this);
5120 const Loop *L = AR->getLoop();
5122 // Check whether the backedge-taken count is SCEVCouldNotCompute.
5125 // being called from within backedge-taken count analysis, such that
5126 // attempting to ask for the backedge-taken count would likely result
5132 // Normally, in the cases we can prove no-overflow via a
5135 // guards present in the loop -- SCEV is not great at exploiting
5144 // If the backedge is guarded by a comparison with the pre-inc value the
5146 // start value and the backedge is guarded by a comparison with the post-inc
5160 SCEV::NoWrapFlags Result = AR->getNoWrapFlags();
5162 if (AR->hasNoUnsignedWrap())
5165 if (!AR->isAffine())
5172 const SCEV *Step = AR->getStepRecurrence(*this);
5173 unsigned BitWidth = getTypeSizeInBits(AR->getType());
5174 const Loop *L = AR->getLoop();
5176 // Check whether the backedge-taken count is SCEVCouldNotCompute.
5179 // being called from within backedge-taken count analysis, such that
5180 // attempting to ask for the backedge-taken count would likely result
5186 // Normally, in the cases we can prove no-overflow via a
5189 // guards present in the loop -- SCEV is not great at exploiting
5198 // If the backedge is guarded by a comparison with the pre-inc value the
5200 // start value and the backedge is guarded by a comparison with the post-inc
5203 const SCEV *N = getConstant(APInt::getMinValue(BitWidth) -
5231 : Opcode(Op->getOpcode()), LHS(Op->getOperand(0)), RHS(Op->getOperand(1)),
5234 IsNSW = OBO->hasNoSignedWrap();
5235 IsNUW = OBO->hasNoUnsignedWrap();
5256 // creating new SCEV expressions -- our caller knowns tricks to avoid creating
5259 switch (Op->getOpcode()) {
5272 if (cast<PossiblyDisjointInst>(Op)->isDisjoint())
5273 return BinaryOp(Instruction::Add, Op->getOperand(0), Op->getOperand(1),
5279 if (auto *RHSC = dyn_cast<ConstantInt>(Op->getOperand(1)))
5282 if (RHSC->getValue().isSignMask())
5283 return BinaryOp(Instruction::Add, Op->getOperand(0), Op->getOperand(1));
5284 // Binary `xor` is a bit-wise `add`.
5285 if (V->getType()->isIntegerTy(1))
5286 return BinaryOp(Instruction::Add, Op->getOperand(0), Op->getOperand(1));
5291 if (ConstantInt *SA = dyn_cast<ConstantInt>(Op->getOperand(1))) {
5292 uint32_t BitWidth = cast<IntegerType>(Op->getType())->getBitWidth();
5298 if (SA->getValue().ult(BitWidth)) {
5300 ConstantInt::get(SA->getContext(),
5301 APInt::getOneBitSet(BitWidth, SA->getZExtValue()));
5302 return BinaryOp(Instruction::UDiv, Op->getOperand(0), X);
5309 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5312 auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand());
5316 Instruction::BinaryOps BinOp = WO->getBinaryOp();
5317 bool Signed = WO->isSigned();
5320 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5322 // Now that we know that all uses of the arithmetic-result component of
5324 // that the arithmetic is non-overflowing.
5325 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5336 if (II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5337 return BinaryOp(Instruction::Sub, II->getOperand(0), II->getOperand(1));
5368 unsigned SourceBits = SE.getTypeSizeInBits(SymbolicPHI->getType());
5369 unsigned NewBits = SE.getTypeSizeInBits(Op->getType());
5378 SExt ? dyn_cast<SCEVTruncateExpr>(SExt->getOperand())
5379 : dyn_cast<SCEVTruncateExpr>(ZExt->getOperand());
5382 const SCEV *X = Trunc->getOperand();
5386 return Trunc->getType();
5390 if (!PN->getType()->isIntegerTy())
5392 const Loop *L = LI.getLoopFor(PN->getParent());
5393 if (!L || L->getHeader() != PN->getParent())
5401 // which correspond to a phi->trunc->sext/zext->add->phi update chain.
5411 // It will visitMul->visitAdd->visitSExt->visitTrunc->visitUnknown(%X),
5441 // inductions where the sext-trunc / zext-trunc operations (partly) occur
5445 // which correspond to a phi->add->trunc->sext/zext->phi update chain.
5448 // which correspond to a phi->trunc->add->sext/zext->phi update chain.
5455 // *** Part1: Analyze if we have a phi-with-cast pattern for which we can
5458 auto *PN = cast<PHINode>(SymbolicPHI->getValue());
5466 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5467 Value *V = PN->getIncomingValue(i);
5468 if (L->contains(PN->getIncomingBlock(i))) {
5496 unsigned FoundIndex = Add->getNumOperands();
5499 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
5501 isSimpleCastedPHI(Add->getOperand(i), SymbolicPHI, Signed, *this)))
5507 if (FoundIndex == Add->getNumOperands())
5512 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
5514 Ops.push_back(Add->getOperand(i));
5524 // Analysis was successful: we have a phi-with-cast pattern for which we
5528 // fits within the truncated type (does not overflow) for i = 0 to n-1.
5547 // Expr(i) = (Ext ix (Trunc iy (Expr(i-1)) to ix) to iy) + Accum
5554 // = (Ext ix (Trunc iy (Expr(i-1)) to ix) to iy) + Accum + Accum
5557 // = (Ext ix (Trunc iy (Start + (i-1)*Accum) to ix) to iy) + Accum + Accum
5559 // = (Ext ix (Trunc iy (Start + (i-1)*Accum) to ix) to iy)
5563 // = (Ext ix (Trunc iy ((Start + (i-1)*Accum) + Accum) to ix) to iy)
5602 bool CreateSignExtend) -> const SCEV * {
5606 CreateSignExtend ? getSignExtendExpr(TruncatedExpr, Expr->getType())
5607 : getZeroExtendExpr(TruncatedExpr, Expr->getType());
5617 const SCEV *ExtendedExpr) -> bool {
5624 LLVM_DEBUG(dbgs() << "P2 is compile-time false\n";);
5632 LLVM_DEBUG(dbgs() << "P3 is compile-time false\n";);
5637 const SCEV *ExtendedExpr) -> void {
5664 auto *PN = cast<PHINode>(SymbolicPHI->getValue());
5673 I->second;
5708 auto areExprsEqual = [&](const SCEV *Expr1, const SCEV *Expr2) -> bool {
5710 !Preds->implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5711 !Preds->implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5716 if (!areExprsEqual(AR1->getStart(), AR2->getStart()) ||
5717 !areExprsEqual(AR1->getStepRecurrence(SE), AR2->getStepRecurrence(SE)))
5731 const Loop *L = LI.getLoopFor(PN->getParent());
5732 assert(L && L->getHeader() == PN->getParent());
5739 if (BO->Opcode != Instruction::Add)
5743 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5744 Accum = getSCEV(BO->RHS);
5745 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5746 Accum = getSCEV(BO->LHS);
5752 if (BO->IsNUW)
5754 if (BO->IsNSW)
5763 (SCEV::NoWrapFlags)(AR->getNoWrapFlags() |
5767 // We can add Flags to the post-inc expression only if we
5781 const Loop *L = LI.getLoopFor(PN->getParent());
5782 if (!L || L->getHeader() != PN->getParent())
5789 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5790 Value *V = PN->getIncomingValue(i);
5791 if (L->contains(PN->getIncomingBlock(i))) {
5821 // the back-edge.
5832 unsigned FoundIndex = Add->getNumOperands();
5833 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
5834 if (Add->getOperand(i) == SymbolicName)
5840 if (FoundIndex != Add->getNumOperands()) {
5843 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
5845 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(Add->getOperand(i),
5853 cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
5857 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5858 if (BO->IsNUW)
5860 if (BO->IsNSW)
5864 if (GEP->getOperand(0) == PN) {
5865 GEPNoWrapFlags NW = GEP->getNoWrapFlags();
5870 // If the GEP is nuw or nusw with non-negative offset, we know that
5879 // operations -- sub nuw X, Y is not the same as add nuw X, -Y
5894 (SCEV::NoWrapFlags)(AR->getNoWrapFlags() |
5898 // We can add Flags to the post-inc expression only if we
5912 // Because the other in-value of i (0) fits the evolution of BEValue
5917 // PHI(f(0), f({1,+,1})) --> f({0,+,1})
5950 C = BI->getCondition();
5952 BasicBlockEdge LeftEdge(BI->getParent(), BI->getSuccessor(0));
5953 BasicBlockEdge RightEdge(BI->getParent(), BI->getSuccessor(1));
5960 Use &LeftUse = Merge->getOperandUse(0);
5961 Use &RightUse = Merge->getOperandUse(1);
5981 if (PN->getNumIncomingValues() == 2 && all_of(PN->blocks(), IsReachable)) {
5994 BasicBlock *IDom = DT[PN->getParent()]->getIDom()->getBlock();
5997 auto *BI = dyn_cast<BranchInst>(IDom->getTerminator());
6000 if (BI && BI->isConditional() &&
6002 properlyDominates(getSCEV(LHS), PN->getParent()) &&
6003 properlyDominates(getSCEV(RHS), PN->getParent()))
6023 for (Value *Incoming : PN->incoming_values()) {
6028 if (!CommonInst->isIdenticalToWhenDefined(IncomingInst))
6041 all_of(drop_begin(PN->incoming_values()),
6072 const SCEVTypes NonSequentialRootKind; // Non-seq variant of RootKind.
6078 // as the type of our root SCEV expression, and into zero-extensions.
6092 return !isDone() && canRecurseInto(S->getSCEVType());
6111 Value *LHS = ICI->getOperand(0);
6112 Value *RHS = ICI->getOperand(1);
6114 switch (ICI->getPredicate()) {
6125 // a > b ? a+x : b+x -> max(a, b)+x
6126 // a > b ? b+x : a+x -> min(a, b)+x
6127 if (getTypeSizeInBits(LHS->getType()) <= getTypeSizeInBits(Ty)) {
6128 bool Signed = ICI->isSigned();
6133 if (LA->getType()->isPointerTy()) {
6142 auto CoerceOperand = [&](const SCEV *Op) -> const SCEV * {
6143 if (Op->getType()->isPointerTy()) {
6171 // x != 0 ? x+y : C+y -> x == 0 ? C+y : x+y
6175 // x == 0 ? C+y : x+y -> umax(x, C)+y iff C u<= 1
6176 if (getTypeSizeInBits(LHS->getType()) <= getTypeSizeInBits(Ty) &&
6177 isa<ConstantInt>(RHS) && cast<ConstantInt>(RHS)->isZero()) {
6181 const SCEV *Y = getMinusSCEV(FalseValExpr, X); // y = (x+y)-x
6182 const SCEV *C = getMinusSCEV(TrueValExpr, Y); // C = (C+y)-y
6183 if (isa<SCEVConstant>(C) && cast<SCEVConstant>(C)->getAPInt().ule(1))
6186 // x == 0 ? 0 : umin (..., x, ...) -> umin_seq(x, umin (...))
6187 // x == 0 ? 0 : umin_seq(..., x, ...) -> umin_seq(x, umin_seq(...))
6189 // -> umin_seq(x, umin (..., umin_seq(...), ...))
6190 if (isa<ConstantInt>(RHS) && cast<ConstantInt>(RHS)->isZero() &&
6191 isa<ConstantInt>(TrueVal) && cast<ConstantInt>(TrueVal)->isZero()) {
6194 X = ZExt->getOperand();
6195 if (getTypeSizeInBits(X->getType()) <= getTypeSizeInBits(Ty)) {
6213 assert(CondExpr->getType()->isIntegerTy(1) &&
6214 TrueExpr->getType() == FalseExpr->getType() &&
6215 TrueExpr->getType()->isIntegerTy(1) &&
6218 // i1 cond ? i1 x : i1 C --> C + (i1 cond ? (i1 x - i1 C) : i1 0)
6219 // --> C + (umin_seq cond, x - C)
6221 // i1 cond ? i1 C : i1 x --> C + (i1 cond ? i1 0 : (i1 x - i1 C))
6222 // --> C + (i1 ~cond ? (i1 x - i1 C) : i1 0)
6223 // --> C + (umin_seq ~cond, x - C)
6232 CondExpr = SE->getNotSCEV(CondExpr);
6239 return SE->getAddExpr(C, SE->getUMinExpr(CondExpr, SE->getMinusSCEV(X, C),
6249 const auto *SECond = SE->getSCEV(Cond);
6250 const auto *SETrue = SE->getSCEV(TrueVal);
6251 const auto *SEFalse = SE->getSCEV(FalseVal);
6257 assert(Cond->getType()->isIntegerTy(1) && "Select condition is not an i1?");
6258 assert(TrueVal->getType() == FalseVal->getType() &&
6259 V->getType() == TrueVal->getType() &&
6262 // For now, only deal with i1-typed `select`s.
6263 if (!V->getType()->isIntegerTy(1))
6279 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6284 createNodeForSelectOrPHIInstWithICmpInstCond(I->getType(), ICI,
6296 assert(GEP->getSourceElementType()->isSized() &&
6300 for (Value *Index : GEP->indices())
6306 uint64_t BitWidth = getTypeSizeInBits(S->getType());
6314 APInt Res = getConstantMultiple(N->getOperand(0));
6315 for (unsigned I = 1, E = N->getNumOperands(); I < E && Res != 1; ++I)
6317 Res, getConstantMultiple(N->getOperand(I)));
6321 switch (S->getSCEVType()) {
6323 return cast<SCEVConstant>(S)->getAPInt();
6325 return getConstantMultiple(cast<SCEVPtrToIntExpr>(S)->getOperand());
6332 uint32_t TZ = getMinTrailingZeros(T->getOperand());
6337 return getConstantMultiple(Z->getOperand()).zext(BitWidth);
6342 uint32_t TZ = getMinTrailingZeros(E->getOperand());
6347 if (M->hasNoUnsignedWrap()) {
6349 APInt Res = getConstantMultiple(M->getOperand(0));
6350 for (const SCEV *Operand : M->operands().drop_front())
6358 for (const SCEV *Operand : M->operands())
6365 if (N->hasNoUnsignedWrap())
6368 uint32_t TZ = getMinTrailingZeros(N->getOperand(0));
6369 for (const SCEV *Operand : N->operands().drop_front())
6383 computeKnownBits(U->getValue(), getDataLayout(), 0, &AC, nullptr, &DT)
6396 return I->second;
6401 return InsertPair.first->second;
6411 (unsigned)getTypeSizeInBits(S->getType()));
6417 if (MDNode *MD = I->getMetadata(LLVMContext::MD_range))
6420 if (std::optional<ConstantRange> Range = CB->getRange())
6424 if (std::optional<ConstantRange> Range = A->getRange())
6432 if (AddRec->getNoWrapFlags(Flags) != Flags) {
6433 AddRec->setNoWrapFlags(Flags);
6444 unsigned BitWidth = getTypeSizeInBits(U->getType());
6453 // and other addrecs in the same loop (for non-affine addrecs). The code
6455 auto *P = dyn_cast<PHINode>(U->getValue());
6461 // and this leads to false-positive recurrence test.
6462 for (auto *Pred : predecessors(P->getParent()))
6473 auto *L = LI.getLoopFor(P->getParent());
6474 assert(L && L->getHeader() == P->getParent());
6475 if (!L->contains(BO->getParent()))
6484 switch (BO->getOpcode()) {
6493 if (BO->getOperand(0) != P)
6508 APInt TCAP(BitWidth, TC-1);
6514 switch (BO->getOpcode()) {
6520 // saturation => 0 or -1
6568 // Add Expr to the worklist, if Expr is either an N-ary expression or a
6575 switch (Expr->getSCEVType()) {
6577 if (!isa<PHINode>(cast<SCEVUnknown>(Expr)->getValue()))
6603 // Build worklist by queuing operands of N-ary expressions and phi nodes.
6609 for (const SCEV *Op : P->operands())
6614 if (const PHINode *P = dyn_cast<PHINode>(UnknownS->getValue())) {
6617 for (auto &Op : reverse(P->operands()))
6630 if (const PHINode *P = dyn_cast<PHINode>(UnknownS->getValue()))
6642 const SCEV *S, ScalarEvolution::RangeSignHint SignHint, unsigned Depth) {
6653 return I->second;
6656 return setRange(C, SignHint, ConstantRange(C->getAPInt()));
6660 if (Depth > RangeIterThreshold)
6663 unsigned BitWidth = getTypeSizeInBits(S->getType());
6675 APInt::getMaxValue(BitWidth) - Remainder + 1);
6686 switch (S->getSCEVType()) {
6693 ConstantRange X = getRangeRef(Trunc->getOperand(), SignHint, Depth + 1);
6700 ConstantRange X = getRangeRef(ZExt->getOperand(), SignHint, Depth + 1);
6707 ConstantRange X = getRangeRef(SExt->getOperand(), SignHint, Depth + 1);
6714 ConstantRange X = getRangeRef(PtrToInt->getOperand(), SignHint, Depth + 1);
6719 ConstantRange X = getRangeRef(Add->getOperand(0), SignHint, Depth + 1);
6721 if (Add->hasNoSignedWrap())
6723 if (Add->hasNoUnsignedWrap())
6725 for (const SCEV *Op : drop_begin(Add->operands()))
6726 X = X.addWithNoWrap(getRangeRef(Op, SignHint, Depth + 1), WrapType,
6733 ConstantRange X = getRangeRef(Mul->getOperand(0), SignHint, Depth + 1);
6734 for (const SCEV *Op : drop_begin(Mul->operands()))
6735 X = X.multiply(getRangeRef(Op, SignHint, Depth + 1));
6741 ConstantRange X = getRangeRef(UDiv->getLHS(), SignHint, Depth + 1);
6742 ConstantRange Y = getRangeRef(UDiv->getRHS(), SignHint, Depth + 1);
6750 if (AddRec->hasNoUnsignedWrap()) {
6751 APInt UnsignedMinValue = getUnsignedRangeMin(AddRec->getStart());
6762 if (AddRec->hasNoSignedWrap()) {
6765 for (unsigned i = 1, e = AddRec->getNumOperands(); i != e; ++i) {
6766 if (!isKnownNonNegative(AddRec->getOperand(i)))
6768 if (!isKnownNonPositive(AddRec->getOperand(i)))
6773 ConstantRange::getNonEmpty(getSignedRangeMin(AddRec->getStart()),
6779 getSignedRangeMax(AddRec->getStart()) +
6784 // TODO: non-affine addrec
6785 if (AddRec->isAffine()) {
6787 getConstantMaxBackedgeTakenCount(AddRec->getLoop());
6789 APInt MaxBECount = cast<SCEVConstant>(MaxBEScev)->getAPInt();
6801 AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount);
6806 AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount);
6815 getSymbolicMaxBackedgeTakenCount(AddRec->getLoop());
6817 getTypeSizeInBits(MaxBEScev->getType()) <= BitWidth &&
6818 AddRec->hasNoSelfWrap()) {
6835 switch (S->getSCEVType()) {
6854 ConstantRange X = getRangeRef(NAry->getOperand(0), SignHint, Depth + 1);
6855 for (unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6857 ID, {X, getRangeRef(NAry->getOperand(i), SignHint, Depth + 1)});
6863 Value *V = U->getValue();
6886 if (U->getType()->isPointerTy()) {
6889 unsigned ptrSize = DL.getPointerTypeSizeInBits(U->getType());
6890 int ptrIdxDiff = ptrSize - BitWidth;
6892 NS -= ptrIdxDiff;
6909 ConstantRange(APInt::getSignedMinValue(BitWidth).ashr(NS - 1),
6910 APInt::getSignedMaxValue(BitWidth).ashr(NS - 1) + 1),
6913 if (U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6918 V->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed);
6927 APInt::getMaxValue(BitWidth) - APInt(BitWidth, DerefBytes);
6928 uint64_t Align = U->getValue()->getPointerAlignment(DL).value();
6930 MaxVal -= APInt(BitWidth, Rem);
6945 for (const auto &Op : Phi->operands()) {
6946 auto OpRange = getRangeRef(getSCEV(Op), SignHint, Depth + 1);
6962 if (II->getIntrinsicID() == Intrinsic::vscale) {
7004 // abs(INT_SMIN) = abs(-128) = abs(0x80) = -0x80 = 0x80 = 128.
7005 // This equations hold true due to the well-defined wrap-around behavior of
7023 APInt StartUpper = StartRange.getUpper() - 1;
7024 APInt MovedBoundary = Descending ? (StartLower - std::move(Offset))
7046 assert(getTypeSizeInBits(Start->getType()) ==
7047 getTypeSizeInBits(Step->getType()) &&
7048 getTypeSizeInBits(Start->getType()) == MaxBECount.getBitWidth() &&
7075 assert(AddRec->isAffine() && "Non-affine AddRecs are not suppored!\n");
7076 assert(AddRec->hasNoSelfWrap() &&
7077 "This only works for non-self-wrapping AddRecs!");
7079 const SCEV *Step = AddRec->getStepRecurrence(*this);
7083 // Let's make sure that we can prove that we do not self-wrap during
7088 if (getTypeSizeInBits(MaxBECount->getType()) >
7089 getTypeSizeInBits(AddRec->getType()))
7091 MaxBECount = getNoopOrZeroExtend(MaxBECount, AddRec->getType());
7092 const SCEV *RangeWidth = getMinusOne(AddRec->getType());
7103 const SCEV *End = AddRec->evaluateAtIteration(MaxBECount, *this);
7105 // We know that there is no self-wrap. Let's take Start and End values and
7117 const SCEV *Start = applyLoopGuards(AddRec->getStart(), AddRec->getLoop());
7147 assert(getTypeSizeInBits(Start->getType()) == BitWidth &&
7148 getTypeSizeInBits(Step->getType()) == BitWidth &&
7161 assert(SE.getTypeSizeInBits(S->getType()) == BitWidth &&
7168 if (SA->getNumOperands() != 2 || !isa<SCEVConstant>(SA->getOperand(0)))
7171 Offset = cast<SCEVConstant>(SA->getOperand(0))->getAPInt();
7172 S = SA->getOperand(1);
7177 CastOp = SCast->getSCEVType();
7178 S = SCast->getOperand();
7186 !match(SU->getValue(), m_Select(m_Value(Condition), m_APInt(TrueVal),
7195 // Re-apply the cast we peeled off earlier
7215 // Re-apply the constant offset we peeled off earlier
7246 const SCEV *TrueStart = this->getConstant(StartPattern.TrueValue);
7247 const SCEV *TrueStep = this->getConstant(StepPattern.TrueValue);
7248 const SCEV *FalseStart = this->getConstant(StartPattern.FalseValue);
7249 const SCEV *FalseStep = this->getConstant(StepPattern.FalseValue);
7252 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount);
7254 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount);
7265 if (BinOp->hasNoUnsignedWrap())
7267 if (BinOp->hasNoSignedWrap())
7278 return &*AddRec->getLoop()->getHeader()->begin();
7280 if (auto *I = dyn_cast<Instruction>(U->getValue()))
7313 for (const auto *Op : S->operands())
7328 if (A->getParent() == B->getParent() &&
7329 isGuaranteedToTransferExecutionToSuccessor(A->getIterator(),
7330 B->getIterator()))
7333 auto *BLoop = LI.getLoopFor(B->getParent());
7334 if (BLoop && BLoop->getHeader() == B->getParent() &&
7335 BLoop->getLoopPreheader() == A->getParent() &&
7336 isGuaranteedToTransferExecutionToSuccessor(A->getIterator(),
7337 A->getParent()->end()) &&
7338 isGuaranteedToTransferExecutionToSuccessor(B->getParent()->begin(),
7339 B->getIterator()))
7354 // is a non-zero constant, we have to assume the UDiv may be UB.
7355 return UDiv && (!isKnownNonZero(UDiv->getOperand(1)) ||
7356 !isGuaranteedNotToBePoison(UDiv->getOperand(1)));
7377 for (const Use &Op : I->operands()) {
7380 if (isSCEVable(Op->getType()))
7400 auto *ExitingBB = L->getExitingBlock();
7407 // We start by assuming \c I, the post-inc add recurrence, is poison. Only
7416 for (const Use &U : Poison->uses()) {
7419 DT.dominates(PoisonUser->getParent(), ExitingBB))
7422 if (propagatesPoison(U) && L->contains(PoisonUser))
7439 return !SI->isSimple();
7441 return I->mayThrow() || I->mayWriteToMemory();
7447 for (auto *BB : L->getBlocks())
7462 return Itr->second;
7515 if (!isSCEVable(V->getType()))
7523 if (!DT.isReachableFromEntry(I->getParent()))
7524 return getUnknown(PoisonValue::get(V->getType()));
7535 bool IsConstArg = isa<ConstantInt>(BO->RHS);
7536 switch (BO->Opcode) {
7543 if (BO->Op) {
7544 if (BO->Op != V && getExistingSCEV(BO->Op)) {
7545 Ops.push_back(BO->Op);
7549 Ops.push_back(BO->RHS);
7550 auto NewBO = MatchBinaryOp(BO->LHS, getDataLayout(), AC, DT,
7553 (BO->Opcode == Instruction::Add &&
7554 (NewBO->Opcode != Instruction::Add &&
7555 NewBO->Opcode != Instruction::Sub)) ||
7556 (BO->Opcode == Instruction::Mul &&
7557 NewBO->Opcode != Instruction::Mul)) {
7558 Ops.push_back(BO->LHS);
7563 if (BO->Op && (BO->IsNSW || BO->IsNUW)) {
7564 auto *I = dyn_cast<Instruction>(BO->Op);
7566 Ops.push_back(BO->LHS);
7586 if (!IsConstArg && !BO->LHS->getType()->isIntegerTy(1))
7596 Ops.push_back(BO->LHS);
7597 Ops.push_back(BO->RHS);
7601 switch (U->getOpcode()) {
7606 Ops.push_back(U->getOperand(0));
7610 if (isSCEVable(U->getType()) && isSCEVable(U->getOperand(0)->getType())) {
7611 Ops.push_back(U->getOperand(0));
7618 Ops.push_back(U->getOperand(0));
7619 Ops.push_back(U->getOperand(1));
7623 assert(cast<GEPOperator>(U)->getSourceElementType()->isSized() &&
7625 for (Value *Index : U->operands())
7639 if (U->getType()->isIntegerTy(1) || isa<ConstantInt>(U->getOperand(0)))
7642 auto *ICI = dyn_cast<ICmpInst>(U->getOperand(0));
7645 Value *LHS = ICI->getOperand(0);
7646 Value *RHS = ICI->getOperand(1);
7647 if (ICI->getPredicate() == CmpInst::ICMP_EQ ||
7648 ICI->getPredicate() == CmpInst::ICMP_NE) {
7649 if (!(isa<ConstantInt>(RHS) && cast<ConstantInt>(RHS)->isZero()))
7651 } else if (getTypeSizeInBits(LHS->getType()) >
7652 getTypeSizeInBits(U->getType()))
7659 for (Value *Inc : U->operands())
7666 if (Value *RV = cast<CallBase>(U)->getReturnedArgOperand()) {
7672 switch (II->getIntrinsicID()) {
7674 Ops.push_back(II->getArgOperand(0));
7682 Ops.push_back(II->getArgOperand(0));
7683 Ops.push_back(II->getArgOperand(1));
7688 Ops.push_back(II->getArgOperand(0));
7701 if (!isSCEVable(V->getType()))
7709 if (!DT.isReachableFromEntry(I->getParent()))
7710 return getUnknown(PoisonValue::get(V->getType()));
7724 switch (BO->Opcode) {
7729 // because it leads to N-1 getAddExpr calls for N ultimate operands.
7734 if (BO->Op) {
7735 if (auto *OpSCEV = getExistingSCEV(BO->Op)) {
7745 // addition - they may not apply to other additions that can be
7747 const SCEV *RHS = getSCEV(BO->RHS);
7748 SCEV::NoWrapFlags Flags = getNoWrapFlagsFromUB(BO->Op);
7750 const SCEV *LHS = getSCEV(BO->LHS);
7751 if (BO->Opcode == Instruction::Sub)
7759 if (BO->Opcode == Instruction::Sub)
7760 AddOps.push_back(getNegativeSCEV(getSCEV(BO->RHS)));
7762 AddOps.push_back(getSCEV(BO->RHS));
7764 auto NewBO = MatchBinaryOp(BO->LHS, getDataLayout(), AC, DT,
7766 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7767 NewBO->Opcode != Instruction::Sub)) {
7768 AddOps.push_back(getSCEV(BO->LHS));
7780 if (BO->Op) {
7781 if (auto *OpSCEV = getExistingSCEV(BO->Op)) {
7786 SCEV::NoWrapFlags Flags = getNoWrapFlagsFromUB(BO->Op);
7788 LHS = getSCEV(BO->LHS);
7789 RHS = getSCEV(BO->RHS);
7795 MulOps.push_back(getSCEV(BO->RHS));
7796 auto NewBO = MatchBinaryOp(BO->LHS, getDataLayout(), AC, DT,
7798 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7799 MulOps.push_back(getSCEV(BO->LHS));
7808 LHS = getSCEV(BO->LHS);
7809 RHS = getSCEV(BO->RHS);
7812 LHS = getSCEV(BO->LHS);
7813 RHS = getSCEV(BO->RHS);
7817 if (BO->Op)
7818 Flags = getNoWrapFlagsFromUB(BO->Op);
7819 LHS = getSCEV(BO->LHS);
7820 RHS = getSCEV(BO->RHS);
7826 if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->RHS)) {
7827 if (CI->isZero())
7828 return getSCEV(BO->RHS);
7829 if (CI->isMinusOne())
7830 return getSCEV(BO->LHS);
7831 const APInt &A = CI->getValue();
7834 // constants, obscuring what would otherwise be a low-bits mask.
7836 // knew about to reconstruct a low-bits mask value.
7841 computeKnownBits(BO->LHS, Known, getDataLayout(),
7845 APInt::getLowBitsSet(BitWidth, BitWidth - LZ - TZ).shl(TZ);
7848 const SCEV *LHS = getSCEV(BO->LHS);
7851 if (auto *OpC = dyn_cast<SCEVConstant>(LHSMul->getOperand(0))) {
7853 unsigned MulZeros = OpC->getAPInt().countr_zero();
7855 APInt DivAmt = APInt::getOneBitSet(BitWidth, TZ - GCD);
7857 MulOps.push_back(getConstant(OpC->getAPInt().lshr(GCD)));
7858 append_range(MulOps, LHSMul->operands().drop_front());
7859 auto *NewMul = getMulExpr(MulOps, LHSMul->getNoWrapFlags());
7868 IntegerType::get(getContext(), BitWidth - LZ - TZ)),
7869 BO->LHS->getType()),
7873 // Binary `and` is a bit-wise `umin`.
7874 if (BO->LHS->getType()->isIntegerTy(1)) {
7875 LHS = getSCEV(BO->LHS);
7876 RHS = getSCEV(BO->RHS);
7882 // Binary `or` is a bit-wise `umax`.
7883 if (BO->LHS->getType()->isIntegerTy(1)) {
7884 LHS = getSCEV(BO->LHS);
7885 RHS = getSCEV(BO->RHS);
7891 if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->RHS)) {
7892 // If the RHS of xor is -1, then this is a not operation.
7893 if (CI->isMinusOne())
7894 return getNotSCEV(getSCEV(BO->LHS));
7896 // Model xor(and(x, C), C) as and(~x, C), if C is a low-bits mask.
7897 // This is a variant of the check for xor with -1, and it handles
7898 // the case where instcombine has trimmed non-demanded bits out
7899 // of an xor with -1.
7900 if (auto *LBO = dyn_cast<BinaryOperator>(BO->LHS))
7901 if (ConstantInt *LCI = dyn_cast<ConstantInt>(LBO->getOperand(1)))
7902 if (LBO->getOpcode() == Instruction::And &&
7903 LCI->getValue() == CI->getValue())
7905 dyn_cast<SCEVZeroExtendExpr>(getSCEV(BO->LHS))) {
7906 Type *UTy = BO->LHS->getType();
7907 const SCEV *Z0 = Z->getOperand();
7908 Type *Z0Ty = Z0->getType();
7911 // If C is a low-bits mask, the zero extend is serving to
7913 // re-apply the zext.
7914 if (CI->getValue().isMask(Z0TySize))
7917 // If C is a single bit, it may be in the sign-bit position
7918 // before the zero-extend. In this case, represent the xor
7919 // using an add, which is equivalent, and re-apply the zext.
7920 APInt Trunc = CI->getValue().trunc(Z0TySize);
7921 if (Trunc.zext(getTypeSizeInBits(UTy)) == CI->getValue() &&
7931 if (ConstantInt *SA = dyn_cast<ConstantInt>(BO->RHS)) {
7932 uint32_t BitWidth = cast<IntegerType>(SA->getType())->getBitWidth();
7938 if (SA->getValue().uge(BitWidth))
7944 // left shifting by bitwidth - 1.
7946 if (BO->Op) {
7947 auto MulFlags = getNoWrapFlagsFromUB(BO->Op);
7949 ((MulFlags & SCEV::FlagNUW) || SA->getValue().ult(BitWidth - 1)))
7956 getContext(), APInt::getOneBitSet(BitWidth, SA->getZExtValue()));
7957 return getMulExpr(getSCEV(BO->LHS), getConstant(X), Flags);
7963 ConstantInt *CI = dyn_cast<ConstantInt>(BO->RHS);
7967 Type *OuterTy = BO->LHS->getType();
7973 if (CI->getValue().uge(BitWidth))
7976 if (CI->isZero())
7977 return getSCEV(BO->LHS); // shift by zero --> noop
7979 uint64_t AShrAmt = CI->getZExtValue();
7980 Type *TruncTy = IntegerType::get(getContext(), BitWidth - AShrAmt);
7982 Operator *L = dyn_cast<Operator>(BO->LHS);
7987 if (L && L->getOpcode() == Instruction::Add) {
7993 Operator *LShift = dyn_cast<Operator>(L->getOperand(0));
7994 ConstantInt *AddOperandCI = dyn_cast<ConstantInt>(L->getOperand(1));
7995 if (LShift && LShift->getOpcode() == Instruction::Shl) {
7997 const SCEV *ShlOp0SCEV = getSCEV(LShift->getOperand(0));
7998 ShlAmtCI = dyn_cast<ConstantInt>(LShift->getOperand(1));
8002 APInt AddOperand = AddOperandCI->getValue().ashr(AShrAmt);
8003 AddConstant = getConstant(AddOperand.trunc(BitWidth - AShrAmt));
8010 } else if (L && L->getOpcode() == Instruction::Shl) {
8015 const SCEV *ShlOp0SCEV = getSCEV(L->getOperand(0));
8016 ShlAmtCI = dyn_cast<ConstantInt>(L->getOperand(1));
8025 // 1) For a two-shift sext-inreg, i.e. n = m,
8028 // 2) When n > m, use sext(mul(trunc(x), 2^(n-m)))) as the SCEV
8030 // the multiplier, 1 << (ShlAmt - AShrAmt), fits into TruncTy as
8031 // ShlAmt - AShrAmt < Amt.
8032 const APInt &ShlAmt = ShlAmtCI->getValue();
8034 APInt Mul = APInt::getOneBitSet(BitWidth - AShrAmt,
8035 ShlAmtCI->getZExtValue() - AShrAmt);
8038 if (L->getOpcode() != Instruction::Shl)
8048 switch (U->getOpcode()) {
8050 return getTruncateExpr(getSCEV(U->getOperand(0)), U->getType());
8053 return getZeroExtendExpr(getSCEV(U->getOperand(0)), U->getType());
8056 if (auto BO = MatchBinaryOp(U->getOperand(0), getDataLayout(), AC, DT,
8059 // A + (-1)*B. By pushing sign extension onto its operands we are much
8063 // sext((A + B + ...)<nsw>) --> (sext(A) + sext(B) + ...)<nsw>
8065 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8066 Type *Ty = U->getType();
8067 auto *V1 = getSignExtendExpr(getSCEV(BO->LHS), Ty);
8068 auto *V2 = getSignExtendExpr(getSCEV(BO->RHS), Ty);
8072 return getSignExtendExpr(getSCEV(U->getOperand(0)), U->getType());
8075 // BitCasts are no-op casts so we just eliminate the cast.
8076 if (isSCEVable(U->getType()) && isSCEVable(U->getOperand(0)->getType()))
8077 return getSCEV(U->getOperand(0));
8081 // Pointer to integer cast is straight-forward, so do model it.
8082 const SCEV *Op = getSCEV(U->getOperand(0));
8083 Type *DstIntTy = U->getType();
8096 // If both operands are non-negative, this is just an udiv.
8097 if (isKnownNonNegative(getSCEV(U->getOperand(0))) &&
8098 isKnownNonNegative(getSCEV(U->getOperand(1))))
8099 return getUDivExpr(getSCEV(U->getOperand(0)), getSCEV(U->getOperand(1)));
8103 // If both operands are non-negative, this is just an urem.
8104 if (isKnownNonNegative(getSCEV(U->getOperand(0))) &&
8105 isKnownNonNegative(getSCEV(U->getOperand(1))))
8106 return getURemExpr(getSCEV(U->getOperand(0)), getSCEV(U->getOperand(1)));
8116 return createNodeForSelectOrPHI(U, U->getOperand(0), U->getOperand(1),
8117 U->getOperand(2));
8121 if (Value *RV = cast<CallBase>(U)->getReturnedArgOperand())
8125 switch (II->getIntrinsicID()) {
8128 getSCEV(II->getArgOperand(0)),
8129 /*IsNSW=*/cast<ConstantInt>(II->getArgOperand(1))->isOne());
8131 LHS = getSCEV(II->getArgOperand(0));
8132 RHS = getSCEV(II->getArgOperand(1));
8135 LHS = getSCEV(II->getArgOperand(0));
8136 RHS = getSCEV(II->getArgOperand(1));
8139 LHS = getSCEV(II->getArgOperand(0));
8140 RHS = getSCEV(II->getArgOperand(1));
8143 LHS = getSCEV(II->getArgOperand(0));
8144 RHS = getSCEV(II->getArgOperand(1));
8147 const SCEV *X = getSCEV(II->getArgOperand(0));
8148 const SCEV *Y = getSCEV(II->getArgOperand(1));
8153 const SCEV *X = getSCEV(II->getArgOperand(0));
8154 const SCEV *Y = getSCEV(II->getArgOperand(1));
8163 return getSCEV(II->getArgOperand(0));
8165 return getVScale(II->getType());
8176 //===----------------------------------------------------------------------===//
8184 auto *ExitCountType = ExitCount->getType();
8185 assert(ExitCountType->isIntegerTy());
8186 auto *EvalTy = Type::getIntNTy(ExitCountType->getContext(),
8187 1 + ExitCountType->getScalarSizeInBits());
8197 unsigned ExitCountSize = getTypeSizeInBits(ExitCount->getType());
8198 unsigned EvalSize = EvalTy->getPrimitiveSizeInBits();
8207 getMinusOne(ExitCount->getType()));
8215 getAddExpr(ExitCount, getOne(ExitCount->getType())), EvalTy);
8225 ConstantInt *ExitConst = ExitCount->getValue();
8228 if (ExitConst->getValue().getActiveBits() > 32)
8232 return ((unsigned)ExitConst->getZExtValue()) + 1;
8243 assert(ExitingBlock && "Must pass a non-null exiting block!");
8244 assert(L->isLoopExiting(ExitingBlock) &&
8262 L->getExitingBlocks(ExitingBlocks);
8305 assert(ExitingBlock && "Must pass a non-null exiting block!");
8306 assert(L->isLoopExiting(ExitingBlock) &&
8379 BasicBlock *Header = L->getHeader();
8381 // Push all Loop-header PHIs onto the Worklist stack.
8382 for (PHINode &PN : Header->phis())
8396 return Pair.first->second;
8401 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8407 // succeeds, proceed to actually compute a backedge-taken count and
8410 // backedge-taken count, which could result in infinite recursion.
8414 return Pair.first->second;
8431 append_range(ToForget, LoopUsersIt->second);
8434 // Invalidate constant-evolved loop header phis.
8435 for (PHINode &PN : L->getHeader()->phis())
8439 // Re-lookup the insert position, since the call to
8444 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8450 // - The trip counts of all loops have changed arbitrarily
8451 // - Every llvm::Value has been updated in place to produce a different
8478 if (!isSCEVable(I->getType()) && !isa<WithOverflowInst>(I))
8484 eraseValueFromMap(It->first);
8485 ToForget.push_back(It->second);
8500 // Iterate over all the loops and sub-loops to drop SCEV information.
8511 std::pair<const SCEV *, const Loop *> Entry = I->first;
8520 ToForget.insert(ToForget.end(), LoopUsersItr->second.begin(),
8521 LoopUsersItr->second.end());
8524 // Drop information about expressions based on loop-header PHIs.
8531 LoopWorklist.append(CurrL->begin(), CurrL->end());
8537 forgetLoop(L->getOutermostLoop());
8544 // Drop information about expressions based on loop-header PHIs.
8556 if (!isSCEVable(V->getType()))
8572 if (auto *I = dyn_cast<Instruction>(SU->getValue()))
8573 if (L->contains(I))
8576 if (L->contains(AddRec->getLoop()))
8604 if (!isSCEVable(V->getType()))
8613 // loop-invariant, if S changes to loop invariant), so also invalidate
8625 for (const auto *User : Users->second)
8642 return SE->getCouldNotCompute();
8644 const BasicBlock *Latch = L->getLoopLatch();
8647 return SE->getCouldNotCompute();
8654 assert(BECount != SE->getCouldNotCompute() && "Bad exit SCEV!");
8655 assert(SE->DT.dominates(ENT.ExitingBlock, Latch) &&
8671 return SE->getUMinFromMismatchedTypes(Ops, /* Sequential */ true);
8691 /// getConstantMax - Get the constant max backedge taken count for the loop.
8696 return SE->getCouldNotCompute();
8701 return SE->getCouldNotCompute();
8707 "No point in having a non-constant max backedge taken count!");
8724 assert(SE->DT.dominates(ENT.ExitingBlock, L->getLoopLatch()) &&
8736 SymbolicMax = SE->getCouldNotCompute();
8739 SE->getUMinFromMismatchedTypes(ExitCounts, /*Sequential*/ true);
8764 if (ConstantMaxNotTaken->isZero()) {
8765 this->ExactNotTaken = E = ConstantMaxNotTaken;
8766 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8780 "No point in having a non-constant max backedge taken count!");
8790 assert((isa<SCEVCouldNotCompute>(E) || !E->getType()->isPointerTy()) &&
8793 !ConstantMaxNotTaken->getType()->isPointerTy()) &&
8805 /// Allocate memory for BackedgeTakenInfo and copy the not-taken count of each
8825 "No point in having a non-constant max backedge taken count!");
8833 L->getExitingBlocks(ExitingBlocks);
8839 BasicBlock *Latch = L->getLoopLatch(); // may be NULL.
8852 if (auto *BI = dyn_cast<BranchInst>(ExitBB->getTerminator()))
8853 if (auto *CI = dyn_cast<ConstantInt>(BI->getCondition())) {
8854 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
8855 if (ExitIfTrue == CI->isZero())
8883 // non-exiting iterations. Partition the loop exits into two kinds:
8918 // We only care about non-constant SCEVs here, so we can ignore
8935 assert(L->contains(ExitingBlock) && "Exit count for non-loop block?");
8938 const BasicBlock *Latch = L->getLoopLatch();
8942 Instruction *Term = ExitingBlock->getTerminator();
8944 assert(BI->isConditional() && "If unconditional, it can't be in loop!");
8945 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
8946 assert(ExitIfTrue == L->contains(BI->getSuccessor(1)) &&
8949 return computeExitLimitFromCond(L, BI->getCondition(), ExitIfTrue,
8958 if (!L->contains(SBB)) {
8983 (void)this->L;
8984 (void)this->ExitIfTrue;
8985 (void)this->AllowPredicates;
8987 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
8988 this->AllowPredicates == AllowPredicates &&
8993 return Itr->second;
9001 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9002 this->AllowPredicates == AllowPredicates &&
9033 // With an icmp, it may be feasible to compute an exact backedge-taken count.
9052 if (ExitIfTrue == !CI->getZExtValue())
9056 return getZero(CI->getType());
9065 match(WO->getRHS(), m_APInt(C))) {
9067 ConstantRange::makeExactNoWrapRegion(WO->getBinaryOp(), *C,
9068 WO->getNoWrapKind());
9074 auto *LHS = getSCEV(WO->getLHS());
9113 const Constant *NeutralElement = ConstantInt::get(ExitCond->getType(), IsAnd);
9174 Pred = ExitCond->getCmpPredicate();
9176 Pred = ExitCond->getInverseCmpPredicate();
9179 const SCEV *LHS = getSCEV(ExitCond->getOperand(0));
9180 const SCEV *RHS = getSCEV(ExitCond->getOperand(1));
9193 return computeShiftCompareExitLimit(ExitCond->getOperand(0),
9194 ExitCond->getOperand(1), L, OriginalPred);
9207 // If there is a loop-invariant, force it into the RHS.
9215 (void)SimplifyICmpOperands(Pred, LHS, RHS, /*Depth=*/0);
9221 if (AddRec->getLoop() == L) {
9224 ConstantRange::makeExactICmpRegion(Pred, RHSC->getAPInt());
9226 const SCEV *Ret = AddRec->getNumIterationsInRange(CompRange, *this);
9235 // on self-wrap of the IV, then we can infer that IV doesn't self wrap
9241 InnerLHS = ZExt->getOperand();
9243 AR && !AR->hasNoSelfWrap() && AR->getLoop() == L && AR->isAffine() &&
9244 isKnownToBeAPowerOfTwo(AR->getStepRecurrence(*this), /*OrZero=*/true,
9246 auto Flags = AR->getNoWrapFlags();
9248 SmallVector<const SCEV *> Operands{AR->operands()};
9254 // From no-self-wrap, this follows trivially from the fact that every
9255 // (un)signed-wrapped, but not self-wrapped value must be LT than the
9261 AR && AR->getLoop() == L && AR->isAffine() &&
9262 !AR->getNoWrapFlags(WrapType) && AR->hasNoSelfWrap() &&
9263 isKnownPositive(AR->getStepRecurrence(*this))) {
9264 auto Flags = AR->getNoWrapFlags();
9266 SmallVector<const SCEV*> Operands{AR->operands()};
9275 // Convert to: while (X-Y != 0)
9276 if (LHS->getType()->isPointerTy()) {
9281 if (RHS->getType()->isPointerTy()) {
9293 // Convert to: while (X-Y == 0)
9294 if (LHS->getType()->isPointerTy()) {
9299 if (RHS->getType()->isPointerTy()) {
9317 auto *OldType = dyn_cast<IntegerType>(LHS->getType());
9323 Type::getIntNTy(OldType->getContext(), OldType->getBitWidth() * 2);
9332 RHS = getAddExpr(getOne(RHS->getType()), RHS);
9350 RHS = getAddExpr(getMinusOne(RHS->getType()), RHS);
9373 assert(!L->contains(ExitingBlock) && "Not an exiting block!");
9376 if (Switch->getDefaultDest() == ExitingBlock)
9379 assert(L->contains(Switch->getDefaultDest()) &&
9381 const SCEV *LHS = getSCEVAtScope(Switch->getCondition(), L);
9382 const SCEV *RHS = getConstant(Switch->findCaseDest(ExitingBlock));
9384 // while (X != Y) --> while (X-Y != 0)
9396 const SCEV *Val = AddRec->evaluateAtIteration(InVal, SE);
9399 return cast<SCEVConstant>(Val)->getValue();
9408 const BasicBlock *Latch = L->getLoopLatch();
9412 const BasicBlock *Predecessor = L->getLoopPredecessor();
9433 return ShiftAmt->getValue().isStrictlyPositive();
9459 // really care about it being the same *kind* of shift instruction --
9468 if (!PNOut || PNOut->getParent() != L->getHeader())
9471 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9495 // recurrences, the value of the recurrence "stabilizes" to either 0 or -1
9507 // {K,ashr,<positive-constant>} stabilizes to signum(K) in at most
9509 Value *FirstValue = PN->getIncomingValueForBlock(Predecessor);
9511 Predecessor->getTerminator(), &DT);
9512 auto *Ty = cast<IntegerType>(RHS->getType());
9516 StableValue = ConstantInt::get(Ty, -1, true);
9524 // Both {K,lshr,<positive-constant>} and {K,shl,<positive-constant>}
9526 StableValue = ConstantInt::get(cast<IntegerType>(RHS->getType()), 0);
9532 assert(Result->getType()->isIntegerTy(1) &&
9535 if (Result->isZeroValue()) {
9536 unsigned BitWidth = getTypeSizeInBits(RHS->getType());
9538 getConstant(getEffectiveSCEVType(RHS->getType()), BitWidth);
9554 if (const Function *F = CI->getCalledFunction())
9563 if (!L->contains(I)) return false;
9568 return L->getHeader() == I->getParent();
9576 /// getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by
9581 unsigned Depth) {
9582 if (Depth > MaxConstantEvolvingDepth)
9588 for (Value *Op : UseInst->operands()) {
9603 P = getConstantEvolvingPHIOperands(OpInst, L, PHIMap, Depth + 1);
9616 /// getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node
9628 // Record non-constant instructions contained by the loop.
9633 /// EvaluateExpression - Given an expression that passes the
9657 std::vector<Constant*> Operands(I->getNumOperands());
9659 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
9660 Instruction *Operand = dyn_cast<Instruction>(I->getOperand(i));
9662 Operands[i] = dyn_cast<Constant>(I->getOperand(i));
9682 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
9683 if (PN->getIncomingBlock(i) == BB)
9686 auto *CurrentVal = dyn_cast<Constant>(PN->getIncomingValue(i));
9700 /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
9710 return I->second;
9715 Constant *&RetVal = I->second;
9718 BasicBlock *Header = L->getHeader();
9719 assert(PN->getParent() == Header && "Can't evaluate PHI not in loop header!");
9721 BasicBlock *Latch = L->getLoopLatch();
9725 for (PHINode &PHI : Header->phis()) {
9732 Value *BEValue = PN->getIncomingValueForBlock(Latch);
9746 // EvaluateExpression adds non-phi values to the CurrentIterVals map.
9762 if (!PHI || PHI == PN || PHI->getParent() != Header) continue;
9771 Value *BEValue = PHI->getIncomingValueForBlock(Latch);
9795 if (PN->getNumIncomingValues() != 2) return getCouldNotCompute();
9798 BasicBlock *Header = L->getHeader();
9799 assert(PN->getParent() == Header && "Can't evaluate PHI not in loop header!");
9801 BasicBlock *Latch = L->getLoopLatch();
9804 for (PHINode &PHI : Header->phis()) {
9823 if (CondVal->getValue() == uint64_t(ExitWhen)) {
9837 if (!PHI || PHI->getParent() != Header) continue;
9844 Value *BEValue = PHI->getIncomingValueForBlock(Latch);
9881 switch (V->getSCEVType()) {
9887 return cast<SCEVConstant>(V)->getValue();
9889 return dyn_cast<Constant>(cast<SCEVUnknown>(V)->getValue());
9892 if (Constant *CastOp = BuildConstantFromSCEV(P2I->getOperand()))
9893 return ConstantExpr::getPtrToInt(CastOp, P2I->getType());
9899 if (Constant *CastOp = BuildConstantFromSCEV(ST->getOperand()))
9900 return ConstantExpr::getTrunc(CastOp, ST->getType());
9906 for (const SCEV *Op : SA->operands()) {
9914 assert(!C->getType()->isPointerTy() &&
9916 if (OpC->getType()->isPointerTy()) {
9919 C = ConstantExpr::getGetElementPtr(Type::getInt8Ty(C->getContext()),
9944 switch (S->getSCEVType()) {
9949 return getCastExpr(S->getSCEVType(), NewOps[0], S->getType());
9952 return getAddRecExpr(NewOps, AddRec->getLoop(), AddRec->getNoWrapFlags());
9955 return getAddExpr(NewOps, cast<SCEVAddExpr>(S)->getNoWrapFlags());
9957 return getMulExpr(NewOps, cast<SCEVMulExpr>(S)->getNoWrapFlags());
9964 return getMinMaxExpr(S->getSCEVType(), NewOps);
9966 return getSequentialMinMaxExpr(S->getSCEVType(), NewOps);
9978 switch (V->getSCEVType()) {
9987 // Avoid performing the look-up in the common case where the specified
9988 // expression has no loop-variant portions.
9989 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
9990 const SCEV *OpAtScope = getSCEVAtScope(AddRec->getOperand(i), L);
9991 if (OpAtScope == AddRec->getOperand(i))
9997 NewOps.reserve(AddRec->getNumOperands());
9998 append_range(NewOps, AddRec->operands().take_front(i));
10001 NewOps.push_back(getSCEVAtScope(AddRec->getOperand(i), L));
10004 NewOps, AddRec->getLoop(), AddRec->getNoWrapFlags(SCEV::FlagNW));
10016 if (!AddRec->getLoop()->contains(L)) {
10019 const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
10024 return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
10041 ArrayRef<const SCEV *> Ops = V->operands();
10042 // Avoid performing the look-up in the common case where the specified
10043 // expression has no loop-variant portions.
10066 // If this instruction is evolved from a constant-evolving PHI, compute the
10069 Instruction *I = dyn_cast<Instruction>(SU->getValue());
10074 const Loop *CurrLoop = this->LI[I->getParent()];
10076 if (CurrLoop && CurrLoop->getParentLoop() == L &&
10077 PN->getParent() == CurrLoop->getHeader()) {
10079 // to see if the loop that contains it has a known backedge-taken
10085 if (BackedgeTakenCount->isZero()) {
10088 for (unsigned i = 0; i < PN->getNumIncomingValues(); i++) {
10089 if (!CurrLoop->contains(PN->getIncomingBlock(i))) {
10091 InitValue = PN->getIncomingValue(i);
10092 else if (InitValue != PN->getIncomingValue(i)) {
10105 PN->getNumIncomingValues() == 2) {
10108 CurrLoop->contains(PN->getIncomingBlock(0)) ? 0 : 1;
10109 Value *BackedgeVal = PN->getIncomingValue(InLoopPred);
10110 if (CurrLoop->isLoopInvariant(BackedgeVal))
10118 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10133 Operands.reserve(I->getNumOperands());
10135 for (Value *Op : I->operands()) {
10141 // If any of the operands is non-constant and if they are
10142 // non-integer and non-pointer, don't even try to analyze them
10144 if (!isSCEVable(Op->getType()))
10154 assert(C->getType() == Op->getType() && "Type mismatch");
10182 return stripInjectiveFunctions(ZExt->getOperand());
10184 return stripInjectiveFunctions(SExt->getOperand());
10202 assert(BW == SE.getTypeSizeInBits(B->getType()));
10203 assert(A != 0 && "A must be non-zero.");
10220 const SCEV *Zero = SE.getZero(B->getType());
10229 Predicates->push_back(SE.getEqualPredicate(URem, Zero));
10239 APInt AD = A.lshr(Mult2).trunc(BW - Mult2); // AD = A / D
10258 /// compile- time constants.
10261 assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!");
10262 const SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
10263 const SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
10264 const SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
10274 APInt L = LC->getAPInt();
10275 APInt M = MC->getAPInt();
10276 APInt N = NC->getAPInt();
10279 unsigned BitWidth = LC->getAPInt().getBitWidth();
10283 // The sign-extension (as opposed to a zero-extension) here matches the
10292 // After n iterations the accumulated value Acc is L + nM + n(n-1)/2 N.
10295 // L + nM + n(n-1)/2 N = 0, or 2L + 2M n + n(n-1) N = 0.
10297 // N n^2 + (2M-N) n + 2L = 0.
10300 APInt B = 2 * M - A;
10316 unsigned W = std::max(X->getBitWidth(), Y->getBitWidth());
10317 APInt XW = X->sext(W);
10318 APInt YW = Y->sext(W);
10327 /// When solving addrec-related equations, it is preferable to return a value
10341 unsigned W = X->getBitWidth();
10342 if (BitWidth > 1 && BitWidth < W && X->isIntN(BitWidth))
10343 return X->trunc(BitWidth);
10352 /// If the calculated value is a BW-bit integer (for BW > 1), it will be
10378 if (!V->isZero())
10388 /// while c(n-1) does.
10397 assert(AddRec->getOperand(0)->isZero() &&
10403 assert(Range.contains(APInt(SE.getTypeSizeInBits(AddRec->getType()), 0)) &&
10421 [&](APInt Bound) -> std::pair<std::optional<APInt>, bool> {
10432 SO = APIntOps::SolveQuadraticEquationWrap(A, B, -Bound, BitWidth);
10437 APIntOps::SolveQuadraticEquationWrap(A, B, -Bound, BitWidth + 1);
10442 if (Range.contains(V0->getValue()))
10444 // X should be at least 1, so X-1 is non-negative.
10445 ConstantInt *C1 = ConstantInt::get(SE.getContext(), X-1);
10447 if (Range.contains(V1->getValue()))
10473 APInt Lower = Range.getLower().sext(A.getBitWidth()) - 1;
10529 // is now expressed as a single expression, V = x-y. So the exit test is
10537 if (C->getValue()->isZero()) return C;
10550 if (!AddRec || AddRec->getLoop() != L)
10553 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of
10555 if (AddRec->isQuadratic() && AddRec->getType()->isIntegerTy()) {
10567 if (!AddRec->isAffine())
10577 // Step*N = -Start (mod 2^BW)
10582 const SCEV *Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
10583 const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop());
10593 // N = -Start/Step (as unsigned)
10595 // N = Start/-Step
10603 // 1*N = -Start; -1*N = Start (mod 2^BW), so:
10611 // we end up with a loop whose backedge-taken count is n - 1. Detect this
10615 // isn't context-sensitive; it doesn't know that we only care about the
10617 const SCEV *Zero = getZero(Distance->getType());
10618 const SCEV *One = getOne(Distance->getType());
10622 // as "unsigned_max(Distance + 1) - 1".
10624 MaxBECount = APIntOps::umin(MaxBECount, CR.getUnsignedMax() - 1);
10631 // is true) and the addition is no-wrap we can use unsigned divide to
10635 if (ControlsOnlyExit && AddRec->hasNoSelfWrap() &&
10636 loopHasNoAbnormalExits(AddRec->getLoop())) {
10659 if (!StepC || StepC->getValue()->isZero())
10662 StepC->getAPInt(), getNegativeSCEV(Start),
10680 // If the value is a constant, check to see if it is known to be non-zero
10683 if (!C->getValue()->isZero())
10684 return getZero(C->getType());
10699 if (const BasicBlock *Pred = BB->getSinglePredecessor())
10706 return {L->getLoopPredecessor(), L->getHeader()};
10714 /// front-end may have replicated the controlling expression.
10723 return A->isIdenticalTo(B) && (isa<BinaryOperator>(A) || isa<GetElementPtrInst>(A));
10730 if (const Instruction *AI = dyn_cast<Instruction>(AU->getValue()))
10731 if (const Instruction *BI = dyn_cast<Instruction>(BU->getValue()))
10741 if (!Add || Add->getNumOperands() != 2)
10743 if (auto *ME = dyn_cast<SCEVMulExpr>(Add->getOperand(0));
10744 ME && ME->getNumOperands() == 2 && ME->getOperand(0)->isAllOnesValue()) {
10745 LHS = Add->getOperand(1);
10746 RHS = ME->getOperand(1);
10749 if (auto *ME = dyn_cast<SCEVMulExpr>(Add->getOperand(1));
10750 ME && ME->getNumOperands() == 2 && ME->getOperand(0)->isAllOnesValue()) {
10751 LHS = Add->getOperand(0);
10752 RHS = ME->getOperand(1);
10759 const SCEV *&RHS, unsigned Depth) {
10769 if (Depth >= 3)
10776 if (!ICmpInst::compare(LHSC->getAPInt(), RHSC->getAPInt(), Pred))
10786 // If we're comparing an addrec with a value which is loop-invariant in the
10788 // as both operands could be addrecs loop-invariant in each other's loop.
10790 const Loop *L = AR->getLoop();
10791 if (isLoopInvariant(LHS, L) && properlyDominates(LHS, L->getHeader())) {
10799 // cases, and canonicalize *-or-equal comparisons to regular comparisons.
10801 const APInt &RA = RC->getAPInt();
10829 // Fold ((-1) * %a) + %b == 0 (equivalent to %b-%a == 0) into %a == %b.
10842 RHS = getConstant(RA - 1);
10854 RHS = getConstant(RA - 1);
10880 RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS,
10885 LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS,
10893 RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS,
10898 LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS,
10906 RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS,
10911 LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS);
10918 RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS);
10922 LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS,
10937 return SimplifyICmpOperands(Pred, LHS, RHS, Depth + 1);
10962 return isKnownNonZero(SExt->getOperand(0));
10970 return C->getAPInt().isPowerOf2() ||
10971 (OrNegative && C->getAPInt().isNegatedPowerOf2());
10973 // The vscale_range indicates vscale is a power-of-two.
10983 return all_of(Mul->operands(), NonRecursive) && (OrZero || isKnownNonZero(S));
11012 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11013 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11019 return DT.properlyDominates(L1->getHeader(), L2->getHeader());
11024 // if LHS contains unknown non-invariant SCEV then bail out.
11030 // if RHS contains unknown non-invariant SCEV then bail out.
11078 isBasicBlockEntryGuardedByCond(CtxI->getParent(), Pred, LHS, RHS);
11088 if (isBasicBlockEntryGuardedByCond(CtxI->getParent(), Pred, LHS, RHS))
11091 CtxI->getParent(), ICmpInst::getInverseCmpPredicate(Pred), LHS, RHS))
11099 const Loop *L = LHS->getLoop();
11100 return isLoopEntryGuardedByCond(L, Pred, LHS->getStart(), RHS) &&
11101 isLoopBackedgeGuardedByCond(L, Pred, LHS->getPostIncExpr(*this), RHS);
11147 if (!LHS->hasNoUnsignedWrap())
11153 if (!LHS->hasNoSignedWrap())
11156 const SCEV *Step = LHS->getStepRecurrence(*this);
11172 // If there is a loop-invariant, force it into the RHS, otherwise bail out.
11182 if (!ArLHS || ArLHS->getLoop() != L)
11209 return ScalarEvolution::LoopInvariantPredicate(Pred, ArLHS->getStart(),
11221 assert(ArLHS->hasNoUnsignedWrap() && "Is a requirement of monotonicity!");
11225 // - Positive step; (TODO: lift this limitation)
11226 // - nuw - does not cross zero boundary;
11227 // - nsw - does not cross SINT_MAX boundary;
11234 // - ArLHS is always negative. It means that ArLHS <u RHS is always false;
11235 // - ArLHS is always non-negative. Because of (3) RHS is also non-negative.
11241 if (ArLHS->hasNoSignedWrap() && ArLHS->isAffine() &&
11242 isKnownPositive(ArLHS->getStepRecurrence(*this)) &&
11245 return ScalarEvolution::LoopInvariantPredicate(Pred, ArLHS->getStart(),
11266 for (auto *Op : UMin->operands())
11278 // - The predicate is monotonic in the iteration space.
11279 // - If the check does not fail on the 1st iteration:
11280 // - No overflow will happen during first MaxIter iterations;
11281 // - It will not fail on the MaxIter'th iteration.
11285 // If there is a loop-invariant, force it into the RHS, otherwise bail out.
11295 if (!AR || AR->getLoop() != L)
11302 // TODO: Support steps other than +/- 1.
11303 const SCEV *Step = AR->getStepRecurrence(*this);
11304 auto *One = getOne(Step->getType());
11312 if (AR->getType() != MaxIter->getType())
11316 const SCEV *Last = AR->evaluateAtIteration(MaxIter, *this);
11320 // Because step is +/- 1 and MaxIter has same type as Start (i.e. it does
11324 // Start <= Last for step = 1 or Start >= Last for step = -1.
11329 const SCEV *Start = AR->getStart();
11396 XConstOp = getZero(X->getType());
11405 YConstOp = getZero(Y->getType());
11417 OutC1 = cast<SCEVConstant>(XConstOp)->getAPInt();
11418 OutC2 = cast<SCEVConstant>(YConstOp)->getAPInt();
11491 isKnownPredicate(CmpInst::ICMP_SGE, LHS, getZero(LHS->getType())) &&
11511 /// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is
11521 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11525 assert(!verifyFunction(*L->getHeader()->getParent(), &dbgs()) &&
11532 BasicBlock *Latch = L->getLoopLatch();
11537 dyn_cast<BranchInst>(Latch->getTerminator());
11538 if (LoopContinuePredicate && LoopContinuePredicate->isConditional() &&
11540 LoopContinuePredicate->getCondition(),
11541 LoopContinuePredicate->getSuccessor(0) != L->getHeader()))
11545 // -- that can lead to O(n!) time complexity.
11558 Type *Ty = LatchBECount->getType();
11572 if (!DT.dominates(CI, Latch->getTerminator()))
11575 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0), false))
11582 for (DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11583 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11586 BasicBlock *BB = DTN->getBlock();
11590 BasicBlock *PBB = BB->getSinglePredecessor();
11594 BranchInst *ContinuePredicate = dyn_cast<BranchInst>(PBB->getTerminator());
11595 if (!ContinuePredicate || !ContinuePredicate->isConditional())
11598 Value *Condition = ContinuePredicate->getCondition();
11612 BB != ContinuePredicate->getSuccessor(0)))
11628 assert(!verifyFunction(*BB->getParent(), &dbgs()) &&
11633 // non-strict comparison is known from ranges and non-equality is known from
11635 // to prove non-equality and non-strict comparison separately.
11641 auto SplitAndProve = [&](std::function<bool(CmpPredicate)> Fn) -> bool {
11661 const Instruction *CtxI = &BB->front();
11679 if (ContainingLoop && ContainingLoop->getHeader() == BB)
11680 PredBB = ContainingLoop->getLoopPredecessor();
11682 PredBB = BB->getSinglePredecessor();
11686 dyn_cast<BranchInst>(Pair.first->getTerminator());
11687 if (!BlockEntryPredicate || BlockEntryPredicate->isUnconditional())
11690 if (ProveViaCond(BlockEntryPredicate->getCondition(),
11691 BlockEntryPredicate->getSuccessor(0) != Pair.second))
11703 if (ProveViaCond(CI->getArgOperand(0), false))
11711 for (const auto *GU : GuardDecl->users())
11713 if (Guard->getFunction() == BB->getParent() && DT.dominates(Guard, BB))
11714 if (ProveViaCond(Guard->getArgOperand(0), false))
11736 return isBasicBlockEntryGuardedByCond(L->getHeader(), Pred, LHS, RHS);
11745 ConstantInt::getBool(FoundCondValue->getContext(), Inverse))
11773 FoundPred = ICI->getInverseCmpPredicate();
11775 FoundPred = ICI->getCmpPredicate();
11777 const SCEV *FoundLHS = getSCEV(ICI->getOperand(0));
11778 const SCEV *FoundRHS = getSCEV(ICI->getOperand(1));
11788 if (getTypeSizeInBits(LHS->getType()) <
11789 getTypeSizeInBits(FoundLHS->getType())) {
11793 if (!CmpInst::isSigned(FoundPred) && !FoundLHS->getType()->isPointerTy() &&
11794 !FoundRHS->getType()->isPointerTy()) {
11795 auto *NarrowType = LHS->getType();
11796 auto *WideType = FoundLHS->getType();
11812 if (LHS->getType()->isPointerTy() || RHS->getType()->isPointerTy())
11815 LHS = getSignExtendExpr(LHS, FoundLHS->getType());
11816 RHS = getSignExtendExpr(RHS, FoundLHS->getType());
11818 LHS = getZeroExtendExpr(LHS, FoundLHS->getType());
11819 RHS = getZeroExtendExpr(RHS, FoundLHS->getType());
11821 } else if (getTypeSizeInBits(LHS->getType()) >
11822 getTypeSizeInBits(FoundLHS->getType())) {
11823 if (FoundLHS->getType()->isPointerTy() || FoundRHS->getType()->isPointerTy())
11826 FoundLHS = getSignExtendExpr(FoundLHS, LHS->getType());
11827 FoundRHS = getSignExtendExpr(FoundRHS, LHS->getType());
11829 FoundLHS = getZeroExtendExpr(FoundLHS, LHS->getType());
11830 FoundRHS = getZeroExtendExpr(FoundRHS, LHS->getType());
11840 assert(getTypeSizeInBits(LHS->getType()) ==
11841 getTypeSizeInBits(FoundLHS->getType()) &&
11874 // 0. LHS Pred RHS <- FoundLHS SwapPred FoundRHS
11876 // 1. LHS Pred RHS <- FoundRHS Pred FoundLHS
11877 // 2. RHS SwapPred LHS <- FoundLHS SwapPred FoundRHS
11878 // 3. LHS Pred RHS <- ~FoundLHS Pred ~FoundRHS
11879 // 4. ~LHS SwapPred ~RHS <- FoundLHS SwapPred FoundRHS
11891 if (!LHS->getType()->isPointerTy() && !RHS->getType()->isPointerTy() &&
11896 if (!FoundLHS->getType()->isPointerTy() &&
11897 !FoundRHS->getType()->isPointerTy() &&
11913 // operands are non-negative or negative.
11935 // x <u y && y >=s 0 --> x <s y.
11942 // x <s y && y <s 0 --> x <u y.
11972 if (Min == C->getAPInt()) {
11974 // This is true even if (Min + 1) wraps around -- in case of
12047 if (!AE || AE->getNumOperands() != 2)
12050 L = AE->getOperand(0);
12051 R = AE->getOperand(1);
12052 Flags = AE->getNoWrapFlags();
12061 unsigned BW = getTypeSizeInBits(More->getType());
12065 // the number of allowed simplifications to keep compile-time low.
12075 if (LAR->getLoop() != MAR->getLoop())
12080 if (!LAR->isAffine() || !MAR->isAffine())
12083 if (LAR->getStepRecurrence(*this) != MAR->getStepRecurrence(*this))
12086 Less = LAR->getStart();
12087 More = MAR->getStart();
12093 [](const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12095 if (!M || M->getNumOperands() != 2 ||
12096 !isa<SCEVConstant>(M->getOperand(0)))
12099 {M->getOperand(1), cast<SCEVConstant>(M->getOperand(0))->getAPInt()}};
12103 if (MatchedMore->second == MatchedLess->second) {
12104 More = MatchedMore->first;
12105 Less = MatchedLess->first;
12106 DiffMul *= MatchedMore->second;
12117 Diff += C->getAPInt() * DiffMul;
12119 assert(Mul == -1);
12120 Diff -= C->getAPInt() * DiffMul;
12127 for (const SCEV *Op : S->operands())
12133 Decompose(Less, -1);
12135 // Check whether all the non-constants cancel out, or reduce to new
12145 } else if (Mul == -1) {
12191 const BasicBlock *ContextBB = CtxI->getParent();
12194 const Loop *L = AR->getLoop();
12197 if (!L->contains(ContextBB) || !DT.dominates(ContextBB, L->getLoopLatch()))
12199 if (!isAvailableAtLoopEntry(FoundRHS, AR->getLoop()))
12201 return isImpliedCondOperands(Pred, LHS, RHS, AR->getStart(), FoundRHS);
12205 const Loop *L = AR->getLoop();
12208 if (!L->contains(ContextBB) || !DT.dominates(ContextBB, L->getLoopLatch()))
12210 if (!isAvailableAtLoopEntry(FoundLHS, AR->getLoop()))
12212 return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, AR->getStart());
12238 const Loop *L = AddRecFoundLHS->getLoop();
12239 if (L != AddRecLHS->getLoop())
12242 // FoundLHS u< FoundRHS u< -C => (FoundLHS + C) u< (FoundRHS + C) ... (1)
12244 // FoundLHS s< FoundRHS s< INT_MIN - C => (FoundLHS + C) s< (FoundRHS + C)
12253 // FoundLHS s< FoundRHS s< INT_MIN - C
12254 // <=> (FoundLHS + INT_MIN) u< (FoundRHS + INT_MIN) u< -C [ using (3) ]
12267 // Despite (2), "FoundRHS s< INT_MIN - C" does not mean that "FoundRHS + C"
12268 // will not sign underflow. For instance, say FoundLHS = (i8 -128), FoundRHS
12269 // = (i8 -127) and C = (i8 -100). Then INT_MIN - C = (i8 -28), and FoundRHS
12270 // s< (INT_MIN - C). Lack of sign overflow / underflow in "FoundRHS + C" is
12281 if (LDiff->isMinValue())
12287 FoundRHSLimit = -(*RDiff);
12290 FoundRHSLimit = APInt::getSignedMinValue(getTypeSizeInBits(RHS->getType())) - *RDiff;
12301 const SCEV *FoundRHS, unsigned Depth) {
12319 if (auto *Phi = dyn_cast<PHINode>(LU->getValue())) {
12325 if (auto *Phi = dyn_cast<PHINode>(RU->getValue())) {
12352 const BasicBlock *LBB = LPhi->getParent();
12358 isImpliedViaOperations(Pred, S1, S2, FoundLHS, FoundRHS, Depth);
12361 if (RPhi && RPhi->getParent() == LBB) {
12367 const SCEV *L = getSCEV(LPhi->getIncomingValueForBlock(IncBB));
12368 const SCEV *R = getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12372 } else if (RAR && RAR->getLoop()->getHeader() == LBB) {
12378 if (LPhi->getNumIncomingValues() != 2) return false;
12380 auto *RLoop = RAR->getLoop();
12381 auto *Predecessor = RLoop->getLoopPredecessor();
12383 const SCEV *L1 = getSCEV(LPhi->getIncomingValueForBlock(Predecessor));
12384 if (!ProvedEasily(L1, RAR->getStart()))
12386 auto *Latch = RLoop->getLoopLatch();
12388 const SCEV *L2 = getSCEV(LPhi->getIncomingValueForBlock(Latch));
12389 if (!ProvedEasily(L2, RAR->getPostIncExpr(*this)))
12394 // At this point RHS is either a non-Phi, or it is a Phi from some block
12400 const SCEV *L = getSCEV(LPhi->getIncomingValueForBlock(IncBB));
12434 if (match(SUFoundRHS->getValue(),
12438 // LHS <u (shiftee >> shiftvalue) && shiftee <=u RHS ---> LHS <u RHS
12439 // LHS <=u (shiftee >> shiftvalue) && shiftee <=u RHS ---> LHS <=u RHS
12441 // ---> LHS <s RHS
12443 // ---> LHS <=s RHS
12484 return is_contained(MinMaxExpr->operands(), Candidate);
12503 if (LAR->getLoop() != RAR->getLoop())
12505 if (!LAR->isAffine() || !RAR->isAffine())
12508 if (LAR->getStepRecurrence(SE) != RAR->getStepRecurrence(SE))
12513 if (!LAR->getNoWrapFlags(NW) || !RAR->getNoWrapFlags(NW))
12516 return SE.isKnownPredicate(Pred, LAR->getStart(), RAR->getStart());
12556 unsigned Depth) {
12557 assert(getTypeSizeInBits(LHS->getType()) ==
12558 getTypeSizeInBits(RHS->getType()) &&
12560 assert(getTypeSizeInBits(FoundLHS->getType()) ==
12561 getTypeSizeInBits(FoundRHS->getType()) &&
12564 if (Depth > MaxSCEVOperationsImplicationDepth)
12577 // involved values are non-negative.
12580 // Knowing that both FoundLHS and FoundRHS are non-negative, and knowing
12582 // use this fact to prove that LHS and RHS are non-negative.
12583 const SCEV *MinusOne = getMinusOne(LHS->getType());
12596 return Ext->getOperand();
12612 FoundRHS, Depth + 1);
12616 // We want to avoid creation of any new non-constant SCEV. Since we are
12621 if (getTypeSizeInBits(LHS->getType()) != getTypeSizeInBits(RHS->getType()))
12625 if (!LHSAddExpr->hasNoSignedWrap())
12628 auto *LL = LHSAddExpr->getOperand(0);
12629 auto *LR = LHSAddExpr->getOperand(1);
12630 auto *MinusOne = getMinusOne(RHS->getType());
12647 if (match(LHSUnknownExpr->getValue(), m_SDiv(m_Value(LL), m_Value(LR)))) {
12664 if (!Numerator || Numerator->getType() != FoundLHS->getType())
12672 auto *DTy = Denominator->getType();
12673 auto *FRHSTy = FoundRHS->getType();
12674 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
12688 // (FoundRHS > Denominator - 2) && (RHS <= 0) => (LHS > RHS).
12697 // (FoundRHS > -1 - Denominator) && (RHS < 0) => (LHS > RHS).
12698 // For example, given that FoundLHS > -3. Then FoundLHS is at least -2.
12701 // 2. If FoundLHS is non-negative, then the result is non-negative.
12702 // Anyways, the result is non-negative.
12714 if (isImpliedViaMerge(Pred, OrigLHS, RHS, OrigFoundLHS, FoundRHS, Depth + 1))
12807 // The restriction on `FoundRHS` be lifted easily -- it exists only to
12815 const APInt &ConstFoundRHS = cast<SCEVConstant>(FoundRHS)->getAPInt();
12827 const APInt &ConstRHS = cast<SCEVConstant>(RHS)->getAPInt();
12837 unsigned BitWidth = getTypeSizeInBits(RHS->getType());
12838 const SCEV *One = getOne(Stride->getType());
12846 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
12854 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
12860 unsigned BitWidth = getTypeSizeInBits(RHS->getType());
12861 const SCEV *One = getOne(Stride->getType());
12868 // SMinRHS - SMaxStrideMinusOne < SMinValue => overflow!
12876 // UMinRHS - UMaxStrideMinusOne < UMinValue => overflow!
12881 // umin(N, 1) + floor((N - umin(N, 1)) / D)
12882 // This is equivalent to "1 + floor((N - 1) / D)" for N != 0. The umin
12884 const SCEV *MinNOne = getUMinExpr(N, getOne(N->getType()));
12895 // If we can't, the backedge-taken count must be zero.
12897 return getZero(Stride->getType());
12913 // We assume either the stride is positive, or the backedge-taken count
12921 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
12925 // in the other case (End - Start) is zero, leading to a zero maximum backedge
12930 // MaxBECount = ceil((max(MaxEnd, MinStart) - MinStart) / Stride)
12934 return getUDivCeilSCEV(getConstant(MaxEnd - MinStart) /* Delta */,
12948 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(ZExt->getOperand());
12949 if (AR && AR->getLoop() == L && AR->isAffine()) {
12951 // We can use the comparison to infer no-wrap flags only if it fully
12959 if (!isKnownNonZero(AR->getStepRecurrence(*this)))
12964 const unsigned InnerBitWidth = getTypeSizeInBits(AR->getType());
12965 const unsigned OuterBitWidth = getTypeSizeInBits(RHS->getType());
12972 APInt StrideMax = getUnsignedRangeMax(AR->getStepRecurrence(*this));
12973 APInt Limit = APInt::getMaxValue(InnerBitWidth) - (StrideMax - 1);
12977 auto Flags = AR->getNoWrapFlags();
12982 if (AR->hasNoUnsignedWrap()) {
12985 const SCEV *Step = AR->getStepRecurrence(*this);
12986 Type *Ty = ZExt->getType();
12989 getZeroExtendExpr(Step, Ty, 0), L, AR->getNoWrapFlags());
13006 if (!IV || IV->getLoop() != L || !IV->isAffine())
13020 bool NoWrap = ControlsOnlyExit && IV->getNoWrapFlags(WrapType);
13023 const SCEV *Stride = IV->getStepRecurrence(*this);
13031 // effects. Here's the loop structure we are trying to handle -
13039 // The backedge taken count for such loops is evaluated as -
13040 // (max(end, start + stride) - start - 1) /u stride
13043 // of the above formula is as follows -
13077 // pick an arbitrary non-zero value for the denominator (e.g. stride)
13086 // Note: The (Start - Stride) term is used to get the start' term from
13089 auto *StartIfZero = getMinusSCEV(IV->getStart(), Stride);
13093 Stride = getUMaxExpr(Stride, getOne(Stride->getType()));
13112 const SCEV *Start = IV->getStart();
13114 // Preserve pointer-typed Start/RHS to pass to isLoopEntryGuardedByCond.
13116 // Use integer-typed versions for actual computation; we can't subtract
13120 if (Start->getType()->isPointerTy()) {
13125 if (RHS->getType()->isPointerTy()) {
13135 if (PositiveStride && RHSAddRec != nullptr && RHSAddRec->getLoop() == L &&
13136 RHSAddRec->getNoWrapFlags()) {
13149 const SCEV *RHSStart = RHSAddRec->getStart();
13150 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*this);
13152 // If Stride - RHSStride is positive and does not overflow, we can write
13153 // backedge count as ->
13154 // ceil((End - Start) /u (Stride - RHSStride))
13157 // Check if RHSStride < 0 and Stride - RHSStride will not overflow.
13182 Start, Stride, RHS, getTypeSizeInBits(LHS->getType()), IsSigned);
13187 // We use the expression (max(End,Start)-Start)/Stride to describe the
13195 // Can we prove (max(RHS,Start) > Start - Stride?
13200 // "End-Start /uceiling Stride" where "End = max(RHS,Start)"
13202 // "((End - 1) - (Start - Stride)) /u Stride"
13204 // our precondition that max(RHS,Start) > Start - Stride.
13205 // * For RHS <= Start, the backedge-taken count must be zero.
13206 // "((End - 1) - (Start - Stride)) /u Stride" reduces to
13207 // "((Start - 1) - (Start - Stride)) /u Stride" which simplies to
13208 // "Stride - 1 /u Stride" which is indeed zero for all non-zero values
13211 // * For RHS >= Start, the backedge count must be "RHS-Start /uceil
13213 // "((End - 1) - (Start - Stride)) /u Stride" reduces to
13214 // "((RHS - 1) - (Start - Stride)) /u Stride" reassociates to
13215 // "((RHS - (Start - Stride) - 1) /u Stride".
13217 const SCEV *MinusOne = getMinusOne(Stride->getType());
13233 // (RHS > Start - 1) implies RHS >= Start.
13234 // * "RHS >= Start" is trivially equivalent to "RHS > Start - 1" if
13235 // "Start - 1" doesn't overflow.
13236 // * For signed comparison, if Start - 1 does overflow, it's equal
13238 // * For unsigned comparison, if Start - 1 does overflow, it's equal
13244 getAddExpr(OrigStart, getMinusOne(OrigStart->getType()));
13254 // general, we can write the backedge-taken count as:
13256 // RHS >= Start ? ceil(RHS - Start) / Stride : 0
13260 // ceil(max(RHS, Start) - Start) / Stride
13279 // "(Start - End) + (Stride - 1)" has unsigned overflow.
13280 const SCEV *One = getOne(Stride->getType());
13295 // End - Start <= Stride * N <= UMAX - Start
13297 // Since Start is unsigned, UMAX - Start <= UMAX. Therefore:
13299 // End - Start <= Stride * N <= UMAX
13303 // End - Start <= Stride * N <= UMAX - (UMAX mod Stride)
13306 // Stride. Therefore, UMAX mod Stride == Stride - 1. So we can
13309 // End - Start <= Stride * N <= UMAX - Stride - 1
13313 // End - Start <= UMAX - Stride - 1
13315 // Adding Stride - 1 to both sides:
13317 // (End - Start) + (Stride - 1) <= UMAX
13322 // Just rewrite steps before "End - Start <= Stride * N <= UMAX"
13328 // If Start is equal to Stride, (End - Start) + (Stride - 1) == End
13329 // - 1. If !IsSigned, 0 <u Stride == Start <=u End; so 0 <u End - 1
13330 // <u End. If IsSigned, 0 <s Stride == Start <=s End; so 0 <s End -
13333 // If Start is equal to Stride - 1, (End - Start) + Stride - 1 ==
13342 // floor((D + (S - 1)) / S)
13366 Start, Stride, RHS, getTypeSizeInBits(LHS->getType()), IsSigned);
13395 if (!IV || IV->getLoop() != L || !IV->isAffine())
13399 bool NoWrap = ControlsOnlyExit && IV->getNoWrapFlags(WrapType);
13402 const SCEV *Stride = getNegativeSCEV(IV->getStepRecurrence(*this));
13409 // will not generate any unsigned overflow. Relaxed no-overflow conditions
13412 if (!Stride->isOne() && !NoWrap)
13416 const SCEV *Start = IV->getStart();
13428 if (Start->getType()->isPointerTy()) {
13433 if (End->getType()->isPointerTy()) {
13439 // Compute ((Start - End) + (Stride - 1)) / Stride.
13442 const SCEV *One = getOne(Stride->getType());
13452 unsigned BitWidth = getTypeSizeInBits(LHS->getType());
13453 APInt Limit = IsSigned ? APInt::getSignedMinValue(BitWidth) + (MinStride - 1)
13454 : APInt::getMinValue(BitWidth) + (MinStride - 1);
13457 // the case End = RHS. This is safe because in the other case (Start - End)
13466 : getUDivCeilSCEV(getConstant(MaxStart - MinEnd),
13483 // If the start is a non-zero constant, shift the range to simplify things.
13485 if (!SC->getValue()->isZero()) {
13487 Operands[0] = SE.getZero(SC->getType());
13491 return ShiftedAddRec->getNumIterationsInRange(
13492 Range.subtract(SC->getAPInt()), SE);
13519 APInt A = cast<SCEVConstant>(getOperand(1))->getAPInt();
13520 APInt End = A.sge(1) ? (Range.getUpper() - 1) : Range.getLower();
13530 if (Range.contains(Val->getValue()))
13536 ConstantInt::get(SE.getContext(), ExitVal - 1), SE)->getValue()) &&
13556 // may happen if we reach arithmetic depth limit while simplifying. So we
13561 for (unsigned i = 0, e = getNumOperands() - 1; i < e; ++i)
13567 const SCEV *Last = getOperand(getNumOperands() - 1);
13568 assert(!Last->isZero() && "Recurrency with zero step?");
13578 return isa<UndefValue>(SU->getValue());
13587 return SU->getValue() == nullptr;
13596 Ty = Store->getValueOperand()->getType();
13598 Ty = Load->getType();
13602 Type *ETy = getEffectiveSCEVType(PointerType::getUnqual(Inst->getContext()));
13606 //===----------------------------------------------------------------------===//
13608 //===----------------------------------------------------------------------===//
13613 SE->ConstantEvolutionLoopExitValue.erase(PN);
13614 SE->eraseValueFromMap(getValPtr());
13624 SE->forgetValue(getValPtr());
13631 //===----------------------------------------------------------------------===//
13633 //===----------------------------------------------------------------------===//
13653 HasGuards = GuardDecl && !GuardDecl->use_empty();
13692 U = U->Next;
13693 Tmp->~SCEVUnknown();
13714 /// When printing a top-level SCEV for trip counts, it's helpful to include
13718 OS << *S->getType() << " ";
13729 L->getHeader()->printAsOperand(OS, /*PrintType=*/false);
13733 L->getExitingBlocks(ExitingBlocks);
13737 auto *BTC = SE->getBackedgeTakenCount(L);
13739 OS << "backedge-taken count is ";
13742 OS << "Unpredictable backedge-taken count.";
13747 OS << " exit count for " << ExitingBlock->getName() << ": ";
13748 const SCEV *EC = SE->getExitCount(L, ExitingBlock);
13753 EC = SE->getPredicatedExitCount(L, ExitingBlock, &Predicates);
13755 OS << "\n predicated exit count for " << ExitingBlock->getName()
13760 P->print(OS, 4);
13767 L->getHeader()->printAsOperand(OS, /*PrintType=*/false);
13770 auto *ConstantBTC = SE->getConstantMaxBackedgeTakenCount(L);
13772 OS << "constant max backedge-taken count is ";
13774 if (SE->isBackedgeTakenCountMaxOrZero(L))
13777 OS << "Unpredictable constant max backedge-taken count. ";
13782 L->getHeader()->printAsOperand(OS, /*PrintType=*/false);
13785 auto *SymbolicBTC = SE->getSymbolicMaxBackedgeTakenCount(L);
13787 OS << "symbolic max backedge-taken count is ";
13789 if (SE->isBackedgeTakenCountMaxOrZero(L))
13792 OS << "Unpredictable symbolic max backedge-taken count. ";
13798 OS << " symbolic max exit count for " << ExitingBlock->getName() << ": ";
13799 auto *ExitBTC = SE->getExitCount(L, ExitingBlock,
13805 ExitBTC = SE->getPredicatedExitCount(L, ExitingBlock, &Predicates,
13809 << ExitingBlock->getName() << ": ";
13813 P->print(OS, 4);
13820 auto *PBT = SE->getPredicatedBackedgeTakenCount(L, Preds);
13824 L->getHeader()->printAsOperand(OS, /*PrintType=*/false);
13827 OS << "Predicated backedge-taken count is ";
13830 OS << "Unpredictable predicated backedge-taken count.";
13834 P->print(OS, 4);
13839 SE->getPredicatedConstantMaxBackedgeTakenCount(L, Preds);
13844 L->getHeader()->printAsOperand(OS, /*PrintType=*/false);
13847 OS << "Predicated constant max backedge-taken count is ";
13850 OS << "Unpredictable predicated constant max backedge-taken count.";
13854 P->print(OS, 4);
13859 SE->getPredicatedSymbolicMaxBackedgeTakenCount(L, Preds);
13864 L->getHeader()->printAsOperand(OS, /*PrintType=*/false);
13867 OS << "Predicated symbolic max backedge-taken count is ";
13870 OS << "Unpredictable predicated symbolic max backedge-taken count.";
13874 P->print(OS, 4);
13877 if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
13879 L->getHeader()->printAsOperand(OS, /*PrintType=*/false);
13881 OS << "Trip multiple is " << SE->getSmallConstantTripMultiple(L) << "\n";
13933 OS << " --> ";
13935 SV->print(OS);
13947 OS << " --> ";
13948 AtUse->print(OS);
13959 const SCEV *ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop());
13967 for (const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
13975 Iter->getHeader()->printAsOperand(OS, /*PrintType=*/false);
13989 InnerL->getHeader()->printAsOperand(OS, /*PrintType=*/false);
14028 switch (S->getSCEVType()) {
14036 if (AR->getLoop() == L)
14039 // Add recurrences are never invariant in the function-body (null loop).
14044 if (DT.dominates(L->getHeader(), AR->getLoop()->getHeader()))
14046 assert(!L->contains(AR->getLoop()) && "Containing loop's header does not"
14050 if (AR->getLoop()->contains(L))
14055 for (const auto *Op : AR->operands())
14059 // Otherwise it's loop-invariant.
14075 for (const auto *Op : S->operands()) {
14085 // All non-instruction values are loop invariant. All instructions are loop
14089 if (auto *I = dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue()))
14090 return (L && !L->contains(I)) ? LoopInvariant : LoopVariant;
14127 switch (S->getSCEVType()) {
14137 if (!DT.dominates(AR->getLoop()->getHeader(), BB))
14156 for (const SCEV *NAryOp : S->operands()) {
14167 dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue())) {
14168 if (I->getParent() == BB)
14170 if (DT.properlyDominates(I->getParent(), BB))
14199 for (const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14204 UserIt->second.erase({L, Predicated});
14220 for (const auto *User : Users->second)
14230 std::pair<const SCEV *, const Loop *> Entry = I->first;
14253 for (Value *V : ExprIt->second) {
14263 for (const auto &Pair : ScopeIt->second)
14272 for (const auto &Pair : ScopeUserIt->second)
14280 auto Copy = BEUsersIt->second;
14288 for (auto &KV : FoldUser->second)
14302 LoopsUsed.insert(AR->getLoop());
14324 if (match(BB->getTerminator(), m_Br(m_Value(Cond), m_BasicBlock(TrueBB),
14327 Worklist.push_back(C->isOne() ? TrueBB : FalseBB);
14332 const SCEV *L = getSCEV(Cmp->getOperand(0));
14333 const SCEV *R = getSCEV(Cmp->getOperand(1));
14334 if (isKnownPredicateViaConstantRanges(Cmp->getCmpPredicate(), L, R)) {
14338 if (isKnownPredicateViaConstantRanges(Cmp->getInverseCmpPredicate(), L,
14361 return SE.getConstant(Constant->getAPInt());
14365 return SE.getUnknown(Expr->getValue());
14377 auto GetDelta = [&](const SCEV *Old, const SCEV *New) -> const SCEV * {
14401 if (!ReachableBlocks.contains(L->getHeader()))
14411 SCM.visit(It->second.getExact(L, const_cast<ScalarEvolution *>(this)));
14416 // NB! This situation is legal, but is very suspicious -- whatever pass
14418 // computable or vice-versa *should have* invalidated SCEV. However, we
14424 if (SE.getTypeSizeInBits(CurBECount->getType()) >
14425 SE.getTypeSizeInBits(NewBECount->getType()))
14426 NewBECount = SE2.getZeroExtendExpr(NewBECount, CurBECount->getType());
14427 else if (SE.getTypeSizeInBits(CurBECount->getType()) <
14428 SE.getTypeSizeInBits(NewBECount->getType()))
14429 CurBECount = SE2.getZeroExtendExpr(CurBECount, NewBECount->getType());
14432 if (Delta && !Delta->isZero()) {
14447 Worklist.append(L->begin(), L->end());
14453 assert(ValidLoops.contains(AR->getLoop()) &&
14460 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14467 if (!ReachableBlocks.contains(I->getParent()))
14472 if (Delta && !Delta->isZero()) {
14490 if (It->second != KV.first) {
14491 dbgs() << "Value " << *V << " mapped to " << *It->second
14505 if (It != SCEVUsers.end() && It->second.count(&S))
14522 is_contained(It->second, std::make_pair(L, Value)))
14539 is_contained(It->second, std::make_pair(L, ValueAtScope)))
14557 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14589 << BB->getName() << " is incorrect: cached " << CachedDisposition
14604 if (!is_contained(I->second, FoldID)) {
14617 if (I->second != Expr) {
14619 << *I->second << " != " << *Expr << "!\n";
14674 // For compatibility with opt's -analyze feature under legacy pass manager
14683 INITIALIZE_PASS_BEGIN(ScalarEvolutionWrapperPass, "scalar-evolution",
14689 INITIALIZE_PASS_END(ScalarEvolutionWrapperPass, "scalar-evolution",
14710 SE->print(OS);
14717 SE->verify();
14737 assert(LHS->getType() == RHS->getType() &&
14778 /// If \p Pred is non-null, the SCEV expression is rewritten to respect the
14781 /// If \p NewPreds is non-null, rewrite is free to add further predicates to
14793 for (const auto *Pred : U->getPredicates())
14795 if (IPred->getLHS() == Expr &&
14796 IPred->getPredicate() == ICmpInst::ICMP_EQ)
14797 return IPred->getRHS();
14799 if (IPred->getLHS() == Expr &&
14800 IPred->getPredicate() == ICmpInst::ICMP_EQ)
14801 return IPred->getRHS();
14808 const SCEV *Operand = visit(Expr->getOperand());
14810 if (AR && AR->getLoop() == L && AR->isAffine()) {
14813 const SCEV *Step = AR->getStepRecurrence(SE);
14814 Type *Ty = Expr->getType();
14816 return SE.getAddRecExpr(SE.getZeroExtendExpr(AR->getStart(), Ty),
14818 AR->getNoWrapFlags());
14820 return SE.getZeroExtendExpr(Operand, Expr->getType());
14824 const SCEV *Operand = visit(Expr->getOperand());
14826 if (AR && AR->getLoop() == L && AR->isAffine()) {
14829 const SCEV *Step = AR->getStepRecurrence(SE);
14830 Type *Ty = Expr->getType();
14832 return SE.getAddRecExpr(SE.getSignExtendExpr(AR->getStart(), Ty),
14834 AR->getNoWrapFlags());
14836 return SE.getSignExtendExpr(Operand, Expr->getType());
14849 return Pred && Pred->implies(P, SE);
14851 NewPreds->push_back(P);
14868 if (!isa<PHINode>(Expr->getValue()))
14875 for (const auto *P : PredicatedRewrite->second){
14878 if (L != WP->getExpr()->getLoop())
14884 return PredicatedRewrite->first;
14926 assert(LHS->getType() == RHS->getType() && "LHS and RHS types don't match");
14940 return Op->LHS == LHS && Op->RHS == RHS;
14945 void SCEVComparePredicate::print(raw_ostream &OS, unsigned Depth) const {
14947 OS.indent(Depth) << "Equal predicate: " << *LHS << " == " << *RHS << "\n";
14949 OS.indent(Depth) << "Compare predicate: " << *LHS << " " << Pred << ") "
14964 if (!Op || setFlags(Flags, Op->Flags) != Flags)
14967 if (Op->AR == AR)
14974 const SCEV *Start = AR->getStart();
14975 const SCEV *OpStart = Op->AR->getStart();
14976 if (Start->getType()->isPointerTy() != OpStart->getType()->isPointerTy())
14979 const SCEV *Step = AR->getStepRecurrence(SE);
14980 const SCEV *OpStep = Op->AR->getStepRecurrence(SE);
14986 Type *WiderTy = SE.getWiderType(Step->getType(), OpStep->getType());
15001 SCEV::NoWrapFlags ScevFlags = AR->getNoWrapFlags();
15010 void SCEVWrapPredicate::print(raw_ostream &OS, unsigned Depth) const {
15011 OS.indent(Depth) << *getExpr() << " Added Flags: ";
15023 SCEV::NoWrapFlags StaticFlags = AR->getNoWrapFlags();
15032 if (const auto *Step = dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE)))
15033 if (Step->getValue()->getValue().isNonNegative())
15050 [](const SCEVPredicate *I) { return I->isAlwaysTrue(); });
15056 return all_of(Set->Preds, [this, &SE](const SCEVPredicate *I) {
15057 return this->implies(I, SE);
15061 [N, &SE](const SCEVPredicate *I) { return I->implies(N, SE); });
15064 void SCEVUnionPredicate::print(raw_ostream &OS, unsigned Depth) const {
15066 Pred->print(OS, Depth);
15071 for (const auto *Pred : Set->Preds)
15084 if (N->implies(P, SE))
15160 if (Preds->implies(&Pred, SE))
15163 SmallVector<const SCEVPredicate *, 4> NewPreds(Preds->getPredicates());
15196 II.first->second = SCEVWrapPredicate::setFlags(Flags, II.first->second);
15210 Flags = SCEVWrapPredicate::clearFlags(Flags, II->second);
15216 const SCEV *Expr = this->getSCEV(V);
15233 Preds(std::make_unique<SCEVUnionPredicate>(Init.Preds->getPredicates(),
15240 void PredicatedScalarEvolution::print(raw_ostream &OS, unsigned Depth) const {
15254 if (II->second.second == Expr)
15257 OS.indent(Depth) << "[PSE]" << I << ":\n";
15258 OS.indent(Depth + 2) << *Expr << "\n";
15259 OS.indent(Depth + 2) << "--> " << *II->second.second << "\n";
15263 // Match the mathematical pattern A - (A / B) * B, where A and B can be
15265 // for URem with constant power-of-2 second operands.
15270 if (Expr->getType()->isPointerTy())
15274 // for URem with constant power-of-2 second operands. Make sure the size of
15277 if (const auto *Trunc = dyn_cast<SCEVTruncateExpr>(ZExt->getOperand(0))) {
15278 LHS = Trunc->getOperand();
15281 if (getTypeSizeInBits(LHS->getType()) >
15282 getTypeSizeInBits(Expr->getType()))
15284 if (LHS->getType() != Expr->getType())
15285 LHS = getZeroExtendExpr(LHS, Expr->getType());
15286 RHS = getConstant(APInt(getTypeSizeInBits(Expr->getType()), 1)
15287 << getTypeSizeInBits(Trunc->getType()));
15291 if (Add == nullptr || Add->getNumOperands() != 2)
15294 const SCEV *A = Add->getOperand(1);
15295 const auto *Mul = dyn_cast<SCEVMulExpr>(Add->getOperand(0));
15301 // (SomeExpr + (-(SomeExpr / B) * B)).
15310 // (SomeExpr + (-1 * (SomeExpr / B) * B)).
15311 if (Mul->getNumOperands() == 3 && isa<SCEVConstant>(Mul->getOperand(0)))
15312 return MatchURemWithDivisor(Mul->getOperand(1)) ||
15313 MatchURemWithDivisor(Mul->getOperand(2));
15315 // (SomeExpr + ((-SomeExpr / B) * B)) or (SomeExpr + ((SomeExpr / B) * -B)).
15316 if (Mul->getNumOperands() == 2)
15317 return MatchURemWithDivisor(Mul->getOperand(1)) ||
15318 MatchURemWithDivisor(Mul->getOperand(0)) ||
15319 MatchURemWithDivisor(getNegativeSCEV(Mul->getOperand(1))) ||
15320 MatchURemWithDivisor(getNegativeSCEV(Mul->getOperand(0)));
15326 BasicBlock *Header = L->getHeader();
15327 BasicBlock *Pred = L->getLoopPredecessor();
15340 unsigned Depth) {
15345 auto GetMinMaxConst = [&](unsigned IncomingIdx) -> MinMaxPattern {
15351 collectFromBlock(SE, G->second, Phi.getParent(), InBlock, VisitedBlocks,
15352 Depth + 1);
15353 auto &RewriteMap = G->second.RewriteMap;
15359 auto *SM = dyn_cast_if_present<SCEVMinMaxExpr>(S->second);
15362 if (const SCEVConstant *C0 = dyn_cast<SCEVConstant>(SM->getOperand(0)))
15363 return {C0, SM->getSCEVType()};
15367 MinMaxPattern P2) -> MinMaxPattern {
15374 return {C1->getAPInt().ult(C2->getAPInt()) ? C1 : C2, T1};
15376 return {C1->getAPInt().slt(C2->getAPInt()) ? C1 : C2, T1};
15378 return {C1->getAPInt().ugt(C2->getAPInt()) ? C1 : C2, T1};
15380 return {C1->getAPInt().sgt(C2->getAPInt()) ? C1 : C2, T1};
15382 llvm_unreachable("Trying to merge non-MinMaxExpr SCEVs.");
15402 SmallPtrSetImpl<const BasicBlock *> &VisitedBlocks, unsigned Depth) {
15419 // Check for a condition of the form (-C1 + X < C2). InstCombine will
15433 ConstantRange::makeExactICmpRegion(Predicate, C2->getAPInt())
15434 .sub(C1->getAPInt());
15436 // Bail out, unless we have a non-wrapping, monotonic range.
15440 const SCEV *RewrittenLHS = I != RewriteMap.end() ? I->second : LHSUnknown;
15451 // Return true if \p Expr is a MinMax SCEV expression with a non-negative
15453 // the non-constant operand and in \p LHS the constant operand.
15458 if (MinMax->getNumOperands() != 2)
15460 if (auto *C = dyn_cast<SCEVConstant>(MinMax->getOperand(0))) {
15461 if (C->getAPInt().isNegative())
15463 SCTy = MinMax->getSCEVType();
15464 LHS = MinMax->getOperand(0);
15465 RHS = MinMax->getOperand(1);
15472 // Checks whether Expr is a non-negative constant, and Divisor is a positive
15480 ExprVal = ConstExpr->getAPInt();
15481 DivisorVal = ConstDivisor->getAPInt();
15496 // return the SCEV: Expr + Divisor - Expr % Divisor
15497 return SE.getConstant(ExprVal + DivisorVal - Rem);
15511 // return the SCEV: Expr - Expr % Divisor
15512 return SE.getConstant(ExprVal - Rem);
15529 "Expected non-negative operand!");
15549 I != RewriteMap.end() ? I->second : LHSUnknown;
15570 // Puts rewrite rule \p From -> \p To into the rewrite map. Also if \p From
15586 return I != RewriteMap.end() ? I->second : S;
15599 if (Mul->getNumOperands() != 2)
15601 auto *MulLHS = Mul->getOperand(0);
15602 auto *MulRHS = Mul->getOperand(1);
15606 if (Div->getOperand(1) == MulRHS) {
15612 return HasDivisibiltyInfo(MinMax->getOperand(0), DividesBy) ||
15613 HasDivisibiltyInfo(MinMax->getOperand(1), DividesBy);
15620 if (SE.getURemExpr(Expr, DividesBy)->isZero())
15623 return IsKnownToDivideBy(MinMax->getOperand(0), DividesBy) &&
15624 IsKnownToDivideBy(MinMax->getOperand(1), DividesBy);
15638 // 'min(a, b) >= c' -> '(a >= c) and (b >= c)',
15639 // 'min(a, b) > c' -> '(a > c) and (b > c)',
15640 // 'max(a, b) <= c' -> '(a <= c) and (b <= c)',
15641 // 'max(a, b) < c' -> '(a < c) and (b < c)'.
15644 // with non-strict ones against plus or minus one of RHS depending on the
15646 const SCEV *One = SE.getOne(RHS->getType());
15649 if (RHS->getType()->isPointerTy())
15679 append_range(Worklist, S->operands());
15744 Terms.emplace_back(AssumeI->getOperand(0), true);
15751 for (const auto *GU : GuardDecl->users())
15753 if (Guard->getFunction() == Block->getParent() &&
15755 Terms.emplace_back(Guard->getArgOperand(0), true);
15769 dyn_cast<BranchInst>(Pair.first->getTerminator());
15770 if (!LoopEntryPredicate || LoopEntryPredicate->isUnconditional())
15773 Terms.emplace_back(LoopEntryPredicate->getCondition(),
15774 LoopEntryPredicate->getSuccessor(0) == Pair.second);
15778 // conditions to limit compile-time impact for now.
15779 if (Depth > 0 && NumCollectedConditions == 2)
15787 if (Pair.second->hasNPredecessorsOrMore(2) &&
15788 Depth < MaxLoopGuardCollectionDepth) {
15790 for (auto &Phi : Pair.second->phis())
15791 collectFromPHI(SE, Guards, Phi, VisitedBlocks, IncomingGuards, Depth);
15809 EnterIfTrue ? Cmp->getPredicate() : Cmp->getInversePredicate();
15810 const auto *LHS = SE.getSCEV(Cmp->getOperand(0));
15811 const auto *RHS = SE.getSCEV(Cmp->getOperand(1));
15840 // sub-expressions.
15876 return I->second;
15884 Type *Ty = Expr->getType();
15885 const SCEV *Op = Expr->getOperand(0);
15886 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
15888 Bitwidth > Op->getType()->getScalarSizeInBits()) {
15893 return SE.getZeroExtendExpr(I->second, Ty);
15900 return I->second;
15908 return I->second;
15915 return I->second;
15922 return I->second;
15928 for (const auto *Op : Expr->operands()) {
15938 Expr->getNoWrapFlags(), FlagMask));
15944 for (const auto *Op : Expr->operands()) {
15954 Expr->getNoWrapFlags(), FlagMask));