83#include "llvm/Config/llvm-config.h"
138#define DEBUG_TYPE "scalar-evolution"
141 "Number of loop exits with predictable exit counts");
143 "Number of loop exits without predictable exit counts");
145 "Number of loops with trip counts computed by force");
147#ifdef EXPENSIVE_CHECKS
155 cl::desc(
"Maximum number of iterations SCEV will "
156 "symbolically execute a constant "
162 cl::desc(
"Verify ScalarEvolution's backedge taken counts (slow)"));
165 cl::desc(
"Enable stricter verification with -verify-scev is passed"));
169 cl::desc(
"Verify IR correctness when making sensitive SCEV queries (slow)"),
174 cl::desc(
"Threshold for inlining multiplication operands into a SCEV"),
179 cl::desc(
"Threshold for inlining addition operands into a SCEV"),
183 "scalar-evolution-max-scev-compare-depth",
cl::Hidden,
184 cl::desc(
"Maximum depth of recursive SCEV complexity comparisons"),
188 "scalar-evolution-max-scev-operations-implication-depth",
cl::Hidden,
189 cl::desc(
"Maximum depth of recursive SCEV operations implication analysis"),
193 "scalar-evolution-max-value-compare-depth",
cl::Hidden,
194 cl::desc(
"Maximum depth of recursive value complexity comparisons"),
199 cl::desc(
"Maximum depth of recursive arithmetics"),
203 "scalar-evolution-max-constant-evolving-depth",
cl::Hidden,
208 cl::desc(
"Maximum depth of recursive SExt/ZExt/Trunc"),
213 cl::desc(
"Max coefficients in AddRec during evolving"),
218 cl::desc(
"Size of the expression which is considered huge"),
223 cl::desc(
"Threshold for switching to iteratively computing SCEV ranges"),
227 "scalar-evolution-max-loop-guard-collection-depth",
cl::Hidden,
228 cl::desc(
"Maximum depth for recursive loop guard collection"),
cl::init(1));
233 cl::desc(
"When printing analysis, include information on every instruction"));
236 "scalar-evolution-use-expensive-range-sharpening",
cl::Hidden,
238 cl::desc(
"Use more powerful methods of sharpening expression ranges. May "
239 "be costly in terms of compile time"));
242 "scalar-evolution-max-scc-analysis-depth",
cl::Hidden,
243 cl::desc(
"Maximum amount of nodes to process while searching SCEVUnknown "
244 "Phi strongly connected components"),
249 cl::desc(
"Handle <= and >= in finite loops"),
253 "scalar-evolution-use-context-for-no-wrap-flag-strenghening",
cl::Hidden,
254 cl::desc(
"Infer nuw/nsw flags using context where suitable"),
265#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
285 OS <<
"(ptrto" << OpS <<
" " << *
Op->getType() <<
" " << *
Op <<
" to "
292 OS <<
"(trunc " << *
Op->getType() <<
" " << *
Op <<
" to "
299 OS <<
"(zext " << *
Op->getType() <<
" " << *
Op <<
" to "
306 OS <<
"(sext " << *
Op->getType() <<
" " << *
Op <<
" to "
335 const char *OpStr =
nullptr;
348 OpStr =
" umin_seq ";
372 OS <<
"(" << *UDiv->
getLHS() <<
" /u " << *UDiv->
getRHS() <<
")";
379 OS <<
"***COULDNOTCOMPUTE***";
457 if (!
Mul)
return false;
461 if (!SC)
return false;
479 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
481 UniqueSCEVs.InsertNode(S, IP);
495 ConstantInt::get(ITy, V, isSigned,
true));
503 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
506 UniqueSCEVs.InsertNode(S, IP);
526 "Must be a non-bit-width-changing pointer-to-integer cast!");
533 "Must be a non-bit-width-changing pointer-to-integer cast!");
545 "Cannot truncate non-integer value!");
552 "Cannot zero extend non-integer value!");
559 "Cannot sign extend non-integer value!");
564 SE->forgetMemoizedResults(
this);
567 SE->UniqueSCEVs.RemoveNode(
this);
573void SCEVUnknown::allUsesReplacedWith(
Value *New) {
575 SE->forgetMemoizedResults(
this);
578 SE->UniqueSCEVs.RemoveNode(
this);
600 if (LIsPointer != RIsPointer)
601 return (
int)LIsPointer - (int)RIsPointer;
606 return (
int)LID - (int)RID;
611 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
612 return (
int)LArgNo - (int)RArgNo;
618 if (
auto L = LGV->getLinkage() - RGV->getLinkage())
621 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
622 auto LT = GV->getLinkage();
629 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
630 return LGV->getName().compare(RGV->getName());
641 if (LParent != RParent) {
644 if (LDepth != RDepth)
645 return (
int)LDepth - (int)RDepth;
649 unsigned LNumOps = LInst->getNumOperands(),
650 RNumOps = RInst->getNumOperands();
651 if (LNumOps != RNumOps)
652 return (
int)LNumOps - (int)RNumOps;
654 for (
unsigned Idx :
seq(LNumOps)) {
656 RInst->getOperand(Idx),
Depth + 1);
670static std::optional<int>
680 return (
int)LType - (int)RType;
705 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
706 if (LBitWidth != RBitWidth)
707 return (
int)LBitWidth - (int)RBitWidth;
708 return LA.
ult(
RA) ? -1 : 1;
714 return LTy->getBitWidth() - RTy->getBitWidth();
725 if (LLoop != RLoop) {
727 assert(LHead != RHead &&
"Two loops share the same header?");
731 "No dominance between recurrences used by one SCEV?");
755 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
756 if (LNumOps != RNumOps)
757 return (
int)LNumOps - (int)RNumOps;
759 for (
unsigned i = 0; i != LNumOps; ++i) {
784 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) {
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) {
848 for (
unsigned Idx = 0; Idx <
Ops.size();) {
856 Ops.erase(
Ops.begin() + Idx);
863 assert(Folded &&
"Must have folded value");
867 if (Folded && IsAbsorber(Folded->
getAPInt()))
871 if (Folded && !IsIdentity(Folded->
getAPInt()))
872 Ops.insert(
Ops.begin(), Folded);
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) {
1033 ConversionFn CreatePtrCast;
1037 ConversionFn CreatePtrCast)
1038 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
1041 Type *TargetTy, ConversionFn CreatePtrCast) {
1043 return Rewriter.visit(Scev);
1079 "Should only reach pointer-typed SCEVUnknown's.");
1084 return SE.getZero(TargetTy);
1085 return CreatePtrCast(Expr);
1090 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1109 Op, *
this, IntPtrTy, [
this, IntPtrTy](
const SCEVUnknown *U) {
1114 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1116 SCEV *S =
new (SCEVAllocator)
1118 UniqueSCEVs.InsertNode(S, IP);
1120 return static_cast<const SCEV *
>(S);
1123 "We must have succeeded in sinking the cast, "
1124 "and ending up with an integer-typed expression!");
1129 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1130 Type *Ty = DL.getAddressType(
Op->getType());
1141 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1143 SCEV *S =
new (SCEVAllocator)
1145 UniqueSCEVs.InsertNode(S, IP);
1147 return static_cast<const SCEV *
>(S);
1150 "We must have succeeded in sinking the cast, "
1151 "and ending up with an integer-typed expression!");
1156 assert(Ty->isIntegerTy() &&
"Target type must be an integer type!");
1168 "This is not a truncating conversion!");
1170 "This is not a conversion to a SCEVable type!");
1171 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1179 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1201 UniqueSCEVs.InsertNode(S, IP);
1213 unsigned numTruncs = 0;
1214 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1222 if (numTruncs < 2) {
1232 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1239 for (
const SCEV *
Op : AddRec->operands())
1254 UniqueSCEVs.InsertNode(S, IP);
1294struct ExtendOpTraitsBase {
1295 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
const SCEV *,
Type *,
1300template <
typename ExtendOp>
struct ExtendOpTraits {
1316 static const GetExtendExprTy GetExtendExpr;
1318 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1319 ICmpInst::Predicate *Pred,
1320 ScalarEvolution *SE) {
1325const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1332 static const GetExtendExprTy GetExtendExpr;
1334 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1335 ICmpInst::Predicate *Pred,
1336 ScalarEvolution *SE) {
1341const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1353template <
typename ExtendOpTy>
1356 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1357 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1373 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1386 auto PreStartFlags =
1404 const SCEV *OperandExtendedStart =
1406 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1407 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1419 const SCEV *OverflowLimit =
1420 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1422 if (OverflowLimit &&
1430template <
typename ExtendOpTy>
1434 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1442 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1477template <
typename ExtendOpTy>
1478bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1481 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1491 APInt StartAI = StartC->
getAPInt();
1493 for (
unsigned Delta : {-2, -1, 1, 2}) {
1494 const SCEV *PreStart =
getConstant(StartAI - Delta);
1496 FoldingSetNodeID
ID;
1498 ID.AddPointer(PreStart);
1499 ID.AddPointer(Step);
1503 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
1507 if (PreAR && PreAR->getNoWrapFlags(WrapType)) {
1510 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1511 DeltaS, &Pred,
this);
1529 const unsigned BitWidth =
C.getBitWidth();
1547 const APInt &ConstantStart,
1566 auto &UserIDs = FoldCacheUser[
I.first->second];
1567 assert(
count(UserIDs,
ID) == 1 &&
"unexpected duplicates in UserIDs");
1568 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1569 if (UserIDs[
I] ==
ID) {
1574 I.first->second = S;
1576 FoldCacheUser[S].push_back(
ID);
1582 "This is not an extending conversion!");
1584 "This is not a conversion to a SCEVable type!");
1585 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1589 if (
const SCEV *S = FoldCache.lookup(
ID))
1601 "This is not an extending conversion!");
1603 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1620 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1624 UniqueSCEVs.InsertNode(S, IP);
1633 const SCEV *
X = ST->getOperand();
1647 if (AR->isAffine()) {
1648 const SCEV *Start = AR->getStart();
1649 const SCEV *Step = AR->getStepRecurrence(*
this);
1651 const Loop *L = AR->getLoop();
1655 if (AR->hasNoUnsignedWrap()) {
1676 const SCEV *CastedMaxBECount =
1680 if (MaxBECount == RecastedMaxBECount) {
1690 const SCEV *WideMaxBECount =
1692 const SCEV *OperandExtendedAdd =
1698 if (ZAdd == OperandExtendedAdd) {
1709 OperandExtendedAdd =
1715 if (ZAdd == OperandExtendedAdd) {
1736 !AC.assumptions().empty()) {
1738 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1740 if (AR->hasNoUnsignedWrap()) {
1775 const APInt &
C = SC->getAPInt();
1779 const SCEV *SResidual =
1788 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1813 if (SA->hasNoUnsignedWrap()) {
1817 for (
const auto *
Op : SA->operands())
1834 const SCEV *SResidual =
1846 if (SM->hasNoUnsignedWrap()) {
1850 for (
const auto *
Op : SM->operands())
1868 const SCEV *TruncRHS;
1887 for (
auto *Operand :
MinMax->operands())
1898 for (
auto *Operand :
MinMax->operands())
1905 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1908 UniqueSCEVs.InsertNode(S, IP);
1916 "This is not an extending conversion!");
1918 "This is not a conversion to a SCEVable type!");
1919 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1923 if (
const SCEV *S = FoldCache.lookup(
ID))
1935 "This is not an extending conversion!");
1937 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1959 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1964 UniqueSCEVs.InsertNode(S, IP);
1973 const SCEV *
X = ST->getOperand();
1984 if (SA->hasNoSignedWrap()) {
1988 for (
const auto *
Op : SA->operands())
2006 const SCEV *SResidual =
2020 if (AR->isAffine()) {
2021 const SCEV *Start = AR->getStart();
2022 const SCEV *Step = AR->getStepRecurrence(*
this);
2024 const Loop *L = AR->getLoop();
2028 if (AR->hasNoSignedWrap()) {
2050 const SCEV *CastedMaxBECount =
2054 if (MaxBECount == RecastedMaxBECount) {
2064 const SCEV *WideMaxBECount =
2066 const SCEV *OperandExtendedAdd =
2072 if (SAdd == OperandExtendedAdd) {
2083 OperandExtendedAdd =
2089 if (SAdd == OperandExtendedAdd) {
2109 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2111 if (AR->hasNoSignedWrap()) {
2126 const APInt &
C = SC->getAPInt();
2130 const SCEV *SResidual =
2139 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2158 for (
auto *Operand :
MinMax->operands())
2167 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
2170 UniqueSCEVs.InsertNode(S, IP);
2196 "This is not an extending conversion!");
2198 "This is not a conversion to a SCEVable type!");
2203 if (SC->getAPInt().isNegative())
2208 const SCEV *NewOp =
T->getOperand();
2227 for (
const SCEV *
Op : AR->operands())
2266 APInt &AccumulatedConstant,
2269 bool Interesting =
false;
2276 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2278 AccumulatedConstant += Scale *
C->getAPInt();
2283 for (; i !=
Ops.size(); ++i) {
2293 Add->operands(), NewScale, SE);
2299 auto Pair = M.insert({
Key, NewScale});
2303 Pair.first->second += NewScale;
2311 std::pair<DenseMap<const SCEV *, APInt>::iterator,
bool> Pair =
2312 M.insert({
Ops[i], Scale});
2316 Pair.first->second += Scale;
2335 case Instruction::Add:
2338 case Instruction::Sub:
2341 case Instruction::Mul:
2355 const SCEV *
A = (this->*Extension)(
2357 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2358 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2366 if (BinOp == Instruction::Mul)
2372 APInt C = RHSC->getAPInt();
2373 unsigned NumBits =
C.getBitWidth();
2374 bool IsSub = (BinOp == Instruction::Sub);
2375 bool IsNegativeConst = (
Signed &&
C.isNegative());
2377 bool OverflowDown = IsSub ^ IsNegativeConst;
2379 if (IsNegativeConst) {
2392 APInt Limit = Min + Magnitude;
2398 APInt Limit = Max - Magnitude;
2403std::optional<SCEV::NoWrapFlags>
2408 return std::nullopt;
2417 bool Deduced =
false;
2419 if (OBO->
getOpcode() != Instruction::Add &&
2422 return std::nullopt;
2431 false, LHS, RHS, CtxI)) {
2438 true, LHS, RHS, CtxI)) {
2445 return std::nullopt;
2455 using namespace std::placeholders;
2462 assert(CanAnalyze &&
"don't call from other places!");
2469 auto IsKnownNonNegative = [&](
const SCEV *S) {
2479 if (SignOrUnsignWrap != SignOrUnsignMask &&
2486 return Instruction::Add;
2488 return Instruction::Mul;
2499 Opcode,
C, OBO::NoSignedWrap);
2507 Opcode,
C, OBO::NoUnsignedWrap);
2517 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2524 if (UDiv->getOperand(1) ==
Ops[1])
2527 if (UDiv->getOperand(1) ==
Ops[0])
2543 "only nuw or nsw allowed");
2544 assert(!
Ops.empty() &&
"Cannot get empty add!");
2545 if (
Ops.size() == 1)
return Ops[0];
2548 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2550 "SCEVAddExpr operand types don't match!");
2552 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2553 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2558 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2559 [](
const APInt &
C) {
return C.isZero(); },
2560 [](
const APInt &
C) {
return false; });
2573 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2578 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2579 Add->setNoWrapFlags(ComputeFlags(
Ops));
2587 bool FoundMatch =
false;
2588 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2589 if (
Ops[i] ==
Ops[i+1]) {
2601 --i; e -=
Count - 1;
2611 auto FindTruncSrcType = [&]() ->
Type * {
2617 return T->getOperand()->getType();
2619 const auto *LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2621 return T->getOperand()->getType();
2625 if (
auto *SrcType = FindTruncSrcType()) {
2632 if (
T->getOperand()->getType() != SrcType) {
2641 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2644 if (
T->getOperand()->getType() != SrcType) {
2672 if (
Ops.size() == 2) {
2682 auto C2 =
C->getAPInt();
2685 APInt ConstAdd = C1 + C2;
2686 auto AddFlags = AddExpr->getNoWrapFlags();
2727 if (
Ops.size() == 2 &&
2738 if (Idx <
Ops.size()) {
2739 bool DeletedAdd =
false;
2750 Ops.erase(
Ops.begin()+Idx);
2753 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2776 struct APIntCompare {
2777 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2778 return LHS.ult(RHS);
2785 std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists;
2786 for (
const SCEV *NewOp : NewOps)
2787 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2790 if (AccumulatedConstant != 0)
2792 for (
auto &MulOp : MulOpLists) {
2793 if (MulOp.first == 1) {
2795 }
else if (MulOp.first != 0) {
2804 if (
Ops.size() == 1)
2815 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2816 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2819 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp)
2820 if (MulOpSCEV ==
Ops[AddOp]) {
2822 const SCEV *InnerMul =
Mul->getOperand(MulOp == 0);
2823 if (
Mul->getNumOperands() != 2) {
2827 Mul->operands().take_front(MulOp));
2835 if (
Ops.size() == 2)
return OuterMul;
2837 Ops.erase(
Ops.begin()+AddOp);
2838 Ops.erase(
Ops.begin()+Idx-1);
2840 Ops.erase(
Ops.begin()+Idx);
2841 Ops.erase(
Ops.begin()+AddOp-1);
2843 Ops.push_back(OuterMul);
2848 for (
unsigned OtherMulIdx = Idx+1;
2855 OMulOp != e; ++OMulOp)
2856 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2858 const SCEV *InnerMul1 =
Mul->getOperand(MulOp == 0);
2859 if (
Mul->getNumOperands() != 2) {
2861 Mul->operands().take_front(MulOp));
2868 OtherMul->
operands().take_front(OMulOp));
2873 const SCEV *InnerMulSum =
2877 if (
Ops.size() == 2)
return OuterMul;
2878 Ops.erase(
Ops.begin()+Idx);
2879 Ops.erase(
Ops.begin()+OtherMulIdx-1);
2880 Ops.push_back(OuterMul);
2900 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2903 Ops.erase(
Ops.begin()+i);
2908 if (!LIOps.
empty()) {
2933 auto *DefI = getDefiningScopeBound(LIOps);
2935 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2947 if (
Ops.size() == 1)
return NewRec;
2950 for (
unsigned i = 0;; ++i)
2951 if (
Ops[i] == AddRec) {
2961 for (
unsigned OtherIdx = Idx+1;
2969 "AddRecExprs are not sorted in reverse dominance order?");
2976 if (OtherAddRec->getLoop() == AddRecLoop) {
2977 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2979 if (i >= AddRecOps.
size()) {
2980 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2984 AddRecOps[i], OtherAddRec->getOperand(i)};
2987 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3002 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
3014 static_cast<SCEVAddExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3016 const SCEV **O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
3018 S =
new (SCEVAllocator)
3020 UniqueSCEVs.InsertNode(S, IP);
3030 FoldingSetNodeID
ID;
3032 for (
const SCEV *
Op :
Ops)
3037 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3039 const SCEV **
O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
3041 S =
new (SCEVAllocator)
3042 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3043 UniqueSCEVs.InsertNode(S, IP);
3044 LoopUsers[
L].push_back(S);
3054 FoldingSetNodeID
ID;
3056 for (
const SCEV *
Op :
Ops)
3060 static_cast<SCEVMulExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3062 const SCEV **
O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
3064 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3066 UniqueSCEVs.InsertNode(S, IP);
3075 if (j > 1 && k / j != i) Overflow =
true;
3091 if (n == 0 || n == k)
return 1;
3092 if (k > n)
return 0;
3098 for (
uint64_t i = 1; i <= k; ++i) {
3099 r =
umul_ov(r, n-(i-1), Overflow);
3108 struct FindConstantInAddMulChain {
3109 bool FoundConstant =
false;
3111 bool follow(
const SCEV *S) {
3116 bool isDone()
const {
3117 return FoundConstant;
3121 FindConstantInAddMulChain
F;
3123 ST.visitAll(StartExpr);
3124 return F.FoundConstant;
3132 "only nuw or nsw allowed");
3133 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3134 if (
Ops.size() == 1)
return Ops[0];
3136 Type *ETy =
Ops[0]->getType();
3138 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3140 "SCEVMulExpr operand types don't match!");
3145 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3146 [](
const APInt &
C) {
return C.isOne(); },
3147 [](
const APInt &
C) {
return C.isZero(); });
3158 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3163 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3164 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3169 if (
Ops.size() == 2) {
3177 const SCEV *Op0, *Op1;
3185 if (
Ops[0]->isAllOnesValue()) {
3190 bool AnyFolded =
false;
3191 for (
const SCEV *AddOp :
Add->operands()) {
3218 AddRec->getNoWrapFlags(FlagsMask));
3241 APInt C1V = LHSC->getAPInt();
3251 const SCEV *NewMul =
nullptr;
3255 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3270 if (Idx <
Ops.size()) {
3271 bool DeletedMul =
false;
3277 Ops.erase(
Ops.begin()+Idx);
3301 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3304 Ops.erase(
Ops.begin()+i);
3309 if (!LIOps.
empty()) {
3322 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3338 if (
Ops.size() == 1)
return NewRec;
3341 for (
unsigned i = 0;; ++i)
3342 if (
Ops[i] == AddRec) {
3363 bool OpsModified =
false;
3364 for (
unsigned OtherIdx = Idx+1;
3378 bool Overflow =
false;
3385 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3389 z < ze && !Overflow; ++z) {
3392 if (LargerThan64Bits)
3393 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3395 Coeff = Coeff1*Coeff2;
3410 if (
Ops.size() == 2)
return NewAddRec;
3411 Ops[Idx] = NewAddRec;
3412 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3428 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3436 "SCEVURemExpr operand types don't match!");
3441 if (RHSC->getValue()->isOne())
3442 return getZero(LHS->getType());
3445 if (RHSC->getAPInt().isPowerOf2()) {
3446 Type *FullTy = LHS->getType();
3463 assert(!LHS->getType()->isPointerTy() &&
3464 "SCEVUDivExpr operand can't be pointer!");
3465 assert(LHS->getType() == RHS->getType() &&
3466 "SCEVUDivExpr operand types don't match!");
3473 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3481 if (RHSC->getValue()->isOne())
3486 if (!RHSC->getValue()->isZero()) {
3490 Type *Ty = LHS->getType();
3491 unsigned LZ = RHSC->getAPInt().countl_zero();
3495 if (!RHSC->getAPInt().isPowerOf2())
3503 const APInt &StepInt = Step->getAPInt();
3504 const APInt &DivInt = RHSC->getAPInt();
3505 if (!StepInt.
urem(DivInt) &&
3511 for (
const SCEV *
Op : AR->operands())
3517 const APInt *StartRem;
3530 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3534 const SCEV *NewStart =
3536 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3538 const SCEV *NewLHS =
3541 if (LHS != NewLHS) {
3551 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3560 for (
const SCEV *
Op : M->operands())
3564 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3565 const SCEV *
Op = M->getOperand(i);
3577 if (
auto *DivisorConstant =
3579 bool Overflow =
false;
3581 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3592 for (
const SCEV *
Op :
A->operands())
3596 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3603 if (Operands.
size() ==
A->getNumOperands())
3610 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3620 return getZero(LHS->getType());
3624 const SCEV *NewLHS, *NewRHS;
3632 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
3635 UniqueSCEVs.InsertNode(S, IP);
3665 if (!
Mul || !
Mul->hasNoUnsignedWrap())
3672 if (LHSCst == RHSCst) {
3680 APInt Factor =
gcd(LHSCst, RHSCst);
3698 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3699 if (
Mul->getOperand(i) == RHS) {
3718 if (StepChrec->getLoop() == L) {
3732 if (Operands.
size() == 1)
return Operands[0];
3737 "SCEVAddRecExpr operand types don't match!");
3738 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3740 for (
const SCEV *
Op : Operands)
3742 "SCEVAddRecExpr operand is not available at loop entry!");
3745 if (Operands.
back()->isZero()) {
3760 const Loop *NestedLoop = NestedAR->getLoop();
3761 if (L->contains(NestedLoop)
3764 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3766 Operands[0] = NestedAR->getStart();
3770 bool AllInvariant =
all_of(
3782 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3793 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3797 Operands[0] = NestedAR;
3803 return getOrCreateAddRecExpr(Operands, L, Flags);
3819 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3823 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3837 bool FirstIter =
true;
3839 for (
const SCEV *IndexExpr : IndexExprs) {
3846 Offsets.push_back(FieldOffset);
3849 CurTy = STy->getTypeAtIndex(Index);
3854 "The first index of a GEP indexes a pointer");
3855 CurTy = SrcElementTy;
3866 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3867 Offsets.push_back(LocalOffset);
3872 if (Offsets.empty())
3885 "GEP should not change type mid-flight.");
3889SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3892 ID.AddInteger(SCEVType);
3896 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3906 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3907 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3908 if (
Ops.size() == 1)
return Ops[0];
3911 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3913 "Operand types don't match!");
3916 "min/max should be consistently pointerish");
3942 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3944 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3949 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3951 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3957 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3963 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3968 if (Idx <
Ops.size()) {
3969 bool DeletedAny =
false;
3970 while (
Ops[Idx]->getSCEVType() == Kind) {
3972 Ops.erase(
Ops.begin()+Idx);
3990 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3991 if (
Ops[i] ==
Ops[i + 1] ||
3992 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3995 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3998 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
4001 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
4007 if (
Ops.size() == 1)
return Ops[0];
4009 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
4014 ID.AddInteger(Kind);
4018 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4020 return ExistingSCEV;
4021 const SCEV **O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
4023 SCEV *S =
new (SCEVAllocator)
4026 UniqueSCEVs.InsertNode(S, IP);
4033class SCEVSequentialMinMaxDeduplicatingVisitor final
4034 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4035 std::optional<const SCEV *>> {
4036 using RetVal = std::optional<const SCEV *>;
4044 bool canRecurseInto(
SCEVTypes Kind)
const {
4047 return RootKind == Kind || NonSequentialRootKind == Kind;
4050 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
4052 "Only for min/max expressions.");
4055 if (!canRecurseInto(Kind))
4065 return std::nullopt;
4072 RetVal
visit(
const SCEV *S) {
4074 if (!SeenOps.
insert(S).second)
4075 return std::nullopt;
4076 return Base::visit(S);
4080 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4082 : SE(SE), RootKind(RootKind),
4083 NonSequentialRootKind(
4084 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4088 SmallVectorImpl<const SCEV *> &NewOps) {
4093 for (
const SCEV *
Op : OrigOps) {
4098 Ops.emplace_back(*NewOp);
4102 NewOps = std::move(
Ops);
4106 RetVal visitConstant(
const SCEVConstant *Constant) {
return Constant; }
4108 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4110 RetVal visitPtrToAddrExpr(
const SCEVPtrToAddrExpr *Expr) {
return Expr; }
4112 RetVal visitPtrToIntExpr(
const SCEVPtrToIntExpr *Expr) {
return Expr; }
4114 RetVal visitTruncateExpr(
const SCEVTruncateExpr *Expr) {
return Expr; }
4116 RetVal visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
return Expr; }
4118 RetVal visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
return Expr; }
4120 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4122 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4124 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4126 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4128 RetVal visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
4129 return visitAnyMinMaxExpr(Expr);
4132 RetVal visitUMaxExpr(
const SCEVUMaxExpr *Expr) {
4133 return visitAnyMinMaxExpr(Expr);
4136 RetVal visitSMinExpr(
const SCEVSMinExpr *Expr) {
4137 return visitAnyMinMaxExpr(Expr);
4140 RetVal visitUMinExpr(
const SCEVUMinExpr *Expr) {
4141 return visitAnyMinMaxExpr(Expr);
4144 RetVal visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *Expr) {
4145 return visitAnyMinMaxExpr(Expr);
4148 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4150 RetVal visitCouldNotCompute(
const SCEVCouldNotCompute *Expr) {
return Expr; }
4193struct SCEVPoisonCollector {
4194 bool LookThroughMaybePoisonBlocking;
4195 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4196 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4197 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4199 bool follow(
const SCEV *S) {
4200 if (!LookThroughMaybePoisonBlocking &&
4210 bool isDone()
const {
return false; }
4220 SCEVPoisonCollector PC1(
true);
4225 if (PC1.MaybePoison.empty())
4231 SCEVPoisonCollector PC2(
false);
4241 SCEVPoisonCollector PC(
false);
4264 while (!Worklist.
empty()) {
4266 if (!Visited.
insert(V).second)
4270 if (Visited.
size() > 16)
4275 if (PoisonVals.
contains(V) || ::isGuaranteedNotToBePoison(V))
4286 if (PDI->isDisjoint())
4293 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4300 if (
I->hasPoisonGeneratingAnnotations())
4311 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4312 "Not a SCEVSequentialMinMaxExpr!");
4313 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4314 if (
Ops.size() == 1)
4318 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4320 "Operand types don't match!");
4323 "min/max should be consistently pointerish");
4331 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4338 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4348 bool DeletedAny =
false;
4349 while (Idx <
Ops.size()) {
4350 if (
Ops[Idx]->getSCEVType() != Kind) {
4355 Ops.erase(
Ops.begin() + Idx);
4356 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4357 SMME->operands().end());
4365 const SCEV *SaturationPoint;
4376 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4377 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4389 Ops.erase(
Ops.begin() + i);
4394 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4395 Ops.erase(
Ops.begin() + i);
4403 ID.AddInteger(Kind);
4407 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4409 return ExistingSCEV;
4411 const SCEV **O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
4413 SCEV *S =
new (SCEVAllocator)
4416 UniqueSCEVs.InsertNode(S, IP);
4464 if (
Size.isScalable())
4485 "Cannot get offset for structure containing scalable vector types");
4499 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP)) {
4501 "Stale SCEVUnknown in uniquing map!");
4507 UniqueSCEVs.InsertNode(S, IP);
4521 return Ty->isIntOrPtrTy();
4528 if (Ty->isPointerTy())
4539 if (Ty->isIntegerTy())
4543 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4555 bool PreciseA, PreciseB;
4556 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4557 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4558 if (!PreciseA || !PreciseB)
4561 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4562 DT.dominates(ScopeB, ScopeA);
4566 return CouldNotCompute.get();
4569bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4572 return SU && SU->getValue() ==
nullptr;
4575 return !ContainsNulls;
4580 if (
I != HasRecMap.end())
4585 HasRecMap.insert({S, FoundAddRec});
4593 if (
SI == ExprValueMap.
end())
4595 return SI->second.getArrayRef();
4601void ScalarEvolution::eraseValueFromMap(
Value *V) {
4603 if (
I != ValueExprMap.end()) {
4604 auto EVIt = ExprValueMap.find(
I->second);
4605 bool Removed = EVIt->second.remove(V);
4607 assert(Removed &&
"Value not in ExprValueMap?");
4608 ValueExprMap.erase(
I);
4612void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4616 auto It = ValueExprMap.find_as(V);
4617 if (It == ValueExprMap.end()) {
4619 ExprValueMap[S].insert(V);
4630 return createSCEVIter(V);
4637 if (
I != ValueExprMap.end()) {
4638 const SCEV *S =
I->second;
4639 assert(checkValidity(S) &&
4640 "existing SCEV has not been properly invalidated");
4653 Type *Ty = V->getType();
4669 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4682 return (
const SCEV *)
nullptr;
4688 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4692 Type *Ty = V->getType();
4698 assert(
P->getType()->isPointerTy());
4711 const SCEV **PtrOp =
nullptr;
4712 for (
const SCEV *&AddOp :
Ops) {
4713 if (AddOp->getType()->isPointerTy()) {
4714 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4732 return getZero(LHS->getType());
4737 if (RHS->getType()->isPointerTy()) {
4738 if (!LHS->getType()->isPointerTy() ||
4748 const bool RHSIsNotMinSigned =
4779 Type *SrcTy = V->getType();
4780 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4781 "Cannot truncate or zero extend with non-integer arguments!");
4791 Type *SrcTy = V->getType();
4792 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4793 "Cannot truncate or zero extend with non-integer arguments!");
4803 Type *SrcTy = V->getType();
4804 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4805 "Cannot noop or zero extend with non-integer arguments!");
4807 "getNoopOrZeroExtend cannot truncate!");
4815 Type *SrcTy = V->getType();
4816 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4817 "Cannot noop or sign extend with non-integer arguments!");
4819 "getNoopOrSignExtend cannot truncate!");
4827 Type *SrcTy = V->getType();
4828 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4829 "Cannot noop or any extend with non-integer arguments!");
4831 "getNoopOrAnyExtend cannot truncate!");
4839 Type *SrcTy = V->getType();
4840 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4841 "Cannot truncate or noop with non-integer arguments!");
4843 "getTruncateOrNoop cannot extend!");
4851 const SCEV *PromotedLHS = LHS;
4852 const SCEV *PromotedRHS = RHS;
4872 assert(!
Ops.empty() &&
"At least one operand must be!");
4874 if (
Ops.size() == 1)
4878 Type *MaxType =
nullptr;
4879 for (
const auto *S :
Ops)
4884 assert(MaxType &&
"Failed to find maximum type!");
4888 for (
const auto *S :
Ops)
4897 if (!V->getType()->isPointerTy())
4902 V = AddRec->getStart();
4904 const SCEV *PtrOp =
nullptr;
4905 for (
const SCEV *AddOp :
Add->operands()) {
4906 if (AddOp->getType()->isPointerTy()) {
4907 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4911 assert(PtrOp &&
"Must have pointer op");
4923 for (
User *U :
I->users()) {
4925 if (Visited.
insert(UserInsn).second)
4939 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4940 bool IgnoreOtherLoops =
true) {
4943 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4945 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4950 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4952 SeenLoopVariantSCEVUnknown =
true;
4956 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4960 SeenOtherLoops =
true;
4964 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4966 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4969 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4970 : SCEVRewriteVisitor(SE),
L(
L) {}
4973 bool SeenLoopVariantSCEVUnknown =
false;
4974 bool SeenOtherLoops =
false;
4983 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4984 SCEVPostIncRewriter
Rewriter(L, SE);
4986 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4991 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4993 SeenLoopVariantSCEVUnknown =
true;
4997 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5001 SeenOtherLoops =
true;
5005 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
5007 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
5010 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
5011 : SCEVRewriteVisitor(SE),
L(
L) {}
5014 bool SeenLoopVariantSCEVUnknown =
false;
5015 bool SeenOtherLoops =
false;
5021class SCEVBackedgeConditionFolder
5024 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5025 ScalarEvolution &SE) {
5026 bool IsPosBECond =
false;
5027 Value *BECond =
nullptr;
5028 if (BasicBlock *Latch =
L->getLoopLatch()) {
5032 "Both outgoing branches should not target same header!");
5039 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
5043 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5044 const SCEV *
Result = Expr;
5049 switch (
I->getOpcode()) {
5050 case Instruction::Select: {
5052 std::optional<const SCEV *> Res =
5053 compareWithBackedgeCondition(
SI->getCondition());
5061 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5072 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5073 bool IsPosBECond, ScalarEvolution &SE)
5074 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5075 IsPositiveBECond(IsPosBECond) {}
5077 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5081 Value *BackedgeCond =
nullptr;
5083 bool IsPositiveBECond;
5086std::optional<const SCEV *>
5087SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5092 if (BackedgeCond == IC)
5095 return std::nullopt;
5100 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5101 ScalarEvolution &SE) {
5107 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5114 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5124 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5125 : SCEVRewriteVisitor(SE),
L(
L) {}
5134ScalarEvolution::proveNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5138 using OBO = OverflowingBinaryOperator;
5146 const APInt &BECountAP = BECountMax->getAPInt();
5147 unsigned NoOverflowBitWidth =
5159 Instruction::Add, IncRange, OBO::NoSignedWrap);
5160 if (NSWRegion.contains(AddRecRange))
5169 Instruction::Add, IncRange, OBO::NoUnsignedWrap);
5170 if (NUWRegion.contains(AddRecRange))
5178ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5188 if (!SignedWrapViaInductionTried.insert(AR).second)
5213 AC.assumptions().empty())
5221 const SCEV *OverflowLimit =
5223 if (OverflowLimit &&
5231ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5241 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5267 AC.assumptions().empty())
5302 explicit BinaryOp(Operator *
Op)
5306 IsNSW = OBO->hasNoSignedWrap();
5307 IsNUW = OBO->hasNoUnsignedWrap();
5311 explicit BinaryOp(
unsigned Opcode,
Value *
LHS,
Value *
RHS,
bool IsNSW =
false,
5313 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5325 return std::nullopt;
5331 switch (
Op->getOpcode()) {
5332 case Instruction::Add:
5333 case Instruction::Sub:
5334 case Instruction::Mul:
5335 case Instruction::UDiv:
5336 case Instruction::URem:
5337 case Instruction::And:
5338 case Instruction::AShr:
5339 case Instruction::Shl:
5340 return BinaryOp(
Op);
5342 case Instruction::Or: {
5345 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5347 return BinaryOp(
Op);
5350 case Instruction::Xor:
5354 if (RHSC->getValue().isSignMask())
5355 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5357 if (V->getType()->isIntegerTy(1))
5358 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5359 return BinaryOp(
Op);
5361 case Instruction::LShr:
5370 if (SA->getValue().ult(
BitWidth)) {
5372 ConstantInt::get(SA->getContext(),
5374 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5377 return BinaryOp(
Op);
5379 case Instruction::ExtractValue: {
5381 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5389 bool Signed = WO->isSigned();
5392 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5397 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5408 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5409 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5411 return std::nullopt;
5437 if (
Op == SymbolicPHI)
5442 if (SourceBits != NewBits)
5460 if (!L || L->getHeader() != PN->
getParent())
5518std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5519ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5527 assert(L &&
"Expecting an integer loop header phi");
5532 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5533 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5534 Value *
V = PN->getIncomingValue(i);
5535 if (
L->contains(PN->getIncomingBlock(i))) {
5538 }
else if (BEValueV != V) {
5542 }
else if (!StartValueV) {
5544 }
else if (StartValueV != V) {
5545 StartValueV =
nullptr;
5549 if (!BEValueV || !StartValueV)
5550 return std::nullopt;
5552 const SCEV *BEValue =
getSCEV(BEValueV);
5559 return std::nullopt;
5563 unsigned FoundIndex =
Add->getNumOperands();
5564 Type *TruncTy =
nullptr;
5566 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5569 if (FoundIndex == e) {
5574 if (FoundIndex ==
Add->getNumOperands())
5575 return std::nullopt;
5579 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5580 if (i != FoundIndex)
5581 Ops.push_back(
Add->getOperand(i));
5587 return std::nullopt;
5640 const SCEV *StartVal =
getSCEV(StartValueV);
5641 const SCEV *PHISCEV =
5668 auto getExtendedExpr = [&](
const SCEV *Expr,
5669 bool CreateSignExtend) ->
const SCEV * {
5672 const SCEV *ExtendedExpr =
5675 return ExtendedExpr;
5683 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5684 const SCEV *ExtendedExpr) ->
bool {
5685 return Expr != ExtendedExpr &&
5689 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5690 if (PredIsKnownFalse(StartVal, StartExtended)) {
5692 return std::nullopt;
5697 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5698 if (PredIsKnownFalse(Accum, AccumExtended)) {
5700 return std::nullopt;
5703 auto AppendPredicate = [&](
const SCEV *Expr,
5704 const SCEV *ExtendedExpr) ->
void {
5705 if (Expr != ExtendedExpr &&
5713 AppendPredicate(StartVal, StartExtended);
5714 AppendPredicate(Accum, AccumExtended);
5722 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5723 std::make_pair(NewAR, Predicates);
5725 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5729std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5734 return std::nullopt;
5737 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5738 if (
I != PredicatedSCEVRewrites.end()) {
5739 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5742 if (Rewrite.first == SymbolicPHI)
5743 return std::nullopt;
5747 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5751 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5752 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5757 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5758 return std::nullopt;
5775 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5776 if (Expr1 != Expr2 &&
5777 !Preds->implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5778 !Preds->implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5795const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5797 Value *StartValueV) {
5800 assert(BEValueV && StartValueV);
5806 if (BO->Opcode != Instruction::Add)
5809 const SCEV *Accum =
nullptr;
5810 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5812 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5826 insertValueToMap(PN, PHISCEV);
5831 proveNoWrapViaConstantRanges(AR)));
5839 "Accum is defined outside L, but is not invariant?");
5840 if (isAddRecNeverPoison(BEInst, L))
5847const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5848 const Loop *
L = LI.getLoopFor(PN->
getParent());
5855 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5861 }
else if (BEValueV != V) {
5865 }
else if (!StartValueV) {
5867 }
else if (StartValueV != V) {
5868 StartValueV =
nullptr;
5872 if (!BEValueV || !StartValueV)
5875 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5876 "PHI node already processed?");
5880 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5885 insertValueToMap(PN, SymbolicName);
5889 const SCEV *BEValue =
getSCEV(BEValueV);
5899 unsigned FoundIndex =
Add->getNumOperands();
5900 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5901 if (
Add->getOperand(i) == SymbolicName)
5902 if (FoundIndex == e) {
5907 if (FoundIndex !=
Add->getNumOperands()) {
5910 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5911 if (i != FoundIndex)
5912 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5924 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5931 if (
GEP->getOperand(0) == PN) {
5932 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
5950 const SCEV *StartVal =
getSCEV(StartValueV);
5951 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5956 forgetMemoizedResults(SymbolicName);
5957 insertValueToMap(PN, PHISCEV);
5962 proveNoWrapViaConstantRanges(AR)));
5987 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5988 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5990 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5991 const SCEV *StartVal =
getSCEV(StartValueV);
5992 if (Start == StartVal) {
5996 forgetMemoizedResults(SymbolicName);
5997 insertValueToMap(PN, Shifted);
6007 eraseValueFromMap(PN);
6027 Use &LeftUse =
Merge->getOperandUse(0);
6028 Use &RightUse =
Merge->getOperandUse(1);
6045const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
6047 [&](
BasicBlock *BB) {
return DT.isReachableFromEntry(BB); };
6062 assert(IDom &&
"At least the entry block should dominate PN");
6071 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6087ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6088 BinaryOperator *CommonInst =
nullptr;
6099 CommonInst = IncomingInst;
6106 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6107 bool SCEVExprsIdentical =
6109 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6110 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6113const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6114 if (
const SCEV *S = createAddRecFromPHI(PN))
6124 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6127 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6136 struct FindClosure {
6137 const SCEV *OperandToFind;
6143 bool canRecurseInto(
SCEVTypes Kind)
const {
6146 return RootKind == Kind || NonSequentialRootKind == Kind ||
6151 : OperandToFind(OperandToFind), RootKind(RootKind),
6152 NonSequentialRootKind(
6156 bool follow(
const SCEV *S) {
6157 Found = S == OperandToFind;
6159 return !isDone() && canRecurseInto(S->
getSCEVType());
6162 bool isDone()
const {
return Found; }
6165 FindClosure FC(OperandToFind, RootKind);
6170std::optional<const SCEV *>
6171ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6181 switch (ICI->getPredicate()) {
6195 bool Signed = ICI->isSigned();
6196 const SCEV *LA =
getSCEV(TrueVal);
6204 if (LA == LS &&
RA == RS)
6206 if (LA == RS &&
RA == LS)
6209 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6210 if (
Op->getType()->isPointerTy()) {
6221 LS = CoerceOperand(LS);
6222 RS = CoerceOperand(RS);
6246 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6247 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6261 X = ZExt->getOperand();
6263 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6274 return std::nullopt;
6277static std::optional<const SCEV *>
6279 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6283 "Unexpected operands of a select.");
6295 return std::nullopt;
6310static std::optional<const SCEV *>
6314 return std::nullopt;
6317 const auto *SETrue = SE->
getSCEV(TrueVal);
6318 const auto *SEFalse = SE->
getSCEV(FalseVal);
6322const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6324 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6326 V->getType() ==
TrueVal->getType() &&
6327 "Types of select hands and of the result must match.");
6330 if (!
V->getType()->isIntegerTy(1))
6333 if (std::optional<const SCEV *> S =
6346 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6350 if (std::optional<const SCEV *> S =
6351 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6357 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6363 assert(
GEP->getSourceElementType()->isSized() &&
6364 "GEP source element type must be sized");
6367 for (
Value *Index :
GEP->indices())
6372APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6375 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6378 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6380 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6383 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6402 return GetShiftedByZeros(TZ);
6412 return GetShiftedByZeros(TZ);
6416 if (
M->hasNoUnsignedWrap()) {
6419 for (
const SCEV *Operand :
M->operands().drop_front())
6427 for (
const SCEV *Operand :
M->operands())
6429 return GetShiftedByZeros(TZ);
6434 if (
N->hasNoUnsignedWrap())
6435 return GetGCDMultiple(
N);
6438 for (
const SCEV *Operand :
N->operands().drop_front())
6440 return GetShiftedByZeros(TZ);
6457 CtxI = &*F.getEntryBlock().begin();
6463 .countMinTrailingZeros();
6464 return GetShiftedByZeros(Known);
6477 return getConstantMultipleImpl(S, CtxI);
6479 auto I = ConstantMultipleCache.find(S);
6480 if (
I != ConstantMultipleCache.end())
6483 APInt Result = getConstantMultipleImpl(S, CtxI);
6484 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6485 assert(InsertPair.second &&
"Should insert a new key");
6486 return InsertPair.first->second;
6503 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6506 if (std::optional<ConstantRange>
Range = CB->getRange())
6510 if (std::optional<ConstantRange>
Range =
A->getRange())
6513 return std::nullopt;
6520 UnsignedRanges.erase(AddRec);
6521 SignedRanges.erase(AddRec);
6522 ConstantMultipleCache.erase(AddRec);
6527getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6553 Value *Start, *Step;
6560 assert(L && L->getHeader() ==
P->getParent());
6573 case Instruction::AShr:
6574 case Instruction::LShr:
6575 case Instruction::Shl:
6590 KnownStep.getBitWidth() ==
BitWidth);
6593 auto MaxShiftAmt = KnownStep.getMaxValue();
6595 bool Overflow =
false;
6596 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6603 case Instruction::AShr: {
6611 if (KnownStart.isNonNegative())
6614 KnownStart.getMaxValue() + 1);
6615 if (KnownStart.isNegative())
6618 KnownEnd.getMaxValue() + 1);
6621 case Instruction::LShr: {
6630 KnownStart.getMaxValue() + 1);
6632 case Instruction::Shl: {
6636 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6637 return ConstantRange(KnownStart.getMinValue(),
6638 KnownEnd.getMaxValue() + 1);
6646ScalarEvolution::getRangeRefIter(
const SCEV *S,
6647 ScalarEvolution::RangeSignHint SignHint) {
6648 DenseMap<const SCEV *, ConstantRange> &Cache =
6649 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6652 SmallPtrSet<const SCEV *, 8> Seen;
6656 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6657 if (!Seen.
insert(Expr).second)
6691 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6692 const SCEV *
P = WorkList[
I];
6696 for (
const SCEV *
Op :
P->operands())
6702 if (!PendingPhiRangesIter.insert(
P).second)
6709 if (!WorkList.
empty()) {
6714 getRangeRef(
P, SignHint);
6718 PendingPhiRangesIter.erase(
P);
6722 return getRangeRef(S, SignHint, 0);
6729 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6730 DenseMap<const SCEV *, ConstantRange> &Cache =
6731 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6739 if (
I != Cache.
end())
6743 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6748 return getRangeRefIter(S, SignHint);
6751 ConstantRange ConservativeResult(
BitWidth,
true);
6752 using OBO = OverflowingBinaryOperator;
6756 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6760 ConservativeResult =
6767 ConservativeResult = ConstantRange(
6783 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6790 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6797 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6803 return setRange(Cast, SignHint,
X);
6808 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6809 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6811 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6812 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6813 ConservativeResult =
6814 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6816 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6817 unsigned WrapType = OBO::AnyWrap;
6818 if (
Add->hasNoSignedWrap())
6819 WrapType |= OBO::NoSignedWrap;
6820 if (
Add->hasNoUnsignedWrap())
6821 WrapType |= OBO::NoUnsignedWrap;
6823 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6825 return setRange(
Add, SignHint,
6826 ConservativeResult.intersectWith(
X, RangeType));
6830 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6832 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6833 return setRange(
Mul, SignHint,
6834 ConservativeResult.intersectWith(
X, RangeType));
6838 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6839 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6840 return setRange(UDiv, SignHint,
6841 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6849 if (!UnsignedMinValue.
isZero())
6850 ConservativeResult = ConservativeResult.intersectWith(
6851 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6860 bool AllNonNeg =
true;
6861 bool AllNonPos =
true;
6862 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6869 ConservativeResult = ConservativeResult.intersectWith(
6874 ConservativeResult = ConservativeResult.intersectWith(
6883 const SCEV *MaxBEScev =
6897 auto RangeFromAffine = getRangeForAffineAR(
6899 ConservativeResult =
6900 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6902 auto RangeFromFactoring = getRangeViaFactoring(
6904 ConservativeResult =
6905 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6911 const SCEV *SymbolicMaxBECount =
6916 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6917 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6918 ConservativeResult =
6919 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6924 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6934 ID = Intrinsic::umax;
6937 ID = Intrinsic::smax;
6941 ID = Intrinsic::umin;
6944 ID = Intrinsic::smin;
6951 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6952 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6954 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6955 return setRange(S, SignHint,
6956 ConservativeResult.intersectWith(
X, RangeType));
6965 ConservativeResult =
6966 ConservativeResult.intersectWith(*MDRange, RangeType);
6971 auto CR = getRangeForUnknownRecurrence(U);
6972 ConservativeResult = ConservativeResult.intersectWith(CR);
6983 if (
U->getType()->isPointerTy()) {
6986 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
6987 int ptrIdxDiff = ptrSize -
BitWidth;
6988 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
7001 ConservativeResult = ConservativeResult.intersectWith(
7005 ConservativeResult = ConservativeResult.intersectWith(
7010 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
7013 bool CanBeNull, CanBeFreed;
7014 uint64_t DerefBytes =
7015 V->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed);
7025 uint64_t
Align =
U->getValue()->getPointerAlignment(DL).value();
7026 uint64_t Rem = MaxVal.
urem(Align);
7031 ConservativeResult = ConservativeResult.intersectWith(
7039 if (PendingPhiRanges.insert(Phi).second) {
7040 ConstantRange RangeFromOps(
BitWidth,
false);
7042 for (
const auto &
Op :
Phi->operands()) {
7044 RangeFromOps = RangeFromOps.unionWith(OpRange);
7046 if (RangeFromOps.isFullSet())
7049 ConservativeResult =
7050 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7051 bool Erased = PendingPhiRanges.erase(Phi);
7052 assert(Erased &&
"Failed to erase Phi properly?");
7059 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7061 ConservativeResult = ConservativeResult.difference(Disallowed);
7064 return setRange(U, SignHint, std::move(ConservativeResult));
7070 return setRange(S, SignHint, std::move(ConservativeResult));
7079 const APInt &MaxBECount,
7086 if (Step == 0 || MaxBECount == 0)
7093 return ConstantRange::getFull(
BitWidth);
7109 return ConstantRange::getFull(
BitWidth);
7121 APInt MovedBoundary = Descending ? (StartLower - std::move(
Offset))
7122 : (StartUpper + std::move(
Offset));
7127 if (StartRange.
contains(MovedBoundary))
7128 return ConstantRange::getFull(
BitWidth);
7131 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7133 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7142 const APInt &MaxBECount) {
7146 "mismatched bit widths");
7155 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7157 StartSRange, MaxBECount,
7169ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7171 ScalarEvolution::RangeSignHint SignHint) {
7172 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7174 "This only works for non-self-wrapping AddRecs!");
7175 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7179 return ConstantRange::getFull(
BitWidth);
7187 return ConstantRange::getFull(
BitWidth);
7191 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7193 MaxItersWithoutWrap))
7194 return ConstantRange::getFull(
BitWidth);
7215 ConstantRange StartRange = getRangeRef(Start, SignHint);
7216 ConstantRange EndRange = getRangeRef(End, SignHint);
7217 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7221 return RangeBetween;
7226 return ConstantRange::getFull(
BitWidth);
7229 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7230 return RangeBetween;
7232 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7233 return RangeBetween;
7234 return ConstantRange::getFull(
BitWidth);
7239 const APInt &MaxBECount) {
7246 "mismatched bit widths");
7248 struct SelectPattern {
7249 Value *Condition =
nullptr;
7253 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7255 std::optional<unsigned> CastOp;
7269 CastOp = SCast->getSCEVType();
7270 S = SCast->getOperand();
7273 using namespace llvm::PatternMatch;
7280 Condition =
nullptr;
7312 bool isRecognized() {
return Condition !=
nullptr; }
7315 SelectPattern StartPattern(*
this,
BitWidth, Start);
7316 if (!StartPattern.isRecognized())
7317 return ConstantRange::getFull(
BitWidth);
7319 SelectPattern StepPattern(*
this,
BitWidth, Step);
7320 if (!StepPattern.isRecognized())
7321 return ConstantRange::getFull(
BitWidth);
7323 if (StartPattern.Condition != StepPattern.Condition) {
7327 return ConstantRange::getFull(
BitWidth);
7338 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7339 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7340 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7341 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7343 ConstantRange TrueRange =
7344 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount);
7345 ConstantRange FalseRange =
7346 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount);
7368ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7382 SmallPtrSet<const SCEV *, 16> Visited;
7384 auto pushOp = [&](
const SCEV *S) {
7385 if (!Visited.
insert(S).second)
7388 if (Visited.
size() > 30) {
7395 for (
const auto *S :
Ops)
7399 while (!Worklist.
empty()) {
7401 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7402 if (!Bound || DT.dominates(Bound, DefI))
7409 return Bound ? Bound : &*F.getEntryBlock().begin();
7415 return getDefiningScopeBound(
Ops, Discard);
7418bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7420 if (
A->getParent() ==
B->getParent() &&
7425 auto *BLoop = LI.getLoopFor(
B->getParent());
7426 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7427 BLoop->getLoopPreheader() ==
A->getParent() &&
7429 A->getParent()->end()) &&
7436bool ScalarEvolution::isGuaranteedNotToBePoison(
const SCEV *
Op) {
7437 SCEVPoisonCollector PC(
true);
7439 return PC.MaybePoison.empty();
7442bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7448 return M && (!
isKnownNonZero(Op1) || !isGuaranteedNotToBePoison(Op1));
7452bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7469 for (
const Use &
Op :
I->operands()) {
7475 auto *DefI = getDefiningScopeBound(SCEVOps);
7476 return isGuaranteedToTransferExecutionTo(DefI,
I);
7479bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7481 if (isSCEVExprNeverPoison(
I))
7492 auto *ExitingBB =
L->getExitingBlock();
7496 SmallPtrSet<const Value *, 16> KnownPoison;
7505 while (!Worklist.
empty()) {
7508 for (
const Use &U :
Poison->uses()) {
7511 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7515 if (KnownPoison.
insert(PoisonUser).second)
7523ScalarEvolution::LoopProperties
7524ScalarEvolution::getLoopProperties(
const Loop *L) {
7525 using LoopProperties = ScalarEvolution::LoopProperties;
7527 auto Itr = LoopPropertiesCache.find(L);
7528 if (Itr == LoopPropertiesCache.end()) {
7531 return !
SI->isSimple();
7541 return I->mayWriteToMemory();
7544 LoopProperties LP = {
true,
7547 for (
auto *BB :
L->getBlocks())
7548 for (
auto &
I : *BB) {
7550 LP.HasNoAbnormalExits =
false;
7551 if (HasSideEffects(&
I))
7552 LP.HasNoSideEffects =
false;
7553 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7557 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7558 assert(InsertPair.second &&
"We just checked!");
7559 Itr = InsertPair.first;
7572const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7578 Stack.emplace_back(V,
true);
7579 Stack.emplace_back(V,
false);
7580 while (!Stack.empty()) {
7581 auto E = Stack.pop_back_val();
7582 Value *CurV = E.getPointer();
7588 const SCEV *CreatedSCEV =
nullptr;
7591 CreatedSCEV = createSCEV(CurV);
7596 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7600 insertValueToMap(CurV, CreatedSCEV);
7604 Stack.emplace_back(CurV,
true);
7606 Stack.emplace_back(
Op,
false);
7623 if (!DT.isReachableFromEntry(
I->getParent()))
7636 switch (BO->Opcode) {
7637 case Instruction::Add:
7638 case Instruction::Mul: {
7645 Ops.push_back(BO->
Op);
7649 Ops.push_back(BO->RHS);
7653 (BO->Opcode == Instruction::Add &&
7654 (NewBO->Opcode != Instruction::Add &&
7655 NewBO->Opcode != Instruction::Sub)) ||
7656 (BO->Opcode == Instruction::Mul &&
7657 NewBO->Opcode != Instruction::Mul)) {
7658 Ops.push_back(BO->LHS);
7663 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7666 Ops.push_back(BO->LHS);
7674 case Instruction::Sub:
7675 case Instruction::UDiv:
7676 case Instruction::URem:
7678 case Instruction::AShr:
7679 case Instruction::Shl:
7680 case Instruction::Xor:
7684 case Instruction::And:
7685 case Instruction::Or:
7689 case Instruction::LShr:
7696 Ops.push_back(BO->LHS);
7697 Ops.push_back(BO->RHS);
7701 switch (
U->getOpcode()) {
7702 case Instruction::Trunc:
7703 case Instruction::ZExt:
7704 case Instruction::SExt:
7705 case Instruction::PtrToAddr:
7706 case Instruction::PtrToInt:
7707 Ops.push_back(
U->getOperand(0));
7710 case Instruction::BitCast:
7712 Ops.push_back(
U->getOperand(0));
7717 case Instruction::SDiv:
7718 case Instruction::SRem:
7719 Ops.push_back(
U->getOperand(0));
7720 Ops.push_back(
U->getOperand(1));
7723 case Instruction::GetElementPtr:
7725 "GEP source element type must be sized");
7729 case Instruction::IntToPtr:
7732 case Instruction::PHI:
7736 case Instruction::Select: {
7738 auto CanSimplifyToUnknown = [
this,
U]() {
7756 if (CanSimplifyToUnknown())
7763 case Instruction::Call:
7764 case Instruction::Invoke:
7771 switch (
II->getIntrinsicID()) {
7772 case Intrinsic::abs:
7773 Ops.push_back(
II->getArgOperand(0));
7775 case Intrinsic::umax:
7776 case Intrinsic::umin:
7777 case Intrinsic::smax:
7778 case Intrinsic::smin:
7779 case Intrinsic::usub_sat:
7780 case Intrinsic::uadd_sat:
7781 Ops.push_back(
II->getArgOperand(0));
7782 Ops.push_back(
II->getArgOperand(1));
7784 case Intrinsic::start_loop_iterations:
7785 case Intrinsic::annotation:
7786 case Intrinsic::ptr_annotation:
7787 Ops.push_back(
II->getArgOperand(0));
7799const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7808 if (!DT.isReachableFromEntry(
I->getParent()))
7823 switch (BO->Opcode) {
7824 case Instruction::Add: {
7850 if (BO->Opcode == Instruction::Sub)
7858 if (BO->Opcode == Instruction::Sub)
7865 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7866 NewBO->Opcode != Instruction::Sub)) {
7876 case Instruction::Mul: {
7897 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7906 case Instruction::UDiv:
7910 case Instruction::URem:
7914 case Instruction::Sub: {
7917 Flags = getNoWrapFlagsFromUB(BO->
Op);
7922 case Instruction::And:
7928 if (CI->isMinusOne())
7930 const APInt &
A = CI->getValue();
7936 unsigned LZ =
A.countl_zero();
7937 unsigned TZ =
A.countr_zero();
7942 APInt EffectiveMask =
7944 if ((LZ != 0 || TZ != 0) && !((~
A & ~Known.
Zero) & EffectiveMask)) {
7947 const SCEV *ShiftedLHS =
nullptr;
7951 unsigned MulZeros = OpC->getAPInt().countr_zero();
7952 unsigned GCD = std::min(MulZeros, TZ);
7957 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
7979 case Instruction::Or:
7988 case Instruction::Xor:
7991 if (CI->isMinusOne())
8000 if (LBO->getOpcode() == Instruction::And &&
8001 LCI->getValue() == CI->getValue())
8002 if (
const SCEVZeroExtendExpr *Z =
8005 const SCEV *Z0 =
Z->getOperand();
8012 if (CI->getValue().isMask(Z0TySize))
8018 APInt Trunc = CI->getValue().trunc(Z0TySize);
8027 case Instruction::Shl:
8045 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8053 ConstantInt *
X = ConstantInt::get(
8059 case Instruction::AShr:
8081 const SCEV *AddTruncateExpr =
nullptr;
8082 ConstantInt *ShlAmtCI =
nullptr;
8083 const SCEV *AddConstant =
nullptr;
8085 if (L &&
L->getOpcode() == Instruction::Add) {
8093 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8100 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8108 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8113 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8118 if (AddTruncateExpr && ShlAmtCI) {
8130 const APInt &ShlAmt = ShlAmtCI->
getValue();
8134 const SCEV *CompositeExpr =
8136 if (
L->getOpcode() != Instruction::Shl)
8137 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8146 switch (
U->getOpcode()) {
8147 case Instruction::Trunc:
8150 case Instruction::ZExt:
8153 case Instruction::SExt:
8163 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8164 Type *Ty =
U->getType();
8172 case Instruction::BitCast:
8178 case Instruction::PtrToAddr:
8181 case Instruction::PtrToInt: {
8184 Type *DstIntTy =
U->getType();
8192 case Instruction::IntToPtr:
8196 case Instruction::SDiv:
8203 case Instruction::SRem:
8210 case Instruction::GetElementPtr:
8213 case Instruction::PHI:
8216 case Instruction::Select:
8217 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8220 case Instruction::Call:
8221 case Instruction::Invoke:
8226 switch (
II->getIntrinsicID()) {
8227 case Intrinsic::abs:
8231 case Intrinsic::umax:
8235 case Intrinsic::umin:
8239 case Intrinsic::smax:
8243 case Intrinsic::smin:
8247 case Intrinsic::usub_sat: {
8248 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8249 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8253 case Intrinsic::uadd_sat: {
8254 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8255 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8259 case Intrinsic::start_loop_iterations:
8260 case Intrinsic::annotation:
8261 case Intrinsic::ptr_annotation:
8265 case Intrinsic::vscale:
8285 auto *ExitCountType = ExitCount->
getType();
8286 assert(ExitCountType->isIntegerTy());
8288 1 + ExitCountType->getScalarSizeInBits());
8301 auto CanAddOneWithoutOverflow = [&]() {
8303 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8314 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8344 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8345 assert(L->isLoopExiting(ExitingBlock) &&
8346 "Exiting block must actually branch out of the loop!");
8355 const auto *MaxExitCount =
8363 L->getExitingBlocks(ExitingBlocks);
8365 std::optional<unsigned> Res;
8366 for (
auto *ExitingBB : ExitingBlocks) {
8370 Res = std::gcd(*Res, Multiple);
8372 return Res.value_or(1);
8376 const SCEV *ExitCount) {
8406 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8407 assert(L->isLoopExiting(ExitingBlock) &&
8408 "Exiting block must actually branch out of the loop!");
8418 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8420 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8422 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8432 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8435 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8438 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8446 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8453 return getBackedgeTakenInfo(L).getExact(L,
this);
8455 return getBackedgeTakenInfo(L).getConstantMax(
this);
8457 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8464 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8469 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8473 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8483 for (
PHINode &PN : Header->phis())
8484 if (Visited.
insert(&PN).second)
8488ScalarEvolution::BackedgeTakenInfo &
8489ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8490 auto &BTI = getBackedgeTakenInfo(L);
8491 if (BTI.hasFullInfo())
8494 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8497 return Pair.first->second;
8499 BackedgeTakenInfo
Result =
8500 computeBackedgeTakenCount(L,
true);
8502 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8505ScalarEvolution::BackedgeTakenInfo &
8506ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8512 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8513 BackedgeTakenCounts.try_emplace(L);
8515 return Pair.first->second;
8520 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8527 if (
Result.hasAnyInfo()) {
8530 auto LoopUsersIt = LoopUsers.find(L);
8531 if (LoopUsersIt != LoopUsers.end())
8533 forgetMemoizedResults(ToForget);
8536 for (PHINode &PN :
L->getHeader()->phis())
8537 ConstantEvolutionLoopExitValue.erase(&PN);
8545 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8554 BackedgeTakenCounts.clear();
8555 PredicatedBackedgeTakenCounts.clear();
8556 BECountUsers.clear();
8557 LoopPropertiesCache.clear();
8558 ConstantEvolutionLoopExitValue.clear();
8559 ValueExprMap.clear();
8560 ValuesAtScopes.clear();
8561 ValuesAtScopesUsers.clear();
8562 LoopDispositions.clear();
8563 BlockDispositions.clear();
8564 UnsignedRanges.clear();
8565 SignedRanges.clear();
8566 ExprValueMap.clear();
8568 ConstantMultipleCache.clear();
8569 PredicatedSCEVRewrites.clear();
8571 FoldCacheUser.clear();
8573void ScalarEvolution::visitAndClearUsers(
8577 while (!Worklist.
empty()) {
8584 if (It != ValueExprMap.
end()) {
8585 eraseValueFromMap(It->first);
8588 ConstantEvolutionLoopExitValue.erase(PN);
8602 while (!LoopWorklist.
empty()) {
8606 forgetBackedgeTakenCounts(CurrL,
false);
8607 forgetBackedgeTakenCounts(CurrL,
true);
8610 for (
auto I = PredicatedSCEVRewrites.begin();
8611 I != PredicatedSCEVRewrites.end();) {
8612 std::pair<const SCEV *, const Loop *> Entry =
I->first;
8613 if (Entry.second == CurrL)
8614 PredicatedSCEVRewrites.erase(
I++);
8619 auto LoopUsersItr = LoopUsers.find(CurrL);
8620 if (LoopUsersItr != LoopUsers.end())
8625 visitAndClearUsers(Worklist, Visited, ToForget);
8627 LoopPropertiesCache.erase(CurrL);
8630 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8632 forgetMemoizedResults(ToForget);
8649 visitAndClearUsers(Worklist, Visited, ToForget);
8651 forgetMemoizedResults(ToForget);
8663 struct InvalidationRootCollector {
8667 InvalidationRootCollector(
Loop *L) : L(L) {}
8669 bool follow(
const SCEV *S) {
8675 if (L->contains(AddRec->
getLoop()))
8680 bool isDone()
const {
return false; }
8683 InvalidationRootCollector
C(L);
8685 forgetMemoizedResults(
C.Roots);
8698 BlockDispositions.clear();
8699 LoopDispositions.clear();
8716 while (!Worklist.
empty()) {
8718 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8719 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8720 if (!LoopDispoRemoved && !BlockDispoRemoved)
8722 auto Users = SCEVUsers.find(Curr);
8723 if (
Users != SCEVUsers.end())
8736const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8740 if (!isComplete() || ExitNotTaken.
empty())
8751 for (
const auto &ENT : ExitNotTaken) {
8752 const SCEV *BECount = ENT.ExactNotTaken;
8755 "We should only have known counts for exiting blocks that dominate "
8758 Ops.push_back(BECount);
8763 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8764 "Predicate should be always true!");
8773const ScalarEvolution::ExitNotTakenInfo *
8774ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8775 const BasicBlock *ExitingBlock,
8776 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8777 for (
const auto &ENT : ExitNotTaken)
8778 if (ENT.ExitingBlock == ExitingBlock) {
8779 if (ENT.hasAlwaysTruePredicate())
8781 else if (Predicates) {
8791const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8793 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8794 if (!getConstantMax())
8797 for (
const auto &ENT : ExitNotTaken)
8798 if (!ENT.hasAlwaysTruePredicate()) {
8806 "No point in having a non-constant max backedge taken count!");
8807 return getConstantMax();
8810const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8812 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8820 for (
const auto &ENT : ExitNotTaken) {
8821 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8824 "We should only have known counts for exiting blocks that "
8830 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8831 "Predicate should be always true!");
8834 if (ExitCounts.
empty())
8843bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8845 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8846 return !ENT.hasAlwaysTruePredicate();
8848 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8864 this->ExactNotTaken = E = ConstantMaxNotTaken;
8865 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8870 "Exact is not allowed to be less precise than Constant Max");
8873 "Exact is not allowed to be less precise than Symbolic Max");
8876 "Symbolic Max is not allowed to be less precise than Constant Max");
8879 "No point in having a non-constant max backedge taken count!");
8881 for (
const auto PredList : PredLists)
8882 for (
const auto *
P : PredList) {
8890 "Backedge count should be int");
8893 "Max backedge count should be int");
8906ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8908 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8909 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8910 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8912 ExitNotTaken.reserve(ExitCounts.
size());
8913 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8914 std::back_inserter(ExitNotTaken),
8915 [&](
const EdgeExitInfo &EEI) {
8916 BasicBlock *ExitBB = EEI.first;
8917 const ExitLimit &EL = EEI.second;
8918 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
8919 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
8924 "No point in having a non-constant max backedge taken count!");
8928ScalarEvolution::BackedgeTakenInfo
8929ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
8930 bool AllowPredicates) {
8932 L->getExitingBlocks(ExitingBlocks);
8934 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8937 bool CouldComputeBECount =
true;
8939 const SCEV *MustExitMaxBECount =
nullptr;
8940 const SCEV *MayExitMaxBECount =
nullptr;
8941 bool MustExitMaxOrZero =
false;
8942 bool IsOnlyExit = ExitingBlocks.
size() == 1;
8954 if (ExitIfTrue == CI->
isZero())
8958 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
8960 assert((AllowPredicates || EL.Predicates.empty()) &&
8961 "Predicated exit limit when predicates are not allowed!");
8966 ++NumExitCountsComputed;
8970 CouldComputeBECount =
false;
8977 "Exact is known but symbolic isn't?");
8978 ++NumExitCountsNotComputed;
8993 DT.dominates(ExitBB, Latch)) {
8994 if (!MustExitMaxBECount) {
8995 MustExitMaxBECount = EL.ConstantMaxNotTaken;
8996 MustExitMaxOrZero = EL.MaxOrZero;
8999 EL.ConstantMaxNotTaken);
9003 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9006 EL.ConstantMaxNotTaken);
9010 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9014 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9020 for (
const auto &Pair : ExitCounts) {
9022 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9024 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9025 {
L, AllowPredicates});
9027 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9028 MaxBECount, MaxOrZero);
9031ScalarEvolution::ExitLimit
9032ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9033 bool IsOnlyExit,
bool AllowPredicates) {
9034 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9038 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9046 "It should have one successor in loop and one exit block!");
9057 if (!
L->contains(SBB)) {
9062 assert(Exit &&
"Exiting block must have at least one exit");
9063 return computeExitLimitFromSingleExitSwitch(
9064 L, SI, Exit, IsOnlyExit);
9071 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9072 bool AllowPredicates) {
9073 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9074 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9075 ControlsOnlyExit, AllowPredicates);
9078std::optional<ScalarEvolution::ExitLimit>
9079ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9080 bool ExitIfTrue,
bool ControlsOnlyExit,
9081 bool AllowPredicates) {
9083 (void)this->ExitIfTrue;
9084 (void)this->AllowPredicates;
9086 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9087 this->AllowPredicates == AllowPredicates &&
9088 "Variance in assumed invariant key components!");
9089 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9090 if (Itr == TripCountMap.end())
9091 return std::nullopt;
9095void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9097 bool ControlsOnlyExit,
9098 bool AllowPredicates,
9100 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9101 this->AllowPredicates == AllowPredicates &&
9102 "Variance in assumed invariant key components!");
9104 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9105 assert(InsertResult.second &&
"Expected successful insertion!");
9110ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9111 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9112 bool ControlsOnlyExit,
bool AllowPredicates) {
9114 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9118 ExitLimit EL = computeExitLimitFromCondImpl(
9119 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9120 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9124ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9125 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9126 bool ControlsOnlyExit,
bool AllowPredicates) {
9128 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9129 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates))
9130 return *LimitFromBinOp;
9136 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9137 if (EL.hasFullInfo() || !AllowPredicates)
9141 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9161 const WithOverflowInst *WO;
9176 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9177 ControlsOnlyExit, AllowPredicates);
9178 if (EL.hasAnyInfo())
9183 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9186std::optional<ScalarEvolution::ExitLimit>
9187ScalarEvolution::computeExitLimitFromCondFromBinOp(
9188 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9189 bool ControlsOnlyExit,
bool AllowPredicates) {
9198 return std::nullopt;
9203 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9204 ExitLimit EL0 = computeExitLimitFromCondCached(
9205 Cache, L, Op0, ExitIfTrue, ControlsOnlyExit && !EitherMayExit,
9207 ExitLimit EL1 = computeExitLimitFromCondCached(
9208 Cache, L, Op1, ExitIfTrue, ControlsOnlyExit && !EitherMayExit,
9212 const Constant *NeutralElement = ConstantInt::get(ExitCond->
getType(), IsAnd);
9214 return Op1 == NeutralElement ? EL0 : EL1;
9216 return Op0 == NeutralElement ? EL1 : EL0;
9221 if (EitherMayExit) {
9231 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9233 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9236 EL1.ConstantMaxNotTaken);
9238 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9240 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9243 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9247 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9248 BECount = EL0.ExactNotTaken;
9261 SymbolicMaxBECount =
9263 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9267ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9268 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9269 bool AllowPredicates) {
9281 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9283 if (EL.hasAnyInfo())
9286 auto *ExhaustiveCount =
9287 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9290 return ExhaustiveCount;
9292 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9295ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9296 const Loop *L, CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
9297 bool ControlsOnlyExit,
bool AllowPredicates) {
9322 ConstantRange CompRange =
9338 auto *InnerLHS =
LHS;
9340 InnerLHS = ZExt->getOperand();
9387 if (EL.hasAnyInfo())
9404 if (EL.hasAnyInfo())
return EL;
9436 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9438 if (EL.hasAnyInfo())
9454 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9456 if (EL.hasAnyInfo())
9467ScalarEvolution::ExitLimit
9468ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9470 BasicBlock *ExitingBlock,
9471 bool ControlsOnlyExit) {
9472 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9475 if (
Switch->getDefaultDest() == ExitingBlock)
9479 "Default case must not exit the loop!");
9485 if (EL.hasAnyInfo())
9497 "Evaluation of SCEV at constant didn't fold correctly?");
9501ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9511 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9517 auto MatchPositiveShift =
9520 using namespace PatternMatch;
9522 ConstantInt *ShiftAmt;
9524 OutOpCode = Instruction::LShr;
9526 OutOpCode = Instruction::AShr;
9528 OutOpCode = Instruction::Shl;
9543 auto MatchShiftRecurrence =
9545 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9560 if (MatchPositiveShift(
LHS, V, OpC)) {
9561 PostShiftOpCode = OpC;
9567 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9570 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9576 MatchPositiveShift(BEValue, OpLHS, OpCodeOut) &&
9583 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9588 if (!MatchShiftRecurrence(
LHS, PN, OpCode))
9600 ConstantInt *StableValue =
nullptr;
9605 case Instruction::AShr: {
9613 StableValue = ConstantInt::get(Ty, 0);
9615 StableValue = ConstantInt::get(Ty, -1,
true);
9621 case Instruction::LShr:
9622 case Instruction::Shl:
9632 "Otherwise cannot be an operand to a branch instruction");
9634 if (
Result->isZeroValue()) {
9636 const SCEV *UpperBound =
9653 if (
const Function *
F = CI->getCalledFunction())
9662 if (!L->contains(
I))
return false;
9667 return L->getHeader() ==
I->getParent();
9743 if (!
I)
return nullptr;
9756 std::vector<Constant*> Operands(
I->getNumOperands());
9758 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9762 if (!Operands[i])
return nullptr;
9767 if (!
C)
return nullptr;
9789 if (IncomingVal != CurrentVal) {
9792 IncomingVal = CurrentVal;
9804ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9807 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9816 DenseMap<Instruction *, Constant *> CurrentIterVals;
9818 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9824 for (PHINode &
PHI : Header->phis()) {
9826 CurrentIterVals[&
PHI] = StartCST;
9828 if (!CurrentIterVals.
count(PN))
9829 return RetVal =
nullptr;
9835 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9838 unsigned IterationNum = 0;
9840 for (; ; ++IterationNum) {
9841 if (IterationNum == NumIterations)
9842 return RetVal = CurrentIterVals[PN];
9846 DenseMap<Instruction *, Constant *> NextIterVals;
9851 NextIterVals[PN] = NextPHI;
9853 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9859 for (
const auto &
I : CurrentIterVals) {
9861 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9866 for (
const auto &
I : PHIsToCompute) {
9867 PHINode *
PHI =
I.first;
9870 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9873 if (NextPHI !=
I.second)
9874 StoppedEvolving =
false;
9879 if (StoppedEvolving)
9880 return RetVal = CurrentIterVals[PN];
9882 CurrentIterVals.swap(NextIterVals);
9886const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
9896 DenseMap<Instruction *, Constant *> CurrentIterVals;
9898 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9901 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
9903 for (PHINode &
PHI : Header->phis()) {
9905 CurrentIterVals[&
PHI] = StartCST;
9907 if (!CurrentIterVals.
count(PN))
9915 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
9922 if (CondVal->getValue() == uint64_t(ExitWhen)) {
9923 ++NumBruteForceTripCountsComputed;
9928 DenseMap<Instruction *, Constant *> NextIterVals;
9934 for (
const auto &
I : CurrentIterVals) {
9936 if (!
PHI ||
PHI->getParent() != Header)
continue;
9939 for (PHINode *
PHI : PHIsToCompute) {
9941 if (NextPHI)
continue;
9943 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9946 CurrentIterVals.
swap(NextIterVals);
9957 for (
auto &LS : Values)
9959 return LS.second ? LS.second : V;
9964 const SCEV *
C = computeSCEVAtScope(V, L);
9965 for (
auto &LS :
reverse(ValuesAtScopes[V]))
9966 if (LS.first == L) {
9969 ValuesAtScopesUsers[
C].push_back({L, V});
9980 switch (V->getSCEVType()) {
10020 assert(!
C->getType()->isPointerTy() &&
10021 "Can only have one pointer, and it must be last");
10048ScalarEvolution::getWithOperands(
const SCEV *S,
10049 SmallVectorImpl<const SCEV *> &NewOps) {
10084const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10085 switch (
V->getSCEVType()) {
10096 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10107 for (++i; i !=
e; ++i)
10152 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10154 if (OpAtScope !=
Ops[i]) {
10162 for (++i; i !=
e; ++i) {
10167 return getWithOperands(V, NewOps);
10182 const Loop *CurrLoop = this->LI[
I->getParent()];
10193 if (BackedgeTakenCount->
isZero()) {
10194 Value *InitValue =
nullptr;
10195 bool MultipleInitValues =
false;
10201 MultipleInitValues =
true;
10206 if (!MultipleInitValues && InitValue)
10215 unsigned InLoopPred =
10226 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10240 SmallVector<Constant *, 4> Operands;
10241 Operands.
reserve(
I->getNumOperands());
10242 bool MadeImprovement =
false;
10257 MadeImprovement |= OrigV != OpV;
10262 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10267 if (!MadeImprovement)
10288const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10290 return stripInjectiveFunctions(ZExt->getOperand());
10292 return stripInjectiveFunctions(SExt->getOperand());
10310 assert(
A != 0 &&
"A must be non-zero.");
10326 if (MinTZ < Mult2 && L->getLoopPredecessor())
10328 if (MinTZ < Mult2) {
10351 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10371static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10377 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10378 << *AddRec <<
'\n');
10381 if (!LC || !MC || !
NC) {
10382 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10383 return std::nullopt;
10389 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10397 N =
N.sext(NewWidth);
10398 M = M.sext(NewWidth);
10399 L = L.sext(NewWidth);
10416 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10417 <<
", multiplied by " <<
T <<
'\n');
10426 std::optional<APInt>
Y) {
10428 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10431 return XW.
slt(YW) ? *
X : *
Y;
10434 return std::nullopt;
10435 return X ? *
X : *
Y;
10452 return std::nullopt;
10453 unsigned W =
X->getBitWidth();
10473static std::optional<APInt>
10479 return std::nullopt;
10482 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10483 std::optional<APInt>
X =
10486 return std::nullopt;
10491 return std::nullopt;
10506static std::optional<APInt>
10510 "Starting value of addrec should be 0");
10511 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10512 <<
Range <<
", addrec " << *AddRec <<
'\n');
10516 "Addrec's initial value should be in range");
10522 return std::nullopt;
10532 auto SolveForBoundary =
10533 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10536 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10537 << Bound <<
" (before multiplying by " << M <<
")\n");
10540 std::optional<APInt> SO;
10543 "signed overflow\n");
10547 "unsigned overflow\n");
10548 std::optional<APInt> UO =
10551 auto LeavesRange = [&] (
const APInt &
X) {
10568 return {std::nullopt,
false};
10573 if (LeavesRange(*Min))
10574 return { Min,
true };
10575 std::optional<APInt> Max = Min == SO ? UO : SO;
10576 if (LeavesRange(*Max))
10577 return { Max,
true };
10580 return {std::nullopt,
true};
10587 auto SL = SolveForBoundary(
Lower);
10588 auto SU = SolveForBoundary(
Upper);
10591 if (!SL.second || !SU.second)
10592 return std::nullopt;
10635ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10637 bool ControlsOnlyExit,
10638 bool AllowPredicates) {
10649 if (
C->getValue()->isZero())
return C;
10653 const SCEVAddRecExpr *AddRec =
10656 if (!AddRec && AllowPredicates)
10662 if (!AddRec || AddRec->
getLoop() != L)
10673 return ExitLimit(R, R, R,
false, Predicates);
10731 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10757 const SCEV *
Exact =
10765 const SCEV *SymbolicMax =
10767 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10776 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10784 return ExitLimit(
E, M, S,
false, Predicates);
10787ScalarEvolution::ExitLimit
10788ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10796 if (!
C->getValue()->isZero())
10806std::pair<const BasicBlock *, const BasicBlock *>
10807ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10818 if (
const Loop *L = LI.getLoopFor(BB))
10819 return {
L->getLoopPredecessor(),
L->getHeader()};
10821 return {
nullptr, BB};
10830 if (
A ==
B)
return true;
10845 if (ComputesEqualValues(AI, BI))
10853 const SCEV *Op0, *Op1;
10872 auto TrivialCase = [&](
bool TriviallyTrue) {
10881 const SCEV *NewLHS, *NewRHS;
10905 return TrivialCase(
false);
10906 return TrivialCase(
true);
10929 const APInt &
RA = RC->getAPInt();
10931 bool SimplifiedByConstantRange =
false;
10936 return TrivialCase(
true);
10938 return TrivialCase(
false);
10947 Changed = SimplifiedByConstantRange =
true;
10951 if (!SimplifiedByConstantRange) {
10968 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
10974 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
10980 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
10986 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
10998 return TrivialCase(
true);
11000 return TrivialCase(
false);
11105 auto NonRecursive = [
this, OrNegative](
const SCEV *S) {
11107 return C->getAPInt().isPowerOf2() ||
11108 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11111 return isa<SCEVVScale>(S) && F.hasFnAttribute(Attribute::VScaleRange);
11114 if (NonRecursive(S))
11140 APInt C = Cst->getAPInt();
11141 return C.urem(M) == 0;
11149 const SCEV *SmodM =
11164 for (
auto *
A : Assumptions)
11165 if (
A->implies(
P, *
this))
11178std::pair<const SCEV *, const SCEV *>
11181 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11183 return { Start, Start };
11185 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11194 getUsedLoops(LHS, LoopsUsed);
11195 getUsedLoops(RHS, LoopsUsed);
11197 if (LoopsUsed.
empty())
11202 for (
const auto *L1 : LoopsUsed)
11203 for (
const auto *L2 : LoopsUsed)
11204 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11205 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11206 "Domination relationship is not a linear order");
11236 SplitRHS.second) &&
11248 if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
11252 return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11262 return std::nullopt;
11277 if (KnownWithoutContext)
11278 return KnownWithoutContext;
11285 return std::nullopt;
11291 const Loop *L = LHS->getLoop();
11296std::optional<ScalarEvolution::MonotonicPredicateType>
11299 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11305 auto ResultSwapped =
11308 assert(*ResultSwapped != *Result &&
11309 "monotonicity should flip as we flip the predicate");
11316std::optional<ScalarEvolution::MonotonicPredicateType>
11317ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11331 return std::nullopt;
11335 "Should be greater or less!");
11339 if (!LHS->hasNoUnsignedWrap())
11340 return std::nullopt;
11344 "Relational predicate is either signed or unsigned!");
11345 if (!
LHS->hasNoSignedWrap())
11346 return std::nullopt;
11348 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11356 return std::nullopt;
11359std::optional<ScalarEvolution::LoopInvariantPredicate>
11366 return std::nullopt;
11373 if (!ArLHS || ArLHS->
getLoop() != L)
11374 return std::nullopt;
11378 return std::nullopt;
11404 return std::nullopt;
11441 return std::nullopt;
11444std::optional<ScalarEvolution::LoopInvariantPredicate>
11449 Pred, LHS, RHS, L, CtxI, MaxIter))
11457 for (
auto *
Op :
UMin->operands())
11459 Pred, LHS, RHS, L, CtxI,
Op))
11461 return std::nullopt;
11464std::optional<ScalarEvolution::LoopInvariantPredicate>
11479 return std::nullopt;
11486 if (!AR || AR->
getLoop() != L)
11487 return std::nullopt;
11491 return std::nullopt;
11497 if (Step != One && Step != MinusOne)
11498 return std::nullopt;
11504 return std::nullopt;
11510 return std::nullopt;
11518 if (Step == MinusOne)
11522 return std::nullopt;
11528bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11534 auto CheckRange = [&](
bool IsSigned) {
11537 return RangeLHS.
icmp(Pred, RangeRHS);
11546 if (CheckRange(
true) || CheckRange(
false))
11555bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11562 auto MatchBinaryAddToConst = [
this](
const SCEV *
X,
const SCEV *
Y,
11563 APInt &OutC1, APInt &OutC2,
11565 const SCEV *XNonConstOp, *XConstOp;
11566 const SCEV *YNonConstOp, *YConstOp;
11570 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11573 XFlagsPresent = ExpectedFlags;
11578 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11581 YFlagsPresent = ExpectedFlags;
11584 if (YNonConstOp != XNonConstOp)
11592 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11595 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11655bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11677bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11678 const SCEV *
LHS,
const SCEV *
RHS) {
11683 return any_of(*BB, [&](
const Instruction &
I) {
11684 using namespace llvm::PatternMatch;
11689 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11703 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11708 "This cannot be done on broken IR!");
11711 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11720 if (LoopContinuePredicate && LoopContinuePredicate->
isConditional() &&
11721 isImpliedCond(Pred, LHS, RHS,
11723 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11728 if (WalkingBEDominatingConds)
11734 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11735 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11742 const SCEV *LoopCounter =
11750 for (
auto &AssumeVH : AC.assumptions()) {
11757 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11761 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11764 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11765 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11766 assert(DTN &&
"should reach the loop header before reaching the root!");
11769 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11777 if (!ContinuePredicate || !ContinuePredicate->
isConditional())
11791 assert(DT.dominates(DominatingEdge, Latch) &&
"should be!");
11793 if (isImpliedCond(Pred, LHS, RHS, Condition,
11807 if (!DT.isReachableFromEntry(BB))
11811 "This cannot be done on broken IR!");
11819 const bool ProvingStrictComparison =
11821 bool ProvedNonStrictComparison =
false;
11822 bool ProvedNonEquality =
false;
11825 if (!ProvedNonStrictComparison)
11826 ProvedNonStrictComparison = Fn(NonStrictPredicate);
11827 if (!ProvedNonEquality)
11829 if (ProvedNonStrictComparison && ProvedNonEquality)
11834 if (ProvingStrictComparison) {
11836 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
11838 if (SplitAndProve(ProofFn))
11843 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
11845 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
11847 if (ProvingStrictComparison) {
11849 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
11851 if (SplitAndProve(ProofFn))
11860 const Loop *ContainingLoop = LI.getLoopFor(BB);
11862 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
11866 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
11867 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
11879 for (
auto &AssumeVH : AC.assumptions()) {
11883 if (!DT.dominates(CI, BB))
11886 if (ProveViaCond(CI->getArgOperand(0),
false))
11892 F.getParent(), Intrinsic::experimental_guard);
11894 for (
const auto *GU : GuardDecl->users())
11896 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
11897 if (ProveViaCond(Guard->getArgOperand(0),
false))
11912 "LHS is not available at Loop Entry");
11914 "RHS is not available at Loop Entry");
11916 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11927 if (FoundCondValue ==
11931 if (!PendingLoopPredicates.insert(FoundCondValue).second)
11935 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
11938 const Value *Op0, *Op1;
11941 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
11945 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
11946 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
11950 if (!ICI)
return false;
11954 CmpPredicate FoundPred;
11963 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
11966bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
11967 const SCEV *
RHS, CmpPredicate FoundPred,
11968 const SCEV *FoundLHS,
const SCEV *FoundRHS,
11969 const Instruction *CtxI) {
11979 auto *WideType = FoundLHS->
getType();
11991 TruncFoundLHS, TruncFoundRHS, CtxI))
12017 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12021bool ScalarEvolution::isImpliedCondBalancedTypes(
12022 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
12023 const SCEV *FoundLHS,
const SCEV *FoundRHS,
const Instruction *CtxI) {
12026 "Types should be balanced!");
12033 if (FoundLHS == FoundRHS)
12037 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12049 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12066 LHS, FoundLHS, FoundRHS, CtxI);
12068 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12090 assert(P1 != P2 &&
"Handled earlier!");
12094 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12098 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12101 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12102 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12103 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12108 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12119 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12120 CanonicalRHS, CanonicalFoundLHS,
12121 CanonicalFoundRHS);
12126 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12127 CanonicalRHS, CanonicalFoundLHS,
12128 CanonicalFoundRHS);
12135 const SCEVConstant *
C =
nullptr;
12136 const SCEV *
V =
nullptr;
12154 if (Min ==
C->getAPInt()) {
12159 APInt SharperMin = Min + 1;
12162 case ICmpInst::ICMP_SGE:
12163 case ICmpInst::ICMP_UGE:
12166 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12171 case ICmpInst::ICMP_SGT:
12172 case ICmpInst::ICMP_UGT:
12182 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12187 case ICmpInst::ICMP_SLE:
12188 case ICmpInst::ICMP_ULE:
12189 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12190 LHS, V, getConstant(SharperMin), CtxI))
12194 case ICmpInst::ICMP_SLT:
12195 case ICmpInst::ICMP_ULT:
12196 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12197 LHS, V, getConstant(Min), CtxI))
12211 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12215 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12218 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12225bool ScalarEvolution::splitBinaryAdd(
const SCEV *Expr,
12226 const SCEV *&L,
const SCEV *&R,
12235std::optional<APInt>
12242 APInt DiffMul(BW, 1);
12245 for (
unsigned I = 0;
I < 8; ++
I) {
12254 if (LAR->getLoop() != MAR->getLoop())
12255 return std::nullopt;
12259 if (!LAR->isAffine() || !MAR->isAffine())
12260 return std::nullopt;
12262 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12263 return std::nullopt;
12265 Less = LAR->getStart();
12266 More = MAR->getStart();
12271 auto MatchConstMul =
12272 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12277 return std::nullopt;
12279 if (
auto MatchedMore = MatchConstMul(More)) {
12280 if (
auto MatchedLess = MatchConstMul(
Less)) {
12281 if (MatchedMore->second == MatchedLess->second) {
12282 More = MatchedMore->first;
12283 Less = MatchedLess->first;
12284 DiffMul *= MatchedMore->second;
12295 Diff +=
C->getAPInt() * DiffMul;
12298 Diff -=
C->getAPInt() * DiffMul;
12301 Multiplicity[S] +=
Mul;
12303 auto Decompose = [&](
const SCEV *S,
int Mul) {
12310 Decompose(More, 1);
12311 Decompose(
Less, -1);
12315 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12316 for (
const auto &[S,
Mul] : Multiplicity) {
12321 return std::nullopt;
12323 }
else if (
Mul == -1) {
12325 return std::nullopt;
12328 return std::nullopt;
12332 if (NewMore == More || NewLess ==
Less)
12333 return std::nullopt;
12339 if (!More && !
Less)
12343 if (!More || !
Less)
12344 return std::nullopt;
12348 return std::nullopt;
12351bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12375 if (!L->contains(ContextBB) || !DT.
dominates(ContextBB, L->getLoopLatch()))
12386 if (!L->contains(ContextBB) || !DT.
dominates(ContextBB, L->getLoopLatch()))
12396bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12399 const SCEV *FoundLHS,
12400 const SCEV *FoundRHS) {
12409 if (!AddRecFoundLHS)
12416 const Loop *
L = AddRecFoundLHS->getLoop();
12417 if (L != AddRecLHS->getLoop())
12456 if (!RDiff || *LDiff != *RDiff)
12459 if (LDiff->isMinValue())
12462 APInt FoundRHSLimit;
12465 FoundRHSLimit = -(*RDiff);
12477bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12478 const SCEV *
RHS,
const SCEV *FoundLHS,
12479 const SCEV *FoundRHS,
unsigned Depth) {
12480 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12484 bool Erased = PendingMerges.erase(LPhi);
12485 assert(Erased &&
"Failed to erase LPhi!");
12489 bool Erased = PendingMerges.erase(RPhi);
12490 assert(Erased &&
"Failed to erase RPhi!");
12498 if (!PendingMerges.insert(Phi).second)
12512 if (!PendingMerges.insert(Phi).second)
12518 if (!LPhi && !RPhi)
12529 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12533 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12534 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12535 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12536 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12539 if (RPhi && RPhi->getParent() == LBB) {
12546 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12547 if (!ProvedEasily(L, R))
12558 auto *RLoop = RAR->
getLoop();
12559 auto *Predecessor = RLoop->getLoopPredecessor();
12560 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12562 if (!ProvedEasily(L1, RAR->
getStart()))
12564 auto *Latch = RLoop->getLoopLatch();
12565 assert(Latch &&
"Loop with AddRec with no latch?");
12586 if (
auto *Loop = LI.getLoopFor(LBB))
12589 if (!ProvedEasily(L,
RHS))
12596bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12599 const SCEV *FoundLHS,
12600 const SCEV *FoundRHS) {
12603 if (
RHS == FoundRHS) {
12608 if (
LHS != FoundLHS)
12615 Value *Shiftee, *ShiftValue;
12617 using namespace PatternMatch;
12618 if (
match(SUFoundRHS->getValue(),
12620 auto *ShifteeS =
getSCEV(Shiftee);
12638bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12640 const SCEV *FoundLHS,
12641 const SCEV *FoundRHS,
12642 const Instruction *CtxI) {
12643 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12645 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12647 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12648 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12650 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12654template <
typename MinMaxExprType>
12656 const SCEV *Candidate) {
12661 return is_contained(MinMaxExpr->operands(), Candidate);
12674 const SCEV *LStart, *RStart, *Step;
12724bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12726 const SCEV *FoundLHS,
12727 const SCEV *FoundRHS,
12731 "LHS and RHS have different sizes?");
12734 "FoundLHS and FoundRHS have different sizes?");
12768 auto GetOpFromSExt = [&](
const SCEV *S) {
12770 return Ext->getOperand();
12777 auto *OrigLHS =
LHS;
12778 auto *OrigFoundLHS = FoundLHS;
12779 LHS = GetOpFromSExt(
LHS);
12780 FoundLHS = GetOpFromSExt(FoundLHS);
12783 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
12786 FoundRHS,
Depth + 1);
12799 if (!LHSAddExpr->hasNoSignedWrap())
12802 auto *LL = LHSAddExpr->getOperand(0);
12803 auto *LR = LHSAddExpr->getOperand(1);
12807 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
12808 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
12813 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
12819 using namespace llvm::PatternMatch;
12838 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
12846 auto *DTy = Denominator->getType();
12847 auto *FRHSTy = FoundRHS->
getType();
12848 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
12867 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
12878 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
12880 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
12888 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
12921bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
12925 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
12928 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
12931bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
12934 const SCEV *FoundLHS,
12935 const SCEV *FoundRHS) {
12971 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
12977bool ScalarEvolution::isImpliedCondOperandsViaRanges(
12978 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
12979 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
12993 ConstantRange FoundLHSRange =
12997 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13004 return LHSRange.
icmp(Pred, ConstRHS);
13007bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13020 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13028 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13031bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
13043 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
13051 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
13063const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
13064 const SCEV *Stride,
13095 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13106 :
APIntOps::umax(MaxEnd, MinStart);
13113ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13114 const Loop *L,
bool IsSigned,
13115 bool ControlsOnlyExit,
bool AllowPredicates) {
13119 bool PredicatedIV =
false;
13124 auto canProveNUW = [&]() {
13127 if (!ControlsOnlyExit)
13148 Limit = Limit.
zext(OuterBitWidth);
13160 Type *Ty = ZExt->getType();
13171 if (!
IV && AllowPredicates) {
13176 PredicatedIV =
true;
13180 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13194 bool NoWrap = ControlsOnlyExit &&
IV->getNoWrapFlags(WrapType);
13197 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13202 if (!PositiveStride) {
13254 auto wouldZeroStrideBeUB = [&]() {
13266 if (!wouldZeroStrideBeUB()) {
13270 }
else if (!NoWrap) {
13273 if (canIVOverflowOnLT(
RHS, Stride, IsSigned))
13286 const SCEV *
Start =
IV->getStart();
13292 const SCEV *OrigStart =
Start;
13293 const SCEV *OrigRHS =
RHS;
13294 if (
Start->getType()->isPointerTy()) {
13305 const SCEV *End =
nullptr, *BECount =
nullptr,
13306 *BECountIfBackedgeTaken =
nullptr;
13309 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13310 RHSAddRec->getNoWrapFlags()) {
13323 const SCEV *RHSStart = RHSAddRec->getStart();
13324 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13336 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13345 BECountIfBackedgeTaken =
13350 if (BECount ==
nullptr) {
13355 const SCEV *MaxBECount = computeMaxBECountForLT(
13358 MaxBECount,
false , Predicates);
13365 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13392 const SCEV *Numerator =
13398 auto canProveRHSGreaterThanEqualStart = [&]() {
13417 auto *StartMinusOne =
13424 if (canProveRHSGreaterThanEqualStart()) {
13439 BECountIfBackedgeTaken =
13455 bool MayAddOverflow = [&] {
13501 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13515 if (!MayAddOverflow) {
13527 const SCEV *ConstantMaxBECount;
13528 bool MaxOrZero =
false;
13530 ConstantMaxBECount = BECount;
13531 }
else if (BECountIfBackedgeTaken &&
13536 ConstantMaxBECount = BECountIfBackedgeTaken;
13539 ConstantMaxBECount = computeMaxBECountForLT(
13547 const SCEV *SymbolicMaxBECount =
13549 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13553ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13554 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13555 bool ControlsOnlyExit,
bool AllowPredicates) {
13562 if (!
IV && AllowPredicates)
13569 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13573 bool NoWrap = ControlsOnlyExit &&
IV->getNoWrapFlags(WrapType);
13586 if (!Stride->
isOne() && !NoWrap)
13587 if (canIVOverflowOnGT(
RHS, Stride, IsSigned))
13590 const SCEV *
Start =
IV->getStart();
13591 const SCEV *End =
RHS;
13602 if (
Start->getType()->isPointerTy()) {
13637 const SCEV *ConstantMaxBECount =
13644 ConstantMaxBECount = BECount;
13645 const SCEV *SymbolicMaxBECount =
13648 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13654 if (
Range.isFullSet())
13659 if (!SC->getValue()->isZero()) {
13665 return ShiftedAddRec->getNumIterationsInRange(
13666 Range.subtract(SC->getAPInt()), SE);
13697 APInt ExitVal = (End +
A).udiv(
A);
13710 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13711 "Linear scev computation is off in a bad way!");
13742 assert(!
Last->isZero() &&
"Recurrency with zero step?");
13767 Ty = Store->getValueOperand()->getType();
13769 Ty = Load->getType();
13782 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13784 SE->ConstantEvolutionLoopExitValue.erase(PN);
13785 SE->eraseValueFromMap(getValPtr());
13789void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
13790 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13800 : CallbackVH(
V), SE(se) {}
13809 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
13811 LoopDispositions(64), BlockDispositions(64) {
13823 F.getParent(), Intrinsic::experimental_guard);
13824 HasGuards = GuardDecl && !GuardDecl->use_empty();
13828 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
13829 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
13830 ValueExprMap(
std::
move(Arg.ValueExprMap)),
13831 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
13832 PendingPhiRanges(
std::
move(Arg.PendingPhiRanges)),
13833 PendingMerges(
std::
move(Arg.PendingMerges)),
13834 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
13835 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
13836 PredicatedBackedgeTakenCounts(
13837 std::
move(Arg.PredicatedBackedgeTakenCounts)),
13838 BECountUsers(
std::
move(Arg.BECountUsers)),
13839 ConstantEvolutionLoopExitValue(
13840 std::
move(Arg.ConstantEvolutionLoopExitValue)),
13841 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
13842 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
13843 LoopDispositions(
std::
move(Arg.LoopDispositions)),
13844 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
13845 BlockDispositions(
std::
move(Arg.BlockDispositions)),
13846 SCEVUsers(
std::
move(Arg.SCEVUsers)),
13847 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
13848 SignedRanges(
std::
move(Arg.SignedRanges)),
13849 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
13850 UniquePreds(
std::
move(Arg.UniquePreds)),
13851 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
13852 LoopUsers(
std::
move(Arg.LoopUsers)),
13853 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
13854 FirstUnknown(Arg.FirstUnknown) {
13855 Arg.FirstUnknown =
nullptr;
13864 Tmp->~SCEVUnknown();
13866 FirstUnknown =
nullptr;
13868 ExprValueMap.clear();
13869 ValueExprMap.clear();
13871 BackedgeTakenCounts.clear();
13872 PredicatedBackedgeTakenCounts.clear();
13874 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
13875 assert(PendingPhiRanges.empty() &&
"getRangeRef garbage");
13876 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
13877 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
13878 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
13900 L->getHeader()->printAsOperand(OS,
false);
13904 L->getExitingBlocks(ExitingBlocks);
13905 if (ExitingBlocks.
size() != 1)
13906 OS <<
"<multiple exits> ";
13910 OS <<
"backedge-taken count is ";
13913 OS <<
"Unpredictable backedge-taken count.";
13916 if (ExitingBlocks.
size() > 1)
13917 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
13918 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
13926 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
13929 OS <<
"\n Predicates:\n";
13930 for (
const auto *
P : Predicates)
13938 L->getHeader()->printAsOperand(OS,
false);
13943 OS <<
"constant max backedge-taken count is ";
13946 OS <<
", actual taken count either this or zero.";
13948 OS <<
"Unpredictable constant max backedge-taken count. ";
13953 L->getHeader()->printAsOperand(OS,
false);
13958 OS <<
"symbolic max backedge-taken count is ";
13961 OS <<
", actual taken count either this or zero.";
13963 OS <<
"Unpredictable symbolic max backedge-taken count. ";
13967 if (ExitingBlocks.
size() > 1)
13968 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
13969 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
13979 OS <<
"\n predicated symbolic max exit count for "
13980 << ExitingBlock->
getName() <<
": ";
13982 OS <<
"\n Predicates:\n";
13983 for (
const auto *
P : Predicates)
13993 assert(!Preds.
empty() &&
"Different predicated BTC, but no predicates");
13995 L->getHeader()->printAsOperand(OS,
false);
13998 OS <<
"Predicated backedge-taken count is ";
14001 OS <<
"Unpredictable predicated backedge-taken count.";
14003 OS <<
" Predicates:\n";
14004 for (
const auto *
P : Preds)
14009 auto *PredConstantMax =
14011 if (PredConstantMax != ConstantBTC) {
14013 "different predicated constant max BTC but no predicates");
14015 L->getHeader()->printAsOperand(OS,
false);
14018 OS <<
"Predicated constant max backedge-taken count is ";
14021 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14023 OS <<
" Predicates:\n";
14024 for (
const auto *
P : Preds)
14029 auto *PredSymbolicMax =
14031 if (SymbolicBTC != PredSymbolicMax) {
14033 "Different predicated symbolic max BTC, but no predicates");
14035 L->getHeader()->printAsOperand(OS,
false);
14038 OS <<
"Predicated symbolic max backedge-taken count is ";
14041 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14043 OS <<
" Predicates:\n";
14044 for (
const auto *
P : Preds)
14050 L->getHeader()->printAsOperand(OS,
false);
14074 OS <<
"Computable";
14084 OS <<
"DoesNotDominate";
14090 OS <<
"ProperlyDominates";
14107 OS <<
"Classifying expressions for: ";
14108 F.printAsOperand(OS,
false);
14123 const Loop *L = LI.getLoopFor(
I.getParent());
14138 OS <<
"\t\t" "Exits: ";
14141 OS <<
"<<Unknown>>";
14147 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14149 Iter->getHeader()->printAsOperand(OS,
false);
14157 InnerL->getHeader()->printAsOperand(OS,
false);
14168 OS <<
"Determining loop execution counts for: ";
14169 F.printAsOperand(OS,
false);
14177 auto &Values = LoopDispositions[S];
14178 for (
auto &V : Values) {
14179 if (V.getPointer() == L)
14184 auto &Values2 = LoopDispositions[S];
14186 if (V.getPointer() == L) {
14195ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14214 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14215 " dominate the contained loop's header?");
14243 bool HasVarying =
false;
14277 auto &Values = BlockDispositions[S];
14278 for (
auto &V : Values) {
14279 if (V.getPointer() == BB)
14284 auto &Values2 = BlockDispositions[S];
14286 if (V.getPointer() == BB) {
14295ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14325 bool Proper =
true;
14336 if (Instruction *
I =
14338 if (
I->getParent() == BB)
14340 if (DT.properlyDominates(
I->getParent(), BB))
14363void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14366 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14367 auto It = BECounts.find(L);
14368 if (It != BECounts.end()) {
14369 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14370 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14372 auto UserIt = BECountUsers.find(S);
14373 assert(UserIt != BECountUsers.end());
14378 BECounts.erase(It);
14386 while (!Worklist.
empty()) {
14388 auto Users = SCEVUsers.find(Curr);
14389 if (
Users != SCEVUsers.end())
14390 for (
const auto *User :
Users->second)
14391 if (ToForget.
insert(User).second)
14395 for (
const auto *S : ToForget)
14396 forgetMemoizedResultsImpl(S);
14398 for (
auto I = PredicatedSCEVRewrites.begin();
14399 I != PredicatedSCEVRewrites.end();) {
14400 std::pair<const SCEV *, const Loop *>
Entry =
I->first;
14401 if (ToForget.count(
Entry.first))
14402 PredicatedSCEVRewrites.erase(
I++);
14408void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14409 LoopDispositions.erase(S);
14410 BlockDispositions.erase(S);
14411 UnsignedRanges.erase(S);
14412 SignedRanges.erase(S);
14413 HasRecMap.erase(S);
14414 ConstantMultipleCache.erase(S);
14417 UnsignedWrapViaInductionTried.erase(AR);
14418 SignedWrapViaInductionTried.erase(AR);
14421 auto ExprIt = ExprValueMap.find(S);
14422 if (ExprIt != ExprValueMap.end()) {
14423 for (
Value *V : ExprIt->second) {
14424 auto ValueIt = ValueExprMap.find_as(V);
14425 if (ValueIt != ValueExprMap.end())
14426 ValueExprMap.erase(ValueIt);
14428 ExprValueMap.erase(ExprIt);
14431 auto ScopeIt = ValuesAtScopes.find(S);
14432 if (ScopeIt != ValuesAtScopes.end()) {
14433 for (
const auto &Pair : ScopeIt->second)
14436 std::make_pair(Pair.first, S));
14437 ValuesAtScopes.erase(ScopeIt);
14440 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14441 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14442 for (
const auto &Pair : ScopeUserIt->second)
14443 llvm::erase(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
14444 ValuesAtScopesUsers.erase(ScopeUserIt);
14447 auto BEUsersIt = BECountUsers.find(S);
14448 if (BEUsersIt != BECountUsers.end()) {
14450 auto Copy = BEUsersIt->second;
14451 for (
const auto &Pair : Copy)
14452 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14453 BECountUsers.erase(BEUsersIt);
14456 auto FoldUser = FoldCacheUser.find(S);
14457 if (FoldUser != FoldCacheUser.end())
14458 for (
auto &KV : FoldUser->second)
14459 FoldCache.erase(KV);
14460 FoldCacheUser.erase(S);
14464ScalarEvolution::getUsedLoops(
const SCEV *S,
14466 struct FindUsedLoops {
14467 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14468 : LoopsUsed(LoopsUsed) {}
14469 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14470 bool follow(
const SCEV *S) {
14476 bool isDone()
const {
return false; }
14479 FindUsedLoops
F(LoopsUsed);
14480 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14483void ScalarEvolution::getReachableBlocks(
14486 Worklist.
push_back(&F.getEntryBlock());
14487 while (!Worklist.
empty()) {
14489 if (!Reachable.
insert(BB).second)
14497 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14504 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14508 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14543 SCEVMapper SCM(SE2);
14545 SE2.getReachableBlocks(ReachableBlocks, F);
14547 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14565 while (!LoopStack.
empty()) {
14571 if (!ReachableBlocks.
contains(L->getHeader()))
14576 auto It = BackedgeTakenCounts.find(L);
14577 if (It == BackedgeTakenCounts.end())
14581 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14601 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14602 if (Delta && !Delta->
isZero()) {
14603 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14604 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14605 dbgs() <<
"New: " << *NewBECount <<
"\n";
14606 dbgs() <<
"Delta: " << *Delta <<
"\n";
14614 while (!Worklist.
empty()) {
14616 if (ValidLoops.
insert(L).second)
14617 Worklist.
append(L->begin(), L->end());
14619 for (
const auto &KV : ValueExprMap) {
14624 "AddRec references invalid loop");
14629 auto It = ExprValueMap.find(KV.second);
14630 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14631 dbgs() <<
"Value " << *KV.first
14632 <<
" is in ValueExprMap but not in ExprValueMap\n";
14637 if (!ReachableBlocks.
contains(
I->getParent()))
14639 const SCEV *OldSCEV = SCM.visit(KV.second);
14641 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14642 if (Delta && !Delta->
isZero()) {
14643 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14644 <<
"Old: " << *OldSCEV <<
"\n"
14645 <<
"New: " << *NewSCEV <<
"\n"
14646 <<
"Delta: " << *Delta <<
"\n";
14652 for (
const auto &KV : ExprValueMap) {
14653 for (
Value *V : KV.second) {
14654 const SCEV *S = ValueExprMap.lookup(V);
14656 dbgs() <<
"Value " << *V
14657 <<
" is in ExprValueMap but not in ValueExprMap\n";
14660 if (S != KV.first) {
14661 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14662 << *KV.first <<
"\n";
14669 for (
const auto &S : UniqueSCEVs) {
14674 auto It = SCEVUsers.find(
Op);
14675 if (It != SCEVUsers.end() && It->second.count(&S))
14677 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14678 <<
" is not being tracked!\n";
14684 for (
const auto &ValueAndVec : ValuesAtScopes) {
14686 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14687 const Loop *L = LoopAndValueAtScope.first;
14688 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
14690 auto It = ValuesAtScopesUsers.find(ValueAtScope);
14691 if (It != ValuesAtScopesUsers.end() &&
14694 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14695 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14701 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14702 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14703 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14704 const Loop *L = LoopAndValue.first;
14705 const SCEV *
Value = LoopAndValue.second;
14707 auto It = ValuesAtScopes.find(
Value);
14708 if (It != ValuesAtScopes.end() &&
14709 is_contained(It->second, std::make_pair(L, ValueAtScope)))
14711 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14712 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14718 auto VerifyBECountUsers = [&](
bool Predicated) {
14720 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14721 for (
const auto &LoopAndBEInfo : BECounts) {
14722 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14723 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14725 auto UserIt = BECountUsers.find(S);
14726 if (UserIt != BECountUsers.end() &&
14727 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14729 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14730 <<
" missing from BECountUsers\n";
14737 VerifyBECountUsers(
false);
14738 VerifyBECountUsers(
true);
14741 for (
auto &[S, Values] : LoopDispositions) {
14742 for (
auto [
Loop, CachedDisposition] : Values) {
14744 if (CachedDisposition != RecomputedDisposition) {
14745 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
14746 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
14747 << RecomputedDisposition <<
"\n";
14754 for (
auto &[S, Values] : BlockDispositions) {
14755 for (
auto [BB, CachedDisposition] : Values) {
14757 if (CachedDisposition != RecomputedDisposition) {
14758 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
14759 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
14760 <<
", actual " << RecomputedDisposition <<
"\n";
14767 for (
auto [
FoldID, Expr] : FoldCache) {
14768 auto I = FoldCacheUser.find(Expr);
14769 if (
I == FoldCacheUser.end()) {
14770 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
14775 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
14779 for (
auto [Expr, IDs] : FoldCacheUser) {
14780 for (
auto &
FoldID : IDs) {
14783 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
14788 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
14789 <<
" != " << *Expr <<
"!\n";
14800 for (
auto [S, Multiple] : ConstantMultipleCache) {
14802 if ((Multiple != 0 && RecomputedMultiple != 0 &&
14803 Multiple.
urem(RecomputedMultiple) != 0 &&
14804 RecomputedMultiple.
urem(Multiple) != 0)) {
14805 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
14806 << *S <<
" : Computed " << RecomputedMultiple
14807 <<
" but cache contains " << Multiple <<
"!\n";
14815 FunctionAnalysisManager::Invalidator &Inv) {
14847 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
14848 <<
F.getName() <<
"':\n";
14854 "Scalar Evolution Analysis",
false,
true)
14903 const SCEV *LHS,
const SCEV *RHS) {
14905 assert(LHS->getType() == RHS->getType() &&
14906 "Type mismatch between LHS and RHS");
14909 ID.AddInteger(Pred);
14910 ID.AddPointer(LHS);
14911 ID.AddPointer(RHS);
14912 void *IP =
nullptr;
14913 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
14917 UniquePreds.InsertNode(Eq, IP);
14928 ID.AddInteger(AddedFlags);
14929 void *IP =
nullptr;
14930 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
14932 auto *OF =
new (SCEVAllocator)
14934 UniquePreds.InsertNode(OF, IP);
14954 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
14955 return Rewriter.visit(S);
14961 for (
const auto *Pred : U->getPredicates())
14963 if (IPred->getLHS() == Expr &&
14965 return IPred->getRHS();
14967 if (IPred->getLHS() == Expr &&
14968 IPred->getPredicate() == ICmpInst::ICMP_EQ)
14969 return IPred->getRHS();
14972 return convertToAddRecWithPreds(Expr);
14975 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
14991 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15008 explicit SCEVPredicateRewriter(
15009 const Loop *L, ScalarEvolution &SE,
15010 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15011 const SCEVPredicate *Pred)
15012 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15014 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15017 return Pred && Pred->
implies(
P, SE);
15023 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15026 return addOverflowAssumption(
A);
15035 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15039 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15041 if (!PredicatedRewrite)
15043 for (
const auto *
P : PredicatedRewrite->second){
15046 if (L != WP->getExpr()->getLoop())
15049 if (!addOverflowAssumption(
P))
15052 return PredicatedRewrite->first;
15055 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15056 const SCEVPredicate *Pred;
15065 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15072 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15092 if (!Step->
isOne())
15117 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15118 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15131 return Op->LHS == LHS &&
Op->RHS == RHS;
15138 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15140 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15165 const SCEV *Start = AR->getStart();
15166 const SCEV *OpStart =
Op->AR->getStart();
15171 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15174 const SCEV *Step = AR->getStepRecurrence(SE);
15175 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15228 if (Step->getValue()->getValue().isNonNegative())
15232 return ImpliedFlags;
15239 for (
const auto *
P : Preds)
15252 return this->implies(I, SE);
15260 for (
const auto *Pred : Preds)
15261 Pred->print(OS,
Depth);
15266 for (
const auto *Pred : Set->Preds)
15274 bool CheckImplies = Preds.
size() < 16;
15277 if (CheckImplies &&
implies(
N, SE))
15283 for (
auto *
P : Preds) {
15284 if (CheckImplies &&
N->implies(
P, SE))
15288 Preds = std::move(PrunedPreds);
15289 Preds.push_back(
N);
15296 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15301 for (
const auto *
Op :
Ops)
15306 SCEVUsers[
Op].insert(
User);
15310 const SCEV *Expr = SE.getSCEV(V);
15315 RewriteEntry &Entry = RewriteMap[Expr];
15318 if (Entry.second && Generation == Entry.first)
15319 return Entry.second;
15324 Expr = Entry.second;
15326 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15327 Entry = {Generation, NewSCEV};
15333 if (!BackedgeCount) {
15335 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15336 for (
const auto *
P : Preds)
15339 return BackedgeCount;
15343 if (!SymbolicMaxBackedgeCount) {
15345 SymbolicMaxBackedgeCount =
15346 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15347 for (
const auto *
P : Preds)
15350 return SymbolicMaxBackedgeCount;
15354 if (!SmallConstantMaxTripCount) {
15356 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15357 for (
const auto *
P : Preds)
15360 return *SmallConstantMaxTripCount;
15364 if (Preds->implies(&Pred, SE))
15369 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15370 updateGeneration();
15377void PredicatedScalarEvolution::updateGeneration() {
15379 if (++Generation == 0) {
15380 for (
auto &
II : RewriteMap) {
15381 const SCEV *Rewritten =
II.second.second;
15398 auto II = FlagsMap.insert({V, Flags});
15411 auto II = FlagsMap.find(V);
15413 if (
II != FlagsMap.end())
15422 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15427 for (
const auto *
P : NewPreds)
15430 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15436 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15439 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {
15440 for (
auto I :
Init.FlagsMap)
15441 FlagsMap.insert(
I);
15446 for (
auto *BB : L.getBlocks())
15447 for (
auto &
I : *BB) {
15448 if (!SE.isSCEVable(
I.getType()))
15451 auto *Expr = SE.getSCEV(&
I);
15452 auto II = RewriteMap.find(Expr);
15454 if (
II == RewriteMap.end())
15458 if (
II->second.second == Expr)
15463 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15471 LoopGuards Guards(SE);
15479void ScalarEvolution::LoopGuards::collectFromPHI(
15487 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15488 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15502 auto &RewriteMap =
G->second.RewriteMap;
15503 if (RewriteMap.empty())
15505 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15506 if (S == RewriteMap.end())
15512 return {C0, SM->getSCEVType()};
15515 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15516 MinMaxPattern
P2) -> MinMaxPattern {
15517 auto [C1,
T1] =
P1;
15518 auto [C2, T2] =
P2;
15519 if (!C1 || !C2 ||
T1 != T2)
15523 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15525 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15527 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15529 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15534 auto P = GetMinMaxConst(0);
15535 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15538 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15541 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15544 Guards.RewriteMap.insert({
LHS,
RHS});
15552 const APInt &DivisorVal,
15554 const APInt *ExprVal;
15567 const APInt &DivisorVal,
15569 const APInt *ExprVal;
15577 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15591 const SCEV *URemRHS =
nullptr;
15595 const SCEV *Multiple =
15597 DivInfo[URemLHS] = Multiple;
15599 Multiples[URemLHS] =
C->getAPInt();
15619 auto IsMinMaxSCEVWithNonNegativeConstant =
15623 if (
MinMax->getNumOperands() != 2)
15626 if (
C->getAPInt().isNegative())
15628 SCTy =
MinMax->getSCEVType();
15637 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15639 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15644 auto *DivisibleExpr =
15652void ScalarEvolution::LoopGuards::collectFromBlock(
15654 const BasicBlock *
Block,
const BasicBlock *Pred,
15662 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15673 &ExprsToRewrite]() {
15674 const SCEVConstant *C1;
15687 if (ExactRegion.isWrappedSet() || ExactRegion.isFullSet())
15689 auto [
I,
Inserted] = RewriteMap.try_emplace(LHSUnknown);
15690 const SCEV *RewrittenLHS =
Inserted ? LHSUnknown :
I->second;
15698 if (MatchRangeCheckIdiom())
15715 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15717 if (From == FromRewritten)
15719 RewriteMap[From] = To;
15725 auto GetMaybeRewritten = [&](
const SCEV *S) {
15726 return RewriteMap.lookup_or(S, S);
15729 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15731 const APInt &DividesBy =
15746 switch (Predicate) {
15775 SmallPtrSet<const SCEV *, 16> Visited;
15777 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
15781 while (!Worklist.
empty()) {
15785 if (!Visited.
insert(From).second)
15787 const SCEV *FromRewritten = GetMaybeRewritten(From);
15788 const SCEV *To =
nullptr;
15790 switch (Predicate) {
15795 EnqueueOperands(
UMax);
15801 EnqueueOperands(
SMax);
15807 EnqueueOperands(
UMin);
15813 EnqueueOperands(
SMin);
15821 const SCEV *OneAlignedUp =
15823 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
15835 const SCEVConstant *
C;
15844 Guards.NotEqual.insert({
LHS,
RHS});
15853 AddRewrite(From, FromRewritten, To);
15870 SE.F.
getParent(), Intrinsic::experimental_guard);
15872 for (
const auto *GU : GuardDecl->users())
15874 if (Guard->getFunction() ==
Block->getParent() &&
15883 unsigned NumCollectedConditions = 0;
15885 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
15887 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
15889 const BranchInst *LoopEntryPredicate =
15896 NumCollectedConditions++;
15900 if (
Depth > 0 && NumCollectedConditions == 2)
15908 if (Pair.second->hasNPredecessorsOrMore(2) &&
15910 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
15911 for (
auto &Phi : Pair.second->phis())
15922 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
15923 SmallVector<Value *, 8> Worklist;
15924 SmallPtrSet<Value *, 8> Visited;
15926 while (!Worklist.
empty()) {
15933 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
15957 DenseMap<const SCEV *, APInt> Multiples;
15959 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
15966 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
15967 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
15971 for (
const auto &[K, Divisor] : Multiples) {
15972 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
15973 Guards.RewriteMap[
K] =
15975 Guards.
rewrite(K), Divisor, SE),
15984 Guards.PreserveNUW =
true;
15985 Guards.PreserveNSW =
true;
15986 for (
const SCEV *Expr : ExprsToRewrite) {
15987 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
15988 Guards.PreserveNUW &=
15990 Guards.PreserveNSW &=
15997 if (ExprsToRewrite.size() > 1) {
15998 for (
const SCEV *Expr : ExprsToRewrite) {
15999 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16000 Guards.RewriteMap.erase(Expr);
16001 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16010 class SCEVLoopGuardRewriter
16021 NotEqual(Guards.NotEqual) {
16022 if (Guards.PreserveNUW)
16024 if (Guards.PreserveNSW)
16031 return Map.lookup_or(Expr, Expr);
16035 if (
const SCEV *S = Map.lookup(Expr))
16042 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16043 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16044 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16046 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16047 if (
const SCEV *S = Map.lookup(NarrowExt))
16048 return SE.getZeroExtendExpr(S, Ty);
16049 Bitwidth = Bitwidth / 2;
16057 if (
const SCEV *S = Map.lookup(Expr))
16064 if (
const SCEV *S = Map.lookup(Expr))
16070 if (
const SCEV *S = Map.lookup(Expr))
16078 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16079 const SCEV *LHS, *RHS;
16083 if (NotEqual.contains({LHS, RHS})) {
16085 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16086 return SE.getUMaxExpr(OneAlignedUp, S);
16093 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16104 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16105 return SE.getAddExpr(
16108 if (
const SCEV *S = Map.lookup(
Add))
16109 return SE.getAddExpr(Expr->
getOperand(0), S);
16121 : SE.getAddExpr(Operands,
16137 : SE.getMulExpr(Operands,
16143 if (RewriteMap.empty() && NotEqual.empty())
16146 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16147 return Rewriter.visit(Expr);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Expand Atomic instructions
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
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
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
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)
const SmallVectorImpl< MachineOperand > & Cond
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
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 const SCEV * getNextSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
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 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< unsigned > MaxLoopGuardCollectionDepth("scalar-evolution-max-loop-guard-collection-depth", cl::Hidden, cl::desc("Maximum depth for recursive loop guard collection"), cl::init(1))
static cl::opt< bool > VerifyIR("scev-verify-ir", cl::Hidden, cl::desc("Verify IR correctness when making sensitive SCEV queries (slow)"), cl::init(false))
static bool BrPHIToSelect(DominatorTree &DT, BranchInst *BI, PHINode *Merge, Value *&C, Value *&LHS, Value *&RHS)
static const SCEV * getPreStartForExtend(const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE, unsigned Depth)
static std::optional< APInt > MinOptional(std::optional< APInt > X, std::optional< APInt > Y)
Helper function to compare optional APInts: (a) if X and Y both exist, return min(X,...
static cl::opt< unsigned > MulOpsInlineThreshold("scev-mulops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining multiplication operands into a SCEV"), cl::init(32))
static void GroupByComplexity(SmallVectorImpl< const SCEV * > &Ops, LoopInfo *LI, DominatorTree &DT)
Given a list of SCEV objects, order them by their complexity, and group objects of the same complexit...
static 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 bool isDivisibilityGuard(const SCEV *LHS, const SCEV *RHS, ScalarEvolution &SE)
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 const SCEV * SolveLinEquationWithOverflow(const APInt &A, const SCEV *B, SmallVectorImpl< const SCEVPredicate * > *Predicates, ScalarEvolution &SE, const Loop *L)
Finds the minimum unsigned root of the following equation:
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 bool IsKnownPredicateViaAddRecStart(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
static bool collectDivisibilityInformation(ICmpInst::Predicate Predicate, const SCEV *LHS, const SCEV *RHS, DenseMap< const SCEV *, const SCEV * > &DivInfo, DenseMap< const SCEV *, APInt > &Multiples, ScalarEvolution &SE)
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 bool isKnownPredicateExtendIdiom(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
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 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 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 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 SCEV::NoWrapFlags StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, ArrayRef< const SCEV * > Ops, SCEV::NoWrapFlags Flags)
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 * getPreviousSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
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 const SCEV * applyDivisibilityOnMinMaxExpr(const SCEV *MinMaxExpr, APInt Divisor, ScalarEvolution &SE)
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 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 std::optional< int > CompareSCEVComplexity(const LoopInfo *const LI, const SCEV *LHS, const SCEV *RHS, DominatorTree &DT, unsigned Depth=0)
static bool CollectAddOperandsWithScales(SmallDenseMap< const SCEV *, APInt, 16 > &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 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)
static bool IsKnownPredicateViaMinOrMax(ScalarEvolution &SE, CmpPredicate 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?
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
static bool InBlock(const Value *V, const BasicBlock *BB)
Provides some synthesis utilities to produce sequences of values.
This file defines the SmallPtrSet 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 TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
static SymbolRef::Type getType(const Symbol *Sym)
LocallyHashedType DenseMapInfo< LocallyHashedType >::Empty
static std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
static std::optional< bool > isImpliedCondOperands(CmpInst::Predicate Pred, const Value *ALHS, const Value *ARHS, const Value *BLHS, const Value *BRHS)
Return true if "icmp Pred BLHS BRHS" is true whenever "icmp PredALHS ARHS" is true.
Virtual Register Rewriter
static const uint32_t IV[8]
SCEVCastSinkingRewriter(ScalarEvolution &SE, Type *TargetTy, ConversionFn CreatePtrCast)
static const SCEV * rewrite(const SCEV *Scev, ScalarEvolution &SE, Type *TargetTy, ConversionFn CreatePtrCast)
const SCEV * visitUnknown(const SCEVUnknown *Expr)
const SCEV * visitMulExpr(const SCEVMulExpr *Expr)
const SCEV * visitAddExpr(const SCEVAddExpr *Expr)
const SCEV * visit(const SCEV *S)
Class for arbitrary precision integers.
LLVM_ABI APInt umul_ov(const APInt &RHS, bool &Overflow) const
LLVM_ABI 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.
LLVM_ABI APInt getHiBits(unsigned numBits) const
Compute an APInt containing numBits highbits from this APInt.
unsigned getActiveBits() const
Compute the number of active bits in the value.
LLVM_ABI 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 sgt(const APInt &RHS) const
Signed greater than comparison.
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
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.
LLVM_ABI 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.
bool isNonPositive() const
Determine if this APInt Value is non-positive (<= 0).
unsigned countTrailingZeros() const
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
unsigned logBase2() const
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
LLVM_ABI APInt multiplicativeInverse() const
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
LLVM_ABI APInt sext(unsigned width) const
Sign extend to a new width.
APInt shl(unsigned shiftAmt) const
Left-shift function.
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
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 <aparticular IR unit>" (e....
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),...
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< WeakVH > assumptions()
Access the list of assumption handles currently tracked for this function.
LLVM_ABI bool isSingleEdge() const
Check if this is the only edge between Start and End.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
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...
LLVM_ABI unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
LLVM_ABI 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
This class represents a function call, abstracting a target machine's calling convention.
virtual void deleted()
Callback for Value 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 getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
static LLVM_ABI std::optional< CmpPredicate > getMatching(CmpPredicate A, CmpPredicate B)
Compares two CmpPredicates taking samesign into account and returns the canonicalized CmpPredicate if...
LLVM_ABI CmpInst::Predicate getPreferredSignedPredicate() const
Attempts to return a signed CmpInst::Predicate from the CmpPredicate.
CmpInst::Predicate dropSameSign() const
Drops samesign information.
static LLVM_ABI Constant * getNot(Constant *C)
static LLVM_ABI Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static LLVM_ABI Constant * getPtrToAddr(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 LLVM_ABI Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
static LLVM_ABI Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
This is the shared class of boolean and integer constants.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI 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 LLVM_ABI ConstantInt * getBool(LLVMContext &Context, bool V)
This class represents a range of values.
LLVM_ABI ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
LLVM_ABI 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...
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI ConstantRange urem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned remainder operation of...
LLVM_ABI bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
LLVM_ABI bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other?
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI ConstantRange zeroExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
LLVM_ABI bool isSignWrappedSet() const
Return true if this set wraps around the signed domain.
LLVM_ABI APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
LLVM_ABI bool isWrappedSet() const
Return true if this set wraps around the unsigned domain.
LLVM_ABI void print(raw_ostream &OS) const
Print out the bounds to a stream.
LLVM_ABI ConstantRange truncate(uint32_t BitWidth, unsigned NoWrapKind=0) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
LLVM_ABI 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.
LLVM_ABI ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
static LLVM_ABI 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...
LLVM_ABI bool contains(const APInt &Val) const
Return true if the specified value is in the set.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
LLVM_ABI ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
LLVM_ABI 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 LLVM_ABI 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)...
LLVM_ABI 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.
LLVM_ABI ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
LLVM_ABI ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
static LLVM_ABI 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.
A parsed version of the target data layout string in and methods for querying it.
LLVM_ABI const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
LLVM_ABI 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.
LLVM_ABI unsigned getIndexTypeSizeInBits(Type *Ty) const
The size in bits of the index used in GEP calculation for this type.
LLVM_ABI 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)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
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.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
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.
Represents flags for the getelementptr instruction/expression.
bool hasNoUnsignedSignedWrap() const
bool hasNoUnsignedWrap() const
static GEPNoWrapFlags none()
static LLVM_ABI 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.
CmpPredicate getCmpPredicate() const
static bool isGE(Predicate P)
Return true if the predicate is SGE or UGE.
CmpPredicate getSwappedCmpPredicate() const
static LLVM_ABI 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.
CmpPredicate getInverseCmpPredicate() const
Predicate getNonStrictCmpPredicate() const
For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.
static bool isGT(Predicate P)
Return true if the predicate is SGT or UGT.
Predicate getFlippedSignednessPredicate() const
For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->EQ.
static CmpPredicate getInverseCmpPredicate(CmpPredicate Pred)
static bool isEquality(Predicate P)
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.
LLVM_ABI bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
LLVM_ABI bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
LLVM_ABI bool isIdenticalToWhenDefined(const Instruction *I, bool IntersectAttrs=false) const LLVM_READONLY
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...
Class to represent integer types.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
A helper class to return the specified delimiter string after the first invocation of operator String...
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.
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
op_range incoming_values()
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.
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
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 LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
LLVM_ABI void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
LLVM_ABI const SCEVPredicate & getPredicate() const
LLVM_ABI const SCEV * getPredicatedSCEV(const SCEV *Expr)
Returns the rewritten SCEV for Expr in the context of the current SCEV predicate.
LLVM_ABI bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've proved that V doesn't wrap by means of a SCEV predicate.
LLVM_ABI void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Proves that V doesn't overflow by adding SCEV predicate.
LLVM_ABI void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
LLVM_ABI bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds.
LLVM_ABI PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
LLVM_ABI const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
LLVM_ABI unsigned getSmallConstantMaxTripCount()
Returns the upper bound of the loop trip count as a normal unsigned value, or 0 if the trip count is ...
LLVM_ABI const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSymbolicMaxBackedgeTakenCount()
Get the (predicated) symbolic max backedge count for the analyzed loop.
LLVM_ABI 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.
friend class ScalarEvolution
const SCEV * getStart() const
LLVM_ABI 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...
LLVM_ABI 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.
LLVM_ABI 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
LLVM_ABI 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.
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Implementation of the SCEVPredicate interface.
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.
LLVM_ABI 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.
SCEVPredicate(const SCEVPredicate &)=default
virtual bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const =0
Returns true if this predicate implies N.
This class represents a cast from a pointer to a pointer-sized integer value, without capturing the p...
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 * visit(const SCEV *S)
const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)
const SCEV * visitSMinExpr(const SCEVSMinExpr *Expr)
SCEVRewriteVisitor(ScalarEvolution &SE)
const SCEV * visitUMinExpr(const SCEVUMinExpr *Expr)
This class represents a signed minimum selection.
This node is the base class for sequential/in-order min/max selections.
static SCEVTypes getEquivalentNonSequentialSCEVType(SCEVTypes Ty)
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.
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 minimum selection.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
void print(raw_ostream &OS, unsigned Depth) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Returns true if this predicate implies N.
SCEVUnionPredicate(ArrayRef< const SCEVPredicate * > Preds, ScalarEvolution &SE)
Union predicates don't get cached so create a dummy set ID for it.
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
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, ScalarEvolution &SE) 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.
LLVM_ABI ArrayRef< const SCEV * > operands() const
Return operands of this SCEV expression.
unsigned short getExpressionSize() const
LLVM_ABI bool isOne() const
Return true if the expression is a constant one.
LLVM_ABI bool isZero() const
Return true if the expression is a constant zero.
LLVM_ABI void dump() const
This method is used for debugging.
LLVM_ABI bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
LLVM_ABI bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
LLVM_ABI void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
SCEV(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, unsigned short ExpressionSize)
SCEVTypes getSCEVType() const
LLVM_ABI 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.
LLVM_ABI ScalarEvolution run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI 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...
ScalarEvolutionWrapperPass()
static LLVM_ABI 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 ...
LLVM_ABI 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.
LLVM_ABI bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
LLVM_ABI bool isKnownOnEveryIteration(CmpPredicate 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 ...
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterationsImpl(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
LLVM_ABI const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI const SCEV * getUDivCeilSCEV(const SCEV *N, const SCEV *D)
Compute ceil(N / D).
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterations(CmpPredicate 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...
LLVM_ABI Type * getWiderType(Type *Ty1, Type *Ty2) const
LLVM_ABI const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)
LLVM_ABI bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
LLVM_ABI const SCEV * getURemExpr(const SCEV *LHS, const SCEV *RHS)
Represents an unsigned remainder expression based on unsigned division.
LLVM_ABI bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
LLVM_ABI const SCEV * getPredicatedConstantMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getConstantMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
LLVM_ABI bool isLoopEntryGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
LLVM_ABI bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
LLVM_ABI const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
LLVM_ABI const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI 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...
LLVM_ABI const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags)
Update no-wrap flags of an AddRec.
LLVM_ABI 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.
LLVM_ABI 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)?
LLVM_ABI 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...
LLVM_ABI const SCEV * getZeroExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
LLVM_ABI uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
LLVM_ABI const SCEV * getConstant(ConstantInt *V)
LLVM_ABI const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
LLVM_ABI 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.
LLVM_ABI const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
LLVM_ABI const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
LLVM_ABI 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.
LLVM_ABI const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI const SCEV * getLosslessPtrToIntExpr(const SCEV *Op)
LLVM_ABI const SCEV * getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty)
LLVM_ABI const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
LLVM_ABI std::optional< bool > evaluatePredicateAt(CmpPredicate 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.
LLVM_ABI unsigned getSmallConstantMaxTripCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Returns the upper bound of the loop trip count as a normal unsigned value.
LLVM_ABI const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
LLVM_ABI bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
LLVM_ABI 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...
LLVM_ABI bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
LLVM_ABI 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.
LLVM_ABI bool SimplifyICmpOperands(CmpPredicate &Pred, const SCEV *&LHS, const SCEV *&RHS, unsigned Depth=0)
Simplify LHS and RHS in a comparison with predicate Pred.
LLVM_ABI const SCEV * getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo)
Return an expression for offsetof on the given field with type IntTy.
LLVM_ABI LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
LLVM_ABI bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
LLVM_ABI const SCEV * getSignExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
LLVM_ABI bool hasOperand(const SCEV *S, const SCEV *Op) const
Test whether the given SCEV has Op as a direct or indirect operand.
LLVM_ABI const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
LLVM_ABI const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
LLVM_ABI 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...
LLVM_ABI const SCEVPredicate * getComparePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
LLVM_ABI bool haveSameSign(const SCEV *S1, const SCEV *S2)
Return true if we know that S1 and S2 must have the same sign.
LLVM_ABI const SCEV * getNotSCEV(const SCEV *V)
Return the SCEV object corresponding to ~V.
LLVM_ABI const SCEV * getElementCount(Type *Ty, ElementCount EC, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
LLVM_ABI 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...
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
LLVM_ABI void print(raw_ostream &OS) const
LLVM_ABI const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
LLVM_ABI const SCEV * getPredicatedExitCount(const Loop *L, const BasicBlock *ExitingBlock, SmallVectorImpl< const SCEVPredicate * > *Predicates, ExitCountKind Kind=Exact)
Same as above except this uses the predicated backedge taken info and may require predicates.
static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
LLVM_ABI void forgetTopmostLoop(const Loop *L)
LLVM_ABI 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.
LLVM_ABI const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
LLVM_ABI const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
@ MonotonicallyDecreasing
@ MonotonicallyIncreasing
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantPredicate(CmpPredicate 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...
LLVM_ABI const SCEV * getStoreSizeOfExpr(Type *IntTy, Type *StoreTy)
Return an expression for the store size of StoreTy that is type IntTy.
LLVM_ABI const SCEVPredicate * getWrapPredicate(const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
LLVM_ABI bool isLoopBackedgeGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether the backedge of the loop is protected by a conditional between LHS and RHS.
LLVM_ABI const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
LLVM_ABI 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)
LLVM_ABI bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
LLVM_ABI BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB)
Return the "disposition" of the given SCEV with respect to the given block.
LLVM_ABI const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
LLVM_ABI 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...
LLVM_ABI bool loopIsFiniteByAssumption(const Loop *L)
Return true if this loop is finite by assumption.
LLVM_ABI const SCEV * getExistingSCEV(Value *V)
Return an existing SCEV for V if there is one, otherwise return nullptr.
LLVM_ABI APInt getConstantMultiple(const SCEV *S, const Instruction *CtxI=nullptr)
Returns the max constant multiple of S.
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
LLVM_ABI bool isKnownMultipleOf(const SCEV *S, uint64_t M, SmallVectorImpl< const SCEVPredicate * > &Assumptions)
Check that S is a multiple of M.
LLVM_ABI const SCEV * getAnyExtendExpr(const SCEV *Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
LLVM_ABI bool isKnownToBeAPowerOfTwo(const SCEV *S, bool OrZero=false, bool OrNegative=false)
Test if the given expression is known to be a power of 2.
LLVM_ABI 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,...
LLVM_ABI 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...
LLVM_ABI bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
LLVM_ABI 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,...
LLVM_ABI const SCEV * getCouldNotCompute()
LLVM_ABI bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
LLVM_ABI uint32_t getMinTrailingZeros(const SCEV *S, const Instruction *CtxI=nullptr)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
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.
LLVM_ABI const SCEV * getGEPExpr(GEPOperator *GEP, ArrayRef< const SCEV * > IndexExprs)
Returns an expression for a GEP.
LLVM_ABI 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...
LLVM_ABI const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI 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.
LLVM_ABI void forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
LLVM_ABI const SCEV * getVScale(Type *Ty)
LLVM_ABI 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.
LLVM_ABI bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
LLVM_ABI const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
LLVM_ABI const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
LLVM_ABI void forgetAllLoops()
LLVM_ABI 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.
LLVM_ABI const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
LLVM_ABI 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.
LLVM_ABI const SCEV * getPtrToAddrExpr(const SCEV *Op)
LLVM_ABI const SCEVAddRecExpr * convertSCEVToAddRecWithPredicates(const SCEV *S, const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Preds)
Tries to convert the S expression to an AddRec expression, adding additional predicates to Preds as r...
LLVM_ABI const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
LLVM_ABI const SCEV * getSizeOfExpr(Type *IntTy, TypeSize Size)
Return an expression for a TypeSize.
LLVM_ABI std::optional< bool > evaluatePredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Check whether the condition described by Pred, LHS, and RHS is true or false.
LLVM_ABI const SCEV * getUnknown(Value *V)
LLVM_ABI 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.
LLVM_ABI 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.
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask)
Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name ...
LLVM_ABI 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'...
LLVM_ABI bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
LLVM_ABI const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
LLVM_ABI std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
LLVM_ABI 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.
LLVM_ABI bool isKnownPredicateAt(CmpPredicate 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,...
LLVM_ABI const SCEV * getPredicatedSymbolicMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getSymbolicMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI ~ScalarEvolution()
LLVM_ABI const SCEV * getUDivExactExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
LLVM_ABI void registerUser(const SCEV *User, ArrayRef< const SCEV * > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
LLVM_ABI 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.
LLVM_ABI bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the basic block is protected by a conditional between LHS and RHS.
LLVM_ABI 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.
LLVM_ABI 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.
LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI bool isKnownViaInduction(CmpPredicate 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 ...
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.
LLVM_ABI void verify() const
LLVMContext & getContext() const
Implements a dense probed hash-table based set with some number of buckets stored inline.
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.
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.
StringRef - Represent a constant reference to a string, i.e.
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.
static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)
bool isPointerTy() const
True if this is an instance of PointerType.
static LLVM_ABI IntegerType * getInt8Ty(LLVMContext &C)
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntOrPtrTy() const
Return true if this is an integer type or a pointer type.
bool isIntegerTy() const
True if this is an instance of IntegerType.
static LLVM_ABI IntegerType * getIntNTy(LLVMContext &C, unsigned N)
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.
LLVMContext & getContext() const
All values hold a context through their type.
unsigned getValueID() const
Return an ID for the concrete type of this object.
LLVM_ABI 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.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
An efficient, type-erasing, non-owning reference to a callable.
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.
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
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.
LLVM_ABI 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.
LLVM_ABI 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.
int getMinValue(MCInstrInfo const &MCII, MCInst const &MCI)
Return the minimum value of an extendable operand.
@ BasicBlock
Various leaf nodes.
LLVM_ABI Function * getDeclarationIfExists(const Module *M, ID id)
Look up the Function declaration of the intrinsic id in the Module M and return it if it exists.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
IntrinsicID_match m_Intrinsic()
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
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)
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.
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
class_match< const SCEVVScale > m_SCEVVScale()
bind_cst_ty m_scev_APInt(const APInt *&C)
Match an SCEV constant and bind it to an APInt.
cst_pred_ty< is_all_ones > m_scev_AllOnes()
Match an integer with all bits set.
SCEVUnaryExpr_match< SCEVZeroExtendExpr, Op0_t > m_scev_ZExt(const Op0_t &Op0)
is_undef_or_poison m_scev_UndefOrPoison()
Match an SCEVUnknown wrapping undef or poison.
class_match< const SCEVConstant > m_SCEVConstant()
cst_pred_ty< is_one > m_scev_One()
Match an integer 1.
specificloop_ty m_SpecificLoop(const Loop *L)
SCEVAffineAddRec_match< Op0_t, Op1_t, class_match< const Loop > > m_scev_AffineAddRec(const Op0_t &Op0, const Op1_t &Op1)
bind_ty< const SCEVMulExpr > m_scev_Mul(const SCEVMulExpr *&V)
SCEVUnaryExpr_match< SCEVSignExtendExpr, Op0_t > m_scev_SExt(const Op0_t &Op0)
cst_pred_ty< is_zero > m_scev_Zero()
Match an integer 0.
SCEVUnaryExpr_match< SCEVTruncateExpr, Op0_t > m_scev_Trunc(const Op0_t &Op0)
bool match(const SCEV *S, const Pattern &P)
SCEVBinaryExpr_match< SCEVUDivExpr, Op0_t, Op1_t > m_scev_UDiv(const Op0_t &Op0, const Op1_t &Op1)
specificscev_ty m_scev_Specific(const SCEV *S)
Match if we have a specific specified SCEV.
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagNUW, true > m_scev_c_NUWMul(const Op0_t &Op0, const Op1_t &Op1)
class_match< const Loop > m_Loop()
bind_ty< const SCEVAddExpr > m_scev_Add(const SCEVAddExpr *&V)
bind_ty< const SCEVUnknown > m_SCEVUnknown(const SCEVUnknown *&V)
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagAnyWrap, true > m_scev_c_Mul(const Op0_t &Op0, const Op1_t &Op1)
SCEVBinaryExpr_match< SCEVSMaxExpr, Op0_t, Op1_t > m_scev_SMax(const Op0_t &Op0, const Op1_t &Op1)
SCEVURem_match< Op0_t, Op1_t > m_scev_URem(Op0_t LHS, Op1_t RHS, ScalarEvolution &SE)
Match the mathematical pattern A - (A / B) * B, where A and B can be arbitrary expressions.
class_match< const SCEV > m_SCEV()
@ Valid
The data is already valid.
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
friend class Instruction
Iterator for Instructions in a `BasicBlock.
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.
FunctionAddr VTableAddr Value
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.
SaveAndRestore(T &) -> SaveAndRestore< T >
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)
LLVM_ABI bool canCreatePoison(const Operator *Op, bool ConsiderFlagsAndMetadata=true)
LLVM_ABI 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...
LLVM_ABI bool canConstantFoldCallTo(const CallBase *Call, const Function *F)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
InterleavedRange< Range > interleaved(const Range &R, StringRef Separator=", ", StringRef Prefix="", StringRef Suffix="")
Output range R as a sequence of interleaved elements.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI 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)
scope_exit(Callable) -> scope_exit< Callable >
constexpr from_range_t from_range
auto dyn_cast_if_present(const Y &Val)
dyn_cast_if_present<X> - Functionally identical to dyn_cast, except that a null (or none in the case ...
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.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
LLVM_ABI 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)
auto uninitialized_copy(R &&Src, IterTy Dst)
bool isa_and_nonnull(const Y &Val)
LLVM_ABI 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.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI 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...
DomTreeNodeBase< BasicBlock > DomTreeNode
LLVM_ABI 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,...
auto dyn_cast_or_null(const Y &Val)
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.
iterator_range< pointee_iterator< WrappedIteratorT > > make_pointee_range(RangeT &&Range)
auto reverse(ContainerTy &&C)
LLVM_ABI bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
LLVM_ABI bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
LLVM_ABI bool isFinite(const Loop *L)
Return true if this loop can be assumed to run for a finite number of iterations.
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
LLVM_ABI bool programUndefinedIfPoison(const Instruction *Inst)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isPointerTy(const Type *T)
FunctionAddr VTableAddr Count
LLVM_ABI 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...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
LLVM_ABI 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.
LLVM_ABI 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()).
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...
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)
ArrayRef(const T &OneElt) -> ArrayRef< T >
LLVM_ABI unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Return the number of times the sign bit of the register is replicated into the other bits.
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.
LLVM_ABI 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...
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
constexpr bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
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.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI 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.
LLVM_ABI Constant * ConstantFoldInstOperands(const 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 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.
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 LLVM_ABI 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 LLVM_ABI 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 LLVM_ABI KnownBits shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW=false, bool NSW=false, bool ShAmtNonZero=false)
Compute known bits for shl(LHS, RHS).
An object of this class is returned by queries that could not be answered.
LLVM_ABI SCEVCouldNotCompute()
static LLVM_ABI 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...
LLVM_ABI 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
SmallVector< const SCEVPredicate *, 4 > Predicates
A vector of predicate guards for this ExitLimit.
const SCEV * ConstantMaxNotTaken