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!");
3493 if (RHSC->getValue()->isOne())
3498 if (!RHSC->getValue()->isZero()) {
3502 Type *Ty = LHS->getType();
3503 unsigned LZ = RHSC->getAPInt().countl_zero();
3507 if (!RHSC->getAPInt().isPowerOf2())
3515 const APInt &StepInt = Step->getAPInt();
3516 const APInt &DivInt = RHSC->getAPInt();
3517 if (!StepInt.
urem(DivInt) &&
3523 for (
const SCEV *
Op : AR->operands())
3529 const APInt *StartRem;
3542 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3546 const SCEV *NewStart =
3548 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3550 const SCEV *NewLHS =
3560 if (M->hasNoUnsignedWrap()) {
3562 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3563 const SCEV *
Op = M->getOperand(i);
3590 if (
auto *DivisorConstant =
3592 bool Overflow =
false;
3594 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3605 if (
A->hasNoUnsignedWrap()) {
3607 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3614 if (
Operands.size() ==
A->getNumOperands())
3626 const APInt &
N = RHSC->getAPInt();
3627 const APInt *NMinusM, *M;
3631 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3632 *NMinusM ==
N - *M) {
3641 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3651 return getZero(LHS->getType());
3655 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3656 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3657 if (
Mul->getOperand(i) == RHS) {
3668 const SCEV *NewLHS, *NewRHS;
3673 return getOrCreateUDivExpr(LHS, RHS);
3693 if (StepChrec->getLoop() == L) {
3712 "SCEVAddRecExpr operand types don't match!");
3713 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3717 "SCEVAddRecExpr operand is not available at loop entry!");
3735 const Loop *NestedLoop = NestedAR->getLoop();
3736 if (L->contains(NestedLoop)
3739 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3741 Operands[0] = NestedAR->getStart();
3745 bool AllInvariant =
all_of(
3757 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3768 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3778 return getOrCreateAddRecExpr(
Operands, L, Flags);
3794 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3798 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3812 bool FirstIter =
true;
3814 for (
SCEVUse IndexExpr : IndexExprs) {
3821 Offsets.push_back(FieldOffset);
3824 CurTy = STy->getTypeAtIndex(Index);
3829 "The first index of a GEP indexes a pointer");
3830 CurTy = SrcElementTy;
3841 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3842 Offsets.push_back(LocalOffset);
3847 if (Offsets.empty())
3860 "GEP should not change type mid-flight.");
3864SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3869 ID.AddPointer(
Op.getOpaqueValue());
3871 return UniqueSCEVs.lookup(ID, Token);
3881 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3882 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3883 if (
Ops.size() == 1)
return Ops[0];
3886 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3888 "Operand types don't match!");
3891 "min/max should be consistently pointerish");
3917 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3919 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3924 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3926 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3932 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3938 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3943 if (Idx <
Ops.size()) {
3944 bool DeletedAny =
false;
3945 while (
Ops[Idx]->getSCEVType() == Kind) {
3947 Ops.erase(
Ops.begin()+Idx);
3965 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3966 if (
Ops[i] ==
Ops[i + 1] ||
3967 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3970 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3973 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3976 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3982 if (
Ops.size() == 1)
return Ops[0];
3984 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
3991 ID.AddPointer(
Op.getOpaqueValue());
3993 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
3995 return ExistingSCEV;
3998 SCEV *S =
new (SCEVAllocator)
4001 UniqueSCEVs.insert(S, Token);
4009class SCEVSequentialMinMaxDeduplicatingVisitor final
4010 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4011 std::optional<const SCEV *>> {
4012 using RetVal = std::optional<const SCEV *>;
4019 bool canRecurseInto(
SCEVTypes Kind)
const {
4022 return RootKind == Kind || NonSequentialRootKind == Kind;
4027 if (!SeenOps.
insert(S).second)
4028 return std::nullopt;
4032 if (!canRecurseInto(Kind))
4042 return std::nullopt;
4052 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4054 : SE(SE), RootKind(RootKind),
4055 NonSequentialRootKind(
4056 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4060 SmallVectorImpl<SCEVUse> &NewOps) {
4065 for (
const SCEV *
Op : OrigOps) {
4070 Ops.emplace_back(*NewOp);
4074 NewOps = std::move(
Ops);
4118struct SCEVPoisonCollector {
4119 bool LookThroughMaybePoisonBlocking;
4120 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4121 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4122 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4124 bool follow(
const SCEV *S) {
4125 if (!LookThroughMaybePoisonBlocking &&
4135 bool isDone()
const {
return false; }
4145 SCEVPoisonCollector PC1(
true);
4150 if (PC1.MaybePoison.
empty())
4156 SCEVPoisonCollector PC2(
false);
4166 SCEVPoisonCollector PC(
false);
4189 while (!Worklist.
empty()) {
4191 if (!Visited.
insert(V).second)
4195 if (Visited.
size() > 16)
4211 if (PDI->isDisjoint())
4218 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4225 if (
I->hasPoisonGeneratingAnnotations())
4236 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4237 "Not a SCEVSequentialMinMaxExpr!");
4238 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4239 if (
Ops.size() == 1)
4243 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4245 "Operand types don't match!");
4248 "min/max should be consistently pointerish");
4256 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4263 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4273 bool DeletedAny =
false;
4274 while (Idx <
Ops.size()) {
4275 if (
Ops[Idx]->getSCEVType() != Kind) {
4280 Ops.erase(
Ops.begin() + Idx);
4281 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4282 SMME->operands().end());
4290 const SCEV *SaturationPoint;
4301 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4302 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4314 Ops.erase(
Ops.begin() + i);
4319 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4320 Ops.erase(
Ops.begin() + i);
4330 ID.AddPointer(
Op.getOpaqueValue());
4332 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
4334 return ExistingSCEV;
4338 SCEV *S =
new (SCEVAllocator)
4341 UniqueSCEVs.insert(S, Token);
4389 if (
Size.isScalable())
4410 "Cannot get offset for structure containing scalable vector types");
4424 if (
SCEV *S = UniqueSCEVs.lookup(ID, Token)) {
4426 "Stale SCEVUnknown in uniquing map!");
4429 SCEV *S =
new (SCEVAllocator)
SCEVUnknown(ID.Intern(SCEVAllocator), V,
this,
4432 UniqueSCEVs.insert(S, Token);
4447 return Ty->isIntOrPtrTy();
4454 if (Ty->isPointerTy())
4465 if (Ty->isIntegerTy())
4469 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4481 bool PreciseA, PreciseB;
4482 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4483 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4484 if (!PreciseA || !PreciseB)
4487 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4488 DT.dominates(ScopeB, ScopeA);
4492 return CouldNotCompute.get();
4495bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4498 return SU && SU->getValue() ==
nullptr;
4501 return !ContainsNulls;
4506 if (
I != HasRecMap.end())
4511 HasRecMap.insert({S, FoundAddRec});
4519 if (
SI == ExprValueMap.
end())
4521 return SI->second.getArrayRef();
4527void ScalarEvolution::eraseValueFromMap(
Value *V) {
4529 if (
I != ValueExprMap.end()) {
4530 auto EVIt = ExprValueMap.find(
I->second);
4531 bool Removed = EVIt->second.remove(V);
4533 assert(Removed &&
"Value not in ExprValueMap?");
4534 ValueExprMap.erase(
I);
4538void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4542 auto It = ValueExprMap.find_as(V);
4543 if (It == ValueExprMap.end()) {
4545 ExprValueMap[S].insert(V);
4556 return createSCEVIter(V);
4563 if (
I != ValueExprMap.end()) {
4564 const SCEV *S =
I->second;
4565 assert(checkValidity(S) &&
4566 "existing SCEV has not been properly invalidated");
4579 Type *Ty = V->getType();
4595 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4608 return (
const SCEV *)
nullptr;
4614 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4618 Type *Ty = V->getType();
4624 assert(
P->getType()->isPointerTy());
4639 if (AddOp->getType()->isPointerTy()) {
4640 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4658 return getZero(LHS->getType());
4663 if (RHS->getType()->isPointerTy()) {
4664 if (!LHS->getType()->isPointerTy() ||
4674 const bool RHSIsNotMinSigned =
4705 Type *SrcTy = V->getType();
4706 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4707 "Cannot truncate or zero extend with non-integer arguments!");
4717 Type *SrcTy = V->getType();
4718 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4719 "Cannot truncate or zero extend with non-integer arguments!");
4728 Type *SrcTy = V->getType();
4729 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4730 "Cannot noop or zero extend with non-integer arguments!");
4732 "getNoopOrZeroExtend cannot truncate!");
4739 Type *SrcTy = V->getType();
4740 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4741 "Cannot noop or sign extend with non-integer arguments!");
4743 "getNoopOrSignExtend cannot truncate!");
4750 Type *SrcTy = V->getType();
4751 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4752 "Cannot noop or any extend with non-integer arguments!");
4754 "getNoopOrAnyExtend cannot truncate!");
4761 Type *SrcTy = V->getType();
4762 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4763 "Cannot truncate or noop with non-integer arguments!");
4765 "getTruncateOrNoop cannot extend!");
4773 const SCEV *PromotedLHS = LHS;
4774 const SCEV *PromotedRHS = RHS;
4794 assert(!
Ops.empty() &&
"At least one operand must be!");
4796 if (
Ops.size() == 1)
4800 Type *MaxType =
nullptr;
4806 assert(MaxType &&
"Failed to find maximum type!");
4819 if (!V->getType()->isPointerTy())
4824 V = AddRec->getStart();
4826 const SCEV *PtrOp =
nullptr;
4827 for (
const SCEV *AddOp :
Add->operands()) {
4828 if (AddOp->getType()->isPointerTy()) {
4829 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4833 assert(PtrOp &&
"Must have pointer op");
4845 for (
User *U :
I->users()) {
4847 if (Visited.
insert(UserInsn).second)
4861 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4862 bool IgnoreOtherLoops =
true) {
4865 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4867 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4872 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4874 SeenLoopVariantSCEVUnknown =
true;
4878 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4882 SeenOtherLoops =
true;
4886 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4888 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4891 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4892 : SCEVRewriteVisitor(SE),
L(
L) {}
4895 bool SeenLoopVariantSCEVUnknown =
false;
4896 bool SeenOtherLoops =
false;
4905 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4906 SCEVPostIncRewriter
Rewriter(L, SE);
4908 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4913 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4915 SeenLoopVariantSCEVUnknown =
true;
4919 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4923 SeenOtherLoops =
true;
4927 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4929 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4932 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4933 : SCEVRewriteVisitor(SE),
L(
L) {}
4936 bool SeenLoopVariantSCEVUnknown =
false;
4937 bool SeenOtherLoops =
false;
4943class SCEVBackedgeConditionFolder
4946 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4947 ScalarEvolution &SE) {
4948 bool IsPosBECond =
false;
4949 Value *BECond =
nullptr;
4950 if (BasicBlock *Latch =
L->getLoopLatch()) {
4952 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
4953 "Both outgoing branches should not target same header!");
4954 BECond = BI->getCondition();
4955 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
4960 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
4964 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4965 const SCEV *
Result = Expr;
4970 switch (
I->getOpcode()) {
4971 case Instruction::Select: {
4973 std::optional<const SCEV *> Res =
4974 compareWithBackedgeCondition(
SI->getCondition());
4982 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
4993 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
4994 bool IsPosBECond, ScalarEvolution &SE)
4995 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
4996 IsPositiveBECond(IsPosBECond) {}
4998 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5002 Value *BackedgeCond =
nullptr;
5004 bool IsPositiveBECond;
5007std::optional<const SCEV *>
5008SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5013 if (BackedgeCond == IC)
5016 return std::nullopt;
5021 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5022 ScalarEvolution &SE) {
5028 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5035 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5045 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5046 : SCEVRewriteVisitor(SE),
L(
L) {}
5054void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5070 const APInt &BECountAP = BECountMax->getAPInt();
5071 unsigned NoOverflowBitWidth =
5080ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5090 if (!SignedWrapViaInductionTried.insert(AR).second)
5115 AC.assumptions().empty())
5123 const SCEV *OverflowLimit =
5125 if (OverflowLimit &&
5133ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5143 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5168 AC.assumptions().empty())
5177 const SCEV *OverflowLimit =
5206 IsNSW = OBO->hasNoSignedWrap();
5207 IsNUW = OBO->hasNoUnsignedWrap();
5213 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5225 return std::nullopt;
5231 switch (
Op->getOpcode()) {
5232 case Instruction::Add:
5233 case Instruction::Sub:
5234 case Instruction::Mul:
5235 case Instruction::UDiv:
5236 case Instruction::URem:
5237 case Instruction::And:
5238 case Instruction::AShr:
5239 case Instruction::Shl:
5242 case Instruction::Or: {
5245 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5255 case Instruction::Xor:
5259 if (RHSC->getValue().isSignMask())
5260 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5262 if (V->getType()->isIntegerTy(1))
5263 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5266 case Instruction::LShr:
5275 if (SA->getValue().ult(
BitWidth)) {
5277 ConstantInt::get(SA->getContext(),
5279 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5284 case Instruction::ExtractValue: {
5286 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5294 bool Signed = WO->isSigned();
5297 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5302 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5313 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5314 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5316 return std::nullopt;
5342 if (
Op == SymbolicPHI)
5347 if (SourceBits != NewBits)
5365 if (!L || L->getHeader() != PN->
getParent())
5423std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5424ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5432 assert(L &&
"Expecting an integer loop header phi");
5437 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5438 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5439 Value *
V = PN->getIncomingValue(i);
5440 if (
L->contains(PN->getIncomingBlock(i))) {
5443 }
else if (BEValueV != V) {
5447 }
else if (!StartValueV) {
5449 }
else if (StartValueV != V) {
5450 StartValueV =
nullptr;
5454 if (!BEValueV || !StartValueV)
5455 return std::nullopt;
5457 const SCEV *BEValue =
getSCEV(BEValueV);
5464 return std::nullopt;
5468 unsigned FoundIndex =
Add->getNumOperands();
5469 Type *TruncTy =
nullptr;
5471 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5474 if (FoundIndex == e) {
5479 if (FoundIndex ==
Add->getNumOperands())
5480 return std::nullopt;
5484 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5485 if (i != FoundIndex)
5486 Ops.push_back(
Add->getOperand(i));
5492 return std::nullopt;
5545 const SCEV *StartVal =
getSCEV(StartValueV);
5546 const SCEV *PHISCEV =
5573 auto getExtendedExpr = [&](
const SCEV *Expr,
5574 bool CreateSignExtend) ->
const SCEV * {
5577 const SCEV *ExtendedExpr =
5580 return ExtendedExpr;
5588 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5589 const SCEV *ExtendedExpr) ->
bool {
5590 return Expr != ExtendedExpr &&
5594 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5595 if (PredIsKnownFalse(StartVal, StartExtended)) {
5597 return std::nullopt;
5602 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5603 if (PredIsKnownFalse(Accum, AccumExtended)) {
5605 return std::nullopt;
5608 auto AppendPredicate = [&](
const SCEV *Expr,
5609 const SCEV *ExtendedExpr) ->
void {
5610 if (Expr != ExtendedExpr &&
5618 AppendPredicate(StartVal, StartExtended);
5619 AppendPredicate(Accum, AccumExtended);
5627 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5628 std::make_pair(NewAR, Predicates);
5630 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5634std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5639 return std::nullopt;
5642 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5643 if (
I != PredicatedSCEVRewrites.end()) {
5644 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5647 if (Rewrite.first == SymbolicPHI)
5648 return std::nullopt;
5652 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5656 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5657 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5662 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5663 return std::nullopt;
5683 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5684 if (Expr1 != Expr2 &&
5685 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5686 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5703const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5705 Value *StartValueV) {
5708 assert(BEValueV && StartValueV);
5714 if (BO->Opcode != Instruction::Add)
5717 const SCEV *Accum =
nullptr;
5718 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5720 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5734 insertValueToMap(PN, PHISCEV);
5737 inferNoWrapViaConstantRanges(AR);
5744 "Accum is defined outside L, but is not invariant?");
5745 if (isAddRecNeverPoison(BEInst, L))
5752const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5760 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5766 }
else if (BEValueV != V) {
5770 }
else if (!StartValueV) {
5772 }
else if (StartValueV != V) {
5773 StartValueV =
nullptr;
5777 if (!BEValueV || !StartValueV)
5780 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5781 "PHI node already processed?");
5785 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5790 insertValueToMap(PN, SymbolicName);
5794 const SCEV *BEValue =
getSCEV(BEValueV);
5804 unsigned FoundIndex =
Add->getNumOperands();
5805 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5806 if (
Add->getOperand(i) == SymbolicName)
5807 if (FoundIndex == e) {
5812 if (FoundIndex !=
Add->getNumOperands()) {
5815 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5816 if (i != FoundIndex)
5817 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5829 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5836 if (
GEP->getOperand(0) == PN) {
5837 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
5855 const SCEV *StartVal =
getSCEV(StartValueV);
5856 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5861 forgetMemoizedResults({SymbolicName});
5862 insertValueToMap(PN, PHISCEV);
5865 inferNoWrapViaConstantRanges(AR);
5889 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5890 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5892 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5893 const SCEV *StartVal =
getSCEV(StartValueV);
5894 if (Start == StartVal) {
5898 forgetMemoizedResults({SymbolicName});
5899 insertValueToMap(PN, Shifted);
5909 eraseValueFromMap(PN);
5924 Use &LeftUse =
Merge->getOperandUse(0);
5925 Use &RightUse =
Merge->getOperandUse(1);
5961 assert(IDom &&
"At least the entry block should dominate PN");
5969const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
5974 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
5991 CommonInst = IncomingInst;
6007ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6013 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6014 bool SCEVExprsIdentical =
6016 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6017 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6020const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6021 if (
const SCEV *S = createAddRecFromPHI(PN))
6031 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6034 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6043 struct FindClosure {
6044 const SCEV *OperandToFind;
6050 bool canRecurseInto(
SCEVTypes Kind)
const {
6053 return RootKind == Kind || NonSequentialRootKind == Kind ||
6058 : OperandToFind(OperandToFind), RootKind(RootKind),
6059 NonSequentialRootKind(
6063 bool follow(
const SCEV *S) {
6064 Found = S == OperandToFind;
6066 return !isDone() && canRecurseInto(S->
getSCEVType());
6069 bool isDone()
const {
return Found; }
6072 FindClosure FC(OperandToFind, RootKind);
6077std::optional<const SCEV *>
6078ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6088 switch (ICI->getPredicate()) {
6102 bool Signed = ICI->isSigned();
6103 const SCEV *LA =
getSCEV(TrueVal);
6111 if (LA == LS &&
RA == RS)
6113 if (LA == RS &&
RA == LS)
6116 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6117 if (
Op->getType()->isPointerTy()) {
6128 LS = CoerceOperand(LS);
6129 RS = CoerceOperand(RS);
6153 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6154 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6168 X = ZExt->getOperand();
6170 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6181 return std::nullopt;
6184static std::optional<const SCEV *>
6186 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6190 "Unexpected operands of a select.");
6202 return std::nullopt;
6217static std::optional<const SCEV *>
6221 return std::nullopt;
6224 const auto *SETrue = SE->
getSCEV(TrueVal);
6225 const auto *SEFalse = SE->
getSCEV(FalseVal);
6229const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6231 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6233 V->getType() ==
TrueVal->getType() &&
6234 "Types of select hands and of the result must match.");
6237 if (!
V->getType()->isIntegerTy(1))
6240 if (std::optional<const SCEV *> S =
6253 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6257 if (std::optional<const SCEV *> S =
6258 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6264 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6270 assert(
GEP->getSourceElementType()->isSized() &&
6271 "GEP source element type must be sized");
6274 for (
Value *Index :
GEP->indices())
6279APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6282 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6285 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6287 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6290 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6308 return GetShiftedByZeros(TZ);
6318 return GetShiftedByZeros(TZ);
6322 if (
M->hasNoUnsignedWrap()) {
6325 for (
const SCEV *Operand :
M->operands().drop_front())
6333 for (
const SCEV *Operand :
M->operands())
6335 return GetShiftedByZeros(TZ);
6340 if (
N->hasNoUnsignedWrap())
6341 return GetGCDMultiple(
N);
6344 for (
const SCEV *Operand :
N->operands().drop_front())
6346 return GetShiftedByZeros(TZ);
6363 CtxI = &*F.getEntryBlock().begin();
6370 .allowEphemerals(
true))
6371 .countMinTrailingZeros();
6372 return GetShiftedByZeros(
Known);
6385 return getConstantMultipleImpl(S, CtxI);
6387 auto I = ConstantMultipleCache.find(S);
6388 if (
I != ConstantMultipleCache.end())
6391 APInt Result = getConstantMultipleImpl(S, CtxI);
6392 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6393 assert(InsertPair.second &&
"Should insert a new key");
6394 return InsertPair.first->second;
6411 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6414 if (std::optional<ConstantRange>
Range = CB->getRange())
6418 if (std::optional<ConstantRange>
Range =
A->getRange())
6421 return std::nullopt;
6428 UnsignedRanges.erase(AddRec);
6429 SignedRanges.erase(AddRec);
6430 ConstantMultipleCache.erase(AddRec);
6435getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6461 Value *Start, *Step;
6468 assert(L && L->getHeader() ==
P->getParent());
6481 case Instruction::AShr:
6482 case Instruction::LShr:
6483 case Instruction::Shl:
6498 KnownStep.getBitWidth() ==
BitWidth);
6501 auto MaxShiftAmt = KnownStep.getMaxValue();
6503 bool Overflow =
false;
6504 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6511 case Instruction::AShr: {
6519 if (KnownStart.isNonNegative())
6522 KnownStart.getMaxValue() + 1);
6523 if (KnownStart.isNegative())
6526 KnownEnd.getMaxValue() + 1);
6529 case Instruction::LShr: {
6538 KnownStart.getMaxValue() + 1);
6540 case Instruction::Shl: {
6544 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6545 return ConstantRange(KnownStart.getMinValue(),
6546 KnownEnd.getMaxValue() + 1);
6571 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6578ScalarEvolution::getRangeRefIter(
const SCEV *S,
6579 ScalarEvolution::RangeSignHint SignHint) {
6580 DenseMap<const SCEV *, ConstantRange> &Cache =
6581 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6584 SmallPtrSet<const SCEV *, 8> Seen;
6588 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6589 if (!Seen.
insert(Expr).second)
6622 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6623 const SCEV *
P = WorkList[
I];
6627 for (
const SCEV *
Op :
P->operands())
6640 if (!WorkList.
empty()) {
6645 getRangeRef(
P, SignHint);
6649 return getRangeRef(S, SignHint, 0);
6652const APInt *ScalarEvolution::getConstantAPIntOrNull(
const SCEV *S) {
6654 return &
C->getAPInt();
6662 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6663 DenseMap<const SCEV *, ConstantRange> &Cache =
6664 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6671 auto I = Cache.
find(S);
6672 if (
I != Cache.
end())
6676 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6681 return getRangeRefIter(S, SignHint);
6684 ConstantRange ConservativeResult(
BitWidth,
true);
6685 using OBO = OverflowingBinaryOperator;
6689 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6693 ConservativeResult =
6700 ConservativeResult = ConstantRange(
6716 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6723 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6730 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6735 return setRange(Cast, SignHint,
X);
6740 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6741 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6743 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6744 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6745 ConservativeResult =
6746 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6748 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6749 unsigned WrapType = OBO::AnyWrap;
6750 if (
Add->hasNoSignedWrap())
6751 WrapType |= OBO::NoSignedWrap;
6752 if (
Add->hasNoUnsignedWrap())
6753 WrapType |= OBO::NoUnsignedWrap;
6755 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6757 return setRange(
Add, SignHint,
6758 ConservativeResult.intersectWith(
X, RangeType));
6762 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6764 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6765 return setRange(
Mul, SignHint,
6766 ConservativeResult.intersectWith(
X, RangeType));
6770 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6771 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6772 return setRange(UDiv, SignHint,
6773 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6781 if (!UnsignedMinValue.
isZero())
6782 ConservativeResult = ConservativeResult.intersectWith(
6783 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6792 bool AllNonNeg =
true;
6793 bool AllNonPos =
true;
6794 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6801 ConservativeResult = ConservativeResult.intersectWith(
6806 ConservativeResult = ConservativeResult.intersectWith(
6815 const SCEV *MaxBEScev =
6829 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6831 ConservativeResult =
6832 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6835 auto RangeFromFactoring = getRangeViaFactoring(
6837 ConservativeResult =
6838 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6844 const SCEV *SymbolicMaxBECount =
6849 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6850 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6851 ConservativeResult =
6852 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6857 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6867 ID = Intrinsic::umax;
6870 ID = Intrinsic::smax;
6874 ID = Intrinsic::umin;
6877 ID = Intrinsic::smin;
6884 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6885 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6887 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6888 return setRange(S, SignHint,
6889 ConservativeResult.intersectWith(
X, RangeType));
6898 ConservativeResult =
6899 ConservativeResult.intersectWith(*MDRange, RangeType);
6904 auto CR = getRangeForUnknownRecurrence(U);
6905 ConservativeResult = ConservativeResult.intersectWith(CR);
6916 if (
U->getType()->isPointerTy()) {
6919 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
6920 int ptrIdxDiff = ptrSize -
BitWidth;
6921 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
6927 if (!
Known.Zero.getHiBits(NS).isZero())
6928 Known.Zero.setHighBits(NS);
6929 if (!
Known.One.getHiBits(NS).isZero())
6930 Known.One.setHighBits(NS);
6933 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
6934 ConservativeResult = ConservativeResult.intersectWith(
6935 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
6938 ConservativeResult = ConservativeResult.intersectWith(
6943 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6947 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
6948 DL, CanBeNull,
nullptr);
6964 ConservativeResult = ConservativeResult.intersectWith(
6974 return getRangeRef(AR, SignHint,
Depth + 1);
6978 ConstantRange RangeFromOps(
BitWidth,
false);
6980 for (
const auto &
Op :
Phi->operands()) {
6982 RangeFromOps = RangeFromOps.unionWith(OpRange);
6984 if (RangeFromOps.isFullSet())
6987 ConservativeResult =
6988 ConservativeResult.intersectWith(RangeFromOps, RangeType);
6994 if (
II->getIntrinsicID() == Intrinsic::vscale) {
6996 ConservativeResult = ConservativeResult.difference(Disallowed);
6999 return setRange(U, SignHint, std::move(ConservativeResult));
7005 return setRange(S, SignHint, std::move(ConservativeResult));
7013static std::pair<ConstantRange, bool>
7021 if (Step == 0 || MaxBECount == 0)
7022 return {StartRange,
true};
7028 return {ConstantRange::getFull(
BitWidth),
false};
7044 return {ConstantRange::getFull(
BitWidth),
false};
7057 APInt MovedBoundary;
7062 MovedBoundary = StartLower - std::move(
Offset);
7065 MovedBoundary = StartUpper + std::move(
Offset);
7069 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7076 if (StartRange.
contains(MovedBoundary))
7077 return {ConstantRange::getFull(
BitWidth),
false};
7080 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7082 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7090std::pair<ConstantRange, SCEV::NoWrapFlags>
7091ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7092 const APInt &MaxBECount) {
7096 "mismatched bit widths");
7105 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7107 StartSRange, MaxBECount,
7109 ConstantRange SR = SR1.unionWith(SR2);
7126ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7128 ScalarEvolution::RangeSignHint SignHint) {
7129 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7131 "This only works for non-self-wrapping AddRecs!");
7132 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7136 return ConstantRange::getFull(
BitWidth);
7144 return ConstantRange::getFull(
BitWidth);
7148 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7150 MaxItersWithoutWrap))
7151 return ConstantRange::getFull(
BitWidth);
7172 ConstantRange StartRange = getRangeRef(Start, SignHint);
7173 ConstantRange EndRange = getRangeRef(End, SignHint);
7174 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7178 return RangeBetween;
7183 return ConstantRange::getFull(
BitWidth);
7186 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7187 return RangeBetween;
7189 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7190 return RangeBetween;
7191 return ConstantRange::getFull(
BitWidth);
7196 const APInt &MaxBECount) {
7203 "mismatched bit widths");
7205 struct SelectPattern {
7206 Value *Condition =
nullptr;
7210 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7212 std::optional<unsigned> CastOp;
7226 CastOp = SCast->getSCEVType();
7227 S = SCast->getOperand();
7230 using namespace llvm::PatternMatch;
7237 Condition =
nullptr;
7269 bool isRecognized() {
return Condition !=
nullptr; }
7272 SelectPattern StartPattern(*
this,
BitWidth, Start);
7273 if (!StartPattern.isRecognized())
7274 return ConstantRange::getFull(
BitWidth);
7276 SelectPattern StepPattern(*
this,
BitWidth, Step);
7277 if (!StepPattern.isRecognized())
7278 return ConstantRange::getFull(
BitWidth);
7280 if (StartPattern.Condition != StepPattern.Condition) {
7284 return ConstantRange::getFull(
BitWidth);
7295 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7296 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7297 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7298 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7300 ConstantRange TrueRange =
7301 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7302 ConstantRange FalseRange =
7303 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7315 PDI && PDI->isDisjoint()) {
7330ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7343 SmallPtrSet<const SCEV *, 16> Visited;
7345 auto pushOp = [&](
const SCEV *S) {
7346 if (!Visited.
insert(S).second)
7349 if (Visited.
size() > 30) {
7360 while (!Worklist.
empty()) {
7362 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7363 if (!Bound || DT.dominates(Bound, DefI))
7370 return Bound ? Bound : &*F.getEntryBlock().begin();
7376 return getDefiningScopeBound(
Ops, Discard);
7379bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7381 if (
A->getParent() ==
B->getParent() &&
7386 auto *BLoop = LI.getLoopFor(
B->getParent());
7387 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7388 BLoop->getLoopPreheader() ==
A->getParent() &&
7390 A->getParent()->end()) &&
7398 SCEVPoisonCollector PC(
true);
7400 return PC.MaybePoison.
empty();
7403bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7413bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7430 for (
const Use &
Op :
I->operands()) {
7436 auto *DefI = getDefiningScopeBound(SCEVOps);
7437 return isGuaranteedToTransferExecutionTo(DefI,
I);
7440bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7442 if (isSCEVExprNeverPoison(
I))
7453 auto *ExitingBB =
L->getExitingBlock();
7457 SmallPtrSet<const Value *, 16> KnownPoison;
7466 while (!Worklist.
empty()) {
7469 for (
const Use &U :
Poison->uses()) {
7472 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7476 if (KnownPoison.
insert(PoisonUser).second)
7484ScalarEvolution::LoopProperties
7485ScalarEvolution::getLoopProperties(
const Loop *L) {
7486 using LoopProperties = ScalarEvolution::LoopProperties;
7488 auto Itr = LoopPropertiesCache.find(L);
7489 if (Itr == LoopPropertiesCache.end()) {
7492 return !
SI->isSimple();
7502 return I->mayWriteToMemory();
7505 LoopProperties LP = {
true,
7508 for (
auto *BB :
L->getBlocks())
7509 for (
auto &
I : *BB) {
7511 LP.HasNoAbnormalExits =
false;
7512 if (HasSideEffects(&
I))
7513 LP.HasNoSideEffects =
false;
7514 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7518 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7519 assert(InsertPair.second &&
"We just checked!");
7520 Itr = InsertPair.first;
7533const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7539 Stack.emplace_back(V,
false);
7540 while (!Stack.empty()) {
7541 auto E = Stack.back();
7542 Value *CurV = E.getPointer();
7550 const SCEV *CreatedSCEV =
nullptr;
7553 CreatedSCEV = createSCEV(CurV);
7558 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7562 insertValueToMap(CurV, CreatedSCEV);
7565 Stack.back().setInt(
true);
7568 Stack.emplace_back(
Op,
false);
7585 if (!DT.isReachableFromEntry(
I->getParent()))
7598 switch (BO->Opcode) {
7599 case Instruction::Add:
7600 case Instruction::Mul: {
7607 Ops.push_back(BO->
Op);
7611 Ops.push_back(BO->RHS);
7615 (BO->Opcode == Instruction::Add &&
7616 (NewBO->Opcode != Instruction::Add &&
7617 NewBO->Opcode != Instruction::Sub)) ||
7618 (BO->Opcode == Instruction::Mul &&
7619 NewBO->Opcode != Instruction::Mul)) {
7620 Ops.push_back(BO->LHS);
7625 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7628 Ops.push_back(BO->LHS);
7636 case Instruction::Sub:
7637 case Instruction::UDiv:
7638 case Instruction::URem:
7640 case Instruction::AShr:
7641 case Instruction::Shl:
7642 case Instruction::Xor:
7646 case Instruction::And:
7647 case Instruction::Or:
7651 case Instruction::LShr:
7658 Ops.push_back(BO->LHS);
7659 Ops.push_back(BO->RHS);
7663 switch (
U->getOpcode()) {
7664 case Instruction::Trunc:
7665 case Instruction::ZExt:
7666 case Instruction::SExt:
7667 case Instruction::PtrToAddr:
7668 case Instruction::PtrToInt:
7669 Ops.push_back(
U->getOperand(0));
7672 case Instruction::BitCast:
7674 Ops.push_back(
U->getOperand(0));
7679 case Instruction::SDiv:
7680 case Instruction::SRem:
7681 Ops.push_back(
U->getOperand(0));
7682 Ops.push_back(
U->getOperand(1));
7685 case Instruction::GetElementPtr:
7687 "GEP source element type must be sized");
7691 case Instruction::IntToPtr:
7694 case Instruction::PHI:
7725 Ops.push_back(CondICmp->getOperand(0));
7726 Ops.push_back(CondICmp->getOperand(1));
7746 case Instruction::Select: {
7748 auto CanSimplifyToUnknown = [
this,
U]() {
7766 if (CanSimplifyToUnknown())
7773 case Instruction::Call:
7774 case Instruction::Invoke:
7781 switch (
II->getIntrinsicID()) {
7782 case Intrinsic::abs:
7783 Ops.push_back(
II->getArgOperand(0));
7785 case Intrinsic::umax:
7786 case Intrinsic::umin:
7787 case Intrinsic::smax:
7788 case Intrinsic::smin:
7789 case Intrinsic::usub_sat:
7790 case Intrinsic::uadd_sat:
7791 Ops.push_back(
II->getArgOperand(0));
7792 Ops.push_back(
II->getArgOperand(1));
7794 case Intrinsic::start_loop_iterations:
7795 case Intrinsic::annotation:
7796 case Intrinsic::ptr_annotation:
7797 Ops.push_back(
II->getArgOperand(0));
7809const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7818 if (!DT.isReachableFromEntry(
I->getParent()))
7833 switch (BO->Opcode) {
7834 case Instruction::Add: {
7860 if (BO->Opcode == Instruction::Sub)
7868 if (BO->Opcode == Instruction::Sub)
7875 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7876 NewBO->Opcode != Instruction::Sub)) {
7886 case Instruction::Mul: {
7907 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7916 case Instruction::UDiv:
7920 case Instruction::URem:
7924 case Instruction::Sub: {
7927 Flags = getNoWrapFlagsFromUB(BO->
Op);
7932 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
7935 if (HasPtrLHS || HasPtrRHS) {
7940 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
7941 bool BothPtr) ->
const SCEV * {
7944 const SCEV *PtrSCEV =
getSCEV(PtrOp);
7954 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
7955 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
7963 case Instruction::And:
7969 if (CI->isMinusOne())
7971 const APInt &
A = CI->getValue();
7977 unsigned LZ =
A.countl_zero();
7978 unsigned TZ =
A.countr_zero();
7983 APInt EffectiveMask =
7985 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
7988 const SCEV *ShiftedLHS =
nullptr;
7992 unsigned MulZeros = OpC->getAPInt().countr_zero();
7993 unsigned GCD = std::min(MulZeros, TZ);
7998 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8020 case Instruction::Or:
8029 case Instruction::Xor:
8032 if (CI->isMinusOne())
8041 if (LBO->getOpcode() == Instruction::And &&
8042 LCI->getValue() == CI->getValue())
8043 if (
const SCEVZeroExtendExpr *Z =
8046 const SCEV *Z0 =
Z->getOperand();
8053 if (CI->getValue().isMask(Z0TySize))
8059 APInt Trunc = CI->getValue().trunc(Z0TySize);
8068 case Instruction::Shl:
8086 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8095 ConstantInt *
X = ConstantInt::get(
8101 case Instruction::AShr:
8123 const SCEV *AddTruncateExpr =
nullptr;
8124 ConstantInt *ShlAmtCI =
nullptr;
8125 const SCEV *AddConstant =
nullptr;
8127 if (L &&
L->getOpcode() == Instruction::Add) {
8135 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8142 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8150 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8155 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8160 if (AddTruncateExpr && ShlAmtCI) {
8172 const APInt &ShlAmt = ShlAmtCI->
getValue();
8176 const SCEV *CompositeExpr =
8178 if (
L->getOpcode() != Instruction::Shl)
8179 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8188 switch (
U->getOpcode()) {
8189 case Instruction::Trunc:
8192 case Instruction::ZExt:
8195 case Instruction::SExt:
8205 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8206 Type *Ty =
U->getType();
8214 case Instruction::BitCast:
8220 case Instruction::PtrToAddr: {
8227 case Instruction::PtrToInt:
8231 case Instruction::IntToPtr:
8235 case Instruction::SDiv:
8242 case Instruction::SRem:
8249 case Instruction::GetElementPtr:
8252 case Instruction::PHI:
8255 case Instruction::Select:
8256 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8259 case Instruction::Call:
8260 case Instruction::Invoke:
8265 switch (
II->getIntrinsicID()) {
8266 case Intrinsic::abs:
8270 case Intrinsic::umax:
8274 case Intrinsic::umin:
8278 case Intrinsic::smax:
8282 case Intrinsic::smin:
8286 case Intrinsic::usub_sat: {
8287 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8288 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8292 case Intrinsic::uadd_sat: {
8293 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8294 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8298 case Intrinsic::start_loop_iterations:
8299 case Intrinsic::annotation:
8300 case Intrinsic::ptr_annotation:
8304 case Intrinsic::vscale:
8324 auto *ExitCountType = ExitCount->
getType();
8325 assert(ExitCountType->isIntegerTy());
8327 1 + ExitCountType->getScalarSizeInBits());
8340 auto CanAddOneWithoutOverflow = [&]() {
8342 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8353 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8383 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8384 assert(L->isLoopExiting(ExitingBlock) &&
8385 "Exiting block must actually branch out of the loop!");
8394 const auto *MaxExitCount =
8402 L->getExitingBlocks(ExitingBlocks);
8405 if (ExitingBlocks.
empty() ||
8421 const LoopGuards &Guards) {
8425 const SCEV *TCExpr =
8433 : (
unsigned)Multiple.getZExtValue();
8437 const SCEV *ExitCount) {
8459 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8460 assert(L->isLoopExiting(ExitingBlock) &&
8461 "Exiting block must actually branch out of the loop!");
8471 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8473 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8475 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8485 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8488 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8491 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8499 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8506 return getBackedgeTakenInfo(L).getExact(L,
this);
8508 return getBackedgeTakenInfo(L).getConstantMax(
this);
8510 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8517 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8522 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8526 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8536 for (
PHINode &PN : Header->phis())
8537 if (Visited.
insert(&PN).second)
8541ScalarEvolution::BackedgeTakenInfo &
8542ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8543 auto &BTI = getBackedgeTakenInfo(L);
8544 if (BTI.hasFullInfo())
8547 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8550 return Pair.first->second;
8552 BackedgeTakenInfo
Result =
8553 computeBackedgeTakenCount(L,
true);
8555 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8558ScalarEvolution::BackedgeTakenInfo &
8559ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8565 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8566 BackedgeTakenCounts.try_emplace(L);
8568 return Pair.first->second;
8573 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8580 if (
Result.hasAnyInfo()) {
8583 auto LoopUsersIt = LoopUsers.find(L);
8584 if (LoopUsersIt != LoopUsers.end())
8586 forgetMemoizedResults(ToForget);
8589 for (PHINode &PN :
L->getHeader()->phis())
8590 ConstantEvolutionLoopExitValue.erase(&PN);
8598 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8607 BackedgeTakenCounts.clear();
8608 PredicatedBackedgeTakenCounts.clear();
8609 BECountUsers.clear();
8610 LoopPropertiesCache.clear();
8611 ConstantEvolutionLoopExitValue.clear();
8612 ValueExprMap.clear();
8613 ValuesAtScopes.clear();
8614 ValuesAtScopesUsers.clear();
8615 LoopDispositions.clear();
8616 BlockDispositions.clear();
8617 UnsignedRanges.clear();
8618 SignedRanges.clear();
8619 ExprValueMap.clear();
8621 ConstantMultipleCache.clear();
8622 PredicatedSCEVRewrites.clear();
8624 FoldCacheUser.clear();
8626void ScalarEvolution::visitAndClearUsers(
8630 while (!Worklist.
empty()) {
8637 if (It != ValueExprMap.
end()) {
8639 eraseValueFromMap(It->first);
8641 ConstantEvolutionLoopExitValue.erase(PN);
8655 while (!LoopWorklist.
empty()) {
8659 forgetBackedgeTakenCounts(CurrL,
false);
8660 forgetBackedgeTakenCounts(CurrL,
true);
8663 PredicatedSCEVRewrites.remove_if(
8664 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8666 auto LoopUsersItr = LoopUsers.find(CurrL);
8667 if (LoopUsersItr != LoopUsers.end())
8672 visitAndClearUsers(Worklist, Visited, ToForget);
8674 LoopPropertiesCache.erase(CurrL);
8677 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8679 forgetMemoizedResults(ToForget);
8696 visitAndClearUsers(Worklist, Visited, ToForget);
8698 forgetMemoizedResults(ToForget);
8706 auto InvalidateValue = [&](
Value *Val) {
8710 struct InvalidationRootCollector {
8714 InvalidationRootCollector(
Loop *L) : L(L) {}
8716 bool follow(
const SCEV *S) {
8722 if (L->contains(AddRec->
getLoop()))
8727 bool isDone()
const {
return false; }
8730 InvalidationRootCollector
C(L);
8732 forgetMemoizedResults(
C.Roots);
8755 BlockDispositions.clear();
8756 LoopDispositions.clear();
8773 while (!Worklist.
empty()) {
8775 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8776 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8777 if (!LoopDispoRemoved && !BlockDispoRemoved)
8779 auto Users = SCEVUsers.find(Curr);
8780 if (
Users != SCEVUsers.end())
8793const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8797 if (!isComplete() || ExitNotTaken.
empty())
8808 for (
const auto &ENT : ExitNotTaken) {
8809 const SCEV *BECount = ENT.ExactNotTaken;
8812 "We should only have known counts for exiting blocks that dominate "
8815 Ops.push_back(BECount);
8820 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8821 "Predicate should be always true!");
8830const ScalarEvolution::ExitNotTakenInfo *
8831ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8832 const BasicBlock *ExitingBlock,
8833 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8834 for (
const auto &ENT : ExitNotTaken)
8835 if (ENT.ExitingBlock == ExitingBlock) {
8836 if (ENT.hasAlwaysTruePredicate())
8838 else if (Predicates) {
8848const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8850 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8851 if (!getConstantMax())
8854 for (
const auto &ENT : ExitNotTaken)
8855 if (!ENT.hasAlwaysTruePredicate()) {
8863 "No point in having a non-constant max backedge taken count!");
8864 return getConstantMax();
8867const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8869 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8877 for (
const auto &ENT : ExitNotTaken) {
8878 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8881 "We should only have known counts for exiting blocks that "
8887 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8888 "Predicate should be always true!");
8891 if (ExitCounts.
empty())
8900bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8902 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8903 return !ENT.hasAlwaysTruePredicate();
8905 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8921 this->ExactNotTaken = E = ConstantMaxNotTaken;
8922 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8927 "Exact is not allowed to be less precise than Constant Max");
8930 "Exact is not allowed to be less precise than Symbolic Max");
8933 "Symbolic Max is not allowed to be less precise than Constant Max");
8936 "No point in having a non-constant max backedge taken count!");
8938 for (
const auto PredList : PredLists)
8939 for (
const auto *
P : PredList) {
8947 "Backedge count should be int");
8950 "Max backedge count should be int");
8963ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8965 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8966 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8967 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8969 ExitNotTaken.reserve(ExitCounts.
size());
8970 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8971 std::back_inserter(ExitNotTaken),
8972 [&](
const EdgeExitInfo &EEI) {
8973 BasicBlock *ExitBB = EEI.first;
8974 const ExitLimit &EL = EEI.second;
8975 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
8976 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
8981 "No point in having a non-constant max backedge taken count!");
8985ScalarEvolution::BackedgeTakenInfo
8986ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
8987 bool AllowPredicates) {
8989 L->getExitingBlocks(ExitingBlocks);
8991 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8994 bool CouldComputeBECount =
true;
8996 const SCEV *MustExitMaxBECount =
nullptr;
8997 const SCEV *MayExitMaxBECount =
nullptr;
8998 bool MustExitMaxOrZero =
false;
8999 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9010 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9011 if (ExitIfTrue == CI->
isZero())
9015 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9017 assert((AllowPredicates || EL.Predicates.empty()) &&
9018 "Predicated exit limit when predicates are not allowed!");
9023 ++NumExitCountsComputed;
9027 CouldComputeBECount =
false;
9034 "Exact is known but symbolic isn't?");
9035 ++NumExitCountsNotComputed;
9050 DT.dominates(ExitBB, Latch)) {
9051 if (!MustExitMaxBECount) {
9052 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9053 MustExitMaxOrZero = EL.MaxOrZero;
9056 EL.ConstantMaxNotTaken);
9060 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9063 EL.ConstantMaxNotTaken);
9067 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9071 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9077 for (
const auto &Pair : ExitCounts) {
9079 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9081 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9082 {
L, AllowPredicates});
9084 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9085 MaxBECount, MaxOrZero);
9088ScalarEvolution::ExitLimit
9089ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9090 bool IsOnlyExit,
bool AllowPredicates) {
9091 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9095 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9100 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9101 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9102 "It should have one successor in loop and one exit block!");
9113 if (!
L->contains(SBB)) {
9118 assert(Exit &&
"Exiting block must have at least one exit");
9119 return computeExitLimitFromSingleExitSwitch(
9120 L, SI, Exit, IsOnlyExit);
9127 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9128 bool AllowPredicates) {
9129 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9130 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9131 ControlsOnlyExit, AllowPredicates);
9134std::optional<ScalarEvolution::ExitLimit>
9135ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9136 bool ExitIfTrue,
bool ControlsOnlyExit,
9137 bool AllowPredicates) {
9139 (void)this->ExitIfTrue;
9140 (void)this->AllowPredicates;
9142 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9143 this->AllowPredicates == AllowPredicates &&
9144 "Variance in assumed invariant key components!");
9145 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9146 if (Itr == TripCountMap.end())
9147 return std::nullopt;
9151void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9153 bool ControlsOnlyExit,
9154 bool AllowPredicates,
9156 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9157 this->AllowPredicates == AllowPredicates &&
9158 "Variance in assumed invariant key components!");
9160 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9161 assert(InsertResult.second &&
"Expected successful insertion!");
9166ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9167 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9168 bool ControlsOnlyExit,
bool AllowPredicates) {
9170 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9174 ExitLimit EL = computeExitLimitFromCondImpl(
9175 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9176 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9180ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9181 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9182 bool ControlsOnlyExit,
bool AllowPredicates) {
9184 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9185 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9186 return *LimitFromBinOp;
9192 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9193 if (EL.hasFullInfo() || !AllowPredicates)
9197 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9217 const WithOverflowInst *WO;
9232 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9233 ControlsOnlyExit, AllowPredicates);
9234 if (EL.hasAnyInfo())
9239 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9242std::optional<ScalarEvolution::ExitLimit>
9243ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9247 bool AllowPredicates) {
9256 return std::nullopt;
9260 ExitLimit EL0 = computeExitLimitFromCondCached(
9261 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9262 ExitLimit EL1 = computeExitLimitFromCondCached(
9263 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9268 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9273 if (EitherMayExit) {
9283 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9285 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9288 EL1.ConstantMaxNotTaken);
9290 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9292 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9295 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9299 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9300 BECount = EL0.ExactNotTaken;
9313 SymbolicMaxBECount =
9315 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9319ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9320 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9321 bool AllowPredicates) {
9333 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9335 if (EL.hasAnyInfo())
9338 auto *ExhaustiveCount =
9339 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9342 return ExhaustiveCount;
9344 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9347ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9349 bool ControlsOnlyExit,
bool AllowPredicates) {
9374 ConstantRange CompRange =
9392 InnerLHS = ZExt->getOperand();
9439 if (EL.hasAnyInfo())
9456 if (EL.hasAnyInfo())
return EL;
9488 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9490 if (EL.hasAnyInfo())
9506 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9508 if (EL.hasAnyInfo())
9519ScalarEvolution::ExitLimit
9520ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9522 BasicBlock *ExitingBlock,
9523 bool ControlsOnlyExit) {
9524 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9527 if (
Switch->getDefaultDest() == ExitingBlock)
9531 "Default case must not exit the loop!");
9537 if (EL.hasAnyInfo())
9549 "Evaluation of SCEV at constant didn't fold correctly?");
9553ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9563 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9570 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9572 unsigned &OutShiftAmt) {
9573 using namespace PatternMatch;
9575 ConstantInt *ShiftAmt;
9577 OutOpCode = Instruction::LShr;
9579 OutOpCode = Instruction::AShr;
9581 OutOpCode = Instruction::Shl;
9586 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9601 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9603 unsigned &ShiftAmtOut) {
9604 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9620 if (MatchPositiveShift(
LHS, V, OpC, Amt)) {
9621 PostShiftOpCode = OpC;
9627 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9630 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9636 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9643 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9649 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9661 ConstantInt *StableValue =
nullptr;
9666 case Instruction::AShr: {
9673 if (
Known.isNonNegative())
9674 StableValue = ConstantInt::get(Ty, 0);
9675 else if (
Known.isNegative())
9676 StableValue = ConstantInt::get(Ty, -1,
true);
9682 case Instruction::LShr:
9683 case Instruction::Shl:
9693 "Otherwise cannot be an operand to a branch instruction");
9695 if (
Result->isNullValue()) {
9704 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9706 const SCEV *StartSCEV =
getSCEV(StartValue);
9710 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9711 MaxBTC = std::min(MaxBTC, RangeBTC);
9715 const SCEV *UpperBound =
9732 if (
const Function *
F = CI->getCalledFunction())
9741 if (!L->contains(
I))
return false;
9746 return L->getHeader() ==
I->getParent();
9822 if (!
I)
return nullptr;
9835 std::vector<Constant*>
Operands(
I->getNumOperands());
9837 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9846 if (!
C)
return nullptr;
9868 if (IncomingVal != CurrentVal) {
9871 IncomingVal = CurrentVal;
9883ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9886 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9895 DenseMap<Instruction *, Constant *> CurrentIterVals;
9897 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9903 for (PHINode &
PHI : Header->phis()) {
9905 CurrentIterVals[&
PHI] = StartCST;
9907 if (!CurrentIterVals.
count(PN))
9908 return RetVal =
nullptr;
9914 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9917 unsigned IterationNum = 0;
9919 for (; ; ++IterationNum) {
9920 if (IterationNum == NumIterations)
9921 return RetVal = CurrentIterVals[PN];
9925 DenseMap<Instruction *, Constant *> NextIterVals;
9930 NextIterVals[PN] = NextPHI;
9932 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9938 for (
const auto &
I : CurrentIterVals) {
9940 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9945 for (
const auto &
I : PHIsToCompute) {
9946 PHINode *
PHI =
I.first;
9949 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9952 if (NextPHI !=
I.second)
9953 StoppedEvolving =
false;
9958 if (StoppedEvolving)
9959 return RetVal = CurrentIterVals[PN];
9961 CurrentIterVals.swap(NextIterVals);
9965const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
9975 DenseMap<Instruction *, Constant *> CurrentIterVals;
9977 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9980 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
9982 for (PHINode &
PHI : Header->phis()) {
9984 CurrentIterVals[&
PHI] = StartCST;
9986 if (!CurrentIterVals.
count(PN))
9994 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10001 if (CondVal->getValue() ==
uint64_t(ExitWhen)) {
10002 ++NumBruteForceTripCountsComputed;
10007 DenseMap<Instruction *, Constant *> NextIterVals;
10013 for (
const auto &
I : CurrentIterVals) {
10015 if (!
PHI ||
PHI->getParent() != Header)
continue;
10018 for (PHINode *
PHI : PHIsToCompute) {
10020 if (NextPHI)
continue;
10022 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10025 CurrentIterVals.
swap(NextIterVals);
10033 auto &
Values = ValuesAtScopes[V];
10037 return LS.second ? LS.second :
SCEVUse(V);
10039 Values.emplace_back(L,
nullptr);
10042 SCEVUse C = computeSCEVAtScope(V, L);
10043 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10044 if (LS.first == L) {
10050 ValuesAtScopesUsers[
C.getPointer()].push_back({L, V});
10061 switch (V->getSCEVType()) {
10094 assert(!
C->getType()->isPointerTy() &&
10095 "Can only have one pointer, and it must be last");
10120const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10121 SmallVectorImpl<SCEVUse> &NewOps) {
10155SCEVUse ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10156 switch (
V->getSCEVType()) {
10167 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10178 for (++i; i !=
e; ++i)
10218 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10228 for (++i; i !=
e; ++i) {
10233 return getWithOperands(V, NewOps);
10248 const Loop *CurrLoop = this->LI[
I->getParent()];
10259 if (BackedgeTakenCount->
isZero()) {
10260 Value *InitValue =
nullptr;
10261 bool MultipleInitValues =
false;
10267 MultipleInitValues =
true;
10272 if (!MultipleInitValues && InitValue)
10281 unsigned InLoopPred =
10292 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10306 SmallVector<Constant *, 4>
Operands;
10308 bool MadeImprovement =
false;
10323 MadeImprovement |= OrigV != OpV;
10328 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10333 if (!MadeImprovement)
10354const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10356 return stripInjectiveFunctions(ZExt->getOperand());
10358 return stripInjectiveFunctions(SExt->getOperand());
10376 assert(
A != 0 &&
"A must be non-zero.");
10392 if (MinTZ < Mult2 && L->getLoopPredecessor())
10394 if (MinTZ < Mult2) {
10417 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10437static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10443 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10444 << *AddRec <<
'\n');
10447 if (!LC || !MC || !
NC) {
10448 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10449 return std::nullopt;
10455 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10463 N =
N.sext(NewWidth);
10464 M = M.sext(NewWidth);
10465 L = L.sext(NewWidth);
10482 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10483 <<
", multiplied by " <<
T <<
'\n');
10492 std::optional<APInt>
Y) {
10494 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10497 return XW.
slt(YW) ? *
X : *
Y;
10500 return std::nullopt;
10501 return X ? *
X : *
Y;
10518 return std::nullopt;
10519 unsigned W =
X->getBitWidth();
10539static std::optional<APInt>
10545 return std::nullopt;
10548 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10549 std::optional<APInt>
X =
10552 return std::nullopt;
10557 return std::nullopt;
10572static std::optional<APInt>
10576 "Starting value of addrec should be 0");
10577 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10578 <<
Range <<
", addrec " << *AddRec <<
'\n');
10582 "Addrec's initial value should be in range");
10588 return std::nullopt;
10598 auto SolveForBoundary =
10599 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10602 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10603 << Bound <<
" (before multiplying by " << M <<
")\n");
10606 std::optional<APInt> SO;
10609 "signed overflow\n");
10613 "unsigned overflow\n");
10614 std::optional<APInt> UO =
10617 auto LeavesRange = [&] (
const APInt &
X) {
10625 if (
Range.contains(
V1->getValue()))
10634 return {std::nullopt,
false};
10639 if (LeavesRange(*Min))
10640 return { Min,
true };
10641 std::optional<APInt> Max = Min == SO ? UO : SO;
10642 if (LeavesRange(*Max))
10643 return { Max,
true };
10646 return {std::nullopt,
true};
10653 auto SL = SolveForBoundary(
Lower);
10654 auto SU = SolveForBoundary(
Upper);
10657 if (!SL.second || !SU.second)
10658 return std::nullopt;
10701ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10703 bool ControlsOnlyExit,
10704 bool AllowPredicates) {
10715 if (
C->getValue()->isZero())
return C;
10719 const SCEVAddRecExpr *AddRec =
10722 if (!AddRec && AllowPredicates)
10728 if (!AddRec || AddRec->
getLoop() != L)
10739 return ExitLimit(R, R, R,
false, Predicates);
10797 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10827 const SCEV *
Exact =
10835 const SCEV *SymbolicMax =
10837 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10846 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10854 return ExitLimit(
E, M, S,
false, Predicates);
10857ScalarEvolution::ExitLimit
10858ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10866 if (!
C->getValue()->isZero())
10876std::pair<const BasicBlock *, const BasicBlock *>
10877ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10888 if (
const Loop *L = LI.getLoopFor(BB))
10889 return {
L->getLoopPredecessor(),
L->getHeader()};
10891 return {
nullptr, BB};
10900 if (
A ==
B)
return true;
10915 if (ComputesEqualValues(AI, BI))
10923 const SCEV *Op0, *Op1;
10942 auto TrivialCase = [&](
bool TriviallyTrue) {
10951 const SCEV *NewLHS, *NewRHS;
10975 return TrivialCase(
false);
10976 return TrivialCase(
true);
10995 RAdd->hasNoSignedWrap()) ||
10997 RAdd->hasNoUnsignedWrap())) {
11017 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
11018 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
11021 C->getAPInt().isStrictlyPositive()) ||
11045 const APInt &
RA = RC->getAPInt();
11047 bool SimplifiedByConstantRange =
false;
11052 return TrivialCase(
true);
11054 return TrivialCase(
false);
11063 Changed = SimplifiedByConstantRange =
true;
11067 if (!SimplifiedByConstantRange) {
11084 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11090 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11096 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11102 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11122 return TrivialCase(
true);
11124 return TrivialCase(
false);
11229 auto NonRecursive = [OrNegative](
const SCEV *S) {
11231 return C->getAPInt().isPowerOf2() ||
11232 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11238 if (NonRecursive(S))
11248 const SCEV *S, uint64_t M,
11264 APInt C = Cst->getAPInt();
11265 return C.urem(M) == 0;
11273 const SCEV *SmodM =
11291 for (
auto *
A : *Predicates)
11292 if (
A->implies(
P, *
this))
11305std::pair<const SCEV *, const SCEV *>
11308 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11310 return { Start, Start };
11312 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11321 getUsedLoops(LHS, LoopsUsed);
11322 getUsedLoops(RHS, LoopsUsed);
11324 if (LoopsUsed.
empty())
11329 for (
const auto *L1 : LoopsUsed)
11330 for (
const auto *L2 : LoopsUsed)
11331 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11332 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11333 "Domination relationship is not a linear order");
11363 SplitRHS.second) &&
11373 isKnownPredicateViaSplitting(Pred, LHS, RHS) ||
11374 isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11384 return std::nullopt;
11399 if (KnownWithoutContext)
11400 return KnownWithoutContext;
11407 return std::nullopt;
11413 const Loop *L = LHS->getLoop();
11418std::optional<ScalarEvolution::MonotonicPredicateType>
11421 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11427 auto ResultSwapped =
11430 assert(*ResultSwapped != *Result &&
11431 "monotonicity should flip as we flip the predicate");
11438std::optional<ScalarEvolution::MonotonicPredicateType>
11439ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11453 return std::nullopt;
11457 "Should be greater or less!");
11461 if (!LHS->hasNoUnsignedWrap())
11462 return std::nullopt;
11466 "Relational predicate is either signed or unsigned!");
11467 if (!
LHS->hasNoSignedWrap())
11468 return std::nullopt;
11470 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11478 return std::nullopt;
11481std::optional<ScalarEvolution::LoopInvariantPredicate>
11488 return std::nullopt;
11495 if (!ArLHS || ArLHS->
getLoop() != L)
11496 return std::nullopt;
11500 return std::nullopt;
11526 return std::nullopt;
11563 return std::nullopt;
11566std::optional<ScalarEvolution::LoopInvariantPredicate>
11571 Pred, LHS, RHS, L, CtxI, MaxIter))
11581 Pred, LHS, RHS, L, CtxI,
Op))
11583 return std::nullopt;
11586std::optional<ScalarEvolution::LoopInvariantPredicate>
11601 return std::nullopt;
11608 if (!AR || AR->
getLoop() != L)
11609 return std::nullopt;
11614 Pred = Pred.dropSameSign();
11618 return std::nullopt;
11624 if (Step != One && Step != MinusOne)
11625 return std::nullopt;
11631 return std::nullopt;
11637 return std::nullopt;
11645 if (Step == MinusOne)
11649 return std::nullopt;
11655bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11661 auto CheckRange = [&](
bool IsSigned) {
11664 return RangeLHS.
icmp(Pred, RangeRHS);
11673 if (CheckRange(
true) || CheckRange(
false))
11682bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11691 SCEVUse XNonConstOp, XConstOp;
11692 SCEVUse YNonConstOp, YConstOp;
11696 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11699 XFlagsPresent = ExpectedFlags;
11704 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11707 YFlagsPresent = ExpectedFlags;
11710 if (YNonConstOp != XNonConstOp)
11718 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11721 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11781bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11802bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11803 const SCEV *
LHS,
const SCEV *
RHS) {
11808 return any_of(*BB, [&](
const Instruction &
I) {
11809 using namespace llvm::PatternMatch;
11814 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11828 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11833 "This cannot be done on broken IR!");
11836 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11845 if (LoopContinuePredicate &&
11846 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11847 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11852 if (WalkingBEDominatingConds)
11858 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11859 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11866 const SCEV *LoopCounter =
11874 for (
auto &AssumeVH : AC.assumptions()) {
11881 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11885 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11888 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11889 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11890 assert(DTN &&
"should reach the loop header before reaching the root!");
11893 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11911 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
11924 if (!DT.isReachableFromEntry(BB))
11928 "This cannot be done on broken IR!");
11936 const bool ProvingStrictComparison =
11938 bool ProvedNonStrictComparison =
false;
11939 bool ProvedNonEquality =
false;
11942 if (!ProvedNonStrictComparison)
11943 ProvedNonStrictComparison = Fn(NonStrictPredicate);
11944 if (!ProvedNonEquality)
11946 if (ProvedNonStrictComparison && ProvedNonEquality)
11951 if (ProvingStrictComparison) {
11953 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
11955 if (SplitAndProve(ProofFn))
11960 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
11962 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
11964 if (ProvingStrictComparison) {
11966 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
11968 if (SplitAndProve(ProofFn))
11977 const Loop *ContainingLoop = LI.getLoopFor(BB);
11979 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
11983 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
11984 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
11987 if (!BlockEntryPredicate)
11996 for (
auto &AssumeVH : AC.assumptions()) {
12000 if (!DT.dominates(CI, BB))
12003 if (ProveViaCond(CI->getArgOperand(0),
false))
12009 F.getParent(), Intrinsic::experimental_guard);
12011 for (
const auto *GU : GuardDecl->users())
12013 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12014 if (ProveViaCond(Guard->getArgOperand(0),
false))
12029 "LHS is not available at Loop Entry");
12031 "RHS is not available at Loop Entry");
12033 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12044 if (FoundCondValue ==
12048 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12052 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12055 const Value *Op0, *Op1;
12058 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12062 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12063 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12067 if (!ICI)
return false;
12071 CmpPredicate FoundPred;
12080 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12083bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12084 const SCEV *
RHS, CmpPredicate FoundPred,
12085 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12086 const Instruction *CtxI) {
12096 auto *WideType = FoundLHS->
getType();
12108 TruncFoundLHS, TruncFoundRHS, CtxI))
12134 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12138bool ScalarEvolution::isImpliedCondBalancedTypes(
12143 "Types should be balanced!");
12150 if (FoundLHS == FoundRHS)
12154 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12166 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12183 LHS, FoundLHS, FoundRHS, CtxI);
12185 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12207 assert(P1 != P2 &&
"Handled earlier!");
12211 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12215 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12218 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12219 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12220 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12225 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12236 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12237 CanonicalRHS, CanonicalFoundLHS,
12238 CanonicalFoundRHS);
12243 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12244 CanonicalRHS, CanonicalFoundLHS,
12245 CanonicalFoundRHS);
12252 const SCEVConstant *
C =
nullptr;
12253 const SCEV *
V =
nullptr;
12271 if (Min ==
C->getAPInt()) {
12276 APInt SharperMin = Min + 1;
12279 case ICmpInst::ICMP_SGE:
12280 case ICmpInst::ICMP_UGE:
12283 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12288 case ICmpInst::ICMP_SGT:
12289 case ICmpInst::ICMP_UGT:
12299 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12304 case ICmpInst::ICMP_SLE:
12305 case ICmpInst::ICMP_ULE:
12306 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12307 LHS, V, getConstant(SharperMin), CtxI))
12311 case ICmpInst::ICMP_SLT:
12312 case ICmpInst::ICMP_ULT:
12313 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12314 LHS, V, getConstant(Min), CtxI))
12328 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12332 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12335 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12351std::optional<APInt>
12358 APInt DiffMul(BW, 1);
12361 for (
unsigned I = 0;
I < 8; ++
I) {
12370 if (LAR->getLoop() != MAR->getLoop())
12371 return std::nullopt;
12375 if (!LAR->isAffine() || !MAR->isAffine())
12376 return std::nullopt;
12378 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12379 return std::nullopt;
12381 Less = LAR->getStart();
12382 More = MAR->getStart();
12387 auto MatchConstMul =
12388 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12393 return std::nullopt;
12395 if (
auto MatchedMore = MatchConstMul(More)) {
12396 if (
auto MatchedLess = MatchConstMul(
Less)) {
12397 if (MatchedMore->second == MatchedLess->second) {
12398 More = MatchedMore->first;
12399 Less = MatchedLess->first;
12400 DiffMul *= MatchedMore->second;
12411 Diff +=
C->getAPInt() * DiffMul;
12414 Diff -=
C->getAPInt() * DiffMul;
12417 Multiplicity[S] +=
Mul;
12419 auto Decompose = [&](
const SCEV *S,
int Mul) {
12426 Decompose(More, 1);
12427 Decompose(
Less, -1);
12431 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12432 for (
const auto &[S,
Mul] : Multiplicity) {
12437 return std::nullopt;
12439 }
else if (
Mul == -1) {
12441 return std::nullopt;
12444 return std::nullopt;
12448 if (NewMore == More || NewLess ==
Less)
12449 return std::nullopt;
12455 if (!More && !
Less)
12459 if (!More || !
Less)
12460 return std::nullopt;
12464 return std::nullopt;
12467bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12489 const auto *Latch = L->getLoopLatch();
12492 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12501 const auto *Latch = L->getLoopLatch();
12504 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12514bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12517 const SCEV *FoundLHS,
12518 const SCEV *FoundRHS) {
12527 if (!AddRecFoundLHS)
12534 const Loop *
L = AddRecFoundLHS->getLoop();
12535 if (L != AddRecLHS->getLoop())
12574 if (!RDiff || *LDiff != *RDiff)
12577 if (LDiff->isMinValue())
12580 APInt FoundRHSLimit;
12583 FoundRHSLimit = -(*RDiff);
12595bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12596 const SCEV *
RHS,
const SCEV *FoundLHS,
12597 const SCEV *FoundRHS,
unsigned Depth) {
12598 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12602 bool Erased = PendingMerges.erase(LPhi);
12603 assert(Erased &&
"Failed to erase LPhi!");
12607 bool Erased = PendingMerges.erase(RPhi);
12608 assert(Erased &&
"Failed to erase RPhi!");
12616 if (!PendingMerges.insert(Phi).second)
12630 if (!PendingMerges.insert(Phi).second)
12636 if (!LPhi && !RPhi)
12647 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12651 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12652 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12653 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12654 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12657 if (RPhi && RPhi->getParent() == LBB) {
12664 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12665 if (!ProvedEasily(L, R))
12676 auto *RLoop = RAR->
getLoop();
12677 auto *Predecessor = RLoop->getLoopPredecessor();
12678 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12680 if (!ProvedEasily(L1, RAR->
getStart()))
12682 auto *Latch = RLoop->getLoopLatch();
12683 assert(Latch &&
"Loop with AddRec with no latch?");
12704 if (
auto *
Loop = LI.getLoopFor(LBB))
12707 if (!ProvedEasily(L,
RHS))
12714bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12717 const SCEV *FoundLHS,
12718 const SCEV *FoundRHS) {
12721 if (
RHS == FoundRHS) {
12726 if (
LHS != FoundLHS)
12733 Value *Shiftee, *ShiftValue;
12735 using namespace PatternMatch;
12736 if (
match(SUFoundRHS->getValue(),
12738 auto *ShifteeS =
getSCEV(Shiftee);
12756bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12757 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12758 const SCEV *FoundRHS) {
12790 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12798 return Diff == FoundDiff;
12801bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12803 const SCEV *FoundLHS,
12804 const SCEV *FoundRHS,
12805 const Instruction *CtxI) {
12806 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12808 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12810 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12811 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12813 isImpliedCondOperandsViaMatchingDiff(Pred,
LHS,
RHS, FoundLHS,
12815 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12819template <
typename MinMaxExprType>
12821 const SCEV *Candidate) {
12826 return is_contained(MinMaxExpr->operands(), Candidate);
12839 const SCEV *LStart, *RStart, *Step;
12937bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12939 const SCEV *FoundLHS,
12940 const SCEV *FoundRHS,
12944 "LHS and RHS have different sizes?");
12947 "FoundLHS and FoundRHS have different sizes?");
12981 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
12983 return Ext->getOperand();
12990 auto *OrigLHS =
LHS;
12991 auto *OrigFoundLHS = FoundLHS;
12992 LHS = GetOpFromSExt(
LHS);
12993 FoundLHS = GetOpFromSExt(FoundLHS);
12996 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
12999 FoundRHS,
Depth + 1);
13012 if (!LHSAddExpr->hasNoSignedWrap())
13015 SCEVUse LL = LHSAddExpr->getOperand(0);
13016 SCEVUse LR = LHSAddExpr->getOperand(1);
13020 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
13021 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
13026 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
13032 using namespace llvm::PatternMatch;
13051 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13059 auto *DTy = Denominator->getType();
13060 auto *FRHSTy = FoundRHS->
getType();
13061 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13080 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13091 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13093 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13101 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13134bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13138 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13142 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13145bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13148 const SCEV *FoundLHS,
13149 const SCEV *FoundRHS) {
13185 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13191bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13192 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13193 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13207 ConstantRange FoundLHSRange =
13211 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13218 return LHSRange.
icmp(Pred, ConstRHS);
13221bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13234 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13242 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13245bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
13257 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
13265 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
13277const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
13278 const SCEV *Stride,
13309 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13320 :
APIntOps::umax(MaxEnd, MinStart);
13327ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13328 const Loop *L,
bool IsSigned,
13329 bool ControlsOnlyExit,
bool AllowPredicates) {
13333 bool PredicatedIV =
false;
13338 auto canProveNUW = [&]() {
13341 if (!ControlsOnlyExit)
13362 Limit = Limit.
zext(OuterBitWidth);
13374 Type *Ty = ZExt->getType();
13385 if (!
IV && AllowPredicates) {
13390 PredicatedIV =
true;
13394 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13408 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13411 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13416 bool IVMayOverflow =
true;
13419 if (!PositiveStride) {
13471 auto wouldZeroStrideBeUB = [&]() {
13483 if (!wouldZeroStrideBeUB()) {
13490 IVMayOverflow = canIVOverflowOnLT(
RHS, Stride, IsSigned);
13491 if (IVMayOverflow && !NoWrap)
13504 const SCEV *
Start =
IV->getStart();
13510 const SCEV *OrigStart =
Start;
13511 const SCEV *OrigRHS =
RHS;
13512 if (
Start->getType()->isPointerTy()) {
13523 const SCEV *End =
nullptr, *BECount =
nullptr,
13524 *BECountIfBackedgeTaken =
nullptr;
13527 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13528 any(RHSAddRec->getNoWrapFlags())) {
13541 const SCEV *RHSStart = RHSAddRec->getStart();
13542 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13554 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13563 BECountIfBackedgeTaken =
13568 if (BECount ==
nullptr) {
13573 const SCEV *MaxBECount = computeMaxBECountForLT(
13576 MaxBECount,
false , Predicates);
13582 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13588 if ((!IVMayOverflow ||
13621 const SCEV *Numerator =
13627 auto canProveRHSGreaterThanEqualStart = [&]() {
13646 auto *StartMinusOne =
13653 if (canProveRHSGreaterThanEqualStart()) {
13668 BECountIfBackedgeTaken =
13688 bool MayAddOverflow = IVMayOverflow && [&] {
13734 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13748 if (!MayAddOverflow) {
13760 const SCEV *ConstantMaxBECount;
13761 bool MaxOrZero =
false;
13763 ConstantMaxBECount = BECount;
13764 }
else if (BECountIfBackedgeTaken &&
13769 ConstantMaxBECount = BECountIfBackedgeTaken;
13772 ConstantMaxBECount = computeMaxBECountForLT(
13780 const SCEV *SymbolicMaxBECount =
13782 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13786ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13787 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13788 bool ControlsOnlyExit,
bool AllowPredicates) {
13795 if (!
IV && AllowPredicates)
13802 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13806 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13819 bool MayAddOverflow =
false;
13820 const SCEV *
Start =
IV->getStart();
13821 const SCEV *End =
RHS;
13822 if (!Stride->
isOne() && canIVOverflowOnGT(
RHS, Stride, IsSigned)) {
13825 MayAddOverflow =
true;
13838 if (
Start->getType()->isPointerTy()) {
13850 const SCEV *BECount;
13851 if (MayAddOverflow) {
13882 const SCEV *ConstantMaxBECount =
13889 ConstantMaxBECount = BECount;
13890 const SCEV *SymbolicMaxBECount =
13893 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13899 if (
Range.isFullSet())
13904 if (!SC->getValue()->isZero()) {
13910 return ShiftedAddRec->getNumIterationsInRange(
13911 Range.subtract(SC->getAPInt()), SE);
13942 APInt ExitVal = (End +
A).udiv(
A);
13955 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13956 "Linear scev computation is off in a bad way!");
13987 assert(!
Last->isZero() &&
"Recurrency with zero step?");
14013 Ty =
Store->getValueOperand()->getType();
14014 PtrTy =
Store->getPointerOperandType();
14016 Ty =
Load->getType();
14017 PtrTy =
Load->getPointerOperandType();
14031 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14033 SE->ConstantEvolutionLoopExitValue.erase(PN);
14034 SE->eraseValueFromMap(getValPtr());
14038void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
14039 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14049 : CallbackVH(
V), SE(se) {}
14058 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
14060 LoopDispositions(64), BlockDispositions(64) {
14072 F.getParent(), Intrinsic::experimental_guard);
14073 HasGuards = GuardDecl && !GuardDecl->use_empty();
14077 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
14078 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14079 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14080 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14081 PendingMerges(
std::
move(Arg.PendingMerges)),
14082 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14083 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14084 PredicatedBackedgeTakenCounts(
14085 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14086 BECountUsers(
std::
move(Arg.BECountUsers)),
14087 ConstantEvolutionLoopExitValue(
14088 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14089 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14090 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14091 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14092 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14093 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14094 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14095 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14096 SignedRanges(
std::
move(Arg.SignedRanges)),
14097 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14098 UniquePreds(
std::
move(Arg.UniquePreds)),
14099 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14100 ConstantSCEVs(
std::
move(Arg.ConstantSCEVs)),
14101 LoopUsers(
std::
move(Arg.LoopUsers)),
14102 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14103 FirstUnknown(Arg.FirstUnknown) {
14104 Arg.FirstUnknown =
nullptr;
14113 Tmp->~SCEVUnknown();
14115 FirstUnknown =
nullptr;
14117 ExprValueMap.clear();
14118 ValueExprMap.clear();
14120 BackedgeTakenCounts.clear();
14121 PredicatedBackedgeTakenCounts.clear();
14123 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14124 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14125 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14126 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14148 L->getHeader()->printAsOperand(OS,
false);
14152 L->getExitingBlocks(ExitingBlocks);
14153 if (ExitingBlocks.
size() != 1)
14154 OS <<
"<multiple exits> ";
14158 OS <<
"backedge-taken count is ";
14161 OS <<
"Unpredictable backedge-taken count.";
14164 if (ExitingBlocks.
size() > 1)
14165 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14166 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14174 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14177 OS <<
"\n Predicates:\n";
14178 for (
const auto *
P : Predicates)
14186 L->getHeader()->printAsOperand(OS,
false);
14191 OS <<
"constant max backedge-taken count is ";
14194 OS <<
", actual taken count either this or zero.";
14196 OS <<
"Unpredictable constant max backedge-taken count. ";
14201 L->getHeader()->printAsOperand(OS,
false);
14206 OS <<
"symbolic max backedge-taken count is ";
14209 OS <<
", actual taken count either this or zero.";
14211 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14215 if (ExitingBlocks.
size() > 1)
14216 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14217 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14227 OS <<
"\n predicated symbolic max exit count for "
14228 << ExitingBlock->
getName() <<
": ";
14230 OS <<
"\n Predicates:\n";
14231 for (
const auto *
P : Predicates)
14242 L->getHeader()->printAsOperand(OS,
false);
14245 OS <<
"Predicated backedge-taken count is ";
14248 OS <<
"Unpredictable predicated backedge-taken count.";
14250 OS <<
" Predicates:\n";
14251 for (
const auto *
P : Preds)
14256 auto *PredConstantMax =
14258 if (PredConstantMax != ConstantBTC) {
14260 L->getHeader()->printAsOperand(OS,
false);
14263 OS <<
"Predicated constant max backedge-taken count is ";
14266 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14268 OS <<
" Predicates:\n";
14269 for (
const auto *
P : Preds)
14274 auto *PredSymbolicMax =
14276 if (SymbolicBTC != PredSymbolicMax) {
14278 L->getHeader()->printAsOperand(OS,
false);
14281 OS <<
"Predicated symbolic max backedge-taken count is ";
14284 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14286 OS <<
" Predicates:\n";
14287 for (
const auto *
P : Preds)
14293 L->getHeader()->printAsOperand(OS,
false);
14320 OS <<
"Computable";
14330 OS <<
"DoesNotDominate";
14336 OS <<
"ProperlyDominates";
14353 OS <<
"Classifying expressions for: ";
14354 F.printAsOperand(OS,
false);
14369 const Loop *L = LI.getLoopFor(
I.getParent());
14384 OS <<
"\t\t" "Exits: ";
14387 OS <<
"<<Unknown>>";
14393 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14395 Iter->getHeader()->printAsOperand(OS,
false);
14403 InnerL->getHeader()->printAsOperand(OS,
false);
14414 OS <<
"Determining loop execution counts for: ";
14415 F.printAsOperand(OS,
false);
14423 auto &
Values = LoopDispositions[S];
14424 for (
auto &V :
Values) {
14425 if (V.getPointer() == L)
14430 auto &Values2 = LoopDispositions[S];
14432 if (V.getPointer() == L) {
14441ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14459 if (L->contains(AR->
getLoop()) &&
14461 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14466 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14467 " dominate the contained loop's header?");
14494 bool HasVarying =
false;
14495 bool HasUniform =
false;
14537 auto &
Values = BlockDispositions[S];
14538 for (
auto &V :
Values) {
14539 if (V.getPointer() == BB)
14544 auto &Values2 = BlockDispositions[S];
14546 if (V.getPointer() == BB) {
14555ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14584 bool Proper =
true;
14595 if (Instruction *
I =
14597 if (
I->getParent() == BB)
14599 if (DT.properlyDominates(
I->getParent(), BB))
14622void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14625 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14626 auto It = BECounts.find(L);
14627 if (It != BECounts.end()) {
14628 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14629 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14631 auto UserIt = BECountUsers.find(S);
14632 assert(UserIt != BECountUsers.end());
14637 BECounts.erase(It);
14645 while (!Worklist.
empty()) {
14647 auto Users = SCEVUsers.find(Curr);
14648 if (
Users != SCEVUsers.end())
14649 for (
const auto *User :
Users->second)
14650 if (ToForget.
insert(User).second)
14654 for (
const auto *S : ToForget)
14655 forgetMemoizedResultsImpl(S);
14657 PredicatedSCEVRewrites.remove_if(
14658 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14661void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14662 LoopDispositions.erase(S);
14663 BlockDispositions.erase(S);
14664 UnsignedRanges.erase(S);
14665 SignedRanges.erase(S);
14666 HasRecMap.erase(S);
14667 ConstantMultipleCache.erase(S);
14670 UnsignedWrapViaInductionTried.erase(AR);
14671 SignedWrapViaInductionTried.erase(AR);
14674 auto ExprIt = ExprValueMap.find(S);
14675 if (ExprIt != ExprValueMap.end()) {
14676 for (
Value *V : ExprIt->second) {
14677 auto ValueIt = ValueExprMap.find_as(V);
14678 if (ValueIt != ValueExprMap.end())
14679 ValueExprMap.erase(ValueIt);
14681 ExprValueMap.erase(ExprIt);
14684 auto ScopeIt = ValuesAtScopes.find(S);
14685 if (ScopeIt != ValuesAtScopes.end()) {
14686 for (
const auto &Pair : ScopeIt->second)
14688 llvm::erase(ValuesAtScopesUsers[Pair.second.getPointer()],
14689 std::make_pair(Pair.first, S));
14690 ValuesAtScopes.erase(ScopeIt);
14693 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14694 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14695 for (
const auto &Pair : ScopeUserIt->second)
14698 llvm::erase_if(ValuesAtScopes[Pair.second], [&](
const auto &LS) {
14699 return LS.first == Pair.first && LS.second.getPointer() == S;
14701 ValuesAtScopesUsers.erase(ScopeUserIt);
14704 auto BEUsersIt = BECountUsers.find(S);
14705 if (BEUsersIt != BECountUsers.end()) {
14707 auto Copy = BEUsersIt->second;
14708 for (
const auto &Pair : Copy)
14709 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14710 BECountUsers.erase(BEUsersIt);
14713 auto FoldUser = FoldCacheUser.find(S);
14714 if (FoldUser != FoldCacheUser.end())
14715 for (
auto &KV : FoldUser->second)
14716 FoldCache.erase(KV);
14717 FoldCacheUser.erase(S);
14721ScalarEvolution::getUsedLoops(
const SCEV *S,
14723 struct FindUsedLoops {
14724 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14725 : LoopsUsed(LoopsUsed) {}
14726 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14727 bool follow(
const SCEV *S) {
14733 bool isDone()
const {
return false; }
14736 FindUsedLoops
F(LoopsUsed);
14737 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14740void ScalarEvolution::getReachableBlocks(
14743 Worklist.
push_back(&F.getEntryBlock());
14744 while (!Worklist.
empty()) {
14746 if (!Reachable.
insert(BB).second)
14754 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14761 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14765 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14800 SCEVMapper SCM(SE2);
14802 SE2.getReachableBlocks(ReachableBlocks, F);
14804 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14822 while (!LoopStack.
empty()) {
14828 if (!ReachableBlocks.
contains(L->getHeader()))
14833 auto It = BackedgeTakenCounts.find(L);
14834 if (It == BackedgeTakenCounts.end())
14838 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14858 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14859 if (Delta && !Delta->
isZero()) {
14860 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14861 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14862 dbgs() <<
"New: " << *NewBECount <<
"\n";
14863 dbgs() <<
"Delta: " << *Delta <<
"\n";
14871 while (!Worklist.
empty()) {
14873 if (ValidLoops.
insert(L).second)
14874 Worklist.
append(L->begin(), L->end());
14876 for (
const auto &KV : ValueExprMap) {
14881 "AddRec references invalid loop");
14886 auto It = ExprValueMap.find(KV.second);
14887 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14888 dbgs() <<
"Value " << *KV.first
14889 <<
" is in ValueExprMap but not in ExprValueMap\n";
14894 if (!ReachableBlocks.
contains(
I->getParent()))
14896 const SCEV *OldSCEV = SCM.visit(KV.second);
14898 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14899 if (Delta && !Delta->
isZero()) {
14900 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14901 <<
"Old: " << *OldSCEV <<
"\n"
14902 <<
"New: " << *NewSCEV <<
"\n"
14903 <<
"Delta: " << *Delta <<
"\n";
14909 for (
const auto &KV : ExprValueMap) {
14910 for (
Value *V : KV.second) {
14911 const SCEV *S = ValueExprMap.lookup(V);
14913 dbgs() <<
"Value " << *V
14914 <<
" is in ExprValueMap but not in ValueExprMap\n";
14917 if (S != KV.first) {
14918 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14919 << *KV.first <<
"\n";
14926 for (
const auto &S : UniqueSCEVs) {
14931 auto It = SCEVUsers.find(
Op);
14932 if (It != SCEVUsers.end() && It->second.count(&S))
14934 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14935 <<
" is not being tracked!\n";
14941 for (
const auto &ValueAndVec : ValuesAtScopes) {
14943 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14944 const Loop *L = LoopAndValueAtScope.first;
14945 SCEVUse ValueAtScope = LoopAndValueAtScope.second;
14947 auto It = ValuesAtScopesUsers.find(ValueAtScope.
getPointer());
14948 if (It != ValuesAtScopesUsers.end() &&
14951 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14952 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14958 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14959 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14960 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14961 const Loop *L = LoopAndValue.first;
14962 const SCEV *
Value = LoopAndValue.second;
14964 auto It = ValuesAtScopes.find(
Value);
14967 if (It != ValuesAtScopes.end() &&
any_of(It->second, [&](
const auto &LS) {
14968 return LS.first == L && LS.second.getPointer() == ValueAtScope;
14971 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14972 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14978 auto VerifyBECountUsers = [&](
bool Predicated) {
14980 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14981 for (
const auto &LoopAndBEInfo : BECounts) {
14982 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14983 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14985 auto UserIt = BECountUsers.find(S);
14986 if (UserIt != BECountUsers.end() &&
14987 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14989 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14990 <<
" missing from BECountUsers\n";
14997 VerifyBECountUsers(
false);
14998 VerifyBECountUsers(
true);
15001 for (
auto &[S,
Values] : LoopDispositions) {
15002 for (
auto [
Loop, CachedDisposition] :
Values) {
15004 if (CachedDisposition != RecomputedDisposition) {
15005 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
15006 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
15007 << RecomputedDisposition <<
"\n";
15014 for (
auto &[S,
Values] : BlockDispositions) {
15015 for (
auto [BB, CachedDisposition] :
Values) {
15017 if (CachedDisposition != RecomputedDisposition) {
15018 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
15019 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
15020 <<
", actual " << RecomputedDisposition <<
"\n";
15027 for (
auto [
FoldID, Expr] : FoldCache) {
15028 auto I = FoldCacheUser.find(Expr);
15029 if (
I == FoldCacheUser.end()) {
15030 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
15035 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
15039 for (
auto [Expr, IDs] : FoldCacheUser) {
15040 for (
auto &
FoldID : IDs) {
15043 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
15048 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
15049 <<
" != " << *Expr <<
"!\n";
15060 for (
auto [S, Multiple] : ConstantMultipleCache) {
15062 if ((Multiple != 0 && RecomputedMultiple != 0 &&
15063 Multiple.
urem(RecomputedMultiple) != 0 &&
15064 RecomputedMultiple.
urem(Multiple) != 0)) {
15065 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
15066 << *S <<
" : Computed " << RecomputedMultiple
15067 <<
" but cache contains " << Multiple <<
"!\n";
15075 FunctionAnalysisManager::Invalidator &Inv) {
15107 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15108 <<
F.getName() <<
"':\n";
15114 "Scalar Evolution Analysis",
false,
true)
15163 const SCEV *LHS,
const SCEV *RHS) {
15165 assert(LHS->getType() == RHS->getType() &&
15166 "Type mismatch between LHS and RHS");
15169 ID.AddInteger(Pred);
15170 ID.AddPointer(LHS);
15171 ID.AddPointer(RHS);
15173 if (
const auto *S = UniquePreds.lookup(ID, Token))
15177 UniquePreds.insert(Eq, Token);
15188 ID.AddInteger(AddedFlags);
15190 if (
const auto *S = UniquePreds.lookup(ID, Token))
15192 auto *OF =
new (SCEVAllocator)
15194 UniquePreds.insert(OF, Token);
15214 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15215 return Rewriter.visit(S);
15221 for (
const auto *Pred : U->getPredicates())
15223 if (IPred->getLHS() == Expr &&
15225 return IPred->getRHS();
15227 if (IPred->getLHS() == Expr &&
15228 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15229 return IPred->getRHS();
15232 return convertToAddRecWithPreds(Expr);
15235 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15251 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15268 explicit SCEVPredicateRewriter(
15269 const Loop *L, ScalarEvolution &SE,
15270 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15271 const SCEVPredicate *Pred)
15272 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15274 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15277 return Pred && Pred->
implies(
P, SE);
15283 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15286 return addOverflowAssumption(
A);
15295 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15299 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15301 if (!PredicatedRewrite)
15303 for (
const auto *
P : PredicatedRewrite->second){
15306 if (L != WP->getExpr()->getLoop())
15309 if (!addOverflowAssumption(
P))
15312 return PredicatedRewrite->first;
15315 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15316 const SCEVPredicate *Pred;
15325 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15332 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15352 if (!Step->
isOne())
15377 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15378 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15391 return Op->LHS == LHS &&
Op->RHS == RHS;
15398 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15400 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15425 const SCEV *Start = AR->getStart();
15426 const SCEV *OpStart =
Op->AR->getStart();
15431 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15440 const SCEV *Step = AR->getStepRecurrence(SE);
15441 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15494 if (Step->getValue()->getValue().isNonNegative())
15498 return ImpliedFlags;
15505 for (
const auto *
P : Preds)
15518 return this->implies(I, SE);
15530 const Loop *L = NWrap->getExpr()->getLoop();
15537 return RewrittenAR &&
15543 for (
const auto *Pred : Preds)
15544 Pred->print(OS,
Depth);
15549 for (
const auto *Pred : Set->Preds)
15557 bool CheckImplies = Preds.
size() < 16;
15560 if (CheckImplies &&
implies(
N, SE))
15566 for (
auto *
P : Preds) {
15567 if (CheckImplies &&
N->implies(
P, SE))
15571 Preds = std::move(PrunedPreds);
15572 Preds.push_back(
N);
15579 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15584 for (
const auto *
Op :
Ops)
15589 SCEVUsers[
Op].insert(
User);
15598 SCEVUsers[
Op].insert(
User);
15602 const SCEV *Expr = SE.getSCEV(V);
15607 RewriteEntry &Entry = RewriteMap[Expr];
15610 if (Entry.second && Generation == Entry.first)
15611 return Entry.second;
15616 Expr = Entry.second;
15618 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15619 Entry = {Generation, NewSCEV};
15625 if (!BackedgeCount) {
15627 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15628 for (
const auto *
P : Preds)
15631 return BackedgeCount;
15635 if (!SymbolicMaxBackedgeCount) {
15637 SymbolicMaxBackedgeCount =
15638 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15639 for (
const auto *
P : Preds)
15642 return SymbolicMaxBackedgeCount;
15646 if (!SmallConstantMaxTripCount) {
15648 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15649 for (
const auto *
P : Preds)
15652 return *SmallConstantMaxTripCount;
15656 if (Preds->implies(&Pred, SE))
15661 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15662 updateGeneration();
15675void PredicatedScalarEvolution::updateGeneration() {
15677 if (++Generation == 0) {
15678 for (
auto &
II : RewriteMap) {
15679 const SCEV *Rewritten =
II.second.second;
15701 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15707 ExtraPreds->
append(NewPreds);
15713 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15719 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15722 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15726 for (
auto *BB : L.getBlocks())
15727 for (
auto &
I : *BB) {
15728 if (!SE.isSCEVable(
I.getType()))
15731 auto *Expr = SE.getSCEV(&
I);
15732 auto II = RewriteMap.find(Expr);
15734 if (
II == RewriteMap.end())
15738 if (
II->second.second == Expr)
15743 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15751 LoopGuards Guards(SE);
15759void ScalarEvolution::LoopGuards::collectFromPHI(
15767 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15768 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15782 auto &RewriteMap =
G->second.RewriteMap;
15783 if (RewriteMap.empty())
15785 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15786 if (S == RewriteMap.end())
15792 return {C0, SM->getSCEVType()};
15795 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15796 MinMaxPattern
P2) -> MinMaxPattern {
15797 auto [C1,
T1] =
P1;
15798 auto [C2, T2] =
P2;
15799 if (!C1 || !C2 ||
T1 != T2)
15803 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15805 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15807 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15809 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15814 auto P = GetMinMaxConst(0);
15815 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15818 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15821 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15824 Guards.RewriteMap.insert({
LHS,
RHS});
15832 const APInt &DivisorVal,
15834 const APInt *ExprVal;
15847 const APInt &DivisorVal,
15849 const APInt *ExprVal;
15857 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15871 const SCEV *URemRHS =
nullptr;
15875 const SCEV *Multiple =
15877 DivInfo[URemLHS] = Multiple;
15879 Multiples[URemLHS] =
C->getAPInt();
15899 auto IsMinMaxSCEVWithNonNegativeConstant =
15903 if (
MinMax->getNumOperands() != 2)
15906 if (
C->getAPInt().isNegative())
15908 SCTy =
MinMax->getSCEVType();
15917 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15919 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15924 auto *DivisibleExpr =
15932void ScalarEvolution::LoopGuards::collectFromBlock(
15934 const BasicBlock *
Block,
const BasicBlock *Pred,
15942 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15953 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15955 if (From == FromRewritten)
15957 RewriteMap[From] = To;
15963 auto GetMaybeRewritten = [&](
const SCEV *S) {
15964 return RewriteMap.lookup_or(S, S);
15971 const SCEV *MatchLHS,
15972 const SCEV *MatchRHS) {
15973 const SCEVConstant *C1;
15976 if (!
match(MatchLHS,
15988 const SCEV *RewrittenLHS = GetMaybeRewritten(LHSUnknown);
15989 ExactRegion = ExactRegion.intersectWith(SE.
getUnsignedRange(RewrittenLHS),
15994 if (ExactRegion.isEmptySet() || ExactRegion.isWrappedSet() ||
15995 ExactRegion.isFullSet())
15998 const SCEV *RegionMin = SE.
getConstant(ExactRegion.getUnsignedMin());
15999 const SCEV *RegionMax = SE.
getConstant(ExactRegion.getUnsignedMax());
16000 const SCEV *ClampedLHS =
16002 AddRewrite(LHSUnknown, RewrittenLHS, ClampedLHS);
16005 if (MatchRangeCheckIdiom(Predicate,
LHS,
RHS))
16018 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
16020 const APInt &DividesBy =
16035 switch (Predicate) {
16064 SmallPtrSet<const SCEV *, 16> Visited;
16066 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
16070 while (!Worklist.
empty()) {
16074 if (!Visited.
insert(From).second)
16076 const SCEV *FromRewritten = GetMaybeRewritten(From);
16077 const SCEV *To =
nullptr;
16079 switch (Predicate) {
16084 EnqueueOperands(
UMax);
16090 EnqueueOperands(
SMax);
16096 EnqueueOperands(
UMin);
16102 EnqueueOperands(
SMin);
16110 const SCEV *OneAlignedUp =
16112 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16124 const SCEVConstant *
C;
16133 Guards.NotEqual.insert({
LHS,
RHS});
16142 AddRewrite(From, FromRewritten, To);
16159 SE.F.
getParent(), Intrinsic::experimental_guard);
16161 for (
const auto *GU : GuardDecl->users())
16163 if (Guard->getFunction() ==
Block->getParent() &&
16172 unsigned NumCollectedConditions = 0;
16174 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16176 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16178 const CondBrInst *LoopEntryPredicate =
16180 if (!LoopEntryPredicate)
16185 NumCollectedConditions++;
16189 if (
Depth > 0 && NumCollectedConditions == 2)
16197 if (Pair.second->hasNPredecessorsOrMore(2) &&
16199 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16200 for (
auto &Phi : Pair.second->phis())
16211 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16212 SmallVector<Value *, 8> Worklist;
16213 SmallPtrSet<Value *, 8> Visited;
16215 while (!Worklist.
empty()) {
16222 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16246 DenseMap<const SCEV *, APInt> Multiples;
16248 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16255 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16256 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16260 for (
const auto &[K, Divisor] : Multiples) {
16261 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16262 Guards.RewriteMap[
K] =
16264 Guards.
rewrite(K), Divisor, SE),
16273 Guards.PreserveNUW =
true;
16274 Guards.PreserveNSW =
true;
16275 for (
const SCEV *Expr : ExprsToRewrite) {
16276 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16277 Guards.PreserveNUW &=
16279 Guards.PreserveNSW &=
16286 if (ExprsToRewrite.size() > 1) {
16287 for (
const SCEV *Expr : ExprsToRewrite) {
16288 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16289 Guards.RewriteMap.erase(Expr);
16290 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16299 class SCEVLoopGuardRewriter
16310 NotEqual(Guards.NotEqual) {
16311 if (Guards.PreserveNUW)
16313 if (Guards.PreserveNSW)
16320 return Map.lookup_or(Expr, Expr);
16324 if (
const SCEV *S = Map.lookup(Expr))
16331 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16332 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16333 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16335 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16336 if (
const SCEV *S = Map.lookup(NarrowExt))
16337 return SE.getZeroExtendExpr(S, Ty);
16338 Bitwidth = Bitwidth / 2;
16346 if (
const SCEV *S = Map.lookup(Expr))
16353 if (
const SCEV *S = Map.lookup(Expr))
16359 if (
const SCEV *S = Map.lookup(Expr))
16365 if (
const SCEV *S = Map.lookup(Expr))
16370 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16375 if (NotEqual.contains({LHS, RHS})) {
16377 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16378 return SE.getUMaxExpr(OneAlignedUp, S);
16385 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16396 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16397 return SE.getAddExpr(
16400 if (
const SCEV *S = Map.lookup(
Add))
16401 return SE.getAddExpr(Expr->
getOperand(0), S);
16409 const SCEV *S =
nullptr;
16416 S = Map.lookup(SE.getAddExpr(NewC, Expr->
getOperand(1)));
16419 return SE.getAddExpr(S, SE.getMinusOne(Expr->
getType()));
16454 if (RewriteMap.empty() && NotEqual.empty())
16457 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16458 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 bool CanConstantFold(const Instruction *I)
Return true if we can constant fold an instruction of the specified type, assuming that all operands ...
static cl::opt< unsigned > AddOpsInlineThreshold("scev-addops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining addition operands into a SCEV"), cl::init(500))
static cl::opt< unsigned > MaxLoopGuardCollectionDepth("scalar-evolution-max-loop-guard-collection-depth", cl::Hidden, cl::desc("Maximum depth for recursive loop guard collection"), cl::init(1))
static cl::opt< bool > VerifyIR("scev-verify-ir", cl::Hidden, cl::desc("Verify IR correctness when making sensitive SCEV queries (slow)"), cl::init(false))
static bool RangeRefPHIAllowedOperands(DominatorTree &DT, PHINode *PHI)
static 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 cl::opt< unsigned > MulOpsInlineThreshold("scev-mulops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining multiplication operands into a SCEV"), cl::init(32))
static BinaryOperator * getCommonInstForPHI(PHINode *PN)
static bool isDivisibilityGuard(const SCEV *LHS, const SCEV *RHS, ScalarEvolution &SE)
static std::optional< const SCEV * > createNodeForSelectViaUMinSeq(ScalarEvolution *SE, const SCEV *CondExpr, const SCEV *TrueExpr, const SCEV *FalseExpr)
static Constant * BuildConstantFromSCEV(const SCEV *V)
This builds up a Constant using the ConstantExpr interface.
static ConstantInt * EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C, ScalarEvolution &SE)
static const SCEV * BinomialCoefficient(const SCEV *It, unsigned K, ScalarEvolution &SE, Type *ResultTy)
Compute BC(It, K). The result has width W. Assume, K > 0.
static cl::opt< unsigned > MaxCastDepth("scalar-evolution-max-cast-depth", cl::Hidden, cl::desc("Maximum depth of recursive SExt/ZExt/Trunc"), cl::init(8))
static bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr, const SCEV *Candidate)
Is MaybeMinMaxExpr an (U|S)(Min|Max) of Candidate and some other values?
static PHINode * getConstantEvolvingPHI(Value *V, const Loop *L)
getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node in the loop that V is deri...
static const SCEV * SolveLinEquationWithOverflow(const APInt &A, const SCEV *B, SmallVectorImpl< const SCEVPredicate * > *Predicates, ScalarEvolution &SE, const Loop *L)
Finds the minimum unsigned root of the following equation:
static cl::opt< unsigned > MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, cl::desc("Maximum number of iterations SCEV will " "symbolically execute a constant " "derived loop"), cl::init(100))
static uint64_t umul_ov(uint64_t i, uint64_t j, bool &Overflow)
static void PrintSCEVWithTypeHint(raw_ostream &OS, const SCEV *S)
When printing a top-level SCEV for trip counts, it's helpful to include a type for constants which ar...
static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE, const Loop *L)
static SCEV::NoWrapFlags StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, ArrayRef< SCEVUse > Ops, SCEV::NoWrapFlags Flags)
static bool containsConstantInAddMulChain(const SCEV *StartExpr)
Determine if any of the operands in this SCEV are a constant or if any of the add or multiply express...
static const SCEV * getExtendAddRecStart(const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE, unsigned Depth)
static bool CollectAddOperandsWithScales(SmallDenseMap< SCEVUse, APInt, 16 > &M, SmallVectorImpl< SCEVUse > &NewOps, APInt &AccumulatedConstant, ArrayRef< SCEVUse > Ops, const APInt &Scale, ScalarEvolution &SE)
Process the given Ops list, which is a list of operands to be added under the given scale,...
static const SCEV * constantFoldAndGroupOps(ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT, SmallVectorImpl< SCEVUse > &Ops, FoldT Fold, IsIdentityT IsIdentity, IsAbsorberT IsAbsorber)
Performs a number of common optimizations on the passed Ops.
static 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 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 canConstantEvolve(Instruction *I, const Loop *L)
Determine whether this instruction can constant evolve within this loop assuming its operands can all...
static PHINode * getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L, DenseMap< Instruction *, PHINode * > &PHIMap, unsigned Depth)
getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by recursing through each instructi...
static bool scevUnconditionallyPropagatesPoisonFromOperands(SCEVTypes Kind)
static cl::opt< bool > VerifySCEVStrict("verify-scev-strict", cl::Hidden, cl::desc("Enable stricter verification with -verify-scev is passed"))
static Constant * getOtherIncomingValue(PHINode *PN, BasicBlock *BB)
static cl::opt< bool > UseExpensiveRangeSharpening("scalar-evolution-use-expensive-range-sharpening", cl::Hidden, cl::init(false), cl::desc("Use more powerful methods of sharpening expression ranges. May " "be costly in terms of compile time"))
static const SCEV * getUnsignedOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static bool IsKnownPredicateViaMinOrMax(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Is LHS Pred RHS true on the virtue of LHS or RHS being a Min or Max expression?
static bool BrPHIToSelect(DominatorTree &DT, CondBrInst *BI, PHINode *Merge, Value *&C, Value *&LHS, Value *&RHS)
This file defines the 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 const SCEV * getConstant(ConstantInt *V)
LLVM_ABI const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
LLVM_ABI const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
LLVM_ABI const SCEV * getAddRecExpr(SCEVUse Start, SCEVUse Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
LLVM_ABI const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
static LLVM_ABI bool isGuaranteedNotToBePoison(const SCEV *Op)
Returns true if Op is guaranteed to not be poison.
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
LLVM_ABI const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
LLVM_ABI ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI)
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LLVM_ABI const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI const SCEV * 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 void registerUser(const SCEV *User, ArrayRef< const SCEV * > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
LLVM_ABI bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the basic block is protected by a conditional between LHS and RHS.
LLVM_ABI const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool containsErasedValue(const SCEV *S) const
Return true if the SCEV expression contains a Value that has been optimised out and is now a nullptr.
const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
LLVM_ABI void verify() const
LLVMContext & getContext() const
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.
LLVM_ABI bool canConstantFoldCallTo(const CallBase *Call, const Function *F)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
InterleavedRange< Range > interleaved(const Range &R, StringRef Separator=", ", StringRef Prefix="", StringRef Suffix="")
Output range R as a sequence of interleaved elements.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
auto successors(const MachineBasicBlock *BB)
scope_exit(Callable) -> scope_exit< Callable >
@ BinaryOp
One of the operands is a binary op.
@ Load
The value being inserted comes from a load (InsertElement only).
@ Store
The extracted value is stored (ExtractElement only).
constexpr from_range_t from_range
auto dyn_cast_if_present(const Y &Val)
dyn_cast_if_present<X> - Functionally identical to dyn_cast, except that a null (or none in the case ...
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
auto uninitialized_copy(R &&Src, IterTy Dst)
bool isa_and_nonnull(const Y &Val)
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO, const DominatorTree &DT)
Returns true if the arithmetic part of the WO 's result is used only along the paths control dependen...
DomTreeNodeBase< BasicBlock > DomTreeNode
LLVM_ABI bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step)
Attempt to match a simple first order recurrence cycle of the form: iv = phi Ty [Start,...
auto dyn_cast_or_null(const Y &Val)
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
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