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"));
243 cl::desc(
"Handle <= and >= in finite loops"),
247 "scalar-evolution-use-context-for-no-wrap-flag-strenghening",
cl::Hidden,
248 cl::desc(
"Infer nuw/nsw flags using context where suitable"),
290#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
308 OS <<
"(ptrtoaddr " << *
Op->getType() <<
" " <<
Op <<
" to "
315 OS <<
"(trunc " << *
Op->getType() <<
" " <<
Op <<
" to "
322 OS <<
"(zext " << *
Op->getType() <<
" " <<
Op <<
" to " << *ZExt->
getType()
329 OS <<
"(sext " << *
Op->getType() <<
" " <<
Op <<
" to " << *SExt->
getType()
358 const char *OpStr =
nullptr;
371 OpStr =
" umin_seq ";
393 OS <<
"(" << UDiv->
getLHS() <<
" /u " << UDiv->
getRHS() <<
")";
400 OS <<
"***COULDNOTCOMPUTE***";
442 if (!
Mul)
return false;
446 if (!SC)
return false;
460 auto &Entry = ConstantSCEVs[V];
469 static_cast<SCEVConstant *
>(UniqueSCEVs.lookup(ID, Token)))
472 new (SCEVAllocator)
SCEVConstant(ID.Intern(SCEVAllocator), V);
473 UniqueSCEVs.insert(S, Token);
488 ConstantInt::get(ITy, V,
isSigned,
true));
496 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
498 SCEV *S =
new (SCEVAllocator)
SCEVVScale(ID.Intern(SCEVAllocator), Ty);
499 UniqueSCEVs.insert(S, Token);
520 "Must be a non-bit-width-changing pointer-to-integer cast!");
532 "Cannot truncate non-integer value!");
539 "Cannot zero extend non-integer value!");
546 "Cannot sign extend non-integer value!");
551 SE->forgetMemoizedResults({
this});
554 SE->UniqueSCEVs.erase(
this);
560void SCEVUnknown::allUsesReplacedWith(
Value *New) {
562 SE->forgetMemoizedResults({
this});
565 SE->UniqueSCEVs.erase(
this);
587 if (LIsPointer != RIsPointer)
588 return (
int)LIsPointer - (int)RIsPointer;
593 return (
int)LID - (int)RID;
598 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
599 return (
int)LArgNo - (int)RArgNo;
605 if (
auto L = LGV->getLinkage() - RGV->getLinkage())
608 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
609 auto LT = GV->getLinkage();
616 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
617 return LGV->getName().compare(RGV->getName());
628 if (LParent != RParent) {
631 if (LDepth != RDepth)
632 return (
int)LDepth - (int)RDepth;
636 unsigned LNumOps = LInst->getNumOperands(),
637 RNumOps = RInst->getNumOperands();
638 if (LNumOps != RNumOps)
639 return (
int)LNumOps - (int)RNumOps;
641 for (
unsigned Idx :
seq(LNumOps)) {
643 RInst->getOperand(Idx),
Depth + 1);
657static std::optional<int>
667 return (
int)LType - (int)RType;
692 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
693 if (LBitWidth != RBitWidth)
694 return (
int)LBitWidth - (int)RBitWidth;
695 return LA.
ult(
RA) ? -1 : 1;
701 return LTy->getBitWidth() - RTy->getBitWidth();
712 if (LLoop != RLoop) {
714 assert(LHead != RHead &&
"Two loops share the same header?");
718 "No dominance between recurrences used by one SCEV?");
741 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
742 if (LNumOps != RNumOps)
743 return (
int)LNumOps - (int)RNumOps;
745 for (
unsigned i = 0; i != LNumOps; ++i) {
771 if (
Ops.size() < 2)
return;
776 return Complexity && *Complexity < 0;
778 if (
Ops.size() == 2) {
782 if (IsLessComplex(
RHS,
LHS))
795 for (
unsigned i = 0, e =
Ops.size(); i != e-2; ++i) {
801 for (
unsigned j = i+1; j != e &&
Ops[j]->getSCEVType() == Complexity; ++j) {
806 if (i == e-2)
return;
828template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
832 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
834 for (
unsigned Idx = 0; Idx <
Ops.size();) {
842 Ops.erase(
Ops.begin() + Idx);
849 assert(Folded &&
"Must have folded value");
853 if (Folded && IsAbsorber(Folded->
getAPInt()))
857 if (Folded && !IsIdentity(Folded->
getAPInt()))
858 Ops.insert(
Ops.begin(), Folded);
860 return Ops.size() == 1 ?
Ops[0] :
nullptr;
935 APInt OddFactorial(W, 1);
937 for (
unsigned i = 3; i <=
K; ++i) {
940 OddFactorial *= (i >> TwoFactors);
944 unsigned CalculationBits = W +
T;
958 for (
unsigned i = 1; i !=
K; ++i) {
983template <
typename ExprT>
990 return {Res, UseFlags};
1012 "use-specific flags only supported for affine AddRecs");
1014 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1024 Result,
Mul, UseFlags);
1055 ConversionFn CreatePtrCast;
1059 ConversionFn CreatePtrCast)
1060 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
1063 Type *TargetTy, ConversionFn CreatePtrCast) {
1065 return Rewriter.visit(Scev);
1091 "Should only reach pointer-typed SCEVUnknown's.");
1096 return SE.getZero(TargetTy);
1097 return CreatePtrCast(Expr);
1102 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1106 if (DL.hasUnstableRepresentation(
Op->getType()))
1109 Type *Ty = DL.getAddressType(
Op->getType());
1120 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1122 SCEV *S =
new (SCEVAllocator)
1124 UniqueSCEVs.insert(S, Token);
1127 return static_cast<const SCEV *
>(S);
1130 "We must have succeeded in sinking the cast, "
1131 "and ending up with an integer-typed expression!");
1138 "This is not a truncating conversion!");
1140 "This is not a conversion to a SCEVable type!");
1141 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1146 ID.AddPointer(
Op.getOpaqueValue());
1149 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1172 UniqueSCEVs.insert(S, Token);
1185 unsigned numTruncs = 0;
1186 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1194 if (numTruncs < 2) {
1204 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1211 for (
const SCEV *
Op : AddRec->operands())
1226 UniqueSCEVs.insert(S, Token);
1267struct ExtendOpTraitsBase {
1268 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
SCEVUse,
Type *,
1273template <
typename ExtendOp>
struct ExtendOpTraits {
1289 static const GetExtendExprTy GetExtendExpr;
1291 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1292 ICmpInst::Predicate *Pred,
1293 ScalarEvolution *SE) {
1298const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1305 static const GetExtendExprTy GetExtendExpr;
1307 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1308 ICmpInst::Predicate *Pred,
1309 ScalarEvolution *SE) {
1314const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1326template <
typename ExtendOpTy>
1329 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1330 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1346 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1359 auto PreStartFlags =
1377 const SCEV *OperandExtendedStart =
1379 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1380 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1392 const SCEV *OverflowLimit =
1393 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1395 if (OverflowLimit &&
1403template <
typename ExtendOpTy>
1407 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1415 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1450template <
typename ExtendOpTy>
1451bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1454 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1464 APInt StartAI = StartC->
getAPInt();
1466 for (
unsigned Delta : {-2, -1, 1, 2}) {
1467 const SCEV *PreStart =
getConstant(StartAI - Delta);
1469 FoldingSetNodeID
ID;
1471 ID.AddPointer(PreStart);
1472 ID.AddPointer(Step);
1474 FoldingSetInsertToken Token;
1476 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.lookup(ID, Token));
1480 if (PreAR &&
any(PreAR->getNoWrapFlags(WrapType))) {
1483 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1484 DeltaS, &Pred,
this);
1502 const unsigned BitWidth =
C.getBitWidth();
1520 const APInt &ConstantStart,
1535 auto I = FoldCache.
insert({ID, S});
1539 auto &UserIDs = FoldCacheUser[
I.first->second];
1540 assert(
count(UserIDs, ID) == 1 &&
"unexpected duplicates in UserIDs");
1541 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1542 if (UserIDs[
I] == ID) {
1547 I.first->second = S;
1549 FoldCacheUser[S].push_back(ID);
1555 "This is not an extending conversion!");
1557 "This is not a conversion to a SCEVable type!");
1558 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1562 if (
const SCEV *S = FoldCache.lookup(ID))
1574 "This is not an extending conversion!");
1576 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1588 const SCEV *Start, *Step;
1593 if (AR->hasNoUnsignedWrap()) {
1604 ID.AddPointer(
Op.getOpaqueValue());
1607 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1612 UniqueSCEVs.insert(S, Token);
1622 const SCEV *
X = ST->getOperand();
1655 const SCEV *CastedMaxBECount =
1659 if (MaxBECount == RecastedMaxBECount) {
1668 const SCEV *WideMaxBECount =
1670 const SCEV *OperandExtendedAdd =
1676 if (ZAdd == OperandExtendedAdd) {
1687 OperandExtendedAdd =
1693 if (ZAdd == OperandExtendedAdd) {
1714 !AC.assumptions().empty()) {
1716 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1718 if (AR->hasNoUnsignedWrap()) {
1753 const APInt &
C = SC->getAPInt();
1757 const SCEV *SResidual =
1765 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1789 if (SA->hasNoUnsignedWrap()) {
1802 if (SA->hasNoSignedWrap() &&
1805 C->isNegative() && !
C->isMinSignedValue() && C2->
sge(
C->abs())) {
1824 const SCEV *SResidual =
1835 if (SM->hasNoUnsignedWrap()) {
1857 const SCEV *TruncRHS;
1894 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1898 UniqueSCEVs.insert(S, Token);
1907 "This is not an extending conversion!");
1909 "This is not a conversion to a SCEVable type!");
1910 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1914 if (
const SCEV *S = FoldCache.lookup(ID))
1926 "This is not an extending conversion!");
1928 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1945 const SCEV *Start, *Step;
1950 if (AR->hasNoSignedWrap()) {
1961 ID.AddPointer(
Op.getOpaqueValue());
1964 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1970 UniqueSCEVs.insert(S, Token);
1980 const SCEV *
X = ST->getOperand();
1991 if (SA->hasNoSignedWrap()) {
2013 const SCEV *SResidual =
2046 const SCEV *CastedMaxBECount =
2050 if (MaxBECount == RecastedMaxBECount) {
2059 const SCEV *WideMaxBECount =
2061 const SCEV *OperandExtendedAdd =
2067 if (SAdd == OperandExtendedAdd) {
2078 OperandExtendedAdd =
2084 if (SAdd == OperandExtendedAdd) {
2104 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2106 if (AR->hasNoSignedWrap()) {
2120 const APInt &
C = SC->getAPInt();
2124 const SCEV *SResidual =
2132 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2159 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
2163 UniqueSCEVs.insert(S, Token);
2179 assert(Expr->
getType() == Ty &&
"requested type must match");
2191 "This is not an extending conversion!");
2193 "This is not a conversion to a SCEVable type!");
2198 if (SC->getAPInt().isNegative())
2203 const SCEV *NewOp =
T->getOperand();
2222 for (
const SCEV *
Op : AR->operands())
2260 APInt &AccumulatedConstant,
2264 bool Interesting =
false;
2271 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2273 AccumulatedConstant += Scale *
C->getAPInt();
2278 for (; i !=
Ops.size(); ++i) {
2287 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2293 auto Pair = M.insert({
Key, NewScale});
2297 Pair.first->second += NewScale;
2305 auto Pair = M.insert({
Ops[i], Scale});
2309 Pair.first->second += Scale;
2328 case Instruction::Add:
2331 case Instruction::Sub:
2334 case Instruction::Mul:
2348 const SCEV *
A = (this->*Extension)(
2350 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2351 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2359 if (BinOp == Instruction::Mul)
2365 APInt C = RHSC->getAPInt();
2366 unsigned NumBits =
C.getBitWidth();
2367 bool IsSub = (BinOp == Instruction::Sub);
2368 bool IsNegativeConst = (
Signed &&
C.isNegative());
2370 bool OverflowDown = IsSub ^ IsNegativeConst;
2372 if (IsNegativeConst) {
2385 APInt Limit = Min + Magnitude;
2391 APInt Limit = Max - Magnitude;
2396std::optional<SCEV::NoWrapFlags>
2401 return std::nullopt;
2410 bool Deduced =
false;
2416 bool CanUseNSW =
true;
2417 const APInt *ShiftAmt;
2422 return std::nullopt;
2426 Opcode = Instruction::Mul;
2428 }
else if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
2429 Opcode != Instruction::Mul) {
2430 return std::nullopt;
2449 return std::nullopt;
2459 using namespace std::placeholders;
2466 assert(CanAnalyze &&
"don't call from other places!");
2473 auto IsKnownNonNegative = [&](
SCEVUse U) {
2482 if (SignOrUnsignWrap != SignOrUnsignMask &&
2489 return Instruction::Add;
2491 return Instruction::Mul;
2502 Opcode,
C, OBO::NoSignedWrap);
2510 Opcode,
C, OBO::NoUnsignedWrap);
2520 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2527 if (UDiv->getOperand(1) ==
Ops[1])
2530 if (UDiv->getOperand(1) ==
Ops[0])
2546 "only nuw or nsw allowed");
2547 assert(!
Ops.empty() &&
"Cannot get empty add!");
2548 if (
Ops.size() == 1)
return Ops[0];
2551 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2553 "SCEVAddExpr operand types don't match!");
2555 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2556 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2561 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2562 [](
const APInt &
C) {
return C.isZero(); },
2563 [](
const APInt &
C) {
return false; });
2576 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2581 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2582 Add->setNoWrapFlags(ComputeFlags(
Ops));
2590 bool FoundMatch =
false;
2591 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2592 if (
Ops[i] ==
Ops[i+1]) {
2604 --i; e -=
Count - 1;
2614 auto FindTruncSrcType = [&]() ->
Type * {
2620 return T->getOperand()->getType();
2622 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2624 return T->getOperand()->getType();
2628 if (
auto *SrcType = FindTruncSrcType()) {
2635 if (
T->getOperand()->getType() != SrcType) {
2644 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2647 if (
T->getOperand()->getType() != SrcType) {
2675 if (
Ops.size() == 2) {
2685 auto C2 =
C->getAPInt();
2688 APInt ConstAdd = C1 + C2;
2689 auto AddFlags = AddExpr->getNoWrapFlags();
2730 if (
Ops.size() == 2 &&
2741 if (Idx <
Ops.size()) {
2742 bool DeletedAdd =
false;
2753 Ops.erase(
Ops.begin()+Idx);
2756 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2779 struct APIntCompare {
2780 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2781 return LHS.ult(RHS);
2788 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2789 for (
const SCEV *NewOp : NewOps)
2790 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2793 if (AccumulatedConstant != 0)
2795 for (
auto &MulOp : MulOpLists) {
2796 if (MulOp.first == 1) {
2798 }
else if (MulOp.first != 0) {
2807 if (
Ops.size() == 1)
2816 if (M->getNumOperands() == 2)
2817 return M->getOperand(OpIdx == 0);
2819 append_range(Remaining, M->operands().drop_front(OpIdx + 1));
2828 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2832 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2840 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp) {
2841 if (MulOpSCEV ==
Ops[AddOp]) {
2852 for (
unsigned OMulOp = 0, OE = OtherMul->
getNumOperands(); OMulOp != OE;
2854 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2856 Cofactors.
push_back(StripFactor(OtherMul, OMulOp));
2865 if (!Cofactors.
empty()) {
2873 if (
Ops.size() == DeadIndices.
size() + 1)
2880 Ops.erase(
Ops.begin() + Idx);
2884 Ops.push_back(OuterMul);
2903 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2906 Ops.erase(
Ops.begin()+i);
2911 if (!LIOps.
empty()) {
2936 auto *DefI = getDefiningScopeBound(LIOps);
2938 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2950 if (
Ops.size() == 1)
return NewRec;
2953 for (
unsigned i = 0;; ++i)
2954 if (
Ops[i] == AddRec) {
2964 for (
unsigned OtherIdx = Idx+1;
2972 "AddRecExprs are not sorted in reverse dominance order?");
2979 if (OtherAddRec->getLoop() == AddRecLoop) {
2980 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2982 if (i >= AddRecOps.
size()) {
2983 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2987 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
2990 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3005 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
3013 ID.AddPointer(
Op.getOpaqueValue());
3019 S =
new (SCEVAllocator)
3021 UniqueSCEVs.insert(S, Token);
3032 FoldingSetNodeID
ID;
3035 ID.AddPointer(
Op.getOpaqueValue());
3037 FoldingSetInsertToken Token;
3039 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.lookup(ID, Token));
3043 S =
new (SCEVAllocator)
3044 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3045 UniqueSCEVs.insert(S, Token);
3047 LoopUsers[
L].push_back(S);
3056 FoldingSetNodeID
ID;
3059 ID.AddPointer(
Op.getOpaqueValue());
3060 FoldingSetInsertToken Token;
3061 SCEVMulExpr *S =
static_cast<SCEVMulExpr *
>(UniqueSCEVs.lookup(ID, Token));
3065 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3067 UniqueSCEVs.insert(S, Token);
3076 FoldingSetNodeID
ID;
3078 ID.AddPointer(
LHS.getOpaqueValue());
3079 ID.AddPointer(
RHS.getOpaqueValue());
3080 FoldingSetInsertToken Token;
3081 SCEV *S = UniqueSCEVs.lookup(ID, Token);
3083 S =
new (SCEVAllocator) SCEVUDivExpr(
ID.Intern(SCEVAllocator),
LHS,
RHS);
3084 UniqueSCEVs.insert(S, Token);
3093 if (j > 1 && k / j != i) Overflow =
true;
3109 if (n == 0 || n == k)
return 1;
3110 if (k > n)
return 0;
3116 for (
uint64_t i = 1; i <= k; ++i) {
3117 r =
umul_ov(r, n-(i-1), Overflow);
3126 struct FindConstantInAddMulChain {
3127 bool FoundConstant =
false;
3129 bool follow(
const SCEV *S) {
3134 bool isDone()
const {
3135 return FoundConstant;
3139 FindConstantInAddMulChain
F;
3141 ST.visitAll(StartExpr);
3142 return F.FoundConstant;
3150 "only nuw or nsw allowed");
3151 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3152 if (
Ops.size() == 1)
return Ops[0];
3154 Type *ETy =
Ops[0]->getType();
3156 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3158 "SCEVMulExpr operand types don't match!");
3163 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3164 [](
const APInt &
C) {
return C.isOne(); },
3165 [](
const APInt &
C) {
return C.isZero(); });
3176 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3181 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3182 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3187 if (
Ops.size() == 2) {
3195 const SCEV *Op0, *Op1;
3203 if (
Ops[0]->isAllOnesValue()) {
3208 bool AnyFolded =
false;
3209 for (
const SCEV *AddOp :
Add->operands()) {
3229 if (AddRec->hasNoSignedWrap()) {
3236 AddRec->getNoWrapFlags(FlagsMask));
3259 APInt C1V = LHSC->getAPInt();
3269 const SCEV *NewMul =
nullptr;
3273 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3288 if (Idx <
Ops.size()) {
3289 bool DeletedMul =
false;
3295 Ops.erase(
Ops.begin()+Idx);
3319 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3322 Ops.erase(
Ops.begin()+i);
3327 if (!LIOps.
empty()) {
3340 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3356 if (
Ops.size() == 1)
return NewRec;
3359 for (
unsigned i = 0;; ++i)
3360 if (
Ops[i] == AddRec) {
3381 bool OpsModified =
false;
3382 for (
unsigned OtherIdx = Idx+1;
3396 bool Overflow =
false;
3403 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3404 uint64_t Coeff1 =
Choose(x, 2*x - y, Overflow);
3407 z < ze && !Overflow; ++z) {
3408 uint64_t Coeff2 =
Choose(2*x - y, x-z, Overflow);
3410 if (LargerThan64Bits)
3411 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3413 Coeff = Coeff1*Coeff2;
3428 if (
Ops.size() == 2)
return NewAddRec;
3429 Ops[Idx] = NewAddRec;
3430 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3446 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3453 "SCEVURemExpr operand types don't match!");
3458 if (RHSC->getValue()->isOne())
3459 return getZero(LHS->getType());
3462 if (RHSC->getAPInt().isPowerOf2()) {
3463 Type *FullTy = LHS->getType();
3479 assert(!LHS->getType()->isPointerTy() &&
3480 "SCEVUDivExpr operand can't be pointer!");
3481 assert(LHS->getType() == RHS->getType() &&
3482 "SCEVUDivExpr operand types don't match!");
3492 if (RHSC->getValue()->isOne())
3497 if (!RHSC->getValue()->isZero()) {
3501 Type *Ty = LHS->getType();
3502 unsigned LZ = RHSC->getAPInt().countl_zero();
3506 if (!RHSC->getAPInt().isPowerOf2())
3514 const APInt &StepInt = Step->getAPInt();
3515 const APInt &DivInt = RHSC->getAPInt();
3516 if (!StepInt.
urem(DivInt) &&
3522 for (
const SCEV *
Op : AR->operands())
3528 const APInt *StartRem;
3541 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3545 const SCEV *NewStart =
3547 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3549 const SCEV *NewLHS =
3559 if (M->hasNoUnsignedWrap()) {
3561 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3562 const SCEV *
Op = M->getOperand(i);
3589 if (
auto *DivisorConstant =
3591 bool Overflow =
false;
3593 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3604 if (
A->hasNoUnsignedWrap()) {
3606 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3613 if (
Operands.size() ==
A->getNumOperands())
3625 const APInt &
N = RHSC->getAPInt();
3626 const APInt *NMinusM, *M;
3630 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3631 *NMinusM ==
N - *M) {
3640 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3650 return getZero(LHS->getType());
3654 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3655 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3656 if (
Mul->getOperand(i) == RHS) {
3667 const SCEV *NewLHS, *NewRHS;
3672 return getOrCreateUDivExpr(LHS, RHS);
3692 if (StepChrec->getLoop() == L) {
3711 "SCEVAddRecExpr operand types don't match!");
3712 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3716 "SCEVAddRecExpr operand is not available at loop entry!");
3734 const Loop *NestedLoop = NestedAR->getLoop();
3735 if (L->contains(NestedLoop)
3738 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3740 Operands[0] = NestedAR->getStart();
3744 bool AllInvariant =
all_of(
3756 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3767 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3777 return getOrCreateAddRecExpr(
Operands, L, Flags);
3793 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3797 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3811 bool FirstIter =
true;
3813 for (
SCEVUse IndexExpr : IndexExprs) {
3820 Offsets.push_back(FieldOffset);
3823 CurTy = STy->getTypeAtIndex(Index);
3828 "The first index of a GEP indexes a pointer");
3829 CurTy = SrcElementTy;
3840 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3841 Offsets.push_back(LocalOffset);
3846 if (Offsets.empty())
3859 "GEP should not change type mid-flight.");
3863SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3868 ID.AddPointer(
Op.getOpaqueValue());
3870 return UniqueSCEVs.lookup(ID, Token);
3880 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3881 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3882 if (
Ops.size() == 1)
return Ops[0];
3885 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3887 "Operand types don't match!");
3890 "min/max should be consistently pointerish");
3916 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3918 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3923 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3925 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3931 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3937 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3942 if (Idx <
Ops.size()) {
3943 bool DeletedAny =
false;
3944 while (
Ops[Idx]->getSCEVType() == Kind) {
3946 Ops.erase(
Ops.begin()+Idx);
3964 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3965 if (
Ops[i] ==
Ops[i + 1] ||
3966 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3969 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3972 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3975 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3981 if (
Ops.size() == 1)
return Ops[0];
3983 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
3990 ID.AddPointer(
Op.getOpaqueValue());
3992 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
3994 return ExistingSCEV;
3997 SCEV *S =
new (SCEVAllocator)
4000 UniqueSCEVs.insert(S, Token);
4008class SCEVSequentialMinMaxDeduplicatingVisitor final
4009 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4010 std::optional<const SCEV *>> {
4011 using RetVal = std::optional<const SCEV *>;
4018 bool canRecurseInto(
SCEVTypes Kind)
const {
4021 return RootKind == Kind || NonSequentialRootKind == Kind;
4026 if (!SeenOps.
insert(S).second)
4027 return std::nullopt;
4031 if (!canRecurseInto(Kind))
4041 return std::nullopt;
4051 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4053 : SE(SE), RootKind(RootKind),
4054 NonSequentialRootKind(
4055 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4059 SmallVectorImpl<SCEVUse> &NewOps) {
4064 for (
const SCEV *
Op : OrigOps) {
4069 Ops.emplace_back(*NewOp);
4073 NewOps = std::move(
Ops);
4117struct SCEVPoisonCollector {
4118 bool LookThroughMaybePoisonBlocking;
4119 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4120 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4121 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4123 bool follow(
const SCEV *S) {
4124 if (!LookThroughMaybePoisonBlocking &&
4134 bool isDone()
const {
return false; }
4144 SCEVPoisonCollector PC1(
true);
4149 if (PC1.MaybePoison.
empty())
4155 SCEVPoisonCollector PC2(
false);
4165 SCEVPoisonCollector PC(
false);
4188 while (!Worklist.
empty()) {
4190 if (!Visited.
insert(V).second)
4194 if (Visited.
size() > 16)
4210 if (PDI->isDisjoint())
4217 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4224 if (
I->hasPoisonGeneratingAnnotations())
4235 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4236 "Not a SCEVSequentialMinMaxExpr!");
4237 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4238 if (
Ops.size() == 1)
4242 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4244 "Operand types don't match!");
4247 "min/max should be consistently pointerish");
4255 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4262 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4272 bool DeletedAny =
false;
4273 while (Idx <
Ops.size()) {
4274 if (
Ops[Idx]->getSCEVType() != Kind) {
4279 Ops.erase(
Ops.begin() + Idx);
4280 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4281 SMME->operands().end());
4289 const SCEV *SaturationPoint;
4300 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4301 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4313 Ops.erase(
Ops.begin() + i);
4318 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4319 Ops.erase(
Ops.begin() + i);
4329 ID.AddPointer(
Op.getOpaqueValue());
4331 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
4333 return ExistingSCEV;
4337 SCEV *S =
new (SCEVAllocator)
4340 UniqueSCEVs.insert(S, Token);
4388 if (
Size.isScalable())
4409 "Cannot get offset for structure containing scalable vector types");
4423 if (
SCEV *S = UniqueSCEVs.lookup(ID, Token)) {
4425 "Stale SCEVUnknown in uniquing map!");
4428 SCEV *S =
new (SCEVAllocator)
SCEVUnknown(ID.Intern(SCEVAllocator), V,
this,
4431 UniqueSCEVs.insert(S, Token);
4446 return Ty->isIntOrPtrTy();
4453 if (Ty->isPointerTy())
4464 if (Ty->isIntegerTy())
4468 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4480 bool PreciseA, PreciseB;
4481 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4482 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4483 if (!PreciseA || !PreciseB)
4486 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4487 DT.dominates(ScopeB, ScopeA);
4491 return CouldNotCompute.get();
4494bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4497 return SU && SU->getValue() ==
nullptr;
4500 return !ContainsNulls;
4505 if (
I != HasRecMap.end())
4510 HasRecMap.insert({S, FoundAddRec});
4518 if (
SI == ExprValueMap.
end())
4520 return SI->second.getArrayRef();
4526void ScalarEvolution::eraseValueFromMap(
Value *V) {
4528 if (
I != ValueExprMap.end()) {
4529 auto EVIt = ExprValueMap.find(
I->second);
4530 bool Removed = EVIt->second.remove(V);
4532 assert(Removed &&
"Value not in ExprValueMap?");
4533 ValueExprMap.erase(
I);
4537void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4541 auto It = ValueExprMap.find_as(V);
4542 if (It == ValueExprMap.end()) {
4544 ExprValueMap[S].insert(V);
4555 return createSCEVIter(V);
4562 if (
I != ValueExprMap.end()) {
4563 const SCEV *S =
I->second;
4564 assert(checkValidity(S) &&
4565 "existing SCEV has not been properly invalidated");
4578 Type *Ty = V->getType();
4594 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4607 return (
const SCEV *)
nullptr;
4613 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4617 Type *Ty = V->getType();
4623 assert(
P->getType()->isPointerTy());
4638 if (AddOp->getType()->isPointerTy()) {
4639 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4657 return getZero(LHS->getType());
4662 if (RHS->getType()->isPointerTy()) {
4663 if (!LHS->getType()->isPointerTy() ||
4673 const bool RHSIsNotMinSigned =
4704 Type *SrcTy = V->getType();
4705 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4706 "Cannot truncate or zero extend with non-integer arguments!");
4716 Type *SrcTy = V->getType();
4717 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4718 "Cannot truncate or zero extend with non-integer arguments!");
4727 Type *SrcTy = V->getType();
4728 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4729 "Cannot noop or zero extend with non-integer arguments!");
4731 "getNoopOrZeroExtend cannot truncate!");
4738 Type *SrcTy = V->getType();
4739 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4740 "Cannot noop or sign extend with non-integer arguments!");
4742 "getNoopOrSignExtend cannot truncate!");
4749 Type *SrcTy = V->getType();
4750 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4751 "Cannot noop or any extend with non-integer arguments!");
4753 "getNoopOrAnyExtend cannot truncate!");
4760 Type *SrcTy = V->getType();
4761 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4762 "Cannot truncate or noop with non-integer arguments!");
4764 "getTruncateOrNoop cannot extend!");
4772 const SCEV *PromotedLHS = LHS;
4773 const SCEV *PromotedRHS = RHS;
4793 assert(!
Ops.empty() &&
"At least one operand must be!");
4795 if (
Ops.size() == 1)
4799 Type *MaxType =
nullptr;
4805 assert(MaxType &&
"Failed to find maximum type!");
4818 if (!V->getType()->isPointerTy())
4823 V = AddRec->getStart();
4825 const SCEV *PtrOp =
nullptr;
4826 for (
const SCEV *AddOp :
Add->operands()) {
4827 if (AddOp->getType()->isPointerTy()) {
4828 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4832 assert(PtrOp &&
"Must have pointer op");
4844 for (
User *U :
I->users()) {
4846 if (Visited.
insert(UserInsn).second)
4860 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4861 bool IgnoreOtherLoops =
true) {
4864 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4866 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4871 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4873 SeenLoopVariantSCEVUnknown =
true;
4877 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4881 SeenOtherLoops =
true;
4885 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4887 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4890 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4891 : SCEVRewriteVisitor(SE),
L(
L) {}
4894 bool SeenLoopVariantSCEVUnknown =
false;
4895 bool SeenOtherLoops =
false;
4904 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4905 SCEVPostIncRewriter
Rewriter(L, SE);
4907 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4912 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4914 SeenLoopVariantSCEVUnknown =
true;
4918 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4922 SeenOtherLoops =
true;
4926 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4928 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4931 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4932 : SCEVRewriteVisitor(SE),
L(
L) {}
4935 bool SeenLoopVariantSCEVUnknown =
false;
4936 bool SeenOtherLoops =
false;
4942class SCEVBackedgeConditionFolder
4945 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4946 ScalarEvolution &SE) {
4947 bool IsPosBECond =
false;
4948 Value *BECond =
nullptr;
4949 if (BasicBlock *Latch =
L->getLoopLatch()) {
4951 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
4952 "Both outgoing branches should not target same header!");
4953 BECond = BI->getCondition();
4954 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
4959 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
4963 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4964 const SCEV *
Result = Expr;
4969 switch (
I->getOpcode()) {
4970 case Instruction::Select: {
4972 std::optional<const SCEV *> Res =
4973 compareWithBackedgeCondition(
SI->getCondition());
4981 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
4992 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
4993 bool IsPosBECond, ScalarEvolution &SE)
4994 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
4995 IsPositiveBECond(IsPosBECond) {}
4997 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5001 Value *BackedgeCond =
nullptr;
5003 bool IsPositiveBECond;
5006std::optional<const SCEV *>
5007SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5012 if (BackedgeCond == IC)
5015 return std::nullopt;
5020 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5021 ScalarEvolution &SE) {
5027 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5034 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5044 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5045 : SCEVRewriteVisitor(SE),
L(
L) {}
5053void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5069 const APInt &BECountAP = BECountMax->getAPInt();
5070 unsigned NoOverflowBitWidth =
5079ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5089 if (!SignedWrapViaInductionTried.insert(AR).second)
5114 AC.assumptions().empty())
5122 const SCEV *OverflowLimit =
5124 if (OverflowLimit &&
5132ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5142 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5167 AC.assumptions().empty())
5176 const SCEV *OverflowLimit =
5205 IsNSW = OBO->hasNoSignedWrap();
5206 IsNUW = OBO->hasNoUnsignedWrap();
5212 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5224 return std::nullopt;
5230 switch (
Op->getOpcode()) {
5231 case Instruction::Add:
5232 case Instruction::Sub:
5233 case Instruction::Mul:
5234 case Instruction::UDiv:
5235 case Instruction::URem:
5236 case Instruction::And:
5237 case Instruction::AShr:
5238 case Instruction::Shl:
5241 case Instruction::Or: {
5244 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5254 case Instruction::Xor:
5258 if (RHSC->getValue().isSignMask())
5259 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5261 if (V->getType()->isIntegerTy(1))
5262 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5265 case Instruction::LShr:
5274 if (SA->getValue().ult(
BitWidth)) {
5276 ConstantInt::get(SA->getContext(),
5278 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5283 case Instruction::ExtractValue: {
5285 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5293 bool Signed = WO->isSigned();
5296 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5301 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5312 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5313 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5315 return std::nullopt;
5341 if (
Op == SymbolicPHI)
5346 if (SourceBits != NewBits)
5364 if (!L || L->getHeader() != PN->
getParent())
5422std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5423ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5431 assert(L &&
"Expecting an integer loop header phi");
5436 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5437 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5438 Value *
V = PN->getIncomingValue(i);
5439 if (
L->contains(PN->getIncomingBlock(i))) {
5442 }
else if (BEValueV != V) {
5446 }
else if (!StartValueV) {
5448 }
else if (StartValueV != V) {
5449 StartValueV =
nullptr;
5453 if (!BEValueV || !StartValueV)
5454 return std::nullopt;
5456 const SCEV *BEValue =
getSCEV(BEValueV);
5463 return std::nullopt;
5467 unsigned FoundIndex =
Add->getNumOperands();
5468 Type *TruncTy =
nullptr;
5470 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5473 if (FoundIndex == e) {
5478 if (FoundIndex ==
Add->getNumOperands())
5479 return std::nullopt;
5483 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5484 if (i != FoundIndex)
5485 Ops.push_back(
Add->getOperand(i));
5491 return std::nullopt;
5544 const SCEV *StartVal =
getSCEV(StartValueV);
5545 const SCEV *PHISCEV =
5572 auto getExtendedExpr = [&](
const SCEV *Expr,
5573 bool CreateSignExtend) ->
const SCEV * {
5576 const SCEV *ExtendedExpr =
5579 return ExtendedExpr;
5587 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5588 const SCEV *ExtendedExpr) ->
bool {
5589 return Expr != ExtendedExpr &&
5593 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5594 if (PredIsKnownFalse(StartVal, StartExtended)) {
5596 return std::nullopt;
5601 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5602 if (PredIsKnownFalse(Accum, AccumExtended)) {
5604 return std::nullopt;
5607 auto AppendPredicate = [&](
const SCEV *Expr,
5608 const SCEV *ExtendedExpr) ->
void {
5609 if (Expr != ExtendedExpr &&
5617 AppendPredicate(StartVal, StartExtended);
5618 AppendPredicate(Accum, AccumExtended);
5626 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5627 std::make_pair(NewAR, Predicates);
5629 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5633std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5638 return std::nullopt;
5641 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5642 if (
I != PredicatedSCEVRewrites.end()) {
5643 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5646 if (Rewrite.first == SymbolicPHI)
5647 return std::nullopt;
5651 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5655 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5656 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5661 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5662 return std::nullopt;
5682 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5683 if (Expr1 != Expr2 &&
5684 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5685 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5720const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5722 Value *StartValueV) {
5725 assert(BEValueV && StartValueV);
5727 const SCEV *Accum =
nullptr;
5730 if (BO->Opcode != Instruction::Add)
5733 if (BO->LHS == PN &&
L->isLoopInvariant(BO->RHS))
5735 else if (BO->RHS == PN &&
L->isLoopInvariant(BO->LHS))
5749 if (!
GEP ||
GEP->getPointerOperand() != PN ||
GEP->getNumIndices() != 1)
5752 if (!
L->isLoopInvariant(Idx))
5761 const SCEV *StartVal =
getSCEV(StartValueV);
5762 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5763 insertValueToMap(PN, PHISCEV);
5766 inferNoWrapViaConstantRanges(AR);
5773 "Accum is defined outside L, but is not invariant?");
5774 if (isAddRecNeverPoison(BEInst, L))
5781const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5789 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5795 }
else if (BEValueV != V) {
5799 }
else if (!StartValueV) {
5801 }
else if (StartValueV != V) {
5802 StartValueV =
nullptr;
5806 if (!BEValueV || !StartValueV)
5809 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5810 "PHI node already processed?");
5814 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5819 insertValueToMap(PN, SymbolicName);
5823 const SCEV *BEValue =
getSCEV(BEValueV);
5833 unsigned FoundIndex =
Add->getNumOperands();
5834 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5835 if (
Add->getOperand(i) == SymbolicName)
5836 if (FoundIndex == e) {
5841 if (FoundIndex !=
Add->getNumOperands()) {
5844 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5845 if (i != FoundIndex)
5846 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5858 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5865 if (
GEP->getOperand(0) == PN)
5873 const SCEV *StartVal =
getSCEV(StartValueV);
5874 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5879 forgetMemoizedResults({SymbolicName});
5880 insertValueToMap(PN, PHISCEV);
5883 inferNoWrapViaConstantRanges(AR);
5907 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5908 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5910 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5911 const SCEV *StartVal =
getSCEV(StartValueV);
5912 if (Start == StartVal) {
5916 forgetMemoizedResults({SymbolicName});
5917 insertValueToMap(PN, Shifted);
5927 eraseValueFromMap(PN);
5942 Use &LeftUse =
Merge->getOperandUse(0);
5943 Use &RightUse =
Merge->getOperandUse(1);
5979 assert(IDom &&
"At least the entry block should dominate PN");
5987const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
5992 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6009 CommonInst = IncomingInst;
6025ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6031 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6032 bool SCEVExprsIdentical =
6034 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6035 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6038const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6039 if (
const SCEV *S = createAddRecFromPHI(PN))
6049 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6052 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6061 struct FindClosure {
6062 const SCEV *OperandToFind;
6068 bool canRecurseInto(
SCEVTypes Kind)
const {
6071 return RootKind == Kind || NonSequentialRootKind == Kind ||
6076 : OperandToFind(OperandToFind), RootKind(RootKind),
6077 NonSequentialRootKind(
6081 bool follow(
const SCEV *S) {
6082 Found = S == OperandToFind;
6084 return !isDone() && canRecurseInto(S->
getSCEVType());
6087 bool isDone()
const {
return Found; }
6090 FindClosure FC(OperandToFind, RootKind);
6095std::optional<const SCEV *>
6096ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6106 switch (ICI->getPredicate()) {
6120 bool Signed = ICI->isSigned();
6121 const SCEV *LA =
getSCEV(TrueVal);
6129 if (LA == LS &&
RA == RS)
6131 if (LA == RS &&
RA == LS)
6134 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6135 if (
Op->getType()->isPointerTy()) {
6146 LS = CoerceOperand(LS);
6147 RS = CoerceOperand(RS);
6171 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6172 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6186 X = ZExt->getOperand();
6188 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6199 return std::nullopt;
6202static std::optional<const SCEV *>
6204 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6208 "Unexpected operands of a select.");
6220 return std::nullopt;
6235static std::optional<const SCEV *>
6239 return std::nullopt;
6242 const auto *SETrue = SE->
getSCEV(TrueVal);
6243 const auto *SEFalse = SE->
getSCEV(FalseVal);
6247const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6249 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6251 V->getType() ==
TrueVal->getType() &&
6252 "Types of select hands and of the result must match.");
6255 if (!
V->getType()->isIntegerTy(1))
6258 if (std::optional<const SCEV *> S =
6271 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6275 if (std::optional<const SCEV *> S =
6276 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6282 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6288 assert(
GEP->getSourceElementType()->isSized() &&
6289 "GEP source element type must be sized");
6292 for (
Value *Index :
GEP->indices())
6297APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6300 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6303 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6305 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6308 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6326 return GetShiftedByZeros(TZ);
6336 return GetShiftedByZeros(TZ);
6340 if (
M->hasNoUnsignedWrap()) {
6343 for (
const SCEV *Operand :
M->operands().drop_front())
6351 for (
const SCEV *Operand :
M->operands())
6353 return GetShiftedByZeros(TZ);
6358 if (
N->hasNoUnsignedWrap())
6359 return GetGCDMultiple(
N);
6362 for (
const SCEV *Operand :
N->operands().drop_front())
6364 return GetShiftedByZeros(TZ);
6381 CtxI = &*F.getEntryBlock().begin();
6388 .allowEphemerals(
true))
6389 .countMinTrailingZeros();
6390 return GetShiftedByZeros(
Known);
6403 return getConstantMultipleImpl(S, CtxI);
6405 auto I = ConstantMultipleCache.find(S);
6406 if (
I != ConstantMultipleCache.end())
6409 APInt Result = getConstantMultipleImpl(S, CtxI);
6410 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6411 assert(InsertPair.second &&
"Should insert a new key");
6412 return InsertPair.first->second;
6429 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6432 if (std::optional<ConstantRange>
Range = CB->getRange())
6436 if (std::optional<ConstantRange>
Range =
A->getRange())
6439 return std::nullopt;
6446 UnsignedRanges.erase(AddRec);
6447 SignedRanges.erase(AddRec);
6448 ConstantMultipleCache.erase(AddRec);
6453getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6479 Value *Start, *Step;
6486 assert(L && L->getHeader() ==
P->getParent());
6499 case Instruction::AShr:
6500 case Instruction::LShr:
6501 case Instruction::Shl:
6516 KnownStep.getBitWidth() ==
BitWidth);
6519 auto MaxShiftAmt = KnownStep.getMaxValue();
6521 bool Overflow =
false;
6522 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6529 case Instruction::AShr: {
6537 if (KnownStart.isNonNegative())
6540 KnownStart.getMaxValue() + 1);
6541 if (KnownStart.isNegative())
6544 KnownEnd.getMaxValue() + 1);
6547 case Instruction::LShr: {
6556 KnownStart.getMaxValue() + 1);
6558 case Instruction::Shl: {
6562 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6563 return ConstantRange(KnownStart.getMinValue(),
6564 KnownEnd.getMaxValue() + 1);
6589 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6596ScalarEvolution::getRangeRefIter(
const SCEV *S,
6597 ScalarEvolution::RangeSignHint SignHint) {
6598 DenseMap<const SCEV *, ConstantRange> &Cache =
6599 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6602 SmallPtrSet<const SCEV *, 8> Seen;
6606 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6607 if (!Seen.
insert(Expr).second)
6640 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6641 const SCEV *
P = WorkList[
I];
6645 for (
const SCEV *
Op :
P->operands())
6658 if (!WorkList.
empty()) {
6663 getRangeRef(
P, SignHint);
6667 return getRangeRef(S, SignHint, 0);
6670const APInt *ScalarEvolution::getConstantAPIntOrNull(
const SCEV *S) {
6672 return &
C->getAPInt();
6680 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6681 DenseMap<const SCEV *, ConstantRange> &Cache =
6682 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6689 auto I = Cache.
find(S);
6690 if (
I != Cache.
end())
6694 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6699 return getRangeRefIter(S, SignHint);
6702 ConstantRange ConservativeResult(
BitWidth,
true);
6703 using OBO = OverflowingBinaryOperator;
6707 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6711 ConservativeResult =
6718 ConservativeResult = ConstantRange(
6734 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6741 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6748 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6753 return setRange(Cast, SignHint,
X);
6758 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6759 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6761 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6762 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6763 ConservativeResult =
6764 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6766 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6767 unsigned WrapType = OBO::AnyWrap;
6768 if (
Add->hasNoSignedWrap())
6769 WrapType |= OBO::NoSignedWrap;
6770 if (
Add->hasNoUnsignedWrap())
6771 WrapType |= OBO::NoUnsignedWrap;
6773 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6775 return setRange(
Add, SignHint,
6776 ConservativeResult.intersectWith(
X, RangeType));
6780 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6782 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6783 return setRange(
Mul, SignHint,
6784 ConservativeResult.intersectWith(
X, RangeType));
6788 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6789 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6790 return setRange(UDiv, SignHint,
6791 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6799 if (!UnsignedMinValue.
isZero())
6800 ConservativeResult = ConservativeResult.intersectWith(
6801 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6810 bool AllNonNeg =
true;
6811 bool AllNonPos =
true;
6812 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6819 ConservativeResult = ConservativeResult.intersectWith(
6824 ConservativeResult = ConservativeResult.intersectWith(
6833 const SCEV *MaxBEScev =
6847 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6849 ConservativeResult =
6850 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6853 auto RangeFromFactoring = getRangeViaFactoring(
6855 ConservativeResult =
6856 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6862 const SCEV *SymbolicMaxBECount =
6867 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6868 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6869 ConservativeResult =
6870 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6875 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6885 ID = Intrinsic::umax;
6888 ID = Intrinsic::smax;
6892 ID = Intrinsic::umin;
6895 ID = Intrinsic::smin;
6902 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6903 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6905 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6906 return setRange(S, SignHint,
6907 ConservativeResult.intersectWith(
X, RangeType));
6916 ConservativeResult =
6917 ConservativeResult.intersectWith(*MDRange, RangeType);
6922 auto CR = getRangeForUnknownRecurrence(U);
6923 ConservativeResult = ConservativeResult.intersectWith(CR);
6934 if (
U->getType()->isPointerTy()) {
6937 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
6938 int ptrIdxDiff = ptrSize -
BitWidth;
6939 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
6945 if (!
Known.Zero.getHiBits(NS).isZero())
6946 Known.Zero.setHighBits(NS);
6947 if (!
Known.One.getHiBits(NS).isZero())
6948 Known.One.setHighBits(NS);
6951 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
6952 ConservativeResult = ConservativeResult.intersectWith(
6953 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
6956 ConservativeResult = ConservativeResult.intersectWith(
6961 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6965 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
6966 DL, CanBeNull,
nullptr);
6982 ConservativeResult = ConservativeResult.intersectWith(
6992 return getRangeRef(AR, SignHint,
Depth + 1);
6996 ConstantRange RangeFromOps(
BitWidth,
false);
6998 for (
const auto &
Op :
Phi->operands()) {
7000 RangeFromOps = RangeFromOps.unionWith(OpRange);
7002 if (RangeFromOps.isFullSet())
7005 ConservativeResult =
7006 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7012 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7014 ConservativeResult = ConservativeResult.difference(Disallowed);
7017 return setRange(U, SignHint, std::move(ConservativeResult));
7023 return setRange(S, SignHint, std::move(ConservativeResult));
7031static std::pair<ConstantRange, bool>
7039 if (Step == 0 || MaxBECount == 0)
7040 return {StartRange,
true};
7046 return {ConstantRange::getFull(
BitWidth),
false};
7062 return {ConstantRange::getFull(
BitWidth),
false};
7075 APInt MovedBoundary;
7080 MovedBoundary = StartLower - std::move(
Offset);
7083 MovedBoundary = StartUpper + std::move(
Offset);
7087 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7094 if (StartRange.
contains(MovedBoundary))
7095 return {ConstantRange::getFull(
BitWidth),
false};
7098 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7100 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7108std::pair<ConstantRange, SCEV::NoWrapFlags>
7109ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7110 const APInt &MaxBECount) {
7114 "mismatched bit widths");
7123 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7125 StartSRange, MaxBECount,
7127 ConstantRange SR = SR1.unionWith(SR2);
7144ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7146 ScalarEvolution::RangeSignHint SignHint) {
7147 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7149 "This only works for non-self-wrapping AddRecs!");
7150 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7154 return ConstantRange::getFull(
BitWidth);
7162 return ConstantRange::getFull(
BitWidth);
7166 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7168 MaxItersWithoutWrap))
7169 return ConstantRange::getFull(
BitWidth);
7190 ConstantRange StartRange = getRangeRef(Start, SignHint);
7191 ConstantRange EndRange = getRangeRef(End, SignHint);
7192 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7196 return RangeBetween;
7201 return ConstantRange::getFull(
BitWidth);
7204 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7205 return RangeBetween;
7207 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7208 return RangeBetween;
7209 return ConstantRange::getFull(
BitWidth);
7214 const APInt &MaxBECount) {
7221 "mismatched bit widths");
7223 struct SelectPattern {
7224 Value *Condition =
nullptr;
7228 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7230 std::optional<unsigned> CastOp;
7244 CastOp = SCast->getSCEVType();
7245 S = SCast->getOperand();
7248 using namespace llvm::PatternMatch;
7255 Condition =
nullptr;
7287 bool isRecognized() {
return Condition !=
nullptr; }
7290 SelectPattern StartPattern(*
this,
BitWidth, Start);
7291 if (!StartPattern.isRecognized())
7292 return ConstantRange::getFull(
BitWidth);
7294 SelectPattern StepPattern(*
this,
BitWidth, Step);
7295 if (!StepPattern.isRecognized())
7296 return ConstantRange::getFull(
BitWidth);
7298 if (StartPattern.Condition != StepPattern.Condition) {
7302 return ConstantRange::getFull(
BitWidth);
7313 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7314 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7315 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7316 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7318 ConstantRange TrueRange =
7319 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7320 ConstantRange FalseRange =
7321 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7333 PDI && PDI->isDisjoint()) {
7348ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7361 SmallPtrSet<const SCEV *, 16> Visited;
7363 auto pushOp = [&](
const SCEV *S) {
7364 if (!Visited.
insert(S).second)
7367 if (Visited.
size() > 30) {
7378 while (!Worklist.
empty()) {
7380 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7381 if (!Bound || DT.dominates(Bound, DefI))
7388 return Bound ? Bound : &*F.getEntryBlock().begin();
7394 return getDefiningScopeBound(
Ops, Discard);
7397bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7399 if (
A->getParent() ==
B->getParent() &&
7404 auto *BLoop = LI.getLoopFor(
B->getParent());
7405 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7406 BLoop->getLoopPreheader() ==
A->getParent() &&
7408 A->getParent()->end()) &&
7416 SCEVPoisonCollector PC(
true);
7418 return PC.MaybePoison.
empty();
7421bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7431bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7448 for (
const Use &
Op :
I->operands()) {
7454 auto *DefI = getDefiningScopeBound(SCEVOps);
7455 return isGuaranteedToTransferExecutionTo(DefI,
I);
7458bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7460 if (isSCEVExprNeverPoison(
I))
7471 auto *ExitingBB =
L->getExitingBlock();
7475 SmallPtrSet<const Value *, 16> KnownPoison;
7484 while (!Worklist.
empty()) {
7487 for (
const Use &U :
Poison->uses()) {
7490 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7494 if (KnownPoison.
insert(PoisonUser).second)
7502ScalarEvolution::LoopProperties
7503ScalarEvolution::getLoopProperties(
const Loop *L) {
7504 using LoopProperties = ScalarEvolution::LoopProperties;
7506 auto Itr = LoopPropertiesCache.find(L);
7507 if (Itr == LoopPropertiesCache.end()) {
7510 return !
SI->isSimple();
7520 return I->mayWriteToMemory();
7523 LoopProperties LP = {
true,
7526 for (
auto *BB :
L->getBlocks())
7527 for (
auto &
I : *BB) {
7529 LP.HasNoAbnormalExits =
false;
7530 if (HasSideEffects(&
I))
7531 LP.HasNoSideEffects =
false;
7532 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7536 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7537 assert(InsertPair.second &&
"We just checked!");
7538 Itr = InsertPair.first;
7551const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7557 Stack.emplace_back(V,
false);
7558 while (!Stack.empty()) {
7559 auto E = Stack.back();
7560 Value *CurV = E.getPointer();
7568 const SCEV *CreatedSCEV =
nullptr;
7571 CreatedSCEV = createSCEV(CurV);
7576 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7580 insertValueToMap(CurV, CreatedSCEV);
7583 Stack.back().setInt(
true);
7586 Stack.emplace_back(
Op,
false);
7603 if (!DT.isReachableFromEntry(
I->getParent()))
7616 switch (BO->Opcode) {
7617 case Instruction::Add:
7618 case Instruction::Mul: {
7625 Ops.push_back(BO->
Op);
7629 Ops.push_back(BO->RHS);
7633 (BO->Opcode == Instruction::Add &&
7634 (NewBO->Opcode != Instruction::Add &&
7635 NewBO->Opcode != Instruction::Sub)) ||
7636 (BO->Opcode == Instruction::Mul &&
7637 NewBO->Opcode != Instruction::Mul)) {
7638 Ops.push_back(BO->LHS);
7643 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7646 Ops.push_back(BO->LHS);
7654 case Instruction::Sub:
7655 case Instruction::UDiv:
7656 case Instruction::URem:
7658 case Instruction::AShr:
7659 case Instruction::Shl:
7660 case Instruction::Xor:
7664 case Instruction::And:
7665 case Instruction::Or:
7669 case Instruction::LShr:
7676 Ops.push_back(BO->LHS);
7677 Ops.push_back(BO->RHS);
7681 switch (
U->getOpcode()) {
7682 case Instruction::Trunc:
7683 case Instruction::ZExt:
7684 case Instruction::SExt:
7685 case Instruction::PtrToAddr:
7686 case Instruction::PtrToInt:
7687 Ops.push_back(
U->getOperand(0));
7690 case Instruction::BitCast:
7692 Ops.push_back(
U->getOperand(0));
7697 case Instruction::SDiv:
7698 case Instruction::SRem:
7699 Ops.push_back(
U->getOperand(0));
7700 Ops.push_back(
U->getOperand(1));
7703 case Instruction::GetElementPtr:
7705 "GEP source element type must be sized");
7709 case Instruction::IntToPtr:
7712 case Instruction::PHI:
7743 Ops.push_back(CondICmp->getOperand(0));
7744 Ops.push_back(CondICmp->getOperand(1));
7764 case Instruction::Select: {
7766 auto CanSimplifyToUnknown = [
this,
U]() {
7784 if (CanSimplifyToUnknown())
7791 case Instruction::Call:
7792 case Instruction::Invoke:
7799 switch (
II->getIntrinsicID()) {
7800 case Intrinsic::abs:
7801 Ops.push_back(
II->getArgOperand(0));
7803 case Intrinsic::umax:
7804 case Intrinsic::umin:
7805 case Intrinsic::smax:
7806 case Intrinsic::smin:
7807 case Intrinsic::usub_sat:
7808 case Intrinsic::uadd_sat:
7809 Ops.push_back(
II->getArgOperand(0));
7810 Ops.push_back(
II->getArgOperand(1));
7812 case Intrinsic::start_loop_iterations:
7813 case Intrinsic::annotation:
7814 case Intrinsic::ptr_annotation:
7815 Ops.push_back(
II->getArgOperand(0));
7827const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7836 if (!DT.isReachableFromEntry(
I->getParent()))
7851 switch (BO->Opcode) {
7852 case Instruction::Add: {
7878 if (BO->Opcode == Instruction::Sub)
7886 if (BO->Opcode == Instruction::Sub)
7893 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7894 NewBO->Opcode != Instruction::Sub)) {
7904 case Instruction::Mul: {
7925 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7934 case Instruction::UDiv:
7938 case Instruction::URem:
7942 case Instruction::Sub: {
7945 Flags = getNoWrapFlagsFromUB(BO->
Op);
7950 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
7953 if (HasPtrLHS || HasPtrRHS) {
7958 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
7959 bool BothPtr) ->
const SCEV * {
7962 const SCEV *PtrSCEV =
getSCEV(PtrOp);
7972 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
7973 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
7981 case Instruction::And:
7987 if (CI->isMinusOne())
7989 const APInt &
A = CI->getValue();
7995 unsigned LZ =
A.countl_zero();
7996 unsigned TZ =
A.countr_zero();
8001 APInt EffectiveMask =
8003 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
8006 const SCEV *ShiftedLHS =
nullptr;
8010 unsigned MulZeros = OpC->getAPInt().countr_zero();
8011 unsigned GCD = std::min(MulZeros, TZ);
8016 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8038 case Instruction::Or:
8047 case Instruction::Xor:
8050 if (CI->isMinusOne())
8059 if (LBO->getOpcode() == Instruction::And &&
8060 LCI->getValue() == CI->getValue())
8061 if (
const SCEVZeroExtendExpr *Z =
8064 const SCEV *Z0 =
Z->getOperand();
8071 if (CI->getValue().isMask(Z0TySize))
8077 APInt Trunc = CI->getValue().trunc(Z0TySize);
8086 case Instruction::Shl:
8104 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8113 ConstantInt *
X = ConstantInt::get(
8119 case Instruction::AShr:
8141 const SCEV *AddTruncateExpr =
nullptr;
8142 ConstantInt *ShlAmtCI =
nullptr;
8143 const SCEV *AddConstant =
nullptr;
8145 if (L &&
L->getOpcode() == Instruction::Add) {
8153 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8160 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8168 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8173 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8178 if (AddTruncateExpr && ShlAmtCI) {
8190 const APInt &ShlAmt = ShlAmtCI->
getValue();
8194 const SCEV *CompositeExpr =
8196 if (
L->getOpcode() != Instruction::Shl)
8197 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8206 switch (
U->getOpcode()) {
8207 case Instruction::Trunc:
8210 case Instruction::ZExt:
8213 case Instruction::SExt:
8223 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8224 Type *Ty =
U->getType();
8232 case Instruction::BitCast:
8238 case Instruction::PtrToAddr: {
8245 case Instruction::PtrToInt:
8249 case Instruction::IntToPtr:
8253 case Instruction::SDiv:
8260 case Instruction::SRem:
8267 case Instruction::GetElementPtr:
8270 case Instruction::PHI:
8273 case Instruction::Select:
8274 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8277 case Instruction::Call:
8278 case Instruction::Invoke:
8283 switch (
II->getIntrinsicID()) {
8284 case Intrinsic::abs:
8288 case Intrinsic::umax:
8292 case Intrinsic::umin:
8296 case Intrinsic::smax:
8300 case Intrinsic::smin:
8304 case Intrinsic::usub_sat: {
8305 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8306 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8310 case Intrinsic::uadd_sat: {
8311 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8312 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8316 case Intrinsic::start_loop_iterations:
8317 case Intrinsic::annotation:
8318 case Intrinsic::ptr_annotation:
8322 case Intrinsic::vscale:
8342 auto *ExitCountType = ExitCount->
getType();
8343 assert(ExitCountType->isIntegerTy());
8345 1 + ExitCountType->getScalarSizeInBits());
8358 auto CanAddOneWithoutOverflow = [&]() {
8360 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8371 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8401 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8402 assert(L->isLoopExiting(ExitingBlock) &&
8403 "Exiting block must actually branch out of the loop!");
8412 const auto *MaxExitCount =
8420 L->getExitingBlocks(ExitingBlocks);
8423 if (ExitingBlocks.
empty() ||
8439 const LoopGuards &Guards) {
8443 const SCEV *TCExpr =
8451 : (
unsigned)Multiple.getZExtValue();
8455 const SCEV *ExitCount) {
8477 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8478 assert(L->isLoopExiting(ExitingBlock) &&
8479 "Exiting block must actually branch out of the loop!");
8489 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8491 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8493 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8503 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8506 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8509 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8517 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8524 return getBackedgeTakenInfo(L).getExact(L,
this);
8526 return getBackedgeTakenInfo(L).getConstantMax(
this);
8528 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8535 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8540 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8544 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8554 for (
PHINode &PN : Header->phis())
8555 if (Visited.
insert(&PN).second)
8559ScalarEvolution::BackedgeTakenInfo &
8560ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8561 auto &BTI = getBackedgeTakenInfo(L);
8562 if (BTI.hasFullInfo())
8565 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8568 return Pair.first->second;
8570 BackedgeTakenInfo
Result =
8571 computeBackedgeTakenCount(L,
true);
8573 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8576ScalarEvolution::BackedgeTakenInfo &
8577ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8583 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8584 BackedgeTakenCounts.try_emplace(L);
8586 return Pair.first->second;
8591 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8598 if (
Result.hasAnyInfo()) {
8601 auto LoopUsersIt = LoopUsers.find(L);
8602 if (LoopUsersIt != LoopUsers.end())
8604 forgetMemoizedResults(ToForget);
8607 for (PHINode &PN :
L->getHeader()->phis())
8608 ConstantEvolutionLoopExitValue.erase(&PN);
8616 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8625 BackedgeTakenCounts.clear();
8626 PredicatedBackedgeTakenCounts.clear();
8627 BECountUsers.clear();
8628 LoopPropertiesCache.clear();
8629 ConstantEvolutionLoopExitValue.clear();
8630 ValueExprMap.clear();
8631 ValuesAtScopes.clear();
8632 ValuesAtScopesUsers.clear();
8633 LoopDispositions.clear();
8634 BlockDispositions.clear();
8635 UnsignedRanges.clear();
8636 SignedRanges.clear();
8637 ExprValueMap.clear();
8639 ConstantMultipleCache.clear();
8640 PredicatedSCEVRewrites.clear();
8642 FoldCacheUser.clear();
8644void ScalarEvolution::visitAndClearUsers(
8648 while (!Worklist.
empty()) {
8655 if (It != ValueExprMap.
end()) {
8657 eraseValueFromMap(It->first);
8659 ConstantEvolutionLoopExitValue.erase(PN);
8673 while (!LoopWorklist.
empty()) {
8677 forgetBackedgeTakenCounts(CurrL,
false);
8678 forgetBackedgeTakenCounts(CurrL,
true);
8681 PredicatedSCEVRewrites.remove_if(
8682 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8684 auto LoopUsersItr = LoopUsers.find(CurrL);
8685 if (LoopUsersItr != LoopUsers.end())
8690 visitAndClearUsers(Worklist, Visited, ToForget);
8692 LoopPropertiesCache.erase(CurrL);
8695 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8697 forgetMemoizedResults(ToForget);
8714 visitAndClearUsers(Worklist, Visited, ToForget);
8716 forgetMemoizedResults(ToForget);
8727 visitAndClearUsers(Worklist, Visited, ToForget);
8729 forgetMemoizedResults(ToForget);
8737 auto InvalidateValue = [&](
Value *Val) {
8741 struct InvalidationRootCollector {
8745 InvalidationRootCollector(
Loop *L) : L(L) {}
8747 bool follow(
const SCEV *S) {
8753 if (L->contains(AddRec->
getLoop()))
8758 bool isDone()
const {
return false; }
8761 InvalidationRootCollector
C(L);
8763 forgetMemoizedResults(
C.Roots);
8786 BlockDispositions.clear();
8787 LoopDispositions.clear();
8804 while (!Worklist.
empty()) {
8806 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8807 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8808 if (!LoopDispoRemoved && !BlockDispoRemoved)
8810 auto Users = SCEVUsers.find(Curr);
8811 if (
Users != SCEVUsers.end())
8824const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8828 if (!isComplete() || ExitNotTaken.
empty())
8839 for (
const auto &ENT : ExitNotTaken) {
8840 const SCEV *BECount = ENT.ExactNotTaken;
8843 "We should only have known counts for exiting blocks that dominate "
8846 Ops.push_back(BECount);
8851 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8852 "Predicate should be always true!");
8861const ScalarEvolution::ExitNotTakenInfo *
8862ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8863 const BasicBlock *ExitingBlock,
8864 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8865 for (
const auto &ENT : ExitNotTaken)
8866 if (ENT.ExitingBlock == ExitingBlock) {
8867 if (ENT.hasAlwaysTruePredicate())
8869 else if (Predicates) {
8879const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8881 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8882 if (!getConstantMax())
8885 for (
const auto &ENT : ExitNotTaken)
8886 if (!ENT.hasAlwaysTruePredicate()) {
8894 "No point in having a non-constant max backedge taken count!");
8895 return getConstantMax();
8898const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8900 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8908 for (
const auto &ENT : ExitNotTaken) {
8909 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8912 "We should only have known counts for exiting blocks that "
8918 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8919 "Predicate should be always true!");
8922 if (ExitCounts.
empty())
8931bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8933 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8934 return !ENT.hasAlwaysTruePredicate();
8936 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8952 this->ExactNotTaken = E = ConstantMaxNotTaken;
8953 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8958 "Exact is not allowed to be less precise than Constant Max");
8961 "Exact is not allowed to be less precise than Symbolic Max");
8964 "Symbolic Max is not allowed to be less precise than Constant Max");
8967 "No point in having a non-constant max backedge taken count!");
8969 for (
const auto PredList : PredLists)
8970 for (
const auto *
P : PredList) {
8978 "Backedge count should be int");
8981 "Max backedge count should be int");
8994ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8996 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8997 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8998 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9000 ExitNotTaken.reserve(ExitCounts.
size());
9001 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
9002 std::back_inserter(ExitNotTaken),
9003 [&](
const EdgeExitInfo &EEI) {
9004 BasicBlock *ExitBB = EEI.first;
9005 const ExitLimit &EL = EEI.second;
9006 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
9007 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
9012 "No point in having a non-constant max backedge taken count!");
9016ScalarEvolution::BackedgeTakenInfo
9017ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
9018 bool AllowPredicates) {
9020 L->getExitingBlocks(ExitingBlocks);
9022 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9025 bool CouldComputeBECount =
true;
9027 const SCEV *MustExitMaxBECount =
nullptr;
9028 const SCEV *MayExitMaxBECount =
nullptr;
9029 bool MustExitMaxOrZero =
false;
9030 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9041 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9042 if (ExitIfTrue == CI->
isZero())
9046 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9048 assert((AllowPredicates || EL.Predicates.empty()) &&
9049 "Predicated exit limit when predicates are not allowed!");
9054 ++NumExitCountsComputed;
9058 CouldComputeBECount =
false;
9065 "Exact is known but symbolic isn't?");
9066 ++NumExitCountsNotComputed;
9081 DT.dominates(ExitBB, Latch)) {
9082 if (!MustExitMaxBECount) {
9083 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9084 MustExitMaxOrZero = EL.MaxOrZero;
9087 EL.ConstantMaxNotTaken);
9091 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9094 EL.ConstantMaxNotTaken);
9098 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9102 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9108 for (
const auto &Pair : ExitCounts) {
9110 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9112 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9113 {
L, AllowPredicates});
9115 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9116 MaxBECount, MaxOrZero);
9119ScalarEvolution::ExitLimit
9120ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9121 bool IsOnlyExit,
bool AllowPredicates) {
9122 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9126 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9131 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9132 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9133 "It should have one successor in loop and one exit block!");
9144 if (!
L->contains(SBB)) {
9149 assert(Exit &&
"Exiting block must have at least one exit");
9150 return computeExitLimitFromSingleExitSwitch(
9151 L, SI, Exit, IsOnlyExit);
9158 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9159 bool AllowPredicates) {
9160 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9161 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9162 ControlsOnlyExit, AllowPredicates);
9165std::optional<ScalarEvolution::ExitLimit>
9166ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9167 bool ExitIfTrue,
bool ControlsOnlyExit,
9168 bool AllowPredicates) {
9170 (void)this->ExitIfTrue;
9171 (void)this->AllowPredicates;
9173 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9174 this->AllowPredicates == AllowPredicates &&
9175 "Variance in assumed invariant key components!");
9176 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9177 if (Itr == TripCountMap.end())
9178 return std::nullopt;
9182void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9184 bool ControlsOnlyExit,
9185 bool AllowPredicates,
9187 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9188 this->AllowPredicates == AllowPredicates &&
9189 "Variance in assumed invariant key components!");
9191 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9192 assert(InsertResult.second &&
"Expected successful insertion!");
9197ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9198 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9199 bool ControlsOnlyExit,
bool AllowPredicates) {
9201 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9205 ExitLimit EL = computeExitLimitFromCondImpl(
9206 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9207 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9211ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9212 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9213 bool ControlsOnlyExit,
bool AllowPredicates) {
9215 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9216 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9217 return *LimitFromBinOp;
9223 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9224 if (EL.hasFullInfo() || !AllowPredicates)
9228 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9248 const WithOverflowInst *WO;
9263 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9264 ControlsOnlyExit, AllowPredicates);
9265 if (EL.hasAnyInfo())
9270 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9273std::optional<ScalarEvolution::ExitLimit>
9274ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9278 bool AllowPredicates) {
9287 return std::nullopt;
9291 ExitLimit EL0 = computeExitLimitFromCondCached(
9292 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9293 ExitLimit EL1 = computeExitLimitFromCondCached(
9294 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9299 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9304 if (EitherMayExit) {
9314 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9316 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9319 EL1.ConstantMaxNotTaken);
9321 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9323 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9326 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9330 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9331 BECount = EL0.ExactNotTaken;
9344 SymbolicMaxBECount =
9346 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9350ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9351 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9352 bool AllowPredicates) {
9364 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9366 if (EL.hasAnyInfo())
9369 auto *ExhaustiveCount =
9370 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9373 return ExhaustiveCount;
9375 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9378ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9380 bool ControlsOnlyExit,
bool AllowPredicates) {
9405 ConstantRange CompRange =
9423 InnerLHS = ZExt->getOperand();
9470 if (EL.hasAnyInfo())
9487 if (EL.hasAnyInfo())
return EL;
9519 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9521 if (EL.hasAnyInfo())
9537 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9539 if (EL.hasAnyInfo())
9550ScalarEvolution::ExitLimit
9551ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9553 BasicBlock *ExitingBlock,
9554 bool ControlsOnlyExit) {
9555 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9558 if (
Switch->getDefaultDest() == ExitingBlock)
9562 "Default case must not exit the loop!");
9568 if (EL.hasAnyInfo())
9580 "Evaluation of SCEV at constant didn't fold correctly?");
9584ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9594 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9601 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9603 unsigned &OutShiftAmt) {
9604 using namespace PatternMatch;
9606 ConstantInt *ShiftAmt;
9608 OutOpCode = Instruction::LShr;
9610 OutOpCode = Instruction::AShr;
9612 OutOpCode = Instruction::Shl;
9617 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9632 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9634 unsigned &ShiftAmtOut) {
9635 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9651 if (MatchPositiveShift(
LHS, V, OpC, Amt)) {
9652 PostShiftOpCode = OpC;
9658 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9661 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9667 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9674 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9680 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9692 ConstantInt *StableValue =
nullptr;
9697 case Instruction::AShr: {
9704 if (
Known.isNonNegative())
9705 StableValue = ConstantInt::get(Ty, 0);
9706 else if (
Known.isNegative())
9707 StableValue = ConstantInt::get(Ty, -1,
true);
9713 case Instruction::LShr:
9714 case Instruction::Shl:
9724 "Otherwise cannot be an operand to a branch instruction");
9726 if (
Result->isNullValue()) {
9735 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9737 const SCEV *StartSCEV =
getSCEV(StartValue);
9741 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9742 MaxBTC = std::min(MaxBTC, RangeBTC);
9746 const SCEV *UpperBound =
9764 if (
const Function *
F = CI->getCalledFunction())
9774 if (!L->contains(
I))
return false;
9779 return L->getHeader() ==
I->getParent();
9858 if (!
I)
return nullptr;
9872 std::vector<Constant*>
Operands(
I->getNumOperands());
9874 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9883 if (!
C)
return nullptr;
9905 if (IncomingVal != CurrentVal) {
9908 IncomingVal = CurrentVal;
9920ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9923 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9932 DenseMap<Instruction *, Constant *> CurrentIterVals;
9934 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9940 for (PHINode &
PHI : Header->phis()) {
9942 CurrentIterVals[&
PHI] = StartCST;
9944 if (!CurrentIterVals.
count(PN))
9945 return RetVal =
nullptr;
9951 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9954 unsigned IterationNum = 0;
9956 for (; ; ++IterationNum) {
9957 if (IterationNum == NumIterations)
9958 return RetVal = CurrentIterVals[PN];
9962 DenseMap<Instruction *, Constant *> NextIterVals;
9967 NextIterVals[PN] = NextPHI;
9969 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9975 for (
const auto &
I : CurrentIterVals) {
9977 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9982 for (
const auto &
I : PHIsToCompute) {
9983 PHINode *
PHI =
I.first;
9986 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9989 if (NextPHI !=
I.second)
9990 StoppedEvolving =
false;
9995 if (StoppedEvolving)
9996 return RetVal = CurrentIterVals[PN];
9998 CurrentIterVals.swap(NextIterVals);
10002const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
10012 DenseMap<Instruction *, Constant *> CurrentIterVals;
10014 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10017 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
10019 for (PHINode &
PHI : Header->phis()) {
10021 CurrentIterVals[&
PHI] = StartCST;
10023 if (!CurrentIterVals.
count(PN))
10031 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10038 if (CondVal->getValue() ==
uint64_t(ExitWhen)) {
10039 ++NumBruteForceTripCountsComputed;
10044 DenseMap<Instruction *, Constant *> NextIterVals;
10050 for (
const auto &
I : CurrentIterVals) {
10052 if (!
PHI ||
PHI->getParent() != Header)
continue;
10055 for (PHINode *
PHI : PHIsToCompute) {
10057 if (NextPHI)
continue;
10059 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10062 CurrentIterVals.
swap(NextIterVals);
10070 auto &
Values = ValuesAtScopes[V];
10074 return LS.second ? LS.second :
SCEVUse(V);
10076 Values.emplace_back(L,
nullptr);
10079 SCEVUse C = computeSCEVAtScope(V, L);
10080 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10081 if (LS.first == L) {
10087 ValuesAtScopesUsers[
C.getPointer()].push_back({L, V});
10098 switch (V->getSCEVType()) {
10131 assert(!
C->getType()->isPointerTy() &&
10132 "Can only have one pointer, and it must be last");
10157const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10158 SmallVectorImpl<SCEVUse> &NewOps) {
10192SCEVUse ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10193 switch (
V->getSCEVType()) {
10204 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10215 for (++i; i !=
e; ++i)
10255 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10265 for (++i; i !=
e; ++i) {
10270 return getWithOperands(V, NewOps);
10285 const Loop *CurrLoop = this->LI[
I->getParent()];
10296 if (BackedgeTakenCount->
isZero()) {
10297 Value *InitValue =
nullptr;
10298 bool MultipleInitValues =
false;
10304 MultipleInitValues =
true;
10309 if (!MultipleInitValues && InitValue)
10318 unsigned InLoopPred =
10329 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10343 SmallVector<Constant *, 4>
Operands;
10345 bool MadeImprovement =
false;
10360 MadeImprovement |= OrigV != OpV;
10365 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10370 if (!MadeImprovement)
10391const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10393 return stripInjectiveFunctions(ZExt->getOperand());
10395 return stripInjectiveFunctions(SExt->getOperand());
10413 assert(
A != 0 &&
"A must be non-zero.");
10429 if (MinTZ < Mult2 && L->getLoopPredecessor())
10431 if (MinTZ < Mult2) {
10454 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10474static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10480 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10481 << *AddRec <<
'\n');
10484 if (!LC || !MC || !
NC) {
10485 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10486 return std::nullopt;
10492 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10500 N =
N.sext(NewWidth);
10501 M = M.sext(NewWidth);
10502 L = L.sext(NewWidth);
10519 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10520 <<
", multiplied by " <<
T <<
'\n');
10529 std::optional<APInt>
Y) {
10531 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10534 return XW.
slt(YW) ? *
X : *
Y;
10537 return std::nullopt;
10538 return X ? *
X : *
Y;
10555 return std::nullopt;
10556 unsigned W =
X->getBitWidth();
10576static std::optional<APInt>
10582 return std::nullopt;
10585 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10586 std::optional<APInt>
X =
10589 return std::nullopt;
10594 return std::nullopt;
10609static std::optional<APInt>
10613 "Starting value of addrec should be 0");
10614 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10615 <<
Range <<
", addrec " << *AddRec <<
'\n');
10619 "Addrec's initial value should be in range");
10625 return std::nullopt;
10635 auto SolveForBoundary =
10636 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10639 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10640 << Bound <<
" (before multiplying by " << M <<
")\n");
10643 std::optional<APInt> SO;
10646 "signed overflow\n");
10650 "unsigned overflow\n");
10651 std::optional<APInt> UO =
10654 auto LeavesRange = [&] (
const APInt &
X) {
10657 if (
Range.contains(V0->getValue()))
10662 if (
Range.contains(
V1->getValue()))
10671 return {std::nullopt,
false};
10676 if (LeavesRange(*Min))
10677 return { Min,
true };
10678 std::optional<APInt> Max = Min == SO ? UO : SO;
10679 if (LeavesRange(*Max))
10680 return { Max,
true };
10683 return {std::nullopt,
true};
10690 auto SL = SolveForBoundary(
Lower);
10691 auto SU = SolveForBoundary(
Upper);
10694 if (!SL.second || !SU.second)
10695 return std::nullopt;
10738ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10740 bool ControlsOnlyExit,
10741 bool AllowPredicates) {
10752 if (
C->getValue()->isZero())
return C;
10756 const SCEVAddRecExpr *AddRec =
10759 if (!AddRec && AllowPredicates)
10765 if (!AddRec || AddRec->
getLoop() != L)
10776 return ExitLimit(R, R, R,
false, Predicates);
10834 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10864 const SCEV *
Exact =
10872 const SCEV *SymbolicMax =
10874 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10883 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10891 return ExitLimit(
E, M, S,
false, Predicates);
10894ScalarEvolution::ExitLimit
10895ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10903 if (!
C->getValue()->isZero())
10913std::pair<const BasicBlock *, const BasicBlock *>
10914ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10925 if (
const Loop *L = LI.getLoopFor(BB))
10926 return {
L->getLoopPredecessor(),
L->getHeader()};
10928 return {
nullptr, BB};
10937 if (
A ==
B)
return true;
10952 if (ComputesEqualValues(AI, BI))
10960 const SCEV *Op0, *Op1;
10979 auto TrivialCase = [&](
bool TriviallyTrue) {
10988 const SCEV *NewLHS, *NewRHS;
11012 return TrivialCase(
false);
11013 return TrivialCase(
true);
11032 RAdd->hasNoSignedWrap()) ||
11034 RAdd->hasNoUnsignedWrap())) {
11054 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
11055 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
11058 C->getAPInt().isStrictlyPositive()) ||
11082 const APInt &
RA = RC->getAPInt();
11084 bool SimplifiedByConstantRange =
false;
11089 return TrivialCase(
true);
11091 return TrivialCase(
false);
11100 Changed = SimplifiedByConstantRange =
true;
11104 if (!SimplifiedByConstantRange) {
11121 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11127 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11133 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11139 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11159 return TrivialCase(
true);
11161 return TrivialCase(
false);
11266 auto NonRecursive = [OrNegative](
const SCEV *S) {
11268 return C->getAPInt().isPowerOf2() ||
11269 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11275 if (NonRecursive(S))
11285 const SCEV *S, uint64_t M,
11301 APInt C = Cst->getAPInt();
11302 return C.urem(M) == 0;
11310 const SCEV *SmodM =
11328 for (
auto *
A : *Predicates)
11329 if (
A->implies(
P, *
this))
11342std::pair<const SCEV *, const SCEV *>
11345 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11347 return { Start, Start };
11349 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11358 getUsedLoops(LHS, LoopsUsed);
11359 getUsedLoops(RHS, LoopsUsed);
11361 if (LoopsUsed.
empty())
11366 for (
const auto *L1 : LoopsUsed)
11367 for (
const auto *L2 : LoopsUsed)
11368 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11369 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11370 "Domination relationship is not a linear order");
11400 SplitRHS.second) &&
11410 isKnownPredicateViaSplitting(Pred, LHS, RHS) ||
11411 isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11421 return std::nullopt;
11436 if (KnownWithoutContext)
11437 return KnownWithoutContext;
11444 return std::nullopt;
11450 const Loop *L = LHS->getLoop();
11455std::optional<ScalarEvolution::MonotonicPredicateType>
11458 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11464 auto ResultSwapped =
11467 assert(*ResultSwapped != *Result &&
11468 "monotonicity should flip as we flip the predicate");
11475std::optional<ScalarEvolution::MonotonicPredicateType>
11476ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11490 return std::nullopt;
11494 "Should be greater or less!");
11498 if (!LHS->hasNoUnsignedWrap())
11499 return std::nullopt;
11503 "Relational predicate is either signed or unsigned!");
11504 if (!
LHS->hasNoSignedWrap())
11505 return std::nullopt;
11507 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11515 return std::nullopt;
11518std::optional<ScalarEvolution::LoopInvariantPredicate>
11525 return std::nullopt;
11532 if (!ArLHS || ArLHS->
getLoop() != L)
11533 return std::nullopt;
11537 return std::nullopt;
11563 return std::nullopt;
11600 return std::nullopt;
11603std::optional<ScalarEvolution::LoopInvariantPredicate>
11608 Pred, LHS, RHS, L, CtxI, MaxIter))
11618 Pred, LHS, RHS, L, CtxI,
Op))
11620 return std::nullopt;
11623std::optional<ScalarEvolution::LoopInvariantPredicate>
11638 return std::nullopt;
11645 if (!AR || AR->
getLoop() != L)
11646 return std::nullopt;
11651 Pred = Pred.dropSameSign();
11655 return std::nullopt;
11661 if (Step != One && Step != MinusOne)
11662 return std::nullopt;
11668 return std::nullopt;
11674 return std::nullopt;
11682 if (Step == MinusOne)
11686 return std::nullopt;
11692bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11698 auto CheckRange = [&](
bool IsSigned) {
11701 return RangeLHS.
icmp(Pred, RangeRHS);
11710 if (CheckRange(
true) || CheckRange(
false))
11719bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11728 SCEVUse XNonConstOp, XConstOp;
11729 SCEVUse YNonConstOp, YConstOp;
11733 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11736 XFlagsPresent = ExpectedFlags;
11741 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11744 YFlagsPresent = ExpectedFlags;
11747 if (YNonConstOp != XNonConstOp)
11755 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11758 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11818bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11839bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11840 const SCEV *
LHS,
const SCEV *
RHS) {
11845 return any_of(*BB, [&](
const Instruction &
I) {
11846 using namespace llvm::PatternMatch;
11851 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11865 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11870 "This cannot be done on broken IR!");
11873 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11882 if (LoopContinuePredicate &&
11883 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11884 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11889 if (WalkingBEDominatingConds)
11895 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11896 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11903 const SCEV *LoopCounter =
11911 for (
auto &AssumeVH : AC.assumptions()) {
11918 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11922 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11925 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11926 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11927 assert(DTN &&
"should reach the loop header before reaching the root!");
11930 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11948 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
11961 if (!DT.isReachableFromEntry(BB))
11965 "This cannot be done on broken IR!");
11973 const bool ProvingStrictComparison =
11975 bool ProvedNonStrictComparison =
false;
11976 bool ProvedNonEquality =
false;
11979 if (!ProvedNonStrictComparison)
11980 ProvedNonStrictComparison = Fn(NonStrictPredicate);
11981 if (!ProvedNonEquality)
11983 if (ProvedNonStrictComparison && ProvedNonEquality)
11988 if (ProvingStrictComparison) {
11990 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
11992 if (SplitAndProve(ProofFn))
11997 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
11999 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
12001 if (ProvingStrictComparison) {
12003 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
12005 if (SplitAndProve(ProofFn))
12014 const Loop *ContainingLoop = LI.getLoopFor(BB);
12016 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
12020 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
12021 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
12024 if (!BlockEntryPredicate)
12033 for (
auto &AssumeVH : AC.assumptions()) {
12037 if (!DT.dominates(CI, BB))
12040 if (ProveViaCond(CI->getArgOperand(0),
false))
12046 F.getParent(), Intrinsic::experimental_guard);
12048 for (
const auto *GU : GuardDecl->users())
12050 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12051 if (ProveViaCond(Guard->getArgOperand(0),
false))
12066 "LHS is not available at Loop Entry");
12068 "RHS is not available at Loop Entry");
12070 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12081 if (FoundCondValue ==
12085 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12089 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12092 const Value *Op0, *Op1;
12095 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12099 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12100 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12104 if (!ICI)
return false;
12108 CmpPredicate FoundPred;
12117 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12120bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12121 const SCEV *
RHS, CmpPredicate FoundPred,
12122 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12123 const Instruction *CtxI) {
12133 auto *WideType = FoundLHS->
getType();
12145 TruncFoundLHS, TruncFoundRHS, CtxI))
12171 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12175bool ScalarEvolution::isImpliedCondBalancedTypes(
12180 "Types should be balanced!");
12187 if (FoundLHS == FoundRHS)
12191 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12203 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12220 LHS, FoundLHS, FoundRHS, CtxI);
12222 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12244 assert(P1 != P2 &&
"Handled earlier!");
12248 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12252 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12255 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12256 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12257 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12262 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12273 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12274 CanonicalRHS, CanonicalFoundLHS,
12275 CanonicalFoundRHS);
12280 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12281 CanonicalRHS, CanonicalFoundLHS,
12282 CanonicalFoundRHS);
12289 const SCEVConstant *
C =
nullptr;
12290 const SCEV *
V =
nullptr;
12308 if (Min ==
C->getAPInt()) {
12313 APInt SharperMin = Min + 1;
12316 case ICmpInst::ICMP_SGE:
12317 case ICmpInst::ICMP_UGE:
12320 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12325 case ICmpInst::ICMP_SGT:
12326 case ICmpInst::ICMP_UGT:
12336 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12341 case ICmpInst::ICMP_SLE:
12342 case ICmpInst::ICMP_ULE:
12343 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12344 LHS, V, getConstant(SharperMin), CtxI))
12348 case ICmpInst::ICMP_SLT:
12349 case ICmpInst::ICMP_ULT:
12350 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12351 LHS, V, getConstant(Min), CtxI))
12365 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12369 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12372 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12388std::optional<APInt>
12395 APInt DiffMul(BW, 1);
12398 for (
unsigned I = 0;
I < 8; ++
I) {
12407 if (LAR->getLoop() != MAR->getLoop())
12408 return std::nullopt;
12412 if (!LAR->isAffine() || !MAR->isAffine())
12413 return std::nullopt;
12415 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12416 return std::nullopt;
12418 Less = LAR->getStart();
12419 More = MAR->getStart();
12424 auto MatchConstMul =
12425 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12430 return std::nullopt;
12432 if (
auto MatchedMore = MatchConstMul(More)) {
12433 if (
auto MatchedLess = MatchConstMul(
Less)) {
12434 if (MatchedMore->second == MatchedLess->second) {
12435 More = MatchedMore->first;
12436 Less = MatchedLess->first;
12437 DiffMul *= MatchedMore->second;
12448 Diff +=
C->getAPInt() * DiffMul;
12451 Diff -=
C->getAPInt() * DiffMul;
12454 Multiplicity[S] +=
Mul;
12456 auto Decompose = [&](
const SCEV *S,
int Mul) {
12463 Decompose(More, 1);
12464 Decompose(
Less, -1);
12468 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12469 for (
const auto &[S,
Mul] : Multiplicity) {
12474 return std::nullopt;
12476 }
else if (
Mul == -1) {
12478 return std::nullopt;
12481 return std::nullopt;
12485 if (NewMore == More || NewLess ==
Less)
12486 return std::nullopt;
12492 if (!More && !
Less)
12496 if (!More || !
Less)
12497 return std::nullopt;
12501 return std::nullopt;
12504bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12526 const auto *Latch = L->getLoopLatch();
12529 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12538 const auto *Latch = L->getLoopLatch();
12541 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12551bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12554 const SCEV *FoundLHS,
12555 const SCEV *FoundRHS) {
12564 if (!AddRecFoundLHS)
12571 const Loop *
L = AddRecFoundLHS->getLoop();
12572 if (L != AddRecLHS->getLoop())
12611 if (!RDiff || *LDiff != *RDiff)
12614 if (LDiff->isMinValue())
12617 APInt FoundRHSLimit;
12620 FoundRHSLimit = -(*RDiff);
12632bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12633 const SCEV *
RHS,
const SCEV *FoundLHS,
12634 const SCEV *FoundRHS,
unsigned Depth) {
12635 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12639 bool Erased = PendingMerges.erase(LPhi);
12640 assert(Erased &&
"Failed to erase LPhi!");
12644 bool Erased = PendingMerges.erase(RPhi);
12645 assert(Erased &&
"Failed to erase RPhi!");
12653 if (!PendingMerges.insert(Phi).second)
12667 if (!PendingMerges.insert(Phi).second)
12673 if (!LPhi && !RPhi)
12684 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12688 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12689 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12690 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12691 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12694 if (RPhi && RPhi->getParent() == LBB) {
12701 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12702 if (!ProvedEasily(L, R))
12713 auto *RLoop = RAR->
getLoop();
12714 auto *Predecessor = RLoop->getLoopPredecessor();
12715 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12717 if (!ProvedEasily(L1, RAR->
getStart()))
12719 auto *Latch = RLoop->getLoopLatch();
12720 assert(Latch &&
"Loop with AddRec with no latch?");
12741 if (
auto *
Loop = LI.getLoopFor(LBB))
12744 if (!ProvedEasily(L,
RHS))
12751bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12754 const SCEV *FoundLHS,
12755 const SCEV *FoundRHS) {
12758 if (
RHS == FoundRHS) {
12763 if (
LHS != FoundLHS)
12770 Value *Shiftee, *ShiftValue;
12772 using namespace PatternMatch;
12773 if (
match(SUFoundRHS->getValue(),
12775 auto *ShifteeS =
getSCEV(Shiftee);
12793bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12794 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12795 const SCEV *FoundRHS) {
12827 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12835 return Diff == FoundDiff;
12838bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12840 const SCEV *FoundLHS,
12841 const SCEV *FoundRHS,
12842 const Instruction *CtxI) {
12843 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12845 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12847 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12848 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12850 isImpliedCondOperandsViaMatchingDiff(Pred,
LHS,
RHS, FoundLHS,
12852 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12856template <
typename MinMaxExprType>
12858 const SCEV *Candidate) {
12863 return is_contained(MinMaxExpr->operands(), Candidate);
12876 const SCEV *LStart, *RStart, *Step;
12974bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12976 const SCEV *FoundLHS,
12977 const SCEV *FoundRHS,
12981 "LHS and RHS have different sizes?");
12984 "FoundLHS and FoundRHS have different sizes?");
13018 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
13020 return Ext->getOperand();
13027 auto *OrigLHS =
LHS;
13028 auto *OrigFoundLHS = FoundLHS;
13029 LHS = GetOpFromSExt(
LHS);
13030 FoundLHS = GetOpFromSExt(FoundLHS);
13033 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
13036 FoundRHS,
Depth + 1);
13049 if (!LHSAddExpr->hasNoSignedWrap())
13052 SCEVUse LL = LHSAddExpr->getOperand(0);
13053 SCEVUse LR = LHSAddExpr->getOperand(1);
13057 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
13058 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
13063 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
13069 using namespace llvm::PatternMatch;
13088 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13096 auto *DTy = Denominator->getType();
13097 auto *FRHSTy = FoundRHS->
getType();
13098 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13117 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13128 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13130 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13138 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13171bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13175 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13179 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13182bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13185 const SCEV *FoundLHS,
13186 const SCEV *FoundRHS) {
13222 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13228bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13229 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13230 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13244 ConstantRange FoundLHSRange =
13248 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13255 return LHSRange.
icmp(Pred, ConstRHS);
13258bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13271 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13279 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13282bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
13294 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
13302 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
13314const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
13315 const SCEV *Stride,
13346 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13357 :
APIntOps::umax(MaxEnd, MinStart);
13364ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13365 const Loop *L,
bool IsSigned,
13366 bool ControlsOnlyExit,
bool AllowPredicates) {
13370 bool PredicatedIV =
false;
13375 auto canProveNUW = [&]() {
13378 if (!ControlsOnlyExit)
13399 Limit = Limit.
zext(OuterBitWidth);
13411 Type *Ty = ZExt->getType();
13422 if (!
IV && AllowPredicates) {
13427 PredicatedIV =
true;
13431 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13445 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13448 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13453 bool IVMayOverflow =
true;
13456 if (!PositiveStride) {
13508 auto wouldZeroStrideBeUB = [&]() {
13520 if (!wouldZeroStrideBeUB()) {
13527 IVMayOverflow = canIVOverflowOnLT(
RHS, Stride, IsSigned);
13528 if (IVMayOverflow && !NoWrap)
13541 const SCEV *
Start =
IV->getStart();
13547 const SCEV *OrigStart =
Start;
13548 const SCEV *OrigRHS =
RHS;
13549 if (
Start->getType()->isPointerTy()) {
13564 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13565 any(RHSAddRec->getNoWrapFlags())) {
13578 const SCEV *RHSStart = RHSAddRec->getStart();
13579 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13591 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13600 BECountIfBackedgeTaken =
13626 bool AddingStrideMinusOneMayOverflow = IVMayOverflow && [&] {
13672 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13685 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13692 if ((!AddingStrideMinusOneMayOverflow ||
13724 const SCEV *Numerator =
13730 auto canProveRHSGreaterThanEqualStart = [&]() {
13749 auto *StartMinusOne =
13756 if (canProveRHSGreaterThanEqualStart()) {
13771 BECountIfBackedgeTaken =
13776 if (!AddingStrideMinusOneMayOverflow) {
13788 const SCEV *ConstantMaxBECount;
13789 bool MaxOrZero =
false;
13791 ConstantMaxBECount = BECount;
13796 ConstantMaxBECount = BECountIfBackedgeTaken;
13799 ConstantMaxBECount = computeMaxBECountForLT(
13807 const SCEV *SymbolicMaxBECount =
13809 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13813ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13814 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13815 bool ControlsOnlyExit,
bool AllowPredicates) {
13822 if (!
IV && AllowPredicates)
13829 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13833 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13846 bool MayAddOverflow =
false;
13847 const SCEV *
Start =
IV->getStart();
13848 const SCEV *End =
RHS;
13849 if (!Stride->
isOne() && canIVOverflowOnGT(
RHS, Stride, IsSigned)) {
13852 MayAddOverflow =
true;
13865 if (
Start->getType()->isPointerTy()) {
13877 const SCEV *BECount;
13878 if (MayAddOverflow) {
13909 const SCEV *ConstantMaxBECount =
13916 ConstantMaxBECount = BECount;
13917 const SCEV *SymbolicMaxBECount =
13920 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13926 if (
Range.isFullSet())
13931 if (!SC->getValue()->isZero()) {
13937 return ShiftedAddRec->getNumIterationsInRange(
13938 Range.subtract(SC->getAPInt()), SE);
13969 APInt ExitVal = (End +
A).udiv(
A);
13982 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13983 "Linear scev computation is off in a bad way!");
14014 assert(!
Last->isZero() &&
"Recurrency with zero step?");
14040 Ty =
Store->getValueOperand()->getType();
14041 PtrTy =
Store->getPointerOperandType();
14043 Ty =
Load->getType();
14044 PtrTy =
Load->getPointerOperandType();
14058 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14060 SE->ConstantEvolutionLoopExitValue.erase(PN);
14061 SE->eraseValueFromMap(getValPtr());
14065void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
14066 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14076 : CallbackVH(
V), SE(se) {}
14085 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
14087 LoopDispositions(64), BlockDispositions(64) {
14099 F.getParent(), Intrinsic::experimental_guard);
14100 HasGuards = GuardDecl && !GuardDecl->use_empty();
14104 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
14105 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14106 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14107 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14108 PendingMerges(
std::
move(Arg.PendingMerges)),
14109 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14110 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14111 PredicatedBackedgeTakenCounts(
14112 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14113 BECountUsers(
std::
move(Arg.BECountUsers)),
14114 ConstantEvolutionLoopExitValue(
14115 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14116 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14117 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14118 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14119 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14120 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14121 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14122 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14123 SignedRanges(
std::
move(Arg.SignedRanges)),
14124 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14125 UniquePreds(
std::
move(Arg.UniquePreds)),
14126 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14127 ConstantSCEVs(
std::
move(Arg.ConstantSCEVs)),
14128 LoopUsers(
std::
move(Arg.LoopUsers)),
14129 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14130 FirstUnknown(Arg.FirstUnknown) {
14131 Arg.FirstUnknown =
nullptr;
14140 Tmp->~SCEVUnknown();
14142 FirstUnknown =
nullptr;
14144 ExprValueMap.clear();
14145 ValueExprMap.clear();
14147 BackedgeTakenCounts.clear();
14148 PredicatedBackedgeTakenCounts.clear();
14150 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14151 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14152 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14153 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14175 L->getHeader()->printAsOperand(OS,
false);
14179 L->getExitingBlocks(ExitingBlocks);
14180 if (ExitingBlocks.
size() != 1)
14181 OS <<
"<multiple exits> ";
14185 OS <<
"backedge-taken count is ";
14188 OS <<
"Unpredictable backedge-taken count.";
14191 if (ExitingBlocks.
size() > 1)
14192 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14193 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14201 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14204 OS <<
"\n Predicates:\n";
14205 for (
const auto *
P : Predicates)
14213 L->getHeader()->printAsOperand(OS,
false);
14218 OS <<
"constant max backedge-taken count is ";
14221 OS <<
", actual taken count either this or zero.";
14223 OS <<
"Unpredictable constant max backedge-taken count. ";
14228 L->getHeader()->printAsOperand(OS,
false);
14233 OS <<
"symbolic max backedge-taken count is ";
14236 OS <<
", actual taken count either this or zero.";
14238 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14242 if (ExitingBlocks.
size() > 1)
14243 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14244 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14254 OS <<
"\n predicated symbolic max exit count for "
14255 << ExitingBlock->
getName() <<
": ";
14257 OS <<
"\n Predicates:\n";
14258 for (
const auto *
P : Predicates)
14269 L->getHeader()->printAsOperand(OS,
false);
14272 OS <<
"Predicated backedge-taken count is ";
14275 OS <<
"Unpredictable predicated backedge-taken count.";
14277 OS <<
" Predicates:\n";
14278 for (
const auto *
P : Preds)
14283 auto *PredConstantMax =
14285 if (PredConstantMax != ConstantBTC) {
14287 L->getHeader()->printAsOperand(OS,
false);
14290 OS <<
"Predicated constant max backedge-taken count is ";
14293 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14295 OS <<
" Predicates:\n";
14296 for (
const auto *
P : Preds)
14301 auto *PredSymbolicMax =
14303 if (SymbolicBTC != PredSymbolicMax) {
14305 L->getHeader()->printAsOperand(OS,
false);
14308 OS <<
"Predicated symbolic max backedge-taken count is ";
14311 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14313 OS <<
" Predicates:\n";
14314 for (
const auto *
P : Preds)
14320 L->getHeader()->printAsOperand(OS,
false);
14347 OS <<
"Computable";
14357 OS <<
"DoesNotDominate";
14363 OS <<
"ProperlyDominates";
14380 OS <<
"Classifying expressions for: ";
14381 F.printAsOperand(OS,
false);
14396 const Loop *L = LI.getLoopFor(
I.getParent());
14411 OS <<
"\t\t" "Exits: ";
14414 OS <<
"<<Unknown>>";
14420 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14422 Iter->getHeader()->printAsOperand(OS,
false);
14430 InnerL->getHeader()->printAsOperand(OS,
false);
14441 OS <<
"Determining loop execution counts for: ";
14442 F.printAsOperand(OS,
false);
14450 auto &
Values = LoopDispositions[S];
14451 for (
auto &V :
Values) {
14452 if (V.getPointer() == L)
14457 auto &Values2 = LoopDispositions[S];
14459 if (V.getPointer() == L) {
14468ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14486 if (L->contains(AR->
getLoop()) &&
14488 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14493 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14494 " dominate the contained loop's header?");
14521 bool HasVarying =
false;
14522 bool HasUniform =
false;
14564 auto &
Values = BlockDispositions[S];
14565 for (
auto &V :
Values) {
14566 if (V.getPointer() == BB)
14571 auto &Values2 = BlockDispositions[S];
14573 if (V.getPointer() == BB) {
14582ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14611 bool Proper =
true;
14622 if (Instruction *
I =
14624 if (
I->getParent() == BB)
14626 if (DT.properlyDominates(
I->getParent(), BB))
14649void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14652 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14653 auto It = BECounts.find(L);
14654 if (It != BECounts.end()) {
14655 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14656 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14658 auto UserIt = BECountUsers.find(S);
14659 assert(UserIt != BECountUsers.end());
14664 BECounts.erase(It);
14672 while (!Worklist.
empty()) {
14674 auto Users = SCEVUsers.find(Curr);
14675 if (
Users != SCEVUsers.end())
14676 for (
const auto *User :
Users->second)
14677 if (ToForget.
insert(User).second)
14681 for (
const auto *S : ToForget)
14682 forgetMemoizedResultsImpl(S);
14684 PredicatedSCEVRewrites.remove_if(
14685 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14688void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14689 LoopDispositions.erase(S);
14690 BlockDispositions.erase(S);
14691 UnsignedRanges.erase(S);
14692 SignedRanges.erase(S);
14693 HasRecMap.erase(S);
14694 ConstantMultipleCache.erase(S);
14697 UnsignedWrapViaInductionTried.erase(AR);
14698 SignedWrapViaInductionTried.erase(AR);
14701 auto ExprIt = ExprValueMap.find(S);
14702 if (ExprIt != ExprValueMap.end()) {
14703 for (
Value *V : ExprIt->second) {
14704 auto ValueIt = ValueExprMap.find_as(V);
14705 if (ValueIt != ValueExprMap.end())
14706 ValueExprMap.erase(ValueIt);
14708 ExprValueMap.erase(ExprIt);
14711 auto ScopeIt = ValuesAtScopes.find(S);
14712 if (ScopeIt != ValuesAtScopes.end()) {
14713 for (
const auto &Pair : ScopeIt->second)
14715 llvm::erase(ValuesAtScopesUsers[Pair.second.getPointer()],
14716 std::make_pair(Pair.first, S));
14717 ValuesAtScopes.erase(ScopeIt);
14720 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14721 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14722 for (
const auto &Pair : ScopeUserIt->second)
14725 llvm::erase_if(ValuesAtScopes[Pair.second], [&](
const auto &LS) {
14726 return LS.first == Pair.first && LS.second.getPointer() == S;
14728 ValuesAtScopesUsers.erase(ScopeUserIt);
14731 auto BEUsersIt = BECountUsers.find(S);
14732 if (BEUsersIt != BECountUsers.end()) {
14734 auto Copy = BEUsersIt->second;
14735 for (
const auto &Pair : Copy)
14736 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14737 BECountUsers.erase(BEUsersIt);
14740 auto FoldUser = FoldCacheUser.find(S);
14741 if (FoldUser != FoldCacheUser.end())
14742 for (
auto &KV : FoldUser->second)
14743 FoldCache.erase(KV);
14744 FoldCacheUser.erase(S);
14748ScalarEvolution::getUsedLoops(
const SCEV *S,
14750 struct FindUsedLoops {
14751 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14752 : LoopsUsed(LoopsUsed) {}
14753 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14754 bool follow(
const SCEV *S) {
14760 bool isDone()
const {
return false; }
14763 FindUsedLoops
F(LoopsUsed);
14764 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14767void ScalarEvolution::getReachableBlocks(
14770 Worklist.
push_back(&F.getEntryBlock());
14771 while (!Worklist.
empty()) {
14773 if (!Reachable.
insert(BB).second)
14781 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14788 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14792 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14827 SCEVMapper SCM(SE2);
14829 SE2.getReachableBlocks(ReachableBlocks, F);
14831 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14849 while (!LoopStack.
empty()) {
14855 if (!ReachableBlocks.
contains(L->getHeader()))
14860 auto It = BackedgeTakenCounts.find(L);
14861 if (It == BackedgeTakenCounts.end())
14865 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14885 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14886 if (Delta && !Delta->
isZero()) {
14887 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14888 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14889 dbgs() <<
"New: " << *NewBECount <<
"\n";
14890 dbgs() <<
"Delta: " << *Delta <<
"\n";
14898 while (!Worklist.
empty()) {
14900 if (ValidLoops.
insert(L).second)
14901 Worklist.
append(L->begin(), L->end());
14903 for (
const auto &KV : ValueExprMap) {
14908 "AddRec references invalid loop");
14913 auto It = ExprValueMap.find(KV.second);
14914 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14915 dbgs() <<
"Value " << *KV.first
14916 <<
" is in ValueExprMap but not in ExprValueMap\n";
14921 if (!ReachableBlocks.
contains(
I->getParent()))
14923 const SCEV *OldSCEV = SCM.visit(KV.second);
14925 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14926 if (Delta && !Delta->
isZero()) {
14927 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14928 <<
"Old: " << *OldSCEV <<
"\n"
14929 <<
"New: " << *NewSCEV <<
"\n"
14930 <<
"Delta: " << *Delta <<
"\n";
14936 for (
const auto &KV : ExprValueMap) {
14937 for (
Value *V : KV.second) {
14938 const SCEV *S = ValueExprMap.lookup(V);
14940 dbgs() <<
"Value " << *V
14941 <<
" is in ExprValueMap but not in ValueExprMap\n";
14944 if (S != KV.first) {
14945 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14946 << *KV.first <<
"\n";
14953 for (
const auto &S : UniqueSCEVs) {
14958 auto It = SCEVUsers.find(
Op);
14959 if (It != SCEVUsers.end() && It->second.count(&S))
14961 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14962 <<
" is not being tracked!\n";
14968 for (
const auto &ValueAndVec : ValuesAtScopes) {
14970 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14971 const Loop *L = LoopAndValueAtScope.first;
14972 SCEVUse ValueAtScope = LoopAndValueAtScope.second;
14974 auto It = ValuesAtScopesUsers.find(ValueAtScope.
getPointer());
14975 if (It != ValuesAtScopesUsers.end() &&
14978 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14979 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14985 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14986 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14987 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14988 const Loop *L = LoopAndValue.first;
14989 const SCEV *
Value = LoopAndValue.second;
14991 auto It = ValuesAtScopes.find(
Value);
14994 if (It != ValuesAtScopes.end() &&
any_of(It->second, [&](
const auto &LS) {
14995 return LS.first == L && LS.second.getPointer() == ValueAtScope;
14998 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14999 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
15005 auto VerifyBECountUsers = [&](
bool Predicated) {
15007 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
15008 for (
const auto &LoopAndBEInfo : BECounts) {
15009 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
15010 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
15012 auto UserIt = BECountUsers.find(S);
15013 if (UserIt != BECountUsers.end() &&
15014 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
15016 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
15017 <<
" missing from BECountUsers\n";
15024 VerifyBECountUsers(
false);
15025 VerifyBECountUsers(
true);
15028 for (
auto &[S,
Values] : LoopDispositions) {
15029 for (
auto [
Loop, CachedDisposition] :
Values) {
15031 if (CachedDisposition != RecomputedDisposition) {
15032 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
15033 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
15034 << RecomputedDisposition <<
"\n";
15041 for (
auto &[S,
Values] : BlockDispositions) {
15042 for (
auto [BB, CachedDisposition] :
Values) {
15044 if (CachedDisposition != RecomputedDisposition) {
15045 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
15046 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
15047 <<
", actual " << RecomputedDisposition <<
"\n";
15054 for (
auto [
FoldID, Expr] : FoldCache) {
15055 auto I = FoldCacheUser.find(Expr);
15056 if (
I == FoldCacheUser.end()) {
15057 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
15062 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
15066 for (
auto [Expr, IDs] : FoldCacheUser) {
15067 for (
auto &
FoldID : IDs) {
15070 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
15075 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
15076 <<
" != " << *Expr <<
"!\n";
15087 for (
auto [S, Multiple] : ConstantMultipleCache) {
15089 if ((Multiple != 0 && RecomputedMultiple != 0 &&
15090 Multiple.
urem(RecomputedMultiple) != 0 &&
15091 RecomputedMultiple.
urem(Multiple) != 0)) {
15092 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
15093 << *S <<
" : Computed " << RecomputedMultiple
15094 <<
" but cache contains " << Multiple <<
"!\n";
15102 FunctionAnalysisManager::Invalidator &Inv) {
15134 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15135 <<
F.getName() <<
"':\n";
15141 "Scalar Evolution Analysis",
false,
true)
15190 const SCEV *LHS,
const SCEV *RHS) {
15192 assert(LHS->getType() == RHS->getType() &&
15193 "Type mismatch between LHS and RHS");
15196 ID.AddInteger(Pred);
15197 ID.AddPointer(LHS);
15198 ID.AddPointer(RHS);
15200 if (
const auto *S = UniquePreds.lookup(ID, Token))
15204 UniquePreds.insert(Eq, Token);
15215 ID.AddInteger(AddedFlags);
15217 if (
const auto *S = UniquePreds.lookup(ID, Token))
15219 auto *OF =
new (SCEVAllocator)
15221 UniquePreds.insert(OF, Token);
15241 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15242 return Rewriter.visit(S);
15248 for (
const auto *Pred : U->getPredicates())
15250 if (IPred->getLHS() == Expr &&
15252 return IPred->getRHS();
15254 if (IPred->getLHS() == Expr &&
15255 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15256 return IPred->getRHS();
15259 return convertToAddRecWithPreds(Expr);
15262 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15278 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15295 explicit SCEVPredicateRewriter(
15296 const Loop *L, ScalarEvolution &SE,
15297 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15298 const SCEVPredicate *Pred)
15299 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15301 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15304 return Pred && Pred->
implies(
P, SE);
15310 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15313 return addOverflowAssumption(
A);
15322 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15326 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15328 if (!PredicatedRewrite)
15330 for (
const auto *
P : PredicatedRewrite->second){
15333 if (L != WP->getExpr()->getLoop())
15336 if (!addOverflowAssumption(
P))
15339 return PredicatedRewrite->first;
15342 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15343 const SCEVPredicate *Pred;
15352 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15359 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15379 if (!Step->
isOne())
15404 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15405 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15418 return Op->LHS == LHS &&
Op->RHS == RHS;
15425 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15427 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15452 const SCEV *Start = AR->getStart();
15453 const SCEV *OpStart =
Op->AR->getStart();
15458 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15467 const SCEV *Step = AR->getStepRecurrence(SE);
15468 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15521 if (Step->getValue()->getValue().isNonNegative())
15525 return ImpliedFlags;
15532 for (
const auto *
P : Preds)
15545 return this->implies(I, SE);
15557 const Loop *L = NWrap->getExpr()->getLoop();
15564 return RewrittenAR &&
15570 for (
const auto *Pred : Preds)
15571 Pred->print(OS,
Depth);
15576 for (
const auto *Pred : Set->Preds)
15584 bool CheckImplies = Preds.
size() < 16;
15587 if (CheckImplies &&
implies(
N, SE))
15593 for (
auto *
P : Preds) {
15594 if (CheckImplies &&
N->implies(
P, SE))
15598 Preds = std::move(PrunedPreds);
15599 Preds.push_back(
N);
15606 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15615 SCEVUsers[
Op].insert(
User);
15619 const SCEV *Expr = SE.getSCEV(V);
15624 RewriteEntry &Entry = RewriteMap[Expr];
15627 if (Entry.second && Generation == Entry.first)
15628 return Entry.second;
15633 Expr = Entry.second;
15635 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15636 Entry = {Generation, NewSCEV};
15642 if (!BackedgeCount) {
15644 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15645 for (
const auto *
P : Preds)
15648 return BackedgeCount;
15652 if (!SymbolicMaxBackedgeCount) {
15654 SymbolicMaxBackedgeCount =
15655 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15656 for (
const auto *
P : Preds)
15659 return SymbolicMaxBackedgeCount;
15663 if (!SmallConstantMaxTripCount) {
15665 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15666 for (
const auto *
P : Preds)
15669 return *SmallConstantMaxTripCount;
15673 if (Preds->implies(&Pred, SE))
15678 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15679 updateGeneration();
15692void PredicatedScalarEvolution::updateGeneration() {
15694 if (++Generation == 0) {
15695 for (
auto &
II : RewriteMap) {
15696 const SCEV *Rewritten =
II.second.second;
15718 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15724 ExtraPreds->
append(NewPreds);
15730 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15736 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15739 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15743 for (
auto *BB : L.getBlocks())
15744 for (
auto &
I : *BB) {
15745 if (!SE.isSCEVable(
I.getType()))
15748 auto *Expr = SE.getSCEV(&
I);
15749 auto II = RewriteMap.find(Expr);
15751 if (
II == RewriteMap.end())
15755 if (
II->second.second == Expr)
15760 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15768 LoopGuards Guards(SE);
15776void ScalarEvolution::LoopGuards::collectFromPHI(
15784 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15785 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15799 auto &RewriteMap =
G->second.RewriteMap;
15800 if (RewriteMap.empty())
15802 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15803 if (S == RewriteMap.end())
15809 return {C0, SM->getSCEVType()};
15812 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15813 MinMaxPattern
P2) -> MinMaxPattern {
15814 auto [C1,
T1] =
P1;
15815 auto [C2, T2] =
P2;
15816 if (!C1 || !C2 ||
T1 != T2)
15820 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15822 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15824 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15826 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15831 auto P = GetMinMaxConst(0);
15832 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15835 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15838 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15841 Guards.RewriteMap.insert({
LHS,
RHS});
15849 const APInt &DivisorVal,
15851 const APInt *ExprVal;
15864 const APInt &DivisorVal,
15866 const APInt *ExprVal;
15874 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15888 const SCEV *URemRHS =
nullptr;
15892 const SCEV *Multiple =
15894 DivInfo[URemLHS] = Multiple;
15896 Multiples[URemLHS] =
C->getAPInt();
15916 auto IsMinMaxSCEVWithNonNegativeConstant =
15920 if (
MinMax->getNumOperands() != 2)
15923 if (
C->getAPInt().isNegative())
15925 SCTy =
MinMax->getSCEVType();
15934 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15936 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15941 auto *DivisibleExpr =
15949void ScalarEvolution::LoopGuards::collectFromBlock(
15951 const BasicBlock *
Block,
const BasicBlock *Pred,
15959 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15970 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15972 if (From == FromRewritten)
15974 RewriteMap[From] = To;
15980 auto GetMaybeRewritten = [&](
const SCEV *S) {
15981 return RewriteMap.lookup_or(S, S);
15988 const SCEV *MatchLHS,
15989 const SCEV *MatchRHS) {
15990 const SCEVConstant *C1;
15993 if (!
match(MatchLHS,
16005 const SCEV *RewrittenLHS = GetMaybeRewritten(LHSUnknown);
16006 ExactRegion = ExactRegion.intersectWith(SE.
getUnsignedRange(RewrittenLHS),
16011 if (ExactRegion.isEmptySet() || ExactRegion.isWrappedSet() ||
16012 ExactRegion.isFullSet())
16015 const SCEV *RegionMin = SE.
getConstant(ExactRegion.getUnsignedMin());
16016 const SCEV *RegionMax = SE.
getConstant(ExactRegion.getUnsignedMax());
16017 const SCEV *ClampedLHS =
16019 AddRewrite(LHSUnknown, RewrittenLHS, ClampedLHS);
16022 if (MatchRangeCheckIdiom(Predicate,
LHS,
RHS))
16035 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
16037 const APInt &DividesBy =
16052 switch (Predicate) {
16081 SmallPtrSet<const SCEV *, 16> Visited;
16083 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
16087 while (!Worklist.
empty()) {
16091 if (!Visited.
insert(From).second)
16093 const SCEV *FromRewritten = GetMaybeRewritten(From);
16094 const SCEV *To =
nullptr;
16096 switch (Predicate) {
16101 EnqueueOperands(
UMax);
16107 EnqueueOperands(
SMax);
16113 EnqueueOperands(
UMin);
16119 EnqueueOperands(
SMin);
16127 const SCEV *OneAlignedUp =
16129 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16141 const SCEVConstant *
C;
16150 Guards.NotEqual.insert({
LHS,
RHS});
16159 AddRewrite(From, FromRewritten, To);
16176 SE.F.
getParent(), Intrinsic::experimental_guard);
16178 for (
const auto *GU : GuardDecl->users())
16180 if (Guard->getFunction() ==
Block->getParent() &&
16189 unsigned NumCollectedConditions = 0;
16191 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16193 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16195 const CondBrInst *LoopEntryPredicate =
16197 if (!LoopEntryPredicate)
16202 NumCollectedConditions++;
16206 if (
Depth > 0 && NumCollectedConditions == 2)
16214 if (Pair.second->hasNPredecessorsOrMore(2) &&
16216 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16217 for (
auto &Phi : Pair.second->phis())
16228 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16229 SmallVector<Value *, 8> Worklist;
16230 SmallPtrSet<Value *, 8> Visited;
16232 while (!Worklist.
empty()) {
16239 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16263 DenseMap<const SCEV *, APInt> Multiples;
16265 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16272 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16273 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16277 for (
const auto &[K, Divisor] : Multiples) {
16278 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16279 Guards.RewriteMap[
K] =
16281 Guards.
rewrite(K), Divisor, SE),
16290 Guards.PreserveNUW =
true;
16291 Guards.PreserveNSW =
true;
16292 for (
const SCEV *Expr : ExprsToRewrite) {
16293 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16294 Guards.PreserveNUW &=
16296 Guards.PreserveNSW &=
16303 if (ExprsToRewrite.size() > 1) {
16304 for (
const SCEV *Expr : ExprsToRewrite) {
16305 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16306 Guards.RewriteMap.erase(Expr);
16307 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16316 class SCEVLoopGuardRewriter
16327 NotEqual(Guards.NotEqual) {
16328 if (Guards.PreserveNUW)
16330 if (Guards.PreserveNSW)
16337 return Map.lookup_or(Expr, Expr);
16341 if (
const SCEV *S = Map.lookup(Expr))
16348 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16349 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16350 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16352 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16353 if (
const SCEV *S = Map.lookup(NarrowExt))
16354 return SE.getZeroExtendExpr(S, Ty);
16355 Bitwidth = Bitwidth / 2;
16363 if (
const SCEV *S = Map.lookup(Expr))
16370 if (
const SCEV *S = Map.lookup(Expr))
16376 if (
const SCEV *S = Map.lookup(Expr))
16382 if (
const SCEV *S = Map.lookup(Expr))
16387 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16392 if (NotEqual.contains({LHS, RHS})) {
16394 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16395 return SE.getUMaxExpr(OneAlignedUp, S);
16402 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16413 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16414 return SE.getAddExpr(
16417 if (
const SCEV *S = Map.lookup(
Add))
16418 return SE.getAddExpr(Expr->
getOperand(0), S);
16426 const SCEV *S =
nullptr;
16433 S = Map.lookup(SE.getAddExpr(NewC, Expr->
getOperand(1)));
16436 return SE.getAddExpr(S, SE.getMinusOne(Expr->
getType()));
16471 if (RewriteMap.empty() && NotEqual.empty())
16474 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16475 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< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
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)
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 PushLoopPHIs(const Loop *L, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push PHI nodes in the header of the given loop onto the given Worklist.
static void insertFoldCacheEntry(const ScalarEvolution::FoldID &ID, const SCEV *S, DenseMap< ScalarEvolution::FoldID, const SCEV * > &FoldCache, DenseMap< const SCEV *, SmallVector< ScalarEvolution::FoldID, 2 > > &FoldCacheUser)
static cl::opt< bool > ClassifyExpressions("scalar-evolution-classify-expressions", cl::Hidden, cl::init(true), cl::desc("When printing analysis, include information on every instruction"))
static bool hasHugeExpression(ArrayRef< SCEVUse > Ops)
Returns true if Ops contains a huge SCEV (the subtree of S contains at least HugeExprThreshold nodes)...
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 SCEV::NoWrapFlags getNoWrapFlagsForGEP(GEPOperator *GEP, const SCEV *Accum, ScalarEvolution &SE)
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 bool IsKnownPredicateViaAddRecMonotonicity(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Is LHS Pred RHS true because one of them is an AddRec that is known not to go below its own start val...
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 PHINode * getConstantEvolvingPHI(Value *V, const Loop *L, const TargetLibraryInfo *TLI)
getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node in the loop that V is deri...
static bool canConstantFold(const Instruction *I, const TargetLibraryInfo *TLI)
Return true if we can constant fold an instruction of the specified type, assuming that all operands ...
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 PHINode * getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L, DenseMap< Instruction *, PHINode * > &PHIMap, const TargetLibraryInfo *TLI, unsigned Depth)
getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by recursing through each instructi...
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 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 bool IsKnownPredicateViaAddRecStart(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
static const SCEV * getPreStartForExtend(const SCEVAddRecExpr *AR, ScalarEvolution *SE, unsigned Depth)
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 canConstantEvolve(Instruction *I, const Loop *L, const TargetLibraryInfo *TLI)
Determine whether this instruction can constant evolve within this loop assuming its operands can all...
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 SCEVUse withUseFlagsIfNotFolded(const SCEV *Res, SCEVUse LHS, SCEVUse RHS, SCEV::NoWrapFlags UseFlags)
Attach UseFlags to Res as use-specific flags, but only if Res really is the two-operand ExprT over LH...
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 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 scope_exit class, which executes user-defined cleanup logic at scope exit.
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 * 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.
This is the base class for all instructions that perform data casts.
This class is the base class for the comparison instructions.
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 * 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 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.
Insertion token: a failed lookup fills it in, the matching insert consumes it.
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.
void AddInteger(signed I)
This class represents a freeze function that returns random concrete value if an operand is either a ...
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.
This instruction inserts a single (scalar) element into a VectorType value.
This instruction inserts a struct field of array element value into an aggregate value.
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 SCEVUse getExitValue(ScalarEvolution &SE) const
Return the value of this recurrences when its loop exits, i.e.
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 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.
SCEV(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, unsigned short ExpressionSize, Type *Ty)
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.
Type * getType() const
Return the LLVM type of this SCEV expression.
LLVM_ABI void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
SCEVTypes getSCEVType() const
static constexpr auto FlagNW
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 * getZeroExtendExpr(SCEVUse Op, Type *Ty, unsigned Depth=0)
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 * 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 * 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 SCEVUse getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
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 void registerUser(const SCEV *User, ArrayRef< SCEVUse > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
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 void forgetValues(ArrayRef< Value * > Values)
Batched forgetValue: invalidates all Values in one shared def-use walk, avoiding the redundant re-tra...
LLVM_ABI const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &Operands)
LLVM_ABI const SCEV * getCastExpr(SCEVTypes Kind, SCEVUse Op, Type *Ty)
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 bool isKnownMultipleOf(const SCEV *S, uint64_t M, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Check that S is a multiple of M.
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 * getTruncateExpr(SCEVUse 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 * getZeroExtendExprImpl(SCEVUse 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 * getAnyExtendExpr(SCEVUse Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
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 * getSignExtendExpr(SCEVUse 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 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 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 const SCEV * getSignExtendExprImpl(SCEVUse Op, Type *Ty, unsigned Depth=0)
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 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
This class represents the LLVM 'select' instruction.
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.
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 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.
iterator_range< user_iterator > users()
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.
LLVM_ABI APInt GreatestCommonDivisor(APInt A, APInt B, bool IsSigned=false)
Compute GCD of two APInt values.
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
constexpr bool any(E Val)
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< SCEVSMaxExpr, Op0_t, Op1_t, SCEV::FlagAnyWrap, true > m_scev_SMax(const Op0_t &Op0, const Op1_t &Op1)
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagAnyWrap, true > m_scev_c_Mul(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.
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.
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.
LLVM_ABI bool canConstantFoldCallTo(const CallBase *Call, const Function *F, const TargetLibraryInfo *TLI=nullptr)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
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.
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.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
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.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
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.
constexpr detail::IsaCheckPredicate< Types... > IsaPred
Function object wrapper for the llvm::isa type check.
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:
SCEVPtrT getPointer() const
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