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