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"),
343#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
363 OS <<
"(ptrto" << OpS <<
" " << *
Op->getType() <<
" " << *
Op <<
" to "
370 OS <<
"(trunc " << *
Op->getType() <<
" " << *
Op <<
" to "
377 OS <<
"(zext " << *
Op->getType() <<
" " << *
Op <<
" to "
384 OS <<
"(sext " << *
Op->getType() <<
" " << *
Op <<
" to "
413 const char *OpStr =
nullptr;
426 OpStr =
" umin_seq ";
450 OS <<
"(" << *UDiv->
getLHS() <<
" /u " << *UDiv->
getRHS() <<
")";
457 OS <<
"***COULDNOTCOMPUTE***";
535 if (!
Mul)
return false;
539 if (!SC)
return false;
553 auto &Entry = ConstantSCEVs[V];
562 static_cast<SCEVConstant *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP)))
566 UniqueSCEVs.InsertNode(S, IP);
581 ConstantInt::get(ITy, V,
isSigned,
true));
589 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
592 UniqueSCEVs.InsertNode(S, IP);
613 "Must be a non-bit-width-changing pointer-to-integer cast!");
620 "Must be a non-bit-width-changing pointer-to-integer cast!");
632 "Cannot truncate non-integer value!");
639 "Cannot zero extend non-integer value!");
646 "Cannot sign extend non-integer value!");
651 SE->forgetMemoizedResults({
this});
654 SE->UniqueSCEVs.RemoveNode(
this);
660void SCEVUnknown::allUsesReplacedWith(
Value *New) {
662 SE->forgetMemoizedResults({
this});
665 SE->UniqueSCEVs.RemoveNode(
this);
687 if (LIsPointer != RIsPointer)
688 return (
int)LIsPointer - (int)RIsPointer;
693 return (
int)LID - (int)RID;
698 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
699 return (
int)LArgNo - (int)RArgNo;
705 if (
auto L = LGV->getLinkage() - RGV->getLinkage())
708 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
709 auto LT = GV->getLinkage();
716 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
717 return LGV->getName().compare(RGV->getName());
728 if (LParent != RParent) {
731 if (LDepth != RDepth)
732 return (
int)LDepth - (int)RDepth;
736 unsigned LNumOps = LInst->getNumOperands(),
737 RNumOps = RInst->getNumOperands();
738 if (LNumOps != RNumOps)
739 return (
int)LNumOps - (int)RNumOps;
741 for (
unsigned Idx :
seq(LNumOps)) {
743 RInst->getOperand(Idx),
Depth + 1);
757static std::optional<int>
767 return (
int)LType - (int)RType;
792 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
793 if (LBitWidth != RBitWidth)
794 return (
int)LBitWidth - (int)RBitWidth;
795 return LA.
ult(
RA) ? -1 : 1;
801 return LTy->getBitWidth() - RTy->getBitWidth();
812 if (LLoop != RLoop) {
814 assert(LHead != RHead &&
"Two loops share the same header?");
818 "No dominance between recurrences used by one SCEV?");
842 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
843 if (LNumOps != RNumOps)
844 return (
int)LNumOps - (int)RNumOps;
846 for (
unsigned i = 0; i != LNumOps; ++i) {
872 if (
Ops.size() < 2)
return;
877 return Complexity && *Complexity < 0;
879 if (
Ops.size() == 2) {
883 if (IsLessComplex(
RHS,
LHS))
896 for (
unsigned i = 0, e =
Ops.size(); i != e-2; ++i) {
902 for (
unsigned j = i+1; j != e &&
Ops[j]->getSCEVType() == Complexity; ++j) {
907 if (i == e-2)
return;
929template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
933 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
935 for (
unsigned Idx = 0; Idx <
Ops.size();) {
943 Ops.erase(
Ops.begin() + Idx);
950 assert(Folded &&
"Must have folded value");
954 if (Folded && IsAbsorber(Folded->
getAPInt()))
958 if (Folded && !IsIdentity(Folded->
getAPInt()))
959 Ops.insert(
Ops.begin(), Folded);
961 return Ops.size() == 1 ?
Ops[0] :
nullptr;
1036 APInt OddFactorial(W, 1);
1038 for (
unsigned i = 3; i <= K; ++i) {
1041 OddFactorial *= (i >> TwoFactors);
1045 unsigned CalculationBits = W +
T;
1059 for (
unsigned i = 1; i != K; ++i) {
1092 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1121 ConversionFn CreatePtrCast;
1125 ConversionFn CreatePtrCast)
1126 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
1129 Type *TargetTy, ConversionFn CreatePtrCast) {
1131 return Rewriter.visit(Scev);
1167 "Should only reach pointer-typed SCEVUnknown's.");
1172 return SE.getZero(TargetTy);
1173 return CreatePtrCast(Expr);
1178 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1182 if (DL.hasUnstableRepresentation(
Op->getType()))
1185 Type *Ty = DL.getAddressType(
Op->getType());
1196 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1198 SCEV *S =
new (SCEVAllocator)
1200 UniqueSCEVs.InsertNode(S, IP);
1203 return static_cast<const SCEV *
>(S);
1206 "We must have succeeded in sinking the cast, "
1207 "and ending up with an integer-typed expression!");
1212 assert(Ty->isIntegerTy() &&
"Target type must be an integer type!");
1222 "This is not a truncating conversion!");
1224 "This is not a conversion to a SCEVable type!");
1225 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1233 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1255 UniqueSCEVs.InsertNode(S, IP);
1268 unsigned numTruncs = 0;
1269 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1277 if (numTruncs < 2) {
1287 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1294 for (
const SCEV *
Op : AddRec->operands())
1309 UniqueSCEVs.InsertNode(S, IP);
1350struct ExtendOpTraitsBase {
1351 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
const SCEV *,
Type *,
1356template <
typename ExtendOp>
struct ExtendOpTraits {
1372 static const GetExtendExprTy GetExtendExpr;
1374 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1375 ICmpInst::Predicate *Pred,
1376 ScalarEvolution *SE) {
1381const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1388 static const GetExtendExprTy GetExtendExpr;
1390 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1391 ICmpInst::Predicate *Pred,
1392 ScalarEvolution *SE) {
1397const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1409template <
typename ExtendOpTy>
1412 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1413 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1429 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1442 auto PreStartFlags =
1460 const SCEV *OperandExtendedStart =
1462 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1463 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1475 const SCEV *OverflowLimit =
1476 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1478 if (OverflowLimit &&
1486template <
typename ExtendOpTy>
1490 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1498 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1533template <
typename ExtendOpTy>
1534bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1537 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1547 APInt StartAI = StartC->
getAPInt();
1549 for (
unsigned Delta : {-2, -1, 1, 2}) {
1550 const SCEV *PreStart =
getConstant(StartAI - Delta);
1552 FoldingSetNodeID
ID;
1554 ID.AddPointer(PreStart);
1555 ID.AddPointer(Step);
1559 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
1563 if (PreAR &&
any(PreAR->getNoWrapFlags(WrapType))) {
1566 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1567 DeltaS, &Pred,
this);
1585 const unsigned BitWidth =
C.getBitWidth();
1603 const APInt &ConstantStart,
1622 auto &UserIDs = FoldCacheUser[
I.first->second];
1623 assert(
count(UserIDs,
ID) == 1 &&
"unexpected duplicates in UserIDs");
1624 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1625 if (UserIDs[
I] ==
ID) {
1630 I.first->second = S;
1632 FoldCacheUser[S].push_back(
ID);
1638 "This is not an extending conversion!");
1640 "This is not a conversion to a SCEVable type!");
1641 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1645 if (
const SCEV *S = FoldCache.lookup(
ID))
1657 "This is not an extending conversion!");
1659 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1671 const SCEV *Start, *Step;
1676 if (AR->hasNoUnsignedWrap()) {
1690 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1694 UniqueSCEVs.InsertNode(S, IP);
1704 const SCEV *
X = ST->getOperand();
1737 const SCEV *CastedMaxBECount =
1741 if (MaxBECount == RecastedMaxBECount) {
1750 const SCEV *WideMaxBECount =
1752 const SCEV *OperandExtendedAdd =
1758 if (ZAdd == OperandExtendedAdd) {
1769 OperandExtendedAdd =
1775 if (ZAdd == OperandExtendedAdd) {
1796 !AC.assumptions().empty()) {
1798 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1800 if (AR->hasNoUnsignedWrap()) {
1835 const APInt &
C = SC->getAPInt();
1839 const SCEV *SResidual =
1847 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1871 if (SA->hasNoUnsignedWrap()) {
1884 if (SA->hasNoSignedWrap() &&
1887 C->isNegative() && !
C->isMinSignedValue() && C2->
sge(
C->abs())) {
1906 const SCEV *SResidual =
1917 if (
SM->hasNoUnsignedWrap()) {
1939 const SCEV *TruncRHS;
1976 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1979 UniqueSCEVs.InsertNode(S, IP);
1988 "This is not an extending conversion!");
1990 "This is not a conversion to a SCEVable type!");
1991 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1995 if (
const SCEV *S = FoldCache.lookup(
ID))
2007 "This is not an extending conversion!");
2009 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
2026 const SCEV *Start, *Step;
2031 if (AR->hasNoSignedWrap()) {
2045 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
2050 UniqueSCEVs.InsertNode(S, IP);
2060 const SCEV *
X = ST->getOperand();
2071 if (SA->hasNoSignedWrap()) {
2093 const SCEV *SResidual =
2126 const SCEV *CastedMaxBECount =
2130 if (MaxBECount == RecastedMaxBECount) {
2139 const SCEV *WideMaxBECount =
2141 const SCEV *OperandExtendedAdd =
2147 if (SAdd == OperandExtendedAdd) {
2158 OperandExtendedAdd =
2164 if (SAdd == OperandExtendedAdd) {
2184 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2186 if (AR->hasNoSignedWrap()) {
2200 const APInt &
C = SC->getAPInt();
2204 const SCEV *SResidual =
2212 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2239 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
2242 UniqueSCEVs.InsertNode(S, IP);
2259 assert(Expr->
getType() == Ty &&
"requested type must match");
2274 "This is not an extending conversion!");
2276 "This is not a conversion to a SCEVable type!");
2281 if (SC->getAPInt().isNegative())
2286 const SCEV *NewOp =
T->getOperand();
2305 for (
const SCEV *
Op : AR->operands())
2343 APInt &AccumulatedConstant,
2347 bool Interesting =
false;
2354 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2356 AccumulatedConstant += Scale *
C->getAPInt();
2361 for (; i !=
Ops.size(); ++i) {
2370 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2376 auto Pair = M.insert({
Key, NewScale});
2380 Pair.first->second += NewScale;
2388 auto Pair = M.insert({
Ops[i], Scale});
2392 Pair.first->second += Scale;
2411 case Instruction::Add:
2414 case Instruction::Sub:
2417 case Instruction::Mul:
2431 const SCEV *
A = (this->*Extension)(
2433 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2434 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2442 if (BinOp == Instruction::Mul)
2448 APInt C = RHSC->getAPInt();
2449 unsigned NumBits =
C.getBitWidth();
2450 bool IsSub = (BinOp == Instruction::Sub);
2451 bool IsNegativeConst = (
Signed &&
C.isNegative());
2453 bool OverflowDown = IsSub ^ IsNegativeConst;
2455 if (IsNegativeConst) {
2468 APInt Limit = Min + Magnitude;
2474 APInt Limit = Max - Magnitude;
2479std::optional<SCEV::NoWrapFlags>
2484 return std::nullopt;
2493 bool Deduced =
false;
2499 bool CanUseNSW =
true;
2500 const APInt *ShiftAmt;
2505 return std::nullopt;
2509 Opcode = Instruction::Mul;
2511 }
else if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
2512 Opcode != Instruction::Mul) {
2513 return std::nullopt;
2532 return std::nullopt;
2542 using namespace std::placeholders;
2549 assert(CanAnalyze &&
"don't call from other places!");
2556 auto IsKnownNonNegative = [&](
SCEVUse U) {
2565 if (SignOrUnsignWrap != SignOrUnsignMask &&
2572 return Instruction::Add;
2574 return Instruction::Mul;
2585 Opcode,
C, OBO::NoSignedWrap);
2593 Opcode,
C, OBO::NoUnsignedWrap);
2603 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2610 if (UDiv->getOperand(1) ==
Ops[1])
2613 if (UDiv->getOperand(1) ==
Ops[0])
2629 "only nuw or nsw allowed");
2630 assert(!
Ops.empty() &&
"Cannot get empty add!");
2631 if (
Ops.size() == 1)
return Ops[0];
2634 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2636 "SCEVAddExpr operand types don't match!");
2638 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2639 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2644 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2645 [](
const APInt &
C) {
return C.isZero(); },
2646 [](
const APInt &
C) {
return false; });
2659 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2664 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2665 Add->setNoWrapFlags(ComputeFlags(
Ops));
2673 bool FoundMatch =
false;
2674 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2675 if (
Ops[i] ==
Ops[i+1]) {
2687 --i; e -=
Count - 1;
2697 auto FindTruncSrcType = [&]() ->
Type * {
2703 return T->getOperand()->getType();
2705 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2707 return T->getOperand()->getType();
2711 if (
auto *SrcType = FindTruncSrcType()) {
2718 if (
T->getOperand()->getType() != SrcType) {
2727 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2730 if (
T->getOperand()->getType() != SrcType) {
2758 if (
Ops.size() == 2) {
2768 auto C2 =
C->getAPInt();
2771 APInt ConstAdd = C1 + C2;
2772 auto AddFlags = AddExpr->getNoWrapFlags();
2813 if (
Ops.size() == 2 &&
2824 if (Idx <
Ops.size()) {
2825 bool DeletedAdd =
false;
2836 Ops.erase(
Ops.begin()+Idx);
2839 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2862 struct APIntCompare {
2863 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2864 return LHS.ult(RHS);
2871 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2872 for (
const SCEV *NewOp : NewOps)
2873 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2876 if (AccumulatedConstant != 0)
2878 for (
auto &MulOp : MulOpLists) {
2879 if (MulOp.first == 1) {
2881 }
else if (MulOp.first != 0) {
2890 if (
Ops.size() == 1)
2899 if (M->getNumOperands() == 2)
2900 return M->getOperand(
OpIdx == 0);
2911 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2915 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2923 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp) {
2924 if (MulOpSCEV ==
Ops[AddOp]) {
2935 for (
unsigned OMulOp = 0, OE = OtherMul->
getNumOperands(); OMulOp != OE;
2937 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2939 Cofactors.
push_back(StripFactor(OtherMul, OMulOp));
2948 if (!Cofactors.
empty()) {
2956 if (
Ops.size() == DeadIndices.
size() + 1)
2963 Ops.erase(
Ops.begin() + Idx);
2967 Ops.push_back(OuterMul);
2986 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2989 Ops.erase(
Ops.begin()+i);
2994 if (!LIOps.
empty()) {
3019 auto *DefI = getDefiningScopeBound(LIOps);
3021 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
3033 if (
Ops.size() == 1)
return NewRec;
3036 for (
unsigned i = 0;; ++i)
3037 if (
Ops[i] == AddRec) {
3047 for (
unsigned OtherIdx = Idx+1;
3055 "AddRecExprs are not sorted in reverse dominance order?");
3062 if (OtherAddRec->getLoop() == AddRecLoop) {
3063 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
3065 if (i >= AddRecOps.
size()) {
3066 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
3070 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
3073 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3088 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
3099 static_cast<SCEVAddExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3103 S =
new (SCEVAllocator)
3105 UniqueSCEVs.InsertNode(S, IP);
3116 FoldingSetNodeID
ID;
3118 for (
const SCEV *
Op :
Ops)
3123 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3127 S =
new (SCEVAllocator)
3128 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3129 UniqueSCEVs.InsertNode(S, IP);
3131 LoopUsers[
L].push_back(S);
3140 FoldingSetNodeID
ID;
3142 for (
const SCEV *
Op :
Ops)
3146 static_cast<SCEVMulExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3150 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3152 UniqueSCEVs.InsertNode(S, IP);
3162 if (j > 1 && k / j != i) Overflow =
true;
3178 if (n == 0 || n == k)
return 1;
3179 if (k > n)
return 0;
3185 for (
uint64_t i = 1; i <= k; ++i) {
3186 r =
umul_ov(r, n-(i-1), Overflow);
3195 struct FindConstantInAddMulChain {
3196 bool FoundConstant =
false;
3198 bool follow(
const SCEV *S) {
3203 bool isDone()
const {
3204 return FoundConstant;
3208 FindConstantInAddMulChain
F;
3210 ST.visitAll(StartExpr);
3211 return F.FoundConstant;
3219 "only nuw or nsw allowed");
3220 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3221 if (
Ops.size() == 1)
return Ops[0];
3223 Type *ETy =
Ops[0]->getType();
3225 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3227 "SCEVMulExpr operand types don't match!");
3232 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3233 [](
const APInt &
C) {
return C.isOne(); },
3234 [](
const APInt &
C) {
return C.isZero(); });
3245 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3250 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3251 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3256 if (
Ops.size() == 2) {
3264 const SCEV *Op0, *Op1;
3272 if (
Ops[0]->isAllOnesValue()) {
3277 bool AnyFolded =
false;
3278 for (
const SCEV *AddOp :
Add->operands()) {
3298 if (AddRec->hasNoSignedWrap()) {
3305 AddRec->getNoWrapFlags(FlagsMask));
3328 APInt C1V = LHSC->getAPInt();
3338 const SCEV *NewMul =
nullptr;
3342 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3357 if (Idx <
Ops.size()) {
3358 bool DeletedMul =
false;
3364 Ops.erase(
Ops.begin()+Idx);
3388 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3391 Ops.erase(
Ops.begin()+i);
3396 if (!LIOps.
empty()) {
3409 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3425 if (
Ops.size() == 1)
return NewRec;
3428 for (
unsigned i = 0;; ++i)
3429 if (
Ops[i] == AddRec) {
3450 bool OpsModified =
false;
3451 for (
unsigned OtherIdx = Idx+1;
3465 bool Overflow =
false;
3472 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3476 z < ze && !Overflow; ++z) {
3479 if (LargerThan64Bits)
3480 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3482 Coeff = Coeff1*Coeff2;
3497 if (
Ops.size() == 2)
return NewAddRec;
3498 Ops[Idx] = NewAddRec;
3499 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3515 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3522 "SCEVURemExpr operand types don't match!");
3527 if (RHSC->getValue()->isOne())
3528 return getZero(LHS->getType());
3531 if (RHSC->getAPInt().isPowerOf2()) {
3532 Type *FullTy = LHS->getType();
3548 assert(!LHS->getType()->isPointerTy() &&
3549 "SCEVUDivExpr operand can't be pointer!");
3550 assert(LHS->getType() == RHS->getType() &&
3551 "SCEVUDivExpr operand types don't match!");
3558 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3566 if (RHSC->getValue()->isOne())
3571 if (!RHSC->getValue()->isZero()) {
3575 Type *Ty = LHS->getType();
3576 unsigned LZ = RHSC->getAPInt().countl_zero();
3580 if (!RHSC->getAPInt().isPowerOf2())
3588 const APInt &StepInt = Step->getAPInt();
3589 const APInt &DivInt = RHSC->getAPInt();
3590 if (!StepInt.
urem(DivInt) &&
3596 for (
const SCEV *
Op : AR->operands())
3602 const APInt *StartRem;
3615 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3619 const SCEV *NewStart =
3621 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3623 const SCEV *NewLHS =
3626 if (LHS != NewLHS) {
3636 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3645 for (
const SCEV *
Op : M->operands())
3649 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3650 const SCEV *
Op = M->getOperand(i);
3677 if (
auto *DivisorConstant =
3679 bool Overflow =
false;
3681 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3692 for (
const SCEV *
Op :
A->operands())
3696 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3703 if (Operands.
size() ==
A->getNumOperands())
3715 const APInt &
N = RHSC->getAPInt();
3716 const APInt *NMinusM, *M;
3720 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3721 *NMinusM ==
N - *M) {
3730 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3740 return getZero(LHS->getType());
3744 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3745 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3746 if (
Mul->getOperand(i) == RHS) {
3757 const SCEV *NewLHS, *NewRHS;
3765 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
3768 UniqueSCEVs.InsertNode(S, IP);
3805 if (StepChrec->getLoop() == L) {
3819 if (Operands.
size() == 1)
return Operands[0];
3824 "SCEVAddRecExpr operand types don't match!");
3825 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3827 for (
const SCEV *
Op : Operands)
3829 "SCEVAddRecExpr operand is not available at loop entry!");
3832 if (Operands.
back()->isZero()) {
3847 const Loop *NestedLoop = NestedAR->getLoop();
3848 if (L->contains(NestedLoop)
3851 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3853 Operands[0] = NestedAR->getStart();
3857 bool AllInvariant =
all_of(
3869 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3880 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3884 Operands[0] = NestedAR;
3890 return getOrCreateAddRecExpr(Operands, L, Flags);
3906 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3910 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3924 bool FirstIter =
true;
3926 for (
SCEVUse IndexExpr : IndexExprs) {
3933 Offsets.push_back(FieldOffset);
3936 CurTy = STy->getTypeAtIndex(Index);
3941 "The first index of a GEP indexes a pointer");
3942 CurTy = SrcElementTy;
3953 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3954 Offsets.push_back(LocalOffset);
3959 if (Offsets.empty())
3972 "GEP should not change type mid-flight.");
3976SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3979 ID.AddInteger(SCEVType);
3983 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3986SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3989 ID.AddInteger(SCEVType);
3993 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4003 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
4004 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4005 if (
Ops.size() == 1)
return Ops[0];
4008 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4010 "Operand types don't match!");
4013 "min/max should be consistently pointerish");
4039 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
4041 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
4046 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
4048 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
4054 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
4060 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
4065 if (Idx <
Ops.size()) {
4066 bool DeletedAny =
false;
4067 while (
Ops[Idx]->getSCEVType() == Kind) {
4069 Ops.erase(
Ops.begin()+Idx);
4087 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
4088 if (
Ops[i] ==
Ops[i + 1] ||
4089 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
4092 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
4095 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
4098 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
4104 if (
Ops.size() == 1)
return Ops[0];
4106 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
4111 ID.AddInteger(Kind);
4115 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4117 return ExistingSCEV;
4120 SCEV *S =
new (SCEVAllocator)
4123 UniqueSCEVs.InsertNode(S, IP);
4131class SCEVSequentialMinMaxDeduplicatingVisitor final
4132 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4133 std::optional<const SCEV *>> {
4134 using RetVal = std::optional<const SCEV *>;
4142 bool canRecurseInto(
SCEVTypes Kind)
const {
4145 return RootKind == Kind || NonSequentialRootKind == Kind;
4148 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
4150 "Only for min/max expressions.");
4153 if (!canRecurseInto(Kind))
4163 return std::nullopt;
4170 RetVal
visit(
const SCEV *S) {
4172 if (!SeenOps.
insert(S).second)
4173 return std::nullopt;
4174 return Base::visit(S);
4178 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4180 : SE(SE), RootKind(RootKind),
4181 NonSequentialRootKind(
4182 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4186 SmallVectorImpl<SCEVUse> &NewOps) {
4191 for (
const SCEV *
Op : OrigOps) {
4196 Ops.emplace_back(*NewOp);
4200 NewOps = std::move(
Ops);
4204 RetVal visitConstant(
const SCEVConstant *Constant) {
return Constant; }
4206 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4208 RetVal visitPtrToAddrExpr(
const SCEVPtrToAddrExpr *Expr) {
return Expr; }
4210 RetVal visitPtrToIntExpr(
const SCEVPtrToIntExpr *Expr) {
return Expr; }
4212 RetVal visitTruncateExpr(
const SCEVTruncateExpr *Expr) {
return Expr; }
4214 RetVal visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
return Expr; }
4216 RetVal visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
return Expr; }
4218 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4220 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4222 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4224 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4226 RetVal visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
4227 return visitAnyMinMaxExpr(Expr);
4230 RetVal visitUMaxExpr(
const SCEVUMaxExpr *Expr) {
4231 return visitAnyMinMaxExpr(Expr);
4234 RetVal visitSMinExpr(
const SCEVSMinExpr *Expr) {
4235 return visitAnyMinMaxExpr(Expr);
4238 RetVal visitUMinExpr(
const SCEVUMinExpr *Expr) {
4239 return visitAnyMinMaxExpr(Expr);
4242 RetVal visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *Expr) {
4243 return visitAnyMinMaxExpr(Expr);
4246 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4248 RetVal visitCouldNotCompute(
const SCEVCouldNotCompute *Expr) {
return Expr; }
4291struct SCEVPoisonCollector {
4292 bool LookThroughMaybePoisonBlocking;
4293 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4294 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4295 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4297 bool follow(
const SCEV *S) {
4298 if (!LookThroughMaybePoisonBlocking &&
4308 bool isDone()
const {
return false; }
4318 SCEVPoisonCollector PC1(
true);
4323 if (PC1.MaybePoison.empty())
4329 SCEVPoisonCollector PC2(
false);
4339 SCEVPoisonCollector PC(
false);
4362 while (!Worklist.
empty()) {
4364 if (!Visited.
insert(V).second)
4368 if (Visited.
size() > 16)
4384 if (PDI->isDisjoint())
4391 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4398 if (
I->hasPoisonGeneratingAnnotations())
4409 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4410 "Not a SCEVSequentialMinMaxExpr!");
4411 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4412 if (
Ops.size() == 1)
4416 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4418 "Operand types don't match!");
4421 "min/max should be consistently pointerish");
4429 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4436 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4446 bool DeletedAny =
false;
4447 while (Idx <
Ops.size()) {
4448 if (
Ops[Idx]->getSCEVType() != Kind) {
4453 Ops.erase(
Ops.begin() + Idx);
4454 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4455 SMME->operands().end());
4463 const SCEV *SaturationPoint;
4474 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4475 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4487 Ops.erase(
Ops.begin() + i);
4492 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4493 Ops.erase(
Ops.begin() + i);
4501 ID.AddInteger(Kind);
4505 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4507 return ExistingSCEV;
4511 SCEV *S =
new (SCEVAllocator)
4514 UniqueSCEVs.InsertNode(S, IP);
4562 if (
Size.isScalable())
4583 "Cannot get offset for structure containing scalable vector types");
4597 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP)) {
4599 "Stale SCEVUnknown in uniquing map!");
4605 UniqueSCEVs.InsertNode(S, IP);
4620 return Ty->isIntOrPtrTy();
4627 if (Ty->isPointerTy())
4638 if (Ty->isIntegerTy())
4642 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4654 bool PreciseA, PreciseB;
4655 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4656 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4657 if (!PreciseA || !PreciseB)
4660 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4661 DT.dominates(ScopeB, ScopeA);
4665 return CouldNotCompute.get();
4668bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4671 return SU && SU->getValue() ==
nullptr;
4674 return !ContainsNulls;
4679 if (
I != HasRecMap.end())
4684 HasRecMap.insert({S, FoundAddRec});
4692 if (
SI == ExprValueMap.
end())
4694 return SI->second.getArrayRef();
4700void ScalarEvolution::eraseValueFromMap(
Value *V) {
4702 if (
I != ValueExprMap.end()) {
4703 auto EVIt = ExprValueMap.find(
I->second);
4704 bool Removed = EVIt->second.remove(V);
4706 assert(Removed &&
"Value not in ExprValueMap?");
4707 ValueExprMap.erase(
I);
4711void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4715 auto It = ValueExprMap.find_as(V);
4716 if (It == ValueExprMap.end()) {
4718 ExprValueMap[S].insert(V);
4729 return createSCEVIter(V);
4736 if (
I != ValueExprMap.end()) {
4737 const SCEV *S =
I->second;
4738 assert(checkValidity(S) &&
4739 "existing SCEV has not been properly invalidated");
4752 Type *Ty = V->getType();
4768 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4781 return (
const SCEV *)
nullptr;
4787 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4791 Type *Ty = V->getType();
4797 assert(
P->getType()->isPointerTy());
4812 if (AddOp->getType()->isPointerTy()) {
4813 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4831 return getZero(LHS->getType());
4836 if (RHS->getType()->isPointerTy()) {
4837 if (!LHS->getType()->isPointerTy() ||
4847 const bool RHSIsNotMinSigned =
4878 Type *SrcTy = V->getType();
4879 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4880 "Cannot truncate or zero extend with non-integer arguments!");
4890 Type *SrcTy = V->getType();
4891 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4892 "Cannot truncate or zero extend with non-integer arguments!");
4902 Type *SrcTy = V->getType();
4903 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4904 "Cannot noop or zero extend with non-integer arguments!");
4906 "getNoopOrZeroExtend cannot truncate!");
4914 Type *SrcTy = V->getType();
4915 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4916 "Cannot noop or sign extend with non-integer arguments!");
4918 "getNoopOrSignExtend cannot truncate!");
4926 Type *SrcTy = V->getType();
4927 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4928 "Cannot noop or any extend with non-integer arguments!");
4930 "getNoopOrAnyExtend cannot truncate!");
4938 Type *SrcTy = V->getType();
4939 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4940 "Cannot truncate or noop with non-integer arguments!");
4942 "getTruncateOrNoop cannot extend!");
4950 const SCEV *PromotedLHS = LHS;
4951 const SCEV *PromotedRHS = RHS;
4971 assert(!
Ops.empty() &&
"At least one operand must be!");
4973 if (
Ops.size() == 1)
4977 Type *MaxType =
nullptr;
4983 assert(MaxType &&
"Failed to find maximum type!");
4996 if (!V->getType()->isPointerTy())
5001 V = AddRec->getStart();
5003 const SCEV *PtrOp =
nullptr;
5004 for (
const SCEV *AddOp :
Add->operands()) {
5005 if (AddOp->getType()->isPointerTy()) {
5006 assert(!PtrOp &&
"Cannot have multiple pointer ops");
5010 assert(PtrOp &&
"Must have pointer op");
5022 for (
User *U :
I->users()) {
5024 if (Visited.
insert(UserInsn).second)
5038 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
5039 bool IgnoreOtherLoops =
true) {
5042 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
5044 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
5049 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5051 SeenLoopVariantSCEVUnknown =
true;
5055 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5059 SeenOtherLoops =
true;
5063 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
5065 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
5068 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
5069 : SCEVRewriteVisitor(SE),
L(
L) {}
5072 bool SeenLoopVariantSCEVUnknown =
false;
5073 bool SeenOtherLoops =
false;
5082 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
5083 SCEVPostIncRewriter
Rewriter(L, SE);
5085 return Rewriter.hasSeenLoopVariantSCEVUnknown()
5090 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5092 SeenLoopVariantSCEVUnknown =
true;
5096 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5100 SeenOtherLoops =
true;
5104 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
5106 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
5109 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
5110 : SCEVRewriteVisitor(SE),
L(
L) {}
5113 bool SeenLoopVariantSCEVUnknown =
false;
5114 bool SeenOtherLoops =
false;
5120class SCEVBackedgeConditionFolder
5123 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5124 ScalarEvolution &SE) {
5125 bool IsPosBECond =
false;
5126 Value *BECond =
nullptr;
5127 if (BasicBlock *Latch =
L->getLoopLatch()) {
5129 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
5130 "Both outgoing branches should not target same header!");
5131 BECond = BI->getCondition();
5132 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
5137 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
5141 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5142 const SCEV *
Result = Expr;
5147 switch (
I->getOpcode()) {
5148 case Instruction::Select: {
5150 std::optional<const SCEV *> Res =
5151 compareWithBackedgeCondition(
SI->getCondition());
5159 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5170 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5171 bool IsPosBECond, ScalarEvolution &SE)
5172 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5173 IsPositiveBECond(IsPosBECond) {}
5175 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5179 Value *BackedgeCond =
nullptr;
5181 bool IsPositiveBECond;
5184std::optional<const SCEV *>
5185SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5190 if (BackedgeCond == IC)
5193 return std::nullopt;
5198 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5199 ScalarEvolution &SE) {
5205 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5212 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5222 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5223 : SCEVRewriteVisitor(SE),
L(
L) {}
5231void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5247 const APInt &BECountAP = BECountMax->getAPInt();
5248 unsigned NoOverflowBitWidth =
5257ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5267 if (!SignedWrapViaInductionTried.insert(AR).second)
5292 AC.assumptions().empty())
5300 const SCEV *OverflowLimit =
5302 if (OverflowLimit &&
5310ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5320 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5346 AC.assumptions().empty())
5385 IsNSW = OBO->hasNoSignedWrap();
5386 IsNUW = OBO->hasNoUnsignedWrap();
5392 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5404 return std::nullopt;
5410 switch (
Op->getOpcode()) {
5411 case Instruction::Add:
5412 case Instruction::Sub:
5413 case Instruction::Mul:
5414 case Instruction::UDiv:
5415 case Instruction::URem:
5416 case Instruction::And:
5417 case Instruction::AShr:
5418 case Instruction::Shl:
5421 case Instruction::Or: {
5424 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5434 case Instruction::Xor:
5438 if (RHSC->getValue().isSignMask())
5439 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5441 if (V->getType()->isIntegerTy(1))
5442 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5445 case Instruction::LShr:
5454 if (SA->getValue().ult(
BitWidth)) {
5456 ConstantInt::get(SA->getContext(),
5458 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5463 case Instruction::ExtractValue: {
5465 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5473 bool Signed = WO->isSigned();
5476 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5481 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5492 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5493 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5495 return std::nullopt;
5521 if (
Op == SymbolicPHI)
5526 if (SourceBits != NewBits)
5544 if (!L || L->getHeader() != PN->
getParent())
5602std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5603ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5611 assert(L &&
"Expecting an integer loop header phi");
5616 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5617 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5618 Value *
V = PN->getIncomingValue(i);
5619 if (
L->contains(PN->getIncomingBlock(i))) {
5622 }
else if (BEValueV != V) {
5626 }
else if (!StartValueV) {
5628 }
else if (StartValueV != V) {
5629 StartValueV =
nullptr;
5633 if (!BEValueV || !StartValueV)
5634 return std::nullopt;
5636 const SCEV *BEValue =
getSCEV(BEValueV);
5643 return std::nullopt;
5647 unsigned FoundIndex =
Add->getNumOperands();
5648 Type *TruncTy =
nullptr;
5650 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5653 if (FoundIndex == e) {
5658 if (FoundIndex ==
Add->getNumOperands())
5659 return std::nullopt;
5663 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5664 if (i != FoundIndex)
5665 Ops.push_back(
Add->getOperand(i));
5671 return std::nullopt;
5724 const SCEV *StartVal =
getSCEV(StartValueV);
5725 const SCEV *PHISCEV =
5752 auto getExtendedExpr = [&](
const SCEV *Expr,
5753 bool CreateSignExtend) ->
const SCEV * {
5756 const SCEV *ExtendedExpr =
5759 return ExtendedExpr;
5767 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5768 const SCEV *ExtendedExpr) ->
bool {
5769 return Expr != ExtendedExpr &&
5773 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5774 if (PredIsKnownFalse(StartVal, StartExtended)) {
5776 return std::nullopt;
5781 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5782 if (PredIsKnownFalse(Accum, AccumExtended)) {
5784 return std::nullopt;
5787 auto AppendPredicate = [&](
const SCEV *Expr,
5788 const SCEV *ExtendedExpr) ->
void {
5789 if (Expr != ExtendedExpr &&
5797 AppendPredicate(StartVal, StartExtended);
5798 AppendPredicate(Accum, AccumExtended);
5806 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5807 std::make_pair(NewAR, Predicates);
5809 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5813std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5818 return std::nullopt;
5821 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5822 if (
I != PredicatedSCEVRewrites.end()) {
5823 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5826 if (Rewrite.first == SymbolicPHI)
5827 return std::nullopt;
5831 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5835 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5836 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5841 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5842 return std::nullopt;
5862 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5863 if (Expr1 != Expr2 &&
5864 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5865 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5882const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5884 Value *StartValueV) {
5887 assert(BEValueV && StartValueV);
5893 if (BO->Opcode != Instruction::Add)
5896 const SCEV *Accum =
nullptr;
5897 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5899 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5913 insertValueToMap(PN, PHISCEV);
5916 inferNoWrapViaConstantRanges(AR);
5923 "Accum is defined outside L, but is not invariant?");
5924 if (isAddRecNeverPoison(BEInst, L))
5931const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5932 const Loop *
L = LI.getLoopFor(PN->
getParent());
5939 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5945 }
else if (BEValueV != V) {
5949 }
else if (!StartValueV) {
5951 }
else if (StartValueV != V) {
5952 StartValueV =
nullptr;
5956 if (!BEValueV || !StartValueV)
5959 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5960 "PHI node already processed?");
5964 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5969 insertValueToMap(PN, SymbolicName);
5973 const SCEV *BEValue =
getSCEV(BEValueV);
5983 unsigned FoundIndex =
Add->getNumOperands();
5984 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5985 if (
Add->getOperand(i) == SymbolicName)
5986 if (FoundIndex == e) {
5991 if (FoundIndex !=
Add->getNumOperands()) {
5994 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5995 if (i != FoundIndex)
5996 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
6008 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
6015 if (
GEP->getOperand(0) == PN) {
6016 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
6034 const SCEV *StartVal =
getSCEV(StartValueV);
6035 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
6040 forgetMemoizedResults({SymbolicName});
6041 insertValueToMap(PN, PHISCEV);
6044 inferNoWrapViaConstantRanges(AR);
6068 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
6069 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
6071 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
6072 const SCEV *StartVal =
getSCEV(StartValueV);
6073 if (Start == StartVal) {
6077 forgetMemoizedResults({SymbolicName});
6078 insertValueToMap(PN, Shifted);
6088 eraseValueFromMap(PN);
6103 Use &LeftUse =
Merge->getOperandUse(0);
6104 Use &RightUse =
Merge->getOperandUse(1);
6140 assert(IDom &&
"At least the entry block should dominate PN");
6148const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
6153 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6170 CommonInst = IncomingInst;
6186ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6192 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6193 bool SCEVExprsIdentical =
6195 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6196 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6199const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6200 if (
const SCEV *S = createAddRecFromPHI(PN))
6210 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6213 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6222 struct FindClosure {
6223 const SCEV *OperandToFind;
6229 bool canRecurseInto(
SCEVTypes Kind)
const {
6232 return RootKind == Kind || NonSequentialRootKind == Kind ||
6237 : OperandToFind(OperandToFind), RootKind(RootKind),
6238 NonSequentialRootKind(
6242 bool follow(
const SCEV *S) {
6243 Found = S == OperandToFind;
6245 return !isDone() && canRecurseInto(S->
getSCEVType());
6248 bool isDone()
const {
return Found; }
6251 FindClosure FC(OperandToFind, RootKind);
6256std::optional<const SCEV *>
6257ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6267 switch (ICI->getPredicate()) {
6281 bool Signed = ICI->isSigned();
6282 const SCEV *LA =
getSCEV(TrueVal);
6290 if (LA == LS &&
RA == RS)
6292 if (LA == RS &&
RA == LS)
6295 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6296 if (
Op->getType()->isPointerTy()) {
6307 LS = CoerceOperand(LS);
6308 RS = CoerceOperand(RS);
6332 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6333 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6347 X = ZExt->getOperand();
6349 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6360 return std::nullopt;
6363static std::optional<const SCEV *>
6365 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6369 "Unexpected operands of a select.");
6381 return std::nullopt;
6396static std::optional<const SCEV *>
6400 return std::nullopt;
6403 const auto *SETrue = SE->
getSCEV(TrueVal);
6404 const auto *SEFalse = SE->
getSCEV(FalseVal);
6408const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6410 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6412 V->getType() ==
TrueVal->getType() &&
6413 "Types of select hands and of the result must match.");
6416 if (!
V->getType()->isIntegerTy(1))
6419 if (std::optional<const SCEV *> S =
6432 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6436 if (std::optional<const SCEV *> S =
6437 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6443 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6449 assert(
GEP->getSourceElementType()->isSized() &&
6450 "GEP source element type must be sized");
6453 for (
Value *Index :
GEP->indices())
6458APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6461 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6464 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6466 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6469 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6488 return GetShiftedByZeros(TZ);
6498 return GetShiftedByZeros(TZ);
6502 if (
M->hasNoUnsignedWrap()) {
6505 for (
const SCEV *Operand :
M->operands().drop_front())
6513 for (
const SCEV *Operand :
M->operands())
6515 return GetShiftedByZeros(TZ);
6520 if (
N->hasNoUnsignedWrap())
6521 return GetGCDMultiple(
N);
6524 for (
const SCEV *Operand :
N->operands().drop_front())
6526 return GetShiftedByZeros(TZ);
6543 CtxI = &*F.getEntryBlock().begin();
6550 .allowEphemerals(
true))
6551 .countMinTrailingZeros();
6552 return GetShiftedByZeros(
Known);
6565 return getConstantMultipleImpl(S, CtxI);
6567 auto I = ConstantMultipleCache.find(S);
6568 if (
I != ConstantMultipleCache.end())
6571 APInt Result = getConstantMultipleImpl(S, CtxI);
6572 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6573 assert(InsertPair.second &&
"Should insert a new key");
6574 return InsertPair.first->second;
6591 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6594 if (std::optional<ConstantRange>
Range = CB->getRange())
6598 if (std::optional<ConstantRange>
Range =
A->getRange())
6601 return std::nullopt;
6608 UnsignedRanges.erase(AddRec);
6609 SignedRanges.erase(AddRec);
6610 ConstantMultipleCache.erase(AddRec);
6615getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6641 Value *Start, *Step;
6648 assert(L && L->getHeader() ==
P->getParent());
6661 case Instruction::AShr:
6662 case Instruction::LShr:
6663 case Instruction::Shl:
6678 KnownStep.getBitWidth() ==
BitWidth);
6681 auto MaxShiftAmt = KnownStep.getMaxValue();
6683 bool Overflow =
false;
6684 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6691 case Instruction::AShr: {
6699 if (KnownStart.isNonNegative())
6702 KnownStart.getMaxValue() + 1);
6703 if (KnownStart.isNegative())
6706 KnownEnd.getMaxValue() + 1);
6709 case Instruction::LShr: {
6718 KnownStart.getMaxValue() + 1);
6720 case Instruction::Shl: {
6724 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6725 return ConstantRange(KnownStart.getMinValue(),
6726 KnownEnd.getMaxValue() + 1);
6751 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6758ScalarEvolution::getRangeRefIter(
const SCEV *S,
6759 ScalarEvolution::RangeSignHint SignHint) {
6760 DenseMap<const SCEV *, ConstantRange> &Cache =
6761 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6764 SmallPtrSet<const SCEV *, 8> Seen;
6768 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6769 if (!Seen.
insert(Expr).second)
6803 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6804 const SCEV *
P = WorkList[
I];
6808 for (
const SCEV *
Op :
P->operands())
6821 if (!WorkList.
empty()) {
6826 getRangeRef(
P, SignHint);
6830 return getRangeRef(S, SignHint, 0);
6837 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6838 DenseMap<const SCEV *, ConstantRange> &Cache =
6839 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6846 auto I = Cache.
find(S);
6847 if (
I != Cache.
end())
6851 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6856 return getRangeRefIter(S, SignHint);
6859 ConstantRange ConservativeResult(
BitWidth,
true);
6860 using OBO = OverflowingBinaryOperator;
6864 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6868 ConservativeResult =
6875 ConservativeResult = ConstantRange(
6891 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6898 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6905 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6911 return setRange(Cast, SignHint,
X);
6916 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6917 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6919 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6920 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6921 ConservativeResult =
6922 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6924 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6925 unsigned WrapType = OBO::AnyWrap;
6926 if (
Add->hasNoSignedWrap())
6927 WrapType |= OBO::NoSignedWrap;
6928 if (
Add->hasNoUnsignedWrap())
6929 WrapType |= OBO::NoUnsignedWrap;
6931 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6933 return setRange(
Add, SignHint,
6934 ConservativeResult.intersectWith(
X, RangeType));
6938 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6940 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6941 return setRange(
Mul, SignHint,
6942 ConservativeResult.intersectWith(
X, RangeType));
6946 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6947 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6948 return setRange(UDiv, SignHint,
6949 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6957 if (!UnsignedMinValue.
isZero())
6958 ConservativeResult = ConservativeResult.intersectWith(
6959 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6968 bool AllNonNeg =
true;
6969 bool AllNonPos =
true;
6970 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6977 ConservativeResult = ConservativeResult.intersectWith(
6982 ConservativeResult = ConservativeResult.intersectWith(
6991 const SCEV *MaxBEScev =
7005 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
7007 ConservativeResult =
7008 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
7011 auto RangeFromFactoring = getRangeViaFactoring(
7013 ConservativeResult =
7014 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
7020 const SCEV *SymbolicMaxBECount =
7025 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
7026 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
7027 ConservativeResult =
7028 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
7033 return setRange(AddRec, SignHint, std::move(ConservativeResult));
7043 ID = Intrinsic::umax;
7046 ID = Intrinsic::smax;
7050 ID = Intrinsic::umin;
7053 ID = Intrinsic::smin;
7060 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
7061 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
7063 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
7064 return setRange(S, SignHint,
7065 ConservativeResult.intersectWith(
X, RangeType));
7074 ConservativeResult =
7075 ConservativeResult.intersectWith(*MDRange, RangeType);
7080 auto CR = getRangeForUnknownRecurrence(U);
7081 ConservativeResult = ConservativeResult.intersectWith(CR);
7092 if (
U->getType()->isPointerTy()) {
7095 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
7096 int ptrIdxDiff = ptrSize -
BitWidth;
7097 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
7103 if (!
Known.Zero.getHiBits(NS).isZero())
7104 Known.Zero.setHighBits(NS);
7105 if (!
Known.One.getHiBits(NS).isZero())
7106 Known.One.setHighBits(NS);
7109 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
7110 ConservativeResult = ConservativeResult.intersectWith(
7111 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
7114 ConservativeResult = ConservativeResult.intersectWith(
7119 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
7123 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
7124 DL, CanBeNull,
nullptr);
7134 uint64_t
Align =
U->getValue()->getPointerAlignment(DL).value();
7135 uint64_t Rem = MaxVal.
urem(Align);
7140 ConservativeResult = ConservativeResult.intersectWith(
7150 return getRangeRef(AR, SignHint,
Depth + 1);
7154 ConstantRange RangeFromOps(
BitWidth,
false);
7156 for (
const auto &
Op :
Phi->operands()) {
7158 RangeFromOps = RangeFromOps.unionWith(OpRange);
7160 if (RangeFromOps.isFullSet())
7163 ConservativeResult =
7164 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7170 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7172 ConservativeResult = ConservativeResult.difference(Disallowed);
7175 return setRange(U, SignHint, std::move(ConservativeResult));
7181 return setRange(S, SignHint, std::move(ConservativeResult));
7189static std::pair<ConstantRange, bool>
7197 if (Step == 0 || MaxBECount == 0)
7198 return {StartRange,
true};
7204 return {ConstantRange::getFull(
BitWidth),
false};
7220 return {ConstantRange::getFull(
BitWidth),
false};
7233 APInt MovedBoundary;
7238 MovedBoundary = StartLower - std::move(
Offset);
7241 MovedBoundary = StartUpper + std::move(
Offset);
7245 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7252 if (StartRange.
contains(MovedBoundary))
7253 return {ConstantRange::getFull(
BitWidth),
false};
7256 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7258 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7266std::pair<ConstantRange, SCEV::NoWrapFlags>
7267ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7268 const APInt &MaxBECount) {
7272 "mismatched bit widths");
7281 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7283 StartSRange, MaxBECount,
7285 ConstantRange SR = SR1.unionWith(SR2);
7302ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7304 ScalarEvolution::RangeSignHint SignHint) {
7305 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7307 "This only works for non-self-wrapping AddRecs!");
7308 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7312 return ConstantRange::getFull(
BitWidth);
7320 return ConstantRange::getFull(
BitWidth);
7324 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7326 MaxItersWithoutWrap))
7327 return ConstantRange::getFull(
BitWidth);
7348 ConstantRange StartRange = getRangeRef(Start, SignHint);
7349 ConstantRange EndRange = getRangeRef(End, SignHint);
7350 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7354 return RangeBetween;
7359 return ConstantRange::getFull(
BitWidth);
7362 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7363 return RangeBetween;
7365 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7366 return RangeBetween;
7367 return ConstantRange::getFull(
BitWidth);
7372 const APInt &MaxBECount) {
7379 "mismatched bit widths");
7381 struct SelectPattern {
7382 Value *Condition =
nullptr;
7386 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7388 std::optional<unsigned> CastOp;
7402 CastOp = SCast->getSCEVType();
7403 S = SCast->getOperand();
7406 using namespace llvm::PatternMatch;
7413 Condition =
nullptr;
7445 bool isRecognized() {
return Condition !=
nullptr; }
7448 SelectPattern StartPattern(*
this,
BitWidth, Start);
7449 if (!StartPattern.isRecognized())
7450 return ConstantRange::getFull(
BitWidth);
7452 SelectPattern StepPattern(*
this,
BitWidth, Step);
7453 if (!StepPattern.isRecognized())
7454 return ConstantRange::getFull(
BitWidth);
7456 if (StartPattern.Condition != StepPattern.Condition) {
7460 return ConstantRange::getFull(
BitWidth);
7471 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7472 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7473 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7474 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7476 ConstantRange TrueRange =
7477 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7478 ConstantRange FalseRange =
7479 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7491 PDI && PDI->isDisjoint()) {
7506ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7519 SmallPtrSet<const SCEV *, 16> Visited;
7521 auto pushOp = [&](
const SCEV *S) {
7522 if (!Visited.
insert(S).second)
7525 if (Visited.
size() > 30) {
7536 while (!Worklist.
empty()) {
7538 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7539 if (!Bound || DT.dominates(Bound, DefI))
7546 return Bound ? Bound : &*F.getEntryBlock().begin();
7552 return getDefiningScopeBound(
Ops, Discard);
7555bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7557 if (
A->getParent() ==
B->getParent() &&
7562 auto *BLoop = LI.getLoopFor(
B->getParent());
7563 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7564 BLoop->getLoopPreheader() ==
A->getParent() &&
7566 A->getParent()->end()) &&
7574 SCEVPoisonCollector PC(
true);
7576 return PC.MaybePoison.empty();
7579bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7589bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7606 for (
const Use &
Op :
I->operands()) {
7612 auto *DefI = getDefiningScopeBound(SCEVOps);
7613 return isGuaranteedToTransferExecutionTo(DefI,
I);
7616bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7618 if (isSCEVExprNeverPoison(
I))
7629 auto *ExitingBB =
L->getExitingBlock();
7633 SmallPtrSet<const Value *, 16> KnownPoison;
7642 while (!Worklist.
empty()) {
7645 for (
const Use &U :
Poison->uses()) {
7648 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7652 if (KnownPoison.
insert(PoisonUser).second)
7660ScalarEvolution::LoopProperties
7661ScalarEvolution::getLoopProperties(
const Loop *L) {
7662 using LoopProperties = ScalarEvolution::LoopProperties;
7664 auto Itr = LoopPropertiesCache.find(L);
7665 if (Itr == LoopPropertiesCache.end()) {
7668 return !
SI->isSimple();
7678 return I->mayWriteToMemory();
7681 LoopProperties LP = {
true,
7684 for (
auto *BB :
L->getBlocks())
7685 for (
auto &
I : *BB) {
7687 LP.HasNoAbnormalExits =
false;
7688 if (HasSideEffects(&
I))
7689 LP.HasNoSideEffects =
false;
7690 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7694 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7695 assert(InsertPair.second &&
"We just checked!");
7696 Itr = InsertPair.first;
7709const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7715 Stack.emplace_back(V,
false);
7716 while (!Stack.empty()) {
7717 auto E = Stack.back();
7718 Value *CurV = E.getPointer();
7726 const SCEV *CreatedSCEV =
nullptr;
7729 CreatedSCEV = createSCEV(CurV);
7734 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7738 insertValueToMap(CurV, CreatedSCEV);
7741 Stack.back().setInt(
true);
7744 Stack.emplace_back(
Op,
false);
7761 if (!DT.isReachableFromEntry(
I->getParent()))
7774 switch (BO->Opcode) {
7775 case Instruction::Add:
7776 case Instruction::Mul: {
7783 Ops.push_back(BO->
Op);
7787 Ops.push_back(BO->RHS);
7791 (BO->Opcode == Instruction::Add &&
7792 (NewBO->Opcode != Instruction::Add &&
7793 NewBO->Opcode != Instruction::Sub)) ||
7794 (BO->Opcode == Instruction::Mul &&
7795 NewBO->Opcode != Instruction::Mul)) {
7796 Ops.push_back(BO->LHS);
7801 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7804 Ops.push_back(BO->LHS);
7812 case Instruction::Sub:
7813 case Instruction::UDiv:
7814 case Instruction::URem:
7816 case Instruction::AShr:
7817 case Instruction::Shl:
7818 case Instruction::Xor:
7822 case Instruction::And:
7823 case Instruction::Or:
7827 case Instruction::LShr:
7834 Ops.push_back(BO->LHS);
7835 Ops.push_back(BO->RHS);
7839 switch (
U->getOpcode()) {
7840 case Instruction::Trunc:
7841 case Instruction::ZExt:
7842 case Instruction::SExt:
7843 case Instruction::PtrToAddr:
7844 case Instruction::PtrToInt:
7845 Ops.push_back(
U->getOperand(0));
7848 case Instruction::BitCast:
7850 Ops.push_back(
U->getOperand(0));
7855 case Instruction::SDiv:
7856 case Instruction::SRem:
7857 Ops.push_back(
U->getOperand(0));
7858 Ops.push_back(
U->getOperand(1));
7861 case Instruction::GetElementPtr:
7863 "GEP source element type must be sized");
7867 case Instruction::IntToPtr:
7870 case Instruction::PHI:
7901 Ops.push_back(CondICmp->getOperand(0));
7902 Ops.push_back(CondICmp->getOperand(1));
7922 case Instruction::Select: {
7924 auto CanSimplifyToUnknown = [
this,
U]() {
7942 if (CanSimplifyToUnknown())
7949 case Instruction::Call:
7950 case Instruction::Invoke:
7957 switch (
II->getIntrinsicID()) {
7958 case Intrinsic::abs:
7959 Ops.push_back(
II->getArgOperand(0));
7961 case Intrinsic::umax:
7962 case Intrinsic::umin:
7963 case Intrinsic::smax:
7964 case Intrinsic::smin:
7965 case Intrinsic::usub_sat:
7966 case Intrinsic::uadd_sat:
7967 Ops.push_back(
II->getArgOperand(0));
7968 Ops.push_back(
II->getArgOperand(1));
7970 case Intrinsic::start_loop_iterations:
7971 case Intrinsic::annotation:
7972 case Intrinsic::ptr_annotation:
7973 Ops.push_back(
II->getArgOperand(0));
7985const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7994 if (!DT.isReachableFromEntry(
I->getParent()))
8009 switch (BO->Opcode) {
8010 case Instruction::Add: {
8036 if (BO->Opcode == Instruction::Sub)
8044 if (BO->Opcode == Instruction::Sub)
8051 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
8052 NewBO->Opcode != Instruction::Sub)) {
8062 case Instruction::Mul: {
8083 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
8092 case Instruction::UDiv:
8096 case Instruction::URem:
8100 case Instruction::Sub: {
8103 Flags = getNoWrapFlagsFromUB(BO->
Op);
8108 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
8111 if (HasPtrLHS || HasPtrRHS) {
8116 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
8117 bool BothPtr) ->
const SCEV * {
8120 const SCEV *PtrSCEV =
getSCEV(PtrOp);
8130 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
8131 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
8139 case Instruction::And:
8145 if (CI->isMinusOne())
8147 const APInt &
A = CI->getValue();
8153 unsigned LZ =
A.countl_zero();
8154 unsigned TZ =
A.countr_zero();
8159 APInt EffectiveMask =
8161 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
8164 const SCEV *ShiftedLHS =
nullptr;
8168 unsigned MulZeros = OpC->getAPInt().countr_zero();
8169 unsigned GCD = std::min(MulZeros, TZ);
8174 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8196 case Instruction::Or:
8205 case Instruction::Xor:
8208 if (CI->isMinusOne())
8217 if (LBO->getOpcode() == Instruction::And &&
8218 LCI->getValue() == CI->getValue())
8219 if (
const SCEVZeroExtendExpr *Z =
8222 const SCEV *Z0 =
Z->getOperand();
8229 if (CI->getValue().isMask(Z0TySize))
8235 APInt Trunc = CI->getValue().trunc(Z0TySize);
8244 case Instruction::Shl:
8262 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8271 ConstantInt *
X = ConstantInt::get(
8277 case Instruction::AShr:
8299 const SCEV *AddTruncateExpr =
nullptr;
8300 ConstantInt *ShlAmtCI =
nullptr;
8301 const SCEV *AddConstant =
nullptr;
8303 if (L &&
L->getOpcode() == Instruction::Add) {
8311 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8318 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8326 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8331 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8336 if (AddTruncateExpr && ShlAmtCI) {
8348 const APInt &ShlAmt = ShlAmtCI->
getValue();
8352 const SCEV *CompositeExpr =
8354 if (
L->getOpcode() != Instruction::Shl)
8355 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8364 switch (
U->getOpcode()) {
8365 case Instruction::Trunc:
8368 case Instruction::ZExt:
8371 case Instruction::SExt:
8381 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8382 Type *Ty =
U->getType();
8390 case Instruction::BitCast:
8396 case Instruction::PtrToAddr: {
8403 case Instruction::PtrToInt: {
8409 const SCEV *PtrSCEV =
getSCEV(
U->getOperand(0));
8418 case Instruction::IntToPtr:
8422 case Instruction::SDiv:
8429 case Instruction::SRem:
8436 case Instruction::GetElementPtr:
8439 case Instruction::PHI:
8442 case Instruction::Select:
8443 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8446 case Instruction::Call:
8447 case Instruction::Invoke:
8452 switch (
II->getIntrinsicID()) {
8453 case Intrinsic::abs:
8457 case Intrinsic::umax:
8461 case Intrinsic::umin:
8465 case Intrinsic::smax:
8469 case Intrinsic::smin:
8473 case Intrinsic::usub_sat: {
8474 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8475 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8479 case Intrinsic::uadd_sat: {
8480 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8481 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8485 case Intrinsic::start_loop_iterations:
8486 case Intrinsic::annotation:
8487 case Intrinsic::ptr_annotation:
8491 case Intrinsic::vscale:
8511 auto *ExitCountType = ExitCount->
getType();
8512 assert(ExitCountType->isIntegerTy());
8514 1 + ExitCountType->getScalarSizeInBits());
8527 auto CanAddOneWithoutOverflow = [&]() {
8529 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8540 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8570 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8571 assert(L->isLoopExiting(ExitingBlock) &&
8572 "Exiting block must actually branch out of the loop!");
8581 const auto *MaxExitCount =
8589 L->getExitingBlocks(ExitingBlocks);
8591 std::optional<unsigned> Res;
8592 for (
auto *ExitingBB : ExitingBlocks) {
8596 Res = std::gcd(*Res, Multiple);
8598 return Res.value_or(1);
8602 const SCEV *ExitCount) {
8632 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8633 assert(L->isLoopExiting(ExitingBlock) &&
8634 "Exiting block must actually branch out of the loop!");
8644 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8646 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8648 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8658 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8661 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8664 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8672 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8679 return getBackedgeTakenInfo(L).getExact(L,
this);
8681 return getBackedgeTakenInfo(L).getConstantMax(
this);
8683 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8690 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8695 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8699 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8702ScalarEvolution::BackedgeTakenInfo &
8703ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8704 auto &BTI = getBackedgeTakenInfo(L);
8705 if (BTI.hasFullInfo())
8708 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8711 return Pair.first->second;
8713 BackedgeTakenInfo Result =
8714 computeBackedgeTakenCount(L,
true);
8716 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8719ScalarEvolution::BackedgeTakenInfo &
8720ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8726 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8727 BackedgeTakenCounts.try_emplace(L);
8729 return Pair.first->second;
8734 BackedgeTakenInfo Result = computeBackedgeTakenCount(L);
8741 if (Result.hasAnyInfo()) {
8744 auto LoopUsersIt = LoopUsers.find(L);
8745 if (LoopUsersIt != LoopUsers.end())
8747 forgetMemoizedResults(ToForget);
8750 for (
PHINode &PN : L->getHeader()->phis())
8751 ConstantEvolutionLoopExitValue.erase(&PN);
8759 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8768 BackedgeTakenCounts.clear();
8769 PredicatedBackedgeTakenCounts.clear();
8770 BECountUsers.clear();
8771 LoopPropertiesCache.clear();
8772 ConstantEvolutionLoopExitValue.clear();
8773 ValueExprMap.clear();
8774 ValuesAtScopes.clear();
8775 ValuesAtScopesUsers.clear();
8776 LoopDispositions.clear();
8777 BlockDispositions.clear();
8778 UnsignedRanges.clear();
8779 SignedRanges.clear();
8780 ExprValueMap.clear();
8782 ConstantMultipleCache.clear();
8783 PredicatedSCEVRewrites.clear();
8785 FoldCacheUser.clear();
8787void ScalarEvolution::visitAndClearUsers(
8791 while (!Worklist.
empty()) {
8798 if (It != ValueExprMap.
end()) {
8800 eraseValueFromMap(It->first);
8802 ConstantEvolutionLoopExitValue.erase(PN);
8814 while (!LoopWorklist.
empty()) {
8818 forgetBackedgeTakenCounts(CurrL,
false);
8819 forgetBackedgeTakenCounts(CurrL,
true);
8822 PredicatedSCEVRewrites.remove_if(
8823 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8825 auto LoopUsersItr = LoopUsers.find(CurrL);
8826 if (LoopUsersItr != LoopUsers.end())
8830 for (
PHINode &PN : CurrL->getHeader()->phis()) {
8831 ConstantEvolutionLoopExitValue.erase(&PN);
8832 auto VIt = ValueExprMap.find_as(
static_cast<Value *
>(&PN));
8833 if (VIt != ValueExprMap.end())
8837 LoopPropertiesCache.erase(CurrL);
8840 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8842 forgetMemoizedResults(ToForget);
8859 visitAndClearUsers(Worklist, Visited, ToForget);
8861 forgetMemoizedResults(ToForget);
8873 struct InvalidationRootCollector {
8877 InvalidationRootCollector(
Loop *L) : L(L) {}
8879 bool follow(
const SCEV *S) {
8885 if (L->contains(AddRec->
getLoop()))
8890 bool isDone()
const {
return false; }
8893 InvalidationRootCollector
C(L);
8895 forgetMemoizedResults(
C.Roots);
8908 BlockDispositions.clear();
8909 LoopDispositions.clear();
8926 while (!Worklist.
empty()) {
8928 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8929 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8930 if (!LoopDispoRemoved && !BlockDispoRemoved)
8932 auto Users = SCEVUsers.find(Curr);
8933 if (
Users != SCEVUsers.end())
8946const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8950 if (!isComplete() || ExitNotTaken.
empty())
8961 for (
const auto &ENT : ExitNotTaken) {
8962 const SCEV *BECount = ENT.ExactNotTaken;
8965 "We should only have known counts for exiting blocks that dominate "
8968 Ops.push_back(BECount);
8973 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8974 "Predicate should be always true!");
8983const ScalarEvolution::ExitNotTakenInfo *
8984ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8985 const BasicBlock *ExitingBlock,
8986 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8987 for (
const auto &ENT : ExitNotTaken)
8988 if (ENT.ExitingBlock == ExitingBlock) {
8989 if (ENT.hasAlwaysTruePredicate())
8991 else if (Predicates) {
9001const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
9003 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
9004 if (!getConstantMax())
9007 for (
const auto &ENT : ExitNotTaken)
9008 if (!ENT.hasAlwaysTruePredicate()) {
9016 "No point in having a non-constant max backedge taken count!");
9017 return getConstantMax();
9020const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
9022 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
9030 for (
const auto &ENT : ExitNotTaken) {
9031 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
9034 "We should only have known counts for exiting blocks that "
9040 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
9041 "Predicate should be always true!");
9044 if (ExitCounts.
empty())
9053bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
9055 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
9056 return !ENT.hasAlwaysTruePredicate();
9058 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
9074 this->ExactNotTaken = E = ConstantMaxNotTaken;
9075 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
9080 "Exact is not allowed to be less precise than Constant Max");
9083 "Exact is not allowed to be less precise than Symbolic Max");
9086 "Symbolic Max is not allowed to be less precise than Constant Max");
9089 "No point in having a non-constant max backedge taken count!");
9091 for (
const auto PredList : PredLists)
9092 for (
const auto *
P : PredList) {
9100 "Backedge count should be int");
9103 "Max backedge count should be int");
9116ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
9118 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
9119 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
9120 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9122 ExitNotTaken.reserve(ExitCounts.
size());
9123 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
9124 std::back_inserter(ExitNotTaken),
9125 [&](
const EdgeExitInfo &EEI) {
9126 BasicBlock *ExitBB = EEI.first;
9127 const ExitLimit &EL = EEI.second;
9128 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
9129 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
9134 "No point in having a non-constant max backedge taken count!");
9138ScalarEvolution::BackedgeTakenInfo
9139ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
9140 bool AllowPredicates) {
9142 L->getExitingBlocks(ExitingBlocks);
9144 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9147 bool CouldComputeBECount =
true;
9149 const SCEV *MustExitMaxBECount =
nullptr;
9150 const SCEV *MayExitMaxBECount =
nullptr;
9151 bool MustExitMaxOrZero =
false;
9152 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9163 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9164 if (ExitIfTrue == CI->
isZero())
9168 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9170 assert((AllowPredicates || EL.Predicates.empty()) &&
9171 "Predicated exit limit when predicates are not allowed!");
9176 ++NumExitCountsComputed;
9180 CouldComputeBECount =
false;
9187 "Exact is known but symbolic isn't?");
9188 ++NumExitCountsNotComputed;
9203 DT.dominates(ExitBB, Latch)) {
9204 if (!MustExitMaxBECount) {
9205 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9206 MustExitMaxOrZero = EL.MaxOrZero;
9209 EL.ConstantMaxNotTaken);
9213 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9216 EL.ConstantMaxNotTaken);
9220 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9224 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9230 for (
const auto &Pair : ExitCounts) {
9232 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9234 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9235 {
L, AllowPredicates});
9237 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9238 MaxBECount, MaxOrZero);
9241ScalarEvolution::ExitLimit
9242ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9243 bool IsOnlyExit,
bool AllowPredicates) {
9244 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9248 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9253 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9254 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9255 "It should have one successor in loop and one exit block!");
9266 if (!
L->contains(SBB)) {
9271 assert(Exit &&
"Exiting block must have at least one exit");
9272 return computeExitLimitFromSingleExitSwitch(
9273 L, SI, Exit, IsOnlyExit);
9280 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9281 bool AllowPredicates) {
9282 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9283 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9284 ControlsOnlyExit, AllowPredicates);
9287std::optional<ScalarEvolution::ExitLimit>
9288ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9289 bool ExitIfTrue,
bool ControlsOnlyExit,
9290 bool AllowPredicates) {
9292 (void)this->ExitIfTrue;
9293 (void)this->AllowPredicates;
9295 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9296 this->AllowPredicates == AllowPredicates &&
9297 "Variance in assumed invariant key components!");
9298 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9299 if (Itr == TripCountMap.end())
9300 return std::nullopt;
9304void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9306 bool ControlsOnlyExit,
9307 bool AllowPredicates,
9309 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9310 this->AllowPredicates == AllowPredicates &&
9311 "Variance in assumed invariant key components!");
9313 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9314 assert(InsertResult.second &&
"Expected successful insertion!");
9319ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9320 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9321 bool ControlsOnlyExit,
bool AllowPredicates) {
9323 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9327 ExitLimit EL = computeExitLimitFromCondImpl(
9328 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9329 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9333ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9334 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9335 bool ControlsOnlyExit,
bool AllowPredicates) {
9337 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9338 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9339 return *LimitFromBinOp;
9345 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9346 if (EL.hasFullInfo() || !AllowPredicates)
9350 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9370 const WithOverflowInst *WO;
9385 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9386 ControlsOnlyExit, AllowPredicates);
9387 if (EL.hasAnyInfo())
9392 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9395std::optional<ScalarEvolution::ExitLimit>
9396ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9400 bool AllowPredicates) {
9409 return std::nullopt;
9413 ExitLimit EL0 = computeExitLimitFromCondCached(
9414 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9415 ExitLimit EL1 = computeExitLimitFromCondCached(
9416 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9421 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9426 if (EitherMayExit) {
9436 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9438 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9441 EL1.ConstantMaxNotTaken);
9443 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9445 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9448 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9452 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9453 BECount = EL0.ExactNotTaken;
9466 SymbolicMaxBECount =
9468 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9472ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9473 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9474 bool AllowPredicates) {
9486 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9488 if (EL.hasAnyInfo())
9491 auto *ExhaustiveCount =
9492 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9495 return ExhaustiveCount;
9497 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9500ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9502 bool ControlsOnlyExit,
bool AllowPredicates) {
9527 ConstantRange CompRange =
9545 InnerLHS = ZExt->getOperand();
9592 if (EL.hasAnyInfo())
9609 if (EL.hasAnyInfo())
return EL;
9641 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9643 if (EL.hasAnyInfo())
9659 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9661 if (EL.hasAnyInfo())
9672ScalarEvolution::ExitLimit
9673ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9675 BasicBlock *ExitingBlock,
9676 bool ControlsOnlyExit) {
9677 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9680 if (
Switch->getDefaultDest() == ExitingBlock)
9684 "Default case must not exit the loop!");
9690 if (EL.hasAnyInfo())
9702 "Evaluation of SCEV at constant didn't fold correctly?");
9706ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9716 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9723 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9725 unsigned &OutShiftAmt) {
9726 using namespace PatternMatch;
9728 ConstantInt *ShiftAmt;
9730 OutOpCode = Instruction::LShr;
9732 OutOpCode = Instruction::AShr;
9734 OutOpCode = Instruction::Shl;
9739 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9754 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9756 unsigned &ShiftAmtOut) {
9757 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9773 if (MatchPositiveShift(
LHS, V, OpC, Amt)) {
9774 PostShiftOpCode = OpC;
9780 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9783 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9789 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9796 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9802 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9814 ConstantInt *StableValue =
nullptr;
9819 case Instruction::AShr: {
9826 if (
Known.isNonNegative())
9827 StableValue = ConstantInt::get(Ty, 0);
9828 else if (
Known.isNegative())
9829 StableValue = ConstantInt::get(Ty, -1,
true);
9835 case Instruction::LShr:
9836 case Instruction::Shl:
9846 "Otherwise cannot be an operand to a branch instruction");
9848 if (
Result->isNullValue()) {
9857 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9859 const SCEV *StartSCEV =
getSCEV(StartValue);
9863 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9864 MaxBTC = std::min(MaxBTC, RangeBTC);
9868 const SCEV *UpperBound =
9885 if (
const Function *
F = CI->getCalledFunction())
9894 if (!L->contains(
I))
return false;
9899 return L->getHeader() ==
I->getParent();
9975 if (!
I)
return nullptr;
9988 std::vector<Constant*> Operands(
I->getNumOperands());
9990 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9994 if (!Operands[i])
return nullptr;
9999 if (!
C)
return nullptr;
10021 if (IncomingVal != CurrentVal) {
10024 IncomingVal = CurrentVal;
10028 return IncomingVal;
10036ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
10039 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
10048 DenseMap<Instruction *, Constant *> CurrentIterVals;
10050 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10056 for (PHINode &
PHI : Header->phis()) {
10058 CurrentIterVals[&
PHI] = StartCST;
10060 if (!CurrentIterVals.
count(PN))
10061 return RetVal =
nullptr;
10067 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
10070 unsigned IterationNum = 0;
10072 for (; ; ++IterationNum) {
10073 if (IterationNum == NumIterations)
10074 return RetVal = CurrentIterVals[PN];
10078 DenseMap<Instruction *, Constant *> NextIterVals;
10083 NextIterVals[PN] = NextPHI;
10085 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
10091 for (
const auto &
I : CurrentIterVals) {
10093 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
10098 for (
const auto &
I : PHIsToCompute) {
10099 PHINode *
PHI =
I.first;
10102 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10105 if (NextPHI !=
I.second)
10106 StoppedEvolving =
false;
10111 if (StoppedEvolving)
10112 return RetVal = CurrentIterVals[PN];
10114 CurrentIterVals.swap(NextIterVals);
10118const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
10128 DenseMap<Instruction *, Constant *> CurrentIterVals;
10130 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10133 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
10135 for (PHINode &
PHI : Header->phis()) {
10137 CurrentIterVals[&
PHI] = StartCST;
10139 if (!CurrentIterVals.
count(PN))
10147 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10154 if (CondVal->getValue() == uint64_t(ExitWhen)) {
10155 ++NumBruteForceTripCountsComputed;
10160 DenseMap<Instruction *, Constant *> NextIterVals;
10166 for (
const auto &
I : CurrentIterVals) {
10168 if (!
PHI ||
PHI->getParent() != Header)
continue;
10171 for (PHINode *
PHI : PHIsToCompute) {
10173 if (NextPHI)
continue;
10175 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10178 CurrentIterVals.
swap(NextIterVals);
10191 return LS.second ? LS.second : V;
10193 Values.emplace_back(L,
nullptr);
10196 const SCEV *
C = computeSCEVAtScope(V, L);
10197 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10198 if (LS.first == L) {
10201 ValuesAtScopesUsers[
C].push_back({L, V});
10212 switch (V->getSCEVType()) {
10252 assert(!
C->getType()->isPointerTy() &&
10253 "Can only have one pointer, and it must be last");
10278const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10279 SmallVectorImpl<SCEVUse> &NewOps) {
10314const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10315 switch (
V->getSCEVType()) {
10326 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10337 for (++i; i !=
e; ++i)
10382 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10392 for (++i; i !=
e; ++i) {
10397 return getWithOperands(V, NewOps);
10412 const Loop *CurrLoop = this->LI[
I->getParent()];
10423 if (BackedgeTakenCount->
isZero()) {
10424 Value *InitValue =
nullptr;
10425 bool MultipleInitValues =
false;
10431 MultipleInitValues =
true;
10436 if (!MultipleInitValues && InitValue)
10445 unsigned InLoopPred =
10456 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10470 SmallVector<Constant *, 4> Operands;
10471 Operands.
reserve(
I->getNumOperands());
10472 bool MadeImprovement =
false;
10487 MadeImprovement |= OrigV != OpV;
10492 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10497 if (!MadeImprovement)
10518const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10520 return stripInjectiveFunctions(ZExt->getOperand());
10522 return stripInjectiveFunctions(SExt->getOperand());
10540 assert(
A != 0 &&
"A must be non-zero.");
10556 if (MinTZ < Mult2 && L->getLoopPredecessor())
10558 if (MinTZ < Mult2) {
10581 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10601static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10607 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10608 << *AddRec <<
'\n');
10611 if (!LC || !MC || !
NC) {
10612 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10613 return std::nullopt;
10619 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10627 N =
N.sext(NewWidth);
10628 M = M.sext(NewWidth);
10629 L = L.sext(NewWidth);
10646 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10647 <<
", multiplied by " <<
T <<
'\n');
10656 std::optional<APInt>
Y) {
10658 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10661 return XW.
slt(YW) ? *
X : *
Y;
10664 return std::nullopt;
10665 return X ? *
X : *
Y;
10682 return std::nullopt;
10683 unsigned W =
X->getBitWidth();
10703static std::optional<APInt>
10709 return std::nullopt;
10712 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10713 std::optional<APInt>
X =
10716 return std::nullopt;
10721 return std::nullopt;
10736static std::optional<APInt>
10740 "Starting value of addrec should be 0");
10741 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10742 <<
Range <<
", addrec " << *AddRec <<
'\n');
10746 "Addrec's initial value should be in range");
10752 return std::nullopt;
10762 auto SolveForBoundary =
10763 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10766 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10767 << Bound <<
" (before multiplying by " << M <<
")\n");
10770 std::optional<APInt> SO;
10773 "signed overflow\n");
10777 "unsigned overflow\n");
10778 std::optional<APInt> UO =
10781 auto LeavesRange = [&] (
const APInt &
X) {
10789 if (
Range.contains(
V1->getValue()))
10798 return {std::nullopt,
false};
10803 if (LeavesRange(*Min))
10804 return { Min,
true };
10805 std::optional<APInt> Max = Min == SO ? UO : SO;
10806 if (LeavesRange(*Max))
10807 return { Max,
true };
10810 return {std::nullopt,
true};
10817 auto SL = SolveForBoundary(
Lower);
10818 auto SU = SolveForBoundary(
Upper);
10821 if (!SL.second || !SU.second)
10822 return std::nullopt;
10865ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10867 bool ControlsOnlyExit,
10868 bool AllowPredicates) {
10879 if (
C->getValue()->isZero())
return C;
10883 const SCEVAddRecExpr *AddRec =
10886 if (!AddRec && AllowPredicates)
10892 if (!AddRec || AddRec->
getLoop() != L)
10903 return ExitLimit(R, R, R,
false, Predicates);
10961 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10987 const SCEV *
Exact =
10995 const SCEV *SymbolicMax =
10997 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
11006 AllowPredicates ? &Predicates :
nullptr, *
this, L);
11014 return ExitLimit(
E, M, S,
false, Predicates);
11017ScalarEvolution::ExitLimit
11018ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
11026 if (!
C->getValue()->isZero())
11036std::pair<const BasicBlock *, const BasicBlock *>
11037ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
11048 if (
const Loop *L = LI.getLoopFor(BB))
11049 return {
L->getLoopPredecessor(),
L->getHeader()};
11051 return {
nullptr, BB};
11060 if (
A ==
B)
return true;
11075 if (ComputesEqualValues(AI, BI))
11083 const SCEV *Op0, *Op1;
11102 auto TrivialCase = [&](
bool TriviallyTrue) {
11111 const SCEV *NewLHS, *NewRHS;
11135 return TrivialCase(
false);
11136 return TrivialCase(
true);
11155 RAdd->hasNoSignedWrap()) ||
11157 RAdd->hasNoUnsignedWrap())) {
11177 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
11178 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
11181 C->getAPInt().isStrictlyPositive()) ||
11205 const APInt &
RA = RC->getAPInt();
11207 bool SimplifiedByConstantRange =
false;
11212 return TrivialCase(
true);
11214 return TrivialCase(
false);
11223 Changed = SimplifiedByConstantRange =
true;
11227 if (!SimplifiedByConstantRange) {
11244 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11250 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11256 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11262 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11274 return TrivialCase(
true);
11276 return TrivialCase(
false);
11381 auto NonRecursive = [OrNegative](
const SCEV *S) {
11383 return C->getAPInt().isPowerOf2() ||
11384 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11390 if (NonRecursive(S))
11416 APInt C = Cst->getAPInt();
11417 return C.urem(M) == 0;
11425 const SCEV *SmodM =
11440 for (
auto *
A : Assumptions)
11441 if (
A->implies(
P, *
this))
11454std::pair<const SCEV *, const SCEV *>
11457 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11459 return { Start, Start };
11461 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11470 getUsedLoops(LHS, LoopsUsed);
11471 getUsedLoops(RHS, LoopsUsed);
11473 if (LoopsUsed.
empty())
11478 for (
const auto *L1 : LoopsUsed)
11479 for (
const auto *L2 : LoopsUsed)
11480 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11481 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11482 "Domination relationship is not a linear order");
11512 SplitRHS.second) &&
11524 if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
11528 return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11538 return std::nullopt;
11553 if (KnownWithoutContext)
11554 return KnownWithoutContext;
11561 return std::nullopt;
11567 const Loop *L = LHS->getLoop();
11572std::optional<ScalarEvolution::MonotonicPredicateType>
11575 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11581 auto ResultSwapped =
11584 assert(*ResultSwapped != *Result &&
11585 "monotonicity should flip as we flip the predicate");
11592std::optional<ScalarEvolution::MonotonicPredicateType>
11593ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11607 return std::nullopt;
11611 "Should be greater or less!");
11615 if (!LHS->hasNoUnsignedWrap())
11616 return std::nullopt;
11620 "Relational predicate is either signed or unsigned!");
11621 if (!
LHS->hasNoSignedWrap())
11622 return std::nullopt;
11624 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11632 return std::nullopt;
11635std::optional<ScalarEvolution::LoopInvariantPredicate>
11642 return std::nullopt;
11649 if (!ArLHS || ArLHS->
getLoop() != L)
11650 return std::nullopt;
11654 return std::nullopt;
11680 return std::nullopt;
11717 return std::nullopt;
11720std::optional<ScalarEvolution::LoopInvariantPredicate>
11725 Pred, LHS, RHS, L, CtxI, MaxIter))
11735 Pred, LHS, RHS, L, CtxI,
Op))
11737 return std::nullopt;
11740std::optional<ScalarEvolution::LoopInvariantPredicate>
11755 return std::nullopt;
11762 if (!AR || AR->
getLoop() != L)
11763 return std::nullopt;
11768 Pred = Pred.dropSameSign();
11772 return std::nullopt;
11778 if (Step != One && Step != MinusOne)
11779 return std::nullopt;
11785 return std::nullopt;
11791 return std::nullopt;
11799 if (Step == MinusOne)
11803 return std::nullopt;
11809bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11815 auto CheckRange = [&](
bool IsSigned) {
11818 return RangeLHS.
icmp(Pred, RangeRHS);
11827 if (CheckRange(
true) || CheckRange(
false))
11836bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11845 SCEVUse XNonConstOp, XConstOp;
11846 SCEVUse YNonConstOp, YConstOp;
11850 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11853 XFlagsPresent = ExpectedFlags;
11858 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11861 YFlagsPresent = ExpectedFlags;
11864 if (YNonConstOp != XNonConstOp)
11872 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11875 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11935bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11956bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11957 const SCEV *
LHS,
const SCEV *
RHS) {
11962 return any_of(*BB, [&](
const Instruction &
I) {
11963 using namespace llvm::PatternMatch;
11968 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11982 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11987 "This cannot be done on broken IR!");
11990 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11999 if (LoopContinuePredicate &&
12000 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
12001 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
12006 if (WalkingBEDominatingConds)
12012 const auto &BETakenInfo = getBackedgeTakenInfo(L);
12013 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
12020 const SCEV *LoopCounter =
12028 for (
auto &AssumeVH : AC.assumptions()) {
12035 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
12039 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
12042 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
12043 DTN != HeaderDTN; DTN = DTN->getIDom()) {
12044 assert(DTN &&
"should reach the loop header before reaching the root!");
12047 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
12065 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
12078 if (!DT.isReachableFromEntry(BB))
12082 "This cannot be done on broken IR!");
12090 const bool ProvingStrictComparison =
12092 bool ProvedNonStrictComparison =
false;
12093 bool ProvedNonEquality =
false;
12096 if (!ProvedNonStrictComparison)
12097 ProvedNonStrictComparison = Fn(NonStrictPredicate);
12098 if (!ProvedNonEquality)
12100 if (ProvedNonStrictComparison && ProvedNonEquality)
12105 if (ProvingStrictComparison) {
12107 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
12109 if (SplitAndProve(ProofFn))
12114 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
12116 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
12118 if (ProvingStrictComparison) {
12120 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
12122 if (SplitAndProve(ProofFn))
12131 const Loop *ContainingLoop = LI.getLoopFor(BB);
12133 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
12137 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
12138 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
12141 if (!BlockEntryPredicate)
12150 for (
auto &AssumeVH : AC.assumptions()) {
12154 if (!DT.dominates(CI, BB))
12157 if (ProveViaCond(CI->getArgOperand(0),
false))
12163 F.getParent(), Intrinsic::experimental_guard);
12165 for (
const auto *GU : GuardDecl->users())
12167 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12168 if (ProveViaCond(Guard->getArgOperand(0),
false))
12183 "LHS is not available at Loop Entry");
12185 "RHS is not available at Loop Entry");
12187 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12198 if (FoundCondValue ==
12202 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12206 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12209 const Value *Op0, *Op1;
12212 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12216 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12217 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12221 if (!ICI)
return false;
12225 CmpPredicate FoundPred;
12234 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12237bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12238 const SCEV *
RHS, CmpPredicate FoundPred,
12239 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12240 const Instruction *CtxI) {
12250 auto *WideType = FoundLHS->
getType();
12262 TruncFoundLHS, TruncFoundRHS, CtxI))
12288 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12292bool ScalarEvolution::isImpliedCondBalancedTypes(
12297 "Types should be balanced!");
12304 if (FoundLHS == FoundRHS)
12308 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12320 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12337 LHS, FoundLHS, FoundRHS, CtxI);
12339 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12361 assert(P1 != P2 &&
"Handled earlier!");
12365 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12369 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12372 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12373 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12374 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12379 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12390 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12391 CanonicalRHS, CanonicalFoundLHS,
12392 CanonicalFoundRHS);
12397 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12398 CanonicalRHS, CanonicalFoundLHS,
12399 CanonicalFoundRHS);
12406 const SCEVConstant *
C =
nullptr;
12407 const SCEV *
V =
nullptr;
12425 if (Min ==
C->getAPInt()) {
12430 APInt SharperMin = Min + 1;
12433 case ICmpInst::ICMP_SGE:
12434 case ICmpInst::ICMP_UGE:
12437 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12442 case ICmpInst::ICMP_SGT:
12443 case ICmpInst::ICMP_UGT:
12453 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12458 case ICmpInst::ICMP_SLE:
12459 case ICmpInst::ICMP_ULE:
12460 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12461 LHS, V, getConstant(SharperMin), CtxI))
12465 case ICmpInst::ICMP_SLT:
12466 case ICmpInst::ICMP_ULT:
12467 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12468 LHS, V, getConstant(Min), CtxI))
12482 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12486 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12489 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12505std::optional<APInt>
12512 APInt DiffMul(BW, 1);
12515 for (
unsigned I = 0;
I < 8; ++
I) {
12524 if (LAR->getLoop() != MAR->getLoop())
12525 return std::nullopt;
12529 if (!LAR->isAffine() || !MAR->isAffine())
12530 return std::nullopt;
12532 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12533 return std::nullopt;
12535 Less = LAR->getStart();
12536 More = MAR->getStart();
12541 auto MatchConstMul =
12542 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12547 return std::nullopt;
12549 if (
auto MatchedMore = MatchConstMul(More)) {
12550 if (
auto MatchedLess = MatchConstMul(
Less)) {
12551 if (MatchedMore->second == MatchedLess->second) {
12552 More = MatchedMore->first;
12553 Less = MatchedLess->first;
12554 DiffMul *= MatchedMore->second;
12565 Diff +=
C->getAPInt() * DiffMul;
12568 Diff -=
C->getAPInt() * DiffMul;
12571 Multiplicity[S] +=
Mul;
12573 auto Decompose = [&](
const SCEV *S,
int Mul) {
12580 Decompose(More, 1);
12581 Decompose(
Less, -1);
12585 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12586 for (
const auto &[S,
Mul] : Multiplicity) {
12591 return std::nullopt;
12593 }
else if (
Mul == -1) {
12595 return std::nullopt;
12598 return std::nullopt;
12602 if (NewMore == More || NewLess ==
Less)
12603 return std::nullopt;
12609 if (!More && !
Less)
12613 if (!More || !
Less)
12614 return std::nullopt;
12618 return std::nullopt;
12621bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12643 const auto *Latch = L->getLoopLatch();
12646 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12655 const auto *Latch = L->getLoopLatch();
12658 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12668bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12671 const SCEV *FoundLHS,
12672 const SCEV *FoundRHS) {
12681 if (!AddRecFoundLHS)
12688 const Loop *
L = AddRecFoundLHS->getLoop();
12689 if (L != AddRecLHS->getLoop())
12728 if (!RDiff || *LDiff != *RDiff)
12731 if (LDiff->isMinValue())
12734 APInt FoundRHSLimit;
12737 FoundRHSLimit = -(*RDiff);
12749bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12750 const SCEV *
RHS,
const SCEV *FoundLHS,
12751 const SCEV *FoundRHS,
unsigned Depth) {
12752 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12756 bool Erased = PendingMerges.erase(LPhi);
12757 assert(Erased &&
"Failed to erase LPhi!");
12761 bool Erased = PendingMerges.erase(RPhi);
12762 assert(Erased &&
"Failed to erase RPhi!");
12770 if (!PendingMerges.insert(Phi).second)
12784 if (!PendingMerges.insert(Phi).second)
12790 if (!LPhi && !RPhi)
12801 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12805 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12806 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12807 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12808 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12811 if (RPhi && RPhi->getParent() == LBB) {
12818 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12819 if (!ProvedEasily(L, R))
12830 auto *RLoop = RAR->
getLoop();
12831 auto *Predecessor = RLoop->getLoopPredecessor();
12832 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12834 if (!ProvedEasily(L1, RAR->
getStart()))
12836 auto *Latch = RLoop->getLoopLatch();
12837 assert(Latch &&
"Loop with AddRec with no latch?");
12858 if (
auto *Loop = LI.getLoopFor(LBB))
12861 if (!ProvedEasily(L,
RHS))
12868bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12871 const SCEV *FoundLHS,
12872 const SCEV *FoundRHS) {
12875 if (
RHS == FoundRHS) {
12880 if (
LHS != FoundLHS)
12887 Value *Shiftee, *ShiftValue;
12889 using namespace PatternMatch;
12890 if (
match(SUFoundRHS->getValue(),
12892 auto *ShifteeS =
getSCEV(Shiftee);
12910bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12911 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12912 const SCEV *FoundRHS) {
12944 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12952 return Diff == FoundDiff;
12955bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12957 const SCEV *FoundLHS,
12958 const SCEV *FoundRHS,
12959 const Instruction *CtxI) {
12960 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12962 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12964 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12965 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12967 isImpliedCondOperandsViaMatchingDiff(Pred,
LHS,
RHS, FoundLHS,
12969 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12973template <
typename MinMaxExprType>
12975 const SCEV *Candidate) {
12980 return is_contained(MinMaxExpr->operands(), Candidate);
12993 const SCEV *LStart, *RStart, *Step;
13066bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
13068 const SCEV *FoundLHS,
13069 const SCEV *FoundRHS,
13073 "LHS and RHS have different sizes?");
13076 "FoundLHS and FoundRHS have different sizes?");
13110 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
13112 return Ext->getOperand();
13119 auto *OrigLHS =
LHS;
13120 auto *OrigFoundLHS = FoundLHS;
13121 LHS = GetOpFromSExt(
LHS);
13122 FoundLHS = GetOpFromSExt(FoundLHS);
13125 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
13128 FoundRHS,
Depth + 1);
13141 if (!LHSAddExpr->hasNoSignedWrap())
13144 SCEVUse LL = LHSAddExpr->getOperand(0);
13145 SCEVUse LR = LHSAddExpr->getOperand(1);
13149 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
13150 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
13155 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
13161 using namespace llvm::PatternMatch;
13180 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13188 auto *DTy = Denominator->getType();
13189 auto *FRHSTy = FoundRHS->
getType();
13190 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13209 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13220 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13222 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13230 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13263bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13267 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13270 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13273bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13276 const SCEV *FoundLHS,
13277 const SCEV *FoundRHS) {
13313 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13319bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13320 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13321 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13335 ConstantRange FoundLHSRange =
13339 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13346 return LHSRange.
icmp(Pred, ConstRHS);
13349bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13362 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13370 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13373bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
13385 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
13393 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
13405const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
13406 const SCEV *Stride,
13437 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13448 :
APIntOps::umax(MaxEnd, MinStart);
13455ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13456 const Loop *L,
bool IsSigned,
13457 bool ControlsOnlyExit,
bool AllowPredicates) {
13461 bool PredicatedIV =
false;
13466 auto canProveNUW = [&]() {
13469 if (!ControlsOnlyExit)
13490 Limit = Limit.
zext(OuterBitWidth);
13502 Type *Ty = ZExt->getType();
13513 if (!
IV && AllowPredicates) {
13518 PredicatedIV =
true;
13522 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13536 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13539 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13544 if (!PositiveStride) {
13596 auto wouldZeroStrideBeUB = [&]() {
13608 if (!wouldZeroStrideBeUB()) {
13612 }
else if (!NoWrap) {
13615 if (canIVOverflowOnLT(
RHS, Stride, IsSigned))
13628 const SCEV *
Start =
IV->getStart();
13634 const SCEV *OrigStart =
Start;
13635 const SCEV *OrigRHS =
RHS;
13636 if (
Start->getType()->isPointerTy()) {
13647 const SCEV *End =
nullptr, *BECount =
nullptr,
13648 *BECountIfBackedgeTaken =
nullptr;
13651 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13652 any(RHSAddRec->getNoWrapFlags())) {
13665 const SCEV *RHSStart = RHSAddRec->getStart();
13666 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13678 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13687 BECountIfBackedgeTaken =
13692 if (BECount ==
nullptr) {
13697 const SCEV *MaxBECount = computeMaxBECountForLT(
13700 MaxBECount,
false , Predicates);
13707 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13734 const SCEV *Numerator =
13740 auto canProveRHSGreaterThanEqualStart = [&]() {
13759 auto *StartMinusOne =
13766 if (canProveRHSGreaterThanEqualStart()) {
13781 BECountIfBackedgeTaken =
13797 bool MayAddOverflow = [&] {
13843 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13857 if (!MayAddOverflow) {
13869 const SCEV *ConstantMaxBECount;
13870 bool MaxOrZero =
false;
13872 ConstantMaxBECount = BECount;
13873 }
else if (BECountIfBackedgeTaken &&
13878 ConstantMaxBECount = BECountIfBackedgeTaken;
13881 ConstantMaxBECount = computeMaxBECountForLT(
13889 const SCEV *SymbolicMaxBECount =
13891 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13895ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13896 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13897 bool ControlsOnlyExit,
bool AllowPredicates) {
13904 if (!
IV && AllowPredicates)
13911 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13915 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13928 if (!Stride->
isOne() && !NoWrap)
13929 if (canIVOverflowOnGT(
RHS, Stride, IsSigned))
13932 const SCEV *
Start =
IV->getStart();
13933 const SCEV *End =
RHS;
13944 if (
Start->getType()->isPointerTy()) {
13979 const SCEV *ConstantMaxBECount =
13986 ConstantMaxBECount = BECount;
13987 const SCEV *SymbolicMaxBECount =
13990 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13996 if (
Range.isFullSet())
14001 if (!SC->getValue()->isZero()) {
14007 return ShiftedAddRec->getNumIterationsInRange(
14008 Range.subtract(SC->getAPInt()), SE);
14039 APInt ExitVal = (End +
A).udiv(
A);
14052 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
14053 "Linear scev computation is off in a bad way!");
14084 assert(!
Last->isZero() &&
"Recurrency with zero step?");
14110 Ty =
Store->getValueOperand()->getType();
14111 PtrTy =
Store->getPointerOperandType();
14113 Ty =
Load->getType();
14114 PtrTy =
Load->getPointerOperandType();
14128 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14130 SE->ConstantEvolutionLoopExitValue.erase(PN);
14131 SE->eraseValueFromMap(getValPtr());
14135void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
14136 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14146 : CallbackVH(
V), SE(se) {}
14155 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
14157 LoopDispositions(64), BlockDispositions(64) {
14169 F.getParent(), Intrinsic::experimental_guard);
14170 HasGuards = GuardDecl && !GuardDecl->use_empty();
14174 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
14175 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14176 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14177 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14178 PendingMerges(
std::
move(Arg.PendingMerges)),
14179 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14180 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14181 PredicatedBackedgeTakenCounts(
14182 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14183 BECountUsers(
std::
move(Arg.BECountUsers)),
14184 ConstantEvolutionLoopExitValue(
14185 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14186 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14187 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14188 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14189 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14190 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14191 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14192 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14193 SignedRanges(
std::
move(Arg.SignedRanges)),
14194 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14195 UniquePreds(
std::
move(Arg.UniquePreds)),
14196 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14197 ConstantSCEVs(
std::
move(Arg.ConstantSCEVs)),
14198 LoopUsers(
std::
move(Arg.LoopUsers)),
14199 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14200 FirstUnknown(Arg.FirstUnknown) {
14201 Arg.FirstUnknown =
nullptr;
14210 Tmp->~SCEVUnknown();
14212 FirstUnknown =
nullptr;
14214 ExprValueMap.clear();
14215 ValueExprMap.clear();
14217 BackedgeTakenCounts.clear();
14218 PredicatedBackedgeTakenCounts.clear();
14220 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14221 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14222 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14223 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14245 L->getHeader()->printAsOperand(OS,
false);
14249 L->getExitingBlocks(ExitingBlocks);
14250 if (ExitingBlocks.
size() != 1)
14251 OS <<
"<multiple exits> ";
14255 OS <<
"backedge-taken count is ";
14258 OS <<
"Unpredictable backedge-taken count.";
14261 if (ExitingBlocks.
size() > 1)
14262 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14263 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14271 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14274 OS <<
"\n Predicates:\n";
14275 for (
const auto *
P : Predicates)
14283 L->getHeader()->printAsOperand(OS,
false);
14288 OS <<
"constant max backedge-taken count is ";
14291 OS <<
", actual taken count either this or zero.";
14293 OS <<
"Unpredictable constant max backedge-taken count. ";
14298 L->getHeader()->printAsOperand(OS,
false);
14303 OS <<
"symbolic max backedge-taken count is ";
14306 OS <<
", actual taken count either this or zero.";
14308 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14312 if (ExitingBlocks.
size() > 1)
14313 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14314 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14324 OS <<
"\n predicated symbolic max exit count for "
14325 << ExitingBlock->
getName() <<
": ";
14327 OS <<
"\n Predicates:\n";
14328 for (
const auto *
P : Predicates)
14339 L->getHeader()->printAsOperand(OS,
false);
14342 OS <<
"Predicated backedge-taken count is ";
14345 OS <<
"Unpredictable predicated backedge-taken count.";
14347 OS <<
" Predicates:\n";
14348 for (
const auto *
P : Preds)
14353 auto *PredConstantMax =
14355 if (PredConstantMax != ConstantBTC) {
14357 L->getHeader()->printAsOperand(OS,
false);
14360 OS <<
"Predicated constant max backedge-taken count is ";
14363 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14365 OS <<
" Predicates:\n";
14366 for (
const auto *
P : Preds)
14371 auto *PredSymbolicMax =
14373 if (SymbolicBTC != PredSymbolicMax) {
14375 L->getHeader()->printAsOperand(OS,
false);
14378 OS <<
"Predicated symbolic max backedge-taken count is ";
14381 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14383 OS <<
" Predicates:\n";
14384 for (
const auto *
P : Preds)
14390 L->getHeader()->printAsOperand(OS,
false);
14417 OS <<
"Computable";
14427 OS <<
"DoesNotDominate";
14433 OS <<
"ProperlyDominates";
14450 OS <<
"Classifying expressions for: ";
14451 F.printAsOperand(OS,
false);
14466 const Loop *L = LI.getLoopFor(
I.getParent());
14481 OS <<
"\t\t" "Exits: ";
14484 OS <<
"<<Unknown>>";
14490 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14492 Iter->getHeader()->printAsOperand(OS,
false);
14500 InnerL->getHeader()->printAsOperand(OS,
false);
14511 OS <<
"Determining loop execution counts for: ";
14512 F.printAsOperand(OS,
false);
14520 auto &
Values = LoopDispositions[S];
14521 for (
auto &V :
Values) {
14522 if (V.getPointer() == L)
14527 auto &Values2 = LoopDispositions[S];
14529 if (V.getPointer() == L) {
14538ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14556 if (L->contains(AR->
getLoop()) &&
14558 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14563 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14564 " dominate the contained loop's header?");
14592 bool HasVarying =
false;
14593 bool HasUniform =
false;
14635 auto &
Values = BlockDispositions[S];
14636 for (
auto &V :
Values) {
14637 if (V.getPointer() == BB)
14642 auto &Values2 = BlockDispositions[S];
14644 if (V.getPointer() == BB) {
14653ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14683 bool Proper =
true;
14694 if (Instruction *
I =
14696 if (
I->getParent() == BB)
14698 if (DT.properlyDominates(
I->getParent(), BB))
14721void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14724 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14725 auto It = BECounts.find(L);
14726 if (It != BECounts.end()) {
14727 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14728 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14730 auto UserIt = BECountUsers.find(S);
14731 assert(UserIt != BECountUsers.end());
14736 BECounts.erase(It);
14744 while (!Worklist.
empty()) {
14746 auto Users = SCEVUsers.find(Curr);
14747 if (
Users != SCEVUsers.end())
14748 for (
const auto *User :
Users->second)
14749 if (ToForget.
insert(User).second)
14753 for (
const auto *S : ToForget)
14754 forgetMemoizedResultsImpl(S);
14756 PredicatedSCEVRewrites.remove_if(
14757 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14760void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14761 LoopDispositions.erase(S);
14762 BlockDispositions.erase(S);
14763 UnsignedRanges.erase(S);
14764 SignedRanges.erase(S);
14765 HasRecMap.erase(S);
14766 ConstantMultipleCache.erase(S);
14769 UnsignedWrapViaInductionTried.erase(AR);
14770 SignedWrapViaInductionTried.erase(AR);
14773 auto ExprIt = ExprValueMap.find(S);
14774 if (ExprIt != ExprValueMap.end()) {
14775 for (
Value *V : ExprIt->second) {
14776 auto ValueIt = ValueExprMap.find_as(V);
14777 if (ValueIt != ValueExprMap.end())
14778 ValueExprMap.erase(ValueIt);
14780 ExprValueMap.erase(ExprIt);
14783 auto ScopeIt = ValuesAtScopes.find(S);
14784 if (ScopeIt != ValuesAtScopes.end()) {
14785 for (
const auto &Pair : ScopeIt->second)
14788 std::make_pair(Pair.first, S));
14789 ValuesAtScopes.erase(ScopeIt);
14792 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14793 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14794 for (
const auto &Pair : ScopeUserIt->second)
14795 llvm::erase(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
14796 ValuesAtScopesUsers.erase(ScopeUserIt);
14799 auto BEUsersIt = BECountUsers.find(S);
14800 if (BEUsersIt != BECountUsers.end()) {
14802 auto Copy = BEUsersIt->second;
14803 for (
const auto &Pair : Copy)
14804 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14805 BECountUsers.erase(BEUsersIt);
14808 auto FoldUser = FoldCacheUser.find(S);
14809 if (FoldUser != FoldCacheUser.end())
14810 for (
auto &KV : FoldUser->second)
14811 FoldCache.erase(KV);
14812 FoldCacheUser.erase(S);
14816ScalarEvolution::getUsedLoops(
const SCEV *S,
14818 struct FindUsedLoops {
14819 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14820 : LoopsUsed(LoopsUsed) {}
14821 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14822 bool follow(
const SCEV *S) {
14828 bool isDone()
const {
return false; }
14831 FindUsedLoops
F(LoopsUsed);
14832 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14835void ScalarEvolution::getReachableBlocks(
14838 Worklist.
push_back(&F.getEntryBlock());
14839 while (!Worklist.
empty()) {
14841 if (!Reachable.
insert(BB).second)
14849 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14856 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14860 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14895 SCEVMapper SCM(SE2);
14897 SE2.getReachableBlocks(ReachableBlocks, F);
14899 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14917 while (!LoopStack.
empty()) {
14923 if (!ReachableBlocks.
contains(L->getHeader()))
14928 auto It = BackedgeTakenCounts.find(L);
14929 if (It == BackedgeTakenCounts.end())
14933 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14953 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14954 if (Delta && !Delta->
isZero()) {
14955 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14956 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14957 dbgs() <<
"New: " << *NewBECount <<
"\n";
14958 dbgs() <<
"Delta: " << *Delta <<
"\n";
14966 while (!Worklist.
empty()) {
14968 if (ValidLoops.
insert(L).second)
14969 Worklist.
append(L->begin(), L->end());
14971 for (
const auto &KV : ValueExprMap) {
14976 "AddRec references invalid loop");
14981 auto It = ExprValueMap.find(KV.second);
14982 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14983 dbgs() <<
"Value " << *KV.first
14984 <<
" is in ValueExprMap but not in ExprValueMap\n";
14989 if (!ReachableBlocks.
contains(
I->getParent()))
14991 const SCEV *OldSCEV = SCM.visit(KV.second);
14993 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14994 if (Delta && !Delta->
isZero()) {
14995 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14996 <<
"Old: " << *OldSCEV <<
"\n"
14997 <<
"New: " << *NewSCEV <<
"\n"
14998 <<
"Delta: " << *Delta <<
"\n";
15004 for (
const auto &KV : ExprValueMap) {
15005 for (
Value *V : KV.second) {
15006 const SCEV *S = ValueExprMap.lookup(V);
15008 dbgs() <<
"Value " << *V
15009 <<
" is in ExprValueMap but not in ValueExprMap\n";
15012 if (S != KV.first) {
15013 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
15014 << *KV.first <<
"\n";
15021 for (
const auto &S : UniqueSCEVs) {
15026 auto It = SCEVUsers.find(
Op);
15027 if (It != SCEVUsers.end() && It->second.count(&S))
15029 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
15030 <<
" is not being tracked!\n";
15036 for (
const auto &ValueAndVec : ValuesAtScopes) {
15038 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
15039 const Loop *L = LoopAndValueAtScope.first;
15040 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
15042 auto It = ValuesAtScopesUsers.find(ValueAtScope);
15043 if (It != ValuesAtScopesUsers.end() &&
15046 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
15047 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
15053 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
15054 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
15055 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
15056 const Loop *L = LoopAndValue.first;
15057 const SCEV *
Value = LoopAndValue.second;
15059 auto It = ValuesAtScopes.find(
Value);
15060 if (It != ValuesAtScopes.end() &&
15061 is_contained(It->second, std::make_pair(L, ValueAtScope)))
15063 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
15064 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
15070 auto VerifyBECountUsers = [&](
bool Predicated) {
15072 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
15073 for (
const auto &LoopAndBEInfo : BECounts) {
15074 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
15075 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
15077 auto UserIt = BECountUsers.find(S);
15078 if (UserIt != BECountUsers.end() &&
15079 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
15081 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
15082 <<
" missing from BECountUsers\n";
15089 VerifyBECountUsers(
false);
15090 VerifyBECountUsers(
true);
15093 for (
auto &[S,
Values] : LoopDispositions) {
15094 for (
auto [
Loop, CachedDisposition] :
Values) {
15096 if (CachedDisposition != RecomputedDisposition) {
15097 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
15098 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
15099 << RecomputedDisposition <<
"\n";
15106 for (
auto &[S,
Values] : BlockDispositions) {
15107 for (
auto [BB, CachedDisposition] :
Values) {
15109 if (CachedDisposition != RecomputedDisposition) {
15110 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
15111 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
15112 <<
", actual " << RecomputedDisposition <<
"\n";
15119 for (
auto [
FoldID, Expr] : FoldCache) {
15120 auto I = FoldCacheUser.find(Expr);
15121 if (
I == FoldCacheUser.end()) {
15122 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
15127 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
15131 for (
auto [Expr, IDs] : FoldCacheUser) {
15132 for (
auto &
FoldID : IDs) {
15135 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
15140 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
15141 <<
" != " << *Expr <<
"!\n";
15152 for (
auto [S, Multiple] : ConstantMultipleCache) {
15154 if ((Multiple != 0 && RecomputedMultiple != 0 &&
15155 Multiple.
urem(RecomputedMultiple) != 0 &&
15156 RecomputedMultiple.
urem(Multiple) != 0)) {
15157 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
15158 << *S <<
" : Computed " << RecomputedMultiple
15159 <<
" but cache contains " << Multiple <<
"!\n";
15167 FunctionAnalysisManager::Invalidator &Inv) {
15199 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15200 <<
F.getName() <<
"':\n";
15206 "Scalar Evolution Analysis",
false,
true)
15255 const SCEV *LHS,
const SCEV *RHS) {
15257 assert(LHS->getType() == RHS->getType() &&
15258 "Type mismatch between LHS and RHS");
15261 ID.AddInteger(Pred);
15262 ID.AddPointer(LHS);
15263 ID.AddPointer(RHS);
15264 void *IP =
nullptr;
15265 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
15269 UniquePreds.InsertNode(Eq, IP);
15280 ID.AddInteger(AddedFlags);
15281 void *IP =
nullptr;
15282 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
15284 auto *OF =
new (SCEVAllocator)
15286 UniquePreds.InsertNode(OF, IP);
15306 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15307 return Rewriter.visit(S);
15313 for (
const auto *Pred : U->getPredicates())
15315 if (IPred->getLHS() == Expr &&
15317 return IPred->getRHS();
15319 if (IPred->getLHS() == Expr &&
15320 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15321 return IPred->getRHS();
15324 return convertToAddRecWithPreds(Expr);
15327 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15343 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15360 explicit SCEVPredicateRewriter(
15361 const Loop *L, ScalarEvolution &SE,
15362 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15363 const SCEVPredicate *Pred)
15364 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15366 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15369 return Pred && Pred->
implies(
P, SE);
15375 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15378 return addOverflowAssumption(
A);
15387 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15391 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15393 if (!PredicatedRewrite)
15395 for (
const auto *
P : PredicatedRewrite->second){
15398 if (L != WP->getExpr()->getLoop())
15401 if (!addOverflowAssumption(
P))
15404 return PredicatedRewrite->first;
15407 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15408 const SCEVPredicate *Pred;
15417 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15424 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15444 if (!Step->
isOne())
15469 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15470 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15483 return Op->LHS == LHS &&
Op->RHS == RHS;
15490 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15492 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15517 const SCEV *Start = AR->getStart();
15518 const SCEV *OpStart =
Op->AR->getStart();
15523 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15532 const SCEV *Step = AR->getStepRecurrence(SE);
15533 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15586 if (Step->getValue()->getValue().isNonNegative())
15590 return ImpliedFlags;
15597 for (
const auto *
P : Preds)
15610 return this->implies(I, SE);
15622 const Loop *L = NWrap->getExpr()->getLoop();
15629 return RewrittenAR &&
15635 for (
const auto *Pred : Preds)
15636 Pred->print(OS,
Depth);
15641 for (
const auto *Pred : Set->Preds)
15649 bool CheckImplies = Preds.
size() < 16;
15652 if (CheckImplies &&
implies(
N, SE))
15658 for (
auto *
P : Preds) {
15659 if (CheckImplies &&
N->implies(
P, SE))
15663 Preds = std::move(PrunedPreds);
15664 Preds.push_back(
N);
15671 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15676 for (
const auto *
Op :
Ops)
15681 SCEVUsers[
Op].insert(
User);
15690 SCEVUsers[
Op].insert(
User);
15694 const SCEV *Expr = SE.getSCEV(V);
15699 RewriteEntry &Entry = RewriteMap[Expr];
15702 if (Entry.second && Generation == Entry.first)
15703 return Entry.second;
15708 Expr = Entry.second;
15710 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15711 Entry = {Generation, NewSCEV};
15717 if (!BackedgeCount) {
15719 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15720 for (
const auto *
P : Preds)
15723 return BackedgeCount;
15727 if (!SymbolicMaxBackedgeCount) {
15729 SymbolicMaxBackedgeCount =
15730 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15731 for (
const auto *
P : Preds)
15734 return SymbolicMaxBackedgeCount;
15738 if (!SmallConstantMaxTripCount) {
15740 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15741 for (
const auto *
P : Preds)
15744 return *SmallConstantMaxTripCount;
15748 if (Preds->implies(&Pred, SE))
15753 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15754 updateGeneration();
15767void PredicatedScalarEvolution::updateGeneration() {
15769 if (++Generation == 0) {
15770 for (
auto &
II : RewriteMap) {
15771 const SCEV *Rewritten =
II.second.second;
15793 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15799 ExtraPreds->
append(NewPreds);
15805 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15811 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15814 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15818 for (
auto *BB : L.getBlocks())
15819 for (
auto &
I : *BB) {
15820 if (!SE.isSCEVable(
I.getType()))
15823 auto *Expr = SE.getSCEV(&
I);
15824 auto II = RewriteMap.find(Expr);
15826 if (
II == RewriteMap.end())
15830 if (
II->second.second == Expr)
15835 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15843 LoopGuards Guards(SE);
15851void ScalarEvolution::LoopGuards::collectFromPHI(
15859 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15860 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15874 auto &RewriteMap =
G->second.RewriteMap;
15875 if (RewriteMap.empty())
15877 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15878 if (S == RewriteMap.end())
15884 return {C0,
SM->getSCEVType()};
15887 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15888 MinMaxPattern
P2) -> MinMaxPattern {
15889 auto [C1,
T1] =
P1;
15890 auto [C2, T2] =
P2;
15891 if (!C1 || !C2 ||
T1 != T2)
15895 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15897 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15899 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15901 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15906 auto P = GetMinMaxConst(0);
15907 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15910 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15913 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15916 Guards.RewriteMap.insert({
LHS,
RHS});
15924 const APInt &DivisorVal,
15926 const APInt *ExprVal;
15939 const APInt &DivisorVal,
15941 const APInt *ExprVal;
15949 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15963 const SCEV *URemRHS =
nullptr;
15967 const SCEV *Multiple =
15969 DivInfo[URemLHS] = Multiple;
15971 Multiples[URemLHS] =
C->getAPInt();
15991 auto IsMinMaxSCEVWithNonNegativeConstant =
15995 if (
MinMax->getNumOperands() != 2)
15998 if (
C->getAPInt().isNegative())
16000 SCTy =
MinMax->getSCEVType();
16009 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
16011 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
16016 auto *DivisibleExpr =
16024void ScalarEvolution::LoopGuards::collectFromBlock(
16026 const BasicBlock *
Block,
const BasicBlock *Pred,
16034 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
16045 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
16047 if (From == FromRewritten)
16049 RewriteMap[From] = To;
16055 auto GetMaybeRewritten = [&](
const SCEV *S) {
16056 return RewriteMap.lookup_or(S, S);
16063 const SCEV *MatchLHS,
16064 const SCEV *MatchRHS) {
16065 const SCEVConstant *C1;
16068 if (!
match(MatchLHS,
16080 const SCEV *RewrittenLHS = GetMaybeRewritten(LHSUnknown);
16081 ExactRegion = ExactRegion.intersectWith(SE.
getUnsignedRange(RewrittenLHS),
16086 if (ExactRegion.isEmptySet() || ExactRegion.isWrappedSet() ||
16087 ExactRegion.isFullSet())
16090 const SCEV *RegionMin = SE.
getConstant(ExactRegion.getUnsignedMin());
16091 const SCEV *RegionMax = SE.
getConstant(ExactRegion.getUnsignedMax());
16092 const SCEV *ClampedLHS =
16094 AddRewrite(LHSUnknown, RewrittenLHS, ClampedLHS);
16097 if (MatchRangeCheckIdiom(Predicate,
LHS,
RHS))
16110 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
16112 const APInt &DividesBy =
16127 switch (Predicate) {
16156 SmallPtrSet<const SCEV *, 16> Visited;
16158 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
16162 while (!Worklist.
empty()) {
16166 if (!Visited.
insert(From).second)
16168 const SCEV *FromRewritten = GetMaybeRewritten(From);
16169 const SCEV *To =
nullptr;
16171 switch (Predicate) {
16176 EnqueueOperands(
UMax);
16182 EnqueueOperands(
SMax);
16188 EnqueueOperands(
UMin);
16194 EnqueueOperands(
SMin);
16202 const SCEV *OneAlignedUp =
16204 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16216 const SCEVConstant *
C;
16225 Guards.NotEqual.insert({
LHS,
RHS});
16234 AddRewrite(From, FromRewritten, To);
16251 SE.F.
getParent(), Intrinsic::experimental_guard);
16253 for (
const auto *GU : GuardDecl->users())
16255 if (Guard->getFunction() ==
Block->getParent() &&
16264 unsigned NumCollectedConditions = 0;
16266 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16268 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16270 const CondBrInst *LoopEntryPredicate =
16272 if (!LoopEntryPredicate)
16277 NumCollectedConditions++;
16281 if (
Depth > 0 && NumCollectedConditions == 2)
16289 if (Pair.second->hasNPredecessorsOrMore(2) &&
16291 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16292 for (
auto &Phi : Pair.second->phis())
16303 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16304 SmallVector<Value *, 8> Worklist;
16305 SmallPtrSet<Value *, 8> Visited;
16307 while (!Worklist.
empty()) {
16314 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16338 DenseMap<const SCEV *, APInt> Multiples;
16340 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16347 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16348 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16352 for (
const auto &[K, Divisor] : Multiples) {
16353 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16354 Guards.RewriteMap[
K] =
16356 Guards.
rewrite(K), Divisor, SE),
16365 Guards.PreserveNUW =
true;
16366 Guards.PreserveNSW =
true;
16367 for (
const SCEV *Expr : ExprsToRewrite) {
16368 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16369 Guards.PreserveNUW &=
16371 Guards.PreserveNSW &=
16378 if (ExprsToRewrite.size() > 1) {
16379 for (
const SCEV *Expr : ExprsToRewrite) {
16380 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16381 Guards.RewriteMap.erase(Expr);
16382 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16391 class SCEVLoopGuardRewriter
16402 NotEqual(Guards.NotEqual) {
16403 if (Guards.PreserveNUW)
16405 if (Guards.PreserveNSW)
16412 return Map.lookup_or(Expr, Expr);
16416 if (
const SCEV *S = Map.lookup(Expr))
16423 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16424 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16425 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16427 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16428 if (
const SCEV *S = Map.lookup(NarrowExt))
16429 return SE.getZeroExtendExpr(S, Ty);
16430 Bitwidth = Bitwidth / 2;
16438 if (
const SCEV *S = Map.lookup(Expr))
16445 if (
const SCEV *S = Map.lookup(Expr))
16451 if (
const SCEV *S = Map.lookup(Expr))
16459 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16464 if (NotEqual.contains({LHS, RHS})) {
16466 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16467 return SE.getUMaxExpr(OneAlignedUp, S);
16474 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16485 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16486 return SE.getAddExpr(
16489 if (
const SCEV *S = Map.lookup(
Add))
16490 return SE.getAddExpr(Expr->
getOperand(0), S);
16502 : SE.getAddExpr(Operands,
16518 : SE.getMulExpr(Operands,
16524 if (RewriteMap.empty() && NotEqual.empty())
16527 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16528 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.
static bool isSigned(unsigned Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
Value * getPointer(Value *Ptr)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This defines the Use class.
iv Induction Variable Users
static constexpr Value * getValue(Ty &ValueOrUse)
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
MachineInstr unsigned OpIdx
static constexpr unsigned SM(unsigned Version)
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 DominatorTree getDomTree(Function &F)
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
static void visit(BasicBlock &Start, std::function< bool(BasicBlock *)> 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 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 hasHugeExpression(ArrayRef< SCEVUse > Ops)
Returns true if Ops contains a huge SCEV (the subtree of S contains at least HugeExprThreshold nodes)...
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 RangeRefPHIAllowedOperands(DominatorTree &DT, PHINode *PHI)
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 BinaryOperator * getCommonInstForPHI(PHINode *PN)
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 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 SCEV::NoWrapFlags StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, ArrayRef< SCEVUse > Ops, SCEV::NoWrapFlags Flags)
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 CollectAddOperandsWithScales(SmallDenseMap< SCEVUse, APInt, 16 > &M, SmallVectorImpl< SCEVUse > &NewOps, APInt &AccumulatedConstant, ArrayRef< SCEVUse > 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 const SCEV * constantFoldAndGroupOps(ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT, SmallVectorImpl< SCEVUse > &Ops, FoldT Fold, IsIdentityT IsIdentity, IsAbsorberT IsAbsorber)
Performs a number of common optimizations on the passed Ops.
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 void GroupByComplexity(SmallVectorImpl< SCEVUse > &Ops, LoopInfo *LI, DominatorTree &DT)
Given a list of SCEV objects, order them by their complexity, and group objects of the same complexit...
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 bool getOperandsForSelectLikePHI(DominatorTree &DT, PHINode *PN, Value *&Cond, Value *&LHS, Value *&RHS)
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 bool MatchBinarySub(const SCEV *S, SCEVUse &LHS, SCEVUse &RHS)
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 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 std::pair< ConstantRange, bool > getRangeForAffineARHelper(APInt Step, const ConstantRange &StartRange, const APInt &MaxBECount, bool Signed)
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 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?
static bool BrPHIToSelect(DominatorTree &DT, CondBrInst *BI, PHINode *Merge, Value *&C, Value *&LHS, Value *&RHS)
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 SymbolRef::Type getType(const Symbol *Sym)
LocallyHashedType DenseMapInfo< LocallyHashedType >::Empty
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.
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.
LLVM_ABI APInt uadd_ov(const APInt &RHS, bool &Overflow) const
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
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
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.
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
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()
Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
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 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; assumes that the block is well-formed.
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
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.
Conditional Branch instruction.
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
static LLVM_ABI Constant * getNot(Constant *C)
static Constant * getPtrAdd(Constant *Ptr, Constant *Offset, GEPNoWrapFlags NW=GEPNoWrapFlags::none(), std::optional< ConstantRange > InRange=std::nullopt, Type *OnlyIfReduced=nullptr)
Create a getelementptr i8, ptr, offset constant expression.
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 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 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
Return the entry for the specified key, or a default constructed value if no such entry exists.
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.
This class describes a reference to an interned FoldingSetNodeID, which can be a useful to store node...
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)
bool isEquality() const
Return true if this predicate is either EQ or NE.
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 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 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 areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2, ArrayRef< const SCEVPredicate * > ExtraPreds={}) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds and ExtraPreds.
LLVM_ABI bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've statically proved that V doesn't wrap.
LLVM_ABI const SCEVAddRecExpr * getAsAddRec(Value *V, SmallVectorImpl< const SCEVPredicate * > *WrapPredsAdded=nullptr)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
LLVM_ABI void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
LLVM_ABI PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
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 void addPredicates(ArrayRef< const SCEVPredicate * > Preds)
Adds all predicates in Preds.
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
LLVM_ABI const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
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
SCEVUse getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
This is the base class for unary cast operator classes.
SCEVUse getOperand() const
LLVM_ABI SCEVCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, SCEVUse 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, SCEVUse 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
ArrayRef< SCEVUse > operands() const
bool hasNoSelfWrap() const
size_t getNumOperands() const
bool hasNoSignedWrap() const
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
SCEVUse getOperand(unsigned i) 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.
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.
SCEVUnionPredicate getUnionWith(const SCEVPredicate *N, ScalarEvolution &SE) const
Returns a new SCEVUnionPredicate that is the union of this predicate and the given predicate N.
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents the value of vscale, as used when defining the length of a scalable vector or r...
This class represents an assumption made on an AddRec expression.
IncrementWrapFlags
Similar to SCEV::NoWrapFlags, but with slightly different semantics for FlagNUSW.
SCEVWrapPredicate(const FoldingSetNodeIDRef ID, const SCEVAddRecExpr *AR, IncrementWrapFlags Flags)
bool implies(const SCEVPredicate *N, 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.
unsigned short getExpressionSize() const
SCEVNoWrapFlags NoWrapFlags
LLVM_ABI bool isOne() const
Return true if the expression is a constant one.
static constexpr auto FlagNUW
LLVM_ABI void computeAndSetCanonical(ScalarEvolution &SE)
Compute and set the canonical SCEV, by constructing a SCEV with the same operands,...
LLVM_ABI bool isZero() const
Return true if the expression is a constant zero.
const SCEV * CanonicalSCEV
Pointer to the canonical version of the SCEV, i.e.
static constexpr auto FlagAnyWrap
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.
static constexpr auto FlagNSW
LLVM_ABI ArrayRef< SCEVUse > operands() const
Return operands of this SCEV expression.
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
static constexpr auto FlagNW
LLVM_ABI Type * getType() const
Return the LLVM type of this SCEV expression.
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.
LLVM_ABI const SCEV * getUDivExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
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 * 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 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 * getURemExpr(SCEVUse LHS, SCEVUse RHS)
Represents an unsigned remainder expression based on unsigned division.
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 * 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 * getSMinExpr(SCEVUse LHS, SCEVUse 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 SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &Operands)
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.
LLVM_ABI const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
LLVM_ABI const SCEV * getAddRecExpr(SCEVUse Start, SCEVUse Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
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.
static LLVM_ABI bool isGuaranteedNotToBePoison(const SCEV *Op)
Returns true if Op is guaranteed to not be poison.
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 * getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty)
LLVM_ABI const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &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.
LLVM_ABI bool SimplifyICmpOperands(CmpPredicate &Pred, SCEVUse &LHS, SCEVUse &RHS, unsigned Depth=0)
Simplify LHS and RHS in a comparison with predicate Pred.
APInt getUnsignedRangeMin(const SCEV *S)
Determine the min of the unsigned range for a particular SCEV.
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 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 * 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 * 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 bool isLoopUniform(const SCEV *S, const Loop *L)
Returns true if the given SCEV is loop-uniform with respect to the specified loop L.
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)
LLVM_ABI const SCEV * getUMaxExpr(SCEVUse LHS, SCEVUse RHS)
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags Mask)
Convenient NoWrapFlags manipulation.
@ 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 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.
@ LoopUniform
The SCEV is loop-uniform.
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 const SCEV * getMulExpr(SmallVectorImpl< SCEVUse > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
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 * 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 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.
LLVM_ABI const SCEV * getAddExpr(SmallVectorImpl< SCEVUse > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
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 bool isKnownPredicate(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
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 * 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 * getSMaxExpr(SCEVUse LHS, SCEVUse RHS)
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.
LLVM_ABI bool isKnownViaInduction(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
We'd like to check the predicate on every iteration of the most dominated loop between loops used in ...
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 * getUDivExactExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
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 * getGEPExpr(GEPOperator *GEP, ArrayRef< SCEVUse > IndexExprs)
Returns an expression for a GEP.
LLVM_ABI const SCEV * getUMinExpr(SCEVUse LHS, SCEVUse RHS, bool Sequential=false)
LLVM_ABI void registerUser(const SCEV *User, ArrayRef< const SCEV * > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
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.
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.
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.
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.
constexpr bool any(E Val)
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.
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
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)
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
auto m_BasicBlock()
Match an arbitrary basic block value and ignore it.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
auto m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
match_bind< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
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.
brc_match< Cond_t, match_bind< BasicBlock >, match_bind< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
CastOperator_match< OpTy, Instruction::PtrToInt > m_PtrToInt(const OpTy &Op)
Matches PtrToInt.
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
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.
cst_pred_ty< is_one > m_scev_One()
Match an integer 1.
specificloop_ty m_SpecificLoop(const Loop *L)
SCEVUnaryExpr_match< SCEVSignExtendExpr, Op0_t > m_scev_SExt(const Op0_t &Op0)
match_bind< const SCEVMulExpr > m_scev_Mul(const SCEVMulExpr *&V)
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.
SCEVAffineAddRec_match< Op0_t, Op1_t, match_isa< const Loop > > m_scev_AffineAddRec(const Op0_t &Op0, const Op1_t &Op1)
match_bind< const SCEVUnknown > m_SCEVUnknown(const SCEVUnknown *&V)
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagNUW, true > m_scev_c_NUWMul(const Op0_t &Op0, const Op1_t &Op1)
match_bind< const SCEVAddExpr > m_scev_Add(const SCEVAddExpr *&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.
@ 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.
unsigned getOpcode(const VPValue *V)
Return the instruction opcode for the recipe defining V or 0 for unsupported recipes and VPValues not...
This is an optimization pass for GlobalISel generic memory operations.
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt gcd(const DynamicAPInt &A, const DynamicAPInt &B)
void stable_sort(R &&Range)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
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...
RelativeUniformCounterPtr Values
@ Known
Known to have no common set bits.
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 >
@ BinaryOp
One of the operands is a binary op.
@ Load
The value being inserted comes from a load (InsertElement only).
@ Store
The extracted value is stored (ExtractElement only).
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.
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.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
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...
unsigned short computeExpressionSize(ArrayRef< SCEVUse > Args)
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)
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.
constexpr T divideCeil(U Numerator, V Denominator)
Returns the integer ceil(Numerator / Denominator).
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()).
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
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 auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
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)
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.
SCEVUseT< const SCEV * > SCEVUse
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.
static LLVM_ABI KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for ashr(LHS, RHS).
static LLVM_ABI KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for lshr(LHS, RHS).
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