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);
594 if (LIsPointer != RIsPointer)
595 return (
int)LIsPointer - (int)RIsPointer;
600 return (
int)LID - (int)RID;
603 if (
const auto *LA = dyn_cast<Argument>(LV)) {
604 const auto *
RA = cast<Argument>(RV);
605 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
606 return (
int)LArgNo - (int)RArgNo;
609 if (
const auto *LGV = dyn_cast<GlobalValue>(LV)) {
610 const auto *RGV = cast<GlobalValue>(RV);
612 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
613 auto LT = GV->getLinkage();
620 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
621 return LGV->getName().compare(RGV->getName());
626 if (
const auto *LInst = dyn_cast<Instruction>(LV)) {
627 const auto *RInst = cast<Instruction>(RV);
632 if (LParent != RParent) {
635 if (LDepth != RDepth)
636 return (
int)LDepth - (int)RDepth;
640 unsigned LNumOps = LInst->getNumOperands(),
641 RNumOps = RInst->getNumOperands();
642 if (LNumOps != RNumOps)
643 return (
int)LNumOps - (int)RNumOps;
645 for (
unsigned Idx :
seq(LNumOps)) {
661static std::optional<int>
672 return (
int)LType - (int)RType;
702 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
703 if (LBitWidth != RBitWidth)
704 return (
int)LBitWidth - (int)RBitWidth;
705 return LA.
ult(
RA) ? -1 : 1;
709 const auto *LTy = cast<IntegerType>(cast<SCEVVScale>(
LHS)->
getType());
710 const auto *RTy = cast<IntegerType>(cast<SCEVVScale>(
RHS)->
getType());
711 return LTy->getBitWidth() - RTy->getBitWidth();
722 if (LLoop != RLoop) {
724 assert(LHead != RHead &&
"Two loops share the same header?");
728 "No dominance between recurrences used by one SCEV?");
751 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
752 if (LNumOps != RNumOps)
753 return (
int)LNumOps - (int)RNumOps;
755 for (
unsigned i = 0; i != LNumOps; ++i) {
782 if (Ops.
size() < 2)
return;
789 return Complexity && *Complexity < 0;
791 if (Ops.
size() == 2) {
795 if (IsLessComplex(
RHS,
LHS))
802 return IsLessComplex(
LHS,
RHS);
809 for (
unsigned i = 0, e = Ops.
size(); i != e-2; ++i) {
810 const SCEV *S = Ops[i];
815 for (
unsigned j = i+1; j != e && Ops[j]->getSCEVType() == Complexity; ++j) {
820 if (i == e-2)
return;
842template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
846 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
850 if (
const auto *
C = dyn_cast<SCEVConstant>(
Op)) {
854 Folded = cast<SCEVConstant>(
863 assert(Folded &&
"Must have folded value");
867 if (Folded && IsAbsorber(Folded->
getAPInt()))
871 if (Folded && !IsIdentity(Folded->
getAPInt()))
874 return Ops.
size() == 1 ? Ops[0] :
nullptr;
949 APInt OddFactorial(W, 1);
951 for (
unsigned i = 3; i <= K; ++i) {
954 OddFactorial *= (i >> TwoFactors);
958 unsigned CalculationBits = W +
T;
972 for (
unsigned i = 1; i != K; ++i) {
1005 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1010 if (isa<SCEVCouldNotCompute>(Coeff))
1025 "getLosslessPtrToIntExpr() should self-recurse at most once.");
1029 if (!
Op->getType()->isPointerTy())
1040 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1059 if (
auto *U = dyn_cast<SCEVUnknown>(
Op)) {
1064 if (isa<ConstantPointerNull>(U->getValue()))
1070 SCEV *S =
new (SCEVAllocator)
1072 UniqueSCEVs.InsertNode(S, IP);
1077 assert(
Depth == 0 &&
"getLosslessPtrToIntExpr() should not self-recurse for "
1078 "non-SCEVUnknown's.");
1090 class SCEVPtrToIntSinkingRewriter
1098 SCEVPtrToIntSinkingRewriter
Rewriter(SE);
1108 return Base::visit(S);
1113 bool Changed =
false;
1123 bool Changed =
false;
1133 "Should only reach pointer-typed SCEVUnknown's.");
1139 const SCEV *IntOp = SCEVPtrToIntSinkingRewriter::rewrite(
Op, *
this);
1141 "We must have succeeded in sinking the cast, "
1142 "and ending up with an integer-typed expression!");
1150 if (isa<SCEVCouldNotCompute>(IntOp))
1159 "This is not a truncating conversion!");
1161 "This is not a conversion to a SCEVable type!");
1162 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1170 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1192 UniqueSCEVs.InsertNode(S, IP);
1201 if (isa<SCEVAddExpr>(
Op) || isa<SCEVMulExpr>(
Op)) {
1202 auto *CommOp = cast<SCEVCommutativeExpr>(
Op);
1204 unsigned numTruncs = 0;
1205 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1208 if (!isa<SCEVIntegralCastExpr>(CommOp->getOperand(i)) &&
1209 isa<SCEVTruncateExpr>(S))
1213 if (numTruncs < 2) {
1214 if (isa<SCEVAddExpr>(
Op))
1216 if (isa<SCEVMulExpr>(
Op))
1223 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1230 for (
const SCEV *
Op : AddRec->operands())
1245 UniqueSCEVs.InsertNode(S, IP);
1285struct ExtendOpTraitsBase {
1291template <
typename ExtendOp>
struct ExtendOpTraits {
1307 static const GetExtendExprTy GetExtendExpr;
1309 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1316const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1323 static const GetExtendExprTy GetExtendExpr;
1325 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1332const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1344template <
typename ExtendOpTy>
1347 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1348 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1355 const SCEVAddExpr *SA = dyn_cast<SCEVAddExpr>(Start);
1364 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1377 auto PreStartFlags =
1395 const SCEV *OperandExtendedStart =
1397 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1398 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1410 const SCEV *OverflowLimit =
1411 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1413 if (OverflowLimit &&
1421template <
typename ExtendOpTy>
1425 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1427 const SCEV *PreStart = getPreStartForExtend<ExtendOpTy>(AR, Ty, SE,
Depth);
1433 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1468template <
typename ExtendOpTy>
1469bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1472 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1478 const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start);
1484 for (
unsigned Delta : {-2, -1, 1, 2}) {
1489 ID.AddPointer(PreStart);
1490 ID.AddPointer(Step);
1498 if (PreAR && PreAR->getNoWrapFlags(WrapType)) {
1501 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1502 DeltaS, &Pred,
this);
1520 const unsigned BitWidth =
C.getBitWidth();
1538 const APInt &ConstantStart,
1557 auto &UserIDs = FoldCacheUser[
I.first->second];
1558 assert(
count(UserIDs,
ID) == 1 &&
"unexpected duplicates in UserIDs");
1559 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1560 if (UserIDs[
I] ==
ID) {
1565 I.first->second = S;
1567 auto R = FoldCacheUser.insert({S, {}});
1568 R.first->second.push_back(
ID);
1574 "This is not an extending conversion!");
1576 "This is not a conversion to a SCEVable type!");
1577 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1581 auto Iter = FoldCache.find(
ID);
1582 if (Iter != FoldCache.end())
1583 return Iter->second;
1586 if (!isa<SCEVZeroExtendExpr>(S))
1594 "This is not an extending conversion!");
1596 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1613 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1617 UniqueSCEVs.InsertNode(S, IP);
1626 const SCEV *
X = ST->getOperand();
1640 if (AR->isAffine()) {
1641 const SCEV *Start = AR->getStart();
1642 const SCEV *Step = AR->getStepRecurrence(*
this);
1644 const Loop *L = AR->getLoop();
1648 if (AR->hasNoUnsignedWrap()) {
1650 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
Depth + 1);
1664 if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
1669 const SCEV *CastedMaxBECount =
1673 if (MaxBECount == RecastedMaxBECount) {
1683 const SCEV *WideMaxBECount =
1685 const SCEV *OperandExtendedAdd =
1691 if (ZAdd == OperandExtendedAdd) {
1695 Start = getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
1702 OperandExtendedAdd =
1708 if (ZAdd == OperandExtendedAdd) {
1713 Start = getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
1728 if (!isa<SCEVCouldNotCompute>(MaxBECount) || HasGuards ||
1731 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1733 if (AR->hasNoUnsignedWrap()) {
1739 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
Depth + 1);
1756 Start = getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
1767 if (
const auto *SC = dyn_cast<SCEVConstant>(Start)) {
1768 const APInt &
C = SC->getAPInt();
1772 const SCEV *SResidual =
1781 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1784 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
Depth + 1);
1800 if (
auto *Div = dyn_cast<SCEVUDivExpr>(
Op))
1804 if (
auto *SA = dyn_cast<SCEVAddExpr>(
Op)) {
1806 if (SA->hasNoUnsignedWrap()) {
1810 for (
const auto *
Op : SA->operands())
1823 if (
const auto *SC = dyn_cast<SCEVConstant>(SA->getOperand(0))) {
1827 const SCEV *SResidual =
1837 if (
auto *SM = dyn_cast<SCEVMulExpr>(
Op)) {
1839 if (SM->hasNoUnsignedWrap()) {
1843 for (
const auto *
Op : SM->operands())
1860 if (SM->getNumOperands() == 2)
1861 if (
auto *MulLHS = dyn_cast<SCEVConstant>(SM->getOperand(0)))
1862 if (MulLHS->getAPInt().isPowerOf2())
1863 if (
auto *TruncRHS = dyn_cast<SCEVTruncateExpr>(SM->getOperand(1))) {
1865 MulLHS->getAPInt().logBase2();
1877 if (isa<SCEVUMinExpr>(
Op) || isa<SCEVUMaxExpr>(
Op)) {
1878 auto *
MinMax = cast<SCEVMinMaxExpr>(
Op);
1880 for (
auto *Operand :
MinMax->operands())
1882 if (isa<SCEVUMinExpr>(
MinMax))
1888 if (
auto *
MinMax = dyn_cast<SCEVSequentialMinMaxExpr>(
Op)) {
1889 assert(isa<SCEVSequentialUMinExpr>(
MinMax) &&
"Not supported!");
1891 for (
auto *Operand :
MinMax->operands())
1898 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1901 UniqueSCEVs.InsertNode(S, IP);
1909 "This is not an extending conversion!");
1911 "This is not a conversion to a SCEVable type!");
1912 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1916 auto Iter = FoldCache.find(
ID);
1917 if (Iter != FoldCache.end())
1918 return Iter->second;
1921 if (!isa<SCEVSignExtendExpr>(S))
1929 "This is not an extending conversion!");
1931 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1953 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1958 UniqueSCEVs.InsertNode(S, IP);
1967 const SCEV *
X = ST->getOperand();
1976 if (
auto *SA = dyn_cast<SCEVAddExpr>(
Op)) {
1978 if (SA->hasNoSignedWrap()) {
1982 for (
const auto *
Op : SA->operands())
1996 if (
const auto *SC = dyn_cast<SCEVConstant>(SA->getOperand(0))) {
2000 const SCEV *SResidual =
2014 if (AR->isAffine()) {
2015 const SCEV *Start = AR->getStart();
2016 const SCEV *Step = AR->getStepRecurrence(*
this);
2018 const Loop *L = AR->getLoop();
2022 if (AR->hasNoSignedWrap()) {
2024 getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty,
this,
Depth + 1);
2038 if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
2044 const SCEV *CastedMaxBECount =
2048 if (MaxBECount == RecastedMaxBECount) {
2058 const SCEV *WideMaxBECount =
2060 const SCEV *OperandExtendedAdd =
2066 if (SAdd == OperandExtendedAdd) {
2070 Start = getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty,
this,
2077 OperandExtendedAdd =
2083 if (SAdd == OperandExtendedAdd) {
2095 Start = getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty,
this,
2103 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2105 if (AR->hasNoSignedWrap()) {
2111 getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty,
this,
Depth + 1);
2119 if (
const auto *SC = dyn_cast<SCEVConstant>(Start)) {
2120 const APInt &
C = SC->getAPInt();
2124 const SCEV *SResidual =
2133 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2136 getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty,
this,
Depth + 1);
2149 if (isa<SCEVSMinExpr>(
Op) || isa<SCEVSMaxExpr>(
Op)) {
2150 auto *
MinMax = cast<SCEVMinMaxExpr>(
Op);
2152 for (
auto *Operand :
MinMax->operands())
2154 if (isa<SCEVSMinExpr>(
MinMax))
2161 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
2164 UniqueSCEVs.InsertNode(S, IP);
2190 "This is not an extending conversion!");
2192 "This is not a conversion to a SCEVable type!");
2197 if (SC->getAPInt().isNegative())
2202 const SCEV *NewOp =
T->getOperand();
2210 if (!isa<SCEVZeroExtendExpr>(ZExt))
2215 if (!isa<SCEVSignExtendExpr>(SExt))
2221 for (
const SCEV *
Op : AR->operands())
2227 if (isa<SCEVSMaxExpr>(
Op))
2260 APInt &AccumulatedConstant,
2263 bool Interesting =
false;
2267 while (
const SCEVConstant *
C = dyn_cast<SCEVConstant>(Ops[i])) {
2270 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2272 AccumulatedConstant += Scale *
C->getAPInt();
2277 for (; i != Ops.
size(); ++i) {
2279 if (
Mul && isa<SCEVConstant>(
Mul->getOperand(0))) {
2281 Scale * cast<SCEVConstant>(
Mul->getOperand(0))->getAPInt();
2282 if (
Mul->getNumOperands() == 2 && isa<SCEVAddExpr>(
Mul->getOperand(1))) {
2287 Add->operands(), NewScale, SE);
2293 auto Pair = M.insert({Key, NewScale});
2297 Pair.first->second += NewScale;
2305 std::pair<DenseMap<const SCEV *, APInt>::iterator,
bool> Pair =
2306 M.insert({Ops[i], Scale});
2310 Pair.first->second += Scale;
2329 case Instruction::Add:
2332 case Instruction::Sub:
2335 case Instruction::Mul:
2345 auto *NarrowTy = cast<IntegerType>(
LHS->
getType());
2349 const SCEV *
A = (this->*Extension)(
2351 const SCEV *LHSB = (this->*Extension)(
LHS, WideTy, 0);
2352 const SCEV *RHSB = (this->*Extension)(
RHS, WideTy, 0);
2360 if (BinOp == Instruction::Mul)
2362 auto *RHSC = dyn_cast<SCEVConstant>(
RHS);
2366 APInt C = RHSC->getAPInt();
2367 unsigned NumBits =
C.getBitWidth();
2368 bool IsSub = (BinOp == Instruction::Sub);
2369 bool IsNegativeConst = (
Signed &&
C.isNegative());
2371 bool OverflowDown = IsSub ^ IsNegativeConst;
2373 if (IsNegativeConst) {
2386 APInt Limit = Min + Magnitude;
2392 APInt Limit = Max - Magnitude;
2397std::optional<SCEV::NoWrapFlags>
2402 return std::nullopt;
2411 bool Deduced =
false;
2413 if (OBO->
getOpcode() != Instruction::Add &&
2416 return std::nullopt;
2425 false,
LHS,
RHS, CtxI)) {
2439 return std::nullopt;
2449 using namespace std::placeholders;
2456 assert(CanAnalyze &&
"don't call from other places!");
2463 auto IsKnownNonNegative = [&](
const SCEV *S) {
2473 if (SignOrUnsignWrap != SignOrUnsignMask &&
2475 isa<SCEVConstant>(Ops[0])) {
2480 return Instruction::Add;
2482 return Instruction::Mul;
2488 const APInt &
C = cast<SCEVConstant>(Ops[0])->getAPInt();
2493 Opcode,
C, OBO::NoSignedWrap);
2501 Opcode,
C, OBO::NoUnsignedWrap);
2511 Ops[0]->isZero() && IsKnownNonNegative(Ops[1]))
2517 if (
auto *UDiv = dyn_cast<SCEVUDivExpr>(Ops[0]))
2518 if (UDiv->getOperand(1) == Ops[1])
2520 if (
auto *UDiv = dyn_cast<SCEVUDivExpr>(Ops[1]))
2521 if (UDiv->getOperand(1) == Ops[0])
2537 "only nuw or nsw allowed");
2539 if (Ops.
size() == 1)
return Ops[0];
2542 for (
unsigned i = 1, e = Ops.
size(); i != e; ++i)
2544 "SCEVAddExpr operand types don't match!");
2547 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2552 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2553 [](
const APInt &
C) {
return C.isZero(); },
2554 [](
const APInt &
C) {
return false; });
2558 unsigned Idx = isa<SCEVConstant>(Ops[0]) ? 1 : 0;
2567 return getOrCreateAddExpr(Ops, ComputeFlags(Ops));
2572 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2573 Add->setNoWrapFlags(ComputeFlags(Ops));
2580 Type *Ty = Ops[0]->getType();
2581 bool FoundMatch =
false;
2582 for (
unsigned i = 0, e = Ops.
size(); i != e-1; ++i)
2583 if (Ops[i] == Ops[i+1]) {
2586 while (i+Count != e && Ops[i+Count] == Ops[i])
2591 if (Ops.
size() == Count)
2595 --i; e -= Count - 1;
2605 auto FindTruncSrcType = [&]() ->
Type * {
2610 if (
auto *
T = dyn_cast<SCEVTruncateExpr>(Ops[
Idx]))
2611 return T->getOperand()->getType();
2612 if (
const auto *
Mul = dyn_cast<SCEVMulExpr>(Ops[
Idx])) {
2613 const auto *LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2614 if (
const auto *
T = dyn_cast<SCEVTruncateExpr>(LastOp))
2615 return T->getOperand()->getType();
2619 if (
auto *SrcType = FindTruncSrcType()) {
2624 for (
const SCEV *
Op : Ops) {
2626 if (
T->getOperand()->getType() != SrcType) {
2633 }
else if (
const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(
Op)) {
2635 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2637 dyn_cast<SCEVTruncateExpr>(M->getOperand(j))) {
2638 if (
T->getOperand()->getType() != SrcType) {
2643 }
else if (
const auto *
C = dyn_cast<SCEVConstant>(M->getOperand(j))) {
2661 if (isa<SCEVConstant>(Fold) || isa<SCEVUnknown>(Fold))
2666 if (Ops.
size() == 2) {
2670 const SCEV *
A = Ops[0];
2671 const SCEV *
B = Ops[1];
2672 auto *AddExpr = dyn_cast<SCEVAddExpr>(
B);
2673 auto *
C = dyn_cast<SCEVConstant>(
A);
2674 if (AddExpr &&
C && isa<SCEVConstant>(AddExpr->getOperand(0))) {
2675 auto C1 = cast<SCEVConstant>(AddExpr->getOperand(0))->getAPInt();
2676 auto C2 =
C->getAPInt();
2679 APInt ConstAdd = C1 + C2;
2680 auto AddFlags = AddExpr->getNoWrapFlags();
2706 if (Ops.
size() == 2) {
2708 if (
Mul &&
Mul->getNumOperands() == 2 &&
2709 Mul->getOperand(0)->isAllOnesValue()) {
2712 if (matchURem(
Mul->getOperand(1),
X,
Y) &&
X == Ops[1]) {
2724 bool DeletedAdd =
false;
2738 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2754 if (
Idx < Ops.
size() && isa<SCEVMulExpr>(Ops[
Idx])) {
2761 struct APIntCompare {
2770 std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists;
2771 for (
const SCEV *NewOp : NewOps)
2772 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2775 if (AccumulatedConstant != 0)
2777 for (
auto &MulOp : MulOpLists) {
2778 if (MulOp.first == 1) {
2780 }
else if (MulOp.first != 0) {
2789 if (Ops.
size() == 1)
2798 for (;
Idx < Ops.
size() && isa<SCEVMulExpr>(Ops[
Idx]); ++
Idx) {
2800 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2801 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2802 if (isa<SCEVConstant>(MulOpSCEV))
2804 for (
unsigned AddOp = 0, e = Ops.
size(); AddOp != e; ++AddOp)
2805 if (MulOpSCEV == Ops[AddOp]) {
2807 const SCEV *InnerMul =
Mul->getOperand(MulOp == 0);
2808 if (
Mul->getNumOperands() != 2) {
2812 Mul->operands().take_front(MulOp));
2820 if (Ops.
size() == 2)
return OuterMul;
2833 for (
unsigned OtherMulIdx =
Idx+1;
2834 OtherMulIdx < Ops.
size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]);
2836 const SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]);
2840 OMulOp != e; ++OMulOp)
2841 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2843 const SCEV *InnerMul1 =
Mul->getOperand(MulOp == 0);
2844 if (
Mul->getNumOperands() != 2) {
2846 Mul->operands().take_front(MulOp));
2853 OtherMul->
operands().take_front(OMulOp));
2858 const SCEV *InnerMulSum =
2862 if (Ops.
size() == 2)
return OuterMul;
2879 for (;
Idx < Ops.
size() && isa<SCEVAddRecExpr>(Ops[
Idx]); ++
Idx) {
2885 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i)
2893 if (!LIOps.
empty()) {
2918 auto *DefI = getDefiningScopeBound(LIOps);
2920 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2932 if (Ops.
size() == 1)
return NewRec;
2935 for (
unsigned i = 0;; ++i)
2936 if (Ops[i] == AddRec) {
2946 for (
unsigned OtherIdx =
Idx+1;
2947 OtherIdx < Ops.
size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
2952 cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop()->getHeader(),
2954 "AddRecExprs are not sorted in reverse dominance order?");
2955 if (AddRecLoop == cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop()) {
2958 for (; OtherIdx != Ops.
size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
2960 const auto *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
2961 if (OtherAddRec->getLoop() == AddRecLoop) {
2962 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2964 if (i >= AddRecOps.
size()) {
2965 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2969 AddRecOps[i], OtherAddRec->getOperand(i)};
2972 Ops.
erase(Ops.
begin() + OtherIdx); --OtherIdx;
2987 return getOrCreateAddExpr(Ops, ComputeFlags(Ops));
2995 for (
const SCEV *
Op : Ops)
2999 static_cast<SCEVAddExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3002 std::uninitialized_copy(Ops.begin(), Ops.end(), O);
3003 S =
new (SCEVAllocator)
3005 UniqueSCEVs.InsertNode(S, IP);
3017 for (
const SCEV *
Op : Ops)
3025 std::uninitialized_copy(Ops.begin(), Ops.end(), O);
3026 S =
new (SCEVAllocator)
3028 UniqueSCEVs.InsertNode(S, IP);
3029 LoopUsers[
L].push_back(S);
3041 for (
const SCEV *
Op : Ops)
3045 static_cast<SCEVMulExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3048 std::uninitialized_copy(Ops.begin(), Ops.end(), O);
3049 S =
new (SCEVAllocator)
SCEVMulExpr(
ID.Intern(SCEVAllocator),
3051 UniqueSCEVs.InsertNode(S, IP);
3060 if (j > 1 && k / j != i) Overflow =
true;
3076 if (n == 0 || n == k)
return 1;
3077 if (k > n)
return 0;
3083 for (
uint64_t i = 1; i <= k; ++i) {
3084 r =
umul_ov(r, n-(i-1), Overflow);
3093 struct FindConstantInAddMulChain {
3094 bool FoundConstant =
false;
3096 bool follow(
const SCEV *S) {
3097 FoundConstant |= isa<SCEVConstant>(S);
3098 return isa<SCEVAddExpr>(S) || isa<SCEVMulExpr>(S);
3101 bool isDone()
const {
3102 return FoundConstant;
3106 FindConstantInAddMulChain
F;
3108 ST.visitAll(StartExpr);
3109 return F.FoundConstant;
3117 "only nuw or nsw allowed");
3119 if (Ops.
size() == 1)
return Ops[0];
3121 Type *ETy = Ops[0]->getType();
3123 for (
unsigned i = 1, e = Ops.
size(); i != e; ++i)
3125 "SCEVMulExpr operand types don't match!");
3130 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3131 [](
const APInt &
C) {
return C.isOne(); },
3132 [](
const APInt &
C) {
return C.isZero(); });
3143 return getOrCreateMulExpr(Ops, ComputeFlags(Ops));
3148 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3149 Mul->setNoWrapFlags(ComputeFlags(Ops));
3153 if (
const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
3154 if (Ops.
size() == 2) {
3171 if (Ops[0]->isAllOnesValue()) {
3176 bool AnyFolded =
false;
3177 for (
const SCEV *AddOp :
Add->operands()) {
3180 if (!isa<SCEVMulExpr>(
Mul)) AnyFolded =
true;
3185 }
else if (
const auto *AddRec = dyn_cast<SCEVAddRecExpr>(Ops[1])) {
3204 AddRec->getNoWrapFlags(FlagsMask));
3217 bool DeletedMul =
false;
3242 for (;
Idx < Ops.
size() && isa<SCEVAddRecExpr>(Ops[
Idx]); ++
Idx) {
3247 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i)
3255 if (!LIOps.
empty()) {
3268 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3284 if (Ops.
size() == 1)
return NewRec;
3287 for (
unsigned i = 0;; ++i)
3288 if (Ops[i] == AddRec) {
3309 bool OpsModified =
false;
3310 for (
unsigned OtherIdx =
Idx+1;
3311 OtherIdx != Ops.
size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
3314 dyn_cast<SCEVAddRecExpr>(Ops[OtherIdx]);
3324 bool Overflow =
false;
3330 SmallVector <const SCEV *, 7> SumOps;
3331 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3335 z < ze && !Overflow; ++z) {
3338 if (LargerThan64Bits)
3339 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3341 Coeff = Coeff1*Coeff2;
3356 if (Ops.
size() == 2)
return NewAddRec;
3357 Ops[
Idx] = NewAddRec;
3358 Ops.
erase(Ops.
begin() + OtherIdx); --OtherIdx;
3360 AddRec = dyn_cast<SCEVAddRecExpr>(NewAddRec);
3374 return getOrCreateMulExpr(Ops, ComputeFlags(Ops));
3382 "SCEVURemExpr operand types don't match!");
3387 if (RHSC->getValue()->isOne())
3391 if (RHSC->getAPInt().isPowerOf2()) {
3410 "SCEVUDivExpr operand can't be pointer!");
3412 "SCEVUDivExpr operand types don't match!");
3419 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3424 if (LHSC->getValue()->isZero())
3428 if (RHSC->getValue()->isOne())
3433 if (!RHSC->getValue()->isZero()) {
3438 unsigned LZ = RHSC->getAPInt().countl_zero();
3442 if (!RHSC->getAPInt().isPowerOf2())
3448 dyn_cast<SCEVConstant>(AR->getStepRecurrence(*
this))) {
3450 const APInt &StepInt = Step->getAPInt();
3451 const APInt &DivInt = RHSC->getAPInt();
3452 if (!StepInt.
urem(DivInt) &&
3458 for (
const SCEV *
Op : AR->operands())
3465 const SCEVConstant *StartC = dyn_cast<SCEVConstant>(AR->getStart());
3466 if (StartC && !DivInt.
urem(StepInt) &&
3472 const APInt &StartRem = StartInt.
urem(StepInt);
3473 if (StartRem != 0) {
3474 const SCEV *NewLHS =
3477 if (
LHS != NewLHS) {
3487 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3496 for (
const SCEV *
Op : M->operands())
3500 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3501 const SCEV *
Op = M->getOperand(i);
3503 if (!isa<SCEVUDivExpr>(Div) &&
getMulExpr(Div, RHSC) ==
Op) {
3513 if (
auto *DivisorConstant =
3514 dyn_cast<SCEVConstant>(OtherDiv->getRHS())) {
3515 bool Overflow =
false;
3517 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3528 for (
const SCEV *
Op :
A->operands())
3532 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3534 if (isa<SCEVUDivExpr>(
Op) ||
3539 if (
Operands.size() ==
A->getNumOperands())
3546 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3553 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
3556 UniqueSCEVs.InsertNode(S, IP);
3586 if (!
Mul || !
Mul->hasNoUnsignedWrap())
3592 if (
const auto *LHSCst = dyn_cast<SCEVConstant>(
Mul->getOperand(0))) {
3593 if (LHSCst == RHSCst) {
3601 APInt Factor =
gcd(LHSCst, RHSCst);
3604 cast<SCEVConstant>(
getConstant(LHSCst->getAPInt().udiv(Factor)));
3606 cast<SCEVConstant>(
getConstant(RHSCst->getAPInt().udiv(Factor)));
3612 Mul = dyn_cast<SCEVMulExpr>(
LHS);
3619 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3620 if (
Mul->getOperand(i) ==
RHS) {
3638 if (
const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
3639 if (StepChrec->getLoop() == L) {
3658 "SCEVAddRecExpr operand types don't match!");
3659 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3663 "SCEVAddRecExpr operand is not available at loop entry!");
3681 const Loop *NestedLoop = NestedAR->getLoop();
3682 if (L->contains(NestedLoop)
3687 Operands[0] = NestedAR->getStart();
3691 bool AllInvariant =
all_of(
3703 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3714 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3724 return getOrCreateAddRecExpr(
Operands, L, Flags);
3741 auto *GEPI = dyn_cast<Instruction>(
GEP);
3742 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3753 bool FirstIter =
true;
3755 for (
const SCEV *IndexExpr : IndexExprs) {
3757 if (
StructType *STy = dyn_cast<StructType>(CurTy)) {
3762 Offsets.push_back(FieldOffset);
3765 CurTy = STy->getTypeAtIndex(
Index);
3769 assert(isa<PointerType>(CurTy) &&
3770 "The first index of a GEP indexes a pointer");
3771 CurTy =
GEP->getSourceElementType();
3782 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3783 Offsets.push_back(LocalOffset);
3788 if (Offsets.empty())
3801 "GEP should not change type mid-flight.");
3805SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3808 ID.AddInteger(SCEVType);
3809 for (
const SCEV *
Op : Ops)
3812 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3822 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3823 assert(!Ops.
empty() &&
"Cannot get empty (u|s)(min|max)!");
3824 if (Ops.
size() == 1)
return Ops[0];
3827 for (
unsigned i = 1, e = Ops.
size(); i != e; ++i) {
3829 "Operand types don't match!");
3832 "min/max should be consistently pointerish");
3858 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3860 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3865 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3867 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3873 if (
const SCEV *S = findExistingSCEVInCache(Kind, Ops)) {
3879 while (
Idx < Ops.
size() && Ops[
Idx]->getSCEVType() < Kind)
3885 bool DeletedAny =
false;
3886 while (Ops[
Idx]->getSCEVType() == Kind) {
3906 for (
unsigned i = 0, e = Ops.
size() - 1; i != e; ++i) {
3907 if (Ops[i] == Ops[i + 1] ||
3908 isKnownViaNonRecursiveReasoning(FirstPred, Ops[i], Ops[i + 1])) {
3914 }
else if (isKnownViaNonRecursiveReasoning(SecondPred, Ops[i],
3923 if (Ops.
size() == 1)
return Ops[0];
3925 assert(!Ops.
empty() &&
"Reduced smax down to nothing!");
3930 ID.AddInteger(Kind);
3931 for (
const SCEV *
Op : Ops)
3934 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3936 return ExistingSCEV;
3938 std::uninitialized_copy(Ops.
begin(), Ops.
end(), O);
3939 SCEV *S =
new (SCEVAllocator)
3942 UniqueSCEVs.InsertNode(S, IP);
3949class SCEVSequentialMinMaxDeduplicatingVisitor final
3950 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
3951 std::optional<const SCEV *>> {
3952 using RetVal = std::optional<const SCEV *>;
3960 bool canRecurseInto(
SCEVTypes Kind)
const {
3963 return RootKind == Kind || NonSequentialRootKind == Kind;
3966 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
3967 assert((isa<SCEVMinMaxExpr>(S) || isa<SCEVSequentialMinMaxExpr>(S)) &&
3968 "Only for min/max expressions.");
3971 if (!canRecurseInto(Kind))
3974 auto *NAry = cast<SCEVNAryExpr>(S);
3976 bool Changed =
visit(Kind, NAry->operands(), NewOps);
3981 return std::nullopt;
3983 return isa<SCEVSequentialMinMaxExpr>(S)
3990 if (!SeenOps.
insert(S).second)
3991 return std::nullopt;
3992 return Base::visit(S);
3998 : SE(SE), RootKind(RootKind),
3999 NonSequentialRootKind(
4005 bool Changed =
false;
4009 for (
const SCEV *
Op : OrigOps) {
4018 NewOps = std::move(Ops);
4024 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4034 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4036 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4038 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4040 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4043 return visitAnyMinMaxExpr(Expr);
4047 return visitAnyMinMaxExpr(Expr);
4051 return visitAnyMinMaxExpr(Expr);
4055 return visitAnyMinMaxExpr(Expr);
4059 return visitAnyMinMaxExpr(Expr);
4062 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4106struct SCEVPoisonCollector {
4107 bool LookThroughMaybePoisonBlocking;
4109 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4110 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4112 bool follow(
const SCEV *S) {
4113 if (!LookThroughMaybePoisonBlocking &&
4117 if (
auto *SU = dyn_cast<SCEVUnknown>(S)) {
4123 bool isDone()
const {
return false; }
4133 SCEVPoisonCollector PC1(
true);
4138 if (PC1.MaybePoison.empty())
4144 SCEVPoisonCollector PC2(
false);
4154 SCEVPoisonCollector PC(
false);
4177 while (!Worklist.
empty()) {
4179 if (!Visited.
insert(V).second)
4183 if (Visited.
size() > 16)
4191 auto *
I = dyn_cast<Instruction>(V);
4198 if (
auto *PDI = dyn_cast<PossiblyDisjointInst>(
I))
4199 if (PDI->isDisjoint())
4205 if (
auto *
II = dyn_cast<IntrinsicInst>(
I);
4206 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4213 if (
I->hasPoisonGeneratingAnnotations())
4225 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4226 "Not a SCEVSequentialMinMaxExpr!");
4227 assert(!Ops.
empty() &&
"Cannot get empty (u|s)(min|max)!");
4228 if (Ops.
size() == 1)
4232 for (
unsigned i = 1, e = Ops.
size(); i != e; ++i) {
4234 "Operand types don't match!");
4237 "min/max should be consistently pointerish");
4245 if (
const SCEV *S = findExistingSCEVInCache(Kind, Ops))
4252 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4253 bool Changed = Deduplicator.visit(Kind, Ops, Ops);
4262 bool DeletedAny =
false;
4264 if (Ops[
Idx]->getSCEVType() != Kind) {
4268 const auto *SMME = cast<SCEVSequentialMinMaxExpr>(Ops[
Idx]);
4271 SMME->operands().end());
4279 const SCEV *SaturationPoint;
4290 for (
unsigned i = 1, e = Ops.
size(); i != e; ++i) {
4306 if (isKnownViaNonRecursiveReasoning(Pred, Ops[i - 1], Ops[i])) {
4315 ID.AddInteger(Kind);
4316 for (
const SCEV *
Op : Ops)
4319 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4321 return ExistingSCEV;
4324 std::uninitialized_copy(Ops.
begin(), Ops.
end(), O);
4325 SCEV *S =
new (SCEVAllocator)
4328 UniqueSCEVs.InsertNode(S, IP);
4376 if (
Size.isScalable())
4397 "Cannot get offset for structure containing scalable vector types");
4411 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP)) {
4412 assert(cast<SCEVUnknown>(S)->getValue() == V &&
4413 "Stale SCEVUnknown in uniquing map!");
4418 FirstUnknown = cast<SCEVUnknown>(S);
4419 UniqueSCEVs.InsertNode(S, IP);
4467 bool PreciseA, PreciseB;
4468 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4469 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4470 if (!PreciseA || !PreciseB)
4473 return (ScopeA == ScopeB) || DT.
dominates(ScopeA, ScopeB) ||
4478 return CouldNotCompute.get();
4481bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4483 auto *SU = dyn_cast<SCEVUnknown>(S);
4484 return SU && SU->getValue() ==
nullptr;
4487 return !ContainsNulls;
4492 if (
I != HasRecMap.
end())
4497 HasRecMap.
insert({S, FoundAddRec});
4505 if (SI == ExprValueMap.
end())
4506 return std::nullopt;
4507 return SI->second.getArrayRef();
4513void ScalarEvolution::eraseValueFromMap(
Value *V) {
4515 if (
I != ValueExprMap.
end()) {
4516 auto EVIt = ExprValueMap.
find(
I->second);
4517 bool Removed = EVIt->second.remove(V);
4519 assert(Removed &&
"Value not in ExprValueMap?");
4524void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4528 auto It = ValueExprMap.
find_as(V);
4529 if (It == ValueExprMap.
end()) {
4531 ExprValueMap[S].
insert(V);
4542 return createSCEVIter(V);
4549 if (
I != ValueExprMap.
end()) {
4550 const SCEV *S =
I->second;
4551 assert(checkValidity(S) &&
4552 "existing SCEV has not been properly invalidated");
4561 if (
const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
4565 Type *Ty = V->getType();
4573 if (!
Add ||
Add->getNumOperands() != 2 ||
4574 !
Add->getOperand(0)->isAllOnesValue())
4577 const SCEVMulExpr *AddRHS = dyn_cast<SCEVMulExpr>(
Add->getOperand(1));
4587 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4589 if (
const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
4600 return (
const SCEV *)
nullptr;
4606 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4610 Type *Ty = V->getType();
4616 assert(
P->getType()->isPointerTy());
4618 if (
auto *AddRec = dyn_cast<SCEVAddRecExpr>(
P)) {
4626 if (
auto *
Add = dyn_cast<SCEVAddExpr>(
P)) {
4629 const SCEV **PtrOp =
nullptr;
4630 for (
const SCEV *&AddOp : Ops) {
4631 if (AddOp->getType()->isPointerTy()) {
4632 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4666 const bool RHSIsNotMinSigned =
4697 Type *SrcTy = V->getType();
4699 "Cannot truncate or zero extend with non-integer arguments!");
4709 Type *SrcTy = V->getType();
4711 "Cannot truncate or zero extend with non-integer arguments!");
4721 Type *SrcTy = V->getType();
4723 "Cannot noop or zero extend with non-integer arguments!");
4725 "getNoopOrZeroExtend cannot truncate!");
4733 Type *SrcTy = V->getType();
4735 "Cannot noop or sign extend with non-integer arguments!");
4737 "getNoopOrSignExtend cannot truncate!");
4745 Type *SrcTy = V->getType();
4747 "Cannot noop or any extend with non-integer arguments!");
4749 "getNoopOrAnyExtend cannot truncate!");
4757 Type *SrcTy = V->getType();
4759 "Cannot truncate or noop with non-integer arguments!");
4761 "getTruncateOrNoop cannot extend!");
4769 const SCEV *PromotedLHS =
LHS;
4770 const SCEV *PromotedRHS =
RHS;
4790 assert(!Ops.
empty() &&
"At least one operand must be!");
4792 if (Ops.
size() == 1)
4796 Type *MaxType =
nullptr;
4797 for (
const auto *S : Ops)
4802 assert(MaxType &&
"Failed to find maximum type!");
4806 for (
const auto *S : Ops)
4815 if (!V->getType()->isPointerTy())
4819 if (
auto *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
4820 V = AddRec->getStart();
4821 }
else if (
auto *
Add = dyn_cast<SCEVAddExpr>(V)) {
4822 const SCEV *PtrOp =
nullptr;
4823 for (
const SCEV *AddOp :
Add->operands()) {
4824 if (AddOp->getType()->isPointerTy()) {
4825 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4829 assert(PtrOp &&
"Must have pointer op");
4841 for (
User *U :
I->users()) {
4842 auto *UserInsn = cast<Instruction>(U);
4843 if (Visited.
insert(UserInsn).second)
4858 bool IgnoreOtherLoops =
true) {
4861 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4863 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4870 SeenLoopVariantSCEVUnknown =
true;
4878 SeenOtherLoops =
true;
4882 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4884 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4891 bool SeenLoopVariantSCEVUnknown =
false;
4892 bool SeenOtherLoops =
false;
4902 SCEVPostIncRewriter
Rewriter(L, SE);
4904 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4911 SeenLoopVariantSCEVUnknown =
true;
4919 SeenOtherLoops =
true;
4923 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4925 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4932 bool SeenLoopVariantSCEVUnknown =
false;
4933 bool SeenOtherLoops =
false;
4939class SCEVBackedgeConditionFolder
4944 bool IsPosBECond =
false;
4945 Value *BECond =
nullptr;
4947 BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
4950 "Both outgoing branches should not target same header!");
4957 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
4967 switch (
I->getOpcode()) {
4968 case Instruction::Select: {
4970 std::optional<const SCEV *> Res =
4971 compareWithBackedgeCondition(
SI->getCondition());
4973 bool IsOne = cast<SCEVConstant>(*Res)->getValue()->isOne();
4979 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
4990 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
4993 IsPositiveBECond(IsPosBECond) {}
4995 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
4999 Value *BackedgeCond =
nullptr;
5001 bool IsPositiveBECond;
5004std::optional<const SCEV *>
5005SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5010 if (BackedgeCond == IC)
5013 return std::nullopt;
5039 bool isValid() {
return Valid; }
5052ScalarEvolution::proveNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5062 if (
const SCEVConstant *BECountMax = dyn_cast<SCEVConstant>(BECount)) {
5064 const APInt &BECountAP = BECountMax->getAPInt();
5065 unsigned NoOverflowBitWidth =
5077 Instruction::Add, IncRange, OBO::NoSignedWrap);
5078 if (NSWRegion.contains(AddRecRange))
5087 Instruction::Add, IncRange, OBO::NoUnsignedWrap);
5088 if (NUWRegion.contains(AddRecRange))
5096ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5106 if (!SignedWrapViaInductionTried.insert(AR).second)
5130 if (isa<SCEVCouldNotCompute>(MaxBECount) && !HasGuards &&
5139 const SCEV *OverflowLimit =
5141 if (OverflowLimit &&
5149ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5159 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5184 if (isa<SCEVCouldNotCompute>(MaxBECount) && !HasGuards &&
5223 if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(
Op)) {
5224 IsNSW = OBO->hasNoSignedWrap();
5225 IsNUW = OBO->hasNoUnsignedWrap();
5229 explicit BinaryOp(
unsigned Opcode,
Value *
LHS,
Value *
RHS,
bool IsNSW =
false,
5231 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5241 auto *
Op = dyn_cast<Operator>(V);
5243 return std::nullopt;
5249 switch (
Op->getOpcode()) {
5250 case Instruction::Add:
5251 case Instruction::Sub:
5252 case Instruction::Mul:
5253 case Instruction::UDiv:
5254 case Instruction::URem:
5255 case Instruction::And:
5256 case Instruction::AShr:
5257 case Instruction::Shl:
5258 return BinaryOp(
Op);
5260 case Instruction::Or: {
5262 if (cast<PossiblyDisjointInst>(
Op)->isDisjoint())
5263 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5265 return BinaryOp(
Op);
5268 case Instruction::Xor:
5269 if (
auto *RHSC = dyn_cast<ConstantInt>(
Op->getOperand(1)))
5272 if (RHSC->getValue().isSignMask())
5273 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5275 if (V->getType()->isIntegerTy(1))
5276 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5277 return BinaryOp(
Op);
5279 case Instruction::LShr:
5281 if (
ConstantInt *SA = dyn_cast<ConstantInt>(
Op->getOperand(1))) {
5288 if (SA->getValue().ult(
BitWidth)) {
5290 ConstantInt::get(SA->getContext(),
5292 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5295 return BinaryOp(
Op);
5297 case Instruction::ExtractValue: {
5298 auto *EVI = cast<ExtractValueInst>(
Op);
5299 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5302 auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand());
5307 bool Signed = WO->isSigned();
5310 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5315 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5325 if (
auto *
II = dyn_cast<IntrinsicInst>(V))
5326 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5327 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5329 return std::nullopt;
5355 if (
Op == SymbolicPHI)
5360 if (SourceBits != NewBits)
5368 SExt ? dyn_cast<SCEVTruncateExpr>(SExt->
getOperand())
5369 : dyn_cast<SCEVTruncateExpr>(ZExt->
getOperand());
5373 if (
X != SymbolicPHI)
5375 Signed = SExt !=
nullptr;
5383 if (!L || L->getHeader() != PN->
getParent())
5441std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5442ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5448 auto *PN = cast<PHINode>(SymbolicPHI->
getValue());
5450 assert(L &&
"Expecting an integer loop header phi");
5455 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5456 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5457 Value *
V = PN->getIncomingValue(i);
5458 if (
L->contains(PN->getIncomingBlock(i))) {
5461 }
else if (BEValueV != V) {
5465 }
else if (!StartValueV) {
5467 }
else if (StartValueV != V) {
5468 StartValueV =
nullptr;
5472 if (!BEValueV || !StartValueV)
5473 return std::nullopt;
5480 const auto *
Add = dyn_cast<SCEVAddExpr>(BEValue);
5482 return std::nullopt;
5486 unsigned FoundIndex =
Add->getNumOperands();
5487 Type *TruncTy =
nullptr;
5489 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5492 if (FoundIndex == e) {
5497 if (FoundIndex ==
Add->getNumOperands())
5498 return std::nullopt;
5502 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5503 if (i != FoundIndex)
5510 return std::nullopt;
5564 const SCEV *PHISCEV =
5574 if (
const auto *AR = dyn_cast<SCEVAddRecExpr>(PHISCEV)) {
5591 auto getExtendedExpr = [&](
const SCEV *Expr,
5592 bool CreateSignExtend) ->
const SCEV * {
5595 const SCEV *ExtendedExpr =
5598 return ExtendedExpr;
5606 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5607 const SCEV *ExtendedExpr) ->
bool {
5608 return Expr != ExtendedExpr &&
5612 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5613 if (PredIsKnownFalse(StartVal, StartExtended)) {
5615 return std::nullopt;
5620 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5621 if (PredIsKnownFalse(Accum, AccumExtended)) {
5623 return std::nullopt;
5626 auto AppendPredicate = [&](
const SCEV *Expr,
5627 const SCEV *ExtendedExpr) ->
void {
5628 if (Expr != ExtendedExpr &&
5636 AppendPredicate(StartVal, StartExtended);
5637 AppendPredicate(Accum, AccumExtended);
5645 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5646 std::make_pair(NewAR, Predicates);
5648 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5652std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5654 auto *PN = cast<PHINode>(SymbolicPHI->
getValue());
5657 return std::nullopt;
5660 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5661 if (
I != PredicatedSCEVRewrites.end()) {
5662 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5665 if (Rewrite.first == SymbolicPHI)
5666 return std::nullopt;
5669 assert(isa<SCEVAddRecExpr>(Rewrite.first) &&
"Expected an AddRec");
5670 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5674 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5675 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5680 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5681 return std::nullopt;
5698 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5717const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5719 Value *StartValueV) {
5722 assert(BEValueV && StartValueV);
5728 if (BO->Opcode != Instruction::Add)
5731 const SCEV *Accum =
nullptr;
5732 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5734 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5748 insertValueToMap(PN, PHISCEV);
5750 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(PHISCEV)) {
5753 proveNoWrapViaConstantRanges(AR)));
5759 if (
auto *BEInst = dyn_cast<Instruction>(BEValueV)) {
5761 "Accum is defined outside L, but is not invariant?");
5762 if (isAddRecNeverPoison(BEInst, L))
5769const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5777 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5783 }
else if (BEValueV != V) {
5787 }
else if (!StartValueV) {
5789 }
else if (StartValueV != V) {
5790 StartValueV =
nullptr;
5794 if (!BEValueV || !StartValueV)
5798 "PHI node already processed?");
5802 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5807 insertValueToMap(PN, SymbolicName);
5821 unsigned FoundIndex =
Add->getNumOperands();
5822 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5823 if (
Add->getOperand(i) == SymbolicName)
5824 if (FoundIndex == e) {
5829 if (FoundIndex !=
Add->getNumOperands()) {
5832 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5833 if (i != FoundIndex)
5834 Ops.
push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5841 (isa<SCEVAddRecExpr>(Accum) &&
5842 cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
5846 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5853 if (
GEP->getOperand(0) == PN) {
5878 forgetMemoizedResults(SymbolicName);
5879 insertValueToMap(PN, PHISCEV);
5881 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(PHISCEV)) {
5884 proveNoWrapViaConstantRanges(AR)));
5890 if (
auto *BEInst = dyn_cast<Instruction>(BEValueV))
5907 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5908 const SCEV *Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5912 if (Start == StartVal) {
5916 forgetMemoizedResults(SymbolicName);
5917 insertValueToMap(PN, Shifted);
5927 eraseValueFromMap(PN);
5947 Use &LeftUse =
Merge->getOperandUse(0);
5948 Use &RightUse =
Merge->getOperandUse(1);
5965const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
5982 assert(IDom &&
"At least the entry block should dominate PN");
5991 return createNodeForSelectOrPHI(PN,
Cond, LHS, RHS);
5997const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
5998 if (
const SCEV *S = createAddRecFromPHI(PN))
6004 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6013 struct FindClosure {
6014 const SCEV *OperandToFind;
6020 bool canRecurseInto(
SCEVTypes Kind)
const {
6023 return RootKind == Kind || NonSequentialRootKind == Kind ||
6028 : OperandToFind(OperandToFind), RootKind(RootKind),
6029 NonSequentialRootKind(
6033 bool follow(
const SCEV *S) {
6034 Found = S == OperandToFind;
6036 return !isDone() && canRecurseInto(S->
getSCEVType());
6039 bool isDone()
const {
return Found; }
6042 FindClosure FC(OperandToFind, RootKind);
6047std::optional<const SCEV *>
6048ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6058 switch (ICI->getPredicate()) {
6072 bool Signed = ICI->isSigned();
6081 if (LA == LS &&
RA == RS)
6083 if (LA == RS &&
RA == LS)
6086 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6087 if (
Op->getType()->isPointerTy()) {
6089 if (isa<SCEVCouldNotCompute>(
Op))
6098 LS = CoerceOperand(LS);
6099 RS = CoerceOperand(RS);
6100 if (isa<SCEVCouldNotCompute>(LS) || isa<SCEVCouldNotCompute>(RS))
6121 isa<ConstantInt>(RHS) && cast<ConstantInt>(RHS)->
isZero()) {
6127 if (isa<SCEVConstant>(
C) && cast<SCEVConstant>(
C)->getAPInt().ule(1))
6134 if (isa<ConstantInt>(RHS) && cast<ConstantInt>(RHS)->
isZero() &&
6135 isa<ConstantInt>(TrueVal) && cast<ConstantInt>(TrueVal)->
isZero()) {
6137 while (
auto *ZExt = dyn_cast<SCEVZeroExtendExpr>(
X))
6138 X = ZExt->getOperand();
6151 return std::nullopt;
6154static std::optional<const SCEV *>
6156 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6160 "Unexpected operands of a select.");
6171 if (!isa<SCEVConstant>(TrueExpr) && !isa<SCEVConstant>(FalseExpr))
6172 return std::nullopt;
6175 if (isa<SCEVConstant>(TrueExpr)) {
6187static std::optional<const SCEV *>
6190 if (!isa<ConstantInt>(TrueVal) && !isa<ConstantInt>(FalseVal))
6191 return std::nullopt;
6194 const auto *SETrue = SE->
getSCEV(TrueVal);
6195 const auto *SEFalse = SE->
getSCEV(FalseVal);
6199const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6201 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6203 V->getType() ==
TrueVal->getType() &&
6204 "Types of select hands and of the result must match.");
6207 if (!
V->getType()->isIntegerTy(1))
6210 if (std::optional<const SCEV *> S =
6222 if (
auto *CI = dyn_cast<ConstantInt>(
Cond))
6223 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6225 if (
auto *
I = dyn_cast<Instruction>(V)) {
6226 if (
auto *ICI = dyn_cast<ICmpInst>(
Cond)) {
6227 if (std::optional<const SCEV *> S =
6228 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6234 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6240 assert(
GEP->getSourceElementType()->isSized() &&
6241 "GEP source element type must be sized");
6249APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S) {
6259 for (
unsigned I = 1, E =
N->getNumOperands();
I < E && Res != 1; ++
I)
6267 return cast<SCEVConstant>(S)->getAPInt();
6277 return GetShiftedByZeros(TZ);
6289 if (
M->hasNoUnsignedWrap()) {
6292 for (
const SCEV *Operand :
M->operands().drop_front())
6300 for (
const SCEV *Operand :
M->operands())
6302 return GetShiftedByZeros(TZ);
6307 if (
N->hasNoUnsignedWrap())
6308 return GetGCDMultiple(
N);
6311 for (
const SCEV *Operand :
N->operands().drop_front())
6313 return GetShiftedByZeros(TZ);
6320 return GetGCDMultiple(cast<SCEVNAryExpr>(S));
6326 .countMinTrailingZeros();
6327 return GetShiftedByZeros(Known);
6336 auto I = ConstantMultipleCache.find(S);
6337 if (
I != ConstantMultipleCache.end())
6340 APInt Result = getConstantMultipleImpl(S);
6341 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6342 assert(InsertPair.second &&
"Should insert a new key");
6343 return InsertPair.first->second;
6359 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6361 if (
const auto *CB = dyn_cast<CallBase>(V))
6362 if (std::optional<ConstantRange>
Range = CB->getRange())
6365 if (
auto *
A = dyn_cast<Argument>(V))
6366 if (std::optional<ConstantRange>
Range =
A->getRange())
6369 return std::nullopt;
6376 UnsignedRanges.erase(AddRec);
6377 SignedRanges.erase(AddRec);
6378 ConstantMultipleCache.erase(AddRec);
6383getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6397 auto *
P = dyn_cast<PHINode>(U->getValue());
6409 Value *Start, *Step;
6416 assert(L && L->getHeader() ==
P->getParent());
6429 case Instruction::AShr:
6430 case Instruction::LShr:
6431 case Instruction::Shl:
6446 KnownStep.getBitWidth() ==
BitWidth);
6449 auto MaxShiftAmt = KnownStep.getMaxValue();
6451 bool Overflow =
false;
6452 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6459 case Instruction::AShr: {
6467 if (KnownStart.isNonNegative())
6470 KnownStart.getMaxValue() + 1);
6471 if (KnownStart.isNegative())
6474 KnownEnd.getMaxValue() + 1);
6477 case Instruction::LShr: {
6486 KnownStart.getMaxValue() + 1);
6488 case Instruction::Shl: {
6492 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6494 KnownEnd.getMaxValue() + 1);
6502ScalarEvolution::getRangeRefIter(
const SCEV *S,
6503 ScalarEvolution::RangeSignHint SignHint) {
6505 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6512 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6513 if (!Seen.
insert(Expr).second)
6519 if (!isa<PHINode>(cast<SCEVUnknown>(Expr)->getValue()))
6546 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6547 const SCEV *
P = WorkList[
I];
6548 auto *UnknownS = dyn_cast<SCEVUnknown>(
P);
6551 for (
const SCEV *
Op :
P->operands())
6556 if (
const PHINode *
P = dyn_cast<PHINode>(UnknownS->getValue())) {
6557 if (!PendingPhiRangesIter.insert(
P).second)
6564 if (!WorkList.
empty()) {
6569 getRangeRef(
P, SignHint);
6571 if (
auto *UnknownS = dyn_cast<SCEVUnknown>(
P))
6572 if (
const PHINode *
P = dyn_cast<PHINode>(UnknownS->getValue()))
6573 PendingPhiRangesIter.erase(
P);
6577 return getRangeRef(S, SignHint, 0);
6584 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6586 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6594 if (
I != Cache.
end())
6603 return getRangeRefIter(S, SignHint);
6611 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6615 ConservativeResult =
6638 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6645 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6652 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6657 return setRange(PtrToInt, SignHint,
X);
6662 unsigned WrapType = OBO::AnyWrap;
6663 if (
Add->hasNoSignedWrap())
6664 WrapType |= OBO::NoSignedWrap;
6665 if (
Add->hasNoUnsignedWrap())
6666 WrapType |= OBO::NoUnsignedWrap;
6668 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6670 return setRange(
Add, SignHint,
6671 ConservativeResult.intersectWith(
X, RangeType));
6677 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6678 return setRange(
Mul, SignHint,
6679 ConservativeResult.intersectWith(
X, RangeType));
6685 return setRange(UDiv, SignHint,
6686 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6694 if (!UnsignedMinValue.
isZero())
6695 ConservativeResult = ConservativeResult.intersectWith(
6705 bool AllNonNeg =
true;
6706 bool AllNonPos =
true;
6707 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6714 ConservativeResult = ConservativeResult.intersectWith(
6719 ConservativeResult = ConservativeResult.intersectWith(
6728 const SCEV *MaxBEScev =
6730 if (!isa<SCEVCouldNotCompute>(MaxBEScev)) {
6731 APInt MaxBECount = cast<SCEVConstant>(MaxBEScev)->getAPInt();
6742 auto RangeFromAffine = getRangeForAffineAR(
6744 ConservativeResult =
6745 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6747 auto RangeFromFactoring = getRangeViaFactoring(
6749 ConservativeResult =
6750 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6756 const SCEV *SymbolicMaxBECount =
6758 if (!isa<SCEVCouldNotCompute>(SymbolicMaxBECount) &&
6761 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6762 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6763 ConservativeResult =
6764 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6769 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6779 ID = Intrinsic::umax;
6782 ID = Intrinsic::smax;
6786 ID = Intrinsic::umin;
6789 ID = Intrinsic::smin;
6795 const auto *NAry = cast<SCEVNAryExpr>(S);
6797 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6799 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6800 return setRange(S, SignHint,
6801 ConservativeResult.intersectWith(
X, RangeType));
6810 ConservativeResult =
6811 ConservativeResult.intersectWith(*MDRange, RangeType);
6816 auto CR = getRangeForUnknownRecurrence(U);
6817 ConservativeResult = ConservativeResult.intersectWith(CR);
6828 if (
U->getType()->isPointerTy()) {
6831 unsigned ptrSize =
DL.getPointerTypeSizeInBits(
U->getType());
6832 int ptrIdxDiff = ptrSize -
BitWidth;
6833 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
6846 ConservativeResult = ConservativeResult.intersectWith(
6850 ConservativeResult = ConservativeResult.intersectWith(
6855 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6862 if ((isa<GlobalVariable>(V) || isa<AllocaInst>(V) ||
6878 ConservativeResult = ConservativeResult.intersectWith(
6884 if (
PHINode *Phi = dyn_cast<PHINode>(V)) {
6886 if (PendingPhiRanges.insert(Phi).second) {
6889 for (
const auto &
Op :
Phi->operands()) {
6891 RangeFromOps = RangeFromOps.unionWith(OpRange);
6893 if (RangeFromOps.isFullSet())
6896 ConservativeResult =
6897 ConservativeResult.intersectWith(RangeFromOps, RangeType);
6898 bool Erased = PendingPhiRanges.erase(Phi);
6899 assert(Erased &&
"Failed to erase Phi properly?");
6905 if (
const auto *
II = dyn_cast<IntrinsicInst>(V))
6906 if (
II->getIntrinsicID() == Intrinsic::vscale) {
6908 ConservativeResult = ConservativeResult.difference(Disallowed);
6911 return setRange(U, SignHint, std::move(ConservativeResult));
6917 return setRange(S, SignHint, std::move(ConservativeResult));
6926 const APInt &MaxBECount,
6933 if (Step == 0 || MaxBECount == 0)
6940 return ConstantRange::getFull(
BitWidth);
6956 return ConstantRange::getFull(
BitWidth);
6968 APInt MovedBoundary = Descending ? (StartLower - std::move(
Offset))
6969 : (StartUpper + std::move(
Offset));
6974 if (StartRange.
contains(MovedBoundary))
6975 return ConstantRange::getFull(
BitWidth);
6978 Descending ? std::move(MovedBoundary) : std::move(StartLower);
6980 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
6989 const APInt &MaxBECount) {
6993 "mismatched bit widths");
7002 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7004 StartSRange, MaxBECount,
7016ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7018 ScalarEvolution::RangeSignHint SignHint) {
7019 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7021 "This only works for non-self-wrapping AddRecs!");
7022 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7025 if (!isa<SCEVConstant>(Step))
7026 return ConstantRange::getFull(
BitWidth);
7034 return ConstantRange::getFull(
BitWidth);
7040 MaxItersWithoutWrap))
7041 return ConstantRange::getFull(
BitWidth);
7068 return RangeBetween;
7073 return ConstantRange::getFull(
BitWidth);
7076 isKnownPredicateViaConstantRanges(LEPred, Start,
End))
7077 return RangeBetween;
7079 isKnownPredicateViaConstantRanges(GEPred, Start,
End))
7080 return RangeBetween;
7081 return ConstantRange::getFull(
BitWidth);
7086 const APInt &MaxBECount) {
7093 "mismatched bit widths");
7095 struct SelectPattern {
7096 Value *Condition =
nullptr;
7102 std::optional<unsigned> CastOp;
7109 if (
auto *SA = dyn_cast<SCEVAddExpr>(S)) {
7112 if (SA->getNumOperands() != 2 || !isa<SCEVConstant>(SA->getOperand(0)))
7115 Offset = cast<SCEVConstant>(SA->getOperand(0))->getAPInt();
7116 S = SA->getOperand(1);
7120 if (
auto *SCast = dyn_cast<SCEVIntegralCastExpr>(S)) {
7122 S = SCast->getOperand();
7127 auto *SU = dyn_cast<SCEVUnknown>(S);
7132 Condition =
nullptr;
7164 bool isRecognized() {
return Condition !=
nullptr; }
7167 SelectPattern StartPattern(*
this,
BitWidth, Start);
7168 if (!StartPattern.isRecognized())
7169 return ConstantRange::getFull(
BitWidth);
7171 SelectPattern StepPattern(*
this,
BitWidth, Step);
7172 if (!StepPattern.isRecognized())
7173 return ConstantRange::getFull(
BitWidth);
7175 if (StartPattern.Condition != StepPattern.Condition) {
7179 return ConstantRange::getFull(
BitWidth);
7196 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount);
7198 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount);
7220ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7221 if (
auto *AddRec = dyn_cast<SCEVAddRecExpr>(S))
7223 if (
auto *U = dyn_cast<SCEVUnknown>(S))
7224 if (
auto *
I = dyn_cast<Instruction>(
U->getValue()))
7236 auto pushOp = [&](
const SCEV *S) {
7237 if (!Visited.
insert(S).second)
7240 if (Visited.
size() > 30) {
7247 for (
const auto *S : Ops)
7251 while (!Worklist.
empty()) {
7253 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7254 if (!Bound || DT.
dominates(Bound, DefI))
7267 return getDefiningScopeBound(Ops, Discard);
7270bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7272 if (
A->getParent() ==
B->getParent() &&
7278 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7279 BLoop->getLoopPreheader() ==
A->getParent() &&
7281 A->getParent()->end()) &&
7289bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7306 for (
const Use &
Op :
I->operands()) {
7312 auto *DefI = getDefiningScopeBound(SCEVOps);
7313 return isGuaranteedToTransferExecutionTo(DefI,
I);
7316bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7318 if (isSCEVExprNeverPoison(
I))
7329 auto *ExitingBB =
L->getExitingBlock();
7342 while (!Worklist.
empty()) {
7346 const Instruction *PoisonUser = cast<Instruction>(
U.getUser());
7352 if (KnownPoison.
insert(PoisonUser).second)
7360ScalarEvolution::LoopProperties
7361ScalarEvolution::getLoopProperties(
const Loop *L) {
7362 using LoopProperties = ScalarEvolution::LoopProperties;
7364 auto Itr = LoopPropertiesCache.find(L);
7365 if (Itr == LoopPropertiesCache.end()) {
7367 if (
auto *SI = dyn_cast<StoreInst>(
I))
7368 return !
SI->isSimple();
7370 return I->mayThrow() ||
I->mayWriteToMemory();
7373 LoopProperties LP = {
true,
7376 for (
auto *BB :
L->getBlocks())
7377 for (
auto &
I : *BB) {
7379 LP.HasNoAbnormalExits =
false;
7380 if (HasSideEffects(&
I))
7381 LP.HasNoSideEffects =
false;
7382 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7386 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7387 assert(InsertPair.second &&
"We just checked!");
7388 Itr = InsertPair.first;
7401const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7407 Stack.emplace_back(V,
true);
7408 Stack.emplace_back(V,
false);
7409 while (!Stack.empty()) {
7410 auto E = Stack.pop_back_val();
7411 Value *CurV = E.getPointer();
7417 const SCEV *CreatedSCEV =
nullptr;
7420 CreatedSCEV = createSCEV(CurV);
7425 CreatedSCEV = getOperandsToCreate(CurV, Ops);
7429 insertValueToMap(CurV, CreatedSCEV);
7433 Stack.emplace_back(CurV,
true);
7435 Stack.emplace_back(
Op,
false);
7454 }
else if (
ConstantInt *CI = dyn_cast<ConstantInt>(V))
7456 else if (isa<GlobalAlias>(V))
7458 else if (!isa<ConstantExpr>(V))
7464 bool IsConstArg = isa<ConstantInt>(BO->RHS);
7465 switch (BO->Opcode) {
7466 case Instruction::Add:
7467 case Instruction::Mul: {
7480 dyn_cast<Instruction>(V));
7482 (BO->Opcode == Instruction::Add &&
7483 (NewBO->Opcode != Instruction::Add &&
7484 NewBO->Opcode != Instruction::Sub)) ||
7485 (BO->Opcode == Instruction::Mul &&
7486 NewBO->Opcode != Instruction::Mul)) {
7492 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7493 auto *
I = dyn_cast<Instruction>(BO->
Op);
7503 case Instruction::Sub:
7504 case Instruction::UDiv:
7505 case Instruction::URem:
7507 case Instruction::AShr:
7508 case Instruction::Shl:
7509 case Instruction::Xor:
7513 case Instruction::And:
7514 case Instruction::Or:
7518 case Instruction::LShr:
7530 switch (
U->getOpcode()) {
7531 case Instruction::Trunc:
7532 case Instruction::ZExt:
7533 case Instruction::SExt:
7534 case Instruction::PtrToInt:
7538 case Instruction::BitCast:
7545 case Instruction::SDiv:
7546 case Instruction::SRem:
7551 case Instruction::GetElementPtr:
7552 assert(cast<GEPOperator>(U)->getSourceElementType()->isSized() &&
7553 "GEP source element type must be sized");
7558 case Instruction::IntToPtr:
7561 case Instruction::PHI:
7565 case Instruction::Select: {
7567 auto CanSimplifyToUnknown = [
this,
U]() {
7568 if (
U->getType()->isIntegerTy(1) || isa<ConstantInt>(
U->getOperand(0)))
7571 auto *ICI = dyn_cast<ICmpInst>(
U->getOperand(0));
7578 if (!(isa<ConstantInt>(RHS) && cast<ConstantInt>(RHS)->
isZero()))
7585 if (CanSimplifyToUnknown())
7588 for (
Value *Inc :
U->operands())
7593 case Instruction::Call:
7594 case Instruction::Invoke:
7595 if (
Value *RV = cast<CallBase>(U)->getReturnedArgOperand()) {
7600 if (
auto *
II = dyn_cast<IntrinsicInst>(U)) {
7601 switch (
II->getIntrinsicID()) {
7602 case Intrinsic::abs:
7605 case Intrinsic::umax:
7606 case Intrinsic::umin:
7607 case Intrinsic::smax:
7608 case Intrinsic::smin:
7609 case Intrinsic::usub_sat:
7610 case Intrinsic::uadd_sat:
7614 case Intrinsic::start_loop_iterations:
7615 case Intrinsic::annotation:
7616 case Intrinsic::ptr_annotation:
7629const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7640 }
else if (
ConstantInt *CI = dyn_cast<ConstantInt>(V))
7642 else if (isa<GlobalAlias>(V))
7644 else if (!isa<ConstantExpr>(V))
7653 switch (BO->Opcode) {
7654 case Instruction::Add: {
7680 if (BO->Opcode == Instruction::Sub)
7688 if (BO->Opcode == Instruction::Sub)
7694 dyn_cast<Instruction>(V));
7695 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7696 NewBO->Opcode != Instruction::Sub)) {
7706 case Instruction::Mul: {
7726 dyn_cast<Instruction>(V));
7727 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7736 case Instruction::UDiv:
7740 case Instruction::URem:
7744 case Instruction::Sub: {
7747 Flags = getNoWrapFlagsFromUB(BO->
Op);
7752 case Instruction::And:
7755 if (
ConstantInt *CI = dyn_cast<ConstantInt>(BO->RHS)) {
7758 if (CI->isMinusOne())
7760 const APInt &
A = CI->getValue();
7766 unsigned LZ =
A.countl_zero();
7767 unsigned TZ =
A.countr_zero();
7771 0, &AC,
nullptr, &DT);
7773 APInt EffectiveMask =
7775 if ((LZ != 0 || TZ != 0) && !((~
A & ~Known.
Zero) & EffectiveMask)) {
7778 const SCEV *ShiftedLHS =
nullptr;
7779 if (
auto *LHSMul = dyn_cast<SCEVMulExpr>(LHS)) {
7780 if (
auto *OpC = dyn_cast<SCEVConstant>(LHSMul->getOperand(0))) {
7782 unsigned MulZeros = OpC->getAPInt().countr_zero();
7783 unsigned GCD = std::min(MulZeros, TZ);
7788 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
7810 case Instruction::Or:
7819 case Instruction::Xor:
7820 if (
ConstantInt *CI = dyn_cast<ConstantInt>(BO->RHS)) {
7822 if (CI->isMinusOne())
7829 if (
auto *LBO = dyn_cast<BinaryOperator>(BO->LHS))
7830 if (
ConstantInt *LCI = dyn_cast<ConstantInt>(LBO->getOperand(1)))
7831 if (LBO->getOpcode() == Instruction::And &&
7832 LCI->getValue() == CI->getValue())
7834 dyn_cast<SCEVZeroExtendExpr>(
getSCEV(BO->LHS))) {
7836 const SCEV *Z0 =
Z->getOperand();
7843 if (CI->getValue().isMask(Z0TySize))
7849 APInt Trunc = CI->getValue().
trunc(Z0TySize);
7858 case Instruction::Shl:
7860 if (
ConstantInt *SA = dyn_cast<ConstantInt>(BO->RHS)) {
7876 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
7890 case Instruction::AShr:
7911 Operator *
L = dyn_cast<Operator>(BO->LHS);
7912 const SCEV *AddTruncateExpr =
nullptr;
7914 const SCEV *AddConstant =
nullptr;
7916 if (L &&
L->getOpcode() == Instruction::Add) {
7922 Operator *LShift = dyn_cast<Operator>(
L->getOperand(0));
7923 ConstantInt *AddOperandCI = dyn_cast<ConstantInt>(
L->getOperand(1));
7924 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
7927 ShlAmtCI = dyn_cast<ConstantInt>(LShift->
getOperand(1));
7939 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
7945 ShlAmtCI = dyn_cast<ConstantInt>(
L->getOperand(1));
7949 if (AddTruncateExpr && ShlAmtCI) {
7965 const SCEV *CompositeExpr =
7967 if (
L->getOpcode() != Instruction::Shl)
7968 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
7977 switch (
U->getOpcode()) {
7978 case Instruction::Trunc:
7981 case Instruction::ZExt:
7984 case Instruction::SExt:
7986 dyn_cast<Instruction>(V))) {
7994 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
7995 Type *Ty =
U->getType();
8003 case Instruction::BitCast:
8009 case Instruction::PtrToInt: {
8012 Type *DstIntTy =
U->getType();
8016 if (isa<SCEVCouldNotCompute>(IntOp))
8020 case Instruction::IntToPtr:
8024 case Instruction::SDiv:
8031 case Instruction::SRem:
8038 case Instruction::GetElementPtr:
8039 return createNodeForGEP(cast<GEPOperator>(U));
8041 case Instruction::PHI:
8042 return createNodeForPHI(cast<PHINode>(U));
8044 case Instruction::Select:
8045 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8048 case Instruction::Call:
8049 case Instruction::Invoke:
8050 if (
Value *RV = cast<CallBase>(U)->getReturnedArgOperand())
8053 if (
auto *
II = dyn_cast<IntrinsicInst>(U)) {
8054 switch (
II->getIntrinsicID()) {
8055 case Intrinsic::abs:
8058 cast<ConstantInt>(
II->getArgOperand(1))->
isOne());
8059 case Intrinsic::umax:
8063 case Intrinsic::umin:
8067 case Intrinsic::smax:
8071 case Intrinsic::smin:
8075 case Intrinsic::usub_sat: {
8081 case Intrinsic::uadd_sat: {
8087 case Intrinsic::start_loop_iterations:
8088 case Intrinsic::annotation:
8089 case Intrinsic::ptr_annotation:
8093 case Intrinsic::vscale:
8110 if (isa<SCEVCouldNotCompute>(ExitCount))
8113 auto *ExitCountType = ExitCount->
getType();
8114 assert(ExitCountType->isIntegerTy());
8116 1 + ExitCountType->getScalarSizeInBits());
8123 if (isa<SCEVCouldNotCompute>(ExitCount))
8129 auto CanAddOneWithoutOverflow = [&]() {
8131 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8142 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8172 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8173 assert(L->isLoopExiting(ExitingBlock) &&
8174 "Exiting block must actually branch out of the loop!");
8181 const auto *MaxExitCount =
8188 L->getExitingBlocks(ExitingBlocks);
8190 std::optional<unsigned> Res;
8191 for (
auto *ExitingBB : ExitingBlocks) {
8195 Res = (
unsigned)std::gcd(*Res, Multiple);
8197 return Res.value_or(1);
8201 const SCEV *ExitCount) {
8231 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8232 assert(L->isLoopExiting(ExitingBlock) &&
8233 "Exiting block must actually branch out of the loop!");
8243 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8245 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8247 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8255 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8262 return getBackedgeTakenInfo(L).getExact(L,
this);
8264 return getBackedgeTakenInfo(L).getConstantMax(
this);
8266 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8273 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8277 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8287 for (
PHINode &PN : Header->phis())
8288 if (Visited.
insert(&PN).second)
8292ScalarEvolution::BackedgeTakenInfo &
8293ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8294 auto &BTI = getBackedgeTakenInfo(L);
8295 if (BTI.hasFullInfo())
8298 auto Pair = PredicatedBackedgeTakenCounts.insert({
L, BackedgeTakenInfo()});
8301 return Pair.first->second;
8303 BackedgeTakenInfo
Result =
8304 computeBackedgeTakenCount(L,
true);
8306 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8309ScalarEvolution::BackedgeTakenInfo &
8310ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8316 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8317 BackedgeTakenCounts.insert({
L, BackedgeTakenInfo()});
8319 return Pair.first->second;
8324 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8331 if (
Result.hasAnyInfo()) {
8334 auto LoopUsersIt = LoopUsers.find(L);
8335 if (LoopUsersIt != LoopUsers.end())
8337 forgetMemoizedResults(ToForget);
8340 for (
PHINode &PN :
L->getHeader()->phis())
8341 ConstantEvolutionLoopExitValue.erase(&PN);
8349 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8358 BackedgeTakenCounts.clear();
8359 PredicatedBackedgeTakenCounts.clear();
8360 BECountUsers.clear();
8361 LoopPropertiesCache.clear();
8362 ConstantEvolutionLoopExitValue.clear();
8363 ValueExprMap.
clear();
8364 ValuesAtScopes.clear();
8365 ValuesAtScopesUsers.clear();
8366 LoopDispositions.clear();
8367 BlockDispositions.clear();
8368 UnsignedRanges.clear();
8369 SignedRanges.clear();
8370 ExprValueMap.
clear();
8372 ConstantMultipleCache.clear();
8373 PredicatedSCEVRewrites.clear();
8375 FoldCacheUser.clear();
8377void ScalarEvolution::visitAndClearUsers(
8381 while (!Worklist.
empty()) {
8383 if (!
isSCEVable(
I->getType()) && !isa<WithOverflowInst>(
I))
8388 if (It != ValueExprMap.
end()) {
8389 eraseValueFromMap(It->first);
8391 if (
PHINode *PN = dyn_cast<PHINode>(
I))
8392 ConstantEvolutionLoopExitValue.erase(PN);
8406 while (!LoopWorklist.
empty()) {
8410 forgetBackedgeTakenCounts(CurrL,
false);
8411 forgetBackedgeTakenCounts(CurrL,
true);
8414 for (
auto I = PredicatedSCEVRewrites.begin();
8415 I != PredicatedSCEVRewrites.end();) {
8416 std::pair<const SCEV *, const Loop *> Entry =
I->first;
8417 if (Entry.second == CurrL)
8418 PredicatedSCEVRewrites.erase(
I++);
8423 auto LoopUsersItr = LoopUsers.find(CurrL);
8424 if (LoopUsersItr != LoopUsers.end()) {
8425 ToForget.
insert(ToForget.
end(), LoopUsersItr->second.begin(),
8426 LoopUsersItr->second.end());
8431 visitAndClearUsers(Worklist, Visited, ToForget);
8433 LoopPropertiesCache.erase(CurrL);
8436 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8438 forgetMemoizedResults(ToForget);
8455 visitAndClearUsers(Worklist, Visited, ToForget);
8457 forgetMemoizedResults(ToForget);
8469 struct InvalidationRootCollector {
8473 InvalidationRootCollector(
Loop *L) : L(L) {}
8475 bool follow(
const SCEV *S) {
8476 if (
auto *SU = dyn_cast<SCEVUnknown>(S)) {
8477 if (
auto *
I = dyn_cast<Instruction>(SU->getValue()))
8480 }
else if (
auto *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
8481 if (L->contains(AddRec->
getLoop()))
8486 bool isDone()
const {
return false; }
8489 InvalidationRootCollector
C(L);
8491 forgetMemoizedResults(
C.Roots);
8504 BlockDispositions.clear();
8505 LoopDispositions.clear();
8522 while (!Worklist.
empty()) {
8524 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8525 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8526 if (!LoopDispoRemoved && !BlockDispoRemoved)
8528 auto Users = SCEVUsers.find(Curr);
8529 if (
Users != SCEVUsers.end())
8546 if (!isComplete() || ExitNotTaken.empty())
8557 for (
const auto &ENT : ExitNotTaken) {
8558 const SCEV *BECount = ENT.ExactNotTaken;
8561 "We should only have known counts for exiting blocks that dominate "
8567 for (
const auto *
P : ENT.Predicates)
8570 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8571 "Predicate should be always true!");
8582ScalarEvolution::BackedgeTakenInfo::getExact(
const BasicBlock *ExitingBlock,
8584 for (
const auto &ENT : ExitNotTaken)
8585 if (ENT.ExitingBlock == ExitingBlock && ENT.hasAlwaysTruePredicate())
8586 return ENT.ExactNotTaken;
8591const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8593 for (
const auto &ENT : ExitNotTaken)
8594 if (ENT.ExitingBlock == ExitingBlock && ENT.hasAlwaysTruePredicate())
8595 return ENT.ConstantMaxNotTaken;
8600const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8602 for (
const auto &ENT : ExitNotTaken)
8603 if (ENT.ExitingBlock == ExitingBlock && ENT.hasAlwaysTruePredicate())
8604 return ENT.SymbolicMaxNotTaken;
8611ScalarEvolution::BackedgeTakenInfo::getConstantMax(
ScalarEvolution *SE)
const {
8612 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8613 return !ENT.hasAlwaysTruePredicate();
8616 if (!getConstantMax() ||
any_of(ExitNotTaken, PredicateNotAlwaysTrue))
8619 assert((isa<SCEVCouldNotCompute>(getConstantMax()) ||
8620 isa<SCEVConstant>(getConstantMax())) &&
8621 "No point in having a non-constant max backedge taken count!");
8622 return getConstantMax();
8625const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8635 for (
const auto &ENT : ExitNotTaken) {
8636 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8637 if (!isa<SCEVCouldNotCompute>(ExitCount)) {
8639 "We should only have known counts for exiting blocks that "
8643 for (
const auto *
P : ENT.Predicates)
8646 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8647 "Predicate should be always true!");
8650 if (ExitCounts.
empty())
8659bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8661 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8662 return !ENT.hasAlwaysTruePredicate();
8664 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8671 const SCEV *E,
const SCEV *ConstantMaxNotTaken,
8672 const SCEV *SymbolicMaxNotTaken,
bool MaxOrZero,
8674 : ExactNotTaken(E), ConstantMaxNotTaken(ConstantMaxNotTaken),
8675 SymbolicMaxNotTaken(SymbolicMaxNotTaken), MaxOrZero(MaxOrZero) {
8686 "Exact is not allowed to be less precise than Constant Max");
8689 "Exact is not allowed to be less precise than Symbolic Max");
8692 "Symbolic Max is not allowed to be less precise than Constant Max");
8695 "No point in having a non-constant max backedge taken count!");
8696 for (
const auto *PredSet : PredSetList)
8697 for (
const auto *
P : *PredSet)
8700 "Backedge count should be int");
8703 "Max backedge count should be int");
8707 const SCEV *E,
const SCEV *ConstantMaxNotTaken,
8708 const SCEV *SymbolicMaxNotTaken,
bool MaxOrZero,
8710 :
ExitLimit(E, ConstantMaxNotTaken, SymbolicMaxNotTaken, MaxOrZero,
8715ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8717 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8718 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8719 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8721 ExitNotTaken.reserve(ExitCounts.
size());
8722 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8723 std::back_inserter(ExitNotTaken),
8724 [&](
const EdgeExitInfo &EEI) {
8725 BasicBlock *ExitBB = EEI.first;
8726 const ExitLimit &EL = EEI.second;
8727 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
8728 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
8731 assert((isa<SCEVCouldNotCompute>(ConstantMax) ||
8732 isa<SCEVConstant>(ConstantMax)) &&
8733 "No point in having a non-constant max backedge taken count!");
8737ScalarEvolution::BackedgeTakenInfo
8738ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
8739 bool AllowPredicates) {
8741 L->getExitingBlocks(ExitingBlocks);
8743 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8746 bool CouldComputeBECount =
true;
8748 const SCEV *MustExitMaxBECount =
nullptr;
8749 const SCEV *MayExitMaxBECount =
nullptr;
8750 bool MustExitMaxOrZero =
false;
8751 bool IsOnlyExit = ExitingBlocks.
size() == 1;
8760 if (
auto *BI = dyn_cast<BranchInst>(ExitBB->getTerminator()))
8761 if (
auto *CI = dyn_cast<ConstantInt>(BI->
getCondition())) {
8763 if (ExitIfTrue == CI->
isZero())
8767 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
8769 assert((AllowPredicates || EL.Predicates.empty()) &&
8770 "Predicated exit limit when predicates are not allowed!");
8775 ++NumExitCountsComputed;
8779 CouldComputeBECount =
false;
8786 "Exact is known but symbolic isn't?");
8787 ++NumExitCountsNotComputed;
8803 if (!MustExitMaxBECount) {
8804 MustExitMaxBECount = EL.ConstantMaxNotTaken;
8805 MustExitMaxOrZero = EL.MaxOrZero;
8808 EL.ConstantMaxNotTaken);
8812 MayExitMaxBECount = EL.ConstantMaxNotTaken;
8815 EL.ConstantMaxNotTaken);
8819 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
8823 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
8829 for (
const auto &Pair : ExitCounts) {
8830 if (!isa<SCEVConstant>(Pair.second.ExactNotTaken))
8831 BECountUsers[Pair.second.ExactNotTaken].insert({L, AllowPredicates});
8832 if (!isa<SCEVConstant>(Pair.second.SymbolicMaxNotTaken))
8833 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
8834 {L, AllowPredicates});
8836 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
8837 MaxBECount, MaxOrZero);
8841ScalarEvolution::computeExitLimit(
const Loop *L,
BasicBlock *ExitingBlock,
8842 bool IsOnlyExit,
bool AllowPredicates) {
8843 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
8847 if (!Latch || !DT.
dominates(ExitingBlock, Latch))
8851 if (
BranchInst *BI = dyn_cast<BranchInst>(Term)) {
8855 "It should have one successor in loop and one exit block!");
8862 if (
SwitchInst *SI = dyn_cast<SwitchInst>(Term)) {
8866 if (!
L->contains(SBB)) {
8871 assert(Exit &&
"Exiting block must have at least one exit");
8872 return computeExitLimitFromSingleExitSwitch(
8873 L, SI, Exit, IsOnlyExit);
8880 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
8881 bool AllowPredicates) {
8882 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
8883 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
8884 ControlsOnlyExit, AllowPredicates);
8887std::optional<ScalarEvolution::ExitLimit>
8888ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
8889 bool ExitIfTrue,
bool ControlsOnlyExit,
8890 bool AllowPredicates) {
8892 (void)this->ExitIfTrue;
8893 (void)this->AllowPredicates;
8895 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
8896 this->AllowPredicates == AllowPredicates &&
8897 "Variance in assumed invariant key components!");
8898 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
8899 if (Itr == TripCountMap.end())
8900 return std::nullopt;
8904void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
8906 bool ControlsOnlyExit,
8907 bool AllowPredicates,
8908 const ExitLimit &EL) {
8909 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
8910 this->AllowPredicates == AllowPredicates &&
8911 "Variance in assumed invariant key components!");
8913 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
8914 assert(InsertResult.second &&
"Expected successful insertion!");
8920 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
8921 bool ControlsOnlyExit,
bool AllowPredicates) {
8923 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
8927 ExitLimit EL = computeExitLimitFromCondImpl(
8928 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
8929 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
8934 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
8935 bool ControlsOnlyExit,
bool AllowPredicates) {
8937 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
8938 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates))
8939 return *LimitFromBinOp;
8943 if (
ICmpInst *ExitCondICmp = dyn_cast<ICmpInst>(ExitCond)) {
8945 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
8946 if (EL.hasFullInfo() || !AllowPredicates)
8950 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
8959 if (
ConstantInt *CI = dyn_cast<ConstantInt>(ExitCond)) {
8985 auto EL = computeExitLimitFromICmp(L, Pred, LHS,
getConstant(NewRHSC),
8986 ControlsOnlyExit, AllowPredicates);
8987 if (EL.hasAnyInfo())
8992 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
8995std::optional<ScalarEvolution::ExitLimit>
8996ScalarEvolution::computeExitLimitFromCondFromBinOp(
8997 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
8998 bool ControlsOnlyExit,
bool AllowPredicates) {
9007 return std::nullopt;
9012 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9013 ExitLimit EL0 = computeExitLimitFromCondCached(
9014 Cache, L, Op0, ExitIfTrue, ControlsOnlyExit && !EitherMayExit,
9016 ExitLimit EL1 = computeExitLimitFromCondCached(
9017 Cache, L, Op1, ExitIfTrue, ControlsOnlyExit && !EitherMayExit,
9021 const Constant *NeutralElement = ConstantInt::get(ExitCond->
getType(), IsAnd);
9022 if (isa<ConstantInt>(Op1))
9023 return Op1 == NeutralElement ? EL0 : EL1;
9024 if (isa<ConstantInt>(Op0))
9025 return Op0 == NeutralElement ? EL1 : EL0;
9030 if (EitherMayExit) {
9031 bool UseSequentialUMin = !isa<BinaryOperator>(ExitCond);
9040 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9042 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9045 EL1.ConstantMaxNotTaken);
9047 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9049 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9052 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9056 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9057 BECount = EL0.ExactNotTaken;
9066 if (isa<SCEVCouldNotCompute>(ConstantMaxBECount) &&
9067 !isa<SCEVCouldNotCompute>(BECount))
9069 if (isa<SCEVCouldNotCompute>(SymbolicMaxBECount))
9070 SymbolicMaxBECount =
9071 isa<SCEVCouldNotCompute>(BECount) ? ConstantMaxBECount : BECount;
9072 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9073 { &EL0.Predicates, &EL1.Predicates });
9077 const Loop *L,
ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9078 bool AllowPredicates) {
9090 ExitLimit EL = computeExitLimitFromICmp(L, Pred, LHS, RHS, ControlsOnlyExit,
9092 if (EL.hasAnyInfo())
9095 auto *ExhaustiveCount =
9096 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9098 if (!isa<SCEVCouldNotCompute>(ExhaustiveCount))
9099 return ExhaustiveCount;
9101 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9106 bool ControlsOnlyExit,
bool AllowPredicates) {
9127 if (
const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS))
9128 if (
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
9135 if (!isa<SCEVCouldNotCompute>(Ret))
return Ret;
9147 auto *InnerLHS =
LHS;
9148 if (
auto *ZExt = dyn_cast<SCEVZeroExtendExpr>(LHS))
9149 InnerLHS = ZExt->getOperand();
9150 if (
const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(InnerLHS);
9186 if (isa<SCEVCouldNotCompute>(LHS))
9191 if (isa<SCEVCouldNotCompute>(RHS))
9194 ExitLimit EL = howFarToZero(
getMinusSCEV(LHS, RHS), L, ControlsOnlyExit,
9196 if (EL.hasAnyInfo())
9204 if (isa<SCEVCouldNotCompute>(LHS))
9209 if (isa<SCEVCouldNotCompute>(RHS))
9212 ExitLimit EL = howFarToNonZero(
getMinusSCEV(LHS, RHS), L);
9213 if (EL.hasAnyInfo())
return EL;
9225 auto *OldType = dyn_cast<IntegerType>(
LHS->
getType());
9245 ExitLimit EL = howManyLessThans(LHS, RHS, L, IsSigned, ControlsOnlyExit,
9247 if (EL.hasAnyInfo())
9263 ExitLimit EL = howManyGreaterThans(LHS, RHS, L, IsSigned, ControlsOnlyExit,
9265 if (EL.hasAnyInfo())
9277ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9280 bool ControlsOnlyExit) {
9281 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9284 if (
Switch->getDefaultDest() == ExitingBlock)
9288 "Default case must not exit the loop!");
9293 ExitLimit EL = howFarToZero(
getMinusSCEV(LHS, RHS), L, ControlsOnlyExit);
9294 if (EL.hasAnyInfo())
9305 assert(isa<SCEVConstant>(Val) &&
9306 "Evaluation of SCEV at constant didn't fold correctly?");
9307 return cast<SCEVConstant>(Val)->getValue();
9320 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9326 auto MatchPositiveShift =
9329 using namespace PatternMatch;
9333 OutOpCode = Instruction::LShr;
9335 OutOpCode = Instruction::AShr;
9337 OutOpCode = Instruction::Shl;
9352 auto MatchShiftRecurrence =
9354 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9369 if (MatchPositiveShift(LHS, V, OpC)) {
9370 PostShiftOpCode = OpC;
9375 PNOut = dyn_cast<PHINode>(LHS);
9376 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9379 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9385 MatchPositiveShift(BEValue, OpLHS, OpCodeOut) &&
9392 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9397 if (!MatchShiftRecurrence(LHS, PN, OpCode))
9414 case Instruction::AShr: {
9420 auto *Ty = cast<IntegerType>(
RHS->
getType());
9422 StableValue = ConstantInt::get(Ty, 0);
9424 StableValue = ConstantInt::get(Ty, -1,
true);
9430 case Instruction::LShr:
9431 case Instruction::Shl:
9434 StableValue = ConstantInt::get(cast<IntegerType>(
RHS->
getType()), 0);
9441 "Otherwise cannot be an operand to a branch instruction");
9443 if (
Result->isZeroValue()) {
9445 const SCEV *UpperBound =
9456 if (isa<BinaryOperator>(
I) || isa<CmpInst>(
I) ||
9457 isa<SelectInst>(
I) || isa<CastInst>(
I) || isa<GetElementPtrInst>(
I) ||
9458 isa<LoadInst>(
I) || isa<ExtractValueInst>(
I))
9461 if (
const CallInst *CI = dyn_cast<CallInst>(
I))
9462 if (
const Function *F = CI->getCalledFunction())
9471 if (!L->contains(
I))
return false;
9473 if (isa<PHINode>(
I)) {
9476 return L->getHeader() ==
I->getParent();
9497 if (isa<Constant>(
Op))
continue;
9502 PHINode *
P = dyn_cast<PHINode>(OpInst);
9533 if (
PHINode *PN = dyn_cast<PHINode>(
I))
9550 if (
Constant *
C = dyn_cast<Constant>(V))
return C;
9552 if (!
I)
return nullptr;
9563 if (isa<PHINode>(
I))
return nullptr;
9565 std::vector<Constant*>
Operands(
I->getNumOperands());
9567 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9568 Instruction *Operand = dyn_cast<Instruction>(
I->getOperand(i));
9570 Operands[i] = dyn_cast<Constant>(
I->getOperand(i));
9576 if (!
C)
return nullptr;
9598 if (IncomingVal != CurrentVal) {
9601 IncomingVal = CurrentVal;
9613ScalarEvolution::getConstantEvolutionLoopExitValue(
PHINode *PN,
9616 auto I = ConstantEvolutionLoopExitValue.find(PN);
9617 if (
I != ConstantEvolutionLoopExitValue.end())
9621 return ConstantEvolutionLoopExitValue[PN] =
nullptr;
9623 Constant *&RetVal = ConstantEvolutionLoopExitValue[PN];
9627 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9635 CurrentIterVals[&
PHI] = StartCST;
9637 if (!CurrentIterVals.
count(PN))
9638 return RetVal =
nullptr;
9644 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9647 unsigned IterationNum = 0;
9649 for (; ; ++IterationNum) {
9650 if (IterationNum == NumIterations)
9651 return RetVal = CurrentIterVals[PN];
9660 NextIterVals[PN] = NextPHI;
9662 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9668 for (
const auto &
I : CurrentIterVals) {
9670 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9675 for (
const auto &
I : PHIsToCompute) {
9679 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9682 if (NextPHI !=
I.second)
9683 StoppedEvolving =
false;
9688 if (StoppedEvolving)
9689 return RetVal = CurrentIterVals[PN];
9691 CurrentIterVals.swap(NextIterVals);
9695const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
9707 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9710 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
9714 CurrentIterVals[&
PHI] = StartCST;
9716 if (!CurrentIterVals.
count(PN))
9724 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
9725 auto *CondVal = dyn_cast_or_null<ConstantInt>(
9731 if (CondVal->getValue() ==
uint64_t(ExitWhen)) {
9732 ++NumBruteForceTripCountsComputed;
9743 for (
const auto &
I : CurrentIterVals) {
9745 if (!
PHI ||
PHI->getParent() != Header)
continue;
9750 if (NextPHI)
continue;
9752 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9755 CurrentIterVals.swap(NextIterVals);
9766 for (
auto &LS : Values)
9768 return LS.second ? LS.second : V;
9773 const SCEV *
C = computeSCEVAtScope(V, L);
9774 for (
auto &LS :
reverse(ValuesAtScopes[V]))
9775 if (LS.first == L) {
9777 if (!isa<SCEVConstant>(
C))
9778 ValuesAtScopesUsers[
C].push_back({L, V});
9789 switch (V->getSCEVType()) {
9795 return cast<SCEVConstant>(V)->getValue();
9797 return dyn_cast<Constant>(cast<SCEVUnknown>(V)->getValue());
9822 assert(!
C->getType()->isPointerTy() &&
9823 "Can only have one pointer, and it must be last");
9850ScalarEvolution::getWithOperands(
const SCEV *S,
9859 auto *AddRec = cast<SCEVAddRecExpr>(S);
9863 return getAddExpr(NewOps, cast<SCEVAddExpr>(S)->getNoWrapFlags());
9865 return getMulExpr(NewOps, cast<SCEVMulExpr>(S)->getNoWrapFlags());
9885const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
9886 switch (
V->getSCEVType()) {
9897 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
9908 for (++i; i !=
e; ++i)
9913 AddRec = dyn_cast<SCEVAddRecExpr>(FoldedRec);
9952 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
9954 if (OpAtScope != Ops[i]) {
9962 for (++i; i !=
e; ++i) {
9967 return getWithOperands(V, NewOps);
9981 if (
PHINode *PN = dyn_cast<PHINode>(
I)) {
9982 const Loop *CurrLoop = this->LI[
I->getParent()];
9993 if (BackedgeTakenCount->
isZero()) {
9994 Value *InitValue =
nullptr;
9995 bool MultipleInitValues =
false;
10001 MultipleInitValues =
true;
10006 if (!MultipleInitValues && InitValue)
10011 if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) &&
10015 unsigned InLoopPred =
10021 if (
auto *BTCC = dyn_cast<SCEVConstant>(BackedgeTakenCount)) {
10026 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10042 bool MadeImprovement =
false;
10057 MadeImprovement |= OrigV != OpV;
10062 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10067 if (!MadeImprovement)
10088const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10090 return stripInjectiveFunctions(ZExt->getOperand());
10092 return stripInjectiveFunctions(SExt->getOperand());
10108 assert(
A != 0 &&
"A must be non-zero.");
10130 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10150static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10156 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10157 << *AddRec <<
'\n');
10160 if (!LC || !MC || !
NC) {
10161 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10162 return std::nullopt;
10168 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10176 N =
N.sext(NewWidth);
10177 M = M.sext(NewWidth);
10178 L = L.sext(NewWidth);
10195 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10196 <<
", multiplied by " <<
T <<
'\n');
10205 std::optional<APInt>
Y) {
10207 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10210 return XW.
slt(YW) ? *
X : *
Y;
10213 return std::nullopt;
10214 return X ? *
X : *
Y;
10231 return std::nullopt;
10232 unsigned W =
X->getBitWidth();
10252static std::optional<APInt>
10258 return std::nullopt;
10261 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10262 std::optional<APInt>
X =
10265 return std::nullopt;
10270 return std::nullopt;
10285static std::optional<APInt>
10289 "Starting value of addrec should be 0");
10290 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10291 <<
Range <<
", addrec " << *AddRec <<
'\n');
10295 "Addrec's initial value should be in range");
10301 return std::nullopt;
10311 auto SolveForBoundary =
10312 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10315 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10316 << Bound <<
" (before multiplying by " << M <<
")\n");
10319 std::optional<APInt> SO;
10322 "signed overflow\n");
10326 "unsigned overflow\n");
10327 std::optional<APInt> UO =
10330 auto LeavesRange = [&] (
const APInt &
X) {
10347 return {std::nullopt,
false};
10352 if (LeavesRange(*Min))
10353 return { Min,
true };
10354 std::optional<APInt> Max = Min == SO ? UO : SO;
10355 if (LeavesRange(*Max))
10356 return { Max,
true };
10359 return {std::nullopt,
true};
10366 auto SL = SolveForBoundary(
Lower);
10367 auto SU = SolveForBoundary(
Upper);
10370 if (!SL.second || !SU.second)
10371 return std::nullopt;
10416 bool ControlsOnlyExit,
10417 bool AllowPredicates) {
10428 if (
C->getValue()->isZero())
return C;
10433 dyn_cast<SCEVAddRecExpr>(stripInjectiveFunctions(V));
10435 if (!AddRec && AllowPredicates)
10441 if (!AddRec || AddRec->
getLoop() != L)
10452 return ExitLimit(R, R, R,
false, Predicates);
10475 const SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step);
10518 return ExitLimit(Distance,
getConstant(MaxBECount), Distance,
false,
10544 const SCEV *SymbolicMax =
10545 isa<SCEVCouldNotCompute>(
Exact) ? ConstantMax :
Exact;
10546 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10560 auto *S = isa<SCEVCouldNotCompute>(E) ?
M : E;
10561 return ExitLimit(E, M, S,
false, Predicates);
10565ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10573 if (!
C->getValue()->isZero())
10583std::pair<const BasicBlock *, const BasicBlock *>
10584ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10596 return {
L->getLoopPredecessor(),
L->getHeader()};
10598 return {
nullptr,
nullptr};
10607 if (
A ==
B)
return true;
10613 return A->isIdenticalTo(
B) && (isa<BinaryOperator>(
A) || isa<GetElementPtrInst>(
A));
10620 if (
const Instruction *AI = dyn_cast<Instruction>(AU->getValue()))
10621 if (
const Instruction *BI = dyn_cast<Instruction>(BU->getValue()))
10622 if (ComputesEqualValues(AI, BI))
10631 if (!
Add ||
Add->getNumOperands() != 2)
10633 if (
auto *ME = dyn_cast<SCEVMulExpr>(
Add->getOperand(0));
10634 ME && ME->getNumOperands() == 2 && ME->getOperand(0)->isAllOnesValue()) {
10635 LHS =
Add->getOperand(1);
10636 RHS = ME->getOperand(1);
10639 if (
auto *ME = dyn_cast<SCEVMulExpr>(
Add->getOperand(1));
10640 ME && ME->getNumOperands() == 2 && ME->getOperand(0)->isAllOnesValue()) {
10641 LHS =
Add->getOperand(0);
10642 RHS = ME->getOperand(1);
10649 const SCEV *&LHS,
const SCEV *&RHS,
10651 bool Changed =
false;
10654 auto TrivialCase = [&](
bool TriviallyTrue) {
10668 return TrivialCase(
false);
10669 return TrivialCase(
true);
10692 const APInt &
RA = RC->getAPInt();
10694 bool SimplifiedByConstantRange =
false;
10699 return TrivialCase(
true);
10701 return TrivialCase(
false);
10710 Changed = SimplifiedByConstantRange =
true;
10714 if (!SimplifiedByConstantRange) {
10731 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
10737 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
10743 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
10749 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
10761 return TrivialCase(
true);
10763 return TrivialCase(
false);
10852 if (
const auto *SExt = dyn_cast<SCEVSignExtendExpr>(S))
10859 auto NonRecursive = [
this, OrNegative](
const SCEV *S) {
10860 if (
auto *
C = dyn_cast<SCEVConstant>(S))
10861 return C->getAPInt().isPowerOf2() ||
10862 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
10865 return isa<SCEVVScale>(S) && F.
hasFnAttribute(Attribute::VScaleRange);
10868 if (NonRecursive(S))
10871 auto *
Mul = dyn_cast<SCEVMulExpr>(S);
10877std::pair<const SCEV *, const SCEV *>
10880 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
10882 return { Start, Start };
10884 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
10890 const SCEV *LHS,
const SCEV *RHS) {
10893 getUsedLoops(
LHS, LoopsUsed);
10894 getUsedLoops(
RHS, LoopsUsed);
10896 if (LoopsUsed.
empty())
10901 for (
const auto *L1 : LoopsUsed)
10902 for (
const auto *L2 : LoopsUsed)
10904 DT.
dominates(L2->getHeader(), L1->getHeader())) &&
10905 "Domination relationship is not a linear order");
10935 SplitRHS.second) &&
10940 const SCEV *LHS,
const SCEV *RHS) {
10947 if (isKnownPredicateViaSplitting(Pred,
LHS,
RHS))
10951 return isKnownViaNonRecursiveReasoning(Pred,
LHS,
RHS);
10961 return std::nullopt;
10976 if (KnownWithoutContext)
10977 return KnownWithoutContext;
10985 return std::nullopt;
10991 const Loop *L =
LHS->getLoop();
10996std::optional<ScalarEvolution::MonotonicPredicateType>
10999 auto Result = getMonotonicPredicateTypeImpl(
LHS, Pred);
11005 auto ResultSwapped =
11008 assert(*ResultSwapped != *Result &&
11009 "monotonicity should flip as we flip the predicate");
11016std::optional<ScalarEvolution::MonotonicPredicateType>
11017ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11031 return std::nullopt;
11035 "Should be greater or less!");
11039 if (!
LHS->hasNoUnsignedWrap())
11040 return std::nullopt;
11044 "Relational predicate is either signed or unsigned!");
11045 if (!
LHS->hasNoSignedWrap())
11046 return std::nullopt;
11048 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11056 return std::nullopt;
11059std::optional<ScalarEvolution::LoopInvariantPredicate>
11067 return std::nullopt;
11074 if (!ArLHS || ArLHS->
getLoop() != L)
11075 return std::nullopt;
11078 if (!MonotonicType)
11079 return std::nullopt;
11105 return std::nullopt;
11142 return std::nullopt;
11145std::optional<ScalarEvolution::LoopInvariantPredicate>
11150 Pred,
LHS,
RHS, L, CtxI, MaxIter))
11152 if (
auto *
UMin = dyn_cast<SCEVUMinExpr>(MaxIter))
11158 for (
auto *
Op :
UMin->operands())
11162 return std::nullopt;
11165std::optional<ScalarEvolution::LoopInvariantPredicate>
11180 return std::nullopt;
11186 auto *AR = dyn_cast<SCEVAddRecExpr>(
LHS);
11187 if (!AR || AR->
getLoop() != L)
11188 return std::nullopt;
11192 return std::nullopt;
11198 if (Step != One && Step != MinusOne)
11199 return std::nullopt;
11205 return std::nullopt;
11211 return std::nullopt;
11219 if (Step == MinusOne)
11223 return std::nullopt;
11229bool ScalarEvolution::isKnownPredicateViaConstantRanges(
11239 return RangeLHS.
icmp(Pred, RangeRHS);
11250 if (CheckRanges(SL, SR))
11254 if (CheckRanges(UL, UR))
11263 return CheckRanges(SL, SR);
11268 return CheckRanges(UL, UR);
11278 auto MatchBinaryAddToConst = [
this](
const SCEV *
X,
const SCEV *
Y,
11281 const SCEV *XNonConstOp, *XConstOp;
11282 const SCEV *YNonConstOp, *YConstOp;
11286 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11289 XFlagsPresent = ExpectedFlags;
11291 if (!isa<SCEVConstant>(XConstOp) ||
11292 (XFlagsPresent & ExpectedFlags) != ExpectedFlags)
11295 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11298 YFlagsPresent = ExpectedFlags;
11301 if (!isa<SCEVConstant>(YConstOp) ||
11302 (YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11305 if (YNonConstOp != XNonConstOp)
11308 OutC1 = cast<SCEVConstant>(XConstOp)->getAPInt();
11309 OutC2 = cast<SCEVConstant>(YConstOp)->getAPInt();
11386bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB,
11388 const SCEV *LHS,
const SCEV *RHS) {
11397 return match(&
I, m_Intrinsic<Intrinsic::experimental_guard>(
11399 isImpliedCond(Pred, LHS, RHS, Condition,
false);
11409 const SCEV *LHS,
const SCEV *RHS) {
11418 "This cannot be done on broken IR!");
11421 if (isKnownViaNonRecursiveReasoning(Pred,
LHS,
RHS))
11430 if (LoopContinuePredicate && LoopContinuePredicate->
isConditional() &&
11431 isImpliedCond(Pred,
LHS,
RHS,
11433 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11438 if (WalkingBEDominatingConds)
11444 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11445 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11452 const SCEV *LoopCounter =
11463 auto *CI = cast<CallInst>(AssumeVH);
11467 if (isImpliedCond(Pred,
LHS,
RHS, CI->getArgOperand(0),
false))
11471 if (isImpliedViaGuard(Latch, Pred,
LHS,
RHS))
11474 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11475 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11476 assert(DTN &&
"should reach the loop header before reaching the root!");
11479 if (isImpliedViaGuard(BB, Pred,
LHS,
RHS))
11487 if (!ContinuePredicate || !ContinuePredicate->
isConditional())
11503 if (isImpliedCond(Pred,
LHS,
RHS, Condition,
11521 "This cannot be done on broken IR!");
11529 const bool ProvingStrictComparison = (Pred != NonStrictPredicate);
11530 bool ProvedNonStrictComparison =
false;
11531 bool ProvedNonEquality =
false;
11533 auto SplitAndProve =
11535 if (!ProvedNonStrictComparison)
11536 ProvedNonStrictComparison = Fn(NonStrictPredicate);
11537 if (!ProvedNonEquality)
11539 if (ProvedNonStrictComparison && ProvedNonEquality)
11544 if (ProvingStrictComparison) {
11546 return isKnownViaNonRecursiveReasoning(
P,
LHS,
RHS);
11548 if (SplitAndProve(ProofFn))
11553 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
11555 if (isImpliedCond(Pred,
LHS,
RHS, Condition,
Inverse, CtxI))
11557 if (ProvingStrictComparison) {
11561 if (SplitAndProve(ProofFn))
11572 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
11576 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
11577 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
11579 dyn_cast<BranchInst>(Pair.first->getTerminator());
11592 auto *CI = cast<CallInst>(AssumeVH);
11596 if (ProveViaCond(CI->getArgOperand(0),
false))
11604 for (
const auto *GU : GuardDecl->users())
11605 if (
const auto *Guard = dyn_cast<IntrinsicInst>(GU))
11607 if (ProveViaCond(Guard->getArgOperand(0),
false))
11623 "LHS is not available at Loop Entry");
11625 "RHS is not available at Loop Entry");
11627 if (isKnownViaNonRecursiveReasoning(Pred,
LHS,
RHS))
11638 if (FoundCondValue ==
11642 if (!PendingLoopPredicates.insert(FoundCondValue).second)
11646 make_scope_exit([&]() { PendingLoopPredicates.erase(FoundCondValue); });
11649 const Value *Op0, *Op1;
11652 return isImpliedCond(Pred, LHS, RHS, Op0,
Inverse, CtxI) ||
11653 isImpliedCond(Pred, LHS, RHS, Op1,
Inverse, CtxI);
11656 return isImpliedCond(Pred, LHS, RHS, Op0,
Inverse, CtxI) ||
11657 isImpliedCond(Pred, LHS, RHS, Op1,
Inverse, CtxI);
11660 const ICmpInst *ICI = dyn_cast<ICmpInst>(FoundCondValue);
11661 if (!ICI)
return false;
11674 return isImpliedCond(Pred, LHS, RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
11680 const SCEV *FoundLHS,
const SCEV *FoundRHS,
11691 auto *WideType = FoundLHS->
getType();
11701 if (isImpliedCondBalancedTypes(Pred, LHS, RHS, FoundPred, TruncFoundLHS,
11702 TruncFoundRHS, CtxI))
11728 return isImpliedCondBalancedTypes(Pred, LHS, RHS, FoundPred, FoundLHS,
11732bool ScalarEvolution::isImpliedCondBalancedTypes(
11738 "Types should be balanced!");
11745 if (FoundLHS == FoundRHS)
11749 if (LHS == FoundRHS || RHS == FoundLHS) {
11750 if (isa<SCEVConstant>(RHS)) {
11760 if (FoundPred == Pred)
11761 return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS, CtxI);
11775 if (!isa<SCEVConstant>(RHS) && !isa<SCEVAddRecExpr>(LHS))
11776 return isImpliedCondOperands(FoundPred, RHS, LHS, FoundLHS, FoundRHS,
11778 if (!isa<SCEVConstant>(FoundRHS) && !isa<SCEVAddRecExpr>(FoundLHS))
11779 return isImpliedCondOperands(Pred, LHS, RHS, FoundRHS, FoundLHS, CtxI);
11786 FoundLHS, FoundRHS, CtxI))
11791 isImpliedCondOperands(Pred, LHS, RHS,
getNotSCEV(FoundLHS),
11800 assert(P1 != P2 &&
"Handled earlier!");
11804 if (IsSignFlippedPredicate(Pred, FoundPred)) {
11809 return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS, CtxI);
11813 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
11814 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
11819 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
11830 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
11831 CanonicalRHS, CanonicalFoundLHS,
11832 CanonicalFoundRHS);
11837 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
11838 CanonicalRHS, CanonicalFoundLHS,
11839 CanonicalFoundRHS);
11844 (isa<SCEVConstant>(FoundLHS) || isa<SCEVConstant>(FoundRHS))) {
11847 const SCEV *
V =
nullptr;
11849 if (isa<SCEVConstant>(FoundLHS)) {
11850 C = cast<SCEVConstant>(FoundLHS);
11853 C = cast<SCEVConstant>(FoundRHS);
11865 if (Min ==
C->getAPInt()) {
11870 APInt SharperMin = Min + 1;
11877 if (isImpliedCondOperands(Pred, LHS, RHS, V,
getConstant(SharperMin),
11893 if (isImpliedCondOperands(Pred, LHS, RHS, V,
getConstant(Min), CtxI))
11922 if (isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS, CtxI))
11926 if (isImpliedCondOperands(FoundPred, LHS, RHS, FoundLHS, FoundRHS, CtxI))
11929 if (isImpliedCondOperandsViaRanges(Pred, LHS, RHS, FoundPred, FoundLHS, FoundRHS))
11936bool ScalarEvolution::splitBinaryAdd(
const SCEV *Expr,
11939 const auto *AE = dyn_cast<SCEVAddExpr>(Expr);
11940 if (!AE || AE->getNumOperands() != 2)
11943 L = AE->getOperand(0);
11944 R = AE->getOperand(1);
11945 Flags = AE->getNoWrapFlags();
11949std::optional<APInt>
11956 APInt DiffMul(BW, 1);
11959 for (
unsigned I = 0;
I < 8; ++
I) {
11964 if (isa<SCEVAddRecExpr>(
Less) && isa<SCEVAddRecExpr>(More)) {
11965 const auto *LAR = cast<SCEVAddRecExpr>(
Less);
11966 const auto *MAR = cast<SCEVAddRecExpr>(More);
11968 if (LAR->getLoop() != MAR->getLoop())
11969 return std::nullopt;
11973 if (!LAR->isAffine() || !MAR->isAffine())
11974 return std::nullopt;
11976 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
11977 return std::nullopt;
11979 Less = LAR->getStart();
11980 More = MAR->getStart();
11985 auto MatchConstMul =
11986 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
11987 auto *M = dyn_cast<SCEVMulExpr>(S);
11988 if (!M || M->getNumOperands() != 2 ||
11989 !isa<SCEVConstant>(M->getOperand(0)))
11990 return std::nullopt;
11992 {M->getOperand(1), cast<SCEVConstant>(M->getOperand(0))->getAPInt()}};
11994 if (
auto MatchedMore = MatchConstMul(More)) {
11995 if (
auto MatchedLess = MatchConstMul(
Less)) {
11996 if (MatchedMore->second == MatchedLess->second) {
11997 More = MatchedMore->first;
11998 Less = MatchedLess->first;
11999 DiffMul *= MatchedMore->second;
12008 if (
auto *
C = dyn_cast<SCEVConstant>(S)) {
12010 Diff +=
C->getAPInt() * DiffMul;
12013 Diff -=
C->getAPInt() * DiffMul;
12016 Multiplicity[S] +=
Mul;
12018 auto Decompose = [&](
const SCEV *S,
int Mul) {
12019 if (isa<SCEVAddExpr>(S)) {
12025 Decompose(More, 1);
12026 Decompose(
Less, -1);
12030 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12031 for (
const auto &[S,
Mul] : Multiplicity) {
12036 return std::nullopt;
12038 }
else if (
Mul == -1) {
12040 return std::nullopt;
12043 return std::nullopt;
12047 if (NewMore == More || NewLess ==
Less)
12048 return std::nullopt;
12054 if (!More && !
Less)
12058 if (!More || !
Less)
12059 return std::nullopt;
12063 return std::nullopt;
12066bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12086 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(FoundLHS)) {
12090 if (!L->contains(ContextBB) || !DT.
dominates(ContextBB, L->getLoopLatch()))
12094 return isImpliedCondOperands(Pred, LHS, RHS, AR->
getStart(), FoundRHS);
12097 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(FoundRHS)) {
12101 if (!L->contains(ContextBB) || !DT.
dominates(ContextBB, L->getLoopLatch()))
12105 return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, AR->
getStart());
12111bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(
12113 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
12117 const auto *AddRecLHS = dyn_cast<SCEVAddRecExpr>(LHS);
12121 const auto *AddRecFoundLHS = dyn_cast<SCEVAddRecExpr>(FoundLHS);
12122 if (!AddRecFoundLHS)
12129 const Loop *
L = AddRecFoundLHS->getLoop();
12130 if (L != AddRecLHS->getLoop())
12169 if (!RDiff || *LDiff != *RDiff)
12172 if (LDiff->isMinValue())
12175 APInt FoundRHSLimit;
12178 FoundRHSLimit = -(*RDiff);
12192 const SCEV *FoundLHS,
12193 const SCEV *FoundRHS,
unsigned Depth) {
12194 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12198 bool Erased = PendingMerges.erase(LPhi);
12199 assert(Erased &&
"Failed to erase LPhi!");
12203 bool Erased = PendingMerges.erase(RPhi);
12204 assert(Erased &&
"Failed to erase RPhi!");
12210 if (
const SCEVUnknown *LU = dyn_cast<SCEVUnknown>(LHS))
12211 if (
auto *Phi = dyn_cast<PHINode>(LU->getValue())) {
12212 if (!PendingMerges.insert(Phi).second)
12216 if (
const SCEVUnknown *RU = dyn_cast<SCEVUnknown>(RHS))
12217 if (
auto *Phi = dyn_cast<PHINode>(RU->getValue())) {
12226 if (!PendingMerges.insert(Phi).second)
12232 if (!LPhi && !RPhi)
12243 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12247 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12248 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12249 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12250 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12253 if (RPhi && RPhi->getParent() == LBB) {
12260 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12261 if (!ProvedEasily(L, R))
12272 auto *RLoop = RAR->
getLoop();
12273 auto *Predecessor = RLoop->getLoopPredecessor();
12274 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12276 if (!ProvedEasily(L1, RAR->
getStart()))
12278 auto *Latch = RLoop->getLoopLatch();
12279 assert(Latch &&
"Loop with AddRec with no latch?");
12297 if (!ProvedEasily(L, RHS))
12307 const SCEV *FoundLHS,
12308 const SCEV *FoundRHS) {
12311 if (RHS == FoundRHS) {
12316 if (LHS != FoundLHS)
12319 auto *SUFoundRHS = dyn_cast<SCEVUnknown>(FoundRHS);
12323 Value *Shiftee, *ShiftValue;
12325 using namespace PatternMatch;
12326 if (
match(SUFoundRHS->getValue(),
12328 auto *ShifteeS =
getSCEV(Shiftee);
12348 const SCEV *FoundLHS,
12349 const SCEV *FoundRHS,
12351 if (isImpliedCondOperandsViaRanges(Pred, LHS, RHS, Pred, FoundLHS, FoundRHS))
12354 if (isImpliedCondOperandsViaNoOverflow(Pred, LHS, RHS, FoundLHS, FoundRHS))
12357 if (isImpliedCondOperandsViaShift(Pred, LHS, RHS, FoundLHS, FoundRHS))
12360 if (isImpliedCondOperandsViaAddRecStart(Pred, LHS, RHS, FoundLHS, FoundRHS,
12364 return isImpliedCondOperandsHelper(Pred, LHS, RHS,
12365 FoundLHS, FoundRHS);
12369template <
typename MinMaxExprType>
12371 const SCEV *Candidate) {
12372 const MinMaxExprType *MinMaxExpr = dyn_cast<MinMaxExprType>(MaybeMinMaxExpr);
12376 return is_contained(MinMaxExpr->operands(), Candidate);
12381 const SCEV *LHS,
const SCEV *RHS) {
12415 const SCEV *LHS,
const SCEV *RHS) {
12426 IsMinMaxConsistingOf<SCEVSMinExpr>(
LHS,
RHS) ||
12428 IsMinMaxConsistingOf<SCEVSMaxExpr>(
RHS,
LHS);
12437 IsMinMaxConsistingOf<SCEVUMinExpr>(
LHS,
RHS) ||
12439 IsMinMaxConsistingOf<SCEVUMaxExpr>(
RHS,
LHS);
12447 const SCEV *FoundLHS,
12448 const SCEV *FoundRHS,
12452 "LHS and RHS have different sizes?");
12455 "FoundLHS and FoundRHS have different sizes?");
12487 auto GetOpFromSExt = [&](
const SCEV *S) {
12488 if (
auto *Ext = dyn_cast<SCEVSignExtendExpr>(S))
12489 return Ext->getOperand();
12496 auto *OrigLHS =
LHS;
12497 auto *OrigFoundLHS = FoundLHS;
12498 LHS = GetOpFromSExt(LHS);
12499 FoundLHS = GetOpFromSExt(FoundLHS);
12502 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
12505 FoundRHS,
Depth + 1);
12508 if (
auto *LHSAddExpr = dyn_cast<SCEVAddExpr>(LHS)) {
12518 if (!LHSAddExpr->hasNoSignedWrap())
12521 auto *LL = LHSAddExpr->getOperand(0);
12522 auto *LR = LHSAddExpr->getOperand(1);
12526 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
12527 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2, RHS);
12532 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
12534 }
else if (
auto *LHSUnknownExpr = dyn_cast<SCEVUnknown>(LHS)) {
12549 if (!isa<ConstantInt>(LR))
12552 auto *Denominator = cast<SCEVConstant>(
getSCEV(LR));
12557 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
12565 auto *DTy = Denominator->getType();
12566 auto *FRHSTy = FoundRHS->
getType();
12567 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
12586 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
12597 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
12599 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
12607 if (isImpliedViaMerge(Pred, OrigLHS, RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
12614 const SCEV *LHS,
const SCEV *RHS) {
12647 const SCEV *LHS,
const SCEV *RHS) {
12649 isKnownPredicateViaConstantRanges(Pred, LHS, RHS) ||
12652 isKnownPredicateViaNoOverflow(Pred, LHS, RHS);
12658 const SCEV *FoundLHS,
12659 const SCEV *FoundRHS) {
12694 if (isImpliedViaOperations(Pred, LHS, RHS, FoundLHS, FoundRHS))
12704 const SCEV *FoundLHS,
12705 const SCEV *FoundRHS) {
12706 if (!isa<SCEVConstant>(RHS) || !isa<SCEVConstant>(FoundRHS))
12715 const APInt &ConstFoundRHS = cast<SCEVConstant>(FoundRHS)->getAPInt();
12727 const APInt &ConstRHS = cast<SCEVConstant>(RHS)->getAPInt();
12730 return LHSRange.
icmp(Pred, ConstRHS);
12733bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *RHS,
const SCEV *Stride,
12746 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
12754 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
12757bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *RHS,
const SCEV *Stride,
12769 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
12777 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
12789const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
12790 const SCEV *Stride,
12817 : APIntOps::umax(One, MinStride);
12821 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
12832 : APIntOps::umax(MaxEnd, MinStart);
12839ScalarEvolution::howManyLessThans(
const SCEV *LHS,
const SCEV *RHS,
12840 const Loop *L,
bool IsSigned,
12841 bool ControlsOnlyExit,
bool AllowPredicates) {
12845 bool PredicatedIV =
false;
12847 if (
auto *ZExt = dyn_cast<SCEVZeroExtendExpr>(LHS)) {
12848 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(ZExt->getOperand());
12850 auto canProveNUW = [&]() {
12853 if (!ControlsOnlyExit)
12874 Limit = Limit.
zext(OuterBitWidth);
12886 Type *Ty = ZExt->getType();
12888 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this, 0),
12890 IV = dyn_cast<SCEVAddRecExpr>(S);
12897 if (!
IV && AllowPredicates) {
12902 PredicatedIV =
true;
12906 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
12920 bool NoWrap = ControlsOnlyExit &&
IV->getNoWrapFlags(WrapType);
12923 const SCEV *Stride =
IV->getStepRecurrence(*
this);
12928 if (!PositiveStride) {
12980 auto wouldZeroStrideBeUB = [&]() {
12992 if (!wouldZeroStrideBeUB()) {
12996 }
else if (!NoWrap) {
12999 if (canIVOverflowOnLT(RHS, Stride, IsSigned))
13012 const SCEV *Start =
IV->getStart();
13018 const SCEV *OrigStart = Start;
13020 if (Start->getType()->isPointerTy()) {
13022 if (isa<SCEVCouldNotCompute>(Start))
13027 if (isa<SCEVCouldNotCompute>(RHS))
13031 const SCEV *
End =
nullptr, *BECount =
nullptr,
13032 *BECountIfBackedgeTaken =
nullptr;
13034 const auto *RHSAddRec = dyn_cast<SCEVAddRecExpr>(RHS);
13035 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13036 RHSAddRec->getNoWrapFlags()) {
13049 const SCEV *RHSStart = RHSAddRec->getStart();
13050 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13071 BECountIfBackedgeTaken =
13076 if (BECount ==
nullptr) {
13081 const SCEV *MaxBECount = computeMaxBECountForLT(
13084 MaxBECount,
false , Predicates);
13091 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13118 const SCEV *Numerator =
13124 auto canProveRHSGreaterThanEqualStart = [&]() {
13143 auto *StartMinusOne =
13150 if (canProveRHSGreaterThanEqualStart()) {
13165 BECountIfBackedgeTaken =
13181 bool MayAddOverflow = [&] {
13227 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13241 if (!MayAddOverflow) {
13253 const SCEV *ConstantMaxBECount;
13254 bool MaxOrZero =
false;
13255 if (isa<SCEVConstant>(BECount)) {
13256 ConstantMaxBECount = BECount;
13257 }
else if (BECountIfBackedgeTaken &&
13258 isa<SCEVConstant>(BECountIfBackedgeTaken)) {
13262 ConstantMaxBECount = BECountIfBackedgeTaken;
13265 ConstantMaxBECount = computeMaxBECountForLT(
13269 if (isa<SCEVCouldNotCompute>(ConstantMaxBECount) &&
13270 !isa<SCEVCouldNotCompute>(BECount))
13273 const SCEV *SymbolicMaxBECount =
13274 isa<SCEVCouldNotCompute>(BECount) ? ConstantMaxBECount : BECount;
13275 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13280 const SCEV *LHS,
const SCEV *RHS,
const Loop *L,
bool IsSigned,
13281 bool ControlsOnlyExit,
bool AllowPredicates) {
13288 if (!
IV && AllowPredicates)
13295 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13299 bool NoWrap = ControlsOnlyExit &&
IV->getNoWrapFlags(WrapType);
13312 if (!Stride->
isOne() && !NoWrap)
13313 if (canIVOverflowOnGT(RHS, Stride, IsSigned))
13316 const SCEV *Start =
IV->getStart();
13328 if (Start->getType()->isPointerTy()) {
13330 if (isa<SCEVCouldNotCompute>(Start))
13333 if (
End->getType()->isPointerTy()) {
13335 if (isa<SCEVCouldNotCompute>(
End))
13363 const SCEV *ConstantMaxBECount =
13364 isa<SCEVConstant>(BECount)
13369 if (isa<SCEVCouldNotCompute>(ConstantMaxBECount))
13370 ConstantMaxBECount = BECount;
13371 const SCEV *SymbolicMaxBECount =
13372 isa<SCEVCouldNotCompute>(BECount) ? ConstantMaxBECount : BECount;
13374 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13384 if (
const SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart()))
13385 if (!SC->getValue()->isZero()) {
13389 getNoWrapFlags(FlagNW));
13390 if (
const auto *ShiftedAddRec = dyn_cast<SCEVAddRecExpr>(Shifted))
13391 return ShiftedAddRec->getNumIterationsInRange(
13399 if (
any_of(operands(), [](
const SCEV *
Op) {
return !isa<SCEVConstant>(
Op); }))
13419 APInt A = cast<SCEVConstant>(getOperand(1))->getAPInt();
13437 "Linear scev computation is off in a bad way!");
13441 if (isQuadratic()) {
13451 assert(getNumOperands() > 1 &&
"AddRec with zero step?");
13461 for (
unsigned i = 0, e = getNumOperands() - 1; i < e; ++i)
13467 const SCEV *
Last = getOperand(getNumOperands() - 1);
13468 assert(!
Last->isZero() &&
"Recurrency with zero step?");
13470 return cast<SCEVAddRecExpr>(SE.
getAddRecExpr(Ops, getLoop(),
13477 if (
const auto *SU = dyn_cast<SCEVUnknown>(S))
13478 return isa<UndefValue>(SU->
getValue());
13486 if (
const auto *SU = dyn_cast<SCEVUnknown>(S))
13495 if (
StoreInst *Store = dyn_cast<StoreInst>(Inst))
13496 Ty = Store->getValueOperand()->getType();
13497 else if (
LoadInst *Load = dyn_cast<LoadInst>(Inst))
13498 Ty = Load->getType();
13510void ScalarEvolution::SCEVCallbackVH::deleted() {
13511 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13512 if (
PHINode *PN = dyn_cast<PHINode>(getValPtr()))
13513 SE->ConstantEvolutionLoopExitValue.erase(PN);
13514 SE->eraseValueFromMap(getValPtr());
13518void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
13519 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13538 :
F(
F),
DL(
F.getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
13540 LoopDispositions(64), BlockDispositions(64) {
13551 auto *GuardDecl =
F.getParent()->getFunction(
13553 HasGuards = GuardDecl && !GuardDecl->use_empty();
13557 :
F(Arg.
F),
DL(Arg.
DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
13558 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
13559 ValueExprMap(
std::
move(Arg.ValueExprMap)),
13560 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
13561 PendingPhiRanges(
std::
move(Arg.PendingPhiRanges)),
13562 PendingMerges(
std::
move(Arg.PendingMerges)),
13563 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
13564 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
13565 PredicatedBackedgeTakenCounts(
13566 std::
move(Arg.PredicatedBackedgeTakenCounts)),
13567 BECountUsers(
std::
move(Arg.BECountUsers)),
13568 ConstantEvolutionLoopExitValue(
13569 std::
move(Arg.ConstantEvolutionLoopExitValue)),
13570 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
13571 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
13572 LoopDispositions(
std::
move(Arg.LoopDispositions)),
13573 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
13574 BlockDispositions(
std::
move(Arg.BlockDispositions)),
13575 SCEVUsers(
std::
move(Arg.SCEVUsers)),
13576 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
13577 SignedRanges(
std::
move(Arg.SignedRanges)),
13578 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
13579 UniquePreds(
std::
move(Arg.UniquePreds)),
13580 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
13581 LoopUsers(
std::
move(Arg.LoopUsers)),
13582 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
13583 FirstUnknown(Arg.FirstUnknown) {
13584 Arg.FirstUnknown =
nullptr;
13593 Tmp->~SCEVUnknown();
13595 FirstUnknown =
nullptr;
13597 ExprValueMap.
clear();
13598 ValueExprMap.
clear();
13600 BackedgeTakenCounts.clear();
13601 PredicatedBackedgeTakenCounts.clear();
13603 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
13604 assert(PendingPhiRanges.empty() &&
"getRangeRef garbage");
13605 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
13606 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
13607 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
13617 if (isa<SCEVConstant>(S))
13629 L->getHeader()->printAsOperand(
OS,
false);
13633 L->getExitingBlocks(ExitingBlocks);
13634 if (ExitingBlocks.
size() != 1)
13635 OS <<
"<multiple exits> ";
13638 if (!isa<SCEVCouldNotCompute>(BTC)) {
13639 OS <<
"backedge-taken count is ";
13642 OS <<
"Unpredictable backedge-taken count.";
13645 if (ExitingBlocks.
size() > 1)
13646 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
13647 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
13653 L->getHeader()->printAsOperand(
OS,
false);
13657 if (!isa<SCEVCouldNotCompute>(ConstantBTC)) {
13658 OS <<
"constant max backedge-taken count is ";
13661 OS <<
", actual taken count either this or zero.";
13663 OS <<
"Unpredictable constant max backedge-taken count. ";
13668 L->getHeader()->printAsOperand(
OS,
false);
13672 if (!isa<SCEVCouldNotCompute>(SymbolicBTC)) {
13673 OS <<
"symbolic max backedge-taken count is ";
13676 OS <<
", actual taken count either this or zero.";
13678 OS <<
"Unpredictable symbolic max backedge-taken count. ";
13682 if (ExitingBlocks.
size() > 1)
13683 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
13684 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
13693 if (PBT != BTC || !Preds.
empty()) {
13695 L->getHeader()->printAsOperand(
OS,
false);
13697 if (!isa<SCEVCouldNotCompute>(PBT)) {
13698 OS <<
"Predicated backedge-taken count is ";
13701 OS <<
"Unpredictable predicated backedge-taken count.";
13703 OS <<
" Predicates:\n";
13704 for (
const auto *
P : Preds)
13709 auto *PredSymbolicMax =
13711 if (SymbolicBTC != PredSymbolicMax) {
13713 L->getHeader()->printAsOperand(
OS,
false);
13715 if (!isa<SCEVCouldNotCompute>(PredSymbolicMax)) {
13716 OS <<
"Predicated symbolic max backedge-taken count is ";
13719 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
13721 OS <<
" Predicates:\n";
13722 for (
const auto *
P : Preds)
13728 L->getHeader()->printAsOperand(
OS,
false);
13744 OS <<
"Computable";
13753 OS <<
"DoesNotDominate";
13759 OS <<
"ProperlyDominates";
13776 OS <<
"Classifying expressions for: ";
13785 if (!isa<SCEVCouldNotCompute>(SV)) {
13798 if (!isa<SCEVCouldNotCompute>(AtUse)) {
13807 OS <<
"\t\t" "Exits: ";
13810 OS <<
"<<Unknown>>";
13816 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
13818 OS <<
"\t\t" "LoopDispositions: { ";
13824 Iter->getHeader()->printAsOperand(
OS,
false);
13832 OS <<
"\t\t" "LoopDispositions: { ";
13838 InnerL->getHeader()->printAsOperand(
OS,
false);
13849 OS <<
"Determining loop execution counts for: ";
13858 auto &Values = LoopDispositions[S];
13859 for (
auto &V : Values) {
13860 if (V.getPointer() == L)
13865 auto &Values2 = LoopDispositions[S];
13867 if (V.getPointer() == L) {
13876ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
13895 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
13896 " dominate the contained loop's header?");
13923 bool HasVarying =
false;
13938 if (
auto *
I = dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue()))
13957 auto &Values = BlockDispositions[S];
13958 for (
auto &V : Values) {
13959 if (V.getPointer() == BB)
13964 auto &Values2 = BlockDispositions[S];
13966 if (V.getPointer() == BB) {
13975ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14004 bool Proper =
true;
14016 dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue())) {
14017 if (
I->getParent() == BB)
14042void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14045 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14046 auto It = BECounts.find(L);
14047 if (It != BECounts.end()) {
14048 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14049 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14050 if (!isa<SCEVConstant>(S)) {
14051 auto UserIt = BECountUsers.find(S);
14052 assert(UserIt != BECountUsers.end());
14057 BECounts.erase(It);
14065 while (!Worklist.
empty()) {
14067 auto Users = SCEVUsers.find(Curr);
14068 if (
Users != SCEVUsers.end())
14074 for (
const auto *S : ToForget)
14075 forgetMemoizedResultsImpl(S);
14077 for (
auto I = PredicatedSCEVRewrites.begin();
14078 I != PredicatedSCEVRewrites.end();) {
14079 std::pair<const SCEV *, const Loop *>
Entry =
I->first;
14080 if (ToForget.count(
Entry.first))
14081 PredicatedSCEVRewrites.erase(
I++);
14087void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14088 LoopDispositions.erase(S);
14089 BlockDispositions.erase(S);
14090 UnsignedRanges.erase(S);
14091 SignedRanges.erase(S);
14092 HasRecMap.
erase(S);
14093 ConstantMultipleCache.erase(S);
14095 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(S)) {
14096 UnsignedWrapViaInductionTried.erase(AR);
14097 SignedWrapViaInductionTried.erase(AR);
14100 auto ExprIt = ExprValueMap.
find(S);
14101 if (ExprIt != ExprValueMap.
end()) {
14102 for (
Value *V : ExprIt->second) {
14103 auto ValueIt = ValueExprMap.
find_as(V);
14104 if (ValueIt != ValueExprMap.
end())
14105 ValueExprMap.
erase(ValueIt);
14107 ExprValueMap.
erase(ExprIt);
14110 auto ScopeIt = ValuesAtScopes.find(S);
14111 if (ScopeIt != ValuesAtScopes.end()) {
14112 for (
const auto &Pair : ScopeIt->second)
14113 if (!isa_and_nonnull<SCEVConstant>(Pair.second))
14115 std::make_pair(Pair.first, S));
14116 ValuesAtScopes.erase(ScopeIt);
14119 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14120 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14121 for (
const auto &Pair : ScopeUserIt->second)
14122 llvm::erase(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
14123 ValuesAtScopesUsers.erase(ScopeUserIt);
14126 auto BEUsersIt = BECountUsers.find(S);
14127 if (BEUsersIt != BECountUsers.end()) {
14129 auto Copy = BEUsersIt->second;
14130 for (
const auto &Pair : Copy)
14131 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14132 BECountUsers.erase(BEUsersIt);
14135 auto FoldUser = FoldCacheUser.find(S);
14136 if (FoldUser != FoldCacheUser.end())
14137 for (
auto &KV : FoldUser->second)
14138 FoldCache.erase(KV);
14139 FoldCacheUser.erase(S);
14143ScalarEvolution::getUsedLoops(
const SCEV *S,
14145 struct FindUsedLoops {
14147 : LoopsUsed(LoopsUsed) {}
14149 bool follow(
const SCEV *S) {
14150 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(S))
14155 bool isDone()
const {
return false; }
14158 FindUsedLoops F(LoopsUsed);
14162void ScalarEvolution::getReachableBlocks(
14166 while (!Worklist.
empty()) {
14168 if (!Reachable.
insert(BB).second)
14175 if (
auto *
C = dyn_cast<ConstantInt>(
Cond)) {
14176 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14180 if (
auto *Cmp = dyn_cast<ICmpInst>(
Cond)) {
14183 if (isKnownPredicateViaConstantRanges(
Cmp->getPredicate(), L, R)) {
14187 if (isKnownPredicateViaConstantRanges(
Cmp->getInversePredicate(), L,
14222 SCEVMapper SCM(SE2);
14224 SE2.getReachableBlocks(ReachableBlocks,
F);
14226 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14244 while (!LoopStack.
empty()) {
14250 if (!ReachableBlocks.
contains(L->getHeader()))
14255 auto It = BackedgeTakenCounts.find(L);
14256 if (It == BackedgeTakenCounts.end())
14260 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14280 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14281 if (Delta && !Delta->
isZero()) {
14282 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14283 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14284 dbgs() <<
"New: " << *NewBECount <<
"\n";
14285 dbgs() <<
"Delta: " << *Delta <<
"\n";
14293 while (!Worklist.
empty()) {
14295 if (ValidLoops.
insert(L).second)
14296 Worklist.
append(L->begin(), L->end());
14298 for (
const auto &KV : ValueExprMap) {
14301 if (
auto *AR = dyn_cast<SCEVAddRecExpr>(KV.second)) {
14303 "AddRec references invalid loop");
14308 auto It = ExprValueMap.
find(KV.second);
14309 if (It == ExprValueMap.
end() || !It->second.contains(KV.first)) {
14310 dbgs() <<
"Value " << *KV.first
14311 <<
" is in ValueExprMap but not in ExprValueMap\n";
14315 if (
auto *
I = dyn_cast<Instruction>(&*KV.first)) {
14316 if (!ReachableBlocks.
contains(
I->getParent()))
14318 const SCEV *OldSCEV = SCM.visit(KV.second);
14320 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14321 if (Delta && !Delta->
isZero()) {
14322 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14323 <<
"Old: " << *OldSCEV <<
"\n"
14324 <<
"New: " << *NewSCEV <<
"\n"
14325 <<
"Delta: " << *Delta <<
"\n";
14331 for (
const auto &KV : ExprValueMap) {
14332 for (
Value *V : KV.second) {
14333 auto It = ValueExprMap.find_as(V);
14334 if (It == ValueExprMap.end()) {
14335 dbgs() <<
"Value " << *V
14336 <<
" is in ExprValueMap but not in ValueExprMap\n";
14339 if (It->second != KV.first) {
14340 dbgs() <<
"Value " << *V <<
" mapped to " << *It->second
14341 <<
" rather than " << *KV.first <<
"\n";
14348 for (
const auto &S : UniqueSCEVs) {
14351 if (isa<SCEVConstant>(
Op))
14353 auto It = SCEVUsers.find(
Op);
14354 if (It != SCEVUsers.end() && It->second.count(&S))
14356 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14357 <<
" is not being tracked!\n";
14363 for (
const auto &ValueAndVec : ValuesAtScopes) {
14365 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14366 const Loop *L = LoopAndValueAtScope.first;
14367 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
14368 if (!isa<SCEVConstant>(ValueAtScope)) {
14369 auto It = ValuesAtScopesUsers.find(ValueAtScope);
14370 if (It != ValuesAtScopesUsers.end() &&
14373 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14374 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14380 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14381 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14382 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14383 const Loop *L = LoopAndValue.first;
14384 const SCEV *
Value = LoopAndValue.second;
14386 auto It = ValuesAtScopes.find(
Value);
14387 if (It != ValuesAtScopes.end() &&
14388 is_contained(It->second, std::make_pair(L, ValueAtScope)))
14390 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14391 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14397 auto VerifyBECountUsers = [&](
bool Predicated) {
14399 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14400 for (
const auto &LoopAndBEInfo : BECounts) {
14401 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14402 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14403 if (!isa<SCEVConstant>(S)) {
14404 auto UserIt = BECountUsers.find(S);
14405 if (UserIt != BECountUsers.end() &&
14406 UserIt->second.contains({ LoopAndBEInfo.first,
Predicated }))
14408 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14409 <<
" missing from BECountUsers\n";
14416 VerifyBECountUsers(
false);
14417 VerifyBECountUsers(
true);
14420 for (
auto &[S, Values] : LoopDispositions) {
14421 for (
auto [
Loop, CachedDisposition] : Values) {
14423 if (CachedDisposition != RecomputedDisposition) {
14424 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
14425 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
14426 << RecomputedDisposition <<
"\n";
14433 for (
auto &[S, Values] : BlockDispositions) {
14434 for (
auto [BB, CachedDisposition] : Values) {
14436 if (CachedDisposition != RecomputedDisposition) {
14437 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
14438 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
14439 <<
", actual " << RecomputedDisposition <<
"\n";
14446 for (
auto [
FoldID, Expr] : FoldCache) {
14447 auto I = FoldCacheUser.find(Expr);
14448 if (
I == FoldCacheUser.end()) {
14449 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
14454 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
14458 for (
auto [Expr, IDs] : FoldCacheUser) {
14459 for (
auto &
FoldID : IDs) {
14460 auto I = FoldCache.find(
FoldID);
14461 if (
I == FoldCache.end()) {
14462 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
14466 if (
I->second != Expr) {
14467 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: "
14468 << *
I->second <<
" != " << *Expr <<
"!\n";
14479 for (
auto [S, Multiple] : ConstantMultipleCache) {
14481 if ((Multiple != 0 && RecomputedMultiple != 0 &&
14482 Multiple.
urem(RecomputedMultiple) != 0 &&
14483 RecomputedMultiple.
urem(Multiple) != 0)) {
14484 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
14485 << *S <<
" : Computed " << RecomputedMultiple
14486 <<
" but cache contains " << Multiple <<
"!\n";
14526 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
14527 <<
F.getName() <<
"':\n";
14533 "Scalar Evolution Analysis",
false,
true)
14549 F, getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F),
14550 getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F),
14551 getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
14552 getAnalysis<LoopInfoWrapperPass>().getLoopInfo()));
14584 const SCEV *LHS,
const SCEV *RHS) {
14587 "Type mismatch between LHS and RHS");
14590 ID.AddInteger(Pred);
14591 ID.AddPointer(
LHS);
14592 ID.AddPointer(
RHS);
14593 void *IP =
nullptr;
14594 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
14598 UniquePreds.InsertNode(Eq, IP);
14609 ID.AddInteger(AddedFlags);
14610 void *IP =
nullptr;
14611 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
14613 auto *OF =
new (SCEVAllocator)
14615 UniquePreds.InsertNode(OF, IP);
14635 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
14641 if (
auto *U = dyn_cast<SCEVUnionPredicate>(Pred)) {
14642 for (
const auto *Pred : U->getPredicates())
14643 if (
const auto *IPred = dyn_cast<SCEVComparePredicate>(Pred))
14644 if (IPred->getLHS() == Expr &&
14645 IPred->getPredicate() == ICmpInst::ICMP_EQ)
14646 return IPred->getRHS();
14647 }
else if (
const auto *IPred = dyn_cast<SCEVComparePredicate>(Pred)) {
14648 if (IPred->getLHS() == Expr &&
14649 IPred->getPredicate() == ICmpInst::ICMP_EQ)
14650 return IPred->getRHS();
14653 return convertToAddRecWithPreds(Expr);
14706 return addOverflowAssumption(
A);
14716 if (!isa<PHINode>(Expr->
getValue()))
14719 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
14721 if (!PredicatedRewrite)
14723 for (
const auto *
P : PredicatedRewrite->second){
14725 if (
auto *WP = dyn_cast<const SCEVWrapPredicate>(
P)) {
14726 if (L != WP->getExpr()->getLoop())
14729 if (!addOverflowAssumption(
P))
14732 return PredicatedRewrite->first;
14745 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
14752 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
14753 auto *AddRec = dyn_cast<SCEVAddRecExpr>(S);
14760 for (
const auto *
P : TransformPreds)
14769 : FastID(
ID), Kind(Kind) {}
14776 assert(
LHS !=
RHS &&
"LHS and RHS are the same SCEV");
14780 const auto *
Op = dyn_cast<SCEVComparePredicate>(
N);
14810 const auto *
Op = dyn_cast<SCEVWrapPredicate>(
N);
14812 return Op &&
Op->AR == AR &&
setFlags(Flags,
Op->Flags) == Flags;
14848 if (Step->getValue()->getValue().isNonNegative())
14852 return ImpliedFlags;
14858 for (
const auto *
P : Preds)
14868 if (
const auto *Set = dyn_cast<SCEVUnionPredicate>(
N))
14869 return all_of(Set->Preds,
14877 for (
const auto *Pred : Preds)
14882 if (
const auto *Set = dyn_cast<SCEVUnionPredicate>(
N)) {
14883 for (
const auto *Pred : Set->Preds)
14897 Preds = std::make_unique<SCEVUnionPredicate>(
Empty);
14902 for (
const auto *
Op : Ops)
14906 if (!isa<SCEVConstant>(
Op))
14907 SCEVUsers[
Op].insert(
User);
14912 RewriteEntry &Entry = RewriteMap[Expr];
14915 if (Entry.second && Generation == Entry.first)
14916 return Entry.second;
14921 Expr = Entry.second;
14924 Entry = {Generation, NewSCEV};
14930 if (!BackedgeCount) {
14933 for (
const auto *
P : Preds)
14936 return BackedgeCount;
14940 if (!SymbolicMaxBackedgeCount) {
14942 SymbolicMaxBackedgeCount =
14944 for (
const auto *
P : Preds)
14947 return SymbolicMaxBackedgeCount;
14951 if (Preds->implies(&Pred))
14956 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds);
14957 updateGeneration();
14964void PredicatedScalarEvolution::updateGeneration() {
14966 if (++Generation == 0) {
14967 for (
auto &
II : RewriteMap) {
14968 const SCEV *Rewritten =
II.second.second;
14977 const auto *AR = cast<SCEVAddRecExpr>(Expr);
14985 auto II = FlagsMap.insert({V, Flags});
14993 const auto *AR = cast<SCEVAddRecExpr>(Expr);
14998 auto II = FlagsMap.find(V);
15000 if (
II != FlagsMap.end())
15014 for (
const auto *
P : NewPreds)
15017 RewriteMap[SE.
getSCEV(V)] = {Generation, New};
15023 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15025 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {
15026 for (
auto I :
Init.FlagsMap)
15027 FlagsMap.insert(
I);
15032 for (
auto *BB : L.getBlocks())
15033 for (
auto &
I : *BB) {
15038 auto II = RewriteMap.find(Expr);
15040 if (
II == RewriteMap.end())
15044 if (
II->second.second == Expr)
15058bool ScalarEvolution::matchURem(
const SCEV *Expr,
const SCEV *&LHS,
15059 const SCEV *&RHS) {
15066 if (
const auto *ZExt = dyn_cast<SCEVZeroExtendExpr>(Expr))
15067 if (
const auto *Trunc = dyn_cast<SCEVTruncateExpr>(ZExt->getOperand(0))) {
15068 LHS = Trunc->getOperand();
15080 const auto *
Add = dyn_cast<SCEVAddExpr>(Expr);
15081 if (
Add ==
nullptr ||
Add->getNumOperands() != 2)
15084 const SCEV *
A =
Add->getOperand(1);
15085 const auto *
Mul = dyn_cast<SCEVMulExpr>(
Add->getOperand(0));
15087 if (
Mul ==
nullptr)
15090 const auto MatchURemWithDivisor = [&](
const SCEV *
B) {
15101 if (
Mul->getNumOperands() == 3 && isa<SCEVConstant>(
Mul->getOperand(0)))
15102 return MatchURemWithDivisor(
Mul->getOperand(1)) ||
15103 MatchURemWithDivisor(
Mul->getOperand(2));
15106 if (
Mul->getNumOperands() == 2)
15107 return MatchURemWithDivisor(
Mul->getOperand(1)) ||
15108 MatchURemWithDivisor(
Mul->getOperand(0)) ||
15128 if (isa<SCEVConstant>(
LHS)) {
15136 auto MatchRangeCheckIdiom = [&SE, Predicate,
LHS,
RHS, &RewriteMap,
15137 &ExprsToRewrite]() {
15138 auto *AddExpr = dyn_cast<SCEVAddExpr>(
LHS);
15139 if (!AddExpr || AddExpr->getNumOperands() != 2)
15142 auto *C1 = dyn_cast<SCEVConstant>(AddExpr->getOperand(0));
15143 auto *LHSUnknown = dyn_cast<SCEVUnknown>(AddExpr->getOperand(1));
15144 auto *C2 = dyn_cast<SCEVConstant>(
RHS);
15145 if (!C1 || !C2 || !LHSUnknown)
15150 .
sub(C1->getAPInt());
15153 if (ExactRegion.isWrappedSet() || ExactRegion.isFullSet())
15155 auto I = RewriteMap.find(LHSUnknown);
15156 const SCEV *RewrittenLHS =
I != RewriteMap.end() ?
I->second : LHSUnknown;
15164 if (MatchRangeCheckIdiom())
15170 auto IsMinMaxSCEVWithNonNegativeConstant =
15173 if (
auto *
MinMax = dyn_cast<SCEVMinMaxExpr>(Expr)) {
15174 if (
MinMax->getNumOperands() != 2)
15176 if (
auto *
C = dyn_cast<SCEVConstant>(
MinMax->getOperand(0))) {
15177 if (
C->getAPInt().isNegative())
15179 SCTy =
MinMax->getSCEVType();
15190 auto GetNonNegExprAndPosDivisor = [&](
const SCEV *Expr,
const SCEV *Divisor,
15192 auto *ConstExpr = dyn_cast<SCEVConstant>(Expr);
15193 auto *ConstDivisor = dyn_cast<SCEVConstant>(Divisor);
15194 if (!ConstExpr || !ConstDivisor)
15196 ExprVal = ConstExpr->getAPInt();
15197 DivisorVal = ConstDivisor->getAPInt();
15198 return ExprVal.isNonNegative() && !DivisorVal.isNonPositive();
15204 auto GetNextSCEVDividesByDivisor = [&](
const SCEV *Expr,
15205 const SCEV *Divisor) {
15208 if (!GetNonNegExprAndPosDivisor(Expr, Divisor, ExprVal, DivisorVal))
15213 return SE.
getConstant(ExprVal + DivisorVal - Rem);
15220 auto GetPreviousSCEVDividesByDivisor = [&](
const SCEV *Expr,
15221 const SCEV *Divisor) {
15224 if (!GetNonNegExprAndPosDivisor(Expr, Divisor, ExprVal, DivisorVal))
15234 std::function<
const SCEV *(
const SCEV *,
const SCEV *)>
15235 ApplyDivisibiltyOnMinMaxExpr = [&](
const SCEV *MinMaxExpr,
15236 const SCEV *Divisor) {
15237 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15239 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15243 isa<SCEVSMinExpr>(MinMaxExpr) || isa<SCEVUMinExpr>(MinMaxExpr);
15245 "Expected non-negative operand!");
15246 auto *DivisibleExpr =
15247 IsMin ? GetPreviousSCEVDividesByDivisor(MinMaxLHS, Divisor)
15248 : GetNextSCEVDividesByDivisor(MinMaxLHS, Divisor);
15250 ApplyDivisibiltyOnMinMaxExpr(MinMaxRHS, Divisor), DivisibleExpr};
15261 const SCEV *URemLHS =
nullptr;
15262 const SCEV *URemRHS =
nullptr;
15263 if (SE.matchURem(
LHS, URemLHS, URemRHS)) {
15264 if (
const SCEVUnknown *LHSUnknown = dyn_cast<SCEVUnknown>(URemLHS)) {
15265 auto I = RewriteMap.find(LHSUnknown);
15266 const SCEV *RewrittenLHS =
15267 I != RewriteMap.end() ?
I->second : LHSUnknown;
15268 RewrittenLHS = ApplyDivisibiltyOnMinMaxExpr(RewrittenLHS, URemRHS);
15269 const auto *Multiple =
15271 RewriteMap[LHSUnknown] = Multiple;
15283 if (!isa<SCEVUnknown>(
LHS) && isa<SCEVUnknown>(
RHS)) {
15292 auto AddRewrite = [&](
const SCEV *
From,
const SCEV *FromRewritten,
15294 if (
From == FromRewritten)
15296 RewriteMap[
From] = To;
15302 auto GetMaybeRewritten = [&](
const SCEV *S) {
15303 auto I = RewriteMap.find(S);
15304 return I != RewriteMap.end() ?
I->second : S;
15314 std::function<
bool(
const SCEV *,
const SCEV *&)> HasDivisibiltyInfo =
15315 [&](
const SCEV *Expr,
const SCEV *&DividesBy) {
15316 if (
auto *
Mul = dyn_cast<SCEVMulExpr>(Expr)) {
15317 if (
Mul->getNumOperands() != 2)
15319 auto *MulLHS =
Mul->getOperand(0);
15320 auto *MulRHS =
Mul->getOperand(1);
15321 if (isa<SCEVConstant>(MulLHS))
15323 if (
auto *Div = dyn_cast<SCEVUDivExpr>(MulLHS))
15324 if (Div->getOperand(1) == MulRHS) {
15325 DividesBy = MulRHS;
15329 if (
auto *
MinMax = dyn_cast<SCEVMinMaxExpr>(Expr))
15330 return HasDivisibiltyInfo(
MinMax->getOperand(0), DividesBy) ||
15331 HasDivisibiltyInfo(
MinMax->getOperand(1), DividesBy);
15336 std::function<
bool(
const SCEV *,
const SCEV *&)> IsKnownToDivideBy =
15337 [&](
const SCEV *Expr,
const SCEV *DividesBy) {
15340 if (
auto *
MinMax = dyn_cast<SCEVMinMaxExpr>(Expr))
15341 return IsKnownToDivideBy(
MinMax->getOperand(0), DividesBy) &&
15342 IsKnownToDivideBy(
MinMax->getOperand(1), DividesBy);
15346 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15347 const SCEV *DividesBy =
nullptr;
15348 if (HasDivisibiltyInfo(RewrittenLHS, DividesBy))
15351 IsKnownToDivideBy(RewrittenLHS, DividesBy) ? DividesBy :
nullptr;
15365 switch (Predicate) {
15373 RHS = DividesBy ? GetPreviousSCEVDividesByDivisor(
RHS, DividesBy) :
RHS;
15379 RHS = DividesBy ? GetNextSCEVDividesByDivisor(
RHS, DividesBy) :
RHS;
15383 RHS = DividesBy ? GetPreviousSCEVDividesByDivisor(
RHS, DividesBy) :
RHS;
15387 RHS = DividesBy ? GetNextSCEVDividesByDivisor(
RHS, DividesBy) :
RHS;
15396 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
15400 while (!Worklist.
empty()) {
15402 if (isa<SCEVConstant>(
From))
15406 const SCEV *FromRewritten = GetMaybeRewritten(
From);
15407 const SCEV *To =
nullptr;
15409 switch (Predicate) {
15413 if (
auto *
UMax = dyn_cast<SCEVUMaxExpr>(FromRewritten))
15414 EnqueueOperands(
UMax);
15419 if (
auto *
SMax = dyn_cast<SCEVSMaxExpr>(FromRewritten))
15420 EnqueueOperands(
SMax);
15425 if (
auto *
UMin = dyn_cast<SCEVUMinExpr>(FromRewritten))
15426 EnqueueOperands(
UMin);
15431 if (
auto *
SMin = dyn_cast<SCEVSMinExpr>(FromRewritten))
15432 EnqueueOperands(
SMin);
15435 if (isa<SCEVConstant>(
RHS))
15439 if (isa<SCEVConstant>(
RHS) &&
15440 cast<SCEVConstant>(
RHS)->getValue()->isNullValue()) {
15441 const SCEV *OneAlignedUp =
15442 DividesBy ? GetNextSCEVDividesByDivisor(One, DividesBy) : One;
15443 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
15451 AddRewrite(
From, FromRewritten, To);
15461 auto *AssumeI = cast<CallInst>(AssumeVH);
15471 for (
const auto *GU : GuardDecl->users())
15472 if (
const auto *Guard = dyn_cast<IntrinsicInst>(GU))
15473 if (Guard->getFunction() == Header->getParent() &&
15482 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(
15483 L->getLoopPredecessor(), Header);
15485 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
15488 dyn_cast<BranchInst>(Pair.first->getTerminator());
15500 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
15504 while (!Worklist.
empty()) {
15509 if (
auto *Cmp = dyn_cast<ICmpInst>(
Cond)) {
15511 EnterIfTrue ? Cmp->getPredicate() : Cmp->getInversePredicate();
15512 const auto *
LHS = SE.
getSCEV(Cmp->getOperand(0));
15513 const auto *
RHS = SE.
getSCEV(Cmp->getOperand(1));
15514 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap);
15530 Guards.PreserveNUW =
true;
15531 Guards.PreserveNSW =
true;
15532 for (
const SCEV *Expr : ExprsToRewrite) {
15533 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
15534 Guards.PreserveNUW &=
15536 Guards.PreserveNSW &=
15543 if (ExprsToRewrite.
size() > 1) {
15544 for (
const SCEV *Expr : ExprsToRewrite) {
15545 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
15546 Guards.RewriteMap.erase(Expr);
15547 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
15557 class SCEVLoopGuardRewriter
15567 if (Guards.PreserveNUW)
15569 if (Guards.PreserveNSW)
15576 auto I = Map.find(Expr);
15577 if (
I == Map.end())
15583 auto I = Map.find(Expr);
15584 if (
I == Map.end()) {
15590 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
15591 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
15594 auto I = Map.find(NarrowExt);
15595 if (
I != Map.end())
15597 Bitwidth = Bitwidth / 2;
15607 auto I = Map.find(Expr);
15608 if (
I == Map.end())
15615 auto I = Map.find(Expr);
15616 if (
I == Map.end())
15622 auto I = Map.find(Expr);
15623 if (
I == Map.end())
15630 bool Changed =
false;
15638 return !Changed ? Expr
15646 bool Changed =
false;
15654 return !Changed ? Expr
15661 if (RewriteMap.empty())
15664 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
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...
This defines the Use class.
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
void visit(MachineFunction &MF, MachineBasicBlock &Start, std::function< void(MachineBasicBlock *)> op)
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 int CompareValueComplexity(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 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 std::optional< int > CompareSCEVComplexity(EquivalenceClasses< const SCEV * > &EqCacheSCEV, const LoopInfo *const LI, const SCEV *LHS, const SCEV *RHS, DominatorTree &DT, unsigned Depth=0)
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 const SCEV * constantFoldAndGroupOps(ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT, SmallVectorImpl< const SCEV * > &Ops, FoldT Fold, IsIdentityT IsIdentity, IsAbsorberT IsAbsorber)
Performs a number of common optimizations on the passed Ops.
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 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 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)
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]
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
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
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...
static LoopGuards collect(const Loop *L, ScalarEvolution &SE)
Collect rewrite map for loop guards for loop L, together with flags indicating if NUW and NSW can be ...
const SCEV * rewrite(const SCEV *Expr) const
Try to apply the collected loop guards to Expr.
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...
bool isKnownToBeAPowerOfTwo(const SCEV *S, bool OrZero=false, bool OrNegative=false)
Test if the given expression is known to be a power of 2.
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.
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)
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
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)
Provide wrappers to std::max_element which take ranges instead of having to pass begin/end explicitly...
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