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) {
933 OddFactorial *= (i >> TwoFactors);
937 unsigned CalculationBits = W +
T;
951 for (
unsigned i = 1; i != K; ++i) {
984 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
989 if (isa<SCEVCouldNotCompute>(Coeff))
1004 "getLosslessPtrToIntExpr() should self-recurse at most once.");
1008 if (!
Op->getType()->isPointerTy())
1019 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1038 if (
auto *U = dyn_cast<SCEVUnknown>(
Op)) {
1043 if (isa<ConstantPointerNull>(U->getValue()))
1049 SCEV *S =
new (SCEVAllocator)
1051 UniqueSCEVs.InsertNode(S, IP);
1056 assert(
Depth == 0 &&
"getLosslessPtrToIntExpr() should not self-recurse for "
1057 "non-SCEVUnknown's.");
1069 class SCEVPtrToIntSinkingRewriter
1077 SCEVPtrToIntSinkingRewriter
Rewriter(SE);
1087 return Base::visit(S);
1092 bool Changed =
false;
1102 bool Changed =
false;
1112 "Should only reach pointer-typed SCEVUnknown's.");
1118 const SCEV *IntOp = SCEVPtrToIntSinkingRewriter::rewrite(
Op, *
this);
1120 "We must have succeeded in sinking the cast, "
1121 "and ending up with an integer-typed expression!");
1129 if (isa<SCEVCouldNotCompute>(IntOp))
1138 "This is not a truncating conversion!");
1140 "This is not a conversion to a SCEVable type!");
1141 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1149 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1171 UniqueSCEVs.InsertNode(S, IP);
1180 if (isa<SCEVAddExpr>(
Op) || isa<SCEVMulExpr>(
Op)) {
1181 auto *CommOp = cast<SCEVCommutativeExpr>(
Op);
1183 unsigned numTruncs = 0;
1184 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1187 if (!isa<SCEVIntegralCastExpr>(CommOp->getOperand(i)) &&
1188 isa<SCEVTruncateExpr>(S))
1192 if (numTruncs < 2) {
1193 if (isa<SCEVAddExpr>(
Op))
1195 if (isa<SCEVMulExpr>(
Op))
1202 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1209 for (
const SCEV *
Op : AddRec->operands())
1224 UniqueSCEVs.InsertNode(S, IP);
1264struct ExtendOpTraitsBase {
1270template <
typename ExtendOp>
struct ExtendOpTraits {
1286 static const GetExtendExprTy GetExtendExpr;
1288 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1295const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1302 static const GetExtendExprTy GetExtendExpr;
1304 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1311const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1323template <
typename ExtendOpTy>
1326 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1327 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1334 const SCEVAddExpr *SA = dyn_cast<SCEVAddExpr>(Start);
1343 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1356 auto PreStartFlags =
1374 const SCEV *OperandExtendedStart =
1376 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1377 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1389 const SCEV *OverflowLimit =
1390 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1392 if (OverflowLimit &&
1400template <
typename ExtendOpTy>
1404 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1406 const SCEV *PreStart = getPreStartForExtend<ExtendOpTy>(AR, Ty, SE,
Depth);
1412 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1447template <
typename ExtendOpTy>
1448bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1451 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1457 const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start);
1463 for (
unsigned Delta : {-2, -1, 1, 2}) {
1468 ID.AddPointer(PreStart);
1469 ID.AddPointer(Step);
1477 if (PreAR && PreAR->getNoWrapFlags(WrapType)) {
1480 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1481 DeltaS, &Pred,
this);
1499 const unsigned BitWidth =
C.getBitWidth();
1517 const APInt &ConstantStart,
1536 auto &UserIDs = FoldCacheUser[
I.first->second];
1537 assert(
count(UserIDs,
ID) == 1 &&
"unexpected duplicates in UserIDs");
1538 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1539 if (UserIDs[
I] ==
ID) {
1544 I.first->second = S;
1546 auto R = FoldCacheUser.insert({S, {}});
1547 R.first->second.push_back(
ID);
1553 "This is not an extending conversion!");
1555 "This is not a conversion to a SCEVable type!");
1556 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1560 auto Iter = FoldCache.find(
ID);
1561 if (Iter != FoldCache.end())
1562 return Iter->second;
1565 if (!isa<SCEVZeroExtendExpr>(S))
1573 "This is not an extending conversion!");
1575 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1592 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1596 UniqueSCEVs.InsertNode(S, IP);
1605 const SCEV *
X = ST->getOperand();
1619 if (AR->isAffine()) {
1620 const SCEV *Start = AR->getStart();
1621 const SCEV *Step = AR->getStepRecurrence(*
this);
1623 const Loop *L = AR->getLoop();
1627 if (AR->hasNoUnsignedWrap()) {
1629 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
Depth + 1);
1643 if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
1648 const SCEV *CastedMaxBECount =
1652 if (MaxBECount == RecastedMaxBECount) {
1662 const SCEV *WideMaxBECount =
1664 const SCEV *OperandExtendedAdd =
1670 if (ZAdd == OperandExtendedAdd) {
1674 Start = getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
1681 OperandExtendedAdd =
1687 if (ZAdd == OperandExtendedAdd) {
1692 Start = getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
1707 if (!isa<SCEVCouldNotCompute>(MaxBECount) || HasGuards ||
1710 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1712 if (AR->hasNoUnsignedWrap()) {
1718 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
Depth + 1);
1735 Start = getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
1746 if (
const auto *SC = dyn_cast<SCEVConstant>(Start)) {
1747 const APInt &
C = SC->getAPInt();
1751 const SCEV *SResidual =
1760 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1763 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
Depth + 1);
1779 if (
auto *Div = dyn_cast<SCEVUDivExpr>(
Op))
1783 if (
auto *SA = dyn_cast<SCEVAddExpr>(
Op)) {
1785 if (SA->hasNoUnsignedWrap()) {
1789 for (
const auto *
Op : SA->operands())
1802 if (
const auto *SC = dyn_cast<SCEVConstant>(SA->getOperand(0))) {
1806 const SCEV *SResidual =
1816 if (
auto *SM = dyn_cast<SCEVMulExpr>(
Op)) {
1818 if (SM->hasNoUnsignedWrap()) {
1822 for (
const auto *
Op : SM->operands())
1839 if (SM->getNumOperands() == 2)
1840 if (
auto *MulLHS = dyn_cast<SCEVConstant>(SM->getOperand(0)))
1841 if (MulLHS->getAPInt().isPowerOf2())
1842 if (
auto *TruncRHS = dyn_cast<SCEVTruncateExpr>(SM->getOperand(1))) {
1844 MulLHS->getAPInt().logBase2();
1856 if (isa<SCEVUMinExpr>(
Op) || isa<SCEVUMaxExpr>(
Op)) {
1857 auto *
MinMax = cast<SCEVMinMaxExpr>(
Op);
1859 for (
auto *Operand :
MinMax->operands())
1861 if (isa<SCEVUMinExpr>(
MinMax))
1867 if (
auto *
MinMax = dyn_cast<SCEVSequentialMinMaxExpr>(
Op)) {
1868 assert(isa<SCEVSequentialUMinExpr>(
MinMax) &&
"Not supported!");
1870 for (
auto *Operand :
MinMax->operands())
1877 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1880 UniqueSCEVs.InsertNode(S, IP);
1888 "This is not an extending conversion!");
1890 "This is not a conversion to a SCEVable type!");
1891 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1895 auto Iter = FoldCache.find(
ID);
1896 if (Iter != FoldCache.end())
1897 return Iter->second;
1900 if (!isa<SCEVSignExtendExpr>(S))
1908 "This is not an extending conversion!");
1910 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1932 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1937 UniqueSCEVs.InsertNode(S, IP);
1946 const SCEV *
X = ST->getOperand();
1955 if (
auto *SA = dyn_cast<SCEVAddExpr>(
Op)) {
1957 if (SA->hasNoSignedWrap()) {
1961 for (
const auto *
Op : SA->operands())
1975 if (
const auto *SC = dyn_cast<SCEVConstant>(SA->getOperand(0))) {
1979 const SCEV *SResidual =
1993 if (AR->isAffine()) {
1994 const SCEV *Start = AR->getStart();
1995 const SCEV *Step = AR->getStepRecurrence(*
this);
1997 const Loop *L = AR->getLoop();
2001 if (AR->hasNoSignedWrap()) {
2003 getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty,
this,
Depth + 1);
2017 if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
2023 const SCEV *CastedMaxBECount =
2027 if (MaxBECount == RecastedMaxBECount) {
2037 const SCEV *WideMaxBECount =
2039 const SCEV *OperandExtendedAdd =
2045 if (SAdd == OperandExtendedAdd) {
2049 Start = getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty,
this,
2056 OperandExtendedAdd =
2062 if (SAdd == OperandExtendedAdd) {
2074 Start = getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty,
this,
2082 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2084 if (AR->hasNoSignedWrap()) {
2090 getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty,
this,
Depth + 1);
2098 if (
const auto *SC = dyn_cast<SCEVConstant>(Start)) {
2099 const APInt &
C = SC->getAPInt();
2103 const SCEV *SResidual =
2112 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2115 getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty,
this,
Depth + 1);
2128 if (isa<SCEVSMinExpr>(
Op) || isa<SCEVSMaxExpr>(
Op)) {
2129 auto *
MinMax = cast<SCEVMinMaxExpr>(
Op);
2131 for (
auto *Operand :
MinMax->operands())
2133 if (isa<SCEVSMinExpr>(
MinMax))
2140 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
2143 UniqueSCEVs.InsertNode(S, IP);
2169 "This is not an extending conversion!");
2171 "This is not a conversion to a SCEVable type!");
2176 if (SC->getAPInt().isNegative())
2181 const SCEV *NewOp =
T->getOperand();
2189 if (!isa<SCEVZeroExtendExpr>(ZExt))
2194 if (!isa<SCEVSignExtendExpr>(SExt))
2200 for (
const SCEV *
Op : AR->operands())
2206 if (isa<SCEVSMaxExpr>(
Op))
2239 APInt &AccumulatedConstant,
2242 bool Interesting =
false;
2246 while (
const SCEVConstant *
C = dyn_cast<SCEVConstant>(Ops[i])) {
2249 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2251 AccumulatedConstant += Scale *
C->getAPInt();
2256 for (; i != Ops.
size(); ++i) {
2258 if (
Mul && isa<SCEVConstant>(
Mul->getOperand(0))) {
2260 Scale * cast<SCEVConstant>(
Mul->getOperand(0))->getAPInt();
2261 if (
Mul->getNumOperands() == 2 && isa<SCEVAddExpr>(
Mul->getOperand(1))) {
2266 Add->operands(), NewScale, SE);
2272 auto Pair = M.insert({Key, NewScale});
2276 Pair.first->second += NewScale;
2284 std::pair<DenseMap<const SCEV *, APInt>::iterator,
bool> Pair =
2285 M.insert({Ops[i], Scale});
2289 Pair.first->second += Scale;
2308 case Instruction::Add:
2311 case Instruction::Sub:
2314 case Instruction::Mul:
2324 auto *NarrowTy = cast<IntegerType>(
LHS->
getType());
2328 const SCEV *
A = (this->*Extension)(
2330 const SCEV *LHSB = (this->*Extension)(
LHS, WideTy, 0);
2331 const SCEV *RHSB = (this->*Extension)(
RHS, WideTy, 0);
2339 if (BinOp == Instruction::Mul)
2341 auto *RHSC = dyn_cast<SCEVConstant>(
RHS);
2345 APInt C = RHSC->getAPInt();
2346 unsigned NumBits =
C.getBitWidth();
2347 bool IsSub = (BinOp == Instruction::Sub);
2348 bool IsNegativeConst = (
Signed &&
C.isNegative());
2350 bool OverflowDown = IsSub ^ IsNegativeConst;
2352 if (IsNegativeConst) {
2365 APInt Limit = Min + Magnitude;
2371 APInt Limit = Max - Magnitude;
2376std::optional<SCEV::NoWrapFlags>
2381 return std::nullopt;
2390 bool Deduced =
false;
2392 if (OBO->
getOpcode() != Instruction::Add &&
2395 return std::nullopt;
2404 false,
LHS,
RHS, CtxI)) {
2418 return std::nullopt;
2428 using namespace std::placeholders;
2435 assert(CanAnalyze &&
"don't call from other places!");
2442 auto IsKnownNonNegative = [&](
const SCEV *S) {
2452 if (SignOrUnsignWrap != SignOrUnsignMask &&
2454 isa<SCEVConstant>(Ops[0])) {
2459 return Instruction::Add;
2461 return Instruction::Mul;
2467 const APInt &
C = cast<SCEVConstant>(Ops[0])->getAPInt();
2472 Opcode,
C, OBO::NoSignedWrap);
2480 Opcode,
C, OBO::NoUnsignedWrap);
2490 Ops[0]->isZero() && IsKnownNonNegative(Ops[1]))
2496 if (
auto *UDiv = dyn_cast<SCEVUDivExpr>(Ops[0]))
2497 if (UDiv->getOperand(1) == Ops[1])
2499 if (
auto *UDiv = dyn_cast<SCEVUDivExpr>(Ops[1]))
2500 if (UDiv->getOperand(1) == Ops[0])
2516 "only nuw or nsw allowed");
2518 if (Ops.
size() == 1)
return Ops[0];
2521 for (
unsigned i = 1, e = Ops.
size(); i != e; ++i)
2523 "SCEVAddExpr operand types don't match!");
2526 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2534 if (
const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
2539 Ops[0] =
getConstant(LHSC->getAPInt() + RHSC->getAPInt());
2540 if (Ops.
size() == 2)
return Ops[0];
2542 LHSC = cast<SCEVConstant>(Ops[0]);
2546 if (LHSC->getValue()->isZero()) {
2551 if (Ops.
size() == 1)
return Ops[0];
2561 return getOrCreateAddExpr(Ops, ComputeFlags(Ops));
2566 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2567 Add->setNoWrapFlags(ComputeFlags(Ops));
2574 Type *Ty = Ops[0]->getType();
2575 bool FoundMatch =
false;
2576 for (
unsigned i = 0, e = Ops.
size(); i != e-1; ++i)
2577 if (Ops[i] == Ops[i+1]) {
2580 while (i+Count != e && Ops[i+Count] == Ops[i])
2585 if (Ops.
size() == Count)
2589 --i; e -= Count - 1;
2599 auto FindTruncSrcType = [&]() ->
Type * {
2604 if (
auto *
T = dyn_cast<SCEVTruncateExpr>(Ops[
Idx]))
2605 return T->getOperand()->getType();
2606 if (
const auto *
Mul = dyn_cast<SCEVMulExpr>(Ops[
Idx])) {
2607 const auto *LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2608 if (
const auto *
T = dyn_cast<SCEVTruncateExpr>(LastOp))
2609 return T->getOperand()->getType();
2613 if (
auto *SrcType = FindTruncSrcType()) {
2618 for (
const SCEV *
Op : Ops) {
2620 if (
T->getOperand()->getType() != SrcType) {
2627 }
else if (
const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(
Op)) {
2629 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2631 dyn_cast<SCEVTruncateExpr>(M->getOperand(j))) {
2632 if (
T->getOperand()->getType() != SrcType) {
2637 }
else if (
const auto *
C = dyn_cast<SCEVConstant>(M->getOperand(j))) {
2655 if (isa<SCEVConstant>(Fold) || isa<SCEVUnknown>(Fold))
2660 if (Ops.
size() == 2) {
2664 const SCEV *
A = Ops[0];
2665 const SCEV *
B = Ops[1];
2666 auto *AddExpr = dyn_cast<SCEVAddExpr>(
B);
2667 auto *
C = dyn_cast<SCEVConstant>(
A);
2668 if (AddExpr &&
C && isa<SCEVConstant>(AddExpr->getOperand(0))) {
2669 auto C1 = cast<SCEVConstant>(AddExpr->getOperand(0))->getAPInt();
2670 auto C2 =
C->getAPInt();
2673 APInt ConstAdd = C1 + C2;
2674 auto AddFlags = AddExpr->getNoWrapFlags();
2686 ConstAdd.
abs().
ule(C1.abs())) {
2700 if (Ops.
size() == 2) {
2702 if (
Mul &&
Mul->getNumOperands() == 2 &&
2703 Mul->getOperand(0)->isAllOnesValue()) {
2706 if (matchURem(
Mul->getOperand(1),
X,
Y) &&
X == Ops[1]) {
2718 bool DeletedAdd =
false;
2732 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2748 if (
Idx < Ops.
size() && isa<SCEVMulExpr>(Ops[
Idx])) {
2755 struct APIntCompare {
2764 std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists;
2765 for (
const SCEV *NewOp : NewOps)
2766 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2769 if (AccumulatedConstant != 0)
2771 for (
auto &MulOp : MulOpLists) {
2772 if (MulOp.first == 1) {
2774 }
else if (MulOp.first != 0) {
2783 if (Ops.
size() == 1)
2792 for (;
Idx < Ops.
size() && isa<SCEVMulExpr>(Ops[
Idx]); ++
Idx) {
2794 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2795 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2796 if (isa<SCEVConstant>(MulOpSCEV))
2798 for (
unsigned AddOp = 0, e = Ops.
size(); AddOp != e; ++AddOp)
2799 if (MulOpSCEV == Ops[AddOp]) {
2801 const SCEV *InnerMul =
Mul->getOperand(MulOp == 0);
2802 if (
Mul->getNumOperands() != 2) {
2806 Mul->operands().take_front(MulOp));
2814 if (Ops.
size() == 2)
return OuterMul;
2827 for (
unsigned OtherMulIdx =
Idx+1;
2828 OtherMulIdx < Ops.
size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]);
2830 const SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]);
2834 OMulOp != e; ++OMulOp)
2835 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2837 const SCEV *InnerMul1 =
Mul->getOperand(MulOp == 0);
2838 if (
Mul->getNumOperands() != 2) {
2840 Mul->operands().take_front(MulOp));
2847 OtherMul->
operands().take_front(OMulOp));
2852 const SCEV *InnerMulSum =
2856 if (Ops.
size() == 2)
return OuterMul;
2873 for (;
Idx < Ops.
size() && isa<SCEVAddRecExpr>(Ops[
Idx]); ++
Idx) {
2879 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i)
2887 if (!LIOps.
empty()) {
2912 auto *DefI = getDefiningScopeBound(LIOps);
2914 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2926 if (Ops.
size() == 1)
return NewRec;
2929 for (
unsigned i = 0;; ++i)
2930 if (Ops[i] == AddRec) {
2940 for (
unsigned OtherIdx =
Idx+1;
2941 OtherIdx < Ops.
size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
2946 cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop()->getHeader(),
2948 "AddRecExprs are not sorted in reverse dominance order?");
2949 if (AddRecLoop == cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop()) {
2952 for (; OtherIdx != Ops.
size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
2954 const auto *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
2955 if (OtherAddRec->getLoop() == AddRecLoop) {
2956 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2958 if (i >= AddRecOps.
size()) {
2959 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2963 AddRecOps[i], OtherAddRec->getOperand(i)};
2966 Ops.
erase(Ops.
begin() + OtherIdx); --OtherIdx;
2981 return getOrCreateAddExpr(Ops, ComputeFlags(Ops));
2989 for (
const SCEV *
Op : Ops)
2993 static_cast<SCEVAddExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
2996 std::uninitialized_copy(Ops.begin(), Ops.end(), O);
2997 S =
new (SCEVAllocator)
2999 UniqueSCEVs.InsertNode(S, IP);
3011 for (
const SCEV *
Op : Ops)
3019 std::uninitialized_copy(Ops.begin(), Ops.end(), O);
3020 S =
new (SCEVAllocator)
3022 UniqueSCEVs.InsertNode(S, IP);
3023 LoopUsers[
L].push_back(S);
3035 for (
const SCEV *
Op : Ops)
3039 static_cast<SCEVMulExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3042 std::uninitialized_copy(Ops.begin(), Ops.end(), O);
3043 S =
new (SCEVAllocator)
SCEVMulExpr(
ID.Intern(SCEVAllocator),
3045 UniqueSCEVs.InsertNode(S, IP);
3054 if (j > 1 && k / j != i) Overflow =
true;
3070 if (n == 0 || n == k)
return 1;
3071 if (k > n)
return 0;
3077 for (
uint64_t i = 1; i <= k; ++i) {
3078 r =
umul_ov(r, n-(i-1), Overflow);
3087 struct FindConstantInAddMulChain {
3088 bool FoundConstant =
false;
3090 bool follow(
const SCEV *S) {
3091 FoundConstant |= isa<SCEVConstant>(S);
3092 return isa<SCEVAddExpr>(S) || isa<SCEVMulExpr>(S);
3095 bool isDone()
const {
3096 return FoundConstant;
3100 FindConstantInAddMulChain
F;
3102 ST.visitAll(StartExpr);
3103 return F.FoundConstant;
3111 "only nuw or nsw allowed");
3113 if (Ops.
size() == 1)
return Ops[0];
3115 Type *ETy = Ops[0]->getType();
3117 for (
unsigned i = 1, e = Ops.
size(); i != e; ++i)
3119 "SCEVMulExpr operand types don't match!");
3127 if (
const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
3132 Ops[0] =
getConstant(LHSC->getAPInt() * RHSC->getAPInt());
3133 if (Ops.
size() == 2)
return Ops[0];
3135 LHSC = cast<SCEVConstant>(Ops[0]);
3139 if (LHSC->getValue()->isZero())
3143 if (LHSC->getValue()->isOne()) {
3148 if (Ops.
size() == 1)
3159 return getOrCreateMulExpr(Ops, ComputeFlags(Ops));
3164 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3165 Mul->setNoWrapFlags(ComputeFlags(Ops));
3169 if (
const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
3170 if (Ops.
size() == 2) {
3187 if (Ops[0]->isAllOnesValue()) {
3192 bool AnyFolded =
false;
3193 for (
const SCEV *AddOp :
Add->operands()) {
3196 if (!isa<SCEVMulExpr>(
Mul)) AnyFolded =
true;
3201 }
else if (
const auto *AddRec = dyn_cast<SCEVAddRecExpr>(Ops[1])) {
3220 AddRec->getNoWrapFlags(FlagsMask));
3232 bool DeletedMul =
false;
3257 for (;
Idx < Ops.
size() && isa<SCEVAddRecExpr>(Ops[
Idx]); ++
Idx) {
3262 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i)
3270 if (!LIOps.
empty()) {
3283 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3299 if (Ops.
size() == 1)
return NewRec;
3302 for (
unsigned i = 0;; ++i)
3303 if (Ops[i] == AddRec) {
3324 bool OpsModified =
false;
3325 for (
unsigned OtherIdx =
Idx+1;
3326 OtherIdx != Ops.
size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
3329 dyn_cast<SCEVAddRecExpr>(Ops[OtherIdx]);
3339 bool Overflow =
false;
3345 SmallVector <const SCEV *, 7> SumOps;
3346 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3350 z < ze && !Overflow; ++z) {
3353 if (LargerThan64Bits)
3354 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3356 Coeff = Coeff1*Coeff2;
3371 if (Ops.
size() == 2)
return NewAddRec;
3372 Ops[
Idx] = NewAddRec;
3373 Ops.
erase(Ops.
begin() + OtherIdx); --OtherIdx;
3375 AddRec = dyn_cast<SCEVAddRecExpr>(NewAddRec);
3389 return getOrCreateMulExpr(Ops, ComputeFlags(Ops));
3397 "SCEVURemExpr operand types don't match!");
3402 if (RHSC->getValue()->isOne())
3406 if (RHSC->getAPInt().isPowerOf2()) {
3425 "SCEVUDivExpr operand can't be pointer!");
3427 "SCEVUDivExpr operand types don't match!");
3434 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3439 if (LHSC->getValue()->isZero())
3443 if (RHSC->getValue()->isOne())
3448 if (!RHSC->getValue()->isZero()) {
3453 unsigned LZ = RHSC->getAPInt().countl_zero();
3457 if (!RHSC->getAPInt().isPowerOf2())
3463 dyn_cast<SCEVConstant>(AR->getStepRecurrence(*
this))) {
3465 const APInt &StepInt = Step->getAPInt();
3466 const APInt &DivInt = RHSC->getAPInt();
3467 if (!StepInt.
urem(DivInt) &&
3473 for (
const SCEV *
Op : AR->operands())
3480 const SCEVConstant *StartC = dyn_cast<SCEVConstant>(AR->getStart());
3481 if (StartC && !DivInt.
urem(StepInt) &&
3487 const APInt &StartRem = StartInt.
urem(StepInt);
3488 if (StartRem != 0) {
3489 const SCEV *NewLHS =
3492 if (
LHS != NewLHS) {
3502 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3511 for (
const SCEV *
Op : M->operands())
3515 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3516 const SCEV *
Op = M->getOperand(i);
3518 if (!isa<SCEVUDivExpr>(Div) &&
getMulExpr(Div, RHSC) ==
Op) {
3528 if (
auto *DivisorConstant =
3529 dyn_cast<SCEVConstant>(OtherDiv->getRHS())) {
3530 bool Overflow =
false;
3532 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3543 for (
const SCEV *
Op :
A->operands())
3547 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3549 if (isa<SCEVUDivExpr>(
Op) ||
3554 if (
Operands.size() ==
A->getNumOperands())
3561 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3568 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
3571 UniqueSCEVs.InsertNode(S, IP);
3601 if (!
Mul || !
Mul->hasNoUnsignedWrap())
3607 if (
const auto *LHSCst = dyn_cast<SCEVConstant>(
Mul->getOperand(0))) {
3608 if (LHSCst == RHSCst) {
3616 APInt Factor =
gcd(LHSCst, RHSCst);
3619 cast<SCEVConstant>(
getConstant(LHSCst->getAPInt().udiv(Factor)));
3621 cast<SCEVConstant>(
getConstant(RHSCst->getAPInt().udiv(Factor)));
3627 Mul = dyn_cast<SCEVMulExpr>(
LHS);
3634 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3635 if (
Mul->getOperand(i) ==
RHS) {
3653 if (
const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
3654 if (StepChrec->getLoop() == L) {
3673 "SCEVAddRecExpr operand types don't match!");
3674 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3678 "SCEVAddRecExpr operand is not available at loop entry!");
3696 const Loop *NestedLoop = NestedAR->getLoop();
3697 if (L->contains(NestedLoop)
3702 Operands[0] = NestedAR->getStart();
3706 bool AllInvariant =
all_of(
3718 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3729 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3739 return getOrCreateAddRecExpr(
Operands, L, Flags);
3756 auto *GEPI = dyn_cast<Instruction>(
GEP);
3757 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3768 bool FirstIter =
true;
3770 for (
const SCEV *IndexExpr : IndexExprs) {
3772 if (
StructType *STy = dyn_cast<StructType>(CurTy)) {
3777 Offsets.push_back(FieldOffset);
3780 CurTy = STy->getTypeAtIndex(
Index);
3784 assert(isa<PointerType>(CurTy) &&
3785 "The first index of a GEP indexes a pointer");
3786 CurTy =
GEP->getSourceElementType();
3797 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3798 Offsets.push_back(LocalOffset);
3803 if (Offsets.empty())
3816 "GEP should not change type mid-flight.");
3820SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3823 ID.AddInteger(SCEVType);
3824 for (
const SCEV *
Op : Ops)
3827 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3837 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3838 assert(!Ops.
empty() &&
"Cannot get empty (u|s)(min|max)!");
3839 if (Ops.
size() == 1)
return Ops[0];
3842 for (
unsigned i = 1, e = Ops.
size(); i != e; ++i) {
3844 "Operand types don't match!");
3847 "min/max should be consistently pointerish");
3858 if (
const SCEV *S = findExistingSCEVInCache(Kind, Ops)) {
3864 if (
const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
3885 getContext(), FoldOp(LHSC->getAPInt(), RHSC->getAPInt()));
3888 if (Ops.
size() == 1)
return Ops[0];
3889 LHSC = cast<SCEVConstant>(Ops[0]);
3892 bool IsMinV = LHSC->getValue()->isMinValue(IsSigned);
3893 bool IsMaxV = LHSC->getValue()->isMaxValue(IsSigned);
3895 if (IsMax ? IsMinV : IsMaxV) {
3899 }
else if (IsMax ? IsMaxV : IsMinV) {
3905 if (Ops.
size() == 1)
return Ops[0];
3909 while (
Idx < Ops.
size() && Ops[
Idx]->getSCEVType() < Kind)
3915 bool DeletedAny =
false;
3916 while (Ops[
Idx]->getSCEVType() == Kind) {
3936 for (
unsigned i = 0, e = Ops.
size() - 1; i != e; ++i) {
3937 if (Ops[i] == Ops[i + 1] ||
3938 isKnownViaNonRecursiveReasoning(FirstPred, Ops[i], Ops[i + 1])) {
3944 }
else if (isKnownViaNonRecursiveReasoning(SecondPred, Ops[i],
3953 if (Ops.
size() == 1)
return Ops[0];
3955 assert(!Ops.
empty() &&
"Reduced smax down to nothing!");
3960 ID.AddInteger(Kind);
3961 for (
const SCEV *
Op : Ops)
3964 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3966 return ExistingSCEV;
3968 std::uninitialized_copy(Ops.
begin(), Ops.
end(), O);
3969 SCEV *S =
new (SCEVAllocator)
3972 UniqueSCEVs.InsertNode(S, IP);
3979class SCEVSequentialMinMaxDeduplicatingVisitor final
3980 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
3981 std::optional<const SCEV *>> {
3982 using RetVal = std::optional<const SCEV *>;
3990 bool canRecurseInto(
SCEVTypes Kind)
const {
3993 return RootKind == Kind || NonSequentialRootKind == Kind;
3996 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
3997 assert((isa<SCEVMinMaxExpr>(S) || isa<SCEVSequentialMinMaxExpr>(S)) &&
3998 "Only for min/max expressions.");
4001 if (!canRecurseInto(Kind))
4004 auto *NAry = cast<SCEVNAryExpr>(S);
4006 bool Changed = visit(Kind, NAry->operands(), NewOps);
4011 return std::nullopt;
4013 return isa<SCEVSequentialMinMaxExpr>(S)
4018 RetVal visit(
const SCEV *S) {
4020 if (!SeenOps.
insert(S).second)
4021 return std::nullopt;
4022 return Base::visit(S);
4028 : SE(SE), RootKind(RootKind),
4029 NonSequentialRootKind(
4035 bool Changed =
false;
4039 for (
const SCEV *
Op : OrigOps) {
4040 RetVal NewOp = visit(
Op);
4048 NewOps = std::move(Ops);
4054 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4064 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4066 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4068 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4070 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4073 return visitAnyMinMaxExpr(Expr);
4077 return visitAnyMinMaxExpr(Expr);
4081 return visitAnyMinMaxExpr(Expr);
4085 return visitAnyMinMaxExpr(Expr);
4089 return visitAnyMinMaxExpr(Expr);
4092 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4136struct SCEVPoisonCollector {
4137 bool LookThroughMaybePoisonBlocking;
4139 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4140 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4142 bool follow(
const SCEV *S) {
4143 if (!LookThroughMaybePoisonBlocking &&
4147 if (
auto *SU = dyn_cast<SCEVUnknown>(S)) {
4153 bool isDone()
const {
return false; }
4163 SCEVPoisonCollector PC1(
true);
4168 if (PC1.MaybePoison.empty())
4174 SCEVPoisonCollector PC2(
false);
4180 return PC2.MaybePoison.contains(S);
4186 SCEVPoisonCollector PC(
false);
4209 while (!Worklist.
empty()) {
4211 if (!Visited.
insert(V).second)
4215 if (Visited.
size() > 16)
4223 auto *
I = dyn_cast<Instruction>(V);
4230 if (
auto *PDI = dyn_cast<PossiblyDisjointInst>(
I))
4231 if (PDI->isDisjoint())
4237 if (
auto *
II = dyn_cast<IntrinsicInst>(
I);
4238 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4245 if (
I->hasPoisonGeneratingAnnotations())
4257 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4258 "Not a SCEVSequentialMinMaxExpr!");
4259 assert(!Ops.
empty() &&
"Cannot get empty (u|s)(min|max)!");
4260 if (Ops.
size() == 1)
4264 for (
unsigned i = 1, e = Ops.
size(); i != e; ++i) {
4266 "Operand types don't match!");
4269 "min/max should be consistently pointerish");
4277 if (
const SCEV *S = findExistingSCEVInCache(Kind, Ops))
4284 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4285 bool Changed = Deduplicator.visit(Kind, Ops, Ops);
4294 bool DeletedAny =
false;
4296 if (Ops[
Idx]->getSCEVType() != Kind) {
4300 const auto *SMME = cast<SCEVSequentialMinMaxExpr>(Ops[
Idx]);
4303 SMME->operands().end());
4311 const SCEV *SaturationPoint;
4322 for (
unsigned i = 1, e = Ops.
size(); i != e; ++i) {
4338 if (isKnownViaNonRecursiveReasoning(Pred, Ops[i - 1], Ops[i])) {
4347 ID.AddInteger(Kind);
4348 for (
const SCEV *
Op : Ops)
4351 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4353 return ExistingSCEV;
4356 std::uninitialized_copy(Ops.
begin(), Ops.
end(), O);
4357 SCEV *S =
new (SCEVAllocator)
4360 UniqueSCEVs.InsertNode(S, IP);
4408 if (
Size.isScalable())
4429 "Cannot get offset for structure containing scalable vector types");
4443 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP)) {
4444 assert(cast<SCEVUnknown>(S)->getValue() == V &&
4445 "Stale SCEVUnknown in uniquing map!");
4450 FirstUnknown = cast<SCEVUnknown>(S);
4451 UniqueSCEVs.InsertNode(S, IP);
4499 bool PreciseA, PreciseB;
4500 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4501 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4502 if (!PreciseA || !PreciseB)
4505 return (ScopeA == ScopeB) || DT.
dominates(ScopeA, ScopeB) ||
4510 return CouldNotCompute.get();
4513bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4515 auto *SU = dyn_cast<SCEVUnknown>(S);
4516 return SU && SU->getValue() ==
nullptr;
4519 return !ContainsNulls;
4524 if (
I != HasRecMap.
end())
4529 HasRecMap.
insert({S, FoundAddRec});
4537 if (SI == ExprValueMap.
end())
4538 return std::nullopt;
4539 return SI->second.getArrayRef();
4545void ScalarEvolution::eraseValueFromMap(
Value *V) {
4547 if (
I != ValueExprMap.
end()) {
4548 auto EVIt = ExprValueMap.
find(
I->second);
4549 bool Removed = EVIt->second.remove(V);
4551 assert(Removed &&
"Value not in ExprValueMap?");
4556void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4560 auto It = ValueExprMap.
find_as(V);
4561 if (It == ValueExprMap.
end()) {
4563 ExprValueMap[S].
insert(V);
4574 return createSCEVIter(V);
4581 if (
I != ValueExprMap.
end()) {
4582 const SCEV *S =
I->second;
4583 assert(checkValidity(S) &&
4584 "existing SCEV has not been properly invalidated");
4593 if (
const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
4597 Type *Ty = V->getType();
4605 if (!
Add ||
Add->getNumOperands() != 2 ||
4606 !
Add->getOperand(0)->isAllOnesValue())
4609 const SCEVMulExpr *AddRHS = dyn_cast<SCEVMulExpr>(
Add->getOperand(1));
4619 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4621 if (
const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
4632 return (
const SCEV *)
nullptr;
4638 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4642 Type *Ty = V->getType();
4648 assert(
P->getType()->isPointerTy());
4650 if (
auto *AddRec = dyn_cast<SCEVAddRecExpr>(
P)) {
4658 if (
auto *
Add = dyn_cast<SCEVAddExpr>(
P)) {
4661 const SCEV **PtrOp =
nullptr;
4662 for (
const SCEV *&AddOp : Ops) {
4663 if (AddOp->getType()->isPointerTy()) {
4664 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4698 const bool RHSIsNotMinSigned =
4729 Type *SrcTy = V->getType();
4731 "Cannot truncate or zero extend with non-integer arguments!");
4741 Type *SrcTy = V->getType();
4743 "Cannot truncate or zero extend with non-integer arguments!");
4753 Type *SrcTy = V->getType();
4755 "Cannot noop or zero extend with non-integer arguments!");
4757 "getNoopOrZeroExtend cannot truncate!");
4765 Type *SrcTy = V->getType();
4767 "Cannot noop or sign extend with non-integer arguments!");
4769 "getNoopOrSignExtend cannot truncate!");
4777 Type *SrcTy = V->getType();
4779 "Cannot noop or any extend with non-integer arguments!");
4781 "getNoopOrAnyExtend cannot truncate!");
4789 Type *SrcTy = V->getType();
4791 "Cannot truncate or noop with non-integer arguments!");
4793 "getTruncateOrNoop cannot extend!");
4801 const SCEV *PromotedLHS =
LHS;
4802 const SCEV *PromotedRHS =
RHS;
4822 assert(!Ops.
empty() &&
"At least one operand must be!");
4824 if (Ops.
size() == 1)
4828 Type *MaxType =
nullptr;
4829 for (
const auto *S : Ops)
4834 assert(MaxType &&
"Failed to find maximum type!");
4838 for (
const auto *S : Ops)
4847 if (!V->getType()->isPointerTy())
4851 if (
auto *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
4852 V = AddRec->getStart();
4853 }
else if (
auto *
Add = dyn_cast<SCEVAddExpr>(V)) {
4854 const SCEV *PtrOp =
nullptr;
4855 for (
const SCEV *AddOp :
Add->operands()) {
4856 if (AddOp->getType()->isPointerTy()) {
4857 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4861 assert(PtrOp &&
"Must have pointer op");
4873 for (
User *U :
I->users()) {
4874 auto *UserInsn = cast<Instruction>(U);
4875 if (Visited.
insert(UserInsn).second)
4890 bool IgnoreOtherLoops =
true) {
4893 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4895 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4902 SeenLoopVariantSCEVUnknown =
true;
4910 SeenOtherLoops =
true;
4914 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4916 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4923 bool SeenLoopVariantSCEVUnknown =
false;
4924 bool SeenOtherLoops =
false;
4934 SCEVPostIncRewriter
Rewriter(L, SE);
4936 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4943 SeenLoopVariantSCEVUnknown =
true;
4951 SeenOtherLoops =
true;
4955 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4957 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4964 bool SeenLoopVariantSCEVUnknown =
false;
4965 bool SeenOtherLoops =
false;
4971class SCEVBackedgeConditionFolder
4976 bool IsPosBECond =
false;
4977 Value *BECond =
nullptr;
4979 BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
4982 "Both outgoing branches should not target same header!");
4989 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
4999 switch (
I->getOpcode()) {
5000 case Instruction::Select: {
5002 std::optional<const SCEV *> Res =
5003 compareWithBackedgeCondition(
SI->getCondition());
5005 bool IsOne = cast<SCEVConstant>(*Res)->getValue()->isOne();
5011 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5022 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5025 IsPositiveBECond(IsPosBECond) {}
5027 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5031 Value *BackedgeCond =
nullptr;
5033 bool IsPositiveBECond;
5036std::optional<const SCEV *>
5037SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5042 if (BackedgeCond == IC)
5045 return std::nullopt;
5071 bool isValid() {
return Valid; }
5084ScalarEvolution::proveNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5094 if (
const SCEVConstant *BECountMax = dyn_cast<SCEVConstant>(BECount)) {
5096 const APInt &BECountAP = BECountMax->getAPInt();
5097 unsigned NoOverflowBitWidth =
5109 Instruction::Add, IncRange, OBO::NoSignedWrap);
5110 if (NSWRegion.contains(AddRecRange))
5119 Instruction::Add, IncRange, OBO::NoUnsignedWrap);
5120 if (NUWRegion.contains(AddRecRange))
5128ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5138 if (!SignedWrapViaInductionTried.insert(AR).second)
5162 if (isa<SCEVCouldNotCompute>(MaxBECount) && !HasGuards &&
5171 const SCEV *OverflowLimit =
5173 if (OverflowLimit &&
5181ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5191 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5216 if (isa<SCEVCouldNotCompute>(MaxBECount) && !HasGuards &&
5255 if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(
Op)) {
5256 IsNSW = OBO->hasNoSignedWrap();
5257 IsNUW = OBO->hasNoUnsignedWrap();
5261 explicit BinaryOp(
unsigned Opcode,
Value *
LHS,
Value *
RHS,
bool IsNSW =
false,
5263 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5273 auto *
Op = dyn_cast<Operator>(V);
5275 return std::nullopt;
5281 switch (
Op->getOpcode()) {
5282 case Instruction::Add:
5283 case Instruction::Sub:
5284 case Instruction::Mul:
5285 case Instruction::UDiv:
5286 case Instruction::URem:
5287 case Instruction::And:
5288 case Instruction::AShr:
5289 case Instruction::Shl:
5290 return BinaryOp(
Op);
5292 case Instruction::Or: {
5294 if (cast<PossiblyDisjointInst>(
Op)->isDisjoint())
5295 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5297 return BinaryOp(
Op);
5300 case Instruction::Xor:
5301 if (
auto *RHSC = dyn_cast<ConstantInt>(
Op->getOperand(1)))
5304 if (RHSC->getValue().isSignMask())
5305 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5307 if (V->getType()->isIntegerTy(1))
5308 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5309 return BinaryOp(
Op);
5311 case Instruction::LShr:
5313 if (
ConstantInt *SA = dyn_cast<ConstantInt>(
Op->getOperand(1))) {
5320 if (SA->getValue().ult(
BitWidth)) {
5322 ConstantInt::get(SA->getContext(),
5324 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5327 return BinaryOp(
Op);
5329 case Instruction::ExtractValue: {
5330 auto *EVI = cast<ExtractValueInst>(
Op);
5331 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5334 auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand());
5339 bool Signed = WO->isSigned();
5342 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5347 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5357 if (
auto *
II = dyn_cast<IntrinsicInst>(V))
5358 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5359 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5361 return std::nullopt;
5387 if (
Op == SymbolicPHI)
5392 if (SourceBits != NewBits)
5400 SExt ? dyn_cast<SCEVTruncateExpr>(SExt->
getOperand())
5401 : dyn_cast<SCEVTruncateExpr>(ZExt->
getOperand());
5405 if (
X != SymbolicPHI)
5407 Signed = SExt !=
nullptr;
5415 if (!L || L->getHeader() != PN->
getParent())
5473std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5474ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5480 auto *PN = cast<PHINode>(SymbolicPHI->
getValue());
5482 assert(L &&
"Expecting an integer loop header phi");
5487 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5488 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5489 Value *
V = PN->getIncomingValue(i);
5490 if (
L->contains(PN->getIncomingBlock(i))) {
5493 }
else if (BEValueV != V) {
5497 }
else if (!StartValueV) {
5499 }
else if (StartValueV != V) {
5500 StartValueV =
nullptr;
5504 if (!BEValueV || !StartValueV)
5505 return std::nullopt;
5512 const auto *
Add = dyn_cast<SCEVAddExpr>(BEValue);
5514 return std::nullopt;
5518 unsigned FoundIndex =
Add->getNumOperands();
5519 Type *TruncTy =
nullptr;
5521 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5524 if (FoundIndex == e) {
5529 if (FoundIndex ==
Add->getNumOperands())
5530 return std::nullopt;
5534 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5535 if (i != FoundIndex)
5542 return std::nullopt;
5596 const SCEV *PHISCEV =
5606 if (
const auto *AR = dyn_cast<SCEVAddRecExpr>(PHISCEV)) {
5623 auto getExtendedExpr = [&](
const SCEV *Expr,
5624 bool CreateSignExtend) ->
const SCEV * {
5627 const SCEV *ExtendedExpr =
5630 return ExtendedExpr;
5638 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5639 const SCEV *ExtendedExpr) ->
bool {
5640 return Expr != ExtendedExpr &&
5644 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5645 if (PredIsKnownFalse(StartVal, StartExtended)) {
5647 return std::nullopt;
5652 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5653 if (PredIsKnownFalse(Accum, AccumExtended)) {
5655 return std::nullopt;
5658 auto AppendPredicate = [&](
const SCEV *Expr,
5659 const SCEV *ExtendedExpr) ->
void {
5660 if (Expr != ExtendedExpr &&
5668 AppendPredicate(StartVal, StartExtended);
5669 AppendPredicate(Accum, AccumExtended);
5677 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5678 std::make_pair(NewAR, Predicates);
5680 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5684std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5686 auto *PN = cast<PHINode>(SymbolicPHI->
getValue());
5689 return std::nullopt;
5692 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5693 if (
I != PredicatedSCEVRewrites.end()) {
5694 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5697 if (Rewrite.first == SymbolicPHI)
5698 return std::nullopt;
5701 assert(isa<SCEVAddRecExpr>(Rewrite.first) &&
"Expected an AddRec");
5702 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5706 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5707 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5712 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5713 return std::nullopt;
5730 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5749const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5751 Value *StartValueV) {
5754 assert(BEValueV && StartValueV);
5760 if (BO->Opcode != Instruction::Add)
5763 const SCEV *Accum =
nullptr;
5764 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5766 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5780 insertValueToMap(PN, PHISCEV);
5782 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(PHISCEV)) {
5785 proveNoWrapViaConstantRanges(AR)));
5791 if (
auto *BEInst = dyn_cast<Instruction>(BEValueV)) {
5793 "Accum is defined outside L, but is not invariant?");
5794 if (isAddRecNeverPoison(BEInst, L))
5801const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5809 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5815 }
else if (BEValueV != V) {
5819 }
else if (!StartValueV) {
5821 }
else if (StartValueV != V) {
5822 StartValueV =
nullptr;
5826 if (!BEValueV || !StartValueV)
5830 "PHI node already processed?");
5834 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5839 insertValueToMap(PN, SymbolicName);
5853 unsigned FoundIndex =
Add->getNumOperands();
5854 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5855 if (
Add->getOperand(i) == SymbolicName)
5856 if (FoundIndex == e) {
5861 if (FoundIndex !=
Add->getNumOperands()) {
5864 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5865 if (i != FoundIndex)
5866 Ops.
push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5873 (isa<SCEVAddRecExpr>(Accum) &&
5874 cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
5878 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5885 if (
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))
6393 if (
const auto *CB = dyn_cast<CallBase>(V))
6394 if (std::optional<ConstantRange>
Range = CB->getRange())
6397 if (
auto *
A = dyn_cast<Argument>(V))
6398 if (std::optional<ConstantRange>
Range =
A->getRange())
6401 return std::nullopt;
6408 UnsignedRanges.erase(AddRec);
6409 SignedRanges.erase(AddRec);
6410 ConstantMultipleCache.erase(AddRec);
6415getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6429 auto *
P = dyn_cast<PHINode>(U->getValue());
6441 Value *Start, *Step;
6448 assert(L && L->getHeader() ==
P->getParent());
6461 case Instruction::AShr:
6462 case Instruction::LShr:
6463 case Instruction::Shl:
6478 KnownStep.getBitWidth() ==
BitWidth);
6481 auto MaxShiftAmt = KnownStep.getMaxValue();
6483 bool Overflow =
false;
6484 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6491 case Instruction::AShr: {
6499 if (KnownStart.isNonNegative())
6502 KnownStart.getMaxValue() + 1);
6503 if (KnownStart.isNegative())
6506 KnownEnd.getMaxValue() + 1);
6509 case Instruction::LShr: {
6518 KnownStart.getMaxValue() + 1);
6520 case Instruction::Shl: {
6524 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6526 KnownEnd.getMaxValue() + 1);
6534ScalarEvolution::getRangeRefIter(
const SCEV *S,
6535 ScalarEvolution::RangeSignHint SignHint) {
6537 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6544 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6545 if (!Seen.
insert(Expr).second)
6551 if (!isa<PHINode>(cast<SCEVUnknown>(Expr)->getValue()))
6578 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6579 const SCEV *
P = WorkList[
I];
6580 auto *UnknownS = dyn_cast<SCEVUnknown>(
P);
6583 for (
const SCEV *
Op :
P->operands())
6588 if (
const PHINode *
P = dyn_cast<PHINode>(UnknownS->getValue())) {
6589 if (!PendingPhiRangesIter.insert(
P).second)
6596 if (!WorkList.
empty()) {
6601 getRangeRef(
P, SignHint);
6603 if (
auto *UnknownS = dyn_cast<SCEVUnknown>(
P))
6604 if (
const PHINode *
P = dyn_cast<PHINode>(UnknownS->getValue()))
6605 PendingPhiRangesIter.erase(
P);
6609 return getRangeRef(S, SignHint, 0);
6616 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6618 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6626 if (
I != Cache.
end())
6635 return getRangeRefIter(S, SignHint);
6643 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6647 ConservativeResult =
6670 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6677 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6684 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6689 return setRange(PtrToInt, SignHint,
X);
6694 unsigned WrapType = OBO::AnyWrap;
6695 if (
Add->hasNoSignedWrap())
6696 WrapType |= OBO::NoSignedWrap;
6697 if (
Add->hasNoUnsignedWrap())
6698 WrapType |= OBO::NoUnsignedWrap;
6699 for (
unsigned i = 1, e =
Add->getNumOperands(); i != e; ++i)
6700 X =
X.addWithNoWrap(getRangeRef(
Add->getOperand(i), SignHint,
Depth + 1),
6701 WrapType, RangeType);
6702 return setRange(
Add, SignHint,
6703 ConservativeResult.intersectWith(
X, RangeType));
6708 for (
unsigned i = 1, e =
Mul->getNumOperands(); i != e; ++i)
6709 X =
X.multiply(getRangeRef(
Mul->getOperand(i), SignHint,
Depth + 1));
6710 return setRange(
Mul, SignHint,
6711 ConservativeResult.intersectWith(
X, RangeType));
6717 return setRange(UDiv, SignHint,
6718 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6726 if (!UnsignedMinValue.
isZero())
6727 ConservativeResult = ConservativeResult.intersectWith(
6737 bool AllNonNeg =
true;
6738 bool AllNonPos =
true;
6739 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6746 ConservativeResult = ConservativeResult.intersectWith(
6751 ConservativeResult = ConservativeResult.intersectWith(
6760 const SCEV *MaxBEScev =
6762 if (!isa<SCEVCouldNotCompute>(MaxBEScev)) {
6763 APInt MaxBECount = cast<SCEVConstant>(MaxBEScev)->getAPInt();
6774 auto RangeFromAffine = getRangeForAffineAR(
6776 ConservativeResult =
6777 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6779 auto RangeFromFactoring = getRangeViaFactoring(
6781 ConservativeResult =
6782 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6788 const SCEV *SymbolicMaxBECount =
6790 if (!isa<SCEVCouldNotCompute>(SymbolicMaxBECount) &&
6793 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6794 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6795 ConservativeResult =
6796 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6801 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6811 ID = Intrinsic::umax;
6814 ID = Intrinsic::smax;
6818 ID = Intrinsic::umin;
6821 ID = Intrinsic::smin;
6827 const auto *NAry = cast<SCEVNAryExpr>(S);
6829 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6831 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6832 return setRange(S, SignHint,
6833 ConservativeResult.intersectWith(
X, RangeType));
6842 ConservativeResult =
6843 ConservativeResult.intersectWith(*MDRange, RangeType);
6848 auto CR = getRangeForUnknownRecurrence(U);
6849 ConservativeResult = ConservativeResult.intersectWith(CR);
6860 if (
U->getType()->isPointerTy()) {
6863 unsigned ptrSize =
DL.getPointerTypeSizeInBits(
U->getType());
6864 int ptrIdxDiff = ptrSize -
BitWidth;
6865 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
6878 ConservativeResult = ConservativeResult.intersectWith(
6882 ConservativeResult = ConservativeResult.intersectWith(
6887 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6894 if ((isa<GlobalVariable>(V) || isa<AllocaInst>(V) ||
6910 ConservativeResult = ConservativeResult.intersectWith(
6916 if (
PHINode *Phi = dyn_cast<PHINode>(V)) {
6918 if (PendingPhiRanges.insert(Phi).second) {
6921 for (
const auto &
Op :
Phi->operands()) {
6923 RangeFromOps = RangeFromOps.unionWith(OpRange);
6925 if (RangeFromOps.isFullSet())
6928 ConservativeResult =
6929 ConservativeResult.intersectWith(RangeFromOps, RangeType);
6930 bool Erased = PendingPhiRanges.erase(Phi);
6931 assert(Erased &&
"Failed to erase Phi properly?");
6937 if (
const auto *
II = dyn_cast<IntrinsicInst>(V))
6938 if (
II->getIntrinsicID() == Intrinsic::vscale) {
6940 ConservativeResult = ConservativeResult.difference(Disallowed);
6943 return setRange(U, SignHint, std::move(ConservativeResult));
6949 return setRange(S, SignHint, std::move(ConservativeResult));
6958 const APInt &MaxBECount,
6965 if (Step == 0 || MaxBECount == 0)
6972 return ConstantRange::getFull(
BitWidth);
6988 return ConstantRange::getFull(
BitWidth);
7000 APInt MovedBoundary = Descending ? (StartLower - std::move(
Offset))
7001 : (StartUpper + std::move(
Offset));
7006 if (StartRange.
contains(MovedBoundary))
7007 return ConstantRange::getFull(
BitWidth);
7010 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7012 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7021 const APInt &MaxBECount) {
7025 "mismatched bit widths");
7034 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7036 StartSRange, MaxBECount,
7048ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7050 ScalarEvolution::RangeSignHint SignHint) {
7051 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7053 "This only works for non-self-wrapping AddRecs!");
7054 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7057 if (!isa<SCEVConstant>(Step))
7058 return ConstantRange::getFull(
BitWidth);
7066 return ConstantRange::getFull(
BitWidth);
7072 MaxItersWithoutWrap))
7073 return ConstantRange::getFull(
BitWidth);
7100 return RangeBetween;
7105 return ConstantRange::getFull(
BitWidth);
7108 isKnownPredicateViaConstantRanges(LEPred, Start,
End))
7109 return RangeBetween;
7111 isKnownPredicateViaConstantRanges(GEPred, Start,
End))
7112 return RangeBetween;
7113 return ConstantRange::getFull(
BitWidth);
7118 const APInt &MaxBECount) {
7125 "mismatched bit widths");
7127 struct SelectPattern {
7128 Value *Condition =
nullptr;
7134 std::optional<unsigned> CastOp;
7141 if (
auto *SA = dyn_cast<SCEVAddExpr>(S)) {
7144 if (SA->getNumOperands() != 2 || !isa<SCEVConstant>(SA->getOperand(0)))
7147 Offset = cast<SCEVConstant>(SA->getOperand(0))->getAPInt();
7148 S = SA->getOperand(1);
7152 if (
auto *SCast = dyn_cast<SCEVIntegralCastExpr>(S)) {
7154 S = SCast->getOperand();
7159 auto *SU = dyn_cast<SCEVUnknown>(S);
7164 Condition =
nullptr;
7196 bool isRecognized() {
return Condition !=
nullptr; }
7199 SelectPattern StartPattern(*
this,
BitWidth, Start);
7200 if (!StartPattern.isRecognized())
7201 return ConstantRange::getFull(
BitWidth);
7203 SelectPattern StepPattern(*
this,
BitWidth, Step);
7204 if (!StepPattern.isRecognized())
7205 return ConstantRange::getFull(
BitWidth);
7207 if (StartPattern.Condition != StepPattern.Condition) {
7211 return ConstantRange::getFull(
BitWidth);
7228 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount);
7230 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount);
7252ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7253 if (
auto *AddRec = dyn_cast<SCEVAddRecExpr>(S))
7255 if (
auto *U = dyn_cast<SCEVUnknown>(S))
7256 if (
auto *
I = dyn_cast<Instruction>(
U->getValue()))
7268 auto pushOp = [&](
const SCEV *S) {
7269 if (!Visited.
insert(S).second)
7272 if (Visited.
size() > 30) {
7279 for (
const auto *S : Ops)
7283 while (!Worklist.
empty()) {
7285 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7286 if (!Bound || DT.
dominates(Bound, DefI))
7299 return getDefiningScopeBound(Ops, Discard);
7302bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7304 if (
A->getParent() ==
B->getParent() &&
7310 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7311 BLoop->getLoopPreheader() ==
A->getParent() &&
7313 A->getParent()->end()) &&
7321bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7338 for (
const Use &
Op :
I->operands()) {
7344 auto *DefI = getDefiningScopeBound(SCEVOps);
7345 return isGuaranteedToTransferExecutionTo(DefI,
I);
7348bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7350 if (isSCEVExprNeverPoison(
I))
7361 auto *ExitingBB =
L->getExitingBlock();
7374 while (!Worklist.
empty()) {
7377 for (
const Use &U : Poison->
uses()) {
7378 const Instruction *PoisonUser = cast<Instruction>(
U.getUser());
7384 if (KnownPoison.
insert(PoisonUser).second)
7392ScalarEvolution::LoopProperties
7393ScalarEvolution::getLoopProperties(
const Loop *L) {
7394 using LoopProperties = ScalarEvolution::LoopProperties;
7396 auto Itr = LoopPropertiesCache.find(L);
7397 if (Itr == LoopPropertiesCache.end()) {
7399 if (
auto *SI = dyn_cast<StoreInst>(
I))
7400 return !
SI->isSimple();
7402 return I->mayThrow() ||
I->mayWriteToMemory();
7405 LoopProperties LP = {
true,
7408 for (
auto *BB :
L->getBlocks())
7409 for (
auto &
I : *BB) {
7411 LP.HasNoAbnormalExits =
false;
7412 if (HasSideEffects(&
I))
7413 LP.HasNoSideEffects =
false;
7414 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7418 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7419 assert(InsertPair.second &&
"We just checked!");
7420 Itr = InsertPair.first;
7433const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7439 Stack.emplace_back(V,
true);
7440 Stack.emplace_back(V,
false);
7441 while (!Stack.empty()) {
7442 auto E = Stack.pop_back_val();
7443 Value *CurV = E.getPointer();
7449 const SCEV *CreatedSCEV =
nullptr;
7452 CreatedSCEV = createSCEV(CurV);
7457 CreatedSCEV = getOperandsToCreate(CurV, Ops);
7461 insertValueToMap(CurV, CreatedSCEV);
7465 Stack.emplace_back(CurV,
true);
7467 Stack.emplace_back(
Op,
false);
7486 }
else if (
ConstantInt *CI = dyn_cast<ConstantInt>(V))
7488 else if (isa<GlobalAlias>(V))
7490 else if (!isa<ConstantExpr>(V))
7496 bool IsConstArg = isa<ConstantInt>(BO->RHS);
7497 switch (BO->Opcode) {
7498 case Instruction::Add:
7499 case Instruction::Mul: {
7512 dyn_cast<Instruction>(V));
7514 (BO->Opcode == Instruction::Add &&
7515 (NewBO->Opcode != Instruction::Add &&
7516 NewBO->Opcode != Instruction::Sub)) ||
7517 (BO->Opcode == Instruction::Mul &&
7518 NewBO->Opcode != Instruction::Mul)) {
7524 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7525 auto *
I = dyn_cast<Instruction>(BO->
Op);
7535 case Instruction::Sub:
7536 case Instruction::UDiv:
7537 case Instruction::URem:
7539 case Instruction::AShr:
7540 case Instruction::Shl:
7541 case Instruction::Xor:
7545 case Instruction::And:
7546 case Instruction::Or:
7550 case Instruction::LShr:
7562 switch (
U->getOpcode()) {
7563 case Instruction::Trunc:
7564 case Instruction::ZExt:
7565 case Instruction::SExt:
7566 case Instruction::PtrToInt:
7570 case Instruction::BitCast:
7577 case Instruction::SDiv:
7578 case Instruction::SRem:
7583 case Instruction::GetElementPtr:
7584 assert(cast<GEPOperator>(U)->getSourceElementType()->isSized() &&
7585 "GEP source element type must be sized");
7590 case Instruction::IntToPtr:
7593 case Instruction::PHI:
7597 case Instruction::Select: {
7599 auto CanSimplifyToUnknown = [
this,
U]() {
7600 if (
U->getType()->isIntegerTy(1) || isa<ConstantInt>(
U->getOperand(0)))
7603 auto *ICI = dyn_cast<ICmpInst>(
U->getOperand(0));
7610 if (!(isa<ConstantInt>(RHS) && cast<ConstantInt>(RHS)->
isZero()))
7617 if (CanSimplifyToUnknown())
7620 for (
Value *Inc :
U->operands())
7625 case Instruction::Call:
7626 case Instruction::Invoke:
7627 if (
Value *RV = cast<CallBase>(U)->getReturnedArgOperand()) {
7632 if (
auto *
II = dyn_cast<IntrinsicInst>(U)) {
7633 switch (
II->getIntrinsicID()) {
7634 case Intrinsic::abs:
7637 case Intrinsic::umax:
7638 case Intrinsic::umin:
7639 case Intrinsic::smax:
7640 case Intrinsic::smin:
7641 case Intrinsic::usub_sat:
7642 case Intrinsic::uadd_sat:
7646 case Intrinsic::start_loop_iterations:
7647 case Intrinsic::annotation:
7648 case Intrinsic::ptr_annotation:
7661const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7672 }
else if (
ConstantInt *CI = dyn_cast<ConstantInt>(V))
7674 else if (isa<GlobalAlias>(V))
7676 else if (!isa<ConstantExpr>(V))
7685 switch (BO->Opcode) {
7686 case Instruction::Add: {
7712 if (BO->Opcode == Instruction::Sub)
7720 if (BO->Opcode == Instruction::Sub)
7726 dyn_cast<Instruction>(V));
7727 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7728 NewBO->Opcode != Instruction::Sub)) {
7738 case Instruction::Mul: {
7758 dyn_cast<Instruction>(V));
7759 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7768 case Instruction::UDiv:
7772 case Instruction::URem:
7776 case Instruction::Sub: {
7779 Flags = getNoWrapFlagsFromUB(BO->
Op);
7784 case Instruction::And:
7787 if (
ConstantInt *CI = dyn_cast<ConstantInt>(BO->RHS)) {
7790 if (CI->isMinusOne())
7792 const APInt &
A = CI->getValue();
7798 unsigned LZ =
A.countl_zero();
7799 unsigned TZ =
A.countr_zero();
7803 0, &AC,
nullptr, &DT);
7805 APInt EffectiveMask =
7807 if ((LZ != 0 || TZ != 0) && !((~
A & ~Known.
Zero) & EffectiveMask)) {
7810 const SCEV *ShiftedLHS =
nullptr;
7811 if (
auto *LHSMul = dyn_cast<SCEVMulExpr>(LHS)) {
7812 if (
auto *OpC = dyn_cast<SCEVConstant>(LHSMul->getOperand(0))) {
7814 unsigned MulZeros = OpC->getAPInt().countr_zero();
7815 unsigned GCD = std::min(MulZeros, TZ);
7820 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
7842 case Instruction::Or:
7851 case Instruction::Xor:
7852 if (
ConstantInt *CI = dyn_cast<ConstantInt>(BO->RHS)) {
7854 if (CI->isMinusOne())
7861 if (
auto *LBO = dyn_cast<BinaryOperator>(BO->LHS))
7862 if (
ConstantInt *LCI = dyn_cast<ConstantInt>(LBO->getOperand(1)))
7863 if (LBO->getOpcode() == Instruction::And &&
7864 LCI->getValue() == CI->getValue())
7866 dyn_cast<SCEVZeroExtendExpr>(
getSCEV(BO->LHS))) {
7868 const SCEV *Z0 =
Z->getOperand();
7875 if (CI->getValue().isMask(Z0TySize))
7881 APInt Trunc = CI->getValue().
trunc(Z0TySize);
7890 case Instruction::Shl:
7892 if (
ConstantInt *SA = dyn_cast<ConstantInt>(BO->RHS)) {
7908 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
7922 case Instruction::AShr:
7943 Operator *
L = dyn_cast<Operator>(BO->LHS);
7944 const SCEV *AddTruncateExpr =
nullptr;
7946 const SCEV *AddConstant =
nullptr;
7948 if (L &&
L->getOpcode() == Instruction::Add) {
7954 Operator *LShift = dyn_cast<Operator>(
L->getOperand(0));
7955 ConstantInt *AddOperandCI = dyn_cast<ConstantInt>(
L->getOperand(1));
7956 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
7959 ShlAmtCI = dyn_cast<ConstantInt>(LShift->
getOperand(1));
7971 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
7977 ShlAmtCI = dyn_cast<ConstantInt>(
L->getOperand(1));
7981 if (AddTruncateExpr && ShlAmtCI) {
7997 const SCEV *CompositeExpr =
7999 if (
L->getOpcode() != Instruction::Shl)
8000 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8009 switch (
U->getOpcode()) {
8010 case Instruction::Trunc:
8013 case Instruction::ZExt:
8016 case Instruction::SExt:
8018 dyn_cast<Instruction>(V))) {
8026 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8027 Type *Ty =
U->getType();
8035 case Instruction::BitCast:
8041 case Instruction::PtrToInt: {
8044 Type *DstIntTy =
U->getType();
8048 if (isa<SCEVCouldNotCompute>(IntOp))
8052 case Instruction::IntToPtr:
8056 case Instruction::SDiv:
8063 case Instruction::SRem:
8070 case Instruction::GetElementPtr:
8071 return createNodeForGEP(cast<GEPOperator>(U));
8073 case Instruction::PHI:
8074 return createNodeForPHI(cast<PHINode>(U));
8076 case Instruction::Select:
8077 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8080 case Instruction::Call:
8081 case Instruction::Invoke:
8082 if (
Value *RV = cast<CallBase>(U)->getReturnedArgOperand())
8085 if (
auto *
II = dyn_cast<IntrinsicInst>(U)) {
8086 switch (
II->getIntrinsicID()) {
8087 case Intrinsic::abs:
8090 cast<ConstantInt>(
II->getArgOperand(1))->
isOne());
8091 case Intrinsic::umax:
8095 case Intrinsic::umin:
8099 case Intrinsic::smax:
8103 case Intrinsic::smin:
8107 case Intrinsic::usub_sat: {
8113 case Intrinsic::uadd_sat: {
8119 case Intrinsic::start_loop_iterations:
8120 case Intrinsic::annotation:
8121 case Intrinsic::ptr_annotation:
8125 case Intrinsic::vscale:
8142 if (isa<SCEVCouldNotCompute>(ExitCount))
8145 auto *ExitCountType = ExitCount->
getType();
8146 assert(ExitCountType->isIntegerTy());
8148 1 + ExitCountType->getScalarSizeInBits());
8155 if (isa<SCEVCouldNotCompute>(ExitCount))
8161 auto CanAddOneWithoutOverflow = [&]() {
8163 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8174 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8204 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8205 assert(L->isLoopExiting(ExitingBlock) &&
8206 "Exiting block must actually branch out of the loop!");
8213 const auto *MaxExitCount =
8220 L->getExitingBlocks(ExitingBlocks);
8222 std::optional<unsigned> Res;
8223 for (
auto *ExitingBB : ExitingBlocks) {
8227 Res = (
unsigned)std::gcd(*Res, Multiple);
8229 return Res.value_or(1);
8233 const SCEV *ExitCount) {
8263 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8264 assert(L->isLoopExiting(ExitingBlock) &&
8265 "Exiting block must actually branch out of the loop!");
8275 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8277 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8279 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8287 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8294 return getBackedgeTakenInfo(L).getExact(L,
this);
8296 return getBackedgeTakenInfo(L).getConstantMax(
this);
8298 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8305 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8309 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8319 for (
PHINode &PN : Header->phis())
8320 if (Visited.
insert(&PN).second)
8324ScalarEvolution::BackedgeTakenInfo &
8325ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8326 auto &BTI = getBackedgeTakenInfo(L);
8327 if (BTI.hasFullInfo())
8330 auto Pair = PredicatedBackedgeTakenCounts.insert({
L, BackedgeTakenInfo()});
8333 return Pair.first->second;
8335 BackedgeTakenInfo
Result =
8336 computeBackedgeTakenCount(L,
true);
8338 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8341ScalarEvolution::BackedgeTakenInfo &
8342ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8348 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8349 BackedgeTakenCounts.insert({
L, BackedgeTakenInfo()});
8351 return Pair.first->second;
8356 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8363 if (
Result.hasAnyInfo()) {
8366 auto LoopUsersIt = LoopUsers.find(L);
8367 if (LoopUsersIt != LoopUsers.end())
8369 forgetMemoizedResults(ToForget);
8372 for (
PHINode &PN :
L->getHeader()->phis())
8373 ConstantEvolutionLoopExitValue.erase(&PN);
8381 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8390 BackedgeTakenCounts.clear();
8391 PredicatedBackedgeTakenCounts.clear();
8392 BECountUsers.clear();
8393 LoopPropertiesCache.clear();
8394 ConstantEvolutionLoopExitValue.clear();
8395 ValueExprMap.
clear();
8396 ValuesAtScopes.clear();
8397 ValuesAtScopesUsers.clear();
8398 LoopDispositions.clear();
8399 BlockDispositions.clear();
8400 UnsignedRanges.clear();
8401 SignedRanges.clear();
8402 ExprValueMap.
clear();
8404 ConstantMultipleCache.clear();
8405 PredicatedSCEVRewrites.clear();
8407 FoldCacheUser.clear();
8409void ScalarEvolution::visitAndClearUsers(
8413 while (!Worklist.
empty()) {
8420 if (It != ValueExprMap.
end()) {
8421 eraseValueFromMap(It->first);
8423 if (
PHINode *PN = dyn_cast<PHINode>(
I))
8424 ConstantEvolutionLoopExitValue.erase(PN);
8438 while (!LoopWorklist.
empty()) {
8442 forgetBackedgeTakenCounts(CurrL,
false);
8443 forgetBackedgeTakenCounts(CurrL,
true);
8446 for (
auto I = PredicatedSCEVRewrites.begin();
8447 I != PredicatedSCEVRewrites.end();) {
8448 std::pair<const SCEV *, const Loop *> Entry =
I->first;
8449 if (Entry.second == CurrL)
8450 PredicatedSCEVRewrites.erase(
I++);
8455 auto LoopUsersItr = LoopUsers.find(CurrL);
8456 if (LoopUsersItr != LoopUsers.end()) {
8457 ToForget.
insert(ToForget.
end(), LoopUsersItr->second.begin(),
8458 LoopUsersItr->second.end());
8463 visitAndClearUsers(Worklist, Visited, ToForget);
8465 LoopPropertiesCache.erase(CurrL);
8468 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8470 forgetMemoizedResults(ToForget);
8487 visitAndClearUsers(Worklist, Visited, ToForget);
8489 forgetMemoizedResults(ToForget);
8501 struct InvalidationRootCollector {
8505 InvalidationRootCollector(
Loop *L) : L(L) {}
8507 bool follow(
const SCEV *S) {
8508 if (
auto *SU = dyn_cast<SCEVUnknown>(S)) {
8509 if (
auto *
I = dyn_cast<Instruction>(SU->getValue()))
8512 }
else if (
auto *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
8513 if (L->contains(AddRec->
getLoop()))
8518 bool isDone()
const {
return false; }
8521 InvalidationRootCollector
C(L);
8523 forgetMemoizedResults(
C.Roots);
8536 BlockDispositions.clear();
8537 LoopDispositions.clear();
8554 while (!Worklist.
empty()) {
8556 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8557 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8558 if (!LoopDispoRemoved && !BlockDispoRemoved)
8560 auto Users = SCEVUsers.find(Curr);
8561 if (
Users != SCEVUsers.end())
8578 if (!isComplete() || ExitNotTaken.empty())
8589 for (
const auto &ENT : ExitNotTaken) {
8590 const SCEV *BECount = ENT.ExactNotTaken;
8593 "We should only have known counts for exiting blocks that dominate "
8599 for (
const auto *
P : ENT.Predicates)
8602 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8603 "Predicate should be always true!");
8614ScalarEvolution::BackedgeTakenInfo::getExact(
const BasicBlock *ExitingBlock,
8616 for (
const auto &ENT : ExitNotTaken)
8617 if (ENT.ExitingBlock == ExitingBlock && ENT.hasAlwaysTruePredicate())
8618 return ENT.ExactNotTaken;
8623const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8625 for (
const auto &ENT : ExitNotTaken)
8626 if (ENT.ExitingBlock == ExitingBlock && ENT.hasAlwaysTruePredicate())
8627 return ENT.ConstantMaxNotTaken;
8632const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8634 for (
const auto &ENT : ExitNotTaken)
8635 if (ENT.ExitingBlock == ExitingBlock && ENT.hasAlwaysTruePredicate())
8636 return ENT.SymbolicMaxNotTaken;
8643ScalarEvolution::BackedgeTakenInfo::getConstantMax(
ScalarEvolution *SE)
const {
8644 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8645 return !ENT.hasAlwaysTruePredicate();
8648 if (!getConstantMax() ||
any_of(ExitNotTaken, PredicateNotAlwaysTrue))
8651 assert((isa<SCEVCouldNotCompute>(getConstantMax()) ||
8652 isa<SCEVConstant>(getConstantMax())) &&
8653 "No point in having a non-constant max backedge taken count!");
8654 return getConstantMax();
8657const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8667 for (
const auto &ENT : ExitNotTaken) {
8668 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8669 if (!isa<SCEVCouldNotCompute>(ExitCount)) {
8671 "We should only have known counts for exiting blocks that "
8675 for (
const auto *
P : ENT.Predicates)
8678 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8679 "Predicate should be always true!");
8682 if (ExitCounts.
empty())
8691bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8693 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8694 return !ENT.hasAlwaysTruePredicate();
8696 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8703 const SCEV *E,
const SCEV *ConstantMaxNotTaken,
8704 const SCEV *SymbolicMaxNotTaken,
bool MaxOrZero,
8706 : ExactNotTaken(E), ConstantMaxNotTaken(ConstantMaxNotTaken),
8707 SymbolicMaxNotTaken(SymbolicMaxNotTaken), MaxOrZero(MaxOrZero) {
8718 "Exact is not allowed to be less precise than Constant Max");
8721 "Exact is not allowed to be less precise than Symbolic Max");
8724 "Symbolic Max is not allowed to be less precise than Constant Max");
8727 "No point in having a non-constant max backedge taken count!");
8728 for (
const auto *PredSet : PredSetList)
8729 for (
const auto *
P : *PredSet)
8732 "Backedge count should be int");
8735 "Max backedge count should be int");
8739 const SCEV *E,
const SCEV *ConstantMaxNotTaken,
8740 const SCEV *SymbolicMaxNotTaken,
bool MaxOrZero,
8742 :
ExitLimit(E, ConstantMaxNotTaken, SymbolicMaxNotTaken, MaxOrZero,
8747ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8749 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8750 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8751 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8753 ExitNotTaken.reserve(ExitCounts.
size());
8754 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8755 std::back_inserter(ExitNotTaken),
8756 [&](
const EdgeExitInfo &EEI) {
8757 BasicBlock *ExitBB = EEI.first;
8758 const ExitLimit &EL = EEI.second;
8759 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
8760 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
8763 assert((isa<SCEVCouldNotCompute>(ConstantMax) ||
8764 isa<SCEVConstant>(ConstantMax)) &&
8765 "No point in having a non-constant max backedge taken count!");
8769ScalarEvolution::BackedgeTakenInfo
8770ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
8771 bool AllowPredicates) {
8773 L->getExitingBlocks(ExitingBlocks);
8775 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8778 bool CouldComputeBECount =
true;
8780 const SCEV *MustExitMaxBECount =
nullptr;
8781 const SCEV *MayExitMaxBECount =
nullptr;
8782 bool MustExitMaxOrZero =
false;
8783 bool IsOnlyExit = ExitingBlocks.
size() == 1;
8792 if (
auto *BI = dyn_cast<BranchInst>(ExitBB->getTerminator()))
8793 if (
auto *CI = dyn_cast<ConstantInt>(BI->
getCondition())) {
8795 if (ExitIfTrue == CI->
isZero())
8799 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
8801 assert((AllowPredicates || EL.Predicates.empty()) &&
8802 "Predicated exit limit when predicates are not allowed!");
8807 ++NumExitCountsComputed;
8811 CouldComputeBECount =
false;
8818 "Exact is known but symbolic isn't?");
8819 ++NumExitCountsNotComputed;
8835 if (!MustExitMaxBECount) {
8836 MustExitMaxBECount = EL.ConstantMaxNotTaken;
8837 MustExitMaxOrZero = EL.MaxOrZero;
8840 EL.ConstantMaxNotTaken);
8844 MayExitMaxBECount = EL.ConstantMaxNotTaken;
8847 EL.ConstantMaxNotTaken);
8851 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
8855 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
8861 for (
const auto &Pair : ExitCounts) {
8862 if (!isa<SCEVConstant>(Pair.second.ExactNotTaken))
8863 BECountUsers[Pair.second.ExactNotTaken].insert({L, AllowPredicates});
8864 if (!isa<SCEVConstant>(Pair.second.SymbolicMaxNotTaken))
8865 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
8866 {L, AllowPredicates});
8868 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
8869 MaxBECount, MaxOrZero);
8873ScalarEvolution::computeExitLimit(
const Loop *L,
BasicBlock *ExitingBlock,
8874 bool IsOnlyExit,
bool AllowPredicates) {
8875 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
8879 if (!Latch || !DT.
dominates(ExitingBlock, Latch))
8883 if (
BranchInst *BI = dyn_cast<BranchInst>(Term)) {
8887 "It should have one successor in loop and one exit block!");
8894 if (
SwitchInst *SI = dyn_cast<SwitchInst>(Term)) {
8898 if (!
L->contains(SBB)) {
8903 assert(Exit &&
"Exiting block must have at least one exit");
8904 return computeExitLimitFromSingleExitSwitch(
8905 L, SI, Exit, IsOnlyExit);
8912 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
8913 bool AllowPredicates) {
8914 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
8915 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
8916 ControlsOnlyExit, AllowPredicates);
8919std::optional<ScalarEvolution::ExitLimit>
8920ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
8921 bool ExitIfTrue,
bool ControlsOnlyExit,
8922 bool AllowPredicates) {
8924 (void)this->ExitIfTrue;
8925 (void)this->AllowPredicates;
8927 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
8928 this->AllowPredicates == AllowPredicates &&
8929 "Variance in assumed invariant key components!");
8930 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
8931 if (Itr == TripCountMap.end())
8932 return std::nullopt;
8936void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
8938 bool ControlsOnlyExit,
8939 bool AllowPredicates,
8940 const ExitLimit &EL) {
8941 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
8942 this->AllowPredicates == AllowPredicates &&
8943 "Variance in assumed invariant key components!");
8945 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
8946 assert(InsertResult.second &&
"Expected successful insertion!");
8952 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
8953 bool ControlsOnlyExit,
bool AllowPredicates) {
8955 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
8959 ExitLimit EL = computeExitLimitFromCondImpl(
8960 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
8961 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
8966 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
8967 bool ControlsOnlyExit,
bool AllowPredicates) {
8969 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
8970 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates))
8971 return *LimitFromBinOp;
8975 if (
ICmpInst *ExitCondICmp = dyn_cast<ICmpInst>(ExitCond)) {
8977 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
8978 if (EL.hasFullInfo() || !AllowPredicates)
8982 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
8991 if (
ConstantInt *CI = dyn_cast<ConstantInt>(ExitCond)) {
9017 auto EL = computeExitLimitFromICmp(L, Pred, LHS,
getConstant(NewRHSC),
9018 ControlsOnlyExit, AllowPredicates);
9019 if (EL.hasAnyInfo())
9024 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9027std::optional<ScalarEvolution::ExitLimit>
9028ScalarEvolution::computeExitLimitFromCondFromBinOp(
9029 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9030 bool ControlsOnlyExit,
bool AllowPredicates) {
9039 return std::nullopt;
9044 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9045 ExitLimit EL0 = computeExitLimitFromCondCached(
9046 Cache, L, Op0, ExitIfTrue, ControlsOnlyExit && !EitherMayExit,
9048 ExitLimit EL1 = computeExitLimitFromCondCached(
9049 Cache, L, Op1, ExitIfTrue, ControlsOnlyExit && !EitherMayExit,
9053 const Constant *NeutralElement = ConstantInt::get(ExitCond->
getType(), IsAnd);
9054 if (isa<ConstantInt>(Op1))
9055 return Op1 == NeutralElement ? EL0 : EL1;
9056 if (isa<ConstantInt>(Op0))
9057 return Op0 == NeutralElement ? EL1 : EL0;
9062 if (EitherMayExit) {
9063 bool UseSequentialUMin = !isa<BinaryOperator>(ExitCond);
9072 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9074 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9077 EL1.ConstantMaxNotTaken);
9079 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9081 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9084 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9088 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9089 BECount = EL0.ExactNotTaken;
9098 if (isa<SCEVCouldNotCompute>(ConstantMaxBECount) &&
9099 !isa<SCEVCouldNotCompute>(BECount))
9101 if (isa<SCEVCouldNotCompute>(SymbolicMaxBECount))
9102 SymbolicMaxBECount =
9103 isa<SCEVCouldNotCompute>(BECount) ? ConstantMaxBECount : BECount;
9104 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9105 { &EL0.Predicates, &EL1.Predicates });
9109 const Loop *L,
ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9110 bool AllowPredicates) {
9122 ExitLimit EL = computeExitLimitFromICmp(L, Pred, LHS, RHS, ControlsOnlyExit,
9124 if (EL.hasAnyInfo())
9127 auto *ExhaustiveCount =
9128 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9130 if (!isa<SCEVCouldNotCompute>(ExhaustiveCount))
9131 return ExhaustiveCount;
9133 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9138 bool ControlsOnlyExit,
bool AllowPredicates) {
9159 if (
const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS))
9160 if (
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
9167 if (!isa<SCEVCouldNotCompute>(Ret))
return Ret;
9178 auto *InnerLHS =
LHS;
9179 if (
auto *ZExt = dyn_cast<SCEVZeroExtendExpr>(LHS))
9180 InnerLHS = ZExt->getOperand();
9181 if (
const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(InnerLHS)) {
9184 StrideC && StrideC->getAPInt().isPowerOf2()) {
9199 if (isa<SCEVCouldNotCompute>(LHS))
9204 if (isa<SCEVCouldNotCompute>(RHS))
9207 ExitLimit EL = howFarToZero(
getMinusSCEV(LHS, RHS), L, ControlsOnlyExit,
9209 if (EL.hasAnyInfo())
9217 if (isa<SCEVCouldNotCompute>(LHS))
9222 if (isa<SCEVCouldNotCompute>(RHS))
9225 ExitLimit EL = howFarToNonZero(
getMinusSCEV(LHS, RHS), L);
9226 if (EL.hasAnyInfo())
return EL;
9238 auto *OldType = dyn_cast<IntegerType>(
LHS->
getType());
9258 ExitLimit EL = howManyLessThans(LHS, RHS, L, IsSigned, ControlsOnlyExit,
9260 if (EL.hasAnyInfo())
9276 ExitLimit EL = howManyGreaterThans(LHS, RHS, L, IsSigned, ControlsOnlyExit,
9278 if (EL.hasAnyInfo())
9290ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9293 bool ControlsOnlyExit) {
9294 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9297 if (
Switch->getDefaultDest() == ExitingBlock)
9301 "Default case must not exit the loop!");
9306 ExitLimit EL = howFarToZero(
getMinusSCEV(LHS, RHS), L, ControlsOnlyExit);
9307 if (EL.hasAnyInfo())
9318 assert(isa<SCEVConstant>(Val) &&
9319 "Evaluation of SCEV at constant didn't fold correctly?");
9320 return cast<SCEVConstant>(Val)->getValue();
9333 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9339 auto MatchPositiveShift =
9342 using namespace PatternMatch;
9346 OutOpCode = Instruction::LShr;
9348 OutOpCode = Instruction::AShr;
9350 OutOpCode = Instruction::Shl;
9365 auto MatchShiftRecurrence =
9367 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9382 if (MatchPositiveShift(LHS, V, OpC)) {
9383 PostShiftOpCode = OpC;
9388 PNOut = dyn_cast<PHINode>(LHS);
9389 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9392 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9398 MatchPositiveShift(BEValue, OpLHS, OpCodeOut) &&
9405 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9410 if (!MatchShiftRecurrence(LHS, PN, OpCode))
9427 case Instruction::AShr: {
9433 auto *Ty = cast<IntegerType>(
RHS->
getType());
9435 StableValue = ConstantInt::get(Ty, 0);
9437 StableValue = ConstantInt::get(Ty, -1,
true);
9443 case Instruction::LShr:
9444 case Instruction::Shl:
9447 StableValue = ConstantInt::get(cast<IntegerType>(
RHS->
getType()), 0);
9454 "Otherwise cannot be an operand to a branch instruction");
9456 if (
Result->isZeroValue()) {
9458 const SCEV *UpperBound =
9469 if (isa<BinaryOperator>(
I) || isa<CmpInst>(
I) ||
9470 isa<SelectInst>(
I) || isa<CastInst>(
I) || isa<GetElementPtrInst>(
I) ||
9471 isa<LoadInst>(
I) || isa<ExtractValueInst>(
I))
9474 if (
const CallInst *CI = dyn_cast<CallInst>(
I))
9475 if (
const Function *F = CI->getCalledFunction())
9484 if (!L->contains(
I))
return false;
9486 if (isa<PHINode>(
I)) {
9489 return L->getHeader() ==
I->getParent();
9510 if (isa<Constant>(
Op))
continue;
9515 PHINode *
P = dyn_cast<PHINode>(OpInst);
9546 if (
PHINode *PN = dyn_cast<PHINode>(
I))
9563 if (
Constant *
C = dyn_cast<Constant>(V))
return C;
9565 if (!
I)
return nullptr;
9576 if (isa<PHINode>(
I))
return nullptr;
9578 std::vector<Constant*>
Operands(
I->getNumOperands());
9580 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9581 Instruction *Operand = dyn_cast<Instruction>(
I->getOperand(i));
9583 Operands[i] = dyn_cast<Constant>(
I->getOperand(i));
9589 if (!
C)
return nullptr;
9611 if (IncomingVal != CurrentVal) {
9614 IncomingVal = CurrentVal;
9626ScalarEvolution::getConstantEvolutionLoopExitValue(
PHINode *PN,
9629 auto I = ConstantEvolutionLoopExitValue.find(PN);
9630 if (
I != ConstantEvolutionLoopExitValue.end())
9634 return ConstantEvolutionLoopExitValue[PN] =
nullptr;
9636 Constant *&RetVal = ConstantEvolutionLoopExitValue[PN];
9640 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9648 CurrentIterVals[&
PHI] = StartCST;
9650 if (!CurrentIterVals.
count(PN))
9651 return RetVal =
nullptr;
9657 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9660 unsigned IterationNum = 0;
9662 for (; ; ++IterationNum) {
9663 if (IterationNum == NumIterations)
9664 return RetVal = CurrentIterVals[PN];
9673 NextIterVals[PN] = NextPHI;
9675 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9681 for (
const auto &
I : CurrentIterVals) {
9683 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9688 for (
const auto &
I : PHIsToCompute) {
9692 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9695 if (NextPHI !=
I.second)
9696 StoppedEvolving =
false;
9701 if (StoppedEvolving)
9702 return RetVal = CurrentIterVals[PN];
9704 CurrentIterVals.swap(NextIterVals);
9708const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
9720 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9723 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
9727 CurrentIterVals[&
PHI] = StartCST;
9729 if (!CurrentIterVals.
count(PN))
9737 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
9738 auto *CondVal = dyn_cast_or_null<ConstantInt>(
9744 if (CondVal->getValue() ==
uint64_t(ExitWhen)) {
9745 ++NumBruteForceTripCountsComputed;
9756 for (
const auto &
I : CurrentIterVals) {
9758 if (!
PHI ||
PHI->getParent() != Header)
continue;
9763 if (NextPHI)
continue;
9765 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9768 CurrentIterVals.swap(NextIterVals);
9779 for (
auto &LS : Values)
9781 return LS.second ? LS.second : V;
9786 const SCEV *
C = computeSCEVAtScope(V, L);
9787 for (
auto &LS :
reverse(ValuesAtScopes[V]))
9788 if (LS.first == L) {
9790 if (!isa<SCEVConstant>(
C))
9791 ValuesAtScopesUsers[
C].push_back({L, V});
9802 switch (V->getSCEVType()) {
9808 return cast<SCEVConstant>(V)->getValue();
9810 return dyn_cast<Constant>(cast<SCEVUnknown>(V)->getValue());
9835 assert(!
C->getType()->isPointerTy() &&
9836 "Can only have one pointer, and it must be last");
9863ScalarEvolution::getWithOperands(
const SCEV *S,
9872 auto *AddRec = cast<SCEVAddRecExpr>(S);
9876 return getAddExpr(NewOps, cast<SCEVAddExpr>(S)->getNoWrapFlags());
9878 return getMulExpr(NewOps, cast<SCEVMulExpr>(S)->getNoWrapFlags());
9898const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
9899 switch (
V->getSCEVType()) {
9910 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
9921 for (++i; i !=
e; ++i)
9926 AddRec = dyn_cast<SCEVAddRecExpr>(FoldedRec);
9965 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
9967 if (OpAtScope != Ops[i]) {
9975 for (++i; i !=
e; ++i) {
9980 return getWithOperands(V, NewOps);
9994 if (
PHINode *PN = dyn_cast<PHINode>(
I)) {
9995 const Loop *CurrLoop = this->LI[
I->getParent()];
10006 if (BackedgeTakenCount->
isZero()) {
10007 Value *InitValue =
nullptr;
10008 bool MultipleInitValues =
false;
10014 MultipleInitValues =
true;
10019 if (!MultipleInitValues && InitValue)
10024 if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) &&
10028 unsigned InLoopPred =
10034 if (
auto *BTCC = dyn_cast<SCEVConstant>(BackedgeTakenCount)) {
10039 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10055 bool MadeImprovement =
false;
10070 MadeImprovement |= OrigV != OpV;
10075 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10080 if (!MadeImprovement)
10101const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10103 return stripInjectiveFunctions(ZExt->getOperand());
10105 return stripInjectiveFunctions(SExt->getOperand());
10121 assert(
A != 0 &&
"A must be non-zero.");
10143 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10163static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10169 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10170 << *AddRec <<
'\n');
10173 if (!LC || !MC || !
NC) {
10174 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10175 return std::nullopt;
10181 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10189 N =
N.sext(NewWidth);
10190 M = M.sext(NewWidth);
10191 L = L.sext(NewWidth);
10208 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10209 <<
", multiplied by " <<
T <<
'\n');
10218 std::optional<APInt>
Y) {
10220 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10223 return XW.
slt(YW) ? *
X : *
Y;
10226 return std::nullopt;
10227 return X ? *
X : *
Y;
10244 return std::nullopt;
10245 unsigned W =
X->getBitWidth();
10265static std::optional<APInt>
10271 return std::nullopt;
10274 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10275 std::optional<APInt>
X =
10278 return std::nullopt;
10283 return std::nullopt;
10298static std::optional<APInt>
10302 "Starting value of addrec should be 0");
10303 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10304 <<
Range <<
", addrec " << *AddRec <<
'\n');
10308 "Addrec's initial value should be in range");
10314 return std::nullopt;
10324 auto SolveForBoundary =
10325 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10328 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10329 << Bound <<
" (before multiplying by " << M <<
")\n");
10332 std::optional<APInt> SO;
10335 "signed overflow\n");
10339 "unsigned overflow\n");
10340 std::optional<APInt> UO =
10343 auto LeavesRange = [&] (
const APInt &
X) {
10360 return {std::nullopt,
false};
10365 if (LeavesRange(*Min))
10366 return { Min,
true };
10367 std::optional<APInt> Max = Min == SO ? UO : SO;
10368 if (LeavesRange(*Max))
10369 return { Max,
true };
10372 return {std::nullopt,
true};
10379 auto SL = SolveForBoundary(
Lower);
10380 auto SU = SolveForBoundary(
Upper);
10383 if (!SL.second || !SU.second)
10384 return std::nullopt;
10429 bool ControlsOnlyExit,
10430 bool AllowPredicates) {
10441 if (
C->getValue()->isZero())
return C;
10446 dyn_cast<SCEVAddRecExpr>(stripInjectiveFunctions(V));
10448 if (!AddRec && AllowPredicates)
10454 if (!AddRec || AddRec->
getLoop() != L)
10465 return ExitLimit(R, R, R,
false, Predicates);
10488 const SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step);
10530 return ExitLimit(Distance,
getConstant(MaxBECount), Distance,
false,
10556 const SCEV *SymbolicMax =
10557 isa<SCEVCouldNotCompute>(
Exact) ? ConstantMax :
Exact;
10558 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10572 auto *S = isa<SCEVCouldNotCompute>(E) ?
M : E;
10573 return ExitLimit(E, M, S,
false, Predicates);
10577ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10585 if (!
C->getValue()->isZero())
10595std::pair<const BasicBlock *, const BasicBlock *>
10596ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10608 return {
L->getLoopPredecessor(),
L->getHeader()};
10610 return {
nullptr,
nullptr};
10619 if (
A ==
B)
return true;
10625 return A->isIdenticalTo(
B) && (isa<BinaryOperator>(
A) || isa<GetElementPtrInst>(
A));
10632 if (
const Instruction *AI = dyn_cast<Instruction>(AU->getValue()))
10633 if (
const Instruction *BI = dyn_cast<Instruction>(BU->getValue()))
10634 if (ComputesEqualValues(AI, BI))
10643 if (!
Add ||
Add->getNumOperands() != 2)
10645 if (
auto *ME = dyn_cast<SCEVMulExpr>(
Add->getOperand(0));
10646 ME && ME->getNumOperands() == 2 && ME->getOperand(0)->isAllOnesValue()) {
10647 LHS =
Add->getOperand(1);
10648 RHS = ME->getOperand(1);
10651 if (
auto *ME = dyn_cast<SCEVMulExpr>(
Add->getOperand(1));
10652 ME && ME->getNumOperands() == 2 && ME->getOperand(0)->isAllOnesValue()) {
10653 LHS =
Add->getOperand(0);
10654 RHS = ME->getOperand(1);
10661 const SCEV *&LHS,
const SCEV *&RHS,
10663 bool Changed =
false;
10666 auto TrivialCase = [&](
bool TriviallyTrue) {
10680 return TrivialCase(
false);
10681 return TrivialCase(
true);
10704 const APInt &
RA = RC->getAPInt();
10706 bool SimplifiedByConstantRange =
false;
10711 return TrivialCase(
true);
10713 return TrivialCase(
false);
10722 Changed = SimplifiedByConstantRange =
true;
10726 if (!SimplifiedByConstantRange) {
10743 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
10749 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
10755 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
10761 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
10773 return TrivialCase(
true);
10775 return TrivialCase(
false);
10864 if (
const auto *SExt = dyn_cast<SCEVSignExtendExpr>(S))
10869std::pair<const SCEV *, const SCEV *>
10872 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
10874 return { Start, Start };
10876 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
10882 const SCEV *LHS,
const SCEV *RHS) {
10885 getUsedLoops(
LHS, LoopsUsed);
10886 getUsedLoops(
RHS, LoopsUsed);
10888 if (LoopsUsed.
empty())
10893 for (
const auto *L1 : LoopsUsed)
10894 for (
const auto *L2 : LoopsUsed)
10896 DT.
dominates(L2->getHeader(), L1->getHeader())) &&
10897 "Domination relationship is not a linear order");
10927 SplitRHS.second) &&
10932 const SCEV *LHS,
const SCEV *RHS) {
10939 if (isKnownPredicateViaSplitting(Pred,
LHS,
RHS))
10943 return isKnownViaNonRecursiveReasoning(Pred,
LHS,
RHS);
10953 return std::nullopt;
10968 if (KnownWithoutContext)
10969 return KnownWithoutContext;
10977 return std::nullopt;
10983 const Loop *L =
LHS->getLoop();
10988std::optional<ScalarEvolution::MonotonicPredicateType>
10991 auto Result = getMonotonicPredicateTypeImpl(
LHS, Pred);
10997 auto ResultSwapped =
11000 assert(*ResultSwapped != *Result &&
11001 "monotonicity should flip as we flip the predicate");
11008std::optional<ScalarEvolution::MonotonicPredicateType>
11009ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11023 return std::nullopt;
11027 "Should be greater or less!");
11031 if (!
LHS->hasNoUnsignedWrap())
11032 return std::nullopt;
11036 "Relational predicate is either signed or unsigned!");
11037 if (!
LHS->hasNoSignedWrap())
11038 return std::nullopt;
11040 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11048 return std::nullopt;
11051std::optional<ScalarEvolution::LoopInvariantPredicate>
11059 return std::nullopt;
11066 if (!ArLHS || ArLHS->
getLoop() != L)
11067 return std::nullopt;
11070 if (!MonotonicType)
11071 return std::nullopt;
11097 return std::nullopt;
11134 return std::nullopt;
11137std::optional<ScalarEvolution::LoopInvariantPredicate>
11142 Pred,
LHS,
RHS, L, CtxI, MaxIter))
11144 if (
auto *
UMin = dyn_cast<SCEVUMinExpr>(MaxIter))
11150 for (
auto *
Op :
UMin->operands())
11154 return std::nullopt;
11157std::optional<ScalarEvolution::LoopInvariantPredicate>
11172 return std::nullopt;
11178 auto *AR = dyn_cast<SCEVAddRecExpr>(
LHS);
11179 if (!AR || AR->
getLoop() != L)
11180 return std::nullopt;
11184 return std::nullopt;
11190 if (Step != One && Step != MinusOne)
11191 return std::nullopt;
11197 return std::nullopt;
11203 return std::nullopt;
11211 if (Step == MinusOne)
11215 return std::nullopt;
11221bool ScalarEvolution::isKnownPredicateViaConstantRanges(
11231 return RangeLHS.
icmp(Pred, RangeRHS);
11242 if (CheckRanges(SL, SR))
11246 if (CheckRanges(UL, UR))
11255 return CheckRanges(SL, SR);
11260 return CheckRanges(UL, UR);
11270 auto MatchBinaryAddToConst = [
this](
const SCEV *
X,
const SCEV *
Y,
11273 const SCEV *XNonConstOp, *XConstOp;
11274 const SCEV *YNonConstOp, *YConstOp;
11278 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11281 XFlagsPresent = ExpectedFlags;
11283 if (!isa<SCEVConstant>(XConstOp) ||
11284 (XFlagsPresent & ExpectedFlags) != ExpectedFlags)
11287 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11290 YFlagsPresent = ExpectedFlags;
11293 if (!isa<SCEVConstant>(YConstOp) ||
11294 (YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11297 if (YNonConstOp != XNonConstOp)
11300 OutC1 = cast<SCEVConstant>(XConstOp)->getAPInt();
11301 OutC2 = cast<SCEVConstant>(YConstOp)->getAPInt();
11378bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB,
11380 const SCEV *LHS,
const SCEV *RHS) {
11389 return match(&
I, m_Intrinsic<Intrinsic::experimental_guard>(
11391 isImpliedCond(Pred, LHS, RHS, Condition,
false);
11401 const SCEV *LHS,
const SCEV *RHS) {
11410 "This cannot be done on broken IR!");
11413 if (isKnownViaNonRecursiveReasoning(Pred,
LHS,
RHS))
11422 if (LoopContinuePredicate && LoopContinuePredicate->
isConditional() &&
11423 isImpliedCond(Pred,
LHS,
RHS,
11425 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11430 if (WalkingBEDominatingConds)
11436 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11437 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11444 const SCEV *LoopCounter =
11455 auto *CI = cast<CallInst>(AssumeVH);
11459 if (isImpliedCond(Pred,
LHS,
RHS, CI->getArgOperand(0),
false))
11463 if (isImpliedViaGuard(Latch, Pred,
LHS,
RHS))
11466 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11467 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11468 assert(DTN &&
"should reach the loop header before reaching the root!");
11471 if (isImpliedViaGuard(BB, Pred,
LHS,
RHS))
11479 if (!ContinuePredicate || !ContinuePredicate->
isConditional())
11495 if (isImpliedCond(Pred,
LHS,
RHS, Condition,
11513 "This cannot be done on broken IR!");
11521 const bool ProvingStrictComparison = (Pred != NonStrictPredicate);
11522 bool ProvedNonStrictComparison =
false;
11523 bool ProvedNonEquality =
false;
11525 auto SplitAndProve =
11527 if (!ProvedNonStrictComparison)
11528 ProvedNonStrictComparison = Fn(NonStrictPredicate);
11529 if (!ProvedNonEquality)
11531 if (ProvedNonStrictComparison && ProvedNonEquality)
11536 if (ProvingStrictComparison) {
11538 return isKnownViaNonRecursiveReasoning(
P,
LHS,
RHS);
11540 if (SplitAndProve(ProofFn))
11545 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
11547 if (isImpliedCond(Pred,
LHS,
RHS, Condition,
Inverse, CtxI))
11549 if (ProvingStrictComparison) {
11553 if (SplitAndProve(ProofFn))
11564 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
11568 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
11569 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
11571 dyn_cast<BranchInst>(Pair.first->getTerminator());
11584 auto *CI = cast<CallInst>(AssumeVH);
11588 if (ProveViaCond(CI->getArgOperand(0),
false))
11596 for (
const auto *GU : GuardDecl->users())
11597 if (
const auto *Guard = dyn_cast<IntrinsicInst>(GU))
11599 if (ProveViaCond(Guard->getArgOperand(0),
false))
11615 "LHS is not available at Loop Entry");
11617 "RHS is not available at Loop Entry");
11619 if (isKnownViaNonRecursiveReasoning(Pred,
LHS,
RHS))
11630 if (FoundCondValue ==
11634 if (!PendingLoopPredicates.insert(FoundCondValue).second)
11638 make_scope_exit([&]() { PendingLoopPredicates.erase(FoundCondValue); });
11641 const Value *Op0, *Op1;
11644 return isImpliedCond(Pred, LHS, RHS, Op0,
Inverse, CtxI) ||
11645 isImpliedCond(Pred, LHS, RHS, Op1,
Inverse, CtxI);
11648 return isImpliedCond(Pred, LHS, RHS, Op0,
Inverse, CtxI) ||
11649 isImpliedCond(Pred, LHS, RHS, Op1,
Inverse, CtxI);
11652 const ICmpInst *ICI = dyn_cast<ICmpInst>(FoundCondValue);
11653 if (!ICI)
return false;
11666 return isImpliedCond(Pred, LHS, RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
11672 const SCEV *FoundLHS,
const SCEV *FoundRHS,
11683 auto *WideType = FoundLHS->
getType();
11693 if (isImpliedCondBalancedTypes(Pred, LHS, RHS, FoundPred, TruncFoundLHS,
11694 TruncFoundRHS, CtxI))
11720 return isImpliedCondBalancedTypes(Pred, LHS, RHS, FoundPred, FoundLHS,
11724bool ScalarEvolution::isImpliedCondBalancedTypes(
11730 "Types should be balanced!");
11737 if (FoundLHS == FoundRHS)
11741 if (LHS == FoundRHS || RHS == FoundLHS) {
11742 if (isa<SCEVConstant>(RHS)) {
11752 if (FoundPred == Pred)
11753 return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS, CtxI);
11767 if (!isa<SCEVConstant>(RHS) && !isa<SCEVAddRecExpr>(LHS))
11768 return isImpliedCondOperands(FoundPred, RHS, LHS, FoundLHS, FoundRHS,
11770 if (!isa<SCEVConstant>(FoundRHS) && !isa<SCEVAddRecExpr>(FoundLHS))
11771 return isImpliedCondOperands(Pred, LHS, RHS, FoundRHS, FoundLHS, CtxI);
11778 FoundLHS, FoundRHS, CtxI))
11783 isImpliedCondOperands(Pred, LHS, RHS,
getNotSCEV(FoundLHS),
11792 assert(P1 != P2 &&
"Handled earlier!");
11796 if (IsSignFlippedPredicate(Pred, FoundPred)) {
11801 return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS, CtxI);
11805 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
11806 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
11811 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
11822 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
11823 CanonicalRHS, CanonicalFoundLHS,
11824 CanonicalFoundRHS);
11829 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
11830 CanonicalRHS, CanonicalFoundLHS,
11831 CanonicalFoundRHS);
11836 (isa<SCEVConstant>(FoundLHS) || isa<SCEVConstant>(FoundRHS))) {
11839 const SCEV *
V =
nullptr;
11841 if (isa<SCEVConstant>(FoundLHS)) {
11842 C = cast<SCEVConstant>(FoundLHS);
11845 C = cast<SCEVConstant>(FoundRHS);
11857 if (Min ==
C->getAPInt()) {
11862 APInt SharperMin = Min + 1;
11869 if (isImpliedCondOperands(Pred, LHS, RHS, V,
getConstant(SharperMin),
11885 if (isImpliedCondOperands(Pred, LHS, RHS, V,
getConstant(Min), CtxI))
11914 if (isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS, CtxI))
11918 if (isImpliedCondOperands(FoundPred, LHS, RHS, FoundLHS, FoundRHS, CtxI))
11921 if (isImpliedCondOperandsViaRanges(Pred, LHS, RHS, FoundPred, FoundLHS, FoundRHS))
11928bool ScalarEvolution::splitBinaryAdd(
const SCEV *Expr,
11931 const auto *AE = dyn_cast<SCEVAddExpr>(Expr);
11932 if (!AE || AE->getNumOperands() != 2)
11935 L = AE->getOperand(0);
11936 R = AE->getOperand(1);
11937 Flags = AE->getNoWrapFlags();
11941std::optional<APInt>
11950 if (isa<SCEVAddRecExpr>(
Less) && isa<SCEVAddRecExpr>(More)) {
11951 const auto *LAR = cast<SCEVAddRecExpr>(
Less);
11952 const auto *MAR = cast<SCEVAddRecExpr>(More);
11954 if (LAR->getLoop() != MAR->getLoop())
11955 return std::nullopt;
11959 if (!LAR->isAffine() || !MAR->isAffine())
11960 return std::nullopt;
11962 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
11963 return std::nullopt;
11965 Less = LAR->getStart();
11966 More = MAR->getStart();
11971 if (isa<SCEVConstant>(
Less) && isa<SCEVConstant>(More)) {
11972 const auto &M = cast<SCEVConstant>(More)->getAPInt();
11973 const auto &L = cast<SCEVConstant>(
Less)->getAPInt();
11978 const SCEV *LLess =
nullptr, *RLess =
nullptr;
11979 const SCEV *LMore =
nullptr, *RMore =
nullptr;
11982 if (splitBinaryAdd(
Less, LLess, RLess, Flags))
11983 if ((C1 = dyn_cast<SCEVConstant>(LLess)))
11988 if (splitBinaryAdd(More, LMore, RMore, Flags))
11989 if ((C2 = dyn_cast<SCEVConstant>(LMore)))
11991 return C2->getAPInt();
11994 if (C1 && C2 && RLess == RMore)
11995 return C2->getAPInt() - C1->
getAPInt();
11997 return std::nullopt;
12000bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12020 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(FoundLHS)) {
12024 if (!L->contains(ContextBB) || !DT.
dominates(ContextBB, L->getLoopLatch()))
12028 return isImpliedCondOperands(Pred, LHS, RHS, AR->
getStart(), FoundRHS);
12031 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(FoundRHS)) {
12035 if (!L->contains(ContextBB) || !DT.
dominates(ContextBB, L->getLoopLatch()))
12039 return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, AR->
getStart());
12045bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(
12047 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
12051 const auto *AddRecLHS = dyn_cast<SCEVAddRecExpr>(LHS);
12055 const auto *AddRecFoundLHS = dyn_cast<SCEVAddRecExpr>(FoundLHS);
12056 if (!AddRecFoundLHS)
12063 const Loop *
L = AddRecFoundLHS->getLoop();
12064 if (L != AddRecLHS->getLoop())
12101 if (!LDiff || !RDiff || *LDiff != *RDiff)
12104 if (LDiff->isMinValue())
12107 APInt FoundRHSLimit;
12110 FoundRHSLimit = -(*RDiff);
12124 const SCEV *FoundLHS,
12125 const SCEV *FoundRHS,
unsigned Depth) {
12126 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12130 bool Erased = PendingMerges.erase(LPhi);
12131 assert(Erased &&
"Failed to erase LPhi!");
12135 bool Erased = PendingMerges.erase(RPhi);
12136 assert(Erased &&
"Failed to erase RPhi!");
12142 if (
const SCEVUnknown *LU = dyn_cast<SCEVUnknown>(LHS))
12143 if (
auto *Phi = dyn_cast<PHINode>(LU->getValue())) {
12144 if (!PendingMerges.insert(Phi).second)
12148 if (
const SCEVUnknown *RU = dyn_cast<SCEVUnknown>(RHS))
12149 if (
auto *Phi = dyn_cast<PHINode>(RU->getValue())) {
12158 if (!PendingMerges.insert(Phi).second)
12164 if (!LPhi && !RPhi)
12175 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12179 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12180 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12181 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12182 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12185 if (RPhi && RPhi->getParent() == LBB) {
12192 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12193 if (!ProvedEasily(L, R))
12204 auto *RLoop = RAR->
getLoop();
12205 auto *Predecessor = RLoop->getLoopPredecessor();
12206 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12208 if (!ProvedEasily(L1, RAR->
getStart()))
12210 auto *Latch = RLoop->getLoopLatch();
12211 assert(Latch &&
"Loop with AddRec with no latch?");
12229 if (!ProvedEasily(L, RHS))
12239 const SCEV *FoundLHS,
12240 const SCEV *FoundRHS) {
12243 if (RHS == FoundRHS) {
12248 if (LHS != FoundLHS)
12251 auto *SUFoundRHS = dyn_cast<SCEVUnknown>(FoundRHS);
12255 Value *Shiftee, *ShiftValue;
12257 using namespace PatternMatch;
12258 if (
match(SUFoundRHS->getValue(),
12260 auto *ShifteeS =
getSCEV(Shiftee);
12280 const SCEV *FoundLHS,
12281 const SCEV *FoundRHS,
12283 if (isImpliedCondOperandsViaRanges(Pred, LHS, RHS, Pred, FoundLHS, FoundRHS))
12286 if (isImpliedCondOperandsViaNoOverflow(Pred, LHS, RHS, FoundLHS, FoundRHS))
12289 if (isImpliedCondOperandsViaShift(Pred, LHS, RHS, FoundLHS, FoundRHS))
12292 if (isImpliedCondOperandsViaAddRecStart(Pred, LHS, RHS, FoundLHS, FoundRHS,
12296 return isImpliedCondOperandsHelper(Pred, LHS, RHS,
12297 FoundLHS, FoundRHS);
12301template <
typename MinMaxExprType>
12303 const SCEV *Candidate) {
12304 const MinMaxExprType *MinMaxExpr = dyn_cast<MinMaxExprType>(MaybeMinMaxExpr);
12308 return is_contained(MinMaxExpr->operands(), Candidate);
12313 const SCEV *LHS,
const SCEV *RHS) {
12347 const SCEV *LHS,
const SCEV *RHS) {
12358 IsMinMaxConsistingOf<SCEVSMinExpr>(
LHS,
RHS) ||
12360 IsMinMaxConsistingOf<SCEVSMaxExpr>(
RHS,
LHS);
12369 IsMinMaxConsistingOf<SCEVUMinExpr>(
LHS,
RHS) ||
12371 IsMinMaxConsistingOf<SCEVUMaxExpr>(
RHS,
LHS);
12379 const SCEV *FoundLHS,
12380 const SCEV *FoundRHS,
12384 "LHS and RHS have different sizes?");
12387 "FoundLHS and FoundRHS have different sizes?");
12419 auto GetOpFromSExt = [&](
const SCEV *S) {
12420 if (
auto *Ext = dyn_cast<SCEVSignExtendExpr>(S))
12421 return Ext->getOperand();
12428 auto *OrigLHS =
LHS;
12429 auto *OrigFoundLHS = FoundLHS;
12430 LHS = GetOpFromSExt(LHS);
12431 FoundLHS = GetOpFromSExt(FoundLHS);
12434 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
12437 FoundRHS,
Depth + 1);
12440 if (
auto *LHSAddExpr = dyn_cast<SCEVAddExpr>(LHS)) {
12450 if (!LHSAddExpr->hasNoSignedWrap())
12453 auto *LL = LHSAddExpr->getOperand(0);
12454 auto *LR = LHSAddExpr->getOperand(1);
12458 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
12459 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2, RHS);
12464 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
12466 }
else if (
auto *LHSUnknownExpr = dyn_cast<SCEVUnknown>(LHS)) {
12481 if (!isa<ConstantInt>(LR))
12484 auto *Denominator = cast<SCEVConstant>(
getSCEV(LR));
12489 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
12497 auto *DTy = Denominator->getType();
12498 auto *FRHSTy = FoundRHS->
getType();
12499 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
12518 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
12529 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
12531 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
12539 if (isImpliedViaMerge(Pred, OrigLHS, RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
12546 const SCEV *LHS,
const SCEV *RHS) {
12579 const SCEV *LHS,
const SCEV *RHS) {
12581 isKnownPredicateViaConstantRanges(Pred, LHS, RHS) ||
12584 isKnownPredicateViaNoOverflow(Pred, LHS, RHS);
12590 const SCEV *FoundLHS,
12591 const SCEV *FoundRHS) {
12626 if (isImpliedViaOperations(Pred, LHS, RHS, FoundLHS, FoundRHS))
12636 const SCEV *FoundLHS,
12637 const SCEV *FoundRHS) {
12638 if (!isa<SCEVConstant>(RHS) || !isa<SCEVConstant>(FoundRHS))
12647 const APInt &ConstFoundRHS = cast<SCEVConstant>(FoundRHS)->getAPInt();
12659 const APInt &ConstRHS = cast<SCEVConstant>(RHS)->getAPInt();
12662 return LHSRange.
icmp(Pred, ConstRHS);
12665bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *RHS,
const SCEV *Stride,
12678 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
12686 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
12689bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *RHS,
const SCEV *Stride,
12701 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
12709 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
12721const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
12722 const SCEV *Stride,
12749 : APIntOps::umax(One, MinStride);
12753 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
12764 : APIntOps::umax(MaxEnd, MinStart);
12771ScalarEvolution::howManyLessThans(
const SCEV *LHS,
const SCEV *RHS,
12772 const Loop *L,
bool IsSigned,
12773 bool ControlsOnlyExit,
bool AllowPredicates) {
12777 bool PredicatedIV =
false;
12798 if (!StrideC || !StrideC->getAPInt().isPowerOf2())
12808 if (
auto *ZExt = dyn_cast<SCEVZeroExtendExpr>(LHS)) {
12809 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(ZExt->getOperand());
12811 auto canProveNUW = [&]() {
12814 if (!ControlsOnlyExit)
12835 Limit = Limit.
zext(OuterBitWidth);
12847 Type *Ty = ZExt->getType();
12849 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this, 0),
12851 IV = dyn_cast<SCEVAddRecExpr>(S);
12858 if (!
IV && AllowPredicates) {
12863 PredicatedIV =
true;
12867 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
12881 bool NoWrap = ControlsOnlyExit &&
IV->getNoWrapFlags(WrapType);
12884 const SCEV *Stride =
IV->getStepRecurrence(*
this);
12889 if (!PositiveStride) {
12941 auto wouldZeroStrideBeUB = [&]() {
12953 if (!wouldZeroStrideBeUB()) {
12957 }
else if (!Stride->
isOne() && !NoWrap) {
12958 auto isUBOnWrap = [&]() {
12964 return canAssumeNoSelfWrap(
IV);
12971 if (canIVOverflowOnLT(RHS, Stride, IsSigned) && !isUBOnWrap())
12984 const SCEV *Start =
IV->getStart();
12990 const SCEV *OrigStart = Start;
12992 if (Start->getType()->isPointerTy()) {
12994 if (isa<SCEVCouldNotCompute>(Start))
12999 if (isa<SCEVCouldNotCompute>(RHS))
13003 const SCEV *
End =
nullptr, *BECount =
nullptr,
13004 *BECountIfBackedgeTaken =
nullptr;
13006 const auto *RHSAddRec = dyn_cast<SCEVAddRecExpr>(RHS);
13007 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13008 RHSAddRec->getNoWrapFlags()) {
13021 const SCEV *RHSStart = RHSAddRec->getStart();
13022 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13043 BECountIfBackedgeTaken =
13048 if (BECount ==
nullptr) {
13053 const SCEV *MaxBECount = computeMaxBECountForLT(
13056 MaxBECount,
false , Predicates);
13063 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13090 const SCEV *Numerator =
13096 auto canProveRHSGreaterThanEqualStart = [&]() {
13115 auto *StartMinusOne =
13122 if (canProveRHSGreaterThanEqualStart()) {
13137 BECountIfBackedgeTaken =
13153 bool MayAddOverflow = [&] {
13154 if (
auto *StrideC = dyn_cast<SCEVConstant>(Stride)) {
13155 if (StrideC->getAPInt().isPowerOf2()) {
13201 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13215 if (!MayAddOverflow) {
13227 const SCEV *ConstantMaxBECount;
13228 bool MaxOrZero =
false;
13229 if (isa<SCEVConstant>(BECount)) {
13230 ConstantMaxBECount = BECount;
13231 }
else if (BECountIfBackedgeTaken &&
13232 isa<SCEVConstant>(BECountIfBackedgeTaken)) {
13236 ConstantMaxBECount = BECountIfBackedgeTaken;
13239 ConstantMaxBECount = computeMaxBECountForLT(
13243 if (isa<SCEVCouldNotCompute>(ConstantMaxBECount) &&
13244 !isa<SCEVCouldNotCompute>(BECount))
13247 const SCEV *SymbolicMaxBECount =
13248 isa<SCEVCouldNotCompute>(BECount) ? ConstantMaxBECount : BECount;
13249 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13254 const SCEV *LHS,
const SCEV *RHS,
const Loop *L,
bool IsSigned,
13255 bool ControlsOnlyExit,
bool AllowPredicates) {
13262 if (!
IV && AllowPredicates)
13269 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13273 bool NoWrap = ControlsOnlyExit &&
IV->getNoWrapFlags(WrapType);
13286 if (!Stride->
isOne() && !NoWrap)
13287 if (canIVOverflowOnGT(RHS, Stride, IsSigned))
13290 const SCEV *Start =
IV->getStart();
13302 if (Start->getType()->isPointerTy()) {
13304 if (isa<SCEVCouldNotCompute>(Start))
13307 if (
End->getType()->isPointerTy()) {
13309 if (isa<SCEVCouldNotCompute>(
End))
13337 const SCEV *ConstantMaxBECount =
13338 isa<SCEVConstant>(BECount)
13343 if (isa<SCEVCouldNotCompute>(ConstantMaxBECount))
13344 ConstantMaxBECount = BECount;
13345 const SCEV *SymbolicMaxBECount =
13346 isa<SCEVCouldNotCompute>(BECount) ? ConstantMaxBECount : BECount;
13348 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13358 if (
const SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart()))
13359 if (!SC->getValue()->isZero()) {
13363 getNoWrapFlags(FlagNW));
13364 if (
const auto *ShiftedAddRec = dyn_cast<SCEVAddRecExpr>(Shifted))
13365 return ShiftedAddRec->getNumIterationsInRange(
13373 if (
any_of(operands(), [](
const SCEV *
Op) {
return !isa<SCEVConstant>(
Op); }))
13393 APInt A = cast<SCEVConstant>(getOperand(1))->getAPInt();
13411 "Linear scev computation is off in a bad way!");
13415 if (isQuadratic()) {
13425 assert(getNumOperands() > 1 &&
"AddRec with zero step?");
13435 for (
unsigned i = 0, e = getNumOperands() - 1; i < e; ++i)
13441 const SCEV *
Last = getOperand(getNumOperands() - 1);
13442 assert(!
Last->isZero() &&
"Recurrency with zero step?");
13444 return cast<SCEVAddRecExpr>(SE.
getAddRecExpr(Ops, getLoop(),
13451 if (
const auto *SU = dyn_cast<SCEVUnknown>(S))
13452 return isa<UndefValue>(SU->
getValue());
13460 if (
const auto *SU = dyn_cast<SCEVUnknown>(S))
13469 if (
StoreInst *Store = dyn_cast<StoreInst>(Inst))
13470 Ty = Store->getValueOperand()->getType();
13471 else if (
LoadInst *Load = dyn_cast<LoadInst>(Inst))
13472 Ty = Load->getType();
13484void ScalarEvolution::SCEVCallbackVH::deleted() {
13485 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13486 if (
PHINode *PN = dyn_cast<PHINode>(getValPtr()))
13487 SE->ConstantEvolutionLoopExitValue.erase(PN);
13488 SE->eraseValueFromMap(getValPtr());
13492void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
13493 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13512 :
F(
F),
DL(
F.getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
13514 LoopDispositions(64), BlockDispositions(64) {
13525 auto *GuardDecl =
F.getParent()->getFunction(
13527 HasGuards = GuardDecl && !GuardDecl->use_empty();
13531 :
F(Arg.
F),
DL(Arg.
DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
13532 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
13533 ValueExprMap(
std::
move(Arg.ValueExprMap)),
13534 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
13535 PendingPhiRanges(
std::
move(Arg.PendingPhiRanges)),
13536 PendingMerges(
std::
move(Arg.PendingMerges)),
13537 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
13538 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
13539 PredicatedBackedgeTakenCounts(
13540 std::
move(Arg.PredicatedBackedgeTakenCounts)),
13541 BECountUsers(
std::
move(Arg.BECountUsers)),
13542 ConstantEvolutionLoopExitValue(
13543 std::
move(Arg.ConstantEvolutionLoopExitValue)),
13544 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
13545 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
13546 LoopDispositions(
std::
move(Arg.LoopDispositions)),
13547 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
13548 BlockDispositions(
std::
move(Arg.BlockDispositions)),
13549 SCEVUsers(
std::
move(Arg.SCEVUsers)),
13550 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
13551 SignedRanges(
std::
move(Arg.SignedRanges)),
13552 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
13553 UniquePreds(
std::
move(Arg.UniquePreds)),
13554 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
13555 LoopUsers(
std::
move(Arg.LoopUsers)),
13556 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
13557 FirstUnknown(Arg.FirstUnknown) {
13558 Arg.FirstUnknown =
nullptr;
13567 Tmp->~SCEVUnknown();
13569 FirstUnknown =
nullptr;
13571 ExprValueMap.
clear();
13572 ValueExprMap.
clear();
13574 BackedgeTakenCounts.clear();
13575 PredicatedBackedgeTakenCounts.clear();
13577 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
13578 assert(PendingPhiRanges.empty() &&
"getRangeRef garbage");
13579 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
13580 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
13581 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
13591 if (isa<SCEVConstant>(S))
13603 L->getHeader()->printAsOperand(
OS,
false);
13607 L->getExitingBlocks(ExitingBlocks);
13608 if (ExitingBlocks.
size() != 1)
13609 OS <<
"<multiple exits> ";
13612 if (!isa<SCEVCouldNotCompute>(BTC)) {
13613 OS <<
"backedge-taken count is ";
13616 OS <<
"Unpredictable backedge-taken count.";
13619 if (ExitingBlocks.
size() > 1)
13620 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
13621 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
13627 L->getHeader()->printAsOperand(
OS,
false);
13631 if (!isa<SCEVCouldNotCompute>(ConstantBTC)) {
13632 OS <<
"constant max backedge-taken count is ";
13635 OS <<
", actual taken count either this or zero.";
13637 OS <<
"Unpredictable constant max backedge-taken count. ";
13642 L->getHeader()->printAsOperand(
OS,
false);
13646 if (!isa<SCEVCouldNotCompute>(SymbolicBTC)) {
13647 OS <<
"symbolic max backedge-taken count is ";
13650 OS <<
", actual taken count either this or zero.";
13652 OS <<
"Unpredictable symbolic max backedge-taken count. ";
13656 if (ExitingBlocks.
size() > 1)
13657 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
13658 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
13667 if (PBT != BTC || !Preds.
empty()) {
13669 L->getHeader()->printAsOperand(
OS,
false);
13671 if (!isa<SCEVCouldNotCompute>(PBT)) {
13672 OS <<
"Predicated backedge-taken count is ";
13675 OS <<
"Unpredictable predicated backedge-taken count.";
13677 OS <<
" Predicates:\n";
13678 for (
const auto *
P : Preds)
13683 auto *PredSymbolicMax =
13685 if (SymbolicBTC != PredSymbolicMax) {
13687 L->getHeader()->printAsOperand(
OS,
false);
13689 if (!isa<SCEVCouldNotCompute>(PredSymbolicMax)) {
13690 OS <<
"Predicated symbolic max backedge-taken count is ";
13693 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
13695 OS <<
" Predicates:\n";
13696 for (
const auto *
P : Preds)
13702 L->getHeader()->printAsOperand(
OS,
false);
13718 OS <<
"Computable";
13727 OS <<
"DoesNotDominate";
13733 OS <<
"ProperlyDominates";
13750 OS <<
"Classifying expressions for: ";
13759 if (!isa<SCEVCouldNotCompute>(SV)) {
13772 if (!isa<SCEVCouldNotCompute>(AtUse)) {
13781 OS <<
"\t\t" "Exits: ";
13784 OS <<
"<<Unknown>>";
13790 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
13792 OS <<
"\t\t" "LoopDispositions: { ";
13798 Iter->getHeader()->printAsOperand(
OS,
false);
13806 OS <<
"\t\t" "LoopDispositions: { ";
13812 InnerL->getHeader()->printAsOperand(
OS,
false);
13823 OS <<
"Determining loop execution counts for: ";
13832 auto &Values = LoopDispositions[S];
13833 for (
auto &V : Values) {
13834 if (V.getPointer() == L)
13839 auto &Values2 = LoopDispositions[S];
13841 if (V.getPointer() == L) {
13850ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
13869 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
13870 " dominate the contained loop's header?");
13897 bool HasVarying =
false;
13912 if (
auto *
I = dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue()))
13931 auto &Values = BlockDispositions[S];
13932 for (
auto &V : Values) {
13933 if (V.getPointer() == BB)
13938 auto &Values2 = BlockDispositions[S];
13940 if (V.getPointer() == BB) {
13949ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
13978 bool Proper =
true;
13990 dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue())) {
13991 if (
I->getParent() == BB)
14016void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14019 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14020 auto It = BECounts.find(L);
14021 if (It != BECounts.end()) {
14022 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14023 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14024 if (!isa<SCEVConstant>(S)) {
14025 auto UserIt = BECountUsers.find(S);
14026 assert(UserIt != BECountUsers.end());
14027 UserIt->second.erase({L, Predicated});
14031 BECounts.erase(It);
14039 while (!Worklist.
empty()) {
14041 auto Users = SCEVUsers.find(Curr);
14042 if (
Users != SCEVUsers.end())
14048 for (
const auto *S : ToForget)
14049 forgetMemoizedResultsImpl(S);
14051 for (
auto I = PredicatedSCEVRewrites.begin();
14052 I != PredicatedSCEVRewrites.end();) {
14053 std::pair<const SCEV *, const Loop *>
Entry =
I->first;
14054 if (ToForget.count(
Entry.first))
14055 PredicatedSCEVRewrites.erase(
I++);
14061void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14062 LoopDispositions.erase(S);
14063 BlockDispositions.erase(S);
14064 UnsignedRanges.erase(S);
14065 SignedRanges.erase(S);
14066 HasRecMap.
erase(S);
14067 ConstantMultipleCache.erase(S);
14069 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(S)) {
14070 UnsignedWrapViaInductionTried.erase(AR);
14071 SignedWrapViaInductionTried.erase(AR);
14074 auto ExprIt = ExprValueMap.
find(S);
14075 if (ExprIt != ExprValueMap.
end()) {
14076 for (
Value *V : ExprIt->second) {
14077 auto ValueIt = ValueExprMap.
find_as(V);
14078 if (ValueIt != ValueExprMap.
end())
14079 ValueExprMap.
erase(ValueIt);
14081 ExprValueMap.
erase(ExprIt);
14084 auto ScopeIt = ValuesAtScopes.find(S);
14085 if (ScopeIt != ValuesAtScopes.end()) {
14086 for (
const auto &Pair : ScopeIt->second)
14087 if (!isa_and_nonnull<SCEVConstant>(Pair.second))
14089 std::make_pair(Pair.first, S));
14090 ValuesAtScopes.erase(ScopeIt);
14093 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14094 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14095 for (
const auto &Pair : ScopeUserIt->second)
14096 llvm::erase(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
14097 ValuesAtScopesUsers.erase(ScopeUserIt);
14100 auto BEUsersIt = BECountUsers.find(S);
14101 if (BEUsersIt != BECountUsers.end()) {
14103 auto Copy = BEUsersIt->second;
14104 for (
const auto &Pair : Copy)
14105 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14106 BECountUsers.erase(BEUsersIt);
14109 auto FoldUser = FoldCacheUser.find(S);
14110 if (FoldUser != FoldCacheUser.end())
14111 for (
auto &KV : FoldUser->second)
14112 FoldCache.erase(KV);
14113 FoldCacheUser.erase(S);
14117ScalarEvolution::getUsedLoops(
const SCEV *S,
14119 struct FindUsedLoops {
14121 : LoopsUsed(LoopsUsed) {}
14123 bool follow(
const SCEV *S) {
14124 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(S))
14129 bool isDone()
const {
return false; }
14132 FindUsedLoops F(LoopsUsed);
14136void ScalarEvolution::getReachableBlocks(
14140 while (!Worklist.
empty()) {
14142 if (!Reachable.
insert(BB).second)
14149 if (
auto *
C = dyn_cast<ConstantInt>(
Cond)) {
14150 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14154 if (
auto *Cmp = dyn_cast<ICmpInst>(
Cond)) {
14157 if (isKnownPredicateViaConstantRanges(
Cmp->getPredicate(), L, R)) {
14161 if (isKnownPredicateViaConstantRanges(
Cmp->getInversePredicate(), L,
14196 SCEVMapper SCM(SE2);
14198 SE2.getReachableBlocks(ReachableBlocks,
F);
14200 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14218 while (!LoopStack.
empty()) {
14224 if (!ReachableBlocks.
contains(L->getHeader()))
14229 auto It = BackedgeTakenCounts.find(L);
14230 if (It == BackedgeTakenCounts.end())
14234 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14254 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14255 if (Delta && !Delta->
isZero()) {
14256 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14257 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14258 dbgs() <<
"New: " << *NewBECount <<
"\n";
14259 dbgs() <<
"Delta: " << *Delta <<
"\n";
14267 while (!Worklist.
empty()) {
14269 if (ValidLoops.
insert(L).second)
14270 Worklist.
append(L->begin(), L->end());
14272 for (
const auto &KV : ValueExprMap) {
14275 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(KV.second)) {
14277 "AddRec references invalid loop");
14282 auto It = ExprValueMap.
find(KV.second);
14283 if (It == ExprValueMap.
end() || !It->second.contains(KV.first)) {
14284 dbgs() <<
"Value " << *KV.first
14285 <<
" is in ValueExprMap but not in ExprValueMap\n";
14289 if (
auto *
I = dyn_cast<Instruction>(&*KV.first)) {
14290 if (!ReachableBlocks.
contains(
I->getParent()))
14292 const SCEV *OldSCEV = SCM.visit(KV.second);
14294 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14295 if (Delta && !Delta->
isZero()) {
14296 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14297 <<
"Old: " << *OldSCEV <<
"\n"
14298 <<
"New: " << *NewSCEV <<
"\n"
14299 <<
"Delta: " << *Delta <<
"\n";
14305 for (
const auto &KV : ExprValueMap) {
14306 for (
Value *V : KV.second) {
14307 auto It = ValueExprMap.find_as(V);
14308 if (It == ValueExprMap.end()) {
14309 dbgs() <<
"Value " << *V
14310 <<
" is in ExprValueMap but not in ValueExprMap\n";
14313 if (It->second != KV.first) {
14314 dbgs() <<
"Value " << *V <<
" mapped to " << *It->second
14315 <<
" rather than " << *KV.first <<
"\n";
14322 for (
const auto &S : UniqueSCEVs) {
14325 if (isa<SCEVConstant>(
Op))
14327 auto It = SCEVUsers.find(
Op);
14328 if (It != SCEVUsers.end() && It->second.count(&S))
14330 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14331 <<
" is not being tracked!\n";
14337 for (
const auto &ValueAndVec : ValuesAtScopes) {
14339 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14340 const Loop *L = LoopAndValueAtScope.first;
14341 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
14342 if (!isa<SCEVConstant>(ValueAtScope)) {
14343 auto It = ValuesAtScopesUsers.find(ValueAtScope);
14344 if (It != ValuesAtScopesUsers.end() &&
14347 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14348 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14354 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14355 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14356 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14357 const Loop *L = LoopAndValue.first;
14358 const SCEV *
Value = LoopAndValue.second;
14360 auto It = ValuesAtScopes.find(
Value);
14361 if (It != ValuesAtScopes.end() &&
14362 is_contained(It->second, std::make_pair(L, ValueAtScope)))
14364 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14365 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14371 auto VerifyBECountUsers = [&](
bool Predicated) {
14373 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14374 for (
const auto &LoopAndBEInfo : BECounts) {
14375 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14376 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14377 if (!isa<SCEVConstant>(S)) {
14378 auto UserIt = BECountUsers.find(S);
14379 if (UserIt != BECountUsers.end() &&
14380 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14382 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14383 <<
" missing from BECountUsers\n";
14390 VerifyBECountUsers(
false);
14391 VerifyBECountUsers(
true);
14394 for (
auto &[S, Values] : LoopDispositions) {
14395 for (
auto [
Loop, CachedDisposition] : Values) {
14397 if (CachedDisposition != RecomputedDisposition) {
14398 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
14399 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
14400 << RecomputedDisposition <<
"\n";
14407 for (
auto &[S, Values] : BlockDispositions) {
14408 for (
auto [BB, CachedDisposition] : Values) {
14410 if (CachedDisposition != RecomputedDisposition) {
14411 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
14412 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
14413 <<
", actual " << RecomputedDisposition <<
"\n";
14420 for (
auto [
FoldID, Expr] : FoldCache) {
14421 auto I = FoldCacheUser.find(Expr);
14422 if (
I == FoldCacheUser.end()) {
14423 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
14428 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
14432 for (
auto [Expr, IDs] : FoldCacheUser) {
14433 for (
auto &
FoldID : IDs) {
14434 auto I = FoldCache.find(
FoldID);
14435 if (
I == FoldCache.end()) {
14436 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
14440 if (
I->second != Expr) {
14441 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: "
14442 << *
I->second <<
" != " << *Expr <<
"!\n";
14453 for (
auto [S, Multiple] : ConstantMultipleCache) {
14455 if ((Multiple != 0 && RecomputedMultiple != 0 &&
14456 Multiple.
urem(RecomputedMultiple) != 0 &&
14457 RecomputedMultiple.
urem(Multiple) != 0)) {
14458 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
14459 << *S <<
" : Computed " << RecomputedMultiple
14460 <<
" but cache contains " << Multiple <<
"!\n";
14500 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
14501 <<
F.getName() <<
"':\n";
14507 "Scalar Evolution Analysis",
false,
true)
14523 F, getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F),
14524 getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F),
14525 getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
14526 getAnalysis<LoopInfoWrapperPass>().getLoopInfo()));
14558 const SCEV *LHS,
const SCEV *RHS) {
14561 "Type mismatch between LHS and RHS");
14564 ID.AddInteger(Pred);
14565 ID.AddPointer(
LHS);
14566 ID.AddPointer(
RHS);
14567 void *IP =
nullptr;
14568 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
14572 UniquePreds.InsertNode(Eq, IP);
14583 ID.AddInteger(AddedFlags);
14584 void *IP =
nullptr;
14585 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
14587 auto *OF =
new (SCEVAllocator)
14589 UniquePreds.InsertNode(OF, IP);
14609 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
14615 if (
auto *U = dyn_cast<SCEVUnionPredicate>(Pred)) {
14616 for (
const auto *Pred : U->getPredicates())
14617 if (
const auto *IPred = dyn_cast<SCEVComparePredicate>(Pred))
14618 if (IPred->getLHS() == Expr &&
14619 IPred->getPredicate() == ICmpInst::ICMP_EQ)
14620 return IPred->getRHS();
14621 }
else if (
const auto *IPred = dyn_cast<SCEVComparePredicate>(Pred)) {
14622 if (IPred->getLHS() == Expr &&
14623 IPred->getPredicate() == ICmpInst::ICMP_EQ)
14624 return IPred->getRHS();
14627 return convertToAddRecWithPreds(Expr);
14680 return addOverflowAssumption(
A);
14690 if (!isa<PHINode>(Expr->
getValue()))
14693 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
14695 if (!PredicatedRewrite)
14697 for (
const auto *
P : PredicatedRewrite->second){
14699 if (
auto *WP = dyn_cast<const SCEVWrapPredicate>(
P)) {
14700 if (L != WP->getExpr()->getLoop())
14703 if (!addOverflowAssumption(
P))
14706 return PredicatedRewrite->first;
14719 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
14726 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
14727 auto *AddRec = dyn_cast<SCEVAddRecExpr>(S);
14734 for (
const auto *
P : TransformPreds)
14743 : FastID(
ID), Kind(Kind) {}
14750 assert(
LHS !=
RHS &&
"LHS and RHS are the same SCEV");
14754 const auto *
Op = dyn_cast<SCEVComparePredicate>(
N);
14784 const auto *
Op = dyn_cast<SCEVWrapPredicate>(
N);
14786 return Op &&
Op->AR == AR &&
setFlags(Flags,
Op->Flags) == Flags;
14822 if (Step->getValue()->getValue().isNonNegative())
14826 return ImpliedFlags;
14832 for (
const auto *
P : Preds)
14842 if (
const auto *Set = dyn_cast<SCEVUnionPredicate>(
N))
14843 return all_of(Set->Preds,
14851 for (
const auto *Pred : Preds)
14856 if (
const auto *Set = dyn_cast<SCEVUnionPredicate>(
N)) {
14857 for (
const auto *Pred : Set->Preds)
14871 Preds = std::make_unique<SCEVUnionPredicate>(
Empty);
14876 for (
const auto *
Op : Ops)
14880 if (!isa<SCEVConstant>(
Op))
14881 SCEVUsers[
Op].insert(
User);
14886 RewriteEntry &Entry = RewriteMap[Expr];
14889 if (Entry.second && Generation == Entry.first)
14890 return Entry.second;
14895 Expr = Entry.second;
14898 Entry = {Generation, NewSCEV};
14904 if (!BackedgeCount) {
14907 for (
const auto *
P : Preds)
14910 return BackedgeCount;
14914 if (!SymbolicMaxBackedgeCount) {
14916 SymbolicMaxBackedgeCount =
14918 for (
const auto *
P : Preds)
14921 return SymbolicMaxBackedgeCount;
14925 if (Preds->implies(&Pred))
14928 auto &OldPreds = Preds->getPredicates();
14931 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds);
14932 updateGeneration();
14939void PredicatedScalarEvolution::updateGeneration() {
14941 if (++Generation == 0) {
14942 for (
auto &
II : RewriteMap) {
14943 const SCEV *Rewritten =
II.second.second;
14952 const auto *AR = cast<SCEVAddRecExpr>(Expr);
14960 auto II = FlagsMap.insert({V, Flags});
14968 const auto *AR = cast<SCEVAddRecExpr>(Expr);
14973 auto II = FlagsMap.find(V);
14975 if (
II != FlagsMap.end())
14989 for (
const auto *
P : NewPreds)
14992 RewriteMap[SE.
getSCEV(V)] = {Generation, New};
14998 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15000 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {
15001 for (
auto I :
Init.FlagsMap)
15002 FlagsMap.insert(
I);
15007 for (
auto *BB : L.getBlocks())
15008 for (
auto &
I : *BB) {
15013 auto II = RewriteMap.find(Expr);
15015 if (
II == RewriteMap.end())
15019 if (
II->second.second == Expr)
15033bool ScalarEvolution::matchURem(
const SCEV *Expr,
const SCEV *&LHS,
15034 const SCEV *&RHS) {
15041 if (
const auto *ZExt = dyn_cast<SCEVZeroExtendExpr>(Expr))
15042 if (
const auto *Trunc = dyn_cast<SCEVTruncateExpr>(ZExt->getOperand(0))) {
15043 LHS = Trunc->getOperand();
15055 const auto *
Add = dyn_cast<SCEVAddExpr>(Expr);
15056 if (
Add ==
nullptr ||
Add->getNumOperands() != 2)
15059 const SCEV *
A =
Add->getOperand(1);
15060 const auto *
Mul = dyn_cast<SCEVMulExpr>(
Add->getOperand(0));
15062 if (
Mul ==
nullptr)
15065 const auto MatchURemWithDivisor = [&](
const SCEV *
B) {
15076 if (
Mul->getNumOperands() == 3 && isa<SCEVConstant>(
Mul->getOperand(0)))
15077 return MatchURemWithDivisor(
Mul->getOperand(1)) ||
15078 MatchURemWithDivisor(
Mul->getOperand(2));
15081 if (
Mul->getNumOperands() == 2)
15082 return MatchURemWithDivisor(
Mul->getOperand(1)) ||
15083 MatchURemWithDivisor(
Mul->getOperand(0)) ||
15100 bool PreserveNUW,
bool PreserveNSW)
15111 auto I = Map.find(Expr);
15112 if (
I == Map.end())
15118 auto I = Map.find(Expr);
15119 if (
I == Map.end()) {
15125 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
15126 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
15129 auto I = Map.find(NarrowExt);
15130 if (
I != Map.end())
15132 Bitwidth = Bitwidth / 2;
15142 auto I = Map.find(Expr);
15143 if (
I == Map.end())
15150 auto I = Map.find(Expr);
15151 if (
I == Map.end())
15157 auto I = Map.find(Expr);
15158 if (
I == Map.end())
15165 bool Changed =
false;
15180 bool Changed =
false;
15206 if (isa<SCEVConstant>(
LHS)) {
15214 auto MatchRangeCheckIdiom = [
this, Predicate,
LHS,
RHS, &RewriteMap,
15215 &ExprsToRewrite]() {
15216 auto *AddExpr = dyn_cast<SCEVAddExpr>(
LHS);
15217 if (!AddExpr || AddExpr->getNumOperands() != 2)
15220 auto *C1 = dyn_cast<SCEVConstant>(AddExpr->getOperand(0));
15221 auto *LHSUnknown = dyn_cast<SCEVUnknown>(AddExpr->getOperand(1));
15222 auto *C2 = dyn_cast<SCEVConstant>(
RHS);
15223 if (!C1 || !C2 || !LHSUnknown)
15228 .
sub(C1->getAPInt());
15231 if (ExactRegion.isWrappedSet() || ExactRegion.isFullSet())
15233 auto I = RewriteMap.find(LHSUnknown);
15234 const SCEV *RewrittenLHS =
I != RewriteMap.end() ?
I->second : LHSUnknown;
15241 if (MatchRangeCheckIdiom())
15247 auto IsMinMaxSCEVWithNonNegativeConstant =
15250 if (
auto *
MinMax = dyn_cast<SCEVMinMaxExpr>(Expr)) {
15251 if (
MinMax->getNumOperands() != 2)
15253 if (
auto *
C = dyn_cast<SCEVConstant>(
MinMax->getOperand(0))) {
15254 if (
C->getAPInt().isNegative())
15256 SCTy =
MinMax->getSCEVType();
15267 auto GetNonNegExprAndPosDivisor = [&](
const SCEV *Expr,
const SCEV *Divisor,
15269 auto *ConstExpr = dyn_cast<SCEVConstant>(Expr);
15270 auto *ConstDivisor = dyn_cast<SCEVConstant>(Divisor);
15271 if (!ConstExpr || !ConstDivisor)
15273 ExprVal = ConstExpr->getAPInt();
15274 DivisorVal = ConstDivisor->getAPInt();
15275 return ExprVal.isNonNegative() && !DivisorVal.isNonPositive();
15281 auto GetNextSCEVDividesByDivisor = [&](
const SCEV *Expr,
15282 const SCEV *Divisor) {
15285 if (!GetNonNegExprAndPosDivisor(Expr, Divisor, ExprVal, DivisorVal))
15297 auto GetPreviousSCEVDividesByDivisor = [&](
const SCEV *Expr,
15298 const SCEV *Divisor) {
15301 if (!GetNonNegExprAndPosDivisor(Expr, Divisor, ExprVal, DivisorVal))
15311 std::function<
const SCEV *(
const SCEV *,
const SCEV *)>
15312 ApplyDivisibiltyOnMinMaxExpr = [&](
const SCEV *MinMaxExpr,
15313 const SCEV *Divisor) {
15314 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15316 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15320 isa<SCEVSMinExpr>(MinMaxExpr) || isa<SCEVUMinExpr>(MinMaxExpr);
15322 "Expected non-negative operand!");
15323 auto *DivisibleExpr =
15324 IsMin ? GetPreviousSCEVDividesByDivisor(MinMaxLHS, Divisor)
15325 : GetNextSCEVDividesByDivisor(MinMaxLHS, Divisor);
15327 ApplyDivisibiltyOnMinMaxExpr(MinMaxRHS, Divisor), DivisibleExpr};
15338 const SCEV *URemLHS =
nullptr;
15339 const SCEV *URemRHS =
nullptr;
15340 if (matchURem(
LHS, URemLHS, URemRHS)) {
15341 if (
const SCEVUnknown *LHSUnknown = dyn_cast<SCEVUnknown>(URemLHS)) {
15342 auto I = RewriteMap.find(LHSUnknown);
15343 const SCEV *RewrittenLHS =
15344 I != RewriteMap.end() ?
I->second : LHSUnknown;
15345 RewrittenLHS = ApplyDivisibiltyOnMinMaxExpr(RewrittenLHS, URemRHS);
15346 const auto *Multiple =
15348 RewriteMap[LHSUnknown] = Multiple;
15360 if (!isa<SCEVUnknown>(
LHS) && isa<SCEVUnknown>(
RHS)) {
15369 auto AddRewrite = [&](
const SCEV *
From,
const SCEV *FromRewritten,
15371 if (
From == FromRewritten)
15373 RewriteMap[
From] = To;
15379 auto GetMaybeRewritten = [&](
const SCEV *S) {
15380 auto I = RewriteMap.find(S);
15381 return I != RewriteMap.end() ?
I->second : S;
15391 std::function<
bool(
const SCEV *,
const SCEV *&)> HasDivisibiltyInfo =
15392 [&](
const SCEV *Expr,
const SCEV *&DividesBy) {
15393 if (
auto *
Mul = dyn_cast<SCEVMulExpr>(Expr)) {
15394 if (
Mul->getNumOperands() != 2)
15396 auto *MulLHS =
Mul->getOperand(0);
15397 auto *MulRHS =
Mul->getOperand(1);
15398 if (isa<SCEVConstant>(MulLHS))
15400 if (
auto *Div = dyn_cast<SCEVUDivExpr>(MulLHS))
15401 if (Div->getOperand(1) == MulRHS) {
15402 DividesBy = MulRHS;
15406 if (
auto *
MinMax = dyn_cast<SCEVMinMaxExpr>(Expr))
15407 return HasDivisibiltyInfo(
MinMax->getOperand(0), DividesBy) ||
15408 HasDivisibiltyInfo(
MinMax->getOperand(1), DividesBy);
15413 std::function<
bool(
const SCEV *,
const SCEV *&)> IsKnownToDivideBy =
15414 [&](
const SCEV *Expr,
const SCEV *DividesBy) {
15417 if (
auto *
MinMax = dyn_cast<SCEVMinMaxExpr>(Expr))
15418 return IsKnownToDivideBy(
MinMax->getOperand(0), DividesBy) &&
15419 IsKnownToDivideBy(
MinMax->getOperand(1), DividesBy);
15423 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15424 const SCEV *DividesBy =
nullptr;
15425 if (HasDivisibiltyInfo(RewrittenLHS, DividesBy))
15428 IsKnownToDivideBy(RewrittenLHS, DividesBy) ? DividesBy :
nullptr;
15442 switch (Predicate) {
15450 RHS = DividesBy ? GetPreviousSCEVDividesByDivisor(
RHS, DividesBy) :
RHS;
15456 RHS = DividesBy ? GetNextSCEVDividesByDivisor(
RHS, DividesBy) :
RHS;
15460 RHS = DividesBy ? GetPreviousSCEVDividesByDivisor(
RHS, DividesBy) :
RHS;
15464 RHS = DividesBy ? GetNextSCEVDividesByDivisor(
RHS, DividesBy) :
RHS;
15473 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
15477 while (!Worklist.
empty()) {
15479 if (isa<SCEVConstant>(
From))
15483 const SCEV *FromRewritten = GetMaybeRewritten(
From);
15484 const SCEV *To =
nullptr;
15486 switch (Predicate) {
15490 if (
auto *
UMax = dyn_cast<SCEVUMaxExpr>(FromRewritten))
15491 EnqueueOperands(
UMax);
15496 if (
auto *
SMax = dyn_cast<SCEVSMaxExpr>(FromRewritten))
15497 EnqueueOperands(
SMax);
15502 if (
auto *
UMin = dyn_cast<SCEVUMinExpr>(FromRewritten))
15503 EnqueueOperands(
UMin);
15508 if (
auto *
SMin = dyn_cast<SCEVSMinExpr>(FromRewritten))
15509 EnqueueOperands(
SMin);
15512 if (isa<SCEVConstant>(
RHS))
15516 if (isa<SCEVConstant>(
RHS) &&
15517 cast<SCEVConstant>(
RHS)->getValue()->isNullValue()) {
15518 const SCEV *OneAlignedUp =
15519 DividesBy ? GetNextSCEVDividesByDivisor(One, DividesBy) : One;
15528 AddRewrite(
From, FromRewritten, To);
15538 auto *AssumeI = cast<CallInst>(AssumeVH);
15545 auto *GuardDecl =
F.getParent()->getFunction(
15548 for (
const auto *GU : GuardDecl->users())
15549 if (
const auto *Guard = dyn_cast<IntrinsicInst>(GU))
15550 if (Guard->getFunction() == Header->getParent() && DT.
dominates(Guard, Header))
15558 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(
15559 L->getLoopPredecessor(), Header);
15560 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
15563 dyn_cast<BranchInst>(Pair.first->getTerminator());
15576 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
15580 while (!Worklist.
empty()) {
15585 if (
auto *Cmp = dyn_cast<ICmpInst>(
Cond)) {
15587 EnterIfTrue ? Cmp->getPredicate() : Cmp->getInversePredicate();
15588 const auto *
LHS =
getSCEV(Cmp->getOperand(0));
15589 const auto *
RHS =
getSCEV(Cmp->getOperand(1));
15590 CollectCondition(Predicate,
LHS,
RHS, RewriteMap);
15603 if (RewriteMap.
empty())
15609 bool PreserveNUW =
true;
15610 bool PreserveNSW =
true;
15611 for (
const SCEV *Expr : ExprsToRewrite) {
15612 const SCEV *RewriteTo = RewriteMap[Expr];
15620 if (ExprsToRewrite.
size() > 1) {
15621 for (
const SCEV *Expr : ExprsToRewrite) {
15622 const SCEV *RewriteTo = RewriteMap[Expr];
15623 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")
#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
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
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.
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)
const SCEV * visitAddExpr(const SCEVAddExpr *Expr)
SCEVLoopGuardRewriter(ScalarEvolution &SE, DenseMap< const SCEV *, const SCEV * > &M, bool PreserveNUW, bool PreserveNSW)
const SCEV * visitMulExpr(const SCEVMulExpr *Expr)
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 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.
APInt multiplicativeInverse() const
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 * getGetElementPtr(Type *Ty, Constant *C, ArrayRef< Constant * > IdxList, GEPNoWrapFlags NW=GEPNoWrapFlags::none(), std::optional< ConstantRange > InRange=std::nullopt, Type *OnlyIfReducedTy=nullptr)
Getelementptr form.
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static Constant * getNeg(Constant *C, bool HasNSW=false)
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=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.
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
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
Represents flags for the getelementptr instruction/expression.
bool hasNoUnsignedSignedWrap() const
bool hasNoUnsignedWrap() const
static GEPNoWrapFlags none()
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 compare(const APInt &LHS, const APInt &RHS, ICmpInst::Predicate Pred)
Return result of LHS Pred RHS comparison.
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.
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 * getSymbolicMaxBackedgeTakenCount()
Get the (predicated) symbolic max 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 * getPredicatedSymbolicMaxBackedgeTakenCount(const Loop *L, SmallVector< const SCEVPredicate *, 4 > &Predicates)
Similar to getSymbolicMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
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).
const ParentTy * getParent() const
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.
LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt gcd(const DynamicAPInt &A, const DynamicAPInt &B)
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.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
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.
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...
Constant * ConstantFoldInstOperands(Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)
Return true if the given value is known to be non-zero when defined.
@ 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