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))
5702const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5704 Value *StartValueV) {
5707 assert(BEValueV && StartValueV);
5713 if (BO->Opcode != Instruction::Add)
5716 const SCEV *Accum =
nullptr;
5717 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5719 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5733 insertValueToMap(PN, PHISCEV);
5736 inferNoWrapViaConstantRanges(AR);
5743 "Accum is defined outside L, but is not invariant?");
5744 if (isAddRecNeverPoison(BEInst, L))
5751const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5759 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5765 }
else if (BEValueV != V) {
5769 }
else if (!StartValueV) {
5771 }
else if (StartValueV != V) {
5772 StartValueV =
nullptr;
5776 if (!BEValueV || !StartValueV)
5779 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5780 "PHI node already processed?");
5784 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5789 insertValueToMap(PN, SymbolicName);
5793 const SCEV *BEValue =
getSCEV(BEValueV);
5803 unsigned FoundIndex =
Add->getNumOperands();
5804 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5805 if (
Add->getOperand(i) == SymbolicName)
5806 if (FoundIndex == e) {
5811 if (FoundIndex !=
Add->getNumOperands()) {
5814 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5815 if (i != FoundIndex)
5816 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5828 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5835 if (
GEP->getOperand(0) == PN) {
5836 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
5854 const SCEV *StartVal =
getSCEV(StartValueV);
5855 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5860 forgetMemoizedResults({SymbolicName});
5861 insertValueToMap(PN, PHISCEV);
5864 inferNoWrapViaConstantRanges(AR);
5888 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5889 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5891 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5892 const SCEV *StartVal =
getSCEV(StartValueV);
5893 if (Start == StartVal) {
5897 forgetMemoizedResults({SymbolicName});
5898 insertValueToMap(PN, Shifted);
5908 eraseValueFromMap(PN);
5923 Use &LeftUse =
Merge->getOperandUse(0);
5924 Use &RightUse =
Merge->getOperandUse(1);
5960 assert(IDom &&
"At least the entry block should dominate PN");
5968const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
5973 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
5990 CommonInst = IncomingInst;
6006ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6012 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6013 bool SCEVExprsIdentical =
6015 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6016 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6019const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6020 if (
const SCEV *S = createAddRecFromPHI(PN))
6030 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6033 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6042 struct FindClosure {
6043 const SCEV *OperandToFind;
6049 bool canRecurseInto(
SCEVTypes Kind)
const {
6052 return RootKind == Kind || NonSequentialRootKind == Kind ||
6057 : OperandToFind(OperandToFind), RootKind(RootKind),
6058 NonSequentialRootKind(
6062 bool follow(
const SCEV *S) {
6063 Found = S == OperandToFind;
6065 return !isDone() && canRecurseInto(S->
getSCEVType());
6068 bool isDone()
const {
return Found; }
6071 FindClosure FC(OperandToFind, RootKind);
6076std::optional<const SCEV *>
6077ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6087 switch (ICI->getPredicate()) {
6101 bool Signed = ICI->isSigned();
6102 const SCEV *LA =
getSCEV(TrueVal);
6110 if (LA == LS &&
RA == RS)
6112 if (LA == RS &&
RA == LS)
6115 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6116 if (
Op->getType()->isPointerTy()) {
6127 LS = CoerceOperand(LS);
6128 RS = CoerceOperand(RS);
6152 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6153 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6167 X = ZExt->getOperand();
6169 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6180 return std::nullopt;
6183static std::optional<const SCEV *>
6185 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6189 "Unexpected operands of a select.");
6201 return std::nullopt;
6216static std::optional<const SCEV *>
6220 return std::nullopt;
6223 const auto *SETrue = SE->
getSCEV(TrueVal);
6224 const auto *SEFalse = SE->
getSCEV(FalseVal);
6228const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6230 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6232 V->getType() ==
TrueVal->getType() &&
6233 "Types of select hands and of the result must match.");
6236 if (!
V->getType()->isIntegerTy(1))
6239 if (std::optional<const SCEV *> S =
6252 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6256 if (std::optional<const SCEV *> S =
6257 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6263 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6269 assert(
GEP->getSourceElementType()->isSized() &&
6270 "GEP source element type must be sized");
6273 for (
Value *Index :
GEP->indices())
6278APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6281 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6284 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6286 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6289 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6307 return GetShiftedByZeros(TZ);
6317 return GetShiftedByZeros(TZ);
6321 if (
M->hasNoUnsignedWrap()) {
6324 for (
const SCEV *Operand :
M->operands().drop_front())
6332 for (
const SCEV *Operand :
M->operands())
6334 return GetShiftedByZeros(TZ);
6339 if (
N->hasNoUnsignedWrap())
6340 return GetGCDMultiple(
N);
6343 for (
const SCEV *Operand :
N->operands().drop_front())
6345 return GetShiftedByZeros(TZ);
6362 CtxI = &*F.getEntryBlock().begin();
6369 .allowEphemerals(
true))
6370 .countMinTrailingZeros();
6371 return GetShiftedByZeros(
Known);
6384 return getConstantMultipleImpl(S, CtxI);
6386 auto I = ConstantMultipleCache.find(S);
6387 if (
I != ConstantMultipleCache.end())
6390 APInt Result = getConstantMultipleImpl(S, CtxI);
6391 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6392 assert(InsertPair.second &&
"Should insert a new key");
6393 return InsertPair.first->second;
6410 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6413 if (std::optional<ConstantRange>
Range = CB->getRange())
6417 if (std::optional<ConstantRange>
Range =
A->getRange())
6420 return std::nullopt;
6427 UnsignedRanges.erase(AddRec);
6428 SignedRanges.erase(AddRec);
6429 ConstantMultipleCache.erase(AddRec);
6434getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6460 Value *Start, *Step;
6467 assert(L && L->getHeader() ==
P->getParent());
6480 case Instruction::AShr:
6481 case Instruction::LShr:
6482 case Instruction::Shl:
6497 KnownStep.getBitWidth() ==
BitWidth);
6500 auto MaxShiftAmt = KnownStep.getMaxValue();
6502 bool Overflow =
false;
6503 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6510 case Instruction::AShr: {
6518 if (KnownStart.isNonNegative())
6521 KnownStart.getMaxValue() + 1);
6522 if (KnownStart.isNegative())
6525 KnownEnd.getMaxValue() + 1);
6528 case Instruction::LShr: {
6537 KnownStart.getMaxValue() + 1);
6539 case Instruction::Shl: {
6543 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6544 return ConstantRange(KnownStart.getMinValue(),
6545 KnownEnd.getMaxValue() + 1);
6570 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6577ScalarEvolution::getRangeRefIter(
const SCEV *S,
6578 ScalarEvolution::RangeSignHint SignHint) {
6579 DenseMap<const SCEV *, ConstantRange> &Cache =
6580 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6583 SmallPtrSet<const SCEV *, 8> Seen;
6587 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6588 if (!Seen.
insert(Expr).second)
6621 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6622 const SCEV *
P = WorkList[
I];
6626 for (
const SCEV *
Op :
P->operands())
6639 if (!WorkList.
empty()) {
6644 getRangeRef(
P, SignHint);
6648 return getRangeRef(S, SignHint, 0);
6651const APInt *ScalarEvolution::getConstantAPIntOrNull(
const SCEV *S) {
6653 return &
C->getAPInt();
6661 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6662 DenseMap<const SCEV *, ConstantRange> &Cache =
6663 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6670 auto I = Cache.
find(S);
6671 if (
I != Cache.
end())
6675 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6680 return getRangeRefIter(S, SignHint);
6683 ConstantRange ConservativeResult(
BitWidth,
true);
6684 using OBO = OverflowingBinaryOperator;
6688 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6692 ConservativeResult =
6699 ConservativeResult = ConstantRange(
6715 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6722 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6729 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6734 return setRange(Cast, SignHint,
X);
6739 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6740 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6742 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6743 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6744 ConservativeResult =
6745 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6747 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6748 unsigned WrapType = OBO::AnyWrap;
6749 if (
Add->hasNoSignedWrap())
6750 WrapType |= OBO::NoSignedWrap;
6751 if (
Add->hasNoUnsignedWrap())
6752 WrapType |= OBO::NoUnsignedWrap;
6754 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6756 return setRange(
Add, SignHint,
6757 ConservativeResult.intersectWith(
X, RangeType));
6761 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6763 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6764 return setRange(
Mul, SignHint,
6765 ConservativeResult.intersectWith(
X, RangeType));
6769 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6770 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6771 return setRange(UDiv, SignHint,
6772 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6780 if (!UnsignedMinValue.
isZero())
6781 ConservativeResult = ConservativeResult.intersectWith(
6782 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6791 bool AllNonNeg =
true;
6792 bool AllNonPos =
true;
6793 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6800 ConservativeResult = ConservativeResult.intersectWith(
6805 ConservativeResult = ConservativeResult.intersectWith(
6814 const SCEV *MaxBEScev =
6828 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6830 ConservativeResult =
6831 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6834 auto RangeFromFactoring = getRangeViaFactoring(
6836 ConservativeResult =
6837 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6843 const SCEV *SymbolicMaxBECount =
6848 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6849 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6850 ConservativeResult =
6851 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6856 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6866 ID = Intrinsic::umax;
6869 ID = Intrinsic::smax;
6873 ID = Intrinsic::umin;
6876 ID = Intrinsic::smin;
6883 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6884 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6886 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6887 return setRange(S, SignHint,
6888 ConservativeResult.intersectWith(
X, RangeType));
6897 ConservativeResult =
6898 ConservativeResult.intersectWith(*MDRange, RangeType);
6903 auto CR = getRangeForUnknownRecurrence(U);
6904 ConservativeResult = ConservativeResult.intersectWith(CR);
6915 if (
U->getType()->isPointerTy()) {
6918 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
6919 int ptrIdxDiff = ptrSize -
BitWidth;
6920 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
6926 if (!
Known.Zero.getHiBits(NS).isZero())
6927 Known.Zero.setHighBits(NS);
6928 if (!
Known.One.getHiBits(NS).isZero())
6929 Known.One.setHighBits(NS);
6932 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
6933 ConservativeResult = ConservativeResult.intersectWith(
6934 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
6937 ConservativeResult = ConservativeResult.intersectWith(
6942 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6946 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
6947 DL, CanBeNull,
nullptr);
6963 ConservativeResult = ConservativeResult.intersectWith(
6973 return getRangeRef(AR, SignHint,
Depth + 1);
6977 ConstantRange RangeFromOps(
BitWidth,
false);
6979 for (
const auto &
Op :
Phi->operands()) {
6981 RangeFromOps = RangeFromOps.unionWith(OpRange);
6983 if (RangeFromOps.isFullSet())
6986 ConservativeResult =
6987 ConservativeResult.intersectWith(RangeFromOps, RangeType);
6993 if (
II->getIntrinsicID() == Intrinsic::vscale) {
6995 ConservativeResult = ConservativeResult.difference(Disallowed);
6998 return setRange(U, SignHint, std::move(ConservativeResult));
7004 return setRange(S, SignHint, std::move(ConservativeResult));
7012static std::pair<ConstantRange, bool>
7020 if (Step == 0 || MaxBECount == 0)
7021 return {StartRange,
true};
7027 return {ConstantRange::getFull(
BitWidth),
false};
7043 return {ConstantRange::getFull(
BitWidth),
false};
7056 APInt MovedBoundary;
7061 MovedBoundary = StartLower - std::move(
Offset);
7064 MovedBoundary = StartUpper + std::move(
Offset);
7068 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7075 if (StartRange.
contains(MovedBoundary))
7076 return {ConstantRange::getFull(
BitWidth),
false};
7079 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7081 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7089std::pair<ConstantRange, SCEV::NoWrapFlags>
7090ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7091 const APInt &MaxBECount) {
7095 "mismatched bit widths");
7104 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7106 StartSRange, MaxBECount,
7108 ConstantRange SR = SR1.unionWith(SR2);
7125ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7127 ScalarEvolution::RangeSignHint SignHint) {
7128 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7130 "This only works for non-self-wrapping AddRecs!");
7131 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7135 return ConstantRange::getFull(
BitWidth);
7143 return ConstantRange::getFull(
BitWidth);
7147 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7149 MaxItersWithoutWrap))
7150 return ConstantRange::getFull(
BitWidth);
7171 ConstantRange StartRange = getRangeRef(Start, SignHint);
7172 ConstantRange EndRange = getRangeRef(End, SignHint);
7173 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7177 return RangeBetween;
7182 return ConstantRange::getFull(
BitWidth);
7185 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7186 return RangeBetween;
7188 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7189 return RangeBetween;
7190 return ConstantRange::getFull(
BitWidth);
7195 const APInt &MaxBECount) {
7202 "mismatched bit widths");
7204 struct SelectPattern {
7205 Value *Condition =
nullptr;
7209 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7211 std::optional<unsigned> CastOp;
7225 CastOp = SCast->getSCEVType();
7226 S = SCast->getOperand();
7229 using namespace llvm::PatternMatch;
7236 Condition =
nullptr;
7268 bool isRecognized() {
return Condition !=
nullptr; }
7271 SelectPattern StartPattern(*
this,
BitWidth, Start);
7272 if (!StartPattern.isRecognized())
7273 return ConstantRange::getFull(
BitWidth);
7275 SelectPattern StepPattern(*
this,
BitWidth, Step);
7276 if (!StepPattern.isRecognized())
7277 return ConstantRange::getFull(
BitWidth);
7279 if (StartPattern.Condition != StepPattern.Condition) {
7283 return ConstantRange::getFull(
BitWidth);
7294 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7295 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7296 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7297 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7299 ConstantRange TrueRange =
7300 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7301 ConstantRange FalseRange =
7302 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7314 PDI && PDI->isDisjoint()) {
7329ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7342 SmallPtrSet<const SCEV *, 16> Visited;
7344 auto pushOp = [&](
const SCEV *S) {
7345 if (!Visited.
insert(S).second)
7348 if (Visited.
size() > 30) {
7359 while (!Worklist.
empty()) {
7361 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7362 if (!Bound || DT.dominates(Bound, DefI))
7369 return Bound ? Bound : &*F.getEntryBlock().begin();
7375 return getDefiningScopeBound(
Ops, Discard);
7378bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7380 if (
A->getParent() ==
B->getParent() &&
7385 auto *BLoop = LI.getLoopFor(
B->getParent());
7386 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7387 BLoop->getLoopPreheader() ==
A->getParent() &&
7389 A->getParent()->end()) &&
7397 SCEVPoisonCollector PC(
true);
7399 return PC.MaybePoison.
empty();
7402bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7412bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7429 for (
const Use &
Op :
I->operands()) {
7435 auto *DefI = getDefiningScopeBound(SCEVOps);
7436 return isGuaranteedToTransferExecutionTo(DefI,
I);
7439bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7441 if (isSCEVExprNeverPoison(
I))
7452 auto *ExitingBB =
L->getExitingBlock();
7456 SmallPtrSet<const Value *, 16> KnownPoison;
7465 while (!Worklist.
empty()) {
7468 for (
const Use &U :
Poison->uses()) {
7471 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7475 if (KnownPoison.
insert(PoisonUser).second)
7483ScalarEvolution::LoopProperties
7484ScalarEvolution::getLoopProperties(
const Loop *L) {
7485 using LoopProperties = ScalarEvolution::LoopProperties;
7487 auto Itr = LoopPropertiesCache.find(L);
7488 if (Itr == LoopPropertiesCache.end()) {
7491 return !
SI->isSimple();
7501 return I->mayWriteToMemory();
7504 LoopProperties LP = {
true,
7507 for (
auto *BB :
L->getBlocks())
7508 for (
auto &
I : *BB) {
7510 LP.HasNoAbnormalExits =
false;
7511 if (HasSideEffects(&
I))
7512 LP.HasNoSideEffects =
false;
7513 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7517 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7518 assert(InsertPair.second &&
"We just checked!");
7519 Itr = InsertPair.first;
7532const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7538 Stack.emplace_back(V,
false);
7539 while (!Stack.empty()) {
7540 auto E = Stack.back();
7541 Value *CurV = E.getPointer();
7549 const SCEV *CreatedSCEV =
nullptr;
7552 CreatedSCEV = createSCEV(CurV);
7557 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7561 insertValueToMap(CurV, CreatedSCEV);
7564 Stack.back().setInt(
true);
7567 Stack.emplace_back(
Op,
false);
7584 if (!DT.isReachableFromEntry(
I->getParent()))
7597 switch (BO->Opcode) {
7598 case Instruction::Add:
7599 case Instruction::Mul: {
7606 Ops.push_back(BO->
Op);
7610 Ops.push_back(BO->RHS);
7614 (BO->Opcode == Instruction::Add &&
7615 (NewBO->Opcode != Instruction::Add &&
7616 NewBO->Opcode != Instruction::Sub)) ||
7617 (BO->Opcode == Instruction::Mul &&
7618 NewBO->Opcode != Instruction::Mul)) {
7619 Ops.push_back(BO->LHS);
7624 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7627 Ops.push_back(BO->LHS);
7635 case Instruction::Sub:
7636 case Instruction::UDiv:
7637 case Instruction::URem:
7639 case Instruction::AShr:
7640 case Instruction::Shl:
7641 case Instruction::Xor:
7645 case Instruction::And:
7646 case Instruction::Or:
7650 case Instruction::LShr:
7657 Ops.push_back(BO->LHS);
7658 Ops.push_back(BO->RHS);
7662 switch (
U->getOpcode()) {
7663 case Instruction::Trunc:
7664 case Instruction::ZExt:
7665 case Instruction::SExt:
7666 case Instruction::PtrToAddr:
7667 case Instruction::PtrToInt:
7668 Ops.push_back(
U->getOperand(0));
7671 case Instruction::BitCast:
7673 Ops.push_back(
U->getOperand(0));
7678 case Instruction::SDiv:
7679 case Instruction::SRem:
7680 Ops.push_back(
U->getOperand(0));
7681 Ops.push_back(
U->getOperand(1));
7684 case Instruction::GetElementPtr:
7686 "GEP source element type must be sized");
7690 case Instruction::IntToPtr:
7693 case Instruction::PHI:
7724 Ops.push_back(CondICmp->getOperand(0));
7725 Ops.push_back(CondICmp->getOperand(1));
7745 case Instruction::Select: {
7747 auto CanSimplifyToUnknown = [
this,
U]() {
7765 if (CanSimplifyToUnknown())
7772 case Instruction::Call:
7773 case Instruction::Invoke:
7780 switch (
II->getIntrinsicID()) {
7781 case Intrinsic::abs:
7782 Ops.push_back(
II->getArgOperand(0));
7784 case Intrinsic::umax:
7785 case Intrinsic::umin:
7786 case Intrinsic::smax:
7787 case Intrinsic::smin:
7788 case Intrinsic::usub_sat:
7789 case Intrinsic::uadd_sat:
7790 Ops.push_back(
II->getArgOperand(0));
7791 Ops.push_back(
II->getArgOperand(1));
7793 case Intrinsic::start_loop_iterations:
7794 case Intrinsic::annotation:
7795 case Intrinsic::ptr_annotation:
7796 Ops.push_back(
II->getArgOperand(0));
7808const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7817 if (!DT.isReachableFromEntry(
I->getParent()))
7832 switch (BO->Opcode) {
7833 case Instruction::Add: {
7859 if (BO->Opcode == Instruction::Sub)
7867 if (BO->Opcode == Instruction::Sub)
7874 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7875 NewBO->Opcode != Instruction::Sub)) {
7885 case Instruction::Mul: {
7906 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7915 case Instruction::UDiv:
7919 case Instruction::URem:
7923 case Instruction::Sub: {
7926 Flags = getNoWrapFlagsFromUB(BO->
Op);
7931 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
7934 if (HasPtrLHS || HasPtrRHS) {
7939 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
7940 bool BothPtr) ->
const SCEV * {
7943 const SCEV *PtrSCEV =
getSCEV(PtrOp);
7953 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
7954 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
7962 case Instruction::And:
7968 if (CI->isMinusOne())
7970 const APInt &
A = CI->getValue();
7976 unsigned LZ =
A.countl_zero();
7977 unsigned TZ =
A.countr_zero();
7982 APInt EffectiveMask =
7984 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
7987 const SCEV *ShiftedLHS =
nullptr;
7991 unsigned MulZeros = OpC->getAPInt().countr_zero();
7992 unsigned GCD = std::min(MulZeros, TZ);
7997 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8019 case Instruction::Or:
8028 case Instruction::Xor:
8031 if (CI->isMinusOne())
8040 if (LBO->getOpcode() == Instruction::And &&
8041 LCI->getValue() == CI->getValue())
8042 if (
const SCEVZeroExtendExpr *Z =
8045 const SCEV *Z0 =
Z->getOperand();
8052 if (CI->getValue().isMask(Z0TySize))
8058 APInt Trunc = CI->getValue().trunc(Z0TySize);
8067 case Instruction::Shl:
8085 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8094 ConstantInt *
X = ConstantInt::get(
8100 case Instruction::AShr:
8122 const SCEV *AddTruncateExpr =
nullptr;
8123 ConstantInt *ShlAmtCI =
nullptr;
8124 const SCEV *AddConstant =
nullptr;
8126 if (L &&
L->getOpcode() == Instruction::Add) {
8134 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8141 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8149 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8154 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8159 if (AddTruncateExpr && ShlAmtCI) {
8171 const APInt &ShlAmt = ShlAmtCI->
getValue();
8175 const SCEV *CompositeExpr =
8177 if (
L->getOpcode() != Instruction::Shl)
8178 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8187 switch (
U->getOpcode()) {
8188 case Instruction::Trunc:
8191 case Instruction::ZExt:
8194 case Instruction::SExt:
8204 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8205 Type *Ty =
U->getType();
8213 case Instruction::BitCast:
8219 case Instruction::PtrToAddr: {
8226 case Instruction::PtrToInt:
8230 case Instruction::IntToPtr:
8234 case Instruction::SDiv:
8241 case Instruction::SRem:
8248 case Instruction::GetElementPtr:
8251 case Instruction::PHI:
8254 case Instruction::Select:
8255 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8258 case Instruction::Call:
8259 case Instruction::Invoke:
8264 switch (
II->getIntrinsicID()) {
8265 case Intrinsic::abs:
8269 case Intrinsic::umax:
8273 case Intrinsic::umin:
8277 case Intrinsic::smax:
8281 case Intrinsic::smin:
8285 case Intrinsic::usub_sat: {
8286 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8287 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8291 case Intrinsic::uadd_sat: {
8292 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8293 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8297 case Intrinsic::start_loop_iterations:
8298 case Intrinsic::annotation:
8299 case Intrinsic::ptr_annotation:
8303 case Intrinsic::vscale:
8323 auto *ExitCountType = ExitCount->
getType();
8324 assert(ExitCountType->isIntegerTy());
8326 1 + ExitCountType->getScalarSizeInBits());
8339 auto CanAddOneWithoutOverflow = [&]() {
8341 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8352 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8382 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8383 assert(L->isLoopExiting(ExitingBlock) &&
8384 "Exiting block must actually branch out of the loop!");
8393 const auto *MaxExitCount =
8401 L->getExitingBlocks(ExitingBlocks);
8404 if (ExitingBlocks.
empty() ||
8420 const LoopGuards &Guards) {
8424 const SCEV *TCExpr =
8432 : (
unsigned)Multiple.getZExtValue();
8436 const SCEV *ExitCount) {
8458 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8459 assert(L->isLoopExiting(ExitingBlock) &&
8460 "Exiting block must actually branch out of the loop!");
8470 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8472 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8474 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8484 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8487 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8490 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8498 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8505 return getBackedgeTakenInfo(L).getExact(L,
this);
8507 return getBackedgeTakenInfo(L).getConstantMax(
this);
8509 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8516 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8521 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8525 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8535 for (
PHINode &PN : Header->phis())
8536 if (Visited.
insert(&PN).second)
8540ScalarEvolution::BackedgeTakenInfo &
8541ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8542 auto &BTI = getBackedgeTakenInfo(L);
8543 if (BTI.hasFullInfo())
8546 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8549 return Pair.first->second;
8551 BackedgeTakenInfo
Result =
8552 computeBackedgeTakenCount(L,
true);
8554 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8557ScalarEvolution::BackedgeTakenInfo &
8558ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8564 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8565 BackedgeTakenCounts.try_emplace(L);
8567 return Pair.first->second;
8572 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8579 if (
Result.hasAnyInfo()) {
8582 auto LoopUsersIt = LoopUsers.find(L);
8583 if (LoopUsersIt != LoopUsers.end())
8585 forgetMemoizedResults(ToForget);
8588 for (PHINode &PN :
L->getHeader()->phis())
8589 ConstantEvolutionLoopExitValue.erase(&PN);
8597 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8606 BackedgeTakenCounts.clear();
8607 PredicatedBackedgeTakenCounts.clear();
8608 BECountUsers.clear();
8609 LoopPropertiesCache.clear();
8610 ConstantEvolutionLoopExitValue.clear();
8611 ValueExprMap.clear();
8612 ValuesAtScopes.clear();
8613 ValuesAtScopesUsers.clear();
8614 LoopDispositions.clear();
8615 BlockDispositions.clear();
8616 UnsignedRanges.clear();
8617 SignedRanges.clear();
8618 ExprValueMap.clear();
8620 ConstantMultipleCache.clear();
8621 PredicatedSCEVRewrites.clear();
8623 FoldCacheUser.clear();
8625void ScalarEvolution::visitAndClearUsers(
8629 while (!Worklist.
empty()) {
8636 if (It != ValueExprMap.
end()) {
8638 eraseValueFromMap(It->first);
8640 ConstantEvolutionLoopExitValue.erase(PN);
8654 while (!LoopWorklist.
empty()) {
8658 forgetBackedgeTakenCounts(CurrL,
false);
8659 forgetBackedgeTakenCounts(CurrL,
true);
8662 PredicatedSCEVRewrites.remove_if(
8663 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8665 auto LoopUsersItr = LoopUsers.find(CurrL);
8666 if (LoopUsersItr != LoopUsers.end())
8671 visitAndClearUsers(Worklist, Visited, ToForget);
8673 LoopPropertiesCache.erase(CurrL);
8676 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8678 forgetMemoizedResults(ToForget);
8695 visitAndClearUsers(Worklist, Visited, ToForget);
8697 forgetMemoizedResults(ToForget);
8708 visitAndClearUsers(Worklist, Visited, ToForget);
8710 forgetMemoizedResults(ToForget);
8718 auto InvalidateValue = [&](
Value *Val) {
8722 struct InvalidationRootCollector {
8726 InvalidationRootCollector(
Loop *L) : L(L) {}
8728 bool follow(
const SCEV *S) {
8734 if (L->contains(AddRec->
getLoop()))
8739 bool isDone()
const {
return false; }
8742 InvalidationRootCollector
C(L);
8744 forgetMemoizedResults(
C.Roots);
8767 BlockDispositions.clear();
8768 LoopDispositions.clear();
8785 while (!Worklist.
empty()) {
8787 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8788 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8789 if (!LoopDispoRemoved && !BlockDispoRemoved)
8791 auto Users = SCEVUsers.find(Curr);
8792 if (
Users != SCEVUsers.end())
8805const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8809 if (!isComplete() || ExitNotTaken.
empty())
8820 for (
const auto &ENT : ExitNotTaken) {
8821 const SCEV *BECount = ENT.ExactNotTaken;
8824 "We should only have known counts for exiting blocks that dominate "
8827 Ops.push_back(BECount);
8832 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8833 "Predicate should be always true!");
8842const ScalarEvolution::ExitNotTakenInfo *
8843ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8844 const BasicBlock *ExitingBlock,
8845 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8846 for (
const auto &ENT : ExitNotTaken)
8847 if (ENT.ExitingBlock == ExitingBlock) {
8848 if (ENT.hasAlwaysTruePredicate())
8850 else if (Predicates) {
8860const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8862 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8863 if (!getConstantMax())
8866 for (
const auto &ENT : ExitNotTaken)
8867 if (!ENT.hasAlwaysTruePredicate()) {
8875 "No point in having a non-constant max backedge taken count!");
8876 return getConstantMax();
8879const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8881 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8889 for (
const auto &ENT : ExitNotTaken) {
8890 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8893 "We should only have known counts for exiting blocks that "
8899 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8900 "Predicate should be always true!");
8903 if (ExitCounts.
empty())
8912bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8914 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8915 return !ENT.hasAlwaysTruePredicate();
8917 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8933 this->ExactNotTaken = E = ConstantMaxNotTaken;
8934 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8939 "Exact is not allowed to be less precise than Constant Max");
8942 "Exact is not allowed to be less precise than Symbolic Max");
8945 "Symbolic Max is not allowed to be less precise than Constant Max");
8948 "No point in having a non-constant max backedge taken count!");
8950 for (
const auto PredList : PredLists)
8951 for (
const auto *
P : PredList) {
8959 "Backedge count should be int");
8962 "Max backedge count should be int");
8975ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8977 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8978 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8979 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8981 ExitNotTaken.reserve(ExitCounts.
size());
8982 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8983 std::back_inserter(ExitNotTaken),
8984 [&](
const EdgeExitInfo &EEI) {
8985 BasicBlock *ExitBB = EEI.first;
8986 const ExitLimit &EL = EEI.second;
8987 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
8988 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
8993 "No point in having a non-constant max backedge taken count!");
8997ScalarEvolution::BackedgeTakenInfo
8998ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
8999 bool AllowPredicates) {
9001 L->getExitingBlocks(ExitingBlocks);
9003 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9006 bool CouldComputeBECount =
true;
9008 const SCEV *MustExitMaxBECount =
nullptr;
9009 const SCEV *MayExitMaxBECount =
nullptr;
9010 bool MustExitMaxOrZero =
false;
9011 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9022 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9023 if (ExitIfTrue == CI->
isZero())
9027 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9029 assert((AllowPredicates || EL.Predicates.empty()) &&
9030 "Predicated exit limit when predicates are not allowed!");
9035 ++NumExitCountsComputed;
9039 CouldComputeBECount =
false;
9046 "Exact is known but symbolic isn't?");
9047 ++NumExitCountsNotComputed;
9062 DT.dominates(ExitBB, Latch)) {
9063 if (!MustExitMaxBECount) {
9064 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9065 MustExitMaxOrZero = EL.MaxOrZero;
9068 EL.ConstantMaxNotTaken);
9072 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9075 EL.ConstantMaxNotTaken);
9079 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9083 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9089 for (
const auto &Pair : ExitCounts) {
9091 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9093 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9094 {
L, AllowPredicates});
9096 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9097 MaxBECount, MaxOrZero);
9100ScalarEvolution::ExitLimit
9101ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9102 bool IsOnlyExit,
bool AllowPredicates) {
9103 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9107 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9112 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9113 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9114 "It should have one successor in loop and one exit block!");
9125 if (!
L->contains(SBB)) {
9130 assert(Exit &&
"Exiting block must have at least one exit");
9131 return computeExitLimitFromSingleExitSwitch(
9132 L, SI, Exit, IsOnlyExit);
9139 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9140 bool AllowPredicates) {
9141 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9142 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9143 ControlsOnlyExit, AllowPredicates);
9146std::optional<ScalarEvolution::ExitLimit>
9147ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9148 bool ExitIfTrue,
bool ControlsOnlyExit,
9149 bool AllowPredicates) {
9151 (void)this->ExitIfTrue;
9152 (void)this->AllowPredicates;
9154 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9155 this->AllowPredicates == AllowPredicates &&
9156 "Variance in assumed invariant key components!");
9157 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9158 if (Itr == TripCountMap.end())
9159 return std::nullopt;
9163void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9165 bool ControlsOnlyExit,
9166 bool AllowPredicates,
9168 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9169 this->AllowPredicates == AllowPredicates &&
9170 "Variance in assumed invariant key components!");
9172 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9173 assert(InsertResult.second &&
"Expected successful insertion!");
9178ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9179 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9180 bool ControlsOnlyExit,
bool AllowPredicates) {
9182 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9186 ExitLimit EL = computeExitLimitFromCondImpl(
9187 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9188 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9192ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9193 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9194 bool ControlsOnlyExit,
bool AllowPredicates) {
9196 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9197 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9198 return *LimitFromBinOp;
9204 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9205 if (EL.hasFullInfo() || !AllowPredicates)
9209 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9229 const WithOverflowInst *WO;
9244 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9245 ControlsOnlyExit, AllowPredicates);
9246 if (EL.hasAnyInfo())
9251 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9254std::optional<ScalarEvolution::ExitLimit>
9255ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9259 bool AllowPredicates) {
9268 return std::nullopt;
9272 ExitLimit EL0 = computeExitLimitFromCondCached(
9273 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9274 ExitLimit EL1 = computeExitLimitFromCondCached(
9275 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9280 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9285 if (EitherMayExit) {
9295 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9297 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9300 EL1.ConstantMaxNotTaken);
9302 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9304 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9307 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9311 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9312 BECount = EL0.ExactNotTaken;
9325 SymbolicMaxBECount =
9327 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9331ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9332 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9333 bool AllowPredicates) {
9345 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9347 if (EL.hasAnyInfo())
9350 auto *ExhaustiveCount =
9351 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9354 return ExhaustiveCount;
9356 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9359ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9361 bool ControlsOnlyExit,
bool AllowPredicates) {
9386 ConstantRange CompRange =
9404 InnerLHS = ZExt->getOperand();
9451 if (EL.hasAnyInfo())
9468 if (EL.hasAnyInfo())
return EL;
9500 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9502 if (EL.hasAnyInfo())
9518 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9520 if (EL.hasAnyInfo())
9531ScalarEvolution::ExitLimit
9532ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9534 BasicBlock *ExitingBlock,
9535 bool ControlsOnlyExit) {
9536 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9539 if (
Switch->getDefaultDest() == ExitingBlock)
9543 "Default case must not exit the loop!");
9549 if (EL.hasAnyInfo())
9561 "Evaluation of SCEV at constant didn't fold correctly?");
9565ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9575 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9582 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9584 unsigned &OutShiftAmt) {
9585 using namespace PatternMatch;
9587 ConstantInt *ShiftAmt;
9589 OutOpCode = Instruction::LShr;
9591 OutOpCode = Instruction::AShr;
9593 OutOpCode = Instruction::Shl;
9598 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9613 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9615 unsigned &ShiftAmtOut) {
9616 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9632 if (MatchPositiveShift(
LHS, V, OpC, Amt)) {
9633 PostShiftOpCode = OpC;
9639 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9642 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9648 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9655 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9661 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9673 ConstantInt *StableValue =
nullptr;
9678 case Instruction::AShr: {
9685 if (
Known.isNonNegative())
9686 StableValue = ConstantInt::get(Ty, 0);
9687 else if (
Known.isNegative())
9688 StableValue = ConstantInt::get(Ty, -1,
true);
9694 case Instruction::LShr:
9695 case Instruction::Shl:
9705 "Otherwise cannot be an operand to a branch instruction");
9707 if (
Result->isNullValue()) {
9716 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9718 const SCEV *StartSCEV =
getSCEV(StartValue);
9722 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9723 MaxBTC = std::min(MaxBTC, RangeBTC);
9727 const SCEV *UpperBound =
9745 if (
const Function *
F = CI->getCalledFunction())
9755 if (!L->contains(
I))
return false;
9760 return L->getHeader() ==
I->getParent();
9839 if (!
I)
return nullptr;
9853 std::vector<Constant*>
Operands(
I->getNumOperands());
9855 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9864 if (!
C)
return nullptr;
9886 if (IncomingVal != CurrentVal) {
9889 IncomingVal = CurrentVal;
9901ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9904 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9913 DenseMap<Instruction *, Constant *> CurrentIterVals;
9915 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9921 for (PHINode &
PHI : Header->phis()) {
9923 CurrentIterVals[&
PHI] = StartCST;
9925 if (!CurrentIterVals.
count(PN))
9926 return RetVal =
nullptr;
9932 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9935 unsigned IterationNum = 0;
9937 for (; ; ++IterationNum) {
9938 if (IterationNum == NumIterations)
9939 return RetVal = CurrentIterVals[PN];
9943 DenseMap<Instruction *, Constant *> NextIterVals;
9948 NextIterVals[PN] = NextPHI;
9950 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9956 for (
const auto &
I : CurrentIterVals) {
9958 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9963 for (
const auto &
I : PHIsToCompute) {
9964 PHINode *
PHI =
I.first;
9967 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9970 if (NextPHI !=
I.second)
9971 StoppedEvolving =
false;
9976 if (StoppedEvolving)
9977 return RetVal = CurrentIterVals[PN];
9979 CurrentIterVals.swap(NextIterVals);
9983const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
9993 DenseMap<Instruction *, Constant *> CurrentIterVals;
9995 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9998 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
10000 for (PHINode &
PHI : Header->phis()) {
10002 CurrentIterVals[&
PHI] = StartCST;
10004 if (!CurrentIterVals.
count(PN))
10012 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10019 if (CondVal->getValue() ==
uint64_t(ExitWhen)) {
10020 ++NumBruteForceTripCountsComputed;
10025 DenseMap<Instruction *, Constant *> NextIterVals;
10031 for (
const auto &
I : CurrentIterVals) {
10033 if (!
PHI ||
PHI->getParent() != Header)
continue;
10036 for (PHINode *
PHI : PHIsToCompute) {
10038 if (NextPHI)
continue;
10040 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10043 CurrentIterVals.
swap(NextIterVals);
10051 auto &
Values = ValuesAtScopes[V];
10055 return LS.second ? LS.second :
SCEVUse(V);
10057 Values.emplace_back(L,
nullptr);
10060 SCEVUse C = computeSCEVAtScope(V, L);
10061 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10062 if (LS.first == L) {
10068 ValuesAtScopesUsers[
C.getPointer()].push_back({L, V});
10079 switch (V->getSCEVType()) {
10112 assert(!
C->getType()->isPointerTy() &&
10113 "Can only have one pointer, and it must be last");
10138const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10139 SmallVectorImpl<SCEVUse> &NewOps) {
10173SCEVUse ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10174 switch (
V->getSCEVType()) {
10185 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10196 for (++i; i !=
e; ++i)
10236 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10246 for (++i; i !=
e; ++i) {
10251 return getWithOperands(V, NewOps);
10266 const Loop *CurrLoop = this->LI[
I->getParent()];
10277 if (BackedgeTakenCount->
isZero()) {
10278 Value *InitValue =
nullptr;
10279 bool MultipleInitValues =
false;
10285 MultipleInitValues =
true;
10290 if (!MultipleInitValues && InitValue)
10299 unsigned InLoopPred =
10310 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10324 SmallVector<Constant *, 4>
Operands;
10326 bool MadeImprovement =
false;
10341 MadeImprovement |= OrigV != OpV;
10346 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10351 if (!MadeImprovement)
10372const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10374 return stripInjectiveFunctions(ZExt->getOperand());
10376 return stripInjectiveFunctions(SExt->getOperand());
10394 assert(
A != 0 &&
"A must be non-zero.");
10410 if (MinTZ < Mult2 && L->getLoopPredecessor())
10412 if (MinTZ < Mult2) {
10435 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10455static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10461 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10462 << *AddRec <<
'\n');
10465 if (!LC || !MC || !
NC) {
10466 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10467 return std::nullopt;
10473 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10481 N =
N.sext(NewWidth);
10482 M = M.sext(NewWidth);
10483 L = L.sext(NewWidth);
10500 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10501 <<
", multiplied by " <<
T <<
'\n');
10510 std::optional<APInt>
Y) {
10512 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10515 return XW.
slt(YW) ? *
X : *
Y;
10518 return std::nullopt;
10519 return X ? *
X : *
Y;
10536 return std::nullopt;
10537 unsigned W =
X->getBitWidth();
10557static std::optional<APInt>
10563 return std::nullopt;
10566 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10567 std::optional<APInt>
X =
10570 return std::nullopt;
10575 return std::nullopt;
10590static std::optional<APInt>
10594 "Starting value of addrec should be 0");
10595 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10596 <<
Range <<
", addrec " << *AddRec <<
'\n');
10600 "Addrec's initial value should be in range");
10606 return std::nullopt;
10616 auto SolveForBoundary =
10617 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10620 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10621 << Bound <<
" (before multiplying by " << M <<
")\n");
10624 std::optional<APInt> SO;
10627 "signed overflow\n");
10631 "unsigned overflow\n");
10632 std::optional<APInt> UO =
10635 auto LeavesRange = [&] (
const APInt &
X) {
10643 if (
Range.contains(
V1->getValue()))
10652 return {std::nullopt,
false};
10657 if (LeavesRange(*Min))
10658 return { Min,
true };
10659 std::optional<APInt> Max = Min == SO ? UO : SO;
10660 if (LeavesRange(*Max))
10661 return { Max,
true };
10664 return {std::nullopt,
true};
10671 auto SL = SolveForBoundary(
Lower);
10672 auto SU = SolveForBoundary(
Upper);
10675 if (!SL.second || !SU.second)
10676 return std::nullopt;
10719ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10721 bool ControlsOnlyExit,
10722 bool AllowPredicates) {
10733 if (
C->getValue()->isZero())
return C;
10737 const SCEVAddRecExpr *AddRec =
10740 if (!AddRec && AllowPredicates)
10746 if (!AddRec || AddRec->
getLoop() != L)
10757 return ExitLimit(R, R, R,
false, Predicates);
10815 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10845 const SCEV *
Exact =
10853 const SCEV *SymbolicMax =
10855 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10864 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10872 return ExitLimit(
E, M, S,
false, Predicates);
10875ScalarEvolution::ExitLimit
10876ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10884 if (!
C->getValue()->isZero())
10894std::pair<const BasicBlock *, const BasicBlock *>
10895ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10906 if (
const Loop *L = LI.getLoopFor(BB))
10907 return {
L->getLoopPredecessor(),
L->getHeader()};
10909 return {
nullptr, BB};
10918 if (
A ==
B)
return true;
10933 if (ComputesEqualValues(AI, BI))
10941 const SCEV *Op0, *Op1;
10960 auto TrivialCase = [&](
bool TriviallyTrue) {
10969 const SCEV *NewLHS, *NewRHS;
10993 return TrivialCase(
false);
10994 return TrivialCase(
true);
11013 RAdd->hasNoSignedWrap()) ||
11015 RAdd->hasNoUnsignedWrap())) {
11035 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
11036 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
11039 C->getAPInt().isStrictlyPositive()) ||
11063 const APInt &
RA = RC->getAPInt();
11065 bool SimplifiedByConstantRange =
false;
11070 return TrivialCase(
true);
11072 return TrivialCase(
false);
11081 Changed = SimplifiedByConstantRange =
true;
11085 if (!SimplifiedByConstantRange) {
11102 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11108 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11114 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11120 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11140 return TrivialCase(
true);
11142 return TrivialCase(
false);
11247 auto NonRecursive = [OrNegative](
const SCEV *S) {
11249 return C->getAPInt().isPowerOf2() ||
11250 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11256 if (NonRecursive(S))
11266 const SCEV *S, uint64_t M,
11282 APInt C = Cst->getAPInt();
11283 return C.urem(M) == 0;
11291 const SCEV *SmodM =
11309 for (
auto *
A : *Predicates)
11310 if (
A->implies(
P, *
this))
11323std::pair<const SCEV *, const SCEV *>
11326 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11328 return { Start, Start };
11330 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11339 getUsedLoops(LHS, LoopsUsed);
11340 getUsedLoops(RHS, LoopsUsed);
11342 if (LoopsUsed.
empty())
11347 for (
const auto *L1 : LoopsUsed)
11348 for (
const auto *L2 : LoopsUsed)
11349 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11350 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11351 "Domination relationship is not a linear order");
11381 SplitRHS.second) &&
11391 isKnownPredicateViaSplitting(Pred, LHS, RHS) ||
11392 isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11402 return std::nullopt;
11417 if (KnownWithoutContext)
11418 return KnownWithoutContext;
11425 return std::nullopt;
11431 const Loop *L = LHS->getLoop();
11436std::optional<ScalarEvolution::MonotonicPredicateType>
11439 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11445 auto ResultSwapped =
11448 assert(*ResultSwapped != *Result &&
11449 "monotonicity should flip as we flip the predicate");
11456std::optional<ScalarEvolution::MonotonicPredicateType>
11457ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11471 return std::nullopt;
11475 "Should be greater or less!");
11479 if (!LHS->hasNoUnsignedWrap())
11480 return std::nullopt;
11484 "Relational predicate is either signed or unsigned!");
11485 if (!
LHS->hasNoSignedWrap())
11486 return std::nullopt;
11488 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11496 return std::nullopt;
11499std::optional<ScalarEvolution::LoopInvariantPredicate>
11506 return std::nullopt;
11513 if (!ArLHS || ArLHS->
getLoop() != L)
11514 return std::nullopt;
11518 return std::nullopt;
11544 return std::nullopt;
11581 return std::nullopt;
11584std::optional<ScalarEvolution::LoopInvariantPredicate>
11589 Pred, LHS, RHS, L, CtxI, MaxIter))
11599 Pred, LHS, RHS, L, CtxI,
Op))
11601 return std::nullopt;
11604std::optional<ScalarEvolution::LoopInvariantPredicate>
11619 return std::nullopt;
11626 if (!AR || AR->
getLoop() != L)
11627 return std::nullopt;
11632 Pred = Pred.dropSameSign();
11636 return std::nullopt;
11642 if (Step != One && Step != MinusOne)
11643 return std::nullopt;
11649 return std::nullopt;
11655 return std::nullopt;
11663 if (Step == MinusOne)
11667 return std::nullopt;
11673bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11679 auto CheckRange = [&](
bool IsSigned) {
11682 return RangeLHS.
icmp(Pred, RangeRHS);
11691 if (CheckRange(
true) || CheckRange(
false))
11700bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11709 SCEVUse XNonConstOp, XConstOp;
11710 SCEVUse YNonConstOp, YConstOp;
11714 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11717 XFlagsPresent = ExpectedFlags;
11722 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11725 YFlagsPresent = ExpectedFlags;
11728 if (YNonConstOp != XNonConstOp)
11736 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11739 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11799bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11820bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11821 const SCEV *
LHS,
const SCEV *
RHS) {
11826 return any_of(*BB, [&](
const Instruction &
I) {
11827 using namespace llvm::PatternMatch;
11832 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11846 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11851 "This cannot be done on broken IR!");
11854 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11863 if (LoopContinuePredicate &&
11864 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11865 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11870 if (WalkingBEDominatingConds)
11876 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11877 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11884 const SCEV *LoopCounter =
11892 for (
auto &AssumeVH : AC.assumptions()) {
11899 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11903 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11906 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11907 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11908 assert(DTN &&
"should reach the loop header before reaching the root!");
11911 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11929 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
11942 if (!DT.isReachableFromEntry(BB))
11946 "This cannot be done on broken IR!");
11954 const bool ProvingStrictComparison =
11956 bool ProvedNonStrictComparison =
false;
11957 bool ProvedNonEquality =
false;
11960 if (!ProvedNonStrictComparison)
11961 ProvedNonStrictComparison = Fn(NonStrictPredicate);
11962 if (!ProvedNonEquality)
11964 if (ProvedNonStrictComparison && ProvedNonEquality)
11969 if (ProvingStrictComparison) {
11971 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
11973 if (SplitAndProve(ProofFn))
11978 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
11980 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
11982 if (ProvingStrictComparison) {
11984 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
11986 if (SplitAndProve(ProofFn))
11995 const Loop *ContainingLoop = LI.getLoopFor(BB);
11997 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
12001 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
12002 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
12005 if (!BlockEntryPredicate)
12014 for (
auto &AssumeVH : AC.assumptions()) {
12018 if (!DT.dominates(CI, BB))
12021 if (ProveViaCond(CI->getArgOperand(0),
false))
12027 F.getParent(), Intrinsic::experimental_guard);
12029 for (
const auto *GU : GuardDecl->users())
12031 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12032 if (ProveViaCond(Guard->getArgOperand(0),
false))
12047 "LHS is not available at Loop Entry");
12049 "RHS is not available at Loop Entry");
12051 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12062 if (FoundCondValue ==
12066 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12070 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12073 const Value *Op0, *Op1;
12076 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12080 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12081 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12085 if (!ICI)
return false;
12089 CmpPredicate FoundPred;
12098 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12101bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12102 const SCEV *
RHS, CmpPredicate FoundPred,
12103 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12104 const Instruction *CtxI) {
12114 auto *WideType = FoundLHS->
getType();
12126 TruncFoundLHS, TruncFoundRHS, CtxI))
12152 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12156bool ScalarEvolution::isImpliedCondBalancedTypes(
12161 "Types should be balanced!");
12168 if (FoundLHS == FoundRHS)
12172 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12184 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12201 LHS, FoundLHS, FoundRHS, CtxI);
12203 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12225 assert(P1 != P2 &&
"Handled earlier!");
12229 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12233 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12236 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12237 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12238 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12243 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12254 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12255 CanonicalRHS, CanonicalFoundLHS,
12256 CanonicalFoundRHS);
12261 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12262 CanonicalRHS, CanonicalFoundLHS,
12263 CanonicalFoundRHS);
12270 const SCEVConstant *
C =
nullptr;
12271 const SCEV *
V =
nullptr;
12289 if (Min ==
C->getAPInt()) {
12294 APInt SharperMin = Min + 1;
12297 case ICmpInst::ICMP_SGE:
12298 case ICmpInst::ICMP_UGE:
12301 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12306 case ICmpInst::ICMP_SGT:
12307 case ICmpInst::ICMP_UGT:
12317 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12322 case ICmpInst::ICMP_SLE:
12323 case ICmpInst::ICMP_ULE:
12324 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12325 LHS, V, getConstant(SharperMin), CtxI))
12329 case ICmpInst::ICMP_SLT:
12330 case ICmpInst::ICMP_ULT:
12331 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12332 LHS, V, getConstant(Min), CtxI))
12346 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12350 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12353 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12369std::optional<APInt>
12376 APInt DiffMul(BW, 1);
12379 for (
unsigned I = 0;
I < 8; ++
I) {
12388 if (LAR->getLoop() != MAR->getLoop())
12389 return std::nullopt;
12393 if (!LAR->isAffine() || !MAR->isAffine())
12394 return std::nullopt;
12396 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12397 return std::nullopt;
12399 Less = LAR->getStart();
12400 More = MAR->getStart();
12405 auto MatchConstMul =
12406 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12411 return std::nullopt;
12413 if (
auto MatchedMore = MatchConstMul(More)) {
12414 if (
auto MatchedLess = MatchConstMul(
Less)) {
12415 if (MatchedMore->second == MatchedLess->second) {
12416 More = MatchedMore->first;
12417 Less = MatchedLess->first;
12418 DiffMul *= MatchedMore->second;
12429 Diff +=
C->getAPInt() * DiffMul;
12432 Diff -=
C->getAPInt() * DiffMul;
12435 Multiplicity[S] +=
Mul;
12437 auto Decompose = [&](
const SCEV *S,
int Mul) {
12444 Decompose(More, 1);
12445 Decompose(
Less, -1);
12449 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12450 for (
const auto &[S,
Mul] : Multiplicity) {
12455 return std::nullopt;
12457 }
else if (
Mul == -1) {
12459 return std::nullopt;
12462 return std::nullopt;
12466 if (NewMore == More || NewLess ==
Less)
12467 return std::nullopt;
12473 if (!More && !
Less)
12477 if (!More || !
Less)
12478 return std::nullopt;
12482 return std::nullopt;
12485bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12507 const auto *Latch = L->getLoopLatch();
12510 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12519 const auto *Latch = L->getLoopLatch();
12522 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12532bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12535 const SCEV *FoundLHS,
12536 const SCEV *FoundRHS) {
12545 if (!AddRecFoundLHS)
12552 const Loop *
L = AddRecFoundLHS->getLoop();
12553 if (L != AddRecLHS->getLoop())
12592 if (!RDiff || *LDiff != *RDiff)
12595 if (LDiff->isMinValue())
12598 APInt FoundRHSLimit;
12601 FoundRHSLimit = -(*RDiff);
12613bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12614 const SCEV *
RHS,
const SCEV *FoundLHS,
12615 const SCEV *FoundRHS,
unsigned Depth) {
12616 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12620 bool Erased = PendingMerges.erase(LPhi);
12621 assert(Erased &&
"Failed to erase LPhi!");
12625 bool Erased = PendingMerges.erase(RPhi);
12626 assert(Erased &&
"Failed to erase RPhi!");
12634 if (!PendingMerges.insert(Phi).second)
12648 if (!PendingMerges.insert(Phi).second)
12654 if (!LPhi && !RPhi)
12665 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12669 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12670 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12671 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12672 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12675 if (RPhi && RPhi->getParent() == LBB) {
12682 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12683 if (!ProvedEasily(L, R))
12694 auto *RLoop = RAR->
getLoop();
12695 auto *Predecessor = RLoop->getLoopPredecessor();
12696 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12698 if (!ProvedEasily(L1, RAR->
getStart()))
12700 auto *Latch = RLoop->getLoopLatch();
12701 assert(Latch &&
"Loop with AddRec with no latch?");
12722 if (
auto *
Loop = LI.getLoopFor(LBB))
12725 if (!ProvedEasily(L,
RHS))
12732bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12735 const SCEV *FoundLHS,
12736 const SCEV *FoundRHS) {
12739 if (
RHS == FoundRHS) {
12744 if (
LHS != FoundLHS)
12751 Value *Shiftee, *ShiftValue;
12753 using namespace PatternMatch;
12754 if (
match(SUFoundRHS->getValue(),
12756 auto *ShifteeS =
getSCEV(Shiftee);
12774bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12775 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12776 const SCEV *FoundRHS) {
12808 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12816 return Diff == FoundDiff;
12819bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12821 const SCEV *FoundLHS,
12822 const SCEV *FoundRHS,
12823 const Instruction *CtxI) {
12824 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12826 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12828 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12829 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12831 isImpliedCondOperandsViaMatchingDiff(Pred,
LHS,
RHS, FoundLHS,
12833 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12837template <
typename MinMaxExprType>
12839 const SCEV *Candidate) {
12844 return is_contained(MinMaxExpr->operands(), Candidate);
12857 const SCEV *LStart, *RStart, *Step;
12955bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12957 const SCEV *FoundLHS,
12958 const SCEV *FoundRHS,
12962 "LHS and RHS have different sizes?");
12965 "FoundLHS and FoundRHS have different sizes?");
12999 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
13001 return Ext->getOperand();
13008 auto *OrigLHS =
LHS;
13009 auto *OrigFoundLHS = FoundLHS;
13010 LHS = GetOpFromSExt(
LHS);
13011 FoundLHS = GetOpFromSExt(FoundLHS);
13014 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
13017 FoundRHS,
Depth + 1);
13030 if (!LHSAddExpr->hasNoSignedWrap())
13033 SCEVUse LL = LHSAddExpr->getOperand(0);
13034 SCEVUse LR = LHSAddExpr->getOperand(1);
13038 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
13039 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
13044 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
13050 using namespace llvm::PatternMatch;
13069 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13077 auto *DTy = Denominator->getType();
13078 auto *FRHSTy = FoundRHS->
getType();
13079 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13098 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13109 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13111 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13119 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13152bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13156 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13160 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13163bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13166 const SCEV *FoundLHS,
13167 const SCEV *FoundRHS) {
13203 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13209bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13210 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13211 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13225 ConstantRange FoundLHSRange =
13229 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13236 return LHSRange.
icmp(Pred, ConstRHS);
13239bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13252 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13260 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13263bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
13275 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
13283 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
13295const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
13296 const SCEV *Stride,
13327 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13338 :
APIntOps::umax(MaxEnd, MinStart);
13345ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13346 const Loop *L,
bool IsSigned,
13347 bool ControlsOnlyExit,
bool AllowPredicates) {
13351 bool PredicatedIV =
false;
13356 auto canProveNUW = [&]() {
13359 if (!ControlsOnlyExit)
13380 Limit = Limit.
zext(OuterBitWidth);
13392 Type *Ty = ZExt->getType();
13403 if (!
IV && AllowPredicates) {
13408 PredicatedIV =
true;
13412 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13426 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13429 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13434 bool IVMayOverflow =
true;
13437 if (!PositiveStride) {
13489 auto wouldZeroStrideBeUB = [&]() {
13501 if (!wouldZeroStrideBeUB()) {
13508 IVMayOverflow = canIVOverflowOnLT(
RHS, Stride, IsSigned);
13509 if (IVMayOverflow && !NoWrap)
13522 const SCEV *
Start =
IV->getStart();
13528 const SCEV *OrigStart =
Start;
13529 const SCEV *OrigRHS =
RHS;
13530 if (
Start->getType()->isPointerTy()) {
13541 const SCEV *End =
nullptr, *BECount =
nullptr,
13542 *BECountIfBackedgeTaken =
nullptr;
13545 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13546 any(RHSAddRec->getNoWrapFlags())) {
13559 const SCEV *RHSStart = RHSAddRec->getStart();
13560 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13572 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13581 BECountIfBackedgeTaken =
13586 if (BECount ==
nullptr) {
13591 const SCEV *MaxBECount = computeMaxBECountForLT(
13594 MaxBECount,
false , Predicates);
13600 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13606 if ((!IVMayOverflow ||
13639 const SCEV *Numerator =
13645 auto canProveRHSGreaterThanEqualStart = [&]() {
13664 auto *StartMinusOne =
13671 if (canProveRHSGreaterThanEqualStart()) {
13686 BECountIfBackedgeTaken =
13706 bool MayAddOverflow = IVMayOverflow && [&] {
13752 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13766 if (!MayAddOverflow) {
13778 const SCEV *ConstantMaxBECount;
13779 bool MaxOrZero =
false;
13781 ConstantMaxBECount = BECount;
13782 }
else if (BECountIfBackedgeTaken &&
13787 ConstantMaxBECount = BECountIfBackedgeTaken;
13790 ConstantMaxBECount = computeMaxBECountForLT(
13798 const SCEV *SymbolicMaxBECount =
13800 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13804ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13805 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13806 bool ControlsOnlyExit,
bool AllowPredicates) {
13813 if (!
IV && AllowPredicates)
13820 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13824 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13837 bool MayAddOverflow =
false;
13838 const SCEV *
Start =
IV->getStart();
13839 const SCEV *End =
RHS;
13840 if (!Stride->
isOne() && canIVOverflowOnGT(
RHS, Stride, IsSigned)) {
13843 MayAddOverflow =
true;
13856 if (
Start->getType()->isPointerTy()) {
13868 const SCEV *BECount;
13869 if (MayAddOverflow) {
13900 const SCEV *ConstantMaxBECount =
13907 ConstantMaxBECount = BECount;
13908 const SCEV *SymbolicMaxBECount =
13911 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13917 if (
Range.isFullSet())
13922 if (!SC->getValue()->isZero()) {
13928 return ShiftedAddRec->getNumIterationsInRange(
13929 Range.subtract(SC->getAPInt()), SE);
13960 APInt ExitVal = (End +
A).udiv(
A);
13973 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13974 "Linear scev computation is off in a bad way!");
14005 assert(!
Last->isZero() &&
"Recurrency with zero step?");
14031 Ty =
Store->getValueOperand()->getType();
14032 PtrTy =
Store->getPointerOperandType();
14034 Ty =
Load->getType();
14035 PtrTy =
Load->getPointerOperandType();
14049 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14051 SE->ConstantEvolutionLoopExitValue.erase(PN);
14052 SE->eraseValueFromMap(getValPtr());
14056void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
14057 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14067 : CallbackVH(
V), SE(se) {}
14076 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
14078 LoopDispositions(64), BlockDispositions(64) {
14090 F.getParent(), Intrinsic::experimental_guard);
14091 HasGuards = GuardDecl && !GuardDecl->use_empty();
14095 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
14096 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14097 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14098 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14099 PendingMerges(
std::
move(Arg.PendingMerges)),
14100 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14101 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14102 PredicatedBackedgeTakenCounts(
14103 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14104 BECountUsers(
std::
move(Arg.BECountUsers)),
14105 ConstantEvolutionLoopExitValue(
14106 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14107 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14108 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14109 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14110 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14111 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14112 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14113 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14114 SignedRanges(
std::
move(Arg.SignedRanges)),
14115 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14116 UniquePreds(
std::
move(Arg.UniquePreds)),
14117 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14118 ConstantSCEVs(
std::
move(Arg.ConstantSCEVs)),
14119 LoopUsers(
std::
move(Arg.LoopUsers)),
14120 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14121 FirstUnknown(Arg.FirstUnknown) {
14122 Arg.FirstUnknown =
nullptr;
14131 Tmp->~SCEVUnknown();
14133 FirstUnknown =
nullptr;
14135 ExprValueMap.clear();
14136 ValueExprMap.clear();
14138 BackedgeTakenCounts.clear();
14139 PredicatedBackedgeTakenCounts.clear();
14141 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14142 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14143 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14144 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14166 L->getHeader()->printAsOperand(OS,
false);
14170 L->getExitingBlocks(ExitingBlocks);
14171 if (ExitingBlocks.
size() != 1)
14172 OS <<
"<multiple exits> ";
14176 OS <<
"backedge-taken count is ";
14179 OS <<
"Unpredictable backedge-taken count.";
14182 if (ExitingBlocks.
size() > 1)
14183 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14184 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14192 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14195 OS <<
"\n Predicates:\n";
14196 for (
const auto *
P : Predicates)
14204 L->getHeader()->printAsOperand(OS,
false);
14209 OS <<
"constant max backedge-taken count is ";
14212 OS <<
", actual taken count either this or zero.";
14214 OS <<
"Unpredictable constant max backedge-taken count. ";
14219 L->getHeader()->printAsOperand(OS,
false);
14224 OS <<
"symbolic max backedge-taken count is ";
14227 OS <<
", actual taken count either this or zero.";
14229 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14233 if (ExitingBlocks.
size() > 1)
14234 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14235 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14245 OS <<
"\n predicated symbolic max exit count for "
14246 << ExitingBlock->
getName() <<
": ";
14248 OS <<
"\n Predicates:\n";
14249 for (
const auto *
P : Predicates)
14260 L->getHeader()->printAsOperand(OS,
false);
14263 OS <<
"Predicated backedge-taken count is ";
14266 OS <<
"Unpredictable predicated backedge-taken count.";
14268 OS <<
" Predicates:\n";
14269 for (
const auto *
P : Preds)
14274 auto *PredConstantMax =
14276 if (PredConstantMax != ConstantBTC) {
14278 L->getHeader()->printAsOperand(OS,
false);
14281 OS <<
"Predicated constant max backedge-taken count is ";
14284 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14286 OS <<
" Predicates:\n";
14287 for (
const auto *
P : Preds)
14292 auto *PredSymbolicMax =
14294 if (SymbolicBTC != PredSymbolicMax) {
14296 L->getHeader()->printAsOperand(OS,
false);
14299 OS <<
"Predicated symbolic max backedge-taken count is ";
14302 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14304 OS <<
" Predicates:\n";
14305 for (
const auto *
P : Preds)
14311 L->getHeader()->printAsOperand(OS,
false);
14338 OS <<
"Computable";
14348 OS <<
"DoesNotDominate";
14354 OS <<
"ProperlyDominates";
14371 OS <<
"Classifying expressions for: ";
14372 F.printAsOperand(OS,
false);
14387 const Loop *L = LI.getLoopFor(
I.getParent());
14402 OS <<
"\t\t" "Exits: ";
14405 OS <<
"<<Unknown>>";
14411 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14413 Iter->getHeader()->printAsOperand(OS,
false);
14421 InnerL->getHeader()->printAsOperand(OS,
false);
14432 OS <<
"Determining loop execution counts for: ";
14433 F.printAsOperand(OS,
false);
14441 auto &
Values = LoopDispositions[S];
14442 for (
auto &V :
Values) {
14443 if (V.getPointer() == L)
14448 auto &Values2 = LoopDispositions[S];
14450 if (V.getPointer() == L) {
14459ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14477 if (L->contains(AR->
getLoop()) &&
14479 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14484 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14485 " dominate the contained loop's header?");
14512 bool HasVarying =
false;
14513 bool HasUniform =
false;
14555 auto &
Values = BlockDispositions[S];
14556 for (
auto &V :
Values) {
14557 if (V.getPointer() == BB)
14562 auto &Values2 = BlockDispositions[S];
14564 if (V.getPointer() == BB) {
14573ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14602 bool Proper =
true;
14613 if (Instruction *
I =
14615 if (
I->getParent() == BB)
14617 if (DT.properlyDominates(
I->getParent(), BB))
14640void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14643 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14644 auto It = BECounts.find(L);
14645 if (It != BECounts.end()) {
14646 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14647 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14649 auto UserIt = BECountUsers.find(S);
14650 assert(UserIt != BECountUsers.end());
14655 BECounts.erase(It);
14663 while (!Worklist.
empty()) {
14665 auto Users = SCEVUsers.find(Curr);
14666 if (
Users != SCEVUsers.end())
14667 for (
const auto *User :
Users->second)
14668 if (ToForget.
insert(User).second)
14672 for (
const auto *S : ToForget)
14673 forgetMemoizedResultsImpl(S);
14675 PredicatedSCEVRewrites.remove_if(
14676 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14679void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14680 LoopDispositions.erase(S);
14681 BlockDispositions.erase(S);
14682 UnsignedRanges.erase(S);
14683 SignedRanges.erase(S);
14684 HasRecMap.erase(S);
14685 ConstantMultipleCache.erase(S);
14688 UnsignedWrapViaInductionTried.erase(AR);
14689 SignedWrapViaInductionTried.erase(AR);
14692 auto ExprIt = ExprValueMap.find(S);
14693 if (ExprIt != ExprValueMap.end()) {
14694 for (
Value *V : ExprIt->second) {
14695 auto ValueIt = ValueExprMap.find_as(V);
14696 if (ValueIt != ValueExprMap.end())
14697 ValueExprMap.erase(ValueIt);
14699 ExprValueMap.erase(ExprIt);
14702 auto ScopeIt = ValuesAtScopes.find(S);
14703 if (ScopeIt != ValuesAtScopes.end()) {
14704 for (
const auto &Pair : ScopeIt->second)
14706 llvm::erase(ValuesAtScopesUsers[Pair.second.getPointer()],
14707 std::make_pair(Pair.first, S));
14708 ValuesAtScopes.erase(ScopeIt);
14711 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14712 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14713 for (
const auto &Pair : ScopeUserIt->second)
14716 llvm::erase_if(ValuesAtScopes[Pair.second], [&](
const auto &LS) {
14717 return LS.first == Pair.first && LS.second.getPointer() == S;
14719 ValuesAtScopesUsers.erase(ScopeUserIt);
14722 auto BEUsersIt = BECountUsers.find(S);
14723 if (BEUsersIt != BECountUsers.end()) {
14725 auto Copy = BEUsersIt->second;
14726 for (
const auto &Pair : Copy)
14727 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14728 BECountUsers.erase(BEUsersIt);
14731 auto FoldUser = FoldCacheUser.find(S);
14732 if (FoldUser != FoldCacheUser.end())
14733 for (
auto &KV : FoldUser->second)
14734 FoldCache.erase(KV);
14735 FoldCacheUser.erase(S);
14739ScalarEvolution::getUsedLoops(
const SCEV *S,
14741 struct FindUsedLoops {
14742 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14743 : LoopsUsed(LoopsUsed) {}
14744 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14745 bool follow(
const SCEV *S) {
14751 bool isDone()
const {
return false; }
14754 FindUsedLoops
F(LoopsUsed);
14755 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14758void ScalarEvolution::getReachableBlocks(
14761 Worklist.
push_back(&F.getEntryBlock());
14762 while (!Worklist.
empty()) {
14764 if (!Reachable.
insert(BB).second)
14772 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14779 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14783 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14818 SCEVMapper SCM(SE2);
14820 SE2.getReachableBlocks(ReachableBlocks, F);
14822 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14840 while (!LoopStack.
empty()) {
14846 if (!ReachableBlocks.
contains(L->getHeader()))
14851 auto It = BackedgeTakenCounts.find(L);
14852 if (It == BackedgeTakenCounts.end())
14856 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14876 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14877 if (Delta && !Delta->
isZero()) {
14878 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14879 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14880 dbgs() <<
"New: " << *NewBECount <<
"\n";
14881 dbgs() <<
"Delta: " << *Delta <<
"\n";
14889 while (!Worklist.
empty()) {
14891 if (ValidLoops.
insert(L).second)
14892 Worklist.
append(L->begin(), L->end());
14894 for (
const auto &KV : ValueExprMap) {
14899 "AddRec references invalid loop");
14904 auto It = ExprValueMap.find(KV.second);
14905 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14906 dbgs() <<
"Value " << *KV.first
14907 <<
" is in ValueExprMap but not in ExprValueMap\n";
14912 if (!ReachableBlocks.
contains(
I->getParent()))
14914 const SCEV *OldSCEV = SCM.visit(KV.second);
14916 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14917 if (Delta && !Delta->
isZero()) {
14918 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14919 <<
"Old: " << *OldSCEV <<
"\n"
14920 <<
"New: " << *NewSCEV <<
"\n"
14921 <<
"Delta: " << *Delta <<
"\n";
14927 for (
const auto &KV : ExprValueMap) {
14928 for (
Value *V : KV.second) {
14929 const SCEV *S = ValueExprMap.lookup(V);
14931 dbgs() <<
"Value " << *V
14932 <<
" is in ExprValueMap but not in ValueExprMap\n";
14935 if (S != KV.first) {
14936 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14937 << *KV.first <<
"\n";
14944 for (
const auto &S : UniqueSCEVs) {
14949 auto It = SCEVUsers.find(
Op);
14950 if (It != SCEVUsers.end() && It->second.count(&S))
14952 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14953 <<
" is not being tracked!\n";
14959 for (
const auto &ValueAndVec : ValuesAtScopes) {
14961 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14962 const Loop *L = LoopAndValueAtScope.first;
14963 SCEVUse ValueAtScope = LoopAndValueAtScope.second;
14965 auto It = ValuesAtScopesUsers.find(ValueAtScope.
getPointer());
14966 if (It != ValuesAtScopesUsers.end() &&
14969 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14970 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14976 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14977 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14978 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14979 const Loop *L = LoopAndValue.first;
14980 const SCEV *
Value = LoopAndValue.second;
14982 auto It = ValuesAtScopes.find(
Value);
14985 if (It != ValuesAtScopes.end() &&
any_of(It->second, [&](
const auto &LS) {
14986 return LS.first == L && LS.second.getPointer() == ValueAtScope;
14989 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14990 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14996 auto VerifyBECountUsers = [&](
bool Predicated) {
14998 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14999 for (
const auto &LoopAndBEInfo : BECounts) {
15000 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
15001 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
15003 auto UserIt = BECountUsers.find(S);
15004 if (UserIt != BECountUsers.end() &&
15005 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
15007 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
15008 <<
" missing from BECountUsers\n";
15015 VerifyBECountUsers(
false);
15016 VerifyBECountUsers(
true);
15019 for (
auto &[S,
Values] : LoopDispositions) {
15020 for (
auto [
Loop, CachedDisposition] :
Values) {
15022 if (CachedDisposition != RecomputedDisposition) {
15023 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
15024 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
15025 << RecomputedDisposition <<
"\n";
15032 for (
auto &[S,
Values] : BlockDispositions) {
15033 for (
auto [BB, CachedDisposition] :
Values) {
15035 if (CachedDisposition != RecomputedDisposition) {
15036 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
15037 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
15038 <<
", actual " << RecomputedDisposition <<
"\n";
15045 for (
auto [
FoldID, Expr] : FoldCache) {
15046 auto I = FoldCacheUser.find(Expr);
15047 if (
I == FoldCacheUser.end()) {
15048 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
15053 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
15057 for (
auto [Expr, IDs] : FoldCacheUser) {
15058 for (
auto &
FoldID : IDs) {
15061 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
15066 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
15067 <<
" != " << *Expr <<
"!\n";
15078 for (
auto [S, Multiple] : ConstantMultipleCache) {
15080 if ((Multiple != 0 && RecomputedMultiple != 0 &&
15081 Multiple.
urem(RecomputedMultiple) != 0 &&
15082 RecomputedMultiple.
urem(Multiple) != 0)) {
15083 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
15084 << *S <<
" : Computed " << RecomputedMultiple
15085 <<
" but cache contains " << Multiple <<
"!\n";
15093 FunctionAnalysisManager::Invalidator &Inv) {
15125 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15126 <<
F.getName() <<
"':\n";
15132 "Scalar Evolution Analysis",
false,
true)
15181 const SCEV *LHS,
const SCEV *RHS) {
15183 assert(LHS->getType() == RHS->getType() &&
15184 "Type mismatch between LHS and RHS");
15187 ID.AddInteger(Pred);
15188 ID.AddPointer(LHS);
15189 ID.AddPointer(RHS);
15191 if (
const auto *S = UniquePreds.lookup(ID, Token))
15195 UniquePreds.insert(Eq, Token);
15206 ID.AddInteger(AddedFlags);
15208 if (
const auto *S = UniquePreds.lookup(ID, Token))
15210 auto *OF =
new (SCEVAllocator)
15212 UniquePreds.insert(OF, Token);
15232 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15233 return Rewriter.visit(S);
15239 for (
const auto *Pred : U->getPredicates())
15241 if (IPred->getLHS() == Expr &&
15243 return IPred->getRHS();
15245 if (IPred->getLHS() == Expr &&
15246 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15247 return IPred->getRHS();
15250 return convertToAddRecWithPreds(Expr);
15253 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15269 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15286 explicit SCEVPredicateRewriter(
15287 const Loop *L, ScalarEvolution &SE,
15288 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15289 const SCEVPredicate *Pred)
15290 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15292 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15295 return Pred && Pred->
implies(
P, SE);
15301 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15304 return addOverflowAssumption(
A);
15313 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15317 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15319 if (!PredicatedRewrite)
15321 for (
const auto *
P : PredicatedRewrite->second){
15324 if (L != WP->getExpr()->getLoop())
15327 if (!addOverflowAssumption(
P))
15330 return PredicatedRewrite->first;
15333 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15334 const SCEVPredicate *Pred;
15343 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15350 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15370 if (!Step->
isOne())
15395 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15396 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15409 return Op->LHS == LHS &&
Op->RHS == RHS;
15416 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15418 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15443 const SCEV *Start = AR->getStart();
15444 const SCEV *OpStart =
Op->AR->getStart();
15449 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15458 const SCEV *Step = AR->getStepRecurrence(SE);
15459 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15512 if (Step->getValue()->getValue().isNonNegative())
15516 return ImpliedFlags;
15523 for (
const auto *
P : Preds)
15536 return this->implies(I, SE);
15548 const Loop *L = NWrap->getExpr()->getLoop();
15555 return RewrittenAR &&
15561 for (
const auto *Pred : Preds)
15562 Pred->print(OS,
Depth);
15567 for (
const auto *Pred : Set->Preds)
15575 bool CheckImplies = Preds.
size() < 16;
15578 if (CheckImplies &&
implies(
N, SE))
15584 for (
auto *
P : Preds) {
15585 if (CheckImplies &&
N->implies(
P, SE))
15589 Preds = std::move(PrunedPreds);
15590 Preds.push_back(
N);
15597 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15606 SCEVUsers[
Op].insert(
User);
15610 const SCEV *Expr = SE.getSCEV(V);
15615 RewriteEntry &Entry = RewriteMap[Expr];
15618 if (Entry.second && Generation == Entry.first)
15619 return Entry.second;
15624 Expr = Entry.second;
15626 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15627 Entry = {Generation, NewSCEV};
15633 if (!BackedgeCount) {
15635 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15636 for (
const auto *
P : Preds)
15639 return BackedgeCount;
15643 if (!SymbolicMaxBackedgeCount) {
15645 SymbolicMaxBackedgeCount =
15646 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15647 for (
const auto *
P : Preds)
15650 return SymbolicMaxBackedgeCount;
15654 if (!SmallConstantMaxTripCount) {
15656 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15657 for (
const auto *
P : Preds)
15660 return *SmallConstantMaxTripCount;
15664 if (Preds->implies(&Pred, SE))
15669 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15670 updateGeneration();
15683void PredicatedScalarEvolution::updateGeneration() {
15685 if (++Generation == 0) {
15686 for (
auto &
II : RewriteMap) {
15687 const SCEV *Rewritten =
II.second.second;
15709 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15715 ExtraPreds->
append(NewPreds);
15721 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15727 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15730 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15734 for (
auto *BB : L.getBlocks())
15735 for (
auto &
I : *BB) {
15736 if (!SE.isSCEVable(
I.getType()))
15739 auto *Expr = SE.getSCEV(&
I);
15740 auto II = RewriteMap.find(Expr);
15742 if (
II == RewriteMap.end())
15746 if (
II->second.second == Expr)
15751 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15759 LoopGuards Guards(SE);
15767void ScalarEvolution::LoopGuards::collectFromPHI(
15775 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15776 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15790 auto &RewriteMap =
G->second.RewriteMap;
15791 if (RewriteMap.empty())
15793 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15794 if (S == RewriteMap.end())
15800 return {C0, SM->getSCEVType()};
15803 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15804 MinMaxPattern
P2) -> MinMaxPattern {
15805 auto [C1,
T1] =
P1;
15806 auto [C2, T2] =
P2;
15807 if (!C1 || !C2 ||
T1 != T2)
15811 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15813 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15815 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15817 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15822 auto P = GetMinMaxConst(0);
15823 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15826 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15829 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15832 Guards.RewriteMap.insert({
LHS,
RHS});
15840 const APInt &DivisorVal,
15842 const APInt *ExprVal;
15855 const APInt &DivisorVal,
15857 const APInt *ExprVal;
15865 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15879 const SCEV *URemRHS =
nullptr;
15883 const SCEV *Multiple =
15885 DivInfo[URemLHS] = Multiple;
15887 Multiples[URemLHS] =
C->getAPInt();
15907 auto IsMinMaxSCEVWithNonNegativeConstant =
15911 if (
MinMax->getNumOperands() != 2)
15914 if (
C->getAPInt().isNegative())
15916 SCTy =
MinMax->getSCEVType();
15925 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15927 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15932 auto *DivisibleExpr =
15940void ScalarEvolution::LoopGuards::collectFromBlock(
15942 const BasicBlock *
Block,
const BasicBlock *Pred,
15950 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15961 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15963 if (From == FromRewritten)
15965 RewriteMap[From] = To;
15971 auto GetMaybeRewritten = [&](
const SCEV *S) {
15972 return RewriteMap.lookup_or(S, S);
15979 const SCEV *MatchLHS,
15980 const SCEV *MatchRHS) {
15981 const SCEVConstant *C1;
15984 if (!
match(MatchLHS,
15996 const SCEV *RewrittenLHS = GetMaybeRewritten(LHSUnknown);
15997 ExactRegion = ExactRegion.intersectWith(SE.
getUnsignedRange(RewrittenLHS),
16002 if (ExactRegion.isEmptySet() || ExactRegion.isWrappedSet() ||
16003 ExactRegion.isFullSet())
16006 const SCEV *RegionMin = SE.
getConstant(ExactRegion.getUnsignedMin());
16007 const SCEV *RegionMax = SE.
getConstant(ExactRegion.getUnsignedMax());
16008 const SCEV *ClampedLHS =
16010 AddRewrite(LHSUnknown, RewrittenLHS, ClampedLHS);
16013 if (MatchRangeCheckIdiom(Predicate,
LHS,
RHS))
16026 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
16028 const APInt &DividesBy =
16043 switch (Predicate) {
16072 SmallPtrSet<const SCEV *, 16> Visited;
16074 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
16078 while (!Worklist.
empty()) {
16082 if (!Visited.
insert(From).second)
16084 const SCEV *FromRewritten = GetMaybeRewritten(From);
16085 const SCEV *To =
nullptr;
16087 switch (Predicate) {
16092 EnqueueOperands(
UMax);
16098 EnqueueOperands(
SMax);
16104 EnqueueOperands(
UMin);
16110 EnqueueOperands(
SMin);
16118 const SCEV *OneAlignedUp =
16120 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16132 const SCEVConstant *
C;
16141 Guards.NotEqual.insert({
LHS,
RHS});
16150 AddRewrite(From, FromRewritten, To);
16167 SE.F.
getParent(), Intrinsic::experimental_guard);
16169 for (
const auto *GU : GuardDecl->users())
16171 if (Guard->getFunction() ==
Block->getParent() &&
16180 unsigned NumCollectedConditions = 0;
16182 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16184 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16186 const CondBrInst *LoopEntryPredicate =
16188 if (!LoopEntryPredicate)
16193 NumCollectedConditions++;
16197 if (
Depth > 0 && NumCollectedConditions == 2)
16205 if (Pair.second->hasNPredecessorsOrMore(2) &&
16207 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16208 for (
auto &Phi : Pair.second->phis())
16219 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16220 SmallVector<Value *, 8> Worklist;
16221 SmallPtrSet<Value *, 8> Visited;
16223 while (!Worklist.
empty()) {
16230 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16254 DenseMap<const SCEV *, APInt> Multiples;
16256 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16263 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16264 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16268 for (
const auto &[K, Divisor] : Multiples) {
16269 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16270 Guards.RewriteMap[
K] =
16272 Guards.
rewrite(K), Divisor, SE),
16281 Guards.PreserveNUW =
true;
16282 Guards.PreserveNSW =
true;
16283 for (
const SCEV *Expr : ExprsToRewrite) {
16284 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16285 Guards.PreserveNUW &=
16287 Guards.PreserveNSW &=
16294 if (ExprsToRewrite.size() > 1) {
16295 for (
const SCEV *Expr : ExprsToRewrite) {
16296 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16297 Guards.RewriteMap.erase(Expr);
16298 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16307 class SCEVLoopGuardRewriter
16318 NotEqual(Guards.NotEqual) {
16319 if (Guards.PreserveNUW)
16321 if (Guards.PreserveNSW)
16328 return Map.lookup_or(Expr, Expr);
16332 if (
const SCEV *S = Map.lookup(Expr))
16339 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16340 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16341 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16343 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16344 if (
const SCEV *S = Map.lookup(NarrowExt))
16345 return SE.getZeroExtendExpr(S, Ty);
16346 Bitwidth = Bitwidth / 2;
16354 if (
const SCEV *S = Map.lookup(Expr))
16361 if (
const SCEV *S = Map.lookup(Expr))
16367 if (
const SCEV *S = Map.lookup(Expr))
16373 if (
const SCEV *S = Map.lookup(Expr))
16378 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16383 if (NotEqual.contains({LHS, RHS})) {
16385 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16386 return SE.getUMaxExpr(OneAlignedUp, S);
16393 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16404 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16405 return SE.getAddExpr(
16408 if (
const SCEV *S = Map.lookup(
Add))
16409 return SE.getAddExpr(Expr->
getOperand(0), S);
16417 const SCEV *S =
nullptr;
16424 S = Map.lookup(SE.getAddExpr(NewC, Expr->
getOperand(1)));
16427 return SE.getAddExpr(S, SE.getMinusOne(Expr->
getType()));
16462 if (RewriteMap.empty() && NotEqual.empty())
16465 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16466 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 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