84#include "llvm/Config/llvm-config.h"
135using namespace PatternMatch;
137#define DEBUG_TYPE "scalar-evolution"
140 "Number of loop exits with predictable exit counts");
142 "Number of loop exits without predictable exit counts");
144 "Number of loops with trip counts computed by force");
146#ifdef EXPENSIVE_CHECKS
154 cl::desc(
"Maximum number of iterations SCEV will "
155 "symbolically execute a constant "
161 cl::desc(
"Verify ScalarEvolution's backedge taken counts (slow)"));
164 cl::desc(
"Enable stricter verification with -verify-scev is passed"));
168 cl::desc(
"Verify IR correctness when making sensitive SCEV queries (slow)"),
173 cl::desc(
"Threshold for inlining multiplication operands into a SCEV"),
178 cl::desc(
"Threshold for inlining addition operands into a SCEV"),
182 "scalar-evolution-max-scev-compare-depth",
cl::Hidden,
183 cl::desc(
"Maximum depth of recursive SCEV complexity comparisons"),
187 "scalar-evolution-max-scev-operations-implication-depth",
cl::Hidden,
188 cl::desc(
"Maximum depth of recursive SCEV operations implication analysis"),
192 "scalar-evolution-max-value-compare-depth",
cl::Hidden,
193 cl::desc(
"Maximum depth of recursive value complexity comparisons"),
198 cl::desc(
"Maximum depth of recursive arithmetics"),
202 "scalar-evolution-max-constant-evolving-depth",
cl::Hidden,
207 cl::desc(
"Maximum depth of recursive SExt/ZExt/Trunc"),
212 cl::desc(
"Max coefficients in AddRec during evolving"),
217 cl::desc(
"Size of the expression which is considered huge"),
222 cl::desc(
"Threshold for switching to iteratively computing SCEV ranges"),
228 cl::desc(
"When printing analysis, include information on every instruction"));
231 "scalar-evolution-use-expensive-range-sharpening",
cl::Hidden,
233 cl::desc(
"Use more powerful methods of sharpening expression ranges. May "
234 "be costly in terms of compile time"));
237 "scalar-evolution-max-scc-analysis-depth",
cl::Hidden,
238 cl::desc(
"Maximum amount of nodes to process while searching SCEVUnknown "
239 "Phi strongly connected components"),
244 cl::desc(
"Handle <= and >= in finite loops"),
248 "scalar-evolution-use-context-for-no-wrap-flag-strenghening",
cl::Hidden,
249 cl::desc(
"Infer nuw/nsw flags using context where suitable"),
260#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
270 cast<SCEVConstant>(
this)->getValue()->printAsOperand(
OS,
false);
278 OS <<
"(ptrtoint " << *
Op->getType() <<
" " << *
Op <<
" to "
279 << *PtrToInt->
getType() <<
")";
285 OS <<
"(trunc " << *
Op->getType() <<
" " << *
Op <<
" to "
292 OS <<
"(zext " << *
Op->getType() <<
" " << *
Op <<
" to "
299 OS <<
"(sext " << *
Op->getType() <<
" " << *
Op <<
" to "
328 const char *OpStr =
nullptr;
341 OpStr =
" umin_seq ";
347 ListSeparator LS(OpStr);
371 cast<SCEVUnknown>(
this)->getValue()->printAsOperand(
OS,
false);
374 OS <<
"***COULDNOTCOMPUTE***";
383 return cast<SCEVConstant>(
this)->getType();
385 return cast<SCEVVScale>(
this)->getType();
390 return cast<SCEVCastExpr>(
this)->getType();
392 return cast<SCEVAddRecExpr>(
this)->getType();
394 return cast<SCEVMulExpr>(
this)->getType();
399 return cast<SCEVMinMaxExpr>(
this)->getType();
401 return cast<SCEVSequentialMinMaxExpr>(
this)->getType();
403 return cast<SCEVAddExpr>(
this)->getType();
405 return cast<SCEVUDivExpr>(
this)->getType();
407 return cast<SCEVUnknown>(
this)->getType();
424 return cast<SCEVCastExpr>(
this)->operands();
433 return cast<SCEVNAryExpr>(
this)->operands();
435 return cast<SCEVUDivExpr>(
this)->operands();
443 if (
const SCEVConstant *SC = dyn_cast<SCEVConstant>(
this))
444 return SC->getValue()->isZero();
449 if (
const SCEVConstant *SC = dyn_cast<SCEVConstant>(
this))
450 return SC->getValue()->isOne();
455 if (
const SCEVConstant *SC = dyn_cast<SCEVConstant>(
this))
456 return SC->getValue()->isMinusOne();
462 if (!
Mul)
return false;
466 if (!SC)
return false;
469 return SC->getAPInt().isNegative();
484 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
486 UniqueSCEVs.InsertNode(S, IP);
505 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
508 UniqueSCEVs.InsertNode(S, IP);
527 "Must be a non-bit-width-changing pointer-to-integer cast!");
539 "Cannot truncate non-integer value!");
546 "Cannot zero extend non-integer value!");
553 "Cannot sign extend non-integer value!");
556void SCEVUnknown::deleted() {
558 SE->forgetMemoizedResults(
this);
561 SE->UniqueSCEVs.RemoveNode(
this);
567void SCEVUnknown::allUsesReplacedWith(
Value *New) {
569 SE->forgetMemoizedResults(
this);
572 SE->UniqueSCEVs.RemoveNode(
this);
611 if (LIsPointer != RIsPointer)
612 return (
int)LIsPointer - (int)RIsPointer;
617 return (
int)LID - (int)RID;
620 if (
const auto *LA = dyn_cast<Argument>(LV)) {
621 const auto *
RA = cast<Argument>(RV);
622 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
623 return (
int)LArgNo - (int)RArgNo;
626 if (
const auto *LGV = dyn_cast<GlobalValue>(LV)) {
627 const auto *RGV = cast<GlobalValue>(RV);
629 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
630 auto LT = GV->getLinkage();
637 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
638 return LGV->getName().compare(RGV->getName());
643 if (
const auto *LInst = dyn_cast<Instruction>(LV)) {
644 const auto *RInst = cast<Instruction>(RV);
649 if (LParent != RParent) {
652 if (LDepth != RDepth)
653 return (
int)LDepth - (int)RDepth;
657 unsigned LNumOps = LInst->getNumOperands(),
658 RNumOps = RInst->getNumOperands();
659 if (LNumOps != RNumOps)
660 return (
int)LNumOps - (int)RNumOps;
662 for (
unsigned Idx :
seq(LNumOps)) {
680static std::optional<int>
692 return (
int)LType - (int)RType;
722 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
723 if (LBitWidth != RBitWidth)
724 return (
int)LBitWidth - (int)RBitWidth;
725 return LA.
ult(
RA) ? -1 : 1;
729 const auto *LTy = cast<IntegerType>(cast<SCEVVScale>(
LHS)->
getType());
730 const auto *RTy = cast<IntegerType>(cast<SCEVVScale>(
RHS)->
getType());
731 return LTy->getBitWidth() - RTy->getBitWidth();
742 if (LLoop != RLoop) {
744 assert(LHead != RHead &&
"Two loops share the same header?");
748 "No dominance between recurrences used by one SCEV?");
771 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
772 if (LNumOps != RNumOps)
773 return (
int)LNumOps - (int)RNumOps;
775 for (
unsigned i = 0; i != LNumOps; ++i) {
777 ROps[i], DT,
Depth + 1);
802 if (Ops.
size() < 2)
return;
811 return Complexity && *Complexity < 0;
813 if (Ops.
size() == 2) {
817 if (IsLessComplex(
RHS,
LHS))
824 return IsLessComplex(
LHS,
RHS);
831 for (
unsigned i = 0, e = Ops.
size(); i != e-2; ++i) {
832 const SCEV *S = Ops[i];
837 for (
unsigned j = i+1; j != e && Ops[j]->getSCEVType() == Complexity; ++j) {
842 if (i == e-2)
return;
928 APInt OddFactorial(W, 1);
930 for (
unsigned i = 3; i <= K; ++i) {
932 unsigned TwoFactors = Mult.countr_zero();
934 Mult.lshrInPlace(TwoFactors);
935 OddFactorial *= Mult;
939 unsigned CalculationBits = W +
T;
948 APInt MultiplyFactor = OddFactorial.
zext(W+1);
950 MultiplyFactor = MultiplyFactor.
trunc(W);
956 for (
unsigned i = 1; i != K; ++i) {
989 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
994 if (isa<SCEVCouldNotCompute>(Coeff))
1009 "getLosslessPtrToIntExpr() should self-recurse at most once.");
1013 if (!
Op->getType()->isPointerTy())
1024 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1043 if (
auto *U = dyn_cast<SCEVUnknown>(
Op)) {
1048 if (isa<ConstantPointerNull>(U->getValue()))
1054 SCEV *S =
new (SCEVAllocator)
1056 UniqueSCEVs.InsertNode(S, IP);
1061 assert(
Depth == 0 &&
"getLosslessPtrToIntExpr() should not self-recurse for "
1062 "non-SCEVUnknown's.");
1074 class SCEVPtrToIntSinkingRewriter
1082 SCEVPtrToIntSinkingRewriter
Rewriter(SE);
1092 return Base::visit(S);
1097 bool Changed =
false;
1107 bool Changed =
false;
1117 "Should only reach pointer-typed SCEVUnknown's.");
1123 const SCEV *IntOp = SCEVPtrToIntSinkingRewriter::rewrite(
Op, *
this);
1125 "We must have succeeded in sinking the cast, "
1126 "and ending up with an integer-typed expression!");
1134 if (isa<SCEVCouldNotCompute>(IntOp))
1143 "This is not a truncating conversion!");
1145 "This is not a conversion to a SCEVable type!");
1146 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1154 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1176 UniqueSCEVs.InsertNode(S, IP);
1185 if (isa<SCEVAddExpr>(
Op) || isa<SCEVMulExpr>(
Op)) {
1186 auto *CommOp = cast<SCEVCommutativeExpr>(
Op);
1188 unsigned numTruncs = 0;
1189 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1192 if (!isa<SCEVIntegralCastExpr>(CommOp->getOperand(i)) &&
1193 isa<SCEVTruncateExpr>(S))
1197 if (numTruncs < 2) {
1198 if (isa<SCEVAddExpr>(
Op))
1200 if (isa<SCEVMulExpr>(
Op))
1207 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1214 for (
const SCEV *
Op : AddRec->operands())
1229 UniqueSCEVs.InsertNode(S, IP);
1269struct ExtendOpTraitsBase {
1275template <
typename ExtendOp>
struct ExtendOpTraits {
1291 static const GetExtendExprTy GetExtendExpr;
1293 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1300const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1307 static const GetExtendExprTy GetExtendExpr;
1309 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1316const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1328template <
typename ExtendOpTy>
1331 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1332 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1339 const SCEVAddExpr *SA = dyn_cast<SCEVAddExpr>(Start);
1348 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1361 auto PreStartFlags =
1379 const SCEV *OperandExtendedStart =
1381 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1382 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1394 const SCEV *OverflowLimit =
1395 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1397 if (OverflowLimit &&
1405template <
typename ExtendOpTy>
1409 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1411 const SCEV *PreStart = getPreStartForExtend<ExtendOpTy>(AR, Ty, SE,
Depth);
1417 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1452template <
typename ExtendOpTy>
1453bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1456 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1462 const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start);
1468 for (
unsigned Delta : {-2, -1, 1, 2}) {
1473 ID.AddPointer(PreStart);
1474 ID.AddPointer(Step);
1482 if (PreAR && PreAR->getNoWrapFlags(WrapType)) {
1485 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1486 DeltaS, &Pred,
this);
1504 const unsigned BitWidth =
C.getBitWidth();
1522 const APInt &ConstantStart,
1541 auto &UserIDs = FoldCacheUser[
I.first->second];
1542 assert(
count(UserIDs,
ID) == 1 &&
"unexpected duplicates in UserIDs");
1543 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1544 if (UserIDs[
I] ==
ID) {
1549 I.first->second = S;
1551 auto R = FoldCacheUser.insert({S, {}});
1552 R.first->second.push_back(
ID);
1558 "This is not an extending conversion!");
1560 "This is not a conversion to a SCEVable type!");
1561 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1565 auto Iter = FoldCache.find(
ID);
1566 if (Iter != FoldCache.end())
1567 return Iter->second;
1570 if (!isa<SCEVZeroExtendExpr>(S))
1578 "This is not an extending conversion!");
1580 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1597 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1601 UniqueSCEVs.InsertNode(S, IP);
1610 const SCEV *
X = ST->getOperand();
1624 if (AR->isAffine()) {
1625 const SCEV *Start = AR->getStart();
1626 const SCEV *Step = AR->getStepRecurrence(*
this);
1628 const Loop *L = AR->getLoop();
1632 if (AR->hasNoUnsignedWrap()) {
1634 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
Depth + 1);
1648 if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
1653 const SCEV *CastedMaxBECount =
1657 if (MaxBECount == RecastedMaxBECount) {
1667 const SCEV *WideMaxBECount =
1669 const SCEV *OperandExtendedAdd =
1675 if (ZAdd == OperandExtendedAdd) {
1679 Start = getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
1686 OperandExtendedAdd =
1692 if (ZAdd == OperandExtendedAdd) {
1697 Start = getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
1712 if (!isa<SCEVCouldNotCompute>(MaxBECount) || HasGuards ||
1715 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1717 if (AR->hasNoUnsignedWrap()) {
1723 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
Depth + 1);
1740 Start = getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
1751 if (
const auto *SC = dyn_cast<SCEVConstant>(Start)) {
1752 const APInt &
C = SC->getAPInt();
1756 const SCEV *SResidual =
1765 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1768 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
Depth + 1);
1784 if (
auto *Div = dyn_cast<SCEVUDivExpr>(
Op))
1788 if (
auto *SA = dyn_cast<SCEVAddExpr>(
Op)) {
1790 if (SA->hasNoUnsignedWrap()) {
1794 for (
const auto *
Op : SA->operands())
1807 if (
const auto *SC = dyn_cast<SCEVConstant>(SA->getOperand(0))) {
1811 const SCEV *SResidual =
1821 if (
auto *SM = dyn_cast<SCEVMulExpr>(
Op)) {
1823 if (SM->hasNoUnsignedWrap()) {
1827 for (
const auto *
Op : SM->operands())
1844 if (SM->getNumOperands() == 2)
1845 if (
auto *MulLHS = dyn_cast<SCEVConstant>(SM->getOperand(0)))
1846 if (MulLHS->getAPInt().isPowerOf2())
1847 if (
auto *TruncRHS = dyn_cast<SCEVTruncateExpr>(SM->getOperand(1))) {
1849 MulLHS->getAPInt().logBase2();
1861 if (isa<SCEVUMinExpr>(
Op) || isa<SCEVUMaxExpr>(
Op)) {
1862 auto *
MinMax = cast<SCEVMinMaxExpr>(
Op);
1864 for (
auto *Operand :
MinMax->operands())
1866 if (isa<SCEVUMinExpr>(
MinMax))
1872 if (
auto *
MinMax = dyn_cast<SCEVSequentialMinMaxExpr>(
Op)) {
1873 assert(isa<SCEVSequentialUMinExpr>(
MinMax) &&
"Not supported!");
1875 for (
auto *Operand :
MinMax->operands())
1882 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1885 UniqueSCEVs.InsertNode(S, IP);
1893 "This is not an extending conversion!");
1895 "This is not a conversion to a SCEVable type!");
1896 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1900 auto Iter = FoldCache.find(
ID);
1901 if (Iter != FoldCache.end())
1902 return Iter->second;
1905 if (!isa<SCEVSignExtendExpr>(S))
1913 "This is not an extending conversion!");
1915 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1937 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1942 UniqueSCEVs.InsertNode(S, IP);
1951 const SCEV *
X = ST->getOperand();
1960 if (
auto *SA = dyn_cast<SCEVAddExpr>(
Op)) {
1962 if (SA->hasNoSignedWrap()) {
1966 for (
const auto *
Op : SA->operands())
1980 if (
const auto *SC = dyn_cast<SCEVConstant>(SA->getOperand(0))) {
1984 const SCEV *SResidual =
1998 if (AR->isAffine()) {
1999 const SCEV *Start = AR->getStart();
2000 const SCEV *Step = AR->getStepRecurrence(*
this);
2002 const Loop *L = AR->getLoop();
2006 if (AR->hasNoSignedWrap()) {
2008 getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty,
this,
Depth + 1);
2022 if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
2028 const SCEV *CastedMaxBECount =
2032 if (MaxBECount == RecastedMaxBECount) {
2042 const SCEV *WideMaxBECount =
2044 const SCEV *OperandExtendedAdd =
2050 if (SAdd == OperandExtendedAdd) {
2054 Start = getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty,
this,
2061 OperandExtendedAdd =
2067 if (SAdd == OperandExtendedAdd) {
2079 Start = getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty,
this,
2087 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2089 if (AR->hasNoSignedWrap()) {
2095 getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty,
this,
Depth + 1);
2103 if (
const auto *SC = dyn_cast<SCEVConstant>(Start)) {
2104 const APInt &
C = SC->getAPInt();
2108 const SCEV *SResidual =
2117 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2120 getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty,
this,
Depth + 1);
2133 if (isa<SCEVSMinExpr>(
Op) || isa<SCEVSMaxExpr>(
Op)) {
2134 auto *
MinMax = cast<SCEVMinMaxExpr>(
Op);
2136 for (
auto *Operand :
MinMax->operands())
2138 if (isa<SCEVSMinExpr>(
MinMax))
2145 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
2148 UniqueSCEVs.InsertNode(S, IP);
2174 "This is not an extending conversion!");
2176 "This is not a conversion to a SCEVable type!");
2181 if (SC->getAPInt().isNegative())
2186 const SCEV *NewOp =
T->getOperand();
2194 if (!isa<SCEVZeroExtendExpr>(ZExt))
2199 if (!isa<SCEVSignExtendExpr>(SExt))
2205 for (
const SCEV *
Op : AR->operands())
2211 if (isa<SCEVSMaxExpr>(
Op))
2244 APInt &AccumulatedConstant,
2247 bool Interesting =
false;
2251 while (
const SCEVConstant *
C = dyn_cast<SCEVConstant>(Ops[i])) {
2254 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2256 AccumulatedConstant += Scale *
C->getAPInt();
2261 for (; i != Ops.
size(); ++i) {
2263 if (
Mul && isa<SCEVConstant>(
Mul->getOperand(0))) {
2265 Scale * cast<SCEVConstant>(
Mul->getOperand(0))->getAPInt();
2266 if (
Mul->getNumOperands() == 2 && isa<SCEVAddExpr>(
Mul->getOperand(1))) {
2271 Add->operands(), NewScale, SE);
2277 auto Pair = M.insert({Key, NewScale});
2281 Pair.first->second += NewScale;
2289 std::pair<DenseMap<const SCEV *, APInt>::iterator,
bool> Pair =
2290 M.insert({Ops[i], Scale});
2294 Pair.first->second += Scale;
2313 case Instruction::Add:
2316 case Instruction::Sub:
2319 case Instruction::Mul:
2329 auto *NarrowTy = cast<IntegerType>(
LHS->
getType());
2333 const SCEV *
A = (this->*Extension)(
2335 const SCEV *LHSB = (this->*Extension)(
LHS, WideTy, 0);
2336 const SCEV *RHSB = (this->*Extension)(
RHS, WideTy, 0);
2344 if (BinOp == Instruction::Mul)
2346 auto *RHSC = dyn_cast<SCEVConstant>(
RHS);
2350 APInt C = RHSC->getAPInt();
2351 unsigned NumBits =
C.getBitWidth();
2352 bool IsSub = (BinOp == Instruction::Sub);
2353 bool IsNegativeConst = (
Signed &&
C.isNegative());
2355 bool OverflowDown = IsSub ^ IsNegativeConst;
2357 if (IsNegativeConst) {
2370 APInt Limit = Min + Magnitude;
2376 APInt Limit = Max - Magnitude;
2381std::optional<SCEV::NoWrapFlags>
2386 return std::nullopt;
2395 bool Deduced =
false;
2397 if (OBO->
getOpcode() != Instruction::Add &&
2400 return std::nullopt;
2409 false,
LHS,
RHS, CtxI)) {
2423 return std::nullopt;
2433 using namespace std::placeholders;
2440 assert(CanAnalyze &&
"don't call from other places!");
2447 auto IsKnownNonNegative = [&](
const SCEV *S) {
2457 if (SignOrUnsignWrap != SignOrUnsignMask &&
2459 isa<SCEVConstant>(Ops[0])) {
2464 return Instruction::Add;
2466 return Instruction::Mul;
2472 const APInt &
C = cast<SCEVConstant>(Ops[0])->getAPInt();
2477 Opcode,
C, OBO::NoSignedWrap);
2485 Opcode,
C, OBO::NoUnsignedWrap);
2495 Ops[0]->isZero() && IsKnownNonNegative(Ops[1]))
2501 if (
auto *UDiv = dyn_cast<SCEVUDivExpr>(Ops[0]))
2502 if (UDiv->getOperand(1) == Ops[1])
2504 if (
auto *UDiv = dyn_cast<SCEVUDivExpr>(Ops[1]))
2505 if (UDiv->getOperand(1) == Ops[0])
2521 "only nuw or nsw allowed");
2523 if (Ops.
size() == 1)
return Ops[0];
2526 for (
unsigned i = 1, e = Ops.
size(); i != e; ++i)
2528 "SCEVAddExpr operand types don't match!");
2531 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2539 if (
const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
2544 Ops[0] =
getConstant(LHSC->getAPInt() + RHSC->getAPInt());
2545 if (Ops.
size() == 2)
return Ops[0];
2547 LHSC = cast<SCEVConstant>(Ops[0]);
2551 if (LHSC->getValue()->isZero()) {
2556 if (Ops.
size() == 1)
return Ops[0];
2566 return getOrCreateAddExpr(Ops, ComputeFlags(Ops));
2571 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2572 Add->setNoWrapFlags(ComputeFlags(Ops));
2579 Type *Ty = Ops[0]->getType();
2580 bool FoundMatch =
false;
2581 for (
unsigned i = 0, e = Ops.
size(); i != e-1; ++i)
2582 if (Ops[i] == Ops[i+1]) {
2585 while (i+Count != e && Ops[i+Count] == Ops[i])
2590 if (Ops.
size() == Count)
2594 --i; e -= Count - 1;
2604 auto FindTruncSrcType = [&]() ->
Type * {
2609 if (
auto *
T = dyn_cast<SCEVTruncateExpr>(Ops[
Idx]))
2610 return T->getOperand()->getType();
2611 if (
const auto *
Mul = dyn_cast<SCEVMulExpr>(Ops[
Idx])) {
2612 const auto *LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2613 if (
const auto *
T = dyn_cast<SCEVTruncateExpr>(LastOp))
2614 return T->getOperand()->getType();
2618 if (
auto *SrcType = FindTruncSrcType()) {
2623 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
2625 if (
T->getOperand()->getType() != SrcType) {
2630 }
else if (
const SCEVConstant *
C = dyn_cast<SCEVConstant>(Ops[i])) {
2632 }
else if (
const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Ops[i])) {
2634 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2636 dyn_cast<SCEVTruncateExpr>(M->getOperand(j))) {
2637 if (
T->getOperand()->getType() != SrcType) {
2642 }
else if (
const auto *
C = dyn_cast<SCEVConstant>(M->getOperand(j))) {
2660 if (isa<SCEVConstant>(Fold) || isa<SCEVUnknown>(Fold))
2665 if (Ops.
size() == 2) {
2669 const SCEV *
A = Ops[0];
2670 const SCEV *
B = Ops[1];
2671 auto *AddExpr = dyn_cast<SCEVAddExpr>(
B);
2672 auto *
C = dyn_cast<SCEVConstant>(
A);
2673 if (AddExpr &&
C && isa<SCEVConstant>(AddExpr->getOperand(0))) {
2674 auto C1 = cast<SCEVConstant>(AddExpr->getOperand(0))->getAPInt();
2675 auto C2 =
C->getAPInt();
2678 APInt ConstAdd = C1 + C2;
2679 auto AddFlags = AddExpr->getNoWrapFlags();
2691 ConstAdd.
abs().
ule(C1.abs())) {
2705 if (Ops.
size() == 2) {
2707 if (
Mul &&
Mul->getNumOperands() == 2 &&
2708 Mul->getOperand(0)->isAllOnesValue()) {
2711 if (matchURem(
Mul->getOperand(1),
X,
Y) &&
X == Ops[1]) {
2723 bool DeletedAdd =
false;
2737 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2753 if (
Idx < Ops.
size() && isa<SCEVMulExpr>(Ops[
Idx])) {
2760 struct APIntCompare {
2769 std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists;
2770 for (
const SCEV *NewOp : NewOps)
2771 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2774 if (AccumulatedConstant != 0)
2776 for (
auto &MulOp : MulOpLists) {
2777 if (MulOp.first == 1) {
2779 }
else if (MulOp.first != 0) {
2788 if (Ops.
size() == 1)
2797 for (;
Idx < Ops.
size() && isa<SCEVMulExpr>(Ops[
Idx]); ++
Idx) {
2799 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2800 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2801 if (isa<SCEVConstant>(MulOpSCEV))
2803 for (
unsigned AddOp = 0, e = Ops.
size(); AddOp != e; ++AddOp)
2804 if (MulOpSCEV == Ops[AddOp]) {
2806 const SCEV *InnerMul =
Mul->getOperand(MulOp == 0);
2807 if (
Mul->getNumOperands() != 2) {
2811 Mul->operands().take_front(MulOp));
2819 if (Ops.
size() == 2)
return OuterMul;
2832 for (
unsigned OtherMulIdx =
Idx+1;
2833 OtherMulIdx < Ops.
size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]);
2835 const SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]);
2839 OMulOp != e; ++OMulOp)
2840 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2842 const SCEV *InnerMul1 =
Mul->getOperand(MulOp == 0);
2843 if (
Mul->getNumOperands() != 2) {
2845 Mul->operands().take_front(MulOp));
2852 OtherMul->
operands().take_front(OMulOp));
2857 const SCEV *InnerMulSum =
2861 if (Ops.
size() == 2)
return OuterMul;
2878 for (;
Idx < Ops.
size() && isa<SCEVAddRecExpr>(Ops[
Idx]); ++
Idx) {
2884 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i)
2892 if (!LIOps.
empty()) {
2917 auto *DefI = getDefiningScopeBound(LIOps);
2919 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2931 if (Ops.
size() == 1)
return NewRec;
2934 for (
unsigned i = 0;; ++i)
2935 if (Ops[i] == AddRec) {
2945 for (
unsigned OtherIdx =
Idx+1;
2946 OtherIdx < Ops.
size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
2951 cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop()->getHeader(),
2953 "AddRecExprs are not sorted in reverse dominance order?");
2954 if (AddRecLoop == cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop()) {
2957 for (; OtherIdx != Ops.
size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
2959 const auto *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
2960 if (OtherAddRec->getLoop() == AddRecLoop) {
2961 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2963 if (i >= AddRecOps.
size()) {
2964 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2968 AddRecOps[i], OtherAddRec->getOperand(i)};
2971 Ops.
erase(Ops.
begin() + OtherIdx); --OtherIdx;
2986 return getOrCreateAddExpr(Ops, ComputeFlags(Ops));
2994 for (
const SCEV *
Op : Ops)
2998 static_cast<SCEVAddExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3001 std::uninitialized_copy(Ops.begin(), Ops.end(), O);
3002 S =
new (SCEVAllocator)
3004 UniqueSCEVs.InsertNode(S, IP);
3016 for (
const SCEV *
Op : Ops)
3024 std::uninitialized_copy(Ops.begin(), Ops.end(), O);
3025 S =
new (SCEVAllocator)
3027 UniqueSCEVs.InsertNode(S, IP);
3028 LoopUsers[
L].push_back(S);
3040 for (
const SCEV *
Op : Ops)
3044 static_cast<SCEVMulExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3047 std::uninitialized_copy(Ops.begin(), Ops.end(), O);
3048 S =
new (SCEVAllocator)
SCEVMulExpr(
ID.Intern(SCEVAllocator),
3050 UniqueSCEVs.InsertNode(S, IP);
3059 if (j > 1 && k / j != i) Overflow =
true;
3075 if (n == 0 || n == k)
return 1;
3076 if (k > n)
return 0;
3082 for (
uint64_t i = 1; i <= k; ++i) {
3083 r =
umul_ov(r, n-(i-1), Overflow);
3092 struct FindConstantInAddMulChain {
3093 bool FoundConstant =
false;
3095 bool follow(
const SCEV *S) {
3096 FoundConstant |= isa<SCEVConstant>(S);
3097 return isa<SCEVAddExpr>(S) || isa<SCEVMulExpr>(S);
3100 bool isDone()
const {
3101 return FoundConstant;
3105 FindConstantInAddMulChain
F;
3107 ST.visitAll(StartExpr);
3108 return F.FoundConstant;
3116 "only nuw or nsw allowed");
3118 if (Ops.
size() == 1)
return Ops[0];
3120 Type *ETy = Ops[0]->getType();
3122 for (
unsigned i = 1, e = Ops.
size(); i != e; ++i)
3124 "SCEVMulExpr operand types don't match!");
3132 if (
const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
3137 Ops[0] =
getConstant(LHSC->getAPInt() * RHSC->getAPInt());
3138 if (Ops.
size() == 2)
return Ops[0];
3140 LHSC = cast<SCEVConstant>(Ops[0]);
3144 if (LHSC->getValue()->isZero())
3148 if (LHSC->getValue()->isOne()) {
3153 if (Ops.
size() == 1)
3164 return getOrCreateMulExpr(Ops, ComputeFlags(Ops));
3169 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3170 Mul->setNoWrapFlags(ComputeFlags(Ops));
3174 if (
const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
3175 if (Ops.
size() == 2) {
3192 if (Ops[0]->isAllOnesValue()) {
3197 bool AnyFolded =
false;
3198 for (
const SCEV *AddOp :
Add->operands()) {
3201 if (!isa<SCEVMulExpr>(
Mul)) AnyFolded =
true;
3206 }
else if (
const auto *AddRec = dyn_cast<SCEVAddRecExpr>(Ops[1])) {
3225 AddRec->getNoWrapFlags(FlagsMask));
3237 bool DeletedMul =
false;
3262 for (;
Idx < Ops.
size() && isa<SCEVAddRecExpr>(Ops[
Idx]); ++
Idx) {
3267 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i)
3275 if (!LIOps.
empty()) {
3288 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3304 if (Ops.
size() == 1)
return NewRec;
3307 for (
unsigned i = 0;; ++i)
3308 if (Ops[i] == AddRec) {
3329 bool OpsModified =
false;
3330 for (
unsigned OtherIdx =
Idx+1;
3331 OtherIdx != Ops.
size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
3334 dyn_cast<SCEVAddRecExpr>(Ops[OtherIdx]);
3344 bool Overflow =
false;
3350 SmallVector <const SCEV *, 7> SumOps;
3351 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3355 z < ze && !Overflow; ++z) {
3358 if (LargerThan64Bits)
3359 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3361 Coeff = Coeff1*Coeff2;
3376 if (Ops.
size() == 2)
return NewAddRec;
3377 Ops[
Idx] = NewAddRec;
3378 Ops.
erase(Ops.
begin() + OtherIdx); --OtherIdx;
3380 AddRec = dyn_cast<SCEVAddRecExpr>(NewAddRec);
3394 return getOrCreateMulExpr(Ops, ComputeFlags(Ops));
3402 "SCEVURemExpr operand types don't match!");
3407 if (RHSC->getValue()->isOne())
3411 if (RHSC->getAPInt().isPowerOf2()) {
3430 "SCEVUDivExpr operand can't be pointer!");
3432 "SCEVUDivExpr operand types don't match!");
3439 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3444 if (LHSC->getValue()->isZero())
3448 if (RHSC->getValue()->isOne())
3453 if (!RHSC->getValue()->isZero()) {
3458 unsigned LZ = RHSC->getAPInt().countl_zero();
3462 if (!RHSC->getAPInt().isPowerOf2())
3468 dyn_cast<SCEVConstant>(AR->getStepRecurrence(*
this))) {
3470 const APInt &StepInt = Step->getAPInt();
3471 const APInt &DivInt = RHSC->getAPInt();
3472 if (!StepInt.
urem(DivInt) &&
3478 for (
const SCEV *
Op : AR->operands())
3485 const SCEVConstant *StartC = dyn_cast<SCEVConstant>(AR->getStart());
3486 if (StartC && !DivInt.
urem(StepInt) &&
3492 const APInt &StartRem = StartInt.
urem(StepInt);
3493 if (StartRem != 0) {
3494 const SCEV *NewLHS =
3497 if (
LHS != NewLHS) {
3507 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3516 for (
const SCEV *
Op : M->operands())
3520 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3521 const SCEV *
Op = M->getOperand(i);
3523 if (!isa<SCEVUDivExpr>(Div) &&
getMulExpr(Div, RHSC) ==
Op) {
3533 if (
auto *DivisorConstant =
3534 dyn_cast<SCEVConstant>(OtherDiv->getRHS())) {
3535 bool Overflow =
false;
3537 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3548 for (
const SCEV *
Op :
A->operands())
3552 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3554 if (isa<SCEVUDivExpr>(
Op) ||
3559 if (
Operands.size() ==
A->getNumOperands())
3566 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3573 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
3576 UniqueSCEVs.InsertNode(S, IP);
3606 if (!
Mul || !
Mul->hasNoUnsignedWrap())
3612 if (
const auto *LHSCst = dyn_cast<SCEVConstant>(
Mul->getOperand(0))) {
3613 if (LHSCst == RHSCst) {
3621 APInt Factor =
gcd(LHSCst, RHSCst);
3624 cast<SCEVConstant>(
getConstant(LHSCst->getAPInt().udiv(Factor)));
3626 cast<SCEVConstant>(
getConstant(RHSCst->getAPInt().udiv(Factor)));
3632 Mul = dyn_cast<SCEVMulExpr>(
LHS);
3639 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3640 if (
Mul->getOperand(i) ==
RHS) {
3658 if (
const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
3659 if (StepChrec->getLoop() == L) {
3676 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
3678 "SCEVAddRecExpr operand types don't match!");
3681 for (
unsigned i = 0, e =
Operands.size(); i != e; ++i)
3683 "SCEVAddRecExpr operand is not available at loop entry!");
3701 const Loop *NestedLoop = NestedAR->getLoop();
3702 if (L->contains(NestedLoop)
3707 Operands[0] = NestedAR->getStart();
3711 bool AllInvariant =
all_of(
3723 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3734 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3744 return getOrCreateAddRecExpr(
Operands, L, Flags);
3754 const bool AssumeInBoundsFlags = [&]() {
3755 if (!
GEP->isInBounds())
3761 auto *GEPI = dyn_cast<Instruction>(
GEP);
3764 return GEPI && isSCEVExprNeverPoison(GEPI);
3771 bool FirstIter =
true;
3773 for (
const SCEV *IndexExpr : IndexExprs) {
3775 if (
StructType *STy = dyn_cast<StructType>(CurTy)) {
3780 Offsets.push_back(FieldOffset);
3783 CurTy = STy->getTypeAtIndex(
Index);
3787 assert(isa<PointerType>(CurTy) &&
3788 "The first index of a GEP indexes a pointer");
3789 CurTy =
GEP->getSourceElementType();
3800 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3801 Offsets.push_back(LocalOffset);
3806 if (Offsets.empty())
3818 "GEP should not change type mid-flight.");
3822SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3825 ID.AddInteger(SCEVType);
3826 for (
const SCEV *
Op : Ops)
3829 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3839 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3840 assert(!Ops.
empty() &&
"Cannot get empty (u|s)(min|max)!");
3841 if (Ops.
size() == 1)
return Ops[0];
3844 for (
unsigned i = 1, e = Ops.
size(); i != e; ++i) {
3846 "Operand types don't match!");
3849 "min/max should be consistently pointerish");
3860 if (
const SCEV *S = findExistingSCEVInCache(Kind, Ops)) {
3866 if (
const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
3887 getContext(), FoldOp(LHSC->getAPInt(), RHSC->getAPInt()));
3890 if (Ops.
size() == 1)
return Ops[0];
3891 LHSC = cast<SCEVConstant>(Ops[0]);
3894 bool IsMinV = LHSC->getValue()->isMinValue(IsSigned);
3895 bool IsMaxV = LHSC->getValue()->isMaxValue(IsSigned);
3897 if (IsMax ? IsMinV : IsMaxV) {
3901 }
else if (IsMax ? IsMaxV : IsMinV) {
3907 if (Ops.
size() == 1)
return Ops[0];
3911 while (
Idx < Ops.
size() && Ops[
Idx]->getSCEVType() < Kind)
3917 bool DeletedAny =
false;
3918 while (Ops[
Idx]->getSCEVType() == Kind) {
3938 for (
unsigned i = 0, e = Ops.
size() - 1; i != e; ++i) {
3939 if (Ops[i] == Ops[i + 1] ||
3940 isKnownViaNonRecursiveReasoning(FirstPred, Ops[i], Ops[i + 1])) {
3946 }
else if (isKnownViaNonRecursiveReasoning(SecondPred, Ops[i],
3955 if (Ops.
size() == 1)
return Ops[0];
3957 assert(!Ops.
empty() &&
"Reduced smax down to nothing!");
3962 ID.AddInteger(Kind);
3963 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i)
3964 ID.AddPointer(Ops[i]);
3966 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3968 return ExistingSCEV;
3970 std::uninitialized_copy(Ops.
begin(), Ops.
end(), O);
3971 SCEV *S =
new (SCEVAllocator)
3974 UniqueSCEVs.InsertNode(S, IP);
3981class SCEVSequentialMinMaxDeduplicatingVisitor final
3982 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
3983 std::optional<const SCEV *>> {
3984 using RetVal = std::optional<const SCEV *>;
3992 bool canRecurseInto(
SCEVTypes Kind)
const {
3995 return RootKind == Kind || NonSequentialRootKind == Kind;
3998 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
3999 assert((isa<SCEVMinMaxExpr>(S) || isa<SCEVSequentialMinMaxExpr>(S)) &&
4000 "Only for min/max expressions.");
4003 if (!canRecurseInto(Kind))
4006 auto *NAry = cast<SCEVNAryExpr>(S);
4008 bool Changed = visit(Kind, NAry->operands(), NewOps);
4013 return std::nullopt;
4015 return isa<SCEVSequentialMinMaxExpr>(S)
4020 RetVal visit(
const SCEV *S) {
4022 if (!SeenOps.
insert(S).second)
4023 return std::nullopt;
4024 return Base::visit(S);
4030 : SE(SE), RootKind(RootKind),
4031 NonSequentialRootKind(
4037 bool Changed =
false;
4041 for (
const SCEV *
Op : OrigOps) {
4042 RetVal NewOp = visit(
Op);
4050 NewOps = std::move(Ops);
4056 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4066 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4068 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4070 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4072 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4075 return visitAnyMinMaxExpr(Expr);
4079 return visitAnyMinMaxExpr(Expr);
4083 return visitAnyMinMaxExpr(Expr);
4087 return visitAnyMinMaxExpr(Expr);
4091 return visitAnyMinMaxExpr(Expr);
4094 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4138struct SCEVPoisonCollector {
4139 bool LookThroughMaybePoisonBlocking;
4141 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4142 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4144 bool follow(
const SCEV *S) {
4145 if (!LookThroughMaybePoisonBlocking &&
4149 if (
auto *SU = dyn_cast<SCEVUnknown>(S)) {
4155 bool isDone()
const {
return false; }
4165 SCEVPoisonCollector PC1(
true);
4170 if (PC1.MaybePoison.empty())
4176 SCEVPoisonCollector PC2(
false);
4182 return PC2.MaybePoison.contains(S);
4188 SCEVPoisonCollector PC(
false);
4211 while (!Worklist.
empty()) {
4213 if (!Visited.
insert(V).second)
4217 if (Visited.
size() > 16)
4225 auto *
I = dyn_cast<Instruction>(V);
4232 if (
auto *PDI = dyn_cast<PossiblyDisjointInst>(
I))
4233 if (PDI->isDisjoint())
4239 if (
auto *II = dyn_cast<IntrinsicInst>(
I);
4240 II && II->getIntrinsicID() == Intrinsic::vscale)
4247 if (
I->hasPoisonGeneratingFlagsOrMetadata())
4259 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4260 "Not a SCEVSequentialMinMaxExpr!");
4261 assert(!Ops.
empty() &&
"Cannot get empty (u|s)(min|max)!");
4262 if (Ops.
size() == 1)
4266 for (
unsigned i = 1, e = Ops.
size(); i != e; ++i) {
4268 "Operand types don't match!");
4271 "min/max should be consistently pointerish");
4279 if (
const SCEV *S = findExistingSCEVInCache(Kind, Ops))
4286 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4287 bool Changed = Deduplicator.visit(Kind, Ops, Ops);
4296 bool DeletedAny =
false;
4298 if (Ops[
Idx]->getSCEVType() != Kind) {
4302 const auto *SMME = cast<SCEVSequentialMinMaxExpr>(Ops[
Idx]);
4305 SMME->operands().end());
4313 const SCEV *SaturationPoint;
4324 for (
unsigned i = 1, e = Ops.
size(); i != e; ++i) {
4340 if (isKnownViaNonRecursiveReasoning(Pred, Ops[i - 1], Ops[i])) {
4349 ID.AddInteger(Kind);
4350 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i)
4351 ID.AddPointer(Ops[i]);
4353 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4355 return ExistingSCEV;
4358 std::uninitialized_copy(Ops.
begin(), Ops.
end(), O);
4359 SCEV *S =
new (SCEVAllocator)
4362 UniqueSCEVs.InsertNode(S, IP);
4410 if (
Size.isScalable())
4431 "Cannot get offset for structure containing scalable vector types");
4445 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP)) {
4446 assert(cast<SCEVUnknown>(S)->getValue() == V &&
4447 "Stale SCEVUnknown in uniquing map!");
4452 FirstUnknown = cast<SCEVUnknown>(S);
4453 UniqueSCEVs.InsertNode(S, IP);
4501 bool PreciseA, PreciseB;
4502 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4503 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4504 if (!PreciseA || !PreciseB)
4507 return (ScopeA == ScopeB) || DT.
dominates(ScopeA, ScopeB) ||
4512 return CouldNotCompute.get();
4515bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4517 auto *SU = dyn_cast<SCEVUnknown>(S);
4518 return SU && SU->getValue() ==
nullptr;
4521 return !ContainsNulls;
4526 if (
I != HasRecMap.
end())
4531 HasRecMap.
insert({S, FoundAddRec});
4539 if (SI == ExprValueMap.
end())
4540 return std::nullopt;
4541 return SI->second.getArrayRef();
4547void ScalarEvolution::eraseValueFromMap(
Value *V) {
4549 if (
I != ValueExprMap.
end()) {
4550 auto EVIt = ExprValueMap.
find(
I->second);
4551 bool Removed = EVIt->second.remove(V);
4553 assert(Removed &&
"Value not in ExprValueMap?");
4558void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4562 auto It = ValueExprMap.
find_as(V);
4563 if (It == ValueExprMap.
end()) {
4565 ExprValueMap[S].
insert(V);
4576 return createSCEVIter(V);
4583 if (
I != ValueExprMap.
end()) {
4584 const SCEV *S =
I->second;
4585 assert(checkValidity(S) &&
4586 "existing SCEV has not been properly invalidated");
4595 if (
const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
4599 Type *Ty = V->getType();
4607 if (!
Add ||
Add->getNumOperands() != 2 ||
4608 !
Add->getOperand(0)->isAllOnesValue())
4611 const SCEVMulExpr *AddRHS = dyn_cast<SCEVMulExpr>(
Add->getOperand(1));
4621 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4623 if (
const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
4634 return (
const SCEV *)
nullptr;
4640 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4644 Type *Ty = V->getType();
4650 assert(
P->getType()->isPointerTy());
4652 if (
auto *AddRec = dyn_cast<SCEVAddRecExpr>(
P)) {
4660 if (
auto *
Add = dyn_cast<SCEVAddExpr>(
P)) {
4663 const SCEV **PtrOp =
nullptr;
4664 for (
const SCEV *&AddOp : Ops) {
4665 if (AddOp->getType()->isPointerTy()) {
4666 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4700 const bool RHSIsNotMinSigned =
4731 Type *SrcTy = V->getType();
4733 "Cannot truncate or zero extend with non-integer arguments!");
4743 Type *SrcTy = V->getType();
4745 "Cannot truncate or zero extend with non-integer arguments!");
4755 Type *SrcTy = V->getType();
4757 "Cannot noop or zero extend with non-integer arguments!");
4759 "getNoopOrZeroExtend cannot truncate!");
4767 Type *SrcTy = V->getType();
4769 "Cannot noop or sign extend with non-integer arguments!");
4771 "getNoopOrSignExtend cannot truncate!");
4779 Type *SrcTy = V->getType();
4781 "Cannot noop or any extend with non-integer arguments!");
4783 "getNoopOrAnyExtend cannot truncate!");
4791 Type *SrcTy = V->getType();
4793 "Cannot truncate or noop with non-integer arguments!");
4795 "getTruncateOrNoop cannot extend!");
4803 const SCEV *PromotedLHS =
LHS;
4804 const SCEV *PromotedRHS =
RHS;
4824 assert(!Ops.
empty() &&
"At least one operand must be!");
4826 if (Ops.
size() == 1)
4830 Type *MaxType =
nullptr;
4831 for (
const auto *S : Ops)
4836 assert(MaxType &&
"Failed to find maximum type!");
4840 for (
const auto *S : Ops)
4849 if (!V->getType()->isPointerTy())
4853 if (
auto *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
4854 V = AddRec->getStart();
4855 }
else if (
auto *
Add = dyn_cast<SCEVAddExpr>(V)) {
4856 const SCEV *PtrOp =
nullptr;
4857 for (
const SCEV *AddOp :
Add->operands()) {
4858 if (AddOp->getType()->isPointerTy()) {
4859 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4863 assert(PtrOp &&
"Must have pointer op");
4875 for (
User *U :
I->users()) {
4876 auto *UserInsn = cast<Instruction>(U);
4877 if (Visited.
insert(UserInsn).second)
4892 bool IgnoreOtherLoops =
true) {
4895 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4897 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4904 SeenLoopVariantSCEVUnknown =
true;
4912 SeenOtherLoops =
true;
4916 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4918 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4925 bool SeenLoopVariantSCEVUnknown =
false;
4926 bool SeenOtherLoops =
false;
4936 SCEVPostIncRewriter
Rewriter(L, SE);
4938 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4945 SeenLoopVariantSCEVUnknown =
true;
4953 SeenOtherLoops =
true;
4957 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4959 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4966 bool SeenLoopVariantSCEVUnknown =
false;
4967 bool SeenOtherLoops =
false;
4973class SCEVBackedgeConditionFolder
4978 bool IsPosBECond =
false;
4979 Value *BECond =
nullptr;
4981 BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
4984 "Both outgoing branches should not target same header!");
4991 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
5001 switch (
I->getOpcode()) {
5002 case Instruction::Select: {
5004 std::optional<const SCEV *> Res =
5005 compareWithBackedgeCondition(
SI->getCondition());
5007 bool IsOne = cast<SCEVConstant>(*Res)->getValue()->isOne();
5013 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5024 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5027 IsPositiveBECond(IsPosBECond) {}
5029 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5033 Value *BackedgeCond =
nullptr;
5035 bool IsPositiveBECond;
5038std::optional<const SCEV *>
5039SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5044 if (BackedgeCond == IC)
5047 return std::nullopt;
5073 bool isValid() {
return Valid; }
5086ScalarEvolution::proveNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5096 if (
const SCEVConstant *BECountMax = dyn_cast<SCEVConstant>(BECount)) {
5098 const APInt &BECountAP = BECountMax->getAPInt();
5099 unsigned NoOverflowBitWidth =
5111 Instruction::Add, IncRange, OBO::NoSignedWrap);
5112 if (NSWRegion.contains(AddRecRange))
5121 Instruction::Add, IncRange, OBO::NoUnsignedWrap);
5122 if (NUWRegion.contains(AddRecRange))
5130ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5140 if (!SignedWrapViaInductionTried.insert(AR).second)
5164 if (isa<SCEVCouldNotCompute>(MaxBECount) && !HasGuards &&
5173 const SCEV *OverflowLimit =
5175 if (OverflowLimit &&
5183ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5193 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5218 if (isa<SCEVCouldNotCompute>(MaxBECount) && !HasGuards &&
5257 if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(
Op)) {
5258 IsNSW = OBO->hasNoSignedWrap();
5259 IsNUW = OBO->hasNoUnsignedWrap();
5263 explicit BinaryOp(
unsigned Opcode,
Value *
LHS,
Value *
RHS,
bool IsNSW =
false,
5265 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5275 auto *
Op = dyn_cast<Operator>(V);
5277 return std::nullopt;
5283 switch (
Op->getOpcode()) {
5284 case Instruction::Add:
5285 case Instruction::Sub:
5286 case Instruction::Mul:
5287 case Instruction::UDiv:
5288 case Instruction::URem:
5289 case Instruction::And:
5290 case Instruction::AShr:
5291 case Instruction::Shl:
5292 return BinaryOp(
Op);
5294 case Instruction::Or: {
5296 if (cast<PossiblyDisjointInst>(
Op)->isDisjoint())
5297 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5299 return BinaryOp(
Op);
5302 case Instruction::Xor:
5303 if (
auto *RHSC = dyn_cast<ConstantInt>(
Op->getOperand(1)))
5306 if (RHSC->getValue().isSignMask())
5307 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5309 if (V->getType()->isIntegerTy(1))
5310 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5311 return BinaryOp(
Op);
5313 case Instruction::LShr:
5315 if (
ConstantInt *SA = dyn_cast<ConstantInt>(
Op->getOperand(1))) {
5322 if (SA->getValue().ult(
BitWidth)) {
5324 ConstantInt::get(SA->getContext(),
5326 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5329 return BinaryOp(
Op);
5331 case Instruction::ExtractValue: {
5332 auto *EVI = cast<ExtractValueInst>(
Op);
5333 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5336 auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand());
5341 bool Signed = WO->isSigned();
5344 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5349 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5359 if (
auto *II = dyn_cast<IntrinsicInst>(V))
5360 if (II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5361 return BinaryOp(Instruction::Sub, II->getOperand(0), II->getOperand(1));
5363 return std::nullopt;
5389 if (
Op == SymbolicPHI)
5394 if (SourceBits != NewBits)
5402 SExt ? dyn_cast<SCEVTruncateExpr>(SExt->
getOperand())
5403 : dyn_cast<SCEVTruncateExpr>(ZExt->
getOperand());
5407 if (
X != SymbolicPHI)
5409 Signed = SExt !=
nullptr;
5417 if (!L || L->getHeader() != PN->
getParent())
5475std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5476ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5482 auto *PN = cast<PHINode>(SymbolicPHI->
getValue());
5484 assert(L &&
"Expecting an integer loop header phi");
5489 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5490 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5491 Value *
V = PN->getIncomingValue(i);
5492 if (
L->contains(PN->getIncomingBlock(i))) {
5495 }
else if (BEValueV != V) {
5499 }
else if (!StartValueV) {
5501 }
else if (StartValueV != V) {
5502 StartValueV =
nullptr;
5506 if (!BEValueV || !StartValueV)
5507 return std::nullopt;
5514 const auto *
Add = dyn_cast<SCEVAddExpr>(BEValue);
5516 return std::nullopt;
5520 unsigned FoundIndex =
Add->getNumOperands();
5521 Type *TruncTy =
nullptr;
5523 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5526 if (FoundIndex == e) {
5531 if (FoundIndex ==
Add->getNumOperands())
5532 return std::nullopt;
5536 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5537 if (i != FoundIndex)
5544 return std::nullopt;
5598 const SCEV *PHISCEV =
5608 if (
const auto *AR = dyn_cast<SCEVAddRecExpr>(PHISCEV)) {
5625 auto getExtendedExpr = [&](
const SCEV *Expr,
5626 bool CreateSignExtend) ->
const SCEV * {
5629 const SCEV *ExtendedExpr =
5632 return ExtendedExpr;
5640 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5641 const SCEV *ExtendedExpr) ->
bool {
5642 return Expr != ExtendedExpr &&
5646 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5647 if (PredIsKnownFalse(StartVal, StartExtended)) {
5649 return std::nullopt;
5654 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5655 if (PredIsKnownFalse(Accum, AccumExtended)) {
5657 return std::nullopt;
5660 auto AppendPredicate = [&](
const SCEV *Expr,
5661 const SCEV *ExtendedExpr) ->
void {
5662 if (Expr != ExtendedExpr &&
5670 AppendPredicate(StartVal, StartExtended);
5671 AppendPredicate(Accum, AccumExtended);
5679 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5680 std::make_pair(NewAR, Predicates);
5682 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5686std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5688 auto *PN = cast<PHINode>(SymbolicPHI->
getValue());
5691 return std::nullopt;
5694 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5695 if (
I != PredicatedSCEVRewrites.end()) {
5696 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5699 if (Rewrite.first == SymbolicPHI)
5700 return std::nullopt;
5703 assert(isa<SCEVAddRecExpr>(Rewrite.first) &&
"Expected an AddRec");
5704 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5708 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5709 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5714 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5715 return std::nullopt;
5732 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5751const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5753 Value *StartValueV) {
5756 assert(BEValueV && StartValueV);
5762 if (BO->Opcode != Instruction::Add)
5765 const SCEV *Accum =
nullptr;
5766 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5768 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5782 insertValueToMap(PN, PHISCEV);
5784 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(PHISCEV)) {
5787 proveNoWrapViaConstantRanges(AR)));
5793 if (
auto *BEInst = dyn_cast<Instruction>(BEValueV)) {
5795 "Accum is defined outside L, but is not invariant?");
5796 if (isAddRecNeverPoison(BEInst, L))
5803const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5811 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5817 }
else if (BEValueV != V) {
5821 }
else if (!StartValueV) {
5823 }
else if (StartValueV != V) {
5824 StartValueV =
nullptr;
5828 if (!BEValueV || !StartValueV)
5832 "PHI node already processed?");
5836 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5841 insertValueToMap(PN, SymbolicName);
5855 unsigned FoundIndex =
Add->getNumOperands();
5856 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5857 if (
Add->getOperand(i) == SymbolicName)
5858 if (FoundIndex == e) {
5863 if (FoundIndex !=
Add->getNumOperands()) {
5866 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5867 if (i != FoundIndex)
5868 Ops.
push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5875 (isa<SCEVAddRecExpr>(Accum) &&
5876 cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
5880 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5893 if (
GEP->isInBounds() &&
GEP->getOperand(0) == PN) {
5910 forgetMemoizedResults(SymbolicName);
5911 insertValueToMap(PN, PHISCEV);
5913 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(PHISCEV)) {
5916 proveNoWrapViaConstantRanges(AR)));
5922 if (
auto *BEInst = dyn_cast<Instruction>(BEValueV))
5939 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5940 const SCEV *Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5944 if (Start == StartVal) {
5948 forgetMemoizedResults(SymbolicName);
5949 insertValueToMap(PN, Shifted);
5959 eraseValueFromMap(PN);
5979 Use &LeftUse =
Merge->getOperandUse(0);
5980 Use &RightUse =
Merge->getOperandUse(1);
5997const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
6014 assert(IDom &&
"At least the entry block should dominate PN");
6023 return createNodeForSelectOrPHI(PN,
Cond, LHS, RHS);
6029const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6030 if (
const SCEV *S = createAddRecFromPHI(PN))
6036 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6045 struct FindClosure {
6046 const SCEV *OperandToFind;
6052 bool canRecurseInto(
SCEVTypes Kind)
const {
6055 return RootKind == Kind || NonSequentialRootKind == Kind ||
6060 : OperandToFind(OperandToFind), RootKind(RootKind),
6061 NonSequentialRootKind(
6065 bool follow(
const SCEV *S) {
6066 Found = S == OperandToFind;
6068 return !isDone() && canRecurseInto(S->
getSCEVType());
6071 bool isDone()
const {
return Found; }
6074 FindClosure FC(OperandToFind, RootKind);
6079std::optional<const SCEV *>
6080ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6090 switch (ICI->getPredicate()) {
6104 bool Signed = ICI->isSigned();
6113 if (LA == LS &&
RA == RS)
6115 if (LA == RS &&
RA == LS)
6118 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6119 if (
Op->getType()->isPointerTy()) {
6121 if (isa<SCEVCouldNotCompute>(
Op))
6130 LS = CoerceOperand(LS);
6131 RS = CoerceOperand(RS);
6132 if (isa<SCEVCouldNotCompute>(LS) || isa<SCEVCouldNotCompute>(RS))
6153 isa<ConstantInt>(RHS) && cast<ConstantInt>(RHS)->
isZero()) {
6159 if (isa<SCEVConstant>(
C) && cast<SCEVConstant>(
C)->getAPInt().ule(1))
6166 if (isa<ConstantInt>(RHS) && cast<ConstantInt>(RHS)->
isZero() &&
6167 isa<ConstantInt>(TrueVal) && cast<ConstantInt>(TrueVal)->
isZero()) {
6169 while (
auto *ZExt = dyn_cast<SCEVZeroExtendExpr>(
X))
6170 X = ZExt->getOperand();
6183 return std::nullopt;
6186static std::optional<const SCEV *>
6188 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6192 "Unexpected operands of a select.");
6203 if (!isa<SCEVConstant>(TrueExpr) && !isa<SCEVConstant>(FalseExpr))
6204 return std::nullopt;
6207 if (isa<SCEVConstant>(TrueExpr)) {
6219static std::optional<const SCEV *>
6222 if (!isa<ConstantInt>(TrueVal) && !isa<ConstantInt>(FalseVal))
6223 return std::nullopt;
6226 const auto *SETrue = SE->
getSCEV(TrueVal);
6227 const auto *SEFalse = SE->
getSCEV(FalseVal);
6231const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6233 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6235 V->getType() ==
TrueVal->getType() &&
6236 "Types of select hands and of the result must match.");
6239 if (!
V->getType()->isIntegerTy(1))
6242 if (std::optional<const SCEV *> S =
6254 if (
auto *CI = dyn_cast<ConstantInt>(
Cond))
6255 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6257 if (
auto *
I = dyn_cast<Instruction>(V)) {
6258 if (
auto *ICI = dyn_cast<ICmpInst>(
Cond)) {
6259 if (std::optional<const SCEV *> S =
6260 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6266 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6272 assert(
GEP->getSourceElementType()->isSized() &&
6273 "GEP source element type must be sized");
6281APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S) {
6291 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6299 return cast<SCEVConstant>(S)->getAPInt();
6309 return GetShiftedByZeros(TZ);
6321 if (
M->hasNoUnsignedWrap()) {
6324 for (
const SCEV *Operand :
M->operands().drop_front())
6332 for (
const SCEV *Operand :
M->operands())
6334 return GetShiftedByZeros(TZ);
6339 if (
N->hasNoUnsignedWrap())
6340 return GetGCDMultiple(
N);
6343 for (
const SCEV *Operand :
N->operands().drop_front())
6345 return GetShiftedByZeros(TZ);
6352 return GetGCDMultiple(cast<SCEVNAryExpr>(S));
6358 .countMinTrailingZeros();
6359 return GetShiftedByZeros(Known);
6368 auto I = ConstantMultipleCache.find(S);
6369 if (
I != ConstantMultipleCache.end())
6372 APInt Result = getConstantMultipleImpl(S);
6373 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6374 assert(InsertPair.second &&
"Should insert a new key");
6375 return InsertPair.first->second;
6391 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6394 return std::nullopt;
6401 UnsignedRanges.erase(AddRec);
6402 SignedRanges.erase(AddRec);
6403 ConstantMultipleCache.erase(AddRec);
6408getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6422 auto *
P = dyn_cast<PHINode>(U->getValue());
6434 Value *Start, *Step;
6441 assert(L && L->getHeader() ==
P->getParent());
6454 case Instruction::AShr:
6455 case Instruction::LShr:
6456 case Instruction::Shl:
6471 KnownStep.getBitWidth() ==
BitWidth);
6474 auto MaxShiftAmt = KnownStep.getMaxValue();
6476 bool Overflow =
false;
6477 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6484 case Instruction::AShr: {
6492 if (KnownStart.isNonNegative())
6495 KnownStart.getMaxValue() + 1);
6496 if (KnownStart.isNegative())
6499 KnownEnd.getMaxValue() + 1);
6502 case Instruction::LShr: {
6511 KnownStart.getMaxValue() + 1);
6513 case Instruction::Shl: {
6517 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6519 KnownEnd.getMaxValue() + 1);
6527ScalarEvolution::getRangeRefIter(
const SCEV *S,
6528 ScalarEvolution::RangeSignHint SignHint) {
6530 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6537 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6538 if (!Seen.
insert(Expr).second)
6544 if (!isa<PHINode>(cast<SCEVUnknown>(Expr)->getValue()))
6571 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6572 const SCEV *
P = WorkList[
I];
6573 auto *UnknownS = dyn_cast<SCEVUnknown>(
P);
6576 for (
const SCEV *
Op :
P->operands())
6581 if (
const PHINode *
P = dyn_cast<PHINode>(UnknownS->getValue())) {
6582 if (!PendingPhiRangesIter.insert(
P).second)
6589 if (!WorkList.
empty()) {
6594 getRangeRef(
P, SignHint);
6596 if (
auto *UnknownS = dyn_cast<SCEVUnknown>(
P))
6597 if (
const PHINode *
P = dyn_cast<PHINode>(UnknownS->getValue()))
6598 PendingPhiRangesIter.erase(
P);
6602 return getRangeRef(S, SignHint, 0);
6609 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6611 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6619 if (
I != Cache.
end())
6628 return getRangeRefIter(S, SignHint);
6636 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6640 ConservativeResult =
6663 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6670 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6677 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6682 return setRange(PtrToInt, SignHint,
X);
6687 unsigned WrapType = OBO::AnyWrap;
6688 if (
Add->hasNoSignedWrap())
6689 WrapType |= OBO::NoSignedWrap;
6690 if (
Add->hasNoUnsignedWrap())
6691 WrapType |= OBO::NoUnsignedWrap;
6692 for (
unsigned i = 1, e =
Add->getNumOperands(); i != e; ++i)
6693 X =
X.addWithNoWrap(getRangeRef(
Add->getOperand(i), SignHint,
Depth + 1),
6694 WrapType, RangeType);
6695 return setRange(
Add, SignHint,
6696 ConservativeResult.intersectWith(
X, RangeType));
6701 for (
unsigned i = 1, e =
Mul->getNumOperands(); i != e; ++i)
6702 X =
X.multiply(getRangeRef(
Mul->getOperand(i), SignHint,
Depth + 1));
6703 return setRange(
Mul, SignHint,
6704 ConservativeResult.intersectWith(
X, RangeType));
6710 return setRange(UDiv, SignHint,
6711 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6719 if (!UnsignedMinValue.
isZero())
6720 ConservativeResult = ConservativeResult.intersectWith(
6730 bool AllNonNeg =
true;
6731 bool AllNonPos =
true;
6732 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6739 ConservativeResult = ConservativeResult.intersectWith(
6744 ConservativeResult = ConservativeResult.intersectWith(
6753 const SCEV *MaxBEScev =
6755 if (!isa<SCEVCouldNotCompute>(MaxBEScev)) {
6756 APInt MaxBECount = cast<SCEVConstant>(MaxBEScev)->getAPInt();
6767 auto RangeFromAffine = getRangeForAffineAR(
6769 ConservativeResult =
6770 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6772 auto RangeFromFactoring = getRangeViaFactoring(
6774 ConservativeResult =
6775 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6781 const SCEV *SymbolicMaxBECount =
6783 if (!isa<SCEVCouldNotCompute>(SymbolicMaxBECount) &&
6786 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6787 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6788 ConservativeResult =
6789 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6794 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6804 ID = Intrinsic::umax;
6807 ID = Intrinsic::smax;
6811 ID = Intrinsic::umin;
6814 ID = Intrinsic::smin;
6820 const auto *NAry = cast<SCEVNAryExpr>(S);
6822 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6824 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6825 return setRange(S, SignHint,
6826 ConservativeResult.intersectWith(
X, RangeType));
6835 ConservativeResult =
6836 ConservativeResult.intersectWith(*MDRange, RangeType);
6841 auto CR = getRangeForUnknownRecurrence(U);
6842 ConservativeResult = ConservativeResult.intersectWith(CR);
6853 if (
U->getType()->isPointerTy()) {
6856 unsigned ptrSize =
DL.getPointerTypeSizeInBits(
U->getType());
6857 int ptrIdxDiff = ptrSize -
BitWidth;
6858 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
6871 ConservativeResult = ConservativeResult.intersectWith(
6875 ConservativeResult = ConservativeResult.intersectWith(
6880 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6887 if ((isa<GlobalVariable>(V) || isa<AllocaInst>(V) ||
6903 ConservativeResult = ConservativeResult.intersectWith(
6909 if (
PHINode *Phi = dyn_cast<PHINode>(V)) {
6911 if (PendingPhiRanges.insert(Phi).second) {
6914 for (
const auto &
Op :
Phi->operands()) {
6916 RangeFromOps = RangeFromOps.unionWith(OpRange);
6918 if (RangeFromOps.isFullSet())
6921 ConservativeResult =
6922 ConservativeResult.intersectWith(RangeFromOps, RangeType);
6923 bool Erased = PendingPhiRanges.erase(Phi);
6924 assert(Erased &&
"Failed to erase Phi properly?");
6930 if (
const auto *II = dyn_cast<IntrinsicInst>(V))
6931 if (II->getIntrinsicID() == Intrinsic::vscale) {
6933 ConservativeResult = ConservativeResult.difference(Disallowed);
6936 return setRange(U, SignHint, std::move(ConservativeResult));
6942 return setRange(S, SignHint, std::move(ConservativeResult));
6951 const APInt &MaxBECount,
6958 if (Step == 0 || MaxBECount == 0)
6965 return ConstantRange::getFull(
BitWidth);
6981 return ConstantRange::getFull(
BitWidth);
6993 APInt MovedBoundary = Descending ? (StartLower - std::move(
Offset))
6994 : (StartUpper + std::move(
Offset));
6999 if (StartRange.
contains(MovedBoundary))
7000 return ConstantRange::getFull(
BitWidth);
7003 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7005 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7014 const APInt &MaxBECount) {
7018 "mismatched bit widths");
7027 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7029 StartSRange, MaxBECount,
7041ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7043 ScalarEvolution::RangeSignHint SignHint) {
7044 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7046 "This only works for non-self-wrapping AddRecs!");
7047 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7050 if (!isa<SCEVConstant>(Step))
7051 return ConstantRange::getFull(
BitWidth);
7059 return ConstantRange::getFull(
BitWidth);
7065 MaxItersWithoutWrap))
7066 return ConstantRange::getFull(
BitWidth);
7093 return RangeBetween;
7098 return ConstantRange::getFull(
BitWidth);
7101 isKnownPredicateViaConstantRanges(LEPred, Start,
End))
7102 return RangeBetween;
7104 isKnownPredicateViaConstantRanges(GEPred, Start,
End))
7105 return RangeBetween;
7106 return ConstantRange::getFull(
BitWidth);
7111 const APInt &MaxBECount) {
7118 "mismatched bit widths");
7120 struct SelectPattern {
7121 Value *Condition =
nullptr;
7127 std::optional<unsigned> CastOp;
7134 if (
auto *SA = dyn_cast<SCEVAddExpr>(S)) {
7137 if (SA->getNumOperands() != 2 || !isa<SCEVConstant>(SA->getOperand(0)))
7140 Offset = cast<SCEVConstant>(SA->getOperand(0))->getAPInt();
7141 S = SA->getOperand(1);
7145 if (
auto *SCast = dyn_cast<SCEVIntegralCastExpr>(S)) {
7147 S = SCast->getOperand();
7152 auto *SU = dyn_cast<SCEVUnknown>(S);
7157 Condition =
nullptr;
7189 bool isRecognized() {
return Condition !=
nullptr; }
7192 SelectPattern StartPattern(*
this,
BitWidth, Start);
7193 if (!StartPattern.isRecognized())
7194 return ConstantRange::getFull(
BitWidth);
7196 SelectPattern StepPattern(*
this,
BitWidth, Step);
7197 if (!StepPattern.isRecognized())
7198 return ConstantRange::getFull(
BitWidth);
7200 if (StartPattern.Condition != StepPattern.Condition) {
7204 return ConstantRange::getFull(
BitWidth);
7221 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount);
7223 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount);
7245ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7246 if (
auto *AddRec = dyn_cast<SCEVAddRecExpr>(S))
7248 if (
auto *U = dyn_cast<SCEVUnknown>(S))
7249 if (
auto *
I = dyn_cast<Instruction>(
U->getValue()))
7261 auto pushOp = [&](
const SCEV *S) {
7262 if (!Visited.
insert(S).second)
7265 if (Visited.
size() > 30) {
7272 for (
const auto *S : Ops)
7276 while (!Worklist.
empty()) {
7278 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7279 if (!Bound || DT.
dominates(Bound, DefI))
7292 return getDefiningScopeBound(Ops, Discard);
7295bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7297 if (
A->getParent() ==
B->getParent() &&
7303 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7304 BLoop->getLoopPreheader() ==
A->getParent() &&
7306 A->getParent()->end()) &&
7314bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7331 for (
const Use &
Op :
I->operands()) {
7337 auto *DefI = getDefiningScopeBound(SCEVOps);
7338 return isGuaranteedToTransferExecutionTo(DefI,
I);
7341bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7343 if (isSCEVExprNeverPoison(
I))
7354 auto *ExitingBB =
L->getExitingBlock();
7367 while (!Worklist.
empty()) {
7370 for (
const Use &U : Poison->
uses()) {
7371 const Instruction *PoisonUser = cast<Instruction>(
U.getUser());
7377 if (KnownPoison.
insert(PoisonUser).second)
7385ScalarEvolution::LoopProperties
7386ScalarEvolution::getLoopProperties(
const Loop *L) {
7387 using LoopProperties = ScalarEvolution::LoopProperties;
7389 auto Itr = LoopPropertiesCache.find(L);
7390 if (Itr == LoopPropertiesCache.end()) {
7392 if (
auto *SI = dyn_cast<StoreInst>(
I))
7393 return !
SI->isSimple();
7395 return I->mayThrow() ||
I->mayWriteToMemory();
7398 LoopProperties LP = {
true,
7401 for (
auto *BB :
L->getBlocks())
7402 for (
auto &
I : *BB) {
7404 LP.HasNoAbnormalExits =
false;
7405 if (HasSideEffects(&
I))
7406 LP.HasNoSideEffects =
false;
7407 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7411 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7412 assert(InsertPair.second &&
"We just checked!");
7413 Itr = InsertPair.first;
7426const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7432 Stack.emplace_back(V,
true);
7433 Stack.emplace_back(V,
false);
7434 while (!Stack.empty()) {
7435 auto E = Stack.pop_back_val();
7436 Value *CurV =
E.getPointer();
7442 const SCEV *CreatedSCEV =
nullptr;
7445 CreatedSCEV = createSCEV(CurV);
7450 CreatedSCEV = getOperandsToCreate(CurV, Ops);
7454 insertValueToMap(CurV, CreatedSCEV);
7458 Stack.emplace_back(CurV,
true);
7460 Stack.emplace_back(
Op,
false);
7479 }
else if (
ConstantInt *CI = dyn_cast<ConstantInt>(V))
7481 else if (isa<GlobalAlias>(V))
7483 else if (!isa<ConstantExpr>(V))
7489 bool IsConstArg = isa<ConstantInt>(BO->RHS);
7490 switch (BO->Opcode) {
7491 case Instruction::Add:
7492 case Instruction::Mul: {
7505 dyn_cast<Instruction>(V));
7507 (BO->Opcode == Instruction::Add &&
7508 (NewBO->Opcode != Instruction::Add &&
7509 NewBO->Opcode != Instruction::Sub)) ||
7510 (BO->Opcode == Instruction::Mul &&
7511 NewBO->Opcode != Instruction::Mul)) {
7517 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7518 auto *
I = dyn_cast<Instruction>(BO->
Op);
7528 case Instruction::Sub:
7529 case Instruction::UDiv:
7530 case Instruction::URem:
7532 case Instruction::AShr:
7533 case Instruction::Shl:
7534 case Instruction::Xor:
7538 case Instruction::And:
7539 case Instruction::Or:
7543 case Instruction::LShr:
7555 switch (
U->getOpcode()) {
7556 case Instruction::Trunc:
7557 case Instruction::ZExt:
7558 case Instruction::SExt:
7559 case Instruction::PtrToInt:
7563 case Instruction::BitCast:
7570 case Instruction::SDiv:
7571 case Instruction::SRem:
7576 case Instruction::GetElementPtr:
7577 assert(cast<GEPOperator>(U)->getSourceElementType()->isSized() &&
7578 "GEP source element type must be sized");
7583 case Instruction::IntToPtr:
7586 case Instruction::PHI:
7590 case Instruction::Select: {
7592 auto CanSimplifyToUnknown = [
this,
U]() {
7593 if (
U->getType()->isIntegerTy(1) || isa<ConstantInt>(
U->getOperand(0)))
7596 auto *ICI = dyn_cast<ICmpInst>(
U->getOperand(0));
7603 if (!(isa<ConstantInt>(RHS) && cast<ConstantInt>(RHS)->
isZero()))
7610 if (CanSimplifyToUnknown())
7613 for (
Value *Inc :
U->operands())
7618 case Instruction::Call:
7619 case Instruction::Invoke:
7620 if (
Value *RV = cast<CallBase>(U)->getReturnedArgOperand()) {
7625 if (
auto *II = dyn_cast<IntrinsicInst>(U)) {
7626 switch (II->getIntrinsicID()) {
7627 case Intrinsic::abs:
7630 case Intrinsic::umax:
7631 case Intrinsic::umin:
7632 case Intrinsic::smax:
7633 case Intrinsic::smin:
7634 case Intrinsic::usub_sat:
7635 case Intrinsic::uadd_sat:
7639 case Intrinsic::start_loop_iterations:
7640 case Intrinsic::annotation:
7641 case Intrinsic::ptr_annotation:
7654const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7665 }
else if (
ConstantInt *CI = dyn_cast<ConstantInt>(V))
7667 else if (isa<GlobalAlias>(V))
7669 else if (!isa<ConstantExpr>(V))
7678 switch (BO->Opcode) {
7679 case Instruction::Add: {
7705 if (BO->Opcode == Instruction::Sub)
7713 if (BO->Opcode == Instruction::Sub)
7719 dyn_cast<Instruction>(V));
7720 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7721 NewBO->Opcode != Instruction::Sub)) {
7731 case Instruction::Mul: {
7751 dyn_cast<Instruction>(V));
7752 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7761 case Instruction::UDiv:
7765 case Instruction::URem:
7769 case Instruction::Sub: {
7772 Flags = getNoWrapFlagsFromUB(BO->
Op);
7777 case Instruction::And:
7780 if (
ConstantInt *CI = dyn_cast<ConstantInt>(BO->RHS)) {
7783 if (CI->isMinusOne())
7785 const APInt &
A = CI->getValue();
7791 unsigned LZ =
A.countl_zero();
7792 unsigned TZ =
A.countr_zero();
7796 0, &AC,
nullptr, &DT);
7798 APInt EffectiveMask =
7800 if ((LZ != 0 || TZ != 0) && !((~
A & ~Known.
Zero) & EffectiveMask)) {
7803 const SCEV *ShiftedLHS =
nullptr;
7804 if (
auto *LHSMul = dyn_cast<SCEVMulExpr>(LHS)) {
7805 if (
auto *OpC = dyn_cast<SCEVConstant>(LHSMul->getOperand(0))) {
7807 unsigned MulZeros = OpC->getAPInt().countr_zero();
7808 unsigned GCD = std::min(MulZeros, TZ);
7813 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
7835 case Instruction::Or:
7844 case Instruction::Xor:
7845 if (
ConstantInt *CI = dyn_cast<ConstantInt>(BO->RHS)) {
7847 if (CI->isMinusOne())
7854 if (
auto *LBO = dyn_cast<BinaryOperator>(BO->LHS))
7855 if (
ConstantInt *LCI = dyn_cast<ConstantInt>(LBO->getOperand(1)))
7856 if (LBO->getOpcode() == Instruction::And &&
7857 LCI->getValue() == CI->getValue())
7859 dyn_cast<SCEVZeroExtendExpr>(
getSCEV(BO->LHS))) {
7861 const SCEV *Z0 =
Z->getOperand();
7868 if (CI->getValue().isMask(Z0TySize))
7874 APInt Trunc = CI->getValue().
trunc(Z0TySize);
7883 case Instruction::Shl:
7885 if (
ConstantInt *SA = dyn_cast<ConstantInt>(BO->RHS)) {
7901 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
7915 case Instruction::AShr:
7936 Operator *
L = dyn_cast<Operator>(BO->LHS);
7937 const SCEV *AddTruncateExpr =
nullptr;
7939 const SCEV *AddConstant =
nullptr;
7941 if (L &&
L->getOpcode() == Instruction::Add) {
7947 Operator *LShift = dyn_cast<Operator>(
L->getOperand(0));
7948 ConstantInt *AddOperandCI = dyn_cast<ConstantInt>(
L->getOperand(1));
7949 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
7952 ShlAmtCI = dyn_cast<ConstantInt>(LShift->
getOperand(1));
7964 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
7970 ShlAmtCI = dyn_cast<ConstantInt>(
L->getOperand(1));
7974 if (AddTruncateExpr && ShlAmtCI) {
7990 const SCEV *CompositeExpr =
7992 if (
L->getOpcode() != Instruction::Shl)
7993 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8002 switch (
U->getOpcode()) {
8003 case Instruction::Trunc:
8006 case Instruction::ZExt:
8009 case Instruction::SExt:
8011 dyn_cast<Instruction>(V))) {
8019 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8020 Type *Ty =
U->getType();
8028 case Instruction::BitCast:
8034 case Instruction::PtrToInt: {
8037 Type *DstIntTy =
U->getType();
8041 if (isa<SCEVCouldNotCompute>(IntOp))
8045 case Instruction::IntToPtr:
8049 case Instruction::SDiv:
8056 case Instruction::SRem:
8063 case Instruction::GetElementPtr:
8064 return createNodeForGEP(cast<GEPOperator>(U));
8066 case Instruction::PHI:
8067 return createNodeForPHI(cast<PHINode>(U));
8069 case Instruction::Select:
8070 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8073 case Instruction::Call:
8074 case Instruction::Invoke:
8075 if (
Value *RV = cast<CallBase>(U)->getReturnedArgOperand())
8078 if (
auto *II = dyn_cast<IntrinsicInst>(U)) {
8079 switch (II->getIntrinsicID()) {
8080 case Intrinsic::abs:
8082 getSCEV(II->getArgOperand(0)),
8083 cast<ConstantInt>(II->getArgOperand(1))->
isOne());
8084 case Intrinsic::umax:
8088 case Intrinsic::umin:
8092 case Intrinsic::smax:
8096 case Intrinsic::smin:
8100 case Intrinsic::usub_sat: {
8106 case Intrinsic::uadd_sat: {
8112 case Intrinsic::start_loop_iterations:
8113 case Intrinsic::annotation:
8114 case Intrinsic::ptr_annotation:
8117 return getSCEV(II->getArgOperand(0));
8118 case Intrinsic::vscale:
8135 if (isa<SCEVCouldNotCompute>(ExitCount))
8138 auto *ExitCountType = ExitCount->
getType();
8139 assert(ExitCountType->isIntegerTy());
8141 1 + ExitCountType->getScalarSizeInBits());
8148 if (isa<SCEVCouldNotCompute>(ExitCount))
8154 auto CanAddOneWithoutOverflow = [&]() {
8156 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8167 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8197 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8198 assert(L->isLoopExiting(ExitingBlock) &&
8199 "Exiting block must actually branch out of the loop!");
8206 const auto *MaxExitCount =
8213 L->getExitingBlocks(ExitingBlocks);
8215 std::optional<unsigned> Res;
8216 for (
auto *ExitingBB : ExitingBlocks) {
8220 Res = (
unsigned)std::gcd(*Res, Multiple);
8222 return Res.value_or(1);
8226 const SCEV *ExitCount) {
8256 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8257 assert(L->isLoopExiting(ExitingBlock) &&
8258 "Exiting block must actually branch out of the loop!");
8268 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8270 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8272 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8280 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8287 return getBackedgeTakenInfo(L).getExact(L,
this);
8289 return getBackedgeTakenInfo(L).getConstantMax(
this);
8291 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8297 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8307 for (
PHINode &PN : Header->phis())
8308 if (Visited.
insert(&PN).second)
8312const ScalarEvolution::BackedgeTakenInfo &
8313ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8314 auto &BTI = getBackedgeTakenInfo(L);
8315 if (BTI.hasFullInfo())
8318 auto Pair = PredicatedBackedgeTakenCounts.insert({
L, BackedgeTakenInfo()});
8321 return Pair.first->second;
8323 BackedgeTakenInfo
Result =
8324 computeBackedgeTakenCount(L,
true);
8326 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8329ScalarEvolution::BackedgeTakenInfo &
8330ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8336 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8337 BackedgeTakenCounts.insert({
L, BackedgeTakenInfo()});
8339 return Pair.first->second;
8344 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8351 if (
Result.hasAnyInfo()) {
8354 auto LoopUsersIt = LoopUsers.find(L);
8355 if (LoopUsersIt != LoopUsers.end())
8357 forgetMemoizedResults(ToForget);
8360 for (
PHINode &PN :
L->getHeader()->phis())
8361 ConstantEvolutionLoopExitValue.erase(&PN);
8369 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8378 BackedgeTakenCounts.clear();
8379 PredicatedBackedgeTakenCounts.clear();
8380 BECountUsers.clear();
8381 LoopPropertiesCache.clear();
8382 ConstantEvolutionLoopExitValue.clear();
8383 ValueExprMap.
clear();
8384 ValuesAtScopes.clear();
8385 ValuesAtScopesUsers.clear();
8386 LoopDispositions.clear();
8387 BlockDispositions.clear();
8388 UnsignedRanges.clear();
8389 SignedRanges.clear();
8390 ExprValueMap.
clear();
8392 ConstantMultipleCache.clear();
8393 PredicatedSCEVRewrites.clear();
8395 FoldCacheUser.clear();
8397void ScalarEvolution::visitAndClearUsers(
8401 while (!Worklist.
empty()) {
8408 if (It != ValueExprMap.
end()) {
8409 eraseValueFromMap(It->first);
8411 if (
PHINode *PN = dyn_cast<PHINode>(
I))
8412 ConstantEvolutionLoopExitValue.erase(PN);
8426 while (!LoopWorklist.
empty()) {
8430 forgetBackedgeTakenCounts(CurrL,
false);
8431 forgetBackedgeTakenCounts(CurrL,
true);
8434 for (
auto I = PredicatedSCEVRewrites.begin();
8435 I != PredicatedSCEVRewrites.end();) {
8436 std::pair<const SCEV *, const Loop *> Entry =
I->first;
8437 if (Entry.second == CurrL)
8438 PredicatedSCEVRewrites.erase(
I++);
8443 auto LoopUsersItr = LoopUsers.find(CurrL);
8444 if (LoopUsersItr != LoopUsers.end()) {
8445 ToForget.
insert(ToForget.
end(), LoopUsersItr->second.begin(),
8446 LoopUsersItr->second.end());
8451 visitAndClearUsers(Worklist, Visited, ToForget);
8453 LoopPropertiesCache.erase(CurrL);
8456 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8458 forgetMemoizedResults(ToForget);
8475 visitAndClearUsers(Worklist, Visited, ToForget);
8477 forgetMemoizedResults(ToForget);
8489 struct InvalidationRootCollector {
8493 InvalidationRootCollector(
Loop *L) : L(L) {}
8495 bool follow(
const SCEV *S) {
8496 if (
auto *SU = dyn_cast<SCEVUnknown>(S)) {
8497 if (
auto *
I = dyn_cast<Instruction>(SU->getValue()))
8500 }
else if (
auto *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
8501 if (L->contains(AddRec->
getLoop()))
8506 bool isDone()
const {
return false; }
8509 InvalidationRootCollector
C(L);
8511 forgetMemoizedResults(
C.Roots);
8524 BlockDispositions.clear();
8525 LoopDispositions.clear();
8542 while (!Worklist.
empty()) {
8544 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8545 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8546 if (!LoopDispoRemoved && !BlockDispoRemoved)
8548 auto Users = SCEVUsers.find(Curr);
8549 if (
Users != SCEVUsers.end())
8566 if (!isComplete() || ExitNotTaken.empty())
8577 for (
const auto &ENT : ExitNotTaken) {
8578 const SCEV *BECount = ENT.ExactNotTaken;
8581 "We should only have known counts for exiting blocks that dominate "
8587 for (
const auto *
P : ENT.Predicates)
8590 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8591 "Predicate should be always true!");
8602ScalarEvolution::BackedgeTakenInfo::getExact(
const BasicBlock *ExitingBlock,
8604 for (
const auto &ENT : ExitNotTaken)
8605 if (ENT.ExitingBlock == ExitingBlock && ENT.hasAlwaysTruePredicate())
8606 return ENT.ExactNotTaken;
8611const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8613 for (
const auto &ENT : ExitNotTaken)
8614 if (ENT.ExitingBlock == ExitingBlock && ENT.hasAlwaysTruePredicate())
8615 return ENT.ConstantMaxNotTaken;
8620const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8622 for (
const auto &ENT : ExitNotTaken)
8623 if (ENT.ExitingBlock == ExitingBlock && ENT.hasAlwaysTruePredicate())
8624 return ENT.SymbolicMaxNotTaken;
8631ScalarEvolution::BackedgeTakenInfo::getConstantMax(
ScalarEvolution *SE)
const {
8632 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8633 return !ENT.hasAlwaysTruePredicate();
8636 if (!getConstantMax() ||
any_of(ExitNotTaken, PredicateNotAlwaysTrue))
8639 assert((isa<SCEVCouldNotCompute>(getConstantMax()) ||
8640 isa<SCEVConstant>(getConstantMax())) &&
8641 "No point in having a non-constant max backedge taken count!");
8642 return getConstantMax();
8646ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
const Loop *L,
8649 SymbolicMax = SE->computeSymbolicMaxBackedgeTakenCount(L);
8653bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8655 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8656 return !ENT.hasAlwaysTruePredicate();
8658 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8665 const SCEV *
E,
const SCEV *ConstantMaxNotTaken,
8666 const SCEV *SymbolicMaxNotTaken,
bool MaxOrZero,
8668 : ExactNotTaken(
E), ConstantMaxNotTaken(ConstantMaxNotTaken),
8669 SymbolicMaxNotTaken(SymbolicMaxNotTaken), MaxOrZero(MaxOrZero) {
8680 "Exact is not allowed to be less precise than Constant Max");
8683 "Exact is not allowed to be less precise than Symbolic Max");
8686 "Symbolic Max is not allowed to be less precise than Constant Max");
8689 "No point in having a non-constant max backedge taken count!");
8690 for (
const auto *PredSet : PredSetList)
8691 for (
const auto *
P : *PredSet)
8693 assert((isa<SCEVCouldNotCompute>(
E) || !
E->getType()->isPointerTy()) &&
8694 "Backedge count should be int");
8697 "Max backedge count should be int");
8701 const SCEV *
E,
const SCEV *ConstantMaxNotTaken,
8702 const SCEV *SymbolicMaxNotTaken,
bool MaxOrZero,
8704 :
ExitLimit(
E, ConstantMaxNotTaken, SymbolicMaxNotTaken, MaxOrZero,
8709ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8711 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8712 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8713 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8715 ExitNotTaken.reserve(ExitCounts.
size());
8716 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8717 std::back_inserter(ExitNotTaken),
8718 [&](
const EdgeExitInfo &EEI) {
8719 BasicBlock *ExitBB = EEI.first;
8720 const ExitLimit &EL = EEI.second;
8721 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
8722 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
8725 assert((isa<SCEVCouldNotCompute>(ConstantMax) ||
8726 isa<SCEVConstant>(ConstantMax)) &&
8727 "No point in having a non-constant max backedge taken count!");
8731ScalarEvolution::BackedgeTakenInfo
8732ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
8733 bool AllowPredicates) {
8735 L->getExitingBlocks(ExitingBlocks);
8737 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8740 bool CouldComputeBECount =
true;
8742 const SCEV *MustExitMaxBECount =
nullptr;
8743 const SCEV *MayExitMaxBECount =
nullptr;
8744 bool MustExitMaxOrZero =
false;
8749 for (
unsigned i = 0, e = ExitingBlocks.
size(); i != e; ++i) {
8755 if (
auto *BI = dyn_cast<BranchInst>(ExitBB->
getTerminator()))
8756 if (
auto *CI = dyn_cast<ConstantInt>(BI->
getCondition())) {
8758 if (ExitIfTrue == CI->
isZero())
8762 ExitLimit EL = computeExitLimit(L, ExitBB, AllowPredicates);
8764 assert((AllowPredicates || EL.Predicates.empty()) &&
8765 "Predicated exit limit when predicates are not allowed!");
8770 ++NumExitCountsComputed;
8774 CouldComputeBECount =
false;
8781 "Exact is known but symbolic isn't?");
8782 ++NumExitCountsNotComputed;
8798 if (!MustExitMaxBECount) {
8799 MustExitMaxBECount = EL.ConstantMaxNotTaken;
8800 MustExitMaxOrZero = EL.MaxOrZero;
8803 EL.ConstantMaxNotTaken);
8807 MayExitMaxBECount = EL.ConstantMaxNotTaken;
8810 EL.ConstantMaxNotTaken);
8814 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
8818 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.
size() == 1);
8824 for (
const auto &Pair : ExitCounts) {
8825 if (!isa<SCEVConstant>(Pair.second.ExactNotTaken))
8826 BECountUsers[Pair.second.ExactNotTaken].insert({L, AllowPredicates});
8827 if (!isa<SCEVConstant>(Pair.second.SymbolicMaxNotTaken))
8828 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
8829 {L, AllowPredicates});
8831 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
8832 MaxBECount, MaxOrZero);
8836ScalarEvolution::computeExitLimit(
const Loop *L,
BasicBlock *ExitingBlock,
8837 bool AllowPredicates) {
8838 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
8842 if (!Latch || !DT.
dominates(ExitingBlock, Latch))
8845 bool IsOnlyExit = (
L->getExitingBlock() !=
nullptr);
8847 if (
BranchInst *BI = dyn_cast<BranchInst>(Term)) {
8851 "It should have one successor in loop and one exit block!");
8858 if (
SwitchInst *SI = dyn_cast<SwitchInst>(Term)) {
8862 if (!
L->contains(SBB)) {
8867 assert(Exit &&
"Exiting block must have at least one exit");
8868 return computeExitLimitFromSingleExitSwitch(
8877 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
8878 bool AllowPredicates) {
8879 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
8880 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
8881 ControlsOnlyExit, AllowPredicates);
8884std::optional<ScalarEvolution::ExitLimit>
8885ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
8886 bool ExitIfTrue,
bool ControlsOnlyExit,
8887 bool AllowPredicates) {
8889 (void)this->ExitIfTrue;
8890 (void)this->AllowPredicates;
8892 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
8893 this->AllowPredicates == AllowPredicates &&
8894 "Variance in assumed invariant key components!");
8895 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
8896 if (Itr == TripCountMap.end())
8897 return std::nullopt;
8901void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
8903 bool ControlsOnlyExit,
8904 bool AllowPredicates,
8905 const ExitLimit &EL) {
8906 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
8907 this->AllowPredicates == AllowPredicates &&
8908 "Variance in assumed invariant key components!");
8910 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
8911 assert(InsertResult.second &&
"Expected successful insertion!");
8917 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
8918 bool ControlsOnlyExit,
bool AllowPredicates) {
8920 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
8924 ExitLimit EL = computeExitLimitFromCondImpl(
8925 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
8926 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
8931 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
8932 bool ControlsOnlyExit,
bool AllowPredicates) {
8934 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
8935 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates))
8936 return *LimitFromBinOp;
8940 if (
ICmpInst *ExitCondICmp = dyn_cast<ICmpInst>(ExitCond)) {
8942 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
8943 if (EL.hasFullInfo() || !AllowPredicates)
8947 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
8956 if (
ConstantInt *CI = dyn_cast<ConstantInt>(ExitCond)) {
8982 auto EL = computeExitLimitFromICmp(L, Pred, LHS,
getConstant(NewRHSC),
8983 ControlsOnlyExit, AllowPredicates);
8984 if (EL.hasAnyInfo())
8989 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
8992std::optional<ScalarEvolution::ExitLimit>
8993ScalarEvolution::computeExitLimitFromCondFromBinOp(
8994 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
8995 bool ControlsOnlyExit,
bool AllowPredicates) {
9004 return std::nullopt;
9009 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9010 ExitLimit EL0 = computeExitLimitFromCondCached(
9011 Cache, L, Op0, ExitIfTrue, ControlsOnlyExit && !EitherMayExit,
9013 ExitLimit EL1 = computeExitLimitFromCondCached(
9014 Cache, L, Op1, ExitIfTrue, ControlsOnlyExit && !EitherMayExit,
9018 const Constant *NeutralElement = ConstantInt::get(ExitCond->
getType(), IsAnd);
9019 if (isa<ConstantInt>(Op1))
9020 return Op1 == NeutralElement ? EL0 : EL1;
9021 if (isa<ConstantInt>(Op0))
9022 return Op0 == NeutralElement ? EL1 : EL0;
9027 if (EitherMayExit) {
9028 bool UseSequentialUMin = !isa<BinaryOperator>(ExitCond);
9037 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9039 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9042 EL1.ConstantMaxNotTaken);
9044 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9046 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9049 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9053 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9054 BECount = EL0.ExactNotTaken;
9063 if (isa<SCEVCouldNotCompute>(ConstantMaxBECount) &&
9064 !isa<SCEVCouldNotCompute>(BECount))
9066 if (isa<SCEVCouldNotCompute>(SymbolicMaxBECount))
9067 SymbolicMaxBECount =
9068 isa<SCEVCouldNotCompute>(BECount) ? ConstantMaxBECount : BECount;
9069 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9070 { &EL0.Predicates, &EL1.Predicates });
9074 const Loop *L,
ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9075 bool AllowPredicates) {
9087 ExitLimit EL = computeExitLimitFromICmp(L, Pred, LHS, RHS, ControlsOnlyExit,
9089 if (EL.hasAnyInfo())
9092 auto *ExhaustiveCount =
9093 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9095 if (!isa<SCEVCouldNotCompute>(ExhaustiveCount))
9096 return ExhaustiveCount;
9098 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9103 bool ControlsOnlyExit,
bool AllowPredicates) {
9124 if (
const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS))
9125 if (
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
9132 if (!isa<SCEVCouldNotCompute>(Ret))
return Ret;
9143 auto *InnerLHS =
LHS;
9144 if (
auto *ZExt = dyn_cast<SCEVZeroExtendExpr>(LHS))
9145 InnerLHS = ZExt->getOperand();
9146 if (
const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(InnerLHS)) {
9149 StrideC && StrideC->getAPInt().isPowerOf2()) {
9164 if (isa<SCEVCouldNotCompute>(LHS))
9169 if (isa<SCEVCouldNotCompute>(RHS))
9172 ExitLimit EL = howFarToZero(
getMinusSCEV(LHS, RHS), L, ControlsOnlyExit,
9174 if (EL.hasAnyInfo())
9182 if (isa<SCEVCouldNotCompute>(LHS))
9187 if (isa<SCEVCouldNotCompute>(RHS))
9190 ExitLimit EL = howFarToNonZero(
getMinusSCEV(LHS, RHS), L);
9191 if (EL.hasAnyInfo())
return EL;
9206 ExitLimit EL = howManyLessThans(LHS, RHS, L, IsSigned, ControlsOnlyExit,
9208 if (EL.hasAnyInfo())
9224 ExitLimit EL = howManyGreaterThans(LHS, RHS, L, IsSigned, ControlsOnlyExit,
9226 if (EL.hasAnyInfo())
9238ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9241 bool ControlsOnlyExit) {
9242 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9245 if (
Switch->getDefaultDest() == ExitingBlock)
9249 "Default case must not exit the loop!");
9254 ExitLimit EL = howFarToZero(
getMinusSCEV(LHS, RHS), L, ControlsOnlyExit);
9255 if (EL.hasAnyInfo())
9266 assert(isa<SCEVConstant>(Val) &&
9267 "Evaluation of SCEV at constant didn't fold correctly?");
9268 return cast<SCEVConstant>(Val)->getValue();
9281 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9287 auto MatchPositiveShift =
9290 using namespace PatternMatch;
9294 OutOpCode = Instruction::LShr;
9296 OutOpCode = Instruction::AShr;
9298 OutOpCode = Instruction::Shl;
9313 auto MatchShiftRecurrence =
9315 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9330 if (MatchPositiveShift(LHS, V, OpC)) {
9331 PostShiftOpCode = OpC;
9336 PNOut = dyn_cast<PHINode>(LHS);
9337 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9340 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9346 MatchPositiveShift(BEValue, OpLHS, OpCodeOut) &&
9353 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9358 if (!MatchShiftRecurrence(LHS, PN, OpCode))
9375 case Instruction::AShr: {
9381 auto *Ty = cast<IntegerType>(
RHS->
getType());
9383 StableValue = ConstantInt::get(Ty, 0);
9385 StableValue = ConstantInt::get(Ty, -1,
true);
9391 case Instruction::LShr:
9392 case Instruction::Shl:
9395 StableValue = ConstantInt::get(cast<IntegerType>(
RHS->
getType()), 0);
9402 "Otherwise cannot be an operand to a branch instruction");
9404 if (
Result->isZeroValue()) {
9406 const SCEV *UpperBound =
9417 if (isa<BinaryOperator>(
I) || isa<CmpInst>(
I) ||
9418 isa<SelectInst>(
I) || isa<CastInst>(
I) || isa<GetElementPtrInst>(
I) ||
9419 isa<LoadInst>(
I) || isa<ExtractValueInst>(
I))
9422 if (
const CallInst *CI = dyn_cast<CallInst>(
I))
9423 if (
const Function *F = CI->getCalledFunction())
9432 if (!L->contains(
I))
return false;
9434 if (isa<PHINode>(
I)) {
9437 return L->getHeader() ==
I->getParent();
9458 if (isa<Constant>(
Op))
continue;
9463 PHINode *
P = dyn_cast<PHINode>(OpInst);
9494 if (
PHINode *PN = dyn_cast<PHINode>(
I))
9511 if (
Constant *
C = dyn_cast<Constant>(V))
return C;
9513 if (!
I)
return nullptr;
9524 if (isa<PHINode>(
I))
return nullptr;
9526 std::vector<Constant*>
Operands(
I->getNumOperands());
9528 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9529 Instruction *Operand = dyn_cast<Instruction>(
I->getOperand(i));
9531 Operands[i] = dyn_cast<Constant>(
I->getOperand(i));
9537 if (!
C)
return nullptr;
9558 if (IncomingVal != CurrentVal) {
9561 IncomingVal = CurrentVal;
9573ScalarEvolution::getConstantEvolutionLoopExitValue(
PHINode *PN,
9576 auto I = ConstantEvolutionLoopExitValue.find(PN);
9577 if (
I != ConstantEvolutionLoopExitValue.end())
9581 return ConstantEvolutionLoopExitValue[PN] =
nullptr;
9583 Constant *&RetVal = ConstantEvolutionLoopExitValue[PN];
9587 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9595 CurrentIterVals[&
PHI] = StartCST;
9597 if (!CurrentIterVals.
count(PN))
9598 return RetVal =
nullptr;
9604 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9607 unsigned IterationNum = 0;
9609 for (; ; ++IterationNum) {
9610 if (IterationNum == NumIterations)
9611 return RetVal = CurrentIterVals[PN];
9620 NextIterVals[PN] = NextPHI;
9622 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9628 for (
const auto &
I : CurrentIterVals) {
9630 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9635 for (
const auto &
I : PHIsToCompute) {
9639 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9642 if (NextPHI !=
I.second)
9643 StoppedEvolving =
false;
9648 if (StoppedEvolving)
9649 return RetVal = CurrentIterVals[PN];
9651 CurrentIterVals.swap(NextIterVals);
9655const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
9667 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9670 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
9674 CurrentIterVals[&
PHI] = StartCST;
9676 if (!CurrentIterVals.
count(PN))
9684 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
9685 auto *CondVal = dyn_cast_or_null<ConstantInt>(
9691 if (CondVal->getValue() ==
uint64_t(ExitWhen)) {
9692 ++NumBruteForceTripCountsComputed;
9703 for (
const auto &
I : CurrentIterVals) {
9705 if (!
PHI ||
PHI->getParent() != Header)
continue;
9710 if (NextPHI)
continue;
9712 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9715 CurrentIterVals.swap(NextIterVals);
9726 for (
auto &LS : Values)
9728 return LS.second ? LS.second : V;
9733 const SCEV *
C = computeSCEVAtScope(V, L);
9734 for (
auto &LS :
reverse(ValuesAtScopes[V]))
9735 if (LS.first == L) {
9737 if (!isa<SCEVConstant>(
C))
9738 ValuesAtScopesUsers[
C].push_back({L, V});
9749 switch (V->getSCEVType()) {
9755 return cast<SCEVConstant>(V)->getValue();
9757 return dyn_cast<Constant>(cast<SCEVUnknown>(V)->getValue());
9782 assert(!
C->getType()->isPointerTy() &&
9783 "Can only have one pointer, and it must be last");
9810ScalarEvolution::getWithOperands(
const SCEV *S,
9819 auto *AddRec = cast<SCEVAddRecExpr>(S);
9823 return getAddExpr(NewOps, cast<SCEVAddExpr>(S)->getNoWrapFlags());
9825 return getMulExpr(NewOps, cast<SCEVMulExpr>(S)->getNoWrapFlags());
9845const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
9846 switch (
V->getSCEVType()) {
9857 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
9868 for (++i; i !=
e; ++i)
9873 AddRec = dyn_cast<SCEVAddRecExpr>(FoldedRec);
9912 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
9914 if (OpAtScope != Ops[i]) {
9922 for (++i; i !=
e; ++i) {
9927 return getWithOperands(V, NewOps);
9941 if (
PHINode *PN = dyn_cast<PHINode>(
I)) {
9942 const Loop *CurrLoop = this->LI[
I->getParent()];
9953 if (BackedgeTakenCount->
isZero()) {
9954 Value *InitValue =
nullptr;
9955 bool MultipleInitValues =
false;
9961 MultipleInitValues =
true;
9966 if (!MultipleInitValues && InitValue)
9971 if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) &&
9975 unsigned InLoopPred =
9981 if (
auto *BTCC = dyn_cast<SCEVConstant>(BackedgeTakenCount)) {
9986 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10002 bool MadeImprovement =
false;
10017 MadeImprovement |= OrigV != OpV;
10022 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10027 if (!MadeImprovement)
10047const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10049 return stripInjectiveFunctions(ZExt->getOperand());
10051 return stripInjectiveFunctions(SExt->getOperand());
10067 assert(
A != 0 &&
"A must be non-zero.");
10089 APInt AD =
A.lshr(Mult2).zext(BW + 1);
10091 Mod.setBit(BW - Mult2);
10111static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10117 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10118 << *AddRec <<
'\n');
10121 if (!LC || !MC || !
NC) {
10122 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10123 return std::nullopt;
10129 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10137 N =
N.sext(NewWidth);
10138 M = M.sext(NewWidth);
10139 L = L.sext(NewWidth);
10156 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10157 <<
", multiplied by " <<
T <<
'\n');
10166 std::optional<APInt>
Y) {
10168 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10171 return XW.
slt(YW) ? *
X : *
Y;
10174 return std::nullopt;
10175 return X ? *
X : *
Y;
10192 return std::nullopt;
10193 unsigned W =
X->getBitWidth();
10213static std::optional<APInt>
10219 return std::nullopt;
10222 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10223 std::optional<APInt>
X =
10226 return std::nullopt;
10231 return std::nullopt;
10246static std::optional<APInt>
10250 "Starting value of addrec should be 0");
10251 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10252 << Range <<
", addrec " << *AddRec <<
'\n');
10256 "Addrec's initial value should be in range");
10262 return std::nullopt;
10272 auto SolveForBoundary =
10273 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10276 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10277 << Bound <<
" (before multiplying by " << M <<
")\n");
10280 std::optional<APInt> SO;
10283 "signed overflow\n");
10287 "unsigned overflow\n");
10288 std::optional<APInt> UO =
10291 auto LeavesRange = [&] (
const APInt &
X) {
10294 if (Range.contains(V0->
getValue()))
10299 if (Range.contains(V1->
getValue()))
10308 return {std::nullopt,
false};
10313 if (LeavesRange(*Min))
10314 return { Min,
true };
10315 std::optional<APInt> Max = Min == SO ? UO : SO;
10316 if (LeavesRange(*Max))
10317 return { Max,
true };
10320 return {std::nullopt,
true};
10325 APInt Lower = Range.getLower().sext(
A.getBitWidth()) - 1;
10326 APInt Upper = Range.getUpper().sext(
A.getBitWidth());
10327 auto SL = SolveForBoundary(
Lower);
10328 auto SU = SolveForBoundary(
Upper);
10331 if (!SL.second || !SU.second)
10332 return std::nullopt;
10377 bool ControlsOnlyExit,
10378 bool AllowPredicates) {
10389 if (
C->getValue()->isZero())
return C;
10394 dyn_cast<SCEVAddRecExpr>(stripInjectiveFunctions(V));
10396 if (!AddRec && AllowPredicates)
10402 if (!AddRec || AddRec->
getLoop() != L)
10413 return ExitLimit(R, R, R,
false, Predicates);
10443 const SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step);
10478 return ExitLimit(Distance,
getConstant(MaxBECount), Distance,
false,
10497 const SCEV *SymbolicMax =
10498 isa<SCEVCouldNotCompute>(
Exact) ? ConstantMax :
Exact;
10499 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10511 auto *S = isa<SCEVCouldNotCompute>(
E) ?
M :
E;
10512 return ExitLimit(
E, M, S,
false, Predicates);
10516ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10524 if (!
C->getValue()->isZero())
10534std::pair<const BasicBlock *, const BasicBlock *>
10535ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10547 return {
L->getLoopPredecessor(),
L->getHeader()};
10549 return {
nullptr,
nullptr};
10558 if (
A ==
B)
return true;
10564 return A->isIdenticalTo(
B) && (isa<BinaryOperator>(
A) || isa<GetElementPtrInst>(
A));
10571 if (
const Instruction *AI = dyn_cast<Instruction>(AU->getValue()))
10572 if (
const Instruction *BI = dyn_cast<Instruction>(BU->getValue()))
10573 if (ComputesEqualValues(AI, BI))
10582 if (!
Add ||
Add->getNumOperands() != 2)
10584 if (
auto *ME = dyn_cast<SCEVMulExpr>(
Add->getOperand(0));
10585 ME && ME->getNumOperands() == 2 && ME->getOperand(0)->isAllOnesValue()) {
10586 LHS =
Add->getOperand(1);
10587 RHS = ME->getOperand(1);
10590 if (
auto *ME = dyn_cast<SCEVMulExpr>(
Add->getOperand(1));
10591 ME && ME->getNumOperands() == 2 && ME->getOperand(0)->isAllOnesValue()) {
10592 LHS =
Add->getOperand(0);
10593 RHS = ME->getOperand(1);
10600 const SCEV *&LHS,
const SCEV *&RHS,
10602 bool Changed =
false;
10605 auto TrivialCase = [&](
bool TriviallyTrue) {
10621 return TrivialCase(
false);
10622 return TrivialCase(
true);
10645 const APInt &
RA = RC->getAPInt();
10647 bool SimplifiedByConstantRange =
false;
10652 return TrivialCase(
true);
10654 return TrivialCase(
false);
10663 Changed = SimplifiedByConstantRange =
true;
10667 if (!SimplifiedByConstantRange) {
10684 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
10690 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
10696 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
10702 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
10714 return TrivialCase(
true);
10716 return TrivialCase(
false);
10805 if (
const auto *SExt = dyn_cast<SCEVSignExtendExpr>(S))
10810std::pair<const SCEV *, const SCEV *>
10813 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
10815 return { Start, Start };
10817 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
10823 const SCEV *LHS,
const SCEV *RHS) {
10826 getUsedLoops(
LHS, LoopsUsed);
10827 getUsedLoops(
RHS, LoopsUsed);
10829 if (LoopsUsed.
empty())
10834 for (
const auto *L1 : LoopsUsed)
10835 for (
const auto *L2 : LoopsUsed)
10837 DT.
dominates(L2->getHeader(), L1->getHeader())) &&
10838 "Domination relationship is not a linear order");
10868 SplitRHS.second) &&
10873 const SCEV *LHS,
const SCEV *RHS) {
10880 if (isKnownPredicateViaSplitting(Pred,
LHS,
RHS))
10884 return isKnownViaNonRecursiveReasoning(Pred,
LHS,
RHS);
10894 return std::nullopt;
10909 if (KnownWithoutContext)
10910 return KnownWithoutContext;
10918 return std::nullopt;
10924 const Loop *L =
LHS->getLoop();
10929std::optional<ScalarEvolution::MonotonicPredicateType>
10932 auto Result = getMonotonicPredicateTypeImpl(
LHS, Pred);
10938 auto ResultSwapped =
10941 assert(*ResultSwapped != *Result &&
10942 "monotonicity should flip as we flip the predicate");
10949std::optional<ScalarEvolution::MonotonicPredicateType>
10950ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
10964 return std::nullopt;
10968 "Should be greater or less!");
10972 if (!
LHS->hasNoUnsignedWrap())
10973 return std::nullopt;
10977 "Relational predicate is either signed or unsigned!");
10978 if (!
LHS->hasNoSignedWrap())
10979 return std::nullopt;
10981 const SCEV *Step =
LHS->getStepRecurrence(*
this);
10989 return std::nullopt;
10992std::optional<ScalarEvolution::LoopInvariantPredicate>
11000 return std::nullopt;
11007 if (!ArLHS || ArLHS->
getLoop() != L)
11008 return std::nullopt;
11011 if (!MonotonicType)
11012 return std::nullopt;
11038 return std::nullopt;
11075 return std::nullopt;
11078std::optional<ScalarEvolution::LoopInvariantPredicate>
11083 Pred,
LHS,
RHS, L, CtxI, MaxIter))
11085 if (
auto *
UMin = dyn_cast<SCEVUMinExpr>(MaxIter))
11091 for (
auto *
Op :
UMin->operands())
11095 return std::nullopt;
11098std::optional<ScalarEvolution::LoopInvariantPredicate>
11113 return std::nullopt;
11119 auto *AR = dyn_cast<SCEVAddRecExpr>(
LHS);
11120 if (!AR || AR->
getLoop() != L)
11121 return std::nullopt;
11125 return std::nullopt;
11131 if (Step != One && Step != MinusOne)
11132 return std::nullopt;
11138 return std::nullopt;
11144 return std::nullopt;
11152 if (Step == MinusOne)
11156 return std::nullopt;
11162bool ScalarEvolution::isKnownPredicateViaConstantRanges(
11172 return RangeLHS.
icmp(Pred, RangeRHS);
11183 if (CheckRanges(SL, SR))
11187 if (CheckRanges(UL, UR))
11196 return CheckRanges(SL, SR);
11201 return CheckRanges(UL, UR);
11211 auto MatchBinaryAddToConst = [
this](
const SCEV *
X,
const SCEV *
Y,
11214 const SCEV *XNonConstOp, *XConstOp;
11215 const SCEV *YNonConstOp, *YConstOp;
11219 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11222 XFlagsPresent = ExpectedFlags;
11224 if (!isa<SCEVConstant>(XConstOp) ||
11225 (XFlagsPresent & ExpectedFlags) != ExpectedFlags)
11228 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11231 YFlagsPresent = ExpectedFlags;
11234 if (!isa<SCEVConstant>(YConstOp) ||
11235 (YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11238 if (YNonConstOp != XNonConstOp)
11241 OutC1 = cast<SCEVConstant>(XConstOp)->getAPInt();
11242 OutC2 = cast<SCEVConstant>(YConstOp)->getAPInt();
11319bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB,
11321 const SCEV *LHS,
const SCEV *RHS) {
11330 return match(&
I, m_Intrinsic<Intrinsic::experimental_guard>(
11332 isImpliedCond(Pred, LHS, RHS, Condition,
false);
11342 const SCEV *LHS,
const SCEV *RHS) {
11351 "This cannot be done on broken IR!");
11354 if (isKnownViaNonRecursiveReasoning(Pred,
LHS,
RHS))
11363 if (LoopContinuePredicate && LoopContinuePredicate->
isConditional() &&
11364 isImpliedCond(Pred,
LHS,
RHS,
11366 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11371 if (WalkingBEDominatingConds)
11377 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11378 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11385 const SCEV *LoopCounter =
11396 auto *CI = cast<CallInst>(AssumeVH);
11400 if (isImpliedCond(Pred,
LHS,
RHS, CI->getArgOperand(0),
false))
11404 if (isImpliedViaGuard(Latch, Pred,
LHS,
RHS))
11407 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11408 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11409 assert(DTN &&
"should reach the loop header before reaching the root!");
11412 if (isImpliedViaGuard(BB, Pred,
LHS,
RHS))
11420 if (!ContinuePredicate || !ContinuePredicate->
isConditional())
11436 if (isImpliedCond(Pred,
LHS,
RHS, Condition,
11454 "This cannot be done on broken IR!");
11462 const bool ProvingStrictComparison = (Pred != NonStrictPredicate);
11463 bool ProvedNonStrictComparison =
false;
11464 bool ProvedNonEquality =
false;
11466 auto SplitAndProve =
11468 if (!ProvedNonStrictComparison)
11469 ProvedNonStrictComparison = Fn(NonStrictPredicate);
11470 if (!ProvedNonEquality)
11472 if (ProvedNonStrictComparison && ProvedNonEquality)
11477 if (ProvingStrictComparison) {
11479 return isKnownViaNonRecursiveReasoning(
P,
LHS,
RHS);
11481 if (SplitAndProve(ProofFn))
11486 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
11488 if (isImpliedCond(Pred,
LHS,
RHS, Condition,
Inverse, CtxI))
11490 if (ProvingStrictComparison) {
11494 if (SplitAndProve(ProofFn))
11505 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
11509 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
11510 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
11512 dyn_cast<BranchInst>(Pair.first->getTerminator());
11525 auto *CI = cast<CallInst>(AssumeVH);
11529 if (ProveViaCond(CI->getArgOperand(0),
false))
11537 for (
const auto *GU : GuardDecl->users())
11538 if (
const auto *Guard = dyn_cast<IntrinsicInst>(GU))
11540 if (ProveViaCond(Guard->getArgOperand(0),
false))
11556 "LHS is not available at Loop Entry");
11558 "RHS is not available at Loop Entry");
11560 if (isKnownViaNonRecursiveReasoning(Pred,
LHS,
RHS))
11571 if (FoundCondValue ==
11575 if (!PendingLoopPredicates.insert(FoundCondValue).second)
11579 make_scope_exit([&]() { PendingLoopPredicates.erase(FoundCondValue); });
11582 const Value *Op0, *Op1;
11585 return isImpliedCond(Pred, LHS, RHS, Op0,
Inverse, CtxI) ||
11586 isImpliedCond(Pred, LHS, RHS, Op1,
Inverse, CtxI);
11589 return isImpliedCond(Pred, LHS, RHS, Op0,
Inverse, CtxI) ||
11590 isImpliedCond(Pred, LHS, RHS, Op1,
Inverse, CtxI);
11593 const ICmpInst *ICI = dyn_cast<ICmpInst>(FoundCondValue);
11594 if (!ICI)
return false;
11607 return isImpliedCond(Pred, LHS, RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
11613 const SCEV *FoundLHS,
const SCEV *FoundRHS,
11624 auto *WideType = FoundLHS->
getType();
11634 if (isImpliedCondBalancedTypes(Pred, LHS, RHS, FoundPred, TruncFoundLHS,
11635 TruncFoundRHS, CtxI))
11661 return isImpliedCondBalancedTypes(Pred, LHS, RHS, FoundPred, FoundLHS,
11665bool ScalarEvolution::isImpliedCondBalancedTypes(
11671 "Types should be balanced!");
11678 if (FoundLHS == FoundRHS)
11682 if (LHS == FoundRHS || RHS == FoundLHS) {
11683 if (isa<SCEVConstant>(RHS)) {
11693 if (FoundPred == Pred)
11694 return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS, CtxI);
11708 if (!isa<SCEVConstant>(RHS) && !isa<SCEVAddRecExpr>(LHS))
11709 return isImpliedCondOperands(FoundPred, RHS, LHS, FoundLHS, FoundRHS,
11711 if (!isa<SCEVConstant>(FoundRHS) && !isa<SCEVAddRecExpr>(FoundLHS))
11712 return isImpliedCondOperands(Pred, LHS, RHS, FoundRHS, FoundLHS, CtxI);
11719 FoundLHS, FoundRHS, CtxI))
11724 isImpliedCondOperands(Pred, LHS, RHS,
getNotSCEV(FoundLHS),
11733 assert(P1 != P2 &&
"Handled earlier!");
11737 if (IsSignFlippedPredicate(Pred, FoundPred)) {
11742 return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS, CtxI);
11746 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
11747 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
11752 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
11763 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
11764 CanonicalRHS, CanonicalFoundLHS,
11765 CanonicalFoundRHS);
11770 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
11771 CanonicalRHS, CanonicalFoundLHS,
11772 CanonicalFoundRHS);
11777 (isa<SCEVConstant>(FoundLHS) || isa<SCEVConstant>(FoundRHS))) {
11780 const SCEV *
V =
nullptr;
11782 if (isa<SCEVConstant>(FoundLHS)) {
11783 C = cast<SCEVConstant>(FoundLHS);
11786 C = cast<SCEVConstant>(FoundRHS);
11798 if (Min ==
C->getAPInt()) {
11803 APInt SharperMin = Min + 1;
11810 if (isImpliedCondOperands(Pred, LHS, RHS, V,
getConstant(SharperMin),
11826 if (isImpliedCondOperands(Pred, LHS, RHS, V,
getConstant(Min), CtxI))
11855 if (isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS, CtxI))
11859 if (isImpliedCondOperands(FoundPred, LHS, RHS, FoundLHS, FoundRHS, CtxI))
11862 if (isImpliedCondOperandsViaRanges(Pred, LHS, RHS, FoundPred, FoundLHS, FoundRHS))
11869bool ScalarEvolution::splitBinaryAdd(
const SCEV *Expr,
11872 const auto *AE = dyn_cast<SCEVAddExpr>(Expr);
11873 if (!AE || AE->getNumOperands() != 2)
11876 L = AE->getOperand(0);
11877 R = AE->getOperand(1);
11878 Flags = AE->getNoWrapFlags();
11882std::optional<APInt>
11891 if (isa<SCEVAddRecExpr>(
Less) && isa<SCEVAddRecExpr>(More)) {
11892 const auto *LAR = cast<SCEVAddRecExpr>(
Less);
11893 const auto *MAR = cast<SCEVAddRecExpr>(More);
11895 if (LAR->getLoop() != MAR->getLoop())
11896 return std::nullopt;
11900 if (!LAR->isAffine() || !MAR->isAffine())
11901 return std::nullopt;
11903 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
11904 return std::nullopt;
11906 Less = LAR->getStart();
11907 More = MAR->getStart();
11912 if (isa<SCEVConstant>(
Less) && isa<SCEVConstant>(More)) {
11913 const auto &M = cast<SCEVConstant>(More)->getAPInt();
11914 const auto &L = cast<SCEVConstant>(
Less)->getAPInt();
11919 const SCEV *LLess =
nullptr, *RLess =
nullptr;
11920 const SCEV *LMore =
nullptr, *RMore =
nullptr;
11923 if (splitBinaryAdd(
Less, LLess, RLess, Flags))
11924 if ((C1 = dyn_cast<SCEVConstant>(LLess)))
11929 if (splitBinaryAdd(More, LMore, RMore, Flags))
11930 if ((C2 = dyn_cast<SCEVConstant>(LMore)))
11932 return C2->getAPInt();
11935 if (C1 && C2 && RLess == RMore)
11936 return C2->getAPInt() - C1->
getAPInt();
11938 return std::nullopt;
11941bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
11961 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(FoundLHS)) {
11965 if (!L->contains(ContextBB) || !DT.
dominates(ContextBB, L->getLoopLatch()))
11969 return isImpliedCondOperands(Pred, LHS, RHS, AR->
getStart(), FoundRHS);
11972 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(FoundRHS)) {
11976 if (!L->contains(ContextBB) || !DT.
dominates(ContextBB, L->getLoopLatch()))
11980 return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, AR->
getStart());
11986bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(
11988 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
11992 const auto *AddRecLHS = dyn_cast<SCEVAddRecExpr>(LHS);
11996 const auto *AddRecFoundLHS = dyn_cast<SCEVAddRecExpr>(FoundLHS);
11997 if (!AddRecFoundLHS)
12004 const Loop *
L = AddRecFoundLHS->getLoop();
12005 if (L != AddRecLHS->getLoop())
12042 if (!LDiff || !RDiff || *LDiff != *RDiff)
12045 if (LDiff->isMinValue())
12048 APInt FoundRHSLimit;
12051 FoundRHSLimit = -(*RDiff);
12065 const SCEV *FoundLHS,
12066 const SCEV *FoundRHS,
unsigned Depth) {
12067 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12071 bool Erased = PendingMerges.erase(LPhi);
12072 assert(Erased &&
"Failed to erase LPhi!");
12076 bool Erased = PendingMerges.erase(RPhi);
12077 assert(Erased &&
"Failed to erase RPhi!");
12083 if (
const SCEVUnknown *LU = dyn_cast<SCEVUnknown>(LHS))
12084 if (
auto *Phi = dyn_cast<PHINode>(LU->getValue())) {
12085 if (!PendingMerges.insert(Phi).second)
12089 if (
const SCEVUnknown *RU = dyn_cast<SCEVUnknown>(RHS))
12090 if (
auto *Phi = dyn_cast<PHINode>(RU->getValue())) {
12099 if (!PendingMerges.insert(Phi).second)
12105 if (!LPhi && !RPhi)
12116 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12120 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12121 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12122 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12123 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12126 if (RPhi && RPhi->getParent() == LBB) {
12133 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12134 if (!ProvedEasily(L, R))
12145 auto *RLoop = RAR->
getLoop();
12146 auto *Predecessor = RLoop->getLoopPredecessor();
12147 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12149 if (!ProvedEasily(L1, RAR->
getStart()))
12151 auto *Latch = RLoop->getLoopLatch();
12152 assert(Latch &&
"Loop with AddRec with no latch?");
12170 if (!ProvedEasily(L, RHS))
12180 const SCEV *FoundLHS,
12181 const SCEV *FoundRHS) {
12184 if (RHS == FoundRHS) {
12189 if (LHS != FoundLHS)
12192 auto *SUFoundRHS = dyn_cast<SCEVUnknown>(FoundRHS);
12196 Value *Shiftee, *ShiftValue;
12198 using namespace PatternMatch;
12199 if (
match(SUFoundRHS->getValue(),
12201 auto *ShifteeS =
getSCEV(Shiftee);
12221 const SCEV *FoundLHS,
12222 const SCEV *FoundRHS,
12224 if (isImpliedCondOperandsViaRanges(Pred, LHS, RHS, Pred, FoundLHS, FoundRHS))
12227 if (isImpliedCondOperandsViaNoOverflow(Pred, LHS, RHS, FoundLHS, FoundRHS))
12230 if (isImpliedCondOperandsViaShift(Pred, LHS, RHS, FoundLHS, FoundRHS))
12233 if (isImpliedCondOperandsViaAddRecStart(Pred, LHS, RHS, FoundLHS, FoundRHS,
12237 return isImpliedCondOperandsHelper(Pred, LHS, RHS,
12238 FoundLHS, FoundRHS);
12242template <
typename MinMaxExprType>
12244 const SCEV *Candidate) {
12245 const MinMaxExprType *MinMaxExpr = dyn_cast<MinMaxExprType>(MaybeMinMaxExpr);
12249 return is_contained(MinMaxExpr->operands(), Candidate);
12254 const SCEV *LHS,
const SCEV *RHS) {
12288 const SCEV *LHS,
const SCEV *RHS) {
12299 IsMinMaxConsistingOf<SCEVSMinExpr>(
LHS,
RHS) ||
12301 IsMinMaxConsistingOf<SCEVSMaxExpr>(
RHS,
LHS);
12310 IsMinMaxConsistingOf<SCEVUMinExpr>(
LHS,
RHS) ||
12312 IsMinMaxConsistingOf<SCEVUMaxExpr>(
RHS,
LHS);
12320 const SCEV *FoundLHS,
12321 const SCEV *FoundRHS,
12325 "LHS and RHS have different sizes?");
12328 "FoundLHS and FoundRHS have different sizes?");
12360 auto GetOpFromSExt = [&](
const SCEV *S) {
12361 if (
auto *Ext = dyn_cast<SCEVSignExtendExpr>(S))
12362 return Ext->getOperand();
12369 auto *OrigLHS =
LHS;
12370 auto *OrigFoundLHS = FoundLHS;
12371 LHS = GetOpFromSExt(LHS);
12372 FoundLHS = GetOpFromSExt(FoundLHS);
12375 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
12378 FoundRHS,
Depth + 1);
12381 if (
auto *LHSAddExpr = dyn_cast<SCEVAddExpr>(LHS)) {
12391 if (!LHSAddExpr->hasNoSignedWrap())
12394 auto *LL = LHSAddExpr->getOperand(0);
12395 auto *LR = LHSAddExpr->getOperand(1);
12399 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
12400 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2, RHS);
12405 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
12407 }
else if (
auto *LHSUnknownExpr = dyn_cast<SCEVUnknown>(LHS)) {
12422 if (!isa<ConstantInt>(LR))
12425 auto *Denominator = cast<SCEVConstant>(
getSCEV(LR));
12430 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
12438 auto *DTy = Denominator->getType();
12439 auto *FRHSTy = FoundRHS->
getType();
12440 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
12459 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
12470 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
12472 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
12480 if (isImpliedViaMerge(Pred, OrigLHS, RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
12487 const SCEV *LHS,
const SCEV *RHS) {
12520 const SCEV *LHS,
const SCEV *RHS) {
12522 isKnownPredicateViaConstantRanges(Pred, LHS, RHS) ||
12525 isKnownPredicateViaNoOverflow(Pred, LHS, RHS);
12531 const SCEV *FoundLHS,
12532 const SCEV *FoundRHS) {
12567 if (isImpliedViaOperations(Pred, LHS, RHS, FoundLHS, FoundRHS))
12577 const SCEV *FoundLHS,
12578 const SCEV *FoundRHS) {
12579 if (!isa<SCEVConstant>(RHS) || !isa<SCEVConstant>(FoundRHS))
12588 const APInt &ConstFoundRHS = cast<SCEVConstant>(FoundRHS)->getAPInt();
12600 const APInt &ConstRHS = cast<SCEVConstant>(RHS)->getAPInt();
12603 return LHSRange.
icmp(Pred, ConstRHS);
12606bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *RHS,
const SCEV *Stride,
12619 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
12627 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
12630bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *RHS,
const SCEV *Stride,
12642 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
12650 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
12662const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
12663 const SCEV *Stride,
12690 : APIntOps::umax(One, MinStride);
12694 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
12705 : APIntOps::umax(MaxEnd, MinStart);
12712ScalarEvolution::howManyLessThans(
const SCEV *LHS,
const SCEV *RHS,
12713 const Loop *L,
bool IsSigned,
12714 bool ControlsOnlyExit,
bool AllowPredicates) {
12718 bool PredicatedIV =
false;
12739 if (!StrideC || !StrideC->getAPInt().isPowerOf2())
12749 if (
auto *ZExt = dyn_cast<SCEVZeroExtendExpr>(LHS)) {
12750 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(ZExt->getOperand());
12752 auto canProveNUW = [&]() {
12755 if (!ControlsOnlyExit)
12776 Limit = Limit.
zext(OuterBitWidth);
12788 Type *Ty = ZExt->getType();
12790 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this, 0),
12792 IV = dyn_cast<SCEVAddRecExpr>(S);
12799 if (!
IV && AllowPredicates) {
12804 PredicatedIV =
true;
12808 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
12822 bool NoWrap = ControlsOnlyExit &&
IV->getNoWrapFlags(WrapType);
12825 const SCEV *Stride =
IV->getStepRecurrence(*
this);
12830 if (!PositiveStride) {
12882 auto wouldZeroStrideBeUB = [&]() {
12894 if (!wouldZeroStrideBeUB()) {
12898 }
else if (!Stride->
isOne() && !NoWrap) {
12899 auto isUBOnWrap = [&]() {
12905 return canAssumeNoSelfWrap(
IV);
12912 if (canIVOverflowOnLT(RHS, Stride, IsSigned) && !isUBOnWrap())
12925 const SCEV *Start =
IV->getStart();
12931 const SCEV *OrigStart = Start;
12933 if (Start->getType()->isPointerTy()) {
12935 if (isa<SCEVCouldNotCompute>(Start))
12940 if (isa<SCEVCouldNotCompute>(RHS))
12950 const SCEV *MaxBECount = computeMaxBECountForLT(
12953 MaxBECount,
false , Predicates);
12960 const SCEV *BECount =
nullptr;
12961 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
12987 const SCEV *Numerator =
12992 const SCEV *BECountIfBackedgeTaken =
nullptr;
12994 auto canProveRHSGreaterThanEqualStart = [&]() {
13021 if (canProveRHSGreaterThanEqualStart()) {
13051 bool MayAddOverflow = [&] {
13052 if (
auto *StrideC = dyn_cast<SCEVConstant>(Stride)) {
13053 if (StrideC->getAPInt().isPowerOf2()) {
13098 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13110 if (!MayAddOverflow) {
13120 const SCEV *ConstantMaxBECount;
13121 bool MaxOrZero =
false;
13122 if (isa<SCEVConstant>(BECount)) {
13123 ConstantMaxBECount = BECount;
13124 }
else if (BECountIfBackedgeTaken &&
13125 isa<SCEVConstant>(BECountIfBackedgeTaken)) {
13129 ConstantMaxBECount = BECountIfBackedgeTaken;
13132 ConstantMaxBECount = computeMaxBECountForLT(
13136 if (isa<SCEVCouldNotCompute>(ConstantMaxBECount) &&
13137 !isa<SCEVCouldNotCompute>(BECount))
13140 const SCEV *SymbolicMaxBECount =
13141 isa<SCEVCouldNotCompute>(BECount) ? ConstantMaxBECount : BECount;
13142 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13147 const SCEV *LHS,
const SCEV *RHS,
const Loop *L,
bool IsSigned,
13148 bool ControlsOnlyExit,
bool AllowPredicates) {
13155 if (!
IV && AllowPredicates)
13162 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13166 bool NoWrap = ControlsOnlyExit &&
IV->getNoWrapFlags(WrapType);
13179 if (!Stride->
isOne() && !NoWrap)
13180 if (canIVOverflowOnGT(RHS, Stride, IsSigned))
13183 const SCEV *Start =
IV->getStart();
13195 if (Start->getType()->isPointerTy()) {
13197 if (isa<SCEVCouldNotCompute>(Start))
13200 if (
End->getType()->isPointerTy()) {
13202 if (isa<SCEVCouldNotCompute>(
End))
13230 const SCEV *ConstantMaxBECount =
13231 isa<SCEVConstant>(BECount)
13236 if (isa<SCEVCouldNotCompute>(ConstantMaxBECount))
13237 ConstantMaxBECount = BECount;
13238 const SCEV *SymbolicMaxBECount =
13239 isa<SCEVCouldNotCompute>(BECount) ? ConstantMaxBECount : BECount;
13241 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13247 if (Range.isFullSet())
13251 if (
const SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart()))
13252 if (!SC->getValue()->isZero()) {
13256 getNoWrapFlags(FlagNW));
13257 if (
const auto *ShiftedAddRec = dyn_cast<SCEVAddRecExpr>(Shifted))
13258 return ShiftedAddRec->getNumIterationsInRange(
13259 Range.subtract(SC->getAPInt()), SE);
13266 if (
any_of(operands(), [](
const SCEV *
Op) {
return !isa<SCEVConstant>(
Op); }))
13286 APInt A = cast<SCEVConstant>(getOperand(1))->getAPInt();
13287 APInt End =
A.sge(1) ? (Range.getUpper() - 1) : Range.getLower();
13297 if (Range.contains(Val->
getValue()))
13304 "Linear scev computation is off in a bad way!");
13308 if (isQuadratic()) {
13318 assert(getNumOperands() > 1 &&
"AddRec with zero step?");
13328 for (
unsigned i = 0, e = getNumOperands() - 1; i < e; ++i)
13334 const SCEV *
Last = getOperand(getNumOperands() - 1);
13335 assert(!
Last->isZero() &&
"Recurrency with zero step?");
13337 return cast<SCEVAddRecExpr>(SE.
getAddRecExpr(Ops, getLoop(),
13344 if (
const auto *SU = dyn_cast<SCEVUnknown>(S))
13345 return isa<UndefValue>(SU->
getValue());
13353 if (
const auto *SU = dyn_cast<SCEVUnknown>(S))
13362 if (
StoreInst *Store = dyn_cast<StoreInst>(Inst))
13363 Ty = Store->getValueOperand()->getType();
13364 else if (
LoadInst *Load = dyn_cast<LoadInst>(Inst))
13365 Ty = Load->getType();
13377void ScalarEvolution::SCEVCallbackVH::deleted() {
13378 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13379 if (
PHINode *PN = dyn_cast<PHINode>(getValPtr()))
13380 SE->ConstantEvolutionLoopExitValue.erase(PN);
13381 SE->eraseValueFromMap(getValPtr());
13385void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
13386 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13405 :
F(
F), TLI(TLI), AC(AC), DT(DT), LI(LI),
13407 LoopDispositions(64), BlockDispositions(64) {
13418 auto *GuardDecl =
F.getParent()->getFunction(
13420 HasGuards = GuardDecl && !GuardDecl->use_empty();
13424 :
F(Arg.
F), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT),
13425 LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
13426 ValueExprMap(
std::
move(Arg.ValueExprMap)),
13427 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
13428 PendingPhiRanges(
std::
move(Arg.PendingPhiRanges)),
13429 PendingMerges(
std::
move(Arg.PendingMerges)),
13430 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
13431 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
13432 PredicatedBackedgeTakenCounts(
13433 std::
move(Arg.PredicatedBackedgeTakenCounts)),
13434 BECountUsers(
std::
move(Arg.BECountUsers)),
13435 ConstantEvolutionLoopExitValue(
13436 std::
move(Arg.ConstantEvolutionLoopExitValue)),
13437 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
13438 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
13439 LoopDispositions(
std::
move(Arg.LoopDispositions)),
13440 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
13441 BlockDispositions(
std::
move(Arg.BlockDispositions)),
13442 SCEVUsers(
std::
move(Arg.SCEVUsers)),
13443 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
13444 SignedRanges(
std::
move(Arg.SignedRanges)),
13445 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
13446 UniquePreds(
std::
move(Arg.UniquePreds)),
13447 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
13448 LoopUsers(
std::
move(Arg.LoopUsers)),
13449 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
13450 FirstUnknown(Arg.FirstUnknown) {
13451 Arg.FirstUnknown =
nullptr;
13460 Tmp->~SCEVUnknown();
13462 FirstUnknown =
nullptr;
13464 ExprValueMap.
clear();
13465 ValueExprMap.
clear();
13467 BackedgeTakenCounts.clear();
13468 PredicatedBackedgeTakenCounts.clear();
13470 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
13471 assert(PendingPhiRanges.empty() &&
"getRangeRef garbage");
13472 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
13473 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
13474 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
13484 if (isa<SCEVConstant>(S))
13496 L->getHeader()->printAsOperand(
OS,
false);
13500 L->getExitingBlocks(ExitingBlocks);
13501 if (ExitingBlocks.
size() != 1)
13502 OS <<
"<multiple exits> ";
13505 if (!isa<SCEVCouldNotCompute>(BTC)) {
13506 OS <<
"backedge-taken count is ";
13509 OS <<
"Unpredictable backedge-taken count.";
13512 if (ExitingBlocks.
size() > 1)
13513 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
13514 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
13520 L->getHeader()->printAsOperand(
OS,
false);
13524 if (!isa<SCEVCouldNotCompute>(ConstantBTC)) {
13525 OS <<
"constant max backedge-taken count is ";
13528 OS <<
", actual taken count either this or zero.";
13530 OS <<
"Unpredictable constant max backedge-taken count. ";
13535 L->getHeader()->printAsOperand(
OS,
false);
13539 if (!isa<SCEVCouldNotCompute>(SymbolicBTC)) {
13540 OS <<
"symbolic max backedge-taken count is ";
13543 OS <<
", actual taken count either this or zero.";
13545 OS <<
"Unpredictable symbolic max backedge-taken count. ";
13549 if (ExitingBlocks.
size() > 1)
13550 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
13551 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
13560 if (PBT != BTC || !Preds.
empty()) {
13562 L->getHeader()->printAsOperand(
OS,
false);
13564 if (!isa<SCEVCouldNotCompute>(PBT)) {
13565 OS <<
"Predicated backedge-taken count is ";
13568 OS <<
"Unpredictable predicated backedge-taken count.";
13570 OS <<
" Predicates:\n";
13571 for (
const auto *
P : Preds)
13577 L->getHeader()->printAsOperand(
OS,
false);
13593 OS <<
"Computable";
13602 OS <<
"DoesNotDominate";
13608 OS <<
"ProperlyDominates";
13625 OS <<
"Classifying expressions for: ";
13634 if (!isa<SCEVCouldNotCompute>(SV)) {
13647 if (!isa<SCEVCouldNotCompute>(AtUse)) {
13656 OS <<
"\t\t" "Exits: ";
13659 OS <<
"<<Unknown>>";
13665 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
13667 OS <<
"\t\t" "LoopDispositions: { ";
13673 Iter->getHeader()->printAsOperand(
OS,
false);
13681 OS <<
"\t\t" "LoopDispositions: { ";
13687 InnerL->getHeader()->printAsOperand(
OS,
false);
13698 OS <<
"Determining loop execution counts for: ";
13707 auto &Values = LoopDispositions[S];
13708 for (
auto &V : Values) {
13709 if (V.getPointer() == L)
13714 auto &Values2 = LoopDispositions[S];
13716 if (V.getPointer() == L) {
13725ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
13744 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
13745 " dominate the contained loop's header?");
13772 bool HasVarying =
false;
13787 if (
auto *
I = dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue()))
13806 auto &Values = BlockDispositions[S];
13807 for (
auto &V : Values) {
13808 if (V.getPointer() == BB)
13813 auto &Values2 = BlockDispositions[S];
13815 if (V.getPointer() == BB) {
13824ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
13853 bool Proper =
true;
13865 dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue())) {
13866 if (
I->getParent() == BB)
13891void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
13894 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
13895 auto It = BECounts.find(L);
13896 if (It != BECounts.end()) {
13897 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
13898 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
13899 if (!isa<SCEVConstant>(S)) {
13900 auto UserIt = BECountUsers.find(S);
13901 assert(UserIt != BECountUsers.end());
13902 UserIt->second.erase({L, Predicated});
13906 BECounts.erase(It);
13914 while (!Worklist.
empty()) {
13916 auto Users = SCEVUsers.find(Curr);
13917 if (
Users != SCEVUsers.end())
13923 for (
const auto *S : ToForget)
13924 forgetMemoizedResultsImpl(S);
13926 for (
auto I = PredicatedSCEVRewrites.begin();
13927 I != PredicatedSCEVRewrites.end();) {
13928 std::pair<const SCEV *, const Loop *> Entry =
I->first;
13929 if (ToForget.count(Entry.first))
13930 PredicatedSCEVRewrites.erase(
I++);
13936void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
13937 LoopDispositions.erase(S);
13938 BlockDispositions.erase(S);
13939 UnsignedRanges.erase(S);
13940 SignedRanges.erase(S);
13941 HasRecMap.
erase(S);
13942 ConstantMultipleCache.erase(S);
13944 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(S)) {
13945 UnsignedWrapViaInductionTried.erase(AR);
13946 SignedWrapViaInductionTried.erase(AR);
13949 auto ExprIt = ExprValueMap.
find(S);
13950 if (ExprIt != ExprValueMap.
end()) {
13951 for (
Value *V : ExprIt->second) {
13952 auto ValueIt = ValueExprMap.
find_as(V);
13953 if (ValueIt != ValueExprMap.
end())
13954 ValueExprMap.
erase(ValueIt);
13956 ExprValueMap.
erase(ExprIt);
13959 auto ScopeIt = ValuesAtScopes.find(S);
13960 if (ScopeIt != ValuesAtScopes.end()) {
13961 for (
const auto &Pair : ScopeIt->second)
13962 if (!isa_and_nonnull<SCEVConstant>(Pair.second))
13964 std::make_pair(Pair.first, S));
13965 ValuesAtScopes.erase(ScopeIt);
13968 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
13969 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
13970 for (
const auto &Pair : ScopeUserIt->second)
13971 llvm::erase(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
13972 ValuesAtScopesUsers.erase(ScopeUserIt);
13975 auto BEUsersIt = BECountUsers.find(S);
13976 if (BEUsersIt != BECountUsers.end()) {
13978 auto Copy = BEUsersIt->second;
13979 for (
const auto &Pair : Copy)
13980 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
13981 BECountUsers.erase(BEUsersIt);
13984 auto FoldUser = FoldCacheUser.find(S);
13985 if (FoldUser != FoldCacheUser.end())
13986 for (
auto &KV : FoldUser->second)
13987 FoldCache.erase(KV);
13988 FoldCacheUser.erase(S);
13992ScalarEvolution::getUsedLoops(
const SCEV *S,
13994 struct FindUsedLoops {
13996 : LoopsUsed(LoopsUsed) {}
13998 bool follow(
const SCEV *S) {
13999 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(S))
14004 bool isDone()
const {
return false; }
14007 FindUsedLoops F(LoopsUsed);
14011void ScalarEvolution::getReachableBlocks(
14015 while (!Worklist.
empty()) {
14017 if (!Reachable.
insert(BB).second)
14024 if (
auto *
C = dyn_cast<ConstantInt>(
Cond)) {
14025 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14029 if (
auto *Cmp = dyn_cast<ICmpInst>(
Cond)) {
14032 if (isKnownPredicateViaConstantRanges(
Cmp->getPredicate(), L, R)) {
14036 if (isKnownPredicateViaConstantRanges(
Cmp->getInversePredicate(), L,
14071 SCEVMapper SCM(SE2);
14073 SE2.getReachableBlocks(ReachableBlocks,
F);
14075 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14093 while (!LoopStack.
empty()) {
14099 if (!ReachableBlocks.
contains(L->getHeader()))
14104 auto It = BackedgeTakenCounts.find(L);
14105 if (It == BackedgeTakenCounts.end())
14109 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14129 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14130 if (Delta && !Delta->
isZero()) {
14131 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14132 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14133 dbgs() <<
"New: " << *NewBECount <<
"\n";
14134 dbgs() <<
"Delta: " << *Delta <<
"\n";
14142 while (!Worklist.
empty()) {
14144 if (ValidLoops.
insert(L).second)
14145 Worklist.
append(L->begin(), L->end());
14147 for (
const auto &KV : ValueExprMap) {
14150 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(KV.second)) {
14152 "AddRec references invalid loop");
14157 auto It = ExprValueMap.
find(KV.second);
14158 if (It == ExprValueMap.
end() || !It->second.contains(KV.first)) {
14159 dbgs() <<
"Value " << *KV.first
14160 <<
" is in ValueExprMap but not in ExprValueMap\n";
14164 if (
auto *
I = dyn_cast<Instruction>(&*KV.first)) {
14165 if (!ReachableBlocks.
contains(
I->getParent()))
14167 const SCEV *OldSCEV = SCM.visit(KV.second);
14169 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14170 if (Delta && !Delta->
isZero()) {
14171 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14172 <<
"Old: " << *OldSCEV <<
"\n"
14173 <<
"New: " << *NewSCEV <<
"\n"
14174 <<
"Delta: " << *Delta <<
"\n";
14180 for (
const auto &KV : ExprValueMap) {
14181 for (
Value *V : KV.second) {
14182 auto It = ValueExprMap.find_as(V);
14183 if (It == ValueExprMap.end()) {
14184 dbgs() <<
"Value " << *V
14185 <<
" is in ExprValueMap but not in ValueExprMap\n";
14188 if (It->second != KV.first) {
14189 dbgs() <<
"Value " << *V <<
" mapped to " << *It->second
14190 <<
" rather than " << *KV.first <<
"\n";
14197 for (
const auto &S : UniqueSCEVs) {
14200 if (isa<SCEVConstant>(
Op))
14202 auto It = SCEVUsers.find(
Op);
14203 if (It != SCEVUsers.end() && It->second.count(&S))
14205 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14206 <<
" is not being tracked!\n";
14212 for (
const auto &ValueAndVec : ValuesAtScopes) {
14214 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14215 const Loop *L = LoopAndValueAtScope.first;
14216 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
14217 if (!isa<SCEVConstant>(ValueAtScope)) {
14218 auto It = ValuesAtScopesUsers.find(ValueAtScope);
14219 if (It != ValuesAtScopesUsers.end() &&
14222 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14223 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14229 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14230 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14231 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14232 const Loop *L = LoopAndValue.first;
14233 const SCEV *
Value = LoopAndValue.second;
14235 auto It = ValuesAtScopes.find(
Value);
14236 if (It != ValuesAtScopes.end() &&
14237 is_contained(It->second, std::make_pair(L, ValueAtScope)))
14239 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14240 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14246 auto VerifyBECountUsers = [&](
bool Predicated) {
14248 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14249 for (
const auto &LoopAndBEInfo : BECounts) {
14250 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14251 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14252 if (!isa<SCEVConstant>(S)) {
14253 auto UserIt = BECountUsers.find(S);
14254 if (UserIt != BECountUsers.end() &&
14255 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14257 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14258 <<
" missing from BECountUsers\n";
14265 VerifyBECountUsers(
false);
14266 VerifyBECountUsers(
true);
14269 for (
auto &[S, Values] : LoopDispositions) {
14270 for (
auto [
Loop, CachedDisposition] : Values) {
14272 if (CachedDisposition != RecomputedDisposition) {
14273 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
14274 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
14275 << RecomputedDisposition <<
"\n";
14282 for (
auto &[S, Values] : BlockDispositions) {
14283 for (
auto [BB, CachedDisposition] : Values) {
14285 if (CachedDisposition != RecomputedDisposition) {
14286 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
14287 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
14288 <<
", actual " << RecomputedDisposition <<
"\n";
14295 for (
auto [
FoldID, Expr] : FoldCache) {
14296 auto I = FoldCacheUser.find(Expr);
14297 if (
I == FoldCacheUser.end()) {
14298 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
14303 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
14307 for (
auto [Expr, IDs] : FoldCacheUser) {
14308 for (
auto &
FoldID : IDs) {
14309 auto I = FoldCache.find(
FoldID);
14310 if (
I == FoldCache.end()) {
14311 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
14315 if (
I->second != Expr) {
14316 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: "
14317 << *
I->second <<
" != " << *Expr <<
"!\n";
14328 for (
auto [S, Multiple] : ConstantMultipleCache) {
14330 if ((Multiple != 0 && RecomputedMultiple != 0 &&
14331 Multiple.
urem(RecomputedMultiple) != 0 &&
14332 RecomputedMultiple.
urem(Multiple) != 0)) {
14333 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
14334 << *S <<
" : Computed " << RecomputedMultiple
14335 <<
" but cache contains " << Multiple <<
"!\n";
14375 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
14376 <<
F.getName() <<
"':\n";
14382 "Scalar Evolution Analysis",
false,
true)
14398 F, getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F),
14399 getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F),
14400 getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
14401 getAnalysis<LoopInfoWrapperPass>().getLoopInfo()));
14433 const SCEV *LHS,
const SCEV *RHS) {
14436 "Type mismatch between LHS and RHS");
14439 ID.AddInteger(Pred);
14440 ID.AddPointer(
LHS);
14441 ID.AddPointer(
RHS);
14442 void *IP =
nullptr;
14443 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
14447 UniquePreds.InsertNode(Eq, IP);
14458 ID.AddInteger(AddedFlags);
14459 void *IP =
nullptr;
14460 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
14462 auto *OF =
new (SCEVAllocator)
14464 UniquePreds.InsertNode(OF, IP);
14484 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
14490 if (
auto *U = dyn_cast<SCEVUnionPredicate>(Pred)) {
14491 for (
const auto *Pred : U->getPredicates())
14492 if (
const auto *IPred = dyn_cast<SCEVComparePredicate>(Pred))
14493 if (IPred->getLHS() == Expr &&
14494 IPred->getPredicate() == ICmpInst::ICMP_EQ)
14495 return IPred->getRHS();
14496 }
else if (
const auto *IPred = dyn_cast<SCEVComparePredicate>(Pred)) {
14497 if (IPred->getLHS() == Expr &&
14498 IPred->getPredicate() == ICmpInst::ICMP_EQ)
14499 return IPred->getRHS();
14502 return convertToAddRecWithPreds(Expr);
14555 return addOverflowAssumption(
A);
14565 if (!isa<PHINode>(Expr->
getValue()))
14568 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
14570 if (!PredicatedRewrite)
14572 for (
const auto *
P : PredicatedRewrite->second){
14574 if (
auto *WP = dyn_cast<const SCEVWrapPredicate>(
P)) {
14575 if (L != WP->getExpr()->getLoop())
14578 if (!addOverflowAssumption(
P))
14581 return PredicatedRewrite->first;
14594 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
14601 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
14602 auto *AddRec = dyn_cast<SCEVAddRecExpr>(S);
14609 for (
const auto *
P : TransformPreds)
14618 : FastID(
ID), Kind(Kind) {}
14625 assert(
LHS !=
RHS &&
"LHS and RHS are the same SCEV");
14629 const auto *
Op = dyn_cast<SCEVComparePredicate>(
N);
14659 const auto *
Op = dyn_cast<SCEVWrapPredicate>(
N);
14661 return Op &&
Op->AR == AR &&
setFlags(Flags,
Op->Flags) == Flags;
14697 if (Step->getValue()->getValue().isNonNegative())
14701 return ImpliedFlags;
14707 for (
const auto *
P : Preds)
14717 if (
const auto *Set = dyn_cast<SCEVUnionPredicate>(
N))
14718 return all_of(Set->Preds,
14726 for (
const auto *Pred : Preds)
14731 if (
const auto *Set = dyn_cast<SCEVUnionPredicate>(
N)) {
14732 for (
const auto *Pred : Set->Preds)
14744 Preds = std::make_unique<SCEVUnionPredicate>(
Empty);
14749 for (
const auto *
Op : Ops)
14753 if (!isa<SCEVConstant>(
Op))
14754 SCEVUsers[
Op].insert(
User);
14759 RewriteEntry &Entry = RewriteMap[Expr];
14762 if (Entry.second && Generation == Entry.first)
14763 return Entry.second;
14768 Expr = Entry.second;
14771 Entry = {Generation, NewSCEV};
14777 if (!BackedgeCount) {
14780 for (
const auto *
P : Preds)
14783 return BackedgeCount;
14787 if (Preds->implies(&Pred))
14790 auto &OldPreds = Preds->getPredicates();
14793 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds);
14794 updateGeneration();
14801void PredicatedScalarEvolution::updateGeneration() {
14803 if (++Generation == 0) {
14804 for (
auto &II : RewriteMap) {
14805 const SCEV *Rewritten = II.second.second;
14814 const auto *AR = cast<SCEVAddRecExpr>(Expr);
14822 auto II = FlagsMap.insert({V, Flags});
14830 const auto *AR = cast<SCEVAddRecExpr>(Expr);
14835 auto II = FlagsMap.find(V);
14837 if (II != FlagsMap.end())
14851 for (
const auto *
P : NewPreds)
14854 RewriteMap[SE.
getSCEV(V)] = {Generation, New};
14860 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
14862 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {
14863 for (
auto I :
Init.FlagsMap)
14864 FlagsMap.insert(
I);
14869 for (
auto *BB : L.getBlocks())
14870 for (
auto &
I : *BB) {
14875 auto II = RewriteMap.find(Expr);
14877 if (II == RewriteMap.end())
14881 if (II->second.second == Expr)
14886 OS.
indent(
Depth + 2) <<
"--> " << *II->second.second <<
"\n";
14895bool ScalarEvolution::matchURem(
const SCEV *Expr,
const SCEV *&LHS,
14896 const SCEV *&RHS) {
14900 if (
const auto *ZExt = dyn_cast<SCEVZeroExtendExpr>(Expr))
14901 if (
const auto *Trunc = dyn_cast<SCEVTruncateExpr>(ZExt->getOperand(0))) {
14902 LHS = Trunc->getOperand();
14914 const auto *
Add = dyn_cast<SCEVAddExpr>(Expr);
14915 if (
Add ==
nullptr ||
Add->getNumOperands() != 2)
14918 const SCEV *
A =
Add->getOperand(1);
14919 const auto *
Mul = dyn_cast<SCEVMulExpr>(
Add->getOperand(0));
14921 if (
Mul ==
nullptr)
14924 const auto MatchURemWithDivisor = [&](
const SCEV *
B) {
14935 if (
Mul->getNumOperands() == 3 && isa<SCEVConstant>(
Mul->getOperand(0)))
14936 return MatchURemWithDivisor(
Mul->getOperand(1)) ||
14937 MatchURemWithDivisor(
Mul->getOperand(2));
14940 if (
Mul->getNumOperands() == 2)
14941 return MatchURemWithDivisor(
Mul->getOperand(1)) ||
14942 MatchURemWithDivisor(
Mul->getOperand(0)) ||
14949ScalarEvolution::computeSymbolicMaxBackedgeTakenCount(
const Loop *L) {
14951 L->getExitingBlocks(ExitingBlocks);
14957 for (
BasicBlock *ExitingBB : ExitingBlocks) {
14958 const SCEV *ExitCount =
14960 if (!isa<SCEVCouldNotCompute>(ExitCount)) {
14962 "We should only have known counts for exiting blocks that "
14963 "dominate latch!");
14967 if (ExitCounts.
empty())
14986 auto I = Map.find(Expr);
14987 if (
I == Map.end())
14993 auto I = Map.find(Expr);
14994 if (
I == Map.end()) {
15000 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
15001 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
15004 auto I = Map.find(NarrowExt);
15005 if (
I != Map.end())
15007 Bitwidth = Bitwidth / 2;
15017 auto I = Map.find(Expr);
15018 if (
I == Map.end())
15025 auto I = Map.find(Expr);
15026 if (
I == Map.end())
15032 auto I = Map.find(Expr);
15033 if (
I == Map.end())
15051 if (isa<SCEVConstant>(
LHS)) {
15059 auto MatchRangeCheckIdiom = [
this, Predicate,
LHS,
RHS, &RewriteMap,
15060 &ExprsToRewrite]() {
15061 auto *AddExpr = dyn_cast<SCEVAddExpr>(
LHS);
15062 if (!AddExpr || AddExpr->getNumOperands() != 2)
15065 auto *C1 = dyn_cast<SCEVConstant>(AddExpr->getOperand(0));
15066 auto *LHSUnknown = dyn_cast<SCEVUnknown>(AddExpr->getOperand(1));
15067 auto *C2 = dyn_cast<SCEVConstant>(
RHS);
15068 if (!C1 || !C2 || !LHSUnknown)
15073 .
sub(C1->getAPInt());
15076 if (ExactRegion.isWrappedSet() || ExactRegion.isFullSet())
15078 auto I = RewriteMap.find(LHSUnknown);
15079 const SCEV *RewrittenLHS =
I != RewriteMap.end() ?
I->second : LHSUnknown;
15086 if (MatchRangeCheckIdiom())
15092 auto IsMinMaxSCEVWithNonNegativeConstant =
15095 if (
auto *
MinMax = dyn_cast<SCEVMinMaxExpr>(Expr)) {
15096 if (
MinMax->getNumOperands() != 2)
15098 if (
auto *
C = dyn_cast<SCEVConstant>(
MinMax->getOperand(0))) {
15099 if (
C->getAPInt().isNegative())
15101 SCTy =
MinMax->getSCEVType();
15112 auto GetNonNegExprAndPosDivisor = [&](
const SCEV *Expr,
const SCEV *Divisor,
15114 auto *ConstExpr = dyn_cast<SCEVConstant>(Expr);
15115 auto *ConstDivisor = dyn_cast<SCEVConstant>(Divisor);
15116 if (!ConstExpr || !ConstDivisor)
15118 ExprVal = ConstExpr->getAPInt();
15119 DivisorVal = ConstDivisor->getAPInt();
15120 return ExprVal.isNonNegative() && !DivisorVal.isNonPositive();
15126 auto GetNextSCEVDividesByDivisor = [&](
const SCEV *Expr,
15127 const SCEV *Divisor) {
15130 if (!GetNonNegExprAndPosDivisor(Expr, Divisor, ExprVal, DivisorVal))
15142 auto GetPreviousSCEVDividesByDivisor = [&](
const SCEV *Expr,
15143 const SCEV *Divisor) {
15146 if (!GetNonNegExprAndPosDivisor(Expr, Divisor, ExprVal, DivisorVal))
15156 std::function<
const SCEV *(
const SCEV *,
const SCEV *)>
15157 ApplyDivisibiltyOnMinMaxExpr = [&](
const SCEV *MinMaxExpr,
15158 const SCEV *Divisor) {
15159 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15161 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15165 isa<SCEVSMinExpr>(MinMaxExpr) || isa<SCEVUMinExpr>(MinMaxExpr);
15167 "Expected non-negative operand!");
15168 auto *DivisibleExpr =
15169 IsMin ? GetPreviousSCEVDividesByDivisor(MinMaxLHS, Divisor)
15170 : GetNextSCEVDividesByDivisor(MinMaxLHS, Divisor);
15172 ApplyDivisibiltyOnMinMaxExpr(MinMaxRHS, Divisor), DivisibleExpr};
15183 const SCEV *URemLHS =
nullptr;
15184 const SCEV *URemRHS =
nullptr;
15185 if (matchURem(
LHS, URemLHS, URemRHS)) {
15186 if (
const SCEVUnknown *LHSUnknown = dyn_cast<SCEVUnknown>(URemLHS)) {
15187 auto I = RewriteMap.find(LHSUnknown);
15188 const SCEV *RewrittenLHS =
15189 I != RewriteMap.end() ?
I->second : LHSUnknown;
15190 RewrittenLHS = ApplyDivisibiltyOnMinMaxExpr(RewrittenLHS, URemRHS);
15191 const auto *Multiple =
15193 RewriteMap[LHSUnknown] = Multiple;
15205 if (!isa<SCEVUnknown>(
LHS) && isa<SCEVUnknown>(
RHS)) {
15214 auto AddRewrite = [&](
const SCEV *
From,
const SCEV *FromRewritten,
15216 if (
From == FromRewritten)
15218 RewriteMap[
From] = To;
15224 auto GetMaybeRewritten = [&](
const SCEV *S) {
15225 auto I = RewriteMap.find(S);
15226 return I != RewriteMap.end() ?
I->second : S;
15236 std::function<
bool(
const SCEV *,
const SCEV *&)> HasDivisibiltyInfo =
15237 [&](
const SCEV *Expr,
const SCEV *&DividesBy) {
15238 if (
auto *
Mul = dyn_cast<SCEVMulExpr>(Expr)) {
15239 if (
Mul->getNumOperands() != 2)
15241 auto *MulLHS =
Mul->getOperand(0);
15242 auto *MulRHS =
Mul->getOperand(1);
15243 if (isa<SCEVConstant>(MulLHS))
15245 if (
auto *Div = dyn_cast<SCEVUDivExpr>(MulLHS))
15246 if (Div->getOperand(1) == MulRHS) {
15247 DividesBy = MulRHS;
15251 if (
auto *
MinMax = dyn_cast<SCEVMinMaxExpr>(Expr))
15252 return HasDivisibiltyInfo(
MinMax->getOperand(0), DividesBy) ||
15253 HasDivisibiltyInfo(
MinMax->getOperand(1), DividesBy);
15258 std::function<
bool(
const SCEV *,
const SCEV *&)> IsKnownToDivideBy =
15259 [&](
const SCEV *Expr,
const SCEV *DividesBy) {
15262 if (
auto *
MinMax = dyn_cast<SCEVMinMaxExpr>(Expr))
15263 return IsKnownToDivideBy(
MinMax->getOperand(0), DividesBy) &&
15264 IsKnownToDivideBy(
MinMax->getOperand(1), DividesBy);
15268 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15269 const SCEV *DividesBy =
nullptr;
15270 if (HasDivisibiltyInfo(RewrittenLHS, DividesBy))
15273 IsKnownToDivideBy(RewrittenLHS, DividesBy) ? DividesBy :
nullptr;
15287 switch (Predicate) {
15295 RHS = DividesBy ? GetPreviousSCEVDividesByDivisor(
RHS, DividesBy) :
RHS;
15301 RHS = DividesBy ? GetNextSCEVDividesByDivisor(
RHS, DividesBy) :
RHS;
15305 RHS = DividesBy ? GetPreviousSCEVDividesByDivisor(
RHS, DividesBy) :
RHS;
15309 RHS = DividesBy ? GetNextSCEVDividesByDivisor(
RHS, DividesBy) :
RHS;
15318 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
15322 while (!Worklist.
empty()) {
15324 if (isa<SCEVConstant>(
From))
15328 const SCEV *FromRewritten = GetMaybeRewritten(
From);
15329 const SCEV *To =
nullptr;
15331 switch (Predicate) {
15335 if (
auto *
UMax = dyn_cast<SCEVUMaxExpr>(FromRewritten))
15336 EnqueueOperands(
UMax);
15341 if (
auto *
SMax = dyn_cast<SCEVSMaxExpr>(FromRewritten))
15342 EnqueueOperands(
SMax);
15347 if (
auto *
UMin = dyn_cast<SCEVUMinExpr>(FromRewritten))
15348 EnqueueOperands(
UMin);
15353 if (
auto *
SMin = dyn_cast<SCEVSMinExpr>(FromRewritten))
15354 EnqueueOperands(
SMin);
15357 if (isa<SCEVConstant>(
RHS))
15361 if (isa<SCEVConstant>(
RHS) &&
15362 cast<SCEVConstant>(
RHS)->getValue()->isNullValue()) {
15363 const SCEV *OneAlignedUp =
15364 DividesBy ? GetNextSCEVDividesByDivisor(One, DividesBy) : One;
15373 AddRewrite(
From, FromRewritten, To);
15383 auto *AssumeI = cast<CallInst>(AssumeVH);
15390 auto *GuardDecl =
F.getParent()->getFunction(
15393 for (
const auto *GU : GuardDecl->users())
15394 if (
const auto *Guard = dyn_cast<IntrinsicInst>(GU))
15395 if (Guard->getFunction() == Header->getParent() && DT.
dominates(Guard, Header))
15403 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(
15404 L->getLoopPredecessor(), Header);
15405 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
15408 dyn_cast<BranchInst>(Pair.first->getTerminator());
15421 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
15425 while (!Worklist.
empty()) {
15430 if (
auto *Cmp = dyn_cast<ICmpInst>(
Cond)) {
15432 EnterIfTrue ? Cmp->getPredicate() : Cmp->getInversePredicate();
15433 const auto *
LHS =
getSCEV(Cmp->getOperand(0));
15434 const auto *
RHS =
getSCEV(Cmp->getOperand(1));
15435 CollectCondition(Predicate,
LHS,
RHS, RewriteMap);
15448 if (RewriteMap.
empty())
15454 if (ExprsToRewrite.
size() > 1) {
15455 for (
const SCEV *Expr : ExprsToRewrite) {
15456 const SCEV *RewriteTo = RewriteMap[Expr];
15457 RewriteMap.
erase(Expr);
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements a class to represent arbitrary precision integral constant values and operations...
Expand Atomic instructions
block Block Frequency Analysis
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
Generic implementation of equivalence classes through the use Tarjan's efficient union-find algorithm...
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool isSigned(unsigned int Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
iv Induction Variable Users
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
mir Rename Register Operands
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
PowerPC Reduce CR logical Operation
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
static bool rewrite(Function &F)
const SmallVectorImpl< MachineOperand > & Cond
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI optimize exec mask operations pre RA
This file provides utility classes that use RAII to save and restore values.
bool SCEVMinMaxExprContains(const SCEV *Root, const SCEV *OperandToFind, SCEVTypes RootKind)
static cl::opt< unsigned > MaxAddRecSize("scalar-evolution-max-add-rec-size", cl::Hidden, cl::desc("Max coefficients in AddRec during evolving"), cl::init(8))
static cl::opt< unsigned > RangeIterThreshold("scev-range-iter-threshold", cl::Hidden, cl::desc("Threshold for switching to iteratively computing SCEV ranges"), cl::init(32))
static const Loop * isIntegerLoopHeaderPHI(const PHINode *PN, LoopInfo &LI)
static unsigned getConstantTripCount(const SCEVConstant *ExitCount)
static void PushLoopPHIs(const Loop *L, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push PHI nodes in the header of the given loop onto the given Worklist.
static void insertFoldCacheEntry(const ScalarEvolution::FoldID &ID, const SCEV *S, DenseMap< ScalarEvolution::FoldID, const SCEV * > &FoldCache, DenseMap< const SCEV *, SmallVector< ScalarEvolution::FoldID, 2 > > &FoldCacheUser)
static bool IsKnownPredicateViaMinOrMax(ScalarEvolution &SE, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Is LHS Pred RHS true on the virtue of LHS or RHS being a Min or Max expression?
static cl::opt< bool > ClassifyExpressions("scalar-evolution-classify-expressions", cl::Hidden, cl::init(true), cl::desc("When printing analysis, include information on every instruction"))
static bool CanConstantFold(const Instruction *I)
Return true if we can constant fold an instruction of the specified type, assuming that all operands ...
static cl::opt< unsigned > AddOpsInlineThreshold("scev-addops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining addition operands into a SCEV"), cl::init(500))
static cl::opt< bool > VerifyIR("scev-verify-ir", cl::Hidden, cl::desc("Verify IR correctness when making sensitive SCEV queries (slow)"), cl::init(false))
static bool BrPHIToSelect(DominatorTree &DT, BranchInst *BI, PHINode *Merge, Value *&C, Value *&LHS, Value *&RHS)
static const SCEV * getPreStartForExtend(const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE, unsigned Depth)
static std::optional< APInt > MinOptional(std::optional< APInt > X, std::optional< APInt > Y)
Helper function to compare optional APInts: (a) if X and Y both exist, return min(X,...
static cl::opt< unsigned > MulOpsInlineThreshold("scev-mulops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining multiplication operands into a SCEV"), cl::init(32))
static void GroupByComplexity(SmallVectorImpl< const SCEV * > &Ops, LoopInfo *LI, DominatorTree &DT)
Given a list of SCEV objects, order them by their complexity, and group objects of the same complexit...
static std::optional< const SCEV * > createNodeForSelectViaUMinSeq(ScalarEvolution *SE, const SCEV *CondExpr, const SCEV *TrueExpr, const SCEV *FalseExpr)
static Constant * BuildConstantFromSCEV(const SCEV *V)
This builds up a Constant using the ConstantExpr interface.
static ConstantInt * EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C, ScalarEvolution &SE)
static const SCEV * BinomialCoefficient(const SCEV *It, unsigned K, ScalarEvolution &SE, Type *ResultTy)
Compute BC(It, K). The result has width W. Assume, K > 0.
static cl::opt< unsigned > MaxCastDepth("scalar-evolution-max-cast-depth", cl::Hidden, cl::desc("Maximum depth of recursive SExt/ZExt/Trunc"), cl::init(8))
static bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr, const SCEV *Candidate)
Is MaybeMinMaxExpr an (U|S)(Min|Max) of Candidate and some other values?
static PHINode * getConstantEvolvingPHI(Value *V, const Loop *L)
getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node in the loop that V is deri...
static cl::opt< unsigned > MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, cl::desc("Maximum number of iterations SCEV will " "symbolically execute a constant " "derived loop"), cl::init(100))
static bool MatchBinarySub(const SCEV *S, const SCEV *&LHS, const SCEV *&RHS)
static std::optional< int > CompareSCEVComplexity(EquivalenceClasses< const SCEV * > &EqCacheSCEV, EquivalenceClasses< const Value * > &EqCacheValue, const LoopInfo *const LI, const SCEV *LHS, const SCEV *RHS, DominatorTree &DT, unsigned Depth=0)
static uint64_t umul_ov(uint64_t i, uint64_t j, bool &Overflow)
static void PrintSCEVWithTypeHint(raw_ostream &OS, const SCEV *S)
When printing a top-level SCEV for trip counts, it's helpful to include a type for constants which ar...
static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE, const Loop *L)
static bool containsConstantInAddMulChain(const SCEV *StartExpr)
Determine if any of the operands in this SCEV are a constant or if any of the add or multiply express...
static const SCEV * getExtendAddRecStart(const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE, unsigned Depth)
static bool hasHugeExpression(ArrayRef< const SCEV * > Ops)
Returns true if Ops contains a huge SCEV (the subtree of S contains at least HugeExprThreshold nodes)...
static cl::opt< unsigned > MaxPhiSCCAnalysisSize("scalar-evolution-max-scc-analysis-depth", cl::Hidden, cl::desc("Maximum amount of nodes to process while searching SCEVUnknown " "Phi strongly connected components"), cl::init(8))
static int CompareValueComplexity(EquivalenceClasses< const Value * > &EqCacheValue, const LoopInfo *const LI, Value *LV, Value *RV, unsigned Depth)
Compare the two values LV and RV in terms of their "complexity" where "complexity" is a partial (and ...
static cl::opt< unsigned > MaxSCEVOperationsImplicationDepth("scalar-evolution-max-scev-operations-implication-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV operations implication analysis"), cl::init(2))
static void PushDefUseChildren(Instruction *I, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push users of the given Instruction onto the given Worklist.
static std::optional< APInt > SolveQuadraticAddRecRange(const SCEVAddRecExpr *AddRec, const ConstantRange &Range, ScalarEvolution &SE)
Let c(n) be the value of the quadratic chrec {0,+,M,+,N} after n iterations.
static cl::opt< bool > UseContextForNoWrapFlagInference("scalar-evolution-use-context-for-no-wrap-flag-strenghening", cl::Hidden, cl::desc("Infer nuw/nsw flags using context where suitable"), cl::init(true))
static cl::opt< bool > EnableFiniteLoopControl("scalar-evolution-finite-loop", cl::Hidden, cl::desc("Handle <= and >= in finite loops"), cl::init(true))
static std::optional< std::tuple< APInt, APInt, APInt, APInt, unsigned > > GetQuadraticEquation(const SCEVAddRecExpr *AddRec)
For a given quadratic addrec, generate coefficients of the corresponding quadratic equation,...
static std::optional< BinaryOp > MatchBinaryOp(Value *V, const DataLayout &DL, AssumptionCache &AC, const DominatorTree &DT, const Instruction *CxtI)
Try to map V into a BinaryOp, and return std::nullopt on failure.
APInt gcd(const SCEVConstant *C1, const SCEVConstant *C2)
static std::optional< APInt > SolveQuadraticAddRecExact(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE)
Let c(n) be the value of the quadratic chrec {L,+,M,+,N} after n iterations.
static std::optional< APInt > TruncIfPossible(std::optional< APInt > X, unsigned BitWidth)
Helper function to truncate an optional APInt to a given BitWidth.
static bool IsKnownPredicateViaAddRecStart(ScalarEvolution &SE, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
static cl::opt< unsigned > MaxSCEVCompareDepth("scalar-evolution-max-scev-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV complexity comparisons"), cl::init(32))
static APInt extractConstantWithoutWrapping(ScalarEvolution &SE, const SCEVConstant *ConstantTerm, const SCEVAddExpr *WholeAddExpr)
static cl::opt< unsigned > MaxConstantEvolvingDepth("scalar-evolution-max-constant-evolving-depth", cl::Hidden, cl::desc("Maximum depth of recursive constant evolving"), cl::init(32))
static const SCEV * SolveLinEquationWithOverflow(const APInt &A, const SCEV *B, ScalarEvolution &SE)
Finds the minimum unsigned root of the following equation:
static ConstantRange getRangeForAffineARHelper(APInt Step, const ConstantRange &StartRange, const APInt &MaxBECount, bool Signed)
static std::optional< ConstantRange > GetRangeFromMetadata(Value *V)
Helper method to assign a range to V from metadata present in the IR.
static bool CollectAddOperandsWithScales(DenseMap< const SCEV *, APInt > &M, SmallVectorImpl< const SCEV * > &NewOps, APInt &AccumulatedConstant, ArrayRef< const SCEV * > Ops, const APInt &Scale, ScalarEvolution &SE)
Process the given Ops list, which is a list of operands to be added under the given scale,...
static cl::opt< unsigned > HugeExprThreshold("scalar-evolution-huge-expr-threshold", cl::Hidden, cl::desc("Size of the expression which is considered huge"), cl::init(4096))
static bool isKnownPredicateExtendIdiom(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
static Type * isSimpleCastedPHI(const SCEV *Op, const SCEVUnknown *SymbolicPHI, bool &Signed, ScalarEvolution &SE)
Helper function to createAddRecFromPHIWithCasts.
static Constant * EvaluateExpression(Value *V, const Loop *L, DenseMap< Instruction *, Constant * > &Vals, const DataLayout &DL, const TargetLibraryInfo *TLI)
EvaluateExpression - Given an expression that passes the getConstantEvolvingPHI predicate,...
static const SCEV * MatchNotExpr(const SCEV *Expr)
If Expr computes ~A, return A else return nullptr.
static cl::opt< unsigned > MaxValueCompareDepth("scalar-evolution-max-value-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive value complexity comparisons"), cl::init(2))
static cl::opt< bool, true > VerifySCEVOpt("verify-scev", cl::Hidden, cl::location(VerifySCEV), cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"))
static const SCEV * getSignedOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static SCEV::NoWrapFlags StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, const ArrayRef< const SCEV * > Ops, SCEV::NoWrapFlags Flags)
static cl::opt< unsigned > MaxArithDepth("scalar-evolution-max-arith-depth", cl::Hidden, cl::desc("Maximum depth of recursive arithmetics"), cl::init(32))
static bool HasSameValue(const SCEV *A, const SCEV *B)
SCEV structural equivalence is usually sufficient for testing whether two expressions are equal,...
static uint64_t Choose(uint64_t n, uint64_t k, bool &Overflow)
Compute the result of "n choose k", the binomial coefficient.
static bool canConstantEvolve(Instruction *I, const Loop *L)
Determine whether this instruction can constant evolve within this loop assuming its operands can all...
static PHINode * getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L, DenseMap< Instruction *, PHINode * > &PHIMap, unsigned Depth)
getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by recursing through each instructi...
static bool scevUnconditionallyPropagatesPoisonFromOperands(SCEVTypes Kind)
static cl::opt< bool > VerifySCEVStrict("verify-scev-strict", cl::Hidden, cl::desc("Enable stricter verification with -verify-scev is passed"))
static Constant * getOtherIncomingValue(PHINode *PN, BasicBlock *BB)
static cl::opt< bool > UseExpensiveRangeSharpening("scalar-evolution-use-expensive-range-sharpening", cl::Hidden, cl::init(false), cl::desc("Use more powerful methods of sharpening expression ranges. May " "be costly in terms of compile time"))
static const SCEV * getUnsignedOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
Provides some synthesis utilities to produce sequences of values.
This file defines the SmallPtrSet class.
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static SymbolRef::Type getType(const Symbol *Sym)
This defines the Use class.
static std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
Virtual Register Rewriter
static const uint32_t IV[8]
A rewriter to replace SCEV expressions in Map with the corresponding entry in the map.
const SCEV * visitAddRecExpr(const SCEVAddRecExpr *Expr)
const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)
SCEVLoopGuardRewriter(ScalarEvolution &SE, DenseMap< const SCEV *, const SCEV * > &M)
const SCEV * visitSignExtendExpr(const SCEVSignExtendExpr *Expr)
const SCEV * visitUnknown(const SCEVUnknown *Expr)
const SCEV * visitUMinExpr(const SCEVUMinExpr *Expr)
const SCEV * visitSMinExpr(const SCEVSMinExpr *Expr)
Class for arbitrary precision integers.
APInt umul_ov(const APInt &RHS, bool &Overflow) const
APInt udiv(const APInt &RHS) const
Unsigned division operation.
APInt zext(unsigned width) const
Zero extend to a new width.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
uint64_t getZExtValue() const
Get zero extended value.
void setHighBits(unsigned hiBits)
Set the top hiBits bits.
APInt multiplicativeInverse(const APInt &modulo) const
Computes the multiplicative inverse of this APInt for a given modulo.
APInt getHiBits(unsigned numBits) const
Compute an APInt containing numBits highbits from this APInt.
APInt zextOrTrunc(unsigned width) const
Zero extend or truncate to width.
unsigned getActiveBits() const
Compute the number of active bits in the value.
APInt trunc(unsigned width) const
Truncate to new width.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
APInt abs() const
Get the absolute value.
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool isSignMask() const
Check if the APInt's value is returned by getSignMask.
APInt urem(const APInt &RHS) const
Unsigned remainder operation.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
bool isNegative() const
Determine sign of this APInt.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
unsigned countTrailingZeros() const
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
APInt sext(unsigned width) const
Sign extend to a new width.
APInt shl(unsigned shiftAmt) const
Left-shift function.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
bool isSignBitSet() const
Determine if sign bit of this APInt is set.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
API to communicate dependencies between analyses during invalidation.
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Trigger the invalidation of some other analysis pass if not already handled and return whether it was...
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
AnalysisUsage & addRequiredTransitive()
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
ArrayRef< T > take_front(size_t N=1) const
Return a copy of *this with only the first N elements.
size_t size() const
size - Get the array size.
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
MutableArrayRef< ResultElem > assumptions()
Access the list of assumption handles currently tracked for this function.
bool isSingleEdge() const
Check if this is the only edge between Start and End.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const Instruction & front() const
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Function * getParent() const
Return the enclosing method, or null if none.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
BinaryOps getOpcode() const
Conditional or Unconditional Branch instruction.
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
Value * getCondition() const
LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
This class represents a function call, abstracting a target machine's calling convention.
Value handle with callbacks on RAUW and destruction.
bool isFalseWhenEqual() const
This is just a convenience.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ ICMP_UGE
unsigned greater or equal
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
@ ICMP_SGE
signed greater or equal
@ ICMP_ULE
unsigned less or equal
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
bool isTrueWhenEqual() const
This is just a convenience.
Predicate getNonStrictPredicate() const
For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Predicate getPredicate() const
Return the predicate for this instruction.
Predicate getFlippedSignednessPredicate()
For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->Failed assert.
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
static Constant * getNot(Constant *C)
static Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static Constant * getICmp(unsigned short pred, Constant *LHS, Constant *RHS, bool OnlyIfReduced=false)
get* - Return some common constants without having to specify the full Instruction::OPCODE identifier...
static Constant * getGetElementPtr(Type *Ty, Constant *C, ArrayRef< Constant * > IdxList, bool InBounds=false, std::optional< unsigned > InRangeIndex=std::nullopt, Type *OnlyIfReducedTy=nullptr)
Getelementptr form.
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
This is the shared class of boolean and integer constants.
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static ConstantInt * getFalse(LLVMContext &Context)
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
static ConstantInt * getBool(LLVMContext &Context, bool V)
This class represents a range of values.
ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
ConstantRange zextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
PreferredRangeType
If represented precisely, the result of some range operations may consist of multiple disjoint ranges...
bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
const APInt & getLower() const
Return the lower value for this range.
ConstantRange truncate(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other? NOTE: false does not mean that inverse pr...
bool isEmptySet() const
Return true if this set contains no members.
ConstantRange zeroExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
bool isSignWrappedSet() const
Return true if this set wraps around the signed domain.
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
bool isWrappedSet() const
Return true if this set wraps around the unsigned domain.
void print(raw_ostream &OS) const
Print out the bounds to a stream.
ConstantRange signExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
const APInt & getUpper() const
Return the upper value for this range.
ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
unsigned getMinSignedBits() const
Compute the maximal number of bits needed to represent every value in this signed range.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
static ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)
Produce the range that contains X if and only if "X BinOp Other" does not wrap.
This is an important base class in LLVM.
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
IntegerType * getIntPtrType(LLVMContext &C, unsigned AddressSpace=0) const
Returns an integer type with size at least as big as that of a pointer in the given address space.
unsigned getIndexTypeSizeInBits(Type *Ty) const
Layout size of the index used in GEP calculation.
IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
TypeSize getTypeSizeInBits(Type *Ty) const
Size examples:
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive,...
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Analysis pass which computes a DominatorTree.
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...
member_iterator unionSets(const ElemTy &V1, const ElemTy &V2)
union - Merge the two equivalence sets for the specified values, inserting them if they do not alread...
bool isEquivalent(const ElemTy &V1, const ElemTy &V2) const
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID,...
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
FunctionPass class - This class is used to implement most global optimizations.
const BasicBlock & getEntryBlock() const
static Type * getTypeAtIndex(Type *Ty, Value *Idx)
Return the type of the element at the given index of an indexable type.
Module * getParent()
Get the module that this global value is contained inside of...
static bool isPrivateLinkage(LinkageTypes Linkage)
static bool isInternalLinkage(LinkageTypes Linkage)
This instruction compares its operands according to the predicate given to the constructor.
static bool isGE(Predicate P)
Return true if the predicate is SGE or UGE.
static bool isLT(Predicate P)
Return true if the predicate is SLT or ULT.
static bool isGT(Predicate P)
Return true if the predicate is SGT or UGT.
bool isEquality() const
Return true if this predicate is either EQ or NE.
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
static bool isLE(Predicate P)
Return true if the predicate is SLE or ULE.
bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
const BasicBlock * getParent() const
Class to represent integer types.
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
An instruction for reading from memory.
Analysis pass that exposes the LoopInfo for a function.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getHeader() const
unsigned getLoopDepth() const
Return the nesting level of this loop.
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
A Module instance is used to store all the information related to an LLVM module.
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
This is a utility class that provides an abstraction for the common functionality between Instruction...
unsigned getOpcode() const
Return the opcode for this Instruction or ConstantExpr.
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
bool hasNoSignedWrap() const
Test whether this operation is known to never undergo signed overflow, aka the nsw property.
bool hasNoUnsignedWrap() const
Test whether this operation is known to never undergo unsigned overflow, aka the nuw property.
iterator_range< const_block_iterator > blocks() const
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PointerIntPair - This class implements a pair of a pointer and small integer.
static PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the default address space (address sp...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
const SCEVPredicate & getPredicate() const
bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've proved that V doesn't wrap by means of a SCEV predicate.
void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Proves that V doesn't overflow by adding SCEV predicate.
void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds.
PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
constexpr bool isValid() const
This node represents an addition of some number of SCEVs.
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * getStart() const
const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a recurrence without clearing any previously set flags.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
bool isQuadratic() const
Return true if this represents an expression A + B*x + C*x^2 where A, B and C are loop invariant valu...
const SCEV * getNumIterationsInRange(const ConstantRange &Range, ScalarEvolution &SE) const
Return the number of iterations of this loop that produce values in the specified constant range.
const SCEVAddRecExpr * getPostIncExpr(ScalarEvolution &SE) const
Return an expression representing the value of this expression one iteration of the loop ahead.
const Loop * getLoop() const
This is the base class for unary cast operator classes.
const SCEV * getOperand() const
SCEVCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, const SCEV *op, Type *ty)
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a non-recurrence without clearing previously set flags.
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
SCEVComparePredicate(const FoldingSetNodeIDRef ID, const ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
bool implies(const SCEVPredicate *N) const override
Implementation of the SCEVPredicate interface.
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
This class represents a constant integer value.
ConstantInt * getValue() const
const APInt & getAPInt() const
This is the base class for unary integral cast operator classes.
SCEVIntegralCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, const SCEV *op, Type *ty)
This node is the base class min/max selections.
static enum SCEVTypes negate(enum SCEVTypes T)
This node represents multiplication of some number of SCEVs.
This node is a base class providing common functionality for n'ary operators.
bool hasNoUnsignedWrap() const
bool hasNoSelfWrap() const
size_t getNumOperands() const
bool hasNoSignedWrap() const
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
const SCEV * getOperand(unsigned i) const
const SCEV *const * Operands
ArrayRef< const SCEV * > operands() const
This class represents an assumption made using SCEV expressions which can be checked at run-time.
virtual bool implies(const SCEVPredicate *N) const =0
Returns true if this predicate implies N.
SCEVPredicate(const SCEVPredicate &)=default
virtual void print(raw_ostream &OS, unsigned Depth=0) const =0
Prints a textual representation of this predicate with an indentation of Depth.
This class represents a cast from a pointer to a pointer-sized integer value.
This visitor recursively visits a SCEV expression and re-writes it.
const SCEV * visitSignExtendExpr(const SCEVSignExtendExpr *Expr)
const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)
const SCEV * visitSMinExpr(const SCEVSMinExpr *Expr)
const SCEV * visitUMinExpr(const SCEVUMinExpr *Expr)
This class represents a signed maximum selection.
This class represents a signed minimum selection.
This node is the base class for sequential/in-order min/max selections.
SCEVTypes getEquivalentNonSequentialSCEVType() const
This class represents a sequential/in-order unsigned minimum selection.
This class represents a sign extension of a small integer value to a larger integer value.
Visit all nodes in the expression tree using worklist traversal.
void visitAll(const SCEV *Root)
This class represents a truncation of an integer value to a smaller integer value.
This class represents a binary unsigned division operation.
const SCEV * getLHS() const
const SCEV * getRHS() const
This class represents an unsigned maximum selection.
This class represents an unsigned minimum selection.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
SCEVUnionPredicate(ArrayRef< const SCEVPredicate * > Preds)
Union predicates don't get cached so create a dummy set ID for it.
void print(raw_ostream &OS, unsigned Depth) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
bool implies(const SCEVPredicate *N) const override
Returns true if this predicate implies N.
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents the value of vscale, as used when defining the length of a scalable vector or r...
This class represents an assumption made on an AddRec expression.
IncrementWrapFlags
Similar to SCEV::NoWrapFlags, but with slightly different semantics for FlagNUSW.
SCEVWrapPredicate(const FoldingSetNodeIDRef ID, const SCEVAddRecExpr *AR, IncrementWrapFlags Flags)
bool implies(const SCEVPredicate *N) const override
Returns true if this predicate implies N.
static SCEVWrapPredicate::IncrementWrapFlags setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OnFlags)
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
const SCEVAddRecExpr * getExpr() const
Implementation of the SCEVPredicate interface.
static SCEVWrapPredicate::IncrementWrapFlags clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OffFlags)
Convenient IncrementWrapFlags manipulation methods.
static SCEVWrapPredicate::IncrementWrapFlags getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE)
Returns the set of SCEVWrapPredicate no wrap flags implied by a SCEVAddRecExpr.
IncrementWrapFlags getFlags() const
Returns the set assumed no overflow flags.
This class represents a zero extension of a small integer value to a larger integer value.
This class represents an analyzed expression in the program.
ArrayRef< const SCEV * > operands() const
Return operands of this SCEV expression.
unsigned short getExpressionSize() const
bool isOne() const
Return true if the expression is a constant one.
bool isZero() const
Return true if the expression is a constant zero.
void dump() const
This method is used for debugging.
bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
SCEVTypes getSCEVType() const
Type * getType() const
Return the LLVM type of this SCEV expression.
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
Analysis pass that exposes the ScalarEvolution for a function.
ScalarEvolution run(Function &F, FunctionAnalysisManager &AM)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
void print(raw_ostream &OS, const Module *=nullptr) const override
print - Print out the internal state of the pass.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
The main scalar evolution driver.
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
static bool hasFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags TestFlags)
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether the backedge of the loop is protected by a conditional between LHS and RHS.
const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getUDivCeilSCEV(const SCEV *N, const SCEV *D)
Compute ceil(N / D).
const SCEV * getGEPExpr(GEPOperator *GEP, const SmallVectorImpl< const SCEV * > &IndexExprs)
Returns an expression for a GEP.
Type * getWiderType(Type *Ty1, Type *Ty2) const
const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)
bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
const SCEV * getURemExpr(const SCEV *LHS, const SCEV *RHS)
Represents an unsigned remainder expression based on unsigned division.
bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS, const SCEV *&RHS, unsigned Depth=0)
Simplify LHS and RHS in a comparison with predicate Pred.
APInt getConstantMultiple(const SCEV *S)
Returns the max constant multiple of S.
bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags)
Update no-wrap flags of an AddRec.
const SCEV * getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS)
Promote the operands to the wider of the types using zero-extension, and then perform a umax operatio...
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?...
ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsOnlyExit, bool AllowPredicates=false)
Compute the number of times the backedge of the specified loop will execute if its exit condition wer...
const SCEV * getZeroExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
const SCEV * getConstant(ConstantInt *V)
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
unsigned getSmallConstantMaxTripCount(const Loop *L)
Returns the upper bound of the loop trip count as a normal unsigned value.
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI)
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
const SCEV * getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty)
const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
const SCEV * getLosslessPtrToIntExpr(const SCEV *Op, unsigned Depth=0)
bool isKnownViaInduction(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
We'd like to check the predicate on every iteration of the most dominated loop between loops used in ...
std::optional< bool > evaluatePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Check whether the condition described by Pred, LHS, and RHS is true or false.
bool isKnownPredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
APInt getUnsignedRangeMin(const SCEV *S)
Determine the min of the unsigned range for a particular SCEV.
bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
const SCEV * getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo)
Return an expression for offsetof on the given field with type IntTy.
LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
const SCEV * getSignExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the basic block is protected by a conditional between LHS and RHS.
bool isKnownOnEveryIteration(ICmpInst::Predicate Pred, const SCEVAddRecExpr *LHS, const SCEV *RHS)
Test if the condition described by Pred, LHS, RHS is known to be true on every iteration of the loop ...
bool hasOperand(const SCEV *S, const SCEV *Op) const
Test whether the given SCEV has Op as a direct or indirect operand.
const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
const SCEVPredicate * getComparePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
const SCEV * getNotSCEV(const SCEV *V)
Return the SCEV object corresponding to ~V.
std::optional< LoopInvariantPredicate > getLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI=nullptr)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L, return a LoopInvaria...
bool instructionCouldExistWithOperands(const SCEV *A, const SCEV *B)
Return true if there exists a point in the program at which both A and B could be operands to the sam...
std::optional< bool > evaluatePredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Check whether the condition described by Pred, LHS, and RHS is true or false in the given Context.
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
uint32_t getMinTrailingZeros(const SCEV *S)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
void print(raw_ostream &OS) const
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVector< const SCEVPredicate *, 4 > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
void forgetTopmostLoop(const Loop *L)
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
APInt getSignedRangeMin(const SCEV *S)
Determine the min of the signed range for a particular SCEV.
const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
@ MonotonicallyDecreasing
@ MonotonicallyIncreasing
const SCEV * getStoreSizeOfExpr(Type *IntTy, Type *StoreTy)
Return an expression for the store size of StoreTy that is type IntTy.
const SCEVPredicate * getWrapPredicate(const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
APInt getNonZeroConstantMultiple(const SCEV *S)
const SCEV * getMinusOne(Type *Ty)
Return a SCEV for the constant -1 of a specific type.
static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB)
Return the "disposition" of the given SCEV with respect to the given block.
const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
Promote the operands to the wider of the types using zero-extension, and then perform a umin operatio...
bool loopIsFiniteByAssumption(const Loop *L)
Return true if this loop is finite by assumption.
const SCEV * getExistingSCEV(Value *V)
Return an existing SCEV for V if there is one, otherwise return nullptr.
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
@ LoopComputable
The SCEV varies predictably with the loop.
@ LoopVariant
The SCEV is loop-variant (unknown).
@ LoopInvariant
The SCEV is loop-invariant.
friend class SCEVCallbackVH
const SCEV * getAnyExtendExpr(const SCEV *Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
const SCEVAddRecExpr * convertSCEVToAddRecWithPredicates(const SCEV *S, const Loop *L, SmallPtrSetImpl< const SCEVPredicate * > &Preds)
Tries to convert the S expression to an AddRec expression, adding additional predicates to Preds as r...
std::optional< SCEV::NoWrapFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)
Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...
bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
const SCEV * getCouldNotCompute()
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
@ DominatesBlock
The SCEV dominates the block.
@ ProperlyDominatesBlock
The SCEV properly dominates the block.
@ DoesNotDominateBlock
The SCEV does not dominate the block.
std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterationsImpl(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
void getPoisonGeneratingValues(SmallPtrSetImpl< const Value * > &Result, const SCEV *S)
Return the set of Values that, if poison, will definitively result in S being poison as well.
void forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
const SCEV * getVScale(Type *Ty)
unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
APInt getUnsignedRangeMax(const SCEV *S)
Determine the max of the unsigned range for a particular SCEV.
ExitCountKind
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of ...
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
@ ConstantMaximum
A constant which provides an upper bound on the exact trip count.
@ Exact
An expression exactly describing the number of times the backedge has executed when a loop is exited.
std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterations(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L at given Context duri...
const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
const SCEV * getSizeOfExpr(Type *IntTy, TypeSize Size)
Return an expression for a TypeSize.
const SCEV * getUnknown(Value *V)
std::optional< std::pair< const SCEV *, SmallVector< const SCEVPredicate *, 3 > > > createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI)
Checks if SymbolicPHI can be rewritten as an AddRecExpr under some Predicates.
const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
const SCEV * getElementCount(Type *Ty, ElementCount EC)
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask)
Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name ...
std::optional< APInt > computeConstantDifference(const SCEV *LHS, const SCEV *RHS)
Compute LHS - RHS and returns the result as an APInt if it is a constant, and std::nullopt if it isn'...
bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
bool canReuseInstruction(const SCEV *S, Instruction *I, SmallVectorImpl< Instruction * > &DropPoisonGeneratingInsts)
Check whether it is poison-safe to represent the expression S using the instruction I.
const SCEV * getUDivExactExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
void registerUser(const SCEV *User, ArrayRef< const SCEV * > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool containsErasedValue(const SCEV *S) const
Return true if the SCEV expression contains a Value that has been optimised out and is now a nullptr.
const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
LLVMContext & getContext() const
This class represents the LLVM 'select' instruction.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
TypeSize getElementOffset(unsigned Idx) const
TypeSize getSizeInBits() const
Class to represent struct types.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isPointerTy() const
True if this is an instance of PointerType.
static IntegerType * getInt1Ty(LLVMContext &C)
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
static IntegerType * getInt8Ty(LLVMContext &C)
bool isIntOrPtrTy() const
Return true if this is an integer type or a pointer type.
static IntegerType * getInt32Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
unsigned getValueID() const
Return an ID for the concrete type of this object.
void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
StringRef getName() const
Return a constant reference to the value's name.
Represents an op.with.overflow intrinsic.
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
std::optional< APInt > SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, unsigned RangeWidth)
Let q(n) = An^2 + Bn + C, and BW = bit width of the value range (e.g.
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
bool match(Val *V, const Pattern &P)
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
bind_ty< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
initializer< Ty > init(const Ty &Val)
LocationClass< Ty > location(Ty &L)
@ Switch
The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...
NodeAddr< PhiNode * > Phi
This is an optimization pass for GlobalISel generic memory operations.
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to be non-zero when defined.
void stable_sort(R &&Range)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
bool canCreatePoison(const Operator *Op, bool ConsiderFlagsAndMetadata=true)
bool mustTriggerUB(const Instruction *I, const SmallPtrSetImpl< const Value * > &KnownPoison)
Return true if the given instruction must trigger undefined behavior when I is executed with any oper...
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
bool canConstantFoldCallTo(const CallBase *Call, const Function *F)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
auto successors(const MachineBasicBlock *BB)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
unsigned short computeExpressionSize(ArrayRef< const SCEV * > Args)
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO, const DominatorTree &DT)
Returns true if the arithmetic part of the WO 's result is used only along the paths control dependen...
bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step)
Attempt to match a simple first order recurrence cycle of the form: iv = phi Ty [Start,...
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, const TargetLibraryInfo *TLI, ObjectSizeOpts Opts={})
Compute the size of the object pointed by Ptr.
void initializeScalarEvolutionWrapperPassPass(PassRegistry &)
auto reverse(ContainerTy &&C)
bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
Constant * ConstantFoldInstOperands(Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
bool isFinite(const Loop *L)
Return true if this loop can be assumed to run for a finite number of iterations.
bool programUndefinedIfPoison(const Instruction *Inst)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isPointerTy(const Type *T)
ConstantRange getVScaleRange(const Function *F, unsigned BitWidth)
Determine the possible constant range of vscale with the given bit width, based on the vscale_range f...
@ Mod
The access may modify the value stored in memory.
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
bool propagatesPoison(const Use &PoisonOp)
Return true if PoisonOp's user yields poison or raises UB if its operand PoisonOp is poison.
@ UMin
Unsigned integer min implemented in terms of select(cmp()).
@ Mul
Product of integers.
@ SMax
Signed integer max implemented in terms of select(cmp()).
@ SMin
Signed integer min implemented in terms of select(cmp()).
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
DWARFExpression::Operation Op
auto max_element(R &&Range)
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
constexpr unsigned BitWidth
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
auto predecessors(const MachineBasicBlock *BB)
bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates or reallocates memory (eith...
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return the number of times the sign bit of the register is replicated into the other bits.
iterator_range< df_iterator< T > > depth_first(const T &G)
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be poison, but may be undef.
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
Implement std::hash so that hash_code can be used in STL containers.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
This struct is a compact representation of a valid (non-zero power of two) alignment.
A special type used by analysis passes to provide an address that identifies that particular analysis...
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
bool isNonNegative() const
Returns true if this value is known to be non-negative.
static KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for ashr(LHS, RHS).
unsigned getBitWidth() const
Get the bit width of this value.
static KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for lshr(LHS, RHS).
KnownBits zextOrTrunc(unsigned BitWidth) const
Return known bits for a zero extension or truncation of the value we're tracking.
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
APInt getMinValue() const
Return the minimal unsigned value possible given these KnownBits.
bool isNegative() const
Returns true if this value is known to be negative.
static KnownBits shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW=false, bool NSW=false, bool ShAmtNonZero=false)
Compute known bits for shl(LHS, RHS).
Various options to control the behavior of getObjectSize.
bool NullIsUnknownSize
If this is true, null pointers in address space 0 will be treated as though they can't be evaluated.
bool RoundToAlign
Whether to round the result up to the alignment of allocas, byval arguments, and global variables.
An object of this class is returned by queries that could not be answered.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This class defines a simple visitor class that may be used for various SCEV analysis purposes.
A utility class that uses RAII to save and restore the value of a variable.
Information about the number of loop iterations for which a loop exit's branch condition evaluates to...
ExitLimit(const SCEV *E)
Construct either an exact exit limit from a constant, or an unknown one from a SCEVCouldNotCompute.
const SCEV * ExactNotTaken
const SCEV * SymbolicMaxNotTaken
void addPredicate(const SCEVPredicate *P)
const SCEV * ConstantMaxNotTaken