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-operations-implication-depth",
cl::Hidden,
184 cl::desc(
"Maximum depth of recursive SCEV operations implication analysis"),
188 "scalar-evolution-max-value-compare-depth",
cl::Hidden,
189 cl::desc(
"Maximum depth of recursive value complexity comparisons"),
194 cl::desc(
"Maximum depth of recursive arithmetics"),
198 "scalar-evolution-max-constant-evolving-depth",
cl::Hidden,
203 cl::desc(
"Maximum depth of recursive SExt/ZExt/Trunc"),
208 cl::desc(
"Max coefficients in AddRec during evolving"),
213 cl::desc(
"Size of the expression which is considered huge"),
218 cl::desc(
"Threshold for switching to iteratively computing SCEV ranges"),
222 "scalar-evolution-max-loop-guard-collection-depth",
cl::Hidden,
223 cl::desc(
"Maximum depth for recursive loop guard collection"),
cl::init(1));
226 "scalar-evolution-max-guard-dom-tree-steps",
cl::Hidden,
227 cl::desc(
"Maximum number of immediate dominator steps taken when "
228 "collecting loop guards"),
234 cl::desc(
"When printing analysis, include information on every instruction"));
237 "scalar-evolution-use-expensive-range-sharpening",
cl::Hidden,
239 cl::desc(
"Use more powerful methods of sharpening expression ranges. May "
240 "be costly in terms of compile time"));
244 cl::desc(
"Handle <= and >= in finite loops"),
248 "scalar-evolution-use-context-for-no-wrap-flag-strenghening",
cl::Hidden,
249 cl::desc(
"Infer nuw/nsw flags using context where suitable"),
286#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
304 OS <<
"(ptrtoaddr " << *
Op->getType() <<
" " <<
Op <<
" to "
311 OS <<
"(trunc " << *
Op->getType() <<
" " <<
Op <<
" to "
318 OS <<
"(zext " << *
Op->getType() <<
" " <<
Op <<
" to " << *ZExt->
getType()
325 OS <<
"(sext " << *
Op->getType() <<
" " <<
Op <<
" to " << *SExt->
getType()
354 const char *OpStr =
nullptr;
367 OpStr =
" umin_seq ";
389 OS <<
"(" << UDiv->
getLHS() <<
" /u " << UDiv->
getRHS() <<
")";
396 OS <<
"***COULDNOTCOMPUTE***";
438 if (!
Mul)
return false;
442 if (!SC)
return false;
456 auto &Entry = ConstantSCEVs[V];
465 static_cast<SCEVConstant *
>(UniqueSCEVs.lookup(ID, Token)))
468 new (SCEVAllocator)
SCEVConstant(ID.Intern(SCEVAllocator), V);
469 UniqueSCEVs.insert(S, Token);
484 ConstantInt::get(ITy, V,
isSigned,
true));
492 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
494 SCEV *S =
new (SCEVAllocator)
SCEVVScale(ID.Intern(SCEVAllocator), Ty);
495 UniqueSCEVs.insert(S, Token);
516 "Must be a non-bit-width-changing pointer-to-integer cast!");
528 "Cannot truncate non-integer value!");
535 "Cannot zero extend non-integer value!");
542 "Cannot sign extend non-integer value!");
547 SE->forgetMemoizedResults({
this});
550 SE->UniqueSCEVs.erase(
this);
556void SCEVUnknown::allUsesReplacedWith(
Value *New) {
558 SE->forgetMemoizedResults({
this});
561 SE->UniqueSCEVs.erase(
this);
583 if (LIsPointer != RIsPointer)
584 return (
int)LIsPointer - (int)RIsPointer;
589 return (
int)LID - (int)RID;
594 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
595 return (
int)LArgNo - (int)RArgNo;
601 if (
auto L = LGV->getLinkage() - RGV->getLinkage())
604 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
605 auto LT = GV->getLinkage();
612 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
613 return LGV->getName().compare(RGV->getName());
624 if (LParent != RParent) {
627 if (LDepth != RDepth)
628 return (
int)LDepth - (int)RDepth;
632 unsigned LNumOps = LInst->getNumOperands(),
633 RNumOps = RInst->getNumOperands();
634 if (LNumOps != RNumOps)
635 return (
int)LNumOps - (int)RNumOps;
637 for (
unsigned Idx :
seq(LNumOps)) {
639 RInst->getOperand(Idx),
Depth + 1);
657 if (
LHS.getPointer() ==
RHS.getPointer())
658 return (
int)
LHS.getUseNoWrapFlags() - (int)
RHS.getUseNoWrapFlags();
663 return (
int)LType - (int)RType;
686 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
687 if (LBitWidth != RBitWidth)
688 return (
int)LBitWidth - (int)RBitWidth;
689 return LA.
ult(
RA) ? -1 : 1;
695 return LTy->getBitWidth() - RTy->getBitWidth();
706 if (LLoop != RLoop) {
708 assert(LHead != RHead &&
"Two loops share the same header?");
712 "No dominance between recurrences used by one SCEV?");
735 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
736 if (LNumOps != RNumOps)
737 return (
int)LNumOps - (int)RNumOps;
739 for (
unsigned i = 0; i != LNumOps; ++i) {
748 assert(LBitWidth != RBitWidth &&
"distinct SCEVs compare equal");
749 return (
int)LBitWidth - (int)RBitWidth;
769 if (
Ops.size() < 2)
return;
775 if (
Ops.size() == 2) {
779 if (IsLessComplex(
RHS,
LHS))
803template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
807 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
809 for (
unsigned Idx = 0; Idx <
Ops.size();) {
817 Ops.erase(
Ops.begin() + Idx);
835 return Ops.size() == 1 ?
Ops[0] :
nullptr;
910 APInt OddFactorial(W, 1);
912 for (
unsigned i = 3; i <=
K; ++i) {
915 OddFactorial *= (i >> TwoFactors);
919 unsigned CalculationBits = W +
T;
933 for (
unsigned i = 1; i !=
K; ++i) {
966 "use-specific flags only supported for affine AddRecs");
968 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1009 ConversionFn CreatePtrCast;
1013 ConversionFn CreatePtrCast)
1014 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
1017 Type *TargetTy, ConversionFn CreatePtrCast) {
1019 return Rewriter.visit(Scev);
1045 "Should only reach pointer-typed SCEVUnknown's.");
1050 return SE.getZero(TargetTy);
1051 return CreatePtrCast(Expr);
1056 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1060 if (DL.hasUnstableRepresentation(
Op->getType()))
1063 Type *Ty = DL.getAddressType(
Op->getType());
1074 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1076 SCEV *S =
new (SCEVAllocator)
1078 UniqueSCEVs.insert(S, Token);
1081 return static_cast<const SCEV *
>(S);
1084 "We must have succeeded in sinking the cast, "
1085 "and ending up with an integer-typed expression!");
1092 "This is not a truncating conversion!");
1094 "This is not a conversion to a SCEVable type!");
1095 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1100 ID.AddPointer(
Op.getOpaqueValue());
1103 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1126 UniqueSCEVs.insert(S, Token);
1139 unsigned numTruncs = 0;
1140 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1148 if (numTruncs < 2) {
1158 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1165 for (
const SCEV *
Op : AddRec->operands())
1180 UniqueSCEVs.insert(S, Token);
1221struct ExtendOpTraitsBase {
1222 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
SCEVUse,
Type *,
1227template <
typename ExtendOp>
struct ExtendOpTraits {
1243 static const GetExtendExprTy GetExtendExpr;
1245 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1246 ICmpInst::Predicate *Pred,
1247 ScalarEvolution *SE) {
1252const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1259 static const GetExtendExprTy GetExtendExpr;
1261 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1262 ICmpInst::Predicate *Pred,
1263 ScalarEvolution *SE) {
1268const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1280template <
typename ExtendOpTy>
1283 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1284 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1300 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1313 auto PreStartFlags =
1331 const SCEV *OperandExtendedStart =
1333 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1334 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1346 const SCEV *OverflowLimit =
1347 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1349 if (OverflowLimit &&
1357template <
typename ExtendOpTy>
1361 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1369 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1404template <
typename ExtendOpTy>
1405bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1408 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1418 APInt StartAI = StartC->
getAPInt();
1420 for (
unsigned Delta : {-2, -1, 1, 2}) {
1421 const SCEV *PreStart =
getConstant(StartAI - Delta);
1422 const auto *PreAR =
static_cast<SCEVAddRecExpr *
>(
1423 findExistingSCEVInCache(
scAddRecExpr, {PreStart, Step},
L));
1427 if (PreAR &&
any(PreAR->getNoWrapFlags(WrapType))) {
1430 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1431 DeltaS, &Pred,
this);
1449 const unsigned BitWidth =
C.getBitWidth();
1467 const APInt &ConstantStart,
1482 auto I = FoldCache.
insert({ID, S});
1486 auto &UserIDs = FoldCacheUser[
I.first->second];
1487 assert(
count(UserIDs, ID) == 1 &&
"unexpected duplicates in UserIDs");
1488 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1489 if (UserIDs[
I] == ID) {
1494 I.first->second = S;
1496 FoldCacheUser[S].push_back(ID);
1502 "This is not an extending conversion!");
1504 "This is not a conversion to a SCEVable type!");
1505 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1509 if (
const SCEV *S = FoldCache.lookup(ID))
1521 "This is not an extending conversion!");
1523 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1535 const SCEV *Start, *Step;
1540 if (AR->hasNoUnsignedWrap()) {
1551 ID.AddPointer(
Op.getOpaqueValue());
1554 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1559 UniqueSCEVs.insert(S, Token);
1569 const SCEV *
X = ST->getOperand();
1602 const SCEV *CastedMaxBECount =
1606 if (MaxBECount == RecastedMaxBECount) {
1615 const SCEV *WideMaxBECount =
1617 const SCEV *OperandExtendedAdd =
1623 if (ZAdd == OperandExtendedAdd) {
1634 OperandExtendedAdd =
1640 if (ZAdd == OperandExtendedAdd) {
1661 !AC.assumptions().empty()) {
1663 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1665 if (AR->hasNoUnsignedWrap()) {
1700 const APInt &
C = SC->getAPInt();
1704 const SCEV *SResidual =
1712 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1736 if (SA->hasNoUnsignedWrap()) {
1749 if (SA->hasNoSignedWrap() &&
1752 C->isNegative() && !
C->isMinSignedValue() && C2->
sge(
C->abs())) {
1771 const SCEV *SResidual =
1782 if (SM->hasNoUnsignedWrap()) {
1804 const SCEV *TruncRHS;
1841 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1845 UniqueSCEVs.insert(S, Token);
1854 "This is not an extending conversion!");
1856 "This is not a conversion to a SCEVable type!");
1857 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1861 if (
const SCEV *S = FoldCache.lookup(ID))
1873 "This is not an extending conversion!");
1875 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1892 const SCEV *Start, *Step;
1897 if (AR->hasNoSignedWrap()) {
1908 ID.AddPointer(
Op.getOpaqueValue());
1911 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1917 UniqueSCEVs.insert(S, Token);
1927 const SCEV *
X = ST->getOperand();
1938 if (SA->hasNoSignedWrap()) {
1960 const SCEV *SResidual =
1993 const SCEV *CastedMaxBECount =
1997 if (MaxBECount == RecastedMaxBECount) {
2006 const SCEV *WideMaxBECount =
2008 const SCEV *OperandExtendedAdd =
2014 if (SAdd == OperandExtendedAdd) {
2025 OperandExtendedAdd =
2031 if (SAdd == OperandExtendedAdd) {
2051 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2053 if (AR->hasNoSignedWrap()) {
2067 const APInt &
C = SC->getAPInt();
2071 const SCEV *SResidual =
2079 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2106 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
2110 UniqueSCEVs.insert(S, Token);
2126 assert(Expr->
getType() == Ty &&
"requested type must match");
2138 "This is not an extending conversion!");
2140 "This is not a conversion to a SCEVable type!");
2145 if (SC->getAPInt().isNegative())
2150 const SCEV *NewOp =
T->getOperand();
2169 for (
const SCEV *
Op : AR->operands())
2210 bool Interesting =
false;
2217 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2219 AccumulatedConstant += Scale *
C->getAPInt();
2224 for (; i !=
Ops.size(); ++i) {
2233 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2239 auto Pair = M.insert({
Key, NewScale});
2243 Pair.first->second += NewScale;
2251 auto Pair = M.insert({
Ops[i]->getCanonical(), Scale});
2255 Pair.first->second += Scale;
2273 case Instruction::Add:
2275 case Instruction::Sub:
2277 case Instruction::Mul:
2291 const SCEV *
A = (this->*Extension)(
Operation(LHS, RHS), WideTy, 0);
2292 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2293 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2301 if (BinOp == Instruction::Mul)
2307 APInt C = RHSC->getAPInt();
2308 unsigned NumBits =
C.getBitWidth();
2309 bool IsSub = (BinOp == Instruction::Sub);
2310 bool IsNegativeConst = (
Signed &&
C.isNegative());
2312 bool OverflowDown = IsSub ^ IsNegativeConst;
2314 if (IsNegativeConst) {
2327 APInt Limit = Min + Magnitude;
2333 APInt Limit = Max - Magnitude;
2342 return std::nullopt;
2351 bool Deduced =
false;
2357 bool CanUseNSW =
true;
2358 const APInt *ShiftAmt;
2363 return std::nullopt;
2367 Opcode = Instruction::Mul;
2369 }
else if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
2370 Opcode != Instruction::Mul) {
2371 return std::nullopt;
2390 return std::nullopt;
2398 using namespace std::placeholders;
2405 assert(CanAnalyze &&
"don't call from other places!");
2412 auto IsKnownNonNegative = [&](
SCEVUse U) {
2421 if (SignOrUnsignWrap != SignOrUnsignMask &&
2428 return Instruction::Add;
2430 return Instruction::Mul;
2459 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2466 if (UDiv->getOperand(1) ==
Ops[1])
2469 if (UDiv->getOperand(1) ==
Ops[0])
2486 "only nuw or nsw allowed");
2488 "only nuw or nsw allowed");
2489 assert(!
Ops.empty() &&
"Cannot get empty add!");
2490 if (
Ops.size() == 1)
return Ops[0];
2493 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2495 "SCEVAddExpr operand types don't match!");
2497 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2498 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2504 [](
const APInt &
C) {
return C.isZero(); },
2505 [](
const APInt &
C) {
return false; });
2524 return {getOrCreateAddExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
2529 if (
Add->getNoWrapFlags(ExprFlags) != ExprFlags)
2530 Add->setNoWrapFlags(ComputeFlags(
Ops));
2531 return {S, UseFlags};
2538 bool FoundMatch =
false;
2539 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2557 --i; e -=
Count - 1;
2567 auto FindTruncSrcType = [&]() ->
Type * {
2573 return T->getOperand()->getType();
2575 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2577 return T->getOperand()->getType();
2581 if (
auto *SrcType = FindTruncSrcType()) {
2588 if (
T->getOperand()->getType() != SrcType) {
2597 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2600 if (
T->getOperand()->getType() != SrcType) {
2629 if (
Ops.size() == 2) {
2639 auto C2 =
C->getAPInt();
2643 auto AddFlags = AddExpr->getNoWrapFlags();
2684 if (
Ops.size() == 2 &&
2695 if (Idx <
Ops.size()) {
2696 bool DeletedAdd =
false;
2707 Ops.erase(
Ops.begin()+Idx);
2710 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2733 struct APIntCompare {
2734 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2735 return LHS.ult(RHS);
2742 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2744 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2747 if (AccumulatedConstant != 0)
2749 for (
auto &MulOp : MulOpLists) {
2750 if (MulOp.first == 1) {
2752 }
else if (MulOp.first != 0) {
2761 if (
Ops.size() == 1)
2770 if (M->getNumOperands() == 2)
2771 return M->getOperand(OpIdx == 0);
2773 append_range(Remaining, M->operands().drop_front(OpIdx + 1));
2782 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2794 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp) {
2807 for (
unsigned OMulOp = 0, OE = OtherMul->
getNumOperands(); OMulOp != OE;
2813 Cofactors.
push_back(StripFactor(OtherMul, OMulOp));
2822 if (!Cofactors.
empty()) {
2830 if (
Ops.size() == DeadIndices.
size() + 1)
2837 Ops.erase(
Ops.begin() + Idx);
2841 Ops.push_back(OuterMul);
2860 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2863 Ops.erase(
Ops.begin()+i);
2868 if (!LIOps.
empty()) {
2893 auto *DefI = getDefiningScopeBound(LIOps);
2895 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2907 if (
Ops.size() == 1)
return NewRec;
2910 for (
unsigned i = 0;; ++i)
2911 if (
Ops[i] == AddRec) {
2921 for (
unsigned OtherIdx = Idx+1;
2929 "AddRecExprs are not sorted in reverse dominance order?");
2936 if (OtherAddRec->getLoop() == AddRecLoop) {
2937 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2939 if (i >= AddRecOps.
size()) {
2940 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2944 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
2947 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
2963 "Tried to add SCEVUse flags after operands changed");
2964 return {getOrCreateAddExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
2972 ID.AddPointer(
Op.getOpaqueValue());
2978 S =
new (SCEVAllocator)
2980 UniqueSCEVs.insert(S, Token);
2991 FoldingSetNodeID
ID;
2994 ID.AddPointer(
Op.getOpaqueValue());
2996 FoldingSetInsertToken Token;
2998 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.lookup(ID, Token));
3002 S =
new (SCEVAllocator)
3003 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3004 UniqueSCEVs.insert(S, Token);
3006 LoopUsers[
L].push_back(S);
3015 FoldingSetNodeID
ID;
3018 ID.AddPointer(
Op.getOpaqueValue());
3019 FoldingSetInsertToken Token;
3020 SCEVMulExpr *S =
static_cast<SCEVMulExpr *
>(UniqueSCEVs.lookup(ID, Token));
3024 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3026 UniqueSCEVs.insert(S, Token);
3035 FoldingSetNodeID
ID;
3037 ID.AddPointer(
LHS.getOpaqueValue());
3038 ID.AddPointer(
RHS.getOpaqueValue());
3039 FoldingSetInsertToken Token;
3040 SCEV *S = UniqueSCEVs.lookup(ID, Token);
3042 S =
new (SCEVAllocator) SCEVUDivExpr(
ID.Intern(SCEVAllocator),
LHS,
RHS);
3043 UniqueSCEVs.insert(S, Token);
3052 if (j > 1 && k / j != i) Overflow =
true;
3068 if (n == 0 || n == k)
return 1;
3069 if (k > n)
return 0;
3075 for (
uint64_t i = 1; i <= k; ++i) {
3076 r =
umul_ov(r, n-(i-1), Overflow);
3085 struct FindConstantInAddMulChain {
3086 bool FoundConstant =
false;
3088 bool follow(
const SCEV *S) {
3093 bool isDone()
const {
3094 return FoundConstant;
3098 FindConstantInAddMulChain
F;
3100 ST.visitAll(StartExpr);
3101 return F.FoundConstant;
3110 "only nuw or nsw allowed");
3112 "only nuw or nsw allowed");
3113 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3114 if (
Ops.size() == 1)
return Ops[0];
3116 Type *ETy =
Ops[0]->getType();
3118 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3120 "SCEVMulExpr operand types don't match!");
3126 [](
const APInt &
C) {
return C.isOne(); },
3127 [](
const APInt &
C) {
return C.isZero(); });
3144 return {getOrCreateMulExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
3149 if (
Mul->getNoWrapFlags(ExprFlags) != ExprFlags)
3150 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3151 return {S, UseFlags};
3155 if (
Ops.size() == 2) {
3163 const SCEV *Op0, *Op1;
3171 if (
Ops[0]->isAllOnesValue()) {
3176 bool AnyFolded =
false;
3177 for (
const SCEV *AddOp :
Add->operands()) {
3197 if (AddRec->hasNoSignedWrap()) {
3228 APInt C1V = LHSC->getAPInt();
3238 const SCEV *NewMul =
nullptr;
3242 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3257 if (Idx <
Ops.size()) {
3258 bool DeletedMul =
false;
3264 Ops.erase(
Ops.begin()+Idx);
3288 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3291 Ops.erase(
Ops.begin()+i);
3296 if (!LIOps.
empty()) {
3308 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3324 if (
Ops.size() == 1)
return NewRec;
3327 for (
unsigned i = 0;; ++i)
3328 if (
Ops[i] == AddRec) {
3349 bool OpsModified =
false;
3350 for (
unsigned OtherIdx = Idx+1;
3364 bool Overflow =
false;
3371 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3372 uint64_t Coeff1 =
Choose(x, 2*x - y, Overflow);
3375 z < ze && !Overflow; ++z) {
3376 uint64_t Coeff2 =
Choose(2*x - y, x-z, Overflow);
3378 if (LargerThan64Bits)
3379 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3381 Coeff = Coeff1*Coeff2;
3394 const SCEV *NewAddRec =
3396 if (
Ops.size() == 2)
return NewAddRec;
3397 Ops[Idx] = NewAddRec;
3398 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3415 "Tried to add SCEVUse flags after operands changed");
3416 return {getOrCreateMulExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
3423 "SCEVURemExpr operand types don't match!");
3428 if (RHSC->getValue()->isOne())
3429 return getZero(LHS->getType());
3432 if (RHSC->getAPInt().isPowerOf2()) {
3433 Type *FullTy = LHS->getType();
3449 assert(!LHS->getType()->isPointerTy() &&
3450 "SCEVUDivExpr operand can't be pointer!");
3451 assert(LHS->getType() == RHS->getType() &&
3452 "SCEVUDivExpr operand types don't match!");
3462 if (RHSC->getValue()->isOne())
3467 if (!RHSC->getValue()->isZero()) {
3471 Type *Ty = LHS->getType();
3472 unsigned LZ = RHSC->getAPInt().countl_zero();
3476 if (!RHSC->getAPInt().isPowerOf2())
3484 const APInt &StepInt = Step->getAPInt();
3485 const APInt &DivInt = RHSC->getAPInt();
3486 if (!StepInt.
urem(DivInt) &&
3492 for (
const SCEV *
Op : AR->operands())
3498 const APInt *StartRem;
3511 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3515 const SCEV *NewStart =
3517 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3519 const SCEV *NewLHS =
3529 if (M->hasNoUnsignedWrap()) {
3531 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3532 const SCEV *
Op = M->getOperand(i);
3559 if (
auto *DivisorConstant =
3561 bool Overflow =
false;
3563 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3574 if (
A->hasNoUnsignedWrap()) {
3576 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3583 if (
Operands.size() ==
A->getNumOperands())
3595 const APInt &
N = RHSC->getAPInt();
3596 const APInt *NMinusM, *M;
3600 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3601 *NMinusM ==
N - *M) {
3610 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3620 return getZero(LHS->getType());
3624 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3625 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3626 if (
Mul->getOperand(i) == RHS) {
3637 const SCEV *NewLHS, *NewRHS;
3642 return getOrCreateUDivExpr(LHS, RHS);
3661 if (StepChrec->getLoop() == L) {
3680 "only nuw or nsw allowed");
3686 "SCEVAddRecExpr operand types don't match!");
3687 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3691 "SCEVAddRecExpr operand is not available at loop entry!");
3713 const Loop *NestedLoop = NestedAR->getLoop();
3714 if (L->contains(NestedLoop)
3717 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3719 Operands[0] = NestedAR->getStart();
3723 bool AllInvariant =
all_of(
3735 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3746 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3757 "Tried to add SCEVUse flags after operands changed");
3758 return {getOrCreateAddRecExpr(
Operands, L, ExprFlags), UseFlags};
3775 if (!GEPI || !isSCEVExprNeverPoison(GEPI)) {
3777 }
else if (
any_of(IndexExprs, [&](
const SCEVUse &IndexExpr) {
3778 const SCEV *Idx = IndexExpr;
3780 !isGuaranteedToTransferExecutionTo(
3781 getDefiningScopeBound({Idx}), GEPI);
3791 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), BaseNW,
3808 bool FirstIter =
true;
3810 for (
SCEVUse IndexExpr : IndexExprs) {
3817 Offsets.push_back(FieldOffset);
3820 CurTy = STy->getTypeAtIndex(Index);
3825 "The first index of a GEP indexes a pointer");
3826 CurTy = SrcElementTy;
3837 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3838 Offsets.push_back(LocalOffset);
3843 if (Offsets.empty())
3856 "GEP should not change type mid-flight.");
3860SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3864 "L must be passed to find existing AddRecs");
3868 ID.AddPointer(
Op.getOpaqueValue());
3872 return UniqueSCEVs.lookup(ID, Token);
3882 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3883 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3884 if (
Ops.size() == 1)
return Ops[0];
3887 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3889 "Operand types don't match!");
3892 "min/max should be consistently pointerish");
3918 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3920 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3925 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3927 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3933 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3939 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3944 if (Idx <
Ops.size()) {
3945 bool DeletedAny =
false;
3946 while (
Ops[Idx]->getSCEVType() == Kind) {
3948 Ops.erase(
Ops.begin()+Idx);
3966 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3968 Ops[i] =
Ops[i + 1] = Common;
3969 if (
Ops[i] ==
Ops[i + 1] ||
3970 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3973 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3976 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3979 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3985 if (
Ops.size() == 1)
return Ops[0];
3987 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
3994 ID.AddPointer(
Op.getOpaqueValue());
3996 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
3998 return ExistingSCEV;
4001 SCEV *S =
new (SCEVAllocator)
4004 UniqueSCEVs.insert(S, Token);
4012class SCEVSequentialMinMaxDeduplicatingVisitor final
4013 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4014 std::optional<const SCEV *>> {
4015 using RetVal = std::optional<const SCEV *>;
4022 bool canRecurseInto(
SCEVTypes Kind)
const {
4025 return RootKind == Kind || NonSequentialRootKind == Kind;
4030 if (!SeenOps.
insert(S).second)
4031 return std::nullopt;
4035 if (!canRecurseInto(Kind))
4045 return std::nullopt;
4055 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4057 : SE(SE), RootKind(RootKind),
4058 NonSequentialRootKind(
4059 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4063 SmallVectorImpl<SCEVUse> &NewOps) {
4068 for (
const SCEV *
Op : OrigOps) {
4073 Ops.emplace_back(*NewOp);
4077 NewOps = std::move(
Ops);
4121struct SCEVPoisonCollector {
4122 bool LookThroughMaybePoisonBlocking;
4123 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4124 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4125 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4127 bool follow(
const SCEV *S) {
4128 if (!LookThroughMaybePoisonBlocking &&
4138 bool isDone()
const {
return false; }
4148 SCEVPoisonCollector PC1(
true);
4153 if (PC1.MaybePoison.
empty())
4159 SCEVPoisonCollector PC2(
false);
4169 SCEVPoisonCollector PC(
false);
4192 unsigned NumVisitedInsts = 0;
4194 while (!Worklist.
empty()) {
4196 if (!Visited.
insert(V).second)
4205 if (++NumVisitedInsts > InstLimit)
4216 if (PDI->isDisjoint())
4223 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4230 if (
I->hasPoisonGeneratingAnnotations())
4241 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4242 "Not a SCEVSequentialMinMaxExpr!");
4243 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4244 if (
Ops.size() == 1)
4248 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4250 "Operand types don't match!");
4253 "min/max should be consistently pointerish");
4261 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4268 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4278 bool DeletedAny =
false;
4279 while (Idx <
Ops.size()) {
4280 if (
Ops[Idx]->getSCEVType() != Kind) {
4285 Ops.erase(
Ops.begin() + Idx);
4286 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4287 SMME->operands().end());
4295 const SCEV *SaturationPoint;
4306 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4307 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4319 Ops.erase(
Ops.begin() + i);
4324 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4325 Ops.erase(
Ops.begin() + i);
4335 ID.AddPointer(
Op.getOpaqueValue());
4337 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
4339 return ExistingSCEV;
4343 SCEV *S =
new (SCEVAllocator)
4346 UniqueSCEVs.insert(S, Token);
4394 if (
Size.isScalable())
4415 "Cannot get offset for structure containing scalable vector types");
4429 if (
SCEV *S = UniqueSCEVs.lookup(ID, Token)) {
4431 "Stale SCEVUnknown in uniquing map!");
4434 SCEV *S =
new (SCEVAllocator)
SCEVUnknown(ID.Intern(SCEVAllocator), V,
this,
4435 FirstUnknown, NextUnknownOrderID++);
4437 UniqueSCEVs.insert(S, Token);
4452 return Ty->isIntOrPtrTy();
4459 if (Ty->isPointerTy())
4470 if (Ty->isIntegerTy())
4474 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4486 bool PreciseA, PreciseB;
4487 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4488 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4489 if (!PreciseA || !PreciseB)
4492 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4493 DT.dominates(ScopeB, ScopeA);
4497 return CouldNotCompute.get();
4500bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4503 return SU && SU->getValue() ==
nullptr;
4506 return !ContainsNulls;
4511 if (
I != HasRecMap.end())
4516 HasRecMap.insert({S, FoundAddRec});
4523 ExprValueMapType::iterator
SI = ExprValueMap.find_as(S);
4524 if (
SI == ExprValueMap.end())
4532void ScalarEvolution::eraseValueFromMap(
Value *V) {
4534 if (
I != ValueExprMap.end()) {
4535 auto EVIt = ExprValueMap.find(
I->second);
4538 ValueExprMap.erase(
I);
4542void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4546 if (ValueExprMap.insert({SCEVCallbackVH(V, this), S}).second)
4547 ExprValueMap[S].push_back(V);
4557 return createSCEVIter(V);
4564 if (
I != ValueExprMap.end()) {
4565 const SCEV *S =
I->second;
4566 assert(checkValidity(S) &&
4567 "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");
4657 return getZero(LHS->getType());
4662 if (RHS->getType()->isPointerTy()) {
4663 if (!LHS->getType()->isPointerTy() ||
4673 const bool RHSIsNotMinSigned =
4704 Type *SrcTy = V->getType();
4705 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4706 "Cannot truncate or zero extend with non-integer arguments!");
4716 Type *SrcTy = V->getType();
4717 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4718 "Cannot truncate or zero extend with non-integer arguments!");
4727 Type *SrcTy = V->getType();
4728 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4729 "Cannot noop or zero extend with non-integer arguments!");
4731 "getNoopOrZeroExtend cannot truncate!");
4738 Type *SrcTy = V->getType();
4739 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4740 "Cannot noop or sign extend with non-integer arguments!");
4742 "getNoopOrSignExtend cannot truncate!");
4749 Type *SrcTy = V->getType();
4750 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4751 "Cannot noop or any extend with non-integer arguments!");
4753 "getNoopOrAnyExtend cannot truncate!");
4760 Type *SrcTy = V->getType();
4761 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4762 "Cannot truncate or noop with non-integer arguments!");
4764 "getTruncateOrNoop cannot extend!");
4772 const SCEV *PromotedLHS = LHS;
4773 const SCEV *PromotedRHS = RHS;
4793 assert(!
Ops.empty() &&
"At least one operand must be!");
4795 if (
Ops.size() == 1)
4799 Type *MaxType =
nullptr;
4805 assert(MaxType &&
"Failed to find maximum type!");
4818 if (!V->getType()->isPointerTy())
4823 V = AddRec->getStart();
4825 const SCEV *PtrOp =
nullptr;
4826 for (
const SCEV *AddOp :
Add->operands()) {
4827 if (AddOp->getType()->isPointerTy()) {
4828 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4832 assert(PtrOp &&
"Must have pointer op");
4844 for (
User *U :
I->users()) {
4846 if (Visited.
insert(UserInsn).second)
4860 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4861 bool IgnoreOtherLoops =
true) {
4864 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4866 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4871 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4873 SeenLoopVariantSCEVUnknown =
true;
4877 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4881 SeenOtherLoops =
true;
4885 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4887 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4890 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4891 : SCEVRewriteVisitor(SE),
L(
L) {}
4894 bool SeenLoopVariantSCEVUnknown =
false;
4895 bool SeenOtherLoops =
false;
4904 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4905 SCEVPostIncRewriter
Rewriter(L, SE);
4907 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4912 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4914 SeenLoopVariantSCEVUnknown =
true;
4918 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4922 SeenOtherLoops =
true;
4926 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4928 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4931 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4932 : SCEVRewriteVisitor(SE),
L(
L) {}
4935 bool SeenLoopVariantSCEVUnknown =
false;
4936 bool SeenOtherLoops =
false;
4942class SCEVBackedgeConditionFolder
4945 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4946 ScalarEvolution &SE) {
4947 bool IsPosBECond =
false;
4948 Value *BECond =
nullptr;
4949 if (BasicBlock *Latch =
L->getLoopLatch()) {
4951 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
4952 "Both outgoing branches should not target same header!");
4953 BECond = BI->getCondition();
4954 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
4959 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
4963 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4964 const SCEV *
Result = Expr;
4969 switch (
I->getOpcode()) {
4970 case Instruction::Select: {
4972 std::optional<const SCEV *> Res =
4973 compareWithBackedgeCondition(
SI->getCondition());
4981 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
4992 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
4993 bool IsPosBECond, ScalarEvolution &SE)
4994 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
4995 IsPositiveBECond(IsPosBECond) {}
4997 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5001 Value *BackedgeCond =
nullptr;
5003 bool IsPositiveBECond;
5006std::optional<const SCEV *>
5007SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5012 if (BackedgeCond == IC)
5015 return std::nullopt;
5020 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5021 ScalarEvolution &SE) {
5027 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5034 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5044 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5045 : SCEVRewriteVisitor(SE),
L(
L) {}
5053void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5069 const APInt &BECountAP = BECountMax->getAPInt();
5070 unsigned NoOverflowBitWidth =
5079ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5089 if (!SignedWrapViaInductionTried.insert(AR).second)
5114 AC.assumptions().empty())
5122 const SCEV *OverflowLimit =
5124 if (OverflowLimit &&
5132ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5142 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5167 AC.assumptions().empty())
5176 const SCEV *OverflowLimit =
5205 IsNSW = OBO->hasNoSignedWrap();
5206 IsNUW = OBO->hasNoUnsignedWrap();
5212 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5222 return std::nullopt;
5228 switch (
Op->getOpcode()) {
5229 case Instruction::Add:
5230 case Instruction::Sub:
5231 case Instruction::Mul:
5232 case Instruction::UDiv:
5233 case Instruction::URem:
5234 case Instruction::And:
5235 case Instruction::AShr:
5236 case Instruction::Shl:
5239 case Instruction::Or: {
5242 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5252 case Instruction::Xor:
5256 if (RHSC->getValue().isSignMask())
5257 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5259 if (V->getType()->isIntegerTy(1))
5260 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5263 case Instruction::LShr:
5272 if (SA->getValue().ult(
BitWidth)) {
5274 ConstantInt::get(SA->getContext(),
5276 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5281 case Instruction::ExtractValue: {
5283 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5291 bool Signed = WO->isSigned();
5294 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5299 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5310 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5311 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5313 return std::nullopt;
5339 if (
Op == SymbolicPHI)
5344 if (SourceBits != NewBits)
5362 if (!L || L->getHeader() != PN->
getParent())
5420std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5421ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5429 assert(L &&
"Expecting an integer loop header phi");
5434 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5435 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5436 Value *
V = PN->getIncomingValue(i);
5437 if (
L->contains(PN->getIncomingBlock(i))) {
5440 }
else if (BEValueV != V) {
5444 }
else if (!StartValueV) {
5446 }
else if (StartValueV != V) {
5447 StartValueV =
nullptr;
5451 if (!BEValueV || !StartValueV)
5452 return std::nullopt;
5454 const SCEV *BEValue =
getSCEV(BEValueV);
5461 return std::nullopt;
5465 unsigned FoundIndex =
Add->getNumOperands();
5466 Type *TruncTy =
nullptr;
5468 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5471 if (FoundIndex == e) {
5476 if (FoundIndex ==
Add->getNumOperands())
5477 return std::nullopt;
5481 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5482 if (i != FoundIndex)
5483 Ops.push_back(
Add->getOperand(i));
5489 return std::nullopt;
5542 const SCEV *StartVal =
getSCEV(StartValueV);
5543 const SCEV *PHISCEV =
5570 auto getExtendedExpr = [&](
const SCEV *Expr,
5571 bool CreateSignExtend) ->
const SCEV * {
5574 const SCEV *ExtendedExpr =
5577 return ExtendedExpr;
5585 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5586 const SCEV *ExtendedExpr) ->
bool {
5587 return Expr != ExtendedExpr &&
5591 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5592 if (PredIsKnownFalse(StartVal, StartExtended)) {
5594 return std::nullopt;
5599 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5600 if (PredIsKnownFalse(Accum, AccumExtended)) {
5602 return std::nullopt;
5605 auto AppendPredicate = [&](
const SCEV *Expr,
5606 const SCEV *ExtendedExpr) ->
void {
5607 if (Expr != ExtendedExpr &&
5615 AppendPredicate(StartVal, StartExtended);
5616 AppendPredicate(Accum, AccumExtended);
5624 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5625 std::make_pair(NewAR, Predicates);
5627 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5631std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5636 return std::nullopt;
5639 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5640 if (
I != PredicatedSCEVRewrites.end()) {
5641 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5644 if (Rewrite.first == SymbolicPHI)
5645 return std::nullopt;
5649 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5653 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5654 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5659 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5660 return std::nullopt;
5680 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5681 if (Expr1 != Expr2 &&
5682 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5683 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5718const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5720 Value *StartValueV) {
5723 assert(BEValueV && StartValueV);
5725 const SCEV *Accum =
nullptr;
5728 if (BO->Opcode != Instruction::Add)
5731 if (BO->LHS == PN &&
L->isLoopInvariant(BO->RHS))
5733 else if (BO->RHS == PN &&
L->isLoopInvariant(BO->LHS))
5747 if (!
GEP ||
GEP->getPointerOperand() != PN ||
GEP->getNumIndices() != 1)
5750 if (!
L->isLoopInvariant(Idx))
5759 const SCEV *StartVal =
getSCEV(StartValueV);
5760 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5761 insertValueToMap(PN, PHISCEV);
5764 inferNoWrapViaConstantRanges(AR);
5771 "Accum is defined outside L, but is not invariant?");
5772 if (isAddRecNeverPoison(BEInst, L))
5779const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5787 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5793 }
else if (BEValueV != V) {
5797 }
else if (!StartValueV) {
5799 }
else if (StartValueV != V) {
5800 StartValueV =
nullptr;
5804 if (!BEValueV || !StartValueV)
5807 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5808 "PHI node already processed?");
5812 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5817 insertValueToMap(PN, SymbolicName);
5821 const SCEV *BEValue =
getSCEV(BEValueV);
5831 unsigned FoundIndex =
Add->getNumOperands();
5832 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5833 if (
Add->getOperand(i) == SymbolicName)
5834 if (FoundIndex == e) {
5839 if (FoundIndex !=
Add->getNumOperands()) {
5842 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5843 if (i != FoundIndex)
5844 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5856 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5863 if (
GEP->getOperand(0) == PN)
5871 const SCEV *StartVal =
getSCEV(StartValueV);
5872 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5877 forgetMemoizedResults({SymbolicName});
5878 insertValueToMap(PN, PHISCEV);
5881 inferNoWrapViaConstantRanges(AR);
5905 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5906 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5908 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5909 const SCEV *StartVal =
getSCEV(StartValueV);
5910 if (Start == StartVal) {
5914 forgetMemoizedResults({SymbolicName});
5915 insertValueToMap(PN, Shifted);
5925 eraseValueFromMap(PN);
5940 Use &LeftUse =
Merge->getOperandUse(0);
5941 Use &RightUse =
Merge->getOperandUse(1);
5977 assert(IDom &&
"At least the entry block should dominate PN");
5985const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
5990 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6007 CommonInst = IncomingInst;
6023ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6029 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6030 bool SCEVExprsIdentical =
6032 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6033 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6036const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6037 if (
const SCEV *S = createAddRecFromPHI(PN))
6047 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6050 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6059 struct FindClosure {
6060 const SCEV *OperandToFind;
6066 bool canRecurseInto(
SCEVTypes Kind)
const {
6069 return RootKind == Kind || NonSequentialRootKind == Kind ||
6074 : OperandToFind(OperandToFind), RootKind(RootKind),
6075 NonSequentialRootKind(
6079 bool follow(
const SCEV *S) {
6080 Found = S == OperandToFind;
6082 return !isDone() && canRecurseInto(S->
getSCEVType());
6085 bool isDone()
const {
return Found; }
6088 FindClosure FC(OperandToFind, RootKind);
6093std::optional<const SCEV *>
6094ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6104 switch (ICI->getPredicate()) {
6118 bool Signed = ICI->isSigned();
6119 const SCEV *LA =
getSCEV(TrueVal);
6127 if (LA == LS &&
RA == RS)
6129 if (LA == RS &&
RA == LS)
6132 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6133 if (
Op->getType()->isPointerTy()) {
6144 LS = CoerceOperand(LS);
6145 RS = CoerceOperand(RS);
6169 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6170 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6184 X = ZExt->getOperand();
6186 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6197 return std::nullopt;
6200static std::optional<const SCEV *>
6202 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6206 "Unexpected operands of a select.");
6218 return std::nullopt;
6233static std::optional<const SCEV *>
6237 return std::nullopt;
6240 const auto *SETrue = SE->
getSCEV(TrueVal);
6241 const auto *SEFalse = SE->
getSCEV(FalseVal);
6245const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6247 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6249 V->getType() ==
TrueVal->getType() &&
6250 "Types of select hands and of the result must match.");
6253 if (!
V->getType()->isIntegerTy(1))
6256 if (std::optional<const SCEV *> S =
6269 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6273 if (std::optional<const SCEV *> S =
6274 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6280 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6286 assert(
GEP->getSourceElementType()->isSized() &&
6287 "GEP source element type must be sized");
6290 for (
Value *Index :
GEP->indices())
6295APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6298 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6301 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6303 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6306 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6324 return GetShiftedByZeros(TZ);
6334 return GetShiftedByZeros(TZ);
6338 if (
M->hasNoUnsignedWrap()) {
6341 for (
const SCEV *Operand :
M->operands().drop_front())
6349 for (
const SCEV *Operand :
M->operands())
6351 return GetShiftedByZeros(TZ);
6356 if (
N->hasNoUnsignedWrap())
6357 return GetGCDMultiple(
N);
6360 for (
const SCEV *Operand :
N->operands().drop_front())
6362 return GetShiftedByZeros(TZ);
6379 CtxI = &*F.getEntryBlock().begin();
6386 .allowEphemerals(
true))
6387 .countMinTrailingZeros();
6388 return GetShiftedByZeros(
Known);
6401 return getConstantMultipleImpl(S, CtxI);
6403 auto I = ConstantMultipleCache.find(S);
6404 if (
I != ConstantMultipleCache.end())
6407 APInt Result = getConstantMultipleImpl(S, CtxI);
6408 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6409 assert(InsertPair.second &&
"Should insert a new key");
6410 return InsertPair.first->second;
6427 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6430 if (std::optional<ConstantRange>
Range = CB->getRange())
6434 if (std::optional<ConstantRange>
Range =
A->getRange())
6437 return std::nullopt;
6444 UnsignedRanges.erase(AddRec);
6445 SignedRanges.erase(AddRec);
6446 ConstantMultipleCache.erase(AddRec);
6451getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6477 Value *Start, *Step;
6484 assert(L && L->getHeader() ==
P->getParent());
6497 case Instruction::AShr:
6498 case Instruction::LShr:
6499 case Instruction::Shl:
6514 KnownStep.getBitWidth() ==
BitWidth);
6517 auto MaxShiftAmt = KnownStep.getMaxValue();
6519 bool Overflow =
false;
6520 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6527 case Instruction::AShr: {
6535 if (KnownStart.isNonNegative())
6538 KnownStart.getMaxValue() + 1);
6539 if (KnownStart.isNegative())
6542 KnownEnd.getMaxValue() + 1);
6545 case Instruction::LShr: {
6554 KnownStart.getMaxValue() + 1);
6556 case Instruction::Shl: {
6560 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6561 return ConstantRange(KnownStart.getMinValue(),
6562 KnownEnd.getMaxValue() + 1);
6587 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6594ScalarEvolution::getRangeRefIter(
const SCEV *S,
6595 ScalarEvolution::RangeSignHint SignHint) {
6596 DenseMap<const SCEV *, ConstantRange> &Cache =
6597 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6600 SmallPtrSet<const SCEV *, 8> Seen;
6604 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6605 if (!Seen.
insert(Expr).second)
6638 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6639 const SCEV *
P = WorkList[
I];
6643 for (
const SCEV *
Op :
P->operands())
6656 if (!WorkList.
empty()) {
6661 getRangeRef(
P, SignHint);
6665 return getRangeRef(S, SignHint, 0);
6668const APInt *ScalarEvolution::getConstantAPIntOrNull(
const SCEV *S) {
6670 return &
C->getAPInt();
6678 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6679 DenseMap<const SCEV *, ConstantRange> &Cache =
6680 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6687 auto I = Cache.
find(S);
6688 if (
I != Cache.
end())
6692 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6697 return getRangeRefIter(S, SignHint);
6700 ConstantRange ConservativeResult(
BitWidth,
true);
6701 using OBO = OverflowingBinaryOperator;
6705 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6709 ConservativeResult =
6716 ConservativeResult = ConstantRange(
6732 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6739 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6746 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6751 return setRange(Cast, SignHint,
X);
6756 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6757 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6759 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6760 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6761 ConservativeResult =
6762 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6764 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6765 unsigned WrapType = OBO::AnyWrap;
6766 if (
Add->hasNoSignedWrap())
6767 WrapType |= OBO::NoSignedWrap;
6768 if (
Add->hasNoUnsignedWrap())
6769 WrapType |= OBO::NoUnsignedWrap;
6771 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6773 return setRange(
Add, SignHint,
6774 ConservativeResult.intersectWith(
X, RangeType));
6778 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6780 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6781 return setRange(
Mul, SignHint,
6782 ConservativeResult.intersectWith(
X, RangeType));
6786 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6787 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6788 return setRange(UDiv, SignHint,
6789 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6797 if (!UnsignedMinValue.
isZero())
6798 ConservativeResult = ConservativeResult.intersectWith(
6799 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6808 bool AllNonNeg =
true;
6809 bool AllNonPos =
true;
6810 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6817 ConservativeResult = ConservativeResult.intersectWith(
6822 ConservativeResult = ConservativeResult.intersectWith(
6831 const SCEV *MaxBEScev =
6845 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6847 ConservativeResult =
6848 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6851 auto RangeFromFactoring = getRangeViaFactoring(
6853 ConservativeResult =
6854 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6860 const SCEV *SymbolicMaxBECount =
6865 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6866 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6867 ConservativeResult =
6868 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6873 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6883 ID = Intrinsic::umax;
6886 ID = Intrinsic::smax;
6890 ID = Intrinsic::umin;
6893 ID = Intrinsic::smin;
6900 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6901 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6903 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6904 return setRange(S, SignHint,
6905 ConservativeResult.intersectWith(
X, RangeType));
6914 ConservativeResult =
6915 ConservativeResult.intersectWith(*MDRange, RangeType);
6920 auto CR = getRangeForUnknownRecurrence(U);
6921 ConservativeResult = ConservativeResult.intersectWith(CR);
6932 if (
U->getType()->isPointerTy()) {
6935 unsigned PtrIdxDiff =
6936 DL.getPointerTypeSizeInBits(
U->getType()) -
BitWidth;
6937 NS = NS > PtrIdxDiff ? NS - PtrIdxDiff : 1;
6942 if (!
Known.Zero.getHiBits(NS).isZero())
6943 Known.Zero.setHighBits(NS);
6944 if (!
Known.One.getHiBits(NS).isZero())
6945 Known.One.setHighBits(NS);
6948 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
6949 ConservativeResult = ConservativeResult.intersectWith(
6950 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
6953 ConservativeResult = ConservativeResult.intersectWith(
6958 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6962 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
6963 DL, CanBeNull,
nullptr);
6979 ConservativeResult = ConservativeResult.intersectWith(
6989 return getRangeRef(AR, SignHint,
Depth + 1);
6993 ConstantRange RangeFromOps(
BitWidth,
false);
6995 for (
const auto &
Op :
Phi->operands()) {
6997 RangeFromOps = RangeFromOps.unionWith(OpRange);
6999 if (RangeFromOps.isFullSet())
7002 ConservativeResult =
7003 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7009 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7011 ConservativeResult = ConservativeResult.difference(Disallowed);
7014 return setRange(U, SignHint, std::move(ConservativeResult));
7020 return setRange(S, SignHint, std::move(ConservativeResult));
7028static std::pair<ConstantRange, bool>
7036 if (Step == 0 || MaxBECount == 0)
7037 return {StartRange,
true};
7043 return {ConstantRange::getFull(
BitWidth),
false};
7059 return {ConstantRange::getFull(
BitWidth),
false};
7072 APInt MovedBoundary;
7077 MovedBoundary = StartLower - std::move(
Offset);
7080 MovedBoundary = StartUpper + std::move(
Offset);
7084 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7091 if (StartRange.
contains(MovedBoundary))
7092 return {ConstantRange::getFull(
BitWidth),
false};
7095 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7097 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7105std::pair<ConstantRange, SCEVFlags>
7106ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7107 const APInt &MaxBECount) {
7111 "mismatched bit widths");
7120 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7125 StepSRange.
getSignedMax(), StartSRange, MaxBECount,
true);
7126 SR = SR.unionWith(SRMax);
7145ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7147 ScalarEvolution::RangeSignHint SignHint) {
7148 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7150 "This only works for non-self-wrapping AddRecs!");
7151 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7155 return ConstantRange::getFull(
BitWidth);
7163 return ConstantRange::getFull(
BitWidth);
7167 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7169 MaxItersWithoutWrap))
7170 return ConstantRange::getFull(
BitWidth);
7191 ConstantRange StartRange = getRangeRef(Start, SignHint);
7192 ConstantRange EndRange = getRangeRef(
End, SignHint);
7193 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7197 return RangeBetween;
7202 return ConstantRange::getFull(
BitWidth);
7205 isKnownPredicateViaConstantRanges(LEPred, Start,
End))
7206 return RangeBetween;
7208 isKnownPredicateViaConstantRanges(GEPred, Start,
End))
7209 return RangeBetween;
7210 return ConstantRange::getFull(
BitWidth);
7215 const APInt &MaxBECount) {
7222 "mismatched bit widths");
7224 struct SelectPattern {
7225 Value *Condition =
nullptr;
7229 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7231 std::optional<unsigned> CastOp;
7245 CastOp = SCast->getSCEVType();
7246 S = SCast->getOperand();
7249 using namespace llvm::PatternMatch;
7256 Condition =
nullptr;
7288 bool isRecognized() {
return Condition !=
nullptr; }
7291 SelectPattern StartPattern(*
this,
BitWidth, Start);
7292 if (!StartPattern.isRecognized())
7293 return ConstantRange::getFull(
BitWidth);
7295 SelectPattern StepPattern(*
this,
BitWidth, Step);
7296 if (!StepPattern.isRecognized())
7297 return ConstantRange::getFull(
BitWidth);
7299 if (StartPattern.Condition != StepPattern.Condition) {
7303 return ConstantRange::getFull(
BitWidth);
7314 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7315 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7316 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7317 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7319 ConstantRange TrueRange =
7320 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7321 ConstantRange FalseRange =
7322 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7335 PDI && PDI->isDisjoint()) {
7350ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7363 SmallPtrSet<const SCEV *, 16> Visited;
7365 auto pushOp = [&](
const SCEV *S) {
7366 if (!Visited.
insert(S).second)
7369 if (Visited.
size() > 30) {
7380 while (!Worklist.
empty()) {
7382 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7383 if (!Bound || DT.dominates(Bound, DefI))
7390 return Bound ? Bound : &*F.getEntryBlock().begin();
7396 return getDefiningScopeBound(
Ops, Discard);
7399bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7401 if (
A->getParent() ==
B->getParent() &&
7406 auto *BLoop = LI.getLoopFor(
B->getParent());
7407 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7408 BLoop->getLoopPreheader() ==
A->getParent() &&
7410 A->getParent()->end()) &&
7418 SCEVPoisonCollector PC(
true);
7420 return PC.MaybePoison.
empty();
7423bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7433bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7450 for (
const Use &
Op :
I->operands()) {
7456 auto *DefI = getDefiningScopeBound(SCEVOps);
7457 return isGuaranteedToTransferExecutionTo(DefI,
I);
7460bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7462 if (isSCEVExprNeverPoison(
I))
7473 auto *ExitingBB =
L->getExitingBlock();
7477 SmallPtrSet<const Value *, 16> KnownPoison;
7486 while (!Worklist.
empty()) {
7489 for (
const Use &U :
Poison->uses()) {
7492 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7496 if (KnownPoison.
insert(PoisonUser).second)
7504ScalarEvolution::LoopProperties
7505ScalarEvolution::getLoopProperties(
const Loop *L) {
7506 using LoopProperties = ScalarEvolution::LoopProperties;
7508 auto Itr = LoopPropertiesCache.find(L);
7509 if (Itr == LoopPropertiesCache.end()) {
7512 return !
SI->isSimple();
7523 if (
I->isDroppable())
7526 return I->mayWriteToMemory();
7529 LoopProperties LP = {
true,
7532 for (
auto *BB :
L->getBlocks())
7533 for (
auto &
I : *BB) {
7535 LP.HasNoAbnormalExits =
false;
7536 if (HasSideEffects(&
I))
7537 LP.HasNoSideEffects =
false;
7538 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7542 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7543 assert(InsertPair.second &&
"We just checked!");
7544 Itr = InsertPair.first;
7557const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7563 Stack.emplace_back(V,
false);
7564 while (!Stack.empty()) {
7565 auto E = Stack.back();
7566 Value *CurV = E.getPointer();
7574 const SCEV *CreatedSCEV =
nullptr;
7577 CreatedSCEV = createSCEV(CurV);
7582 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7586 insertValueToMap(CurV, CreatedSCEV);
7589 Stack.back().setInt(
true);
7592 Stack.emplace_back(
Op,
false);
7609 if (!DT.isReachableFromEntry(
I->getParent()))
7621 switch (BO->Opcode) {
7622 case Instruction::Add:
7623 case Instruction::Mul: {
7630 Ops.push_back(BO->
Op);
7634 Ops.push_back(BO->RHS);
7637 (BO->Opcode == Instruction::Add &&
7638 (NewBO->Opcode != Instruction::Add &&
7639 NewBO->Opcode != Instruction::Sub)) ||
7640 (BO->Opcode == Instruction::Mul &&
7641 NewBO->Opcode != Instruction::Mul)) {
7642 Ops.push_back(BO->LHS);
7647 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7650 Ops.push_back(BO->LHS);
7658 case Instruction::Sub:
7659 case Instruction::UDiv:
7660 case Instruction::URem:
7662 case Instruction::AShr:
7663 case Instruction::Shl:
7664 case Instruction::Xor:
7668 case Instruction::And:
7669 case Instruction::Or:
7673 case Instruction::LShr:
7680 Ops.push_back(BO->LHS);
7681 Ops.push_back(BO->RHS);
7685 switch (
U->getOpcode()) {
7686 case Instruction::Trunc:
7687 case Instruction::ZExt:
7688 case Instruction::SExt:
7689 case Instruction::PtrToAddr:
7690 case Instruction::PtrToInt:
7691 Ops.push_back(
U->getOperand(0));
7694 case Instruction::BitCast:
7696 Ops.push_back(
U->getOperand(0));
7701 case Instruction::SDiv:
7702 case Instruction::SRem:
7703 Ops.push_back(
U->getOperand(0));
7704 Ops.push_back(
U->getOperand(1));
7707 case Instruction::GetElementPtr:
7709 "GEP source element type must be sized");
7713 case Instruction::IntToPtr:
7716 case Instruction::PHI:
7747 Ops.push_back(CondICmp->getOperand(0));
7748 Ops.push_back(CondICmp->getOperand(1));
7768 case Instruction::Select: {
7770 auto CanSimplifyToUnknown = [
this,
U]() {
7788 if (CanSimplifyToUnknown())
7795 case Instruction::Call:
7796 case Instruction::Invoke:
7803 switch (
II->getIntrinsicID()) {
7804 case Intrinsic::abs:
7805 Ops.push_back(
II->getArgOperand(0));
7807 case Intrinsic::umax:
7808 case Intrinsic::umin:
7809 case Intrinsic::smax:
7810 case Intrinsic::smin:
7811 case Intrinsic::usub_sat:
7812 case Intrinsic::uadd_sat:
7813 Ops.push_back(
II->getArgOperand(0));
7814 Ops.push_back(
II->getArgOperand(1));
7816 case Intrinsic::start_loop_iterations:
7817 case Intrinsic::annotation:
7818 case Intrinsic::ptr_annotation:
7819 Ops.push_back(
II->getArgOperand(0));
7831const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7840 if (!DT.isReachableFromEntry(
I->getParent()))
7854 switch (BO->Opcode) {
7855 case Instruction::Add: {
7881 if (BO->Opcode == Instruction::Sub)
7889 if (BO->Opcode == Instruction::Sub)
7895 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7896 NewBO->Opcode != Instruction::Sub)) {
7906 case Instruction::Mul: {
7926 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7935 case Instruction::UDiv:
7939 case Instruction::URem:
7943 case Instruction::Sub: {
7946 Flags = getNoWrapFlagsFromUB(BO->
Op);
7951 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
7954 if (HasPtrLHS || HasPtrRHS) {
7959 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
7960 bool BothPtr) ->
const SCEV * {
7963 const SCEV *PtrSCEV =
getSCEV(PtrOp);
7973 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
7974 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
7982 case Instruction::And:
7988 if (CI->isMinusOne())
7990 const APInt &
A = CI->getValue();
7996 unsigned LZ =
A.countl_zero();
7997 unsigned TZ =
A.countr_zero();
8002 APInt EffectiveMask =
8004 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
8007 const SCEV *ShiftedLHS =
nullptr;
8011 unsigned MulZeros = OpC->getAPInt().countr_zero();
8012 unsigned GCD = std::min(MulZeros, TZ);
8017 const SCEV *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8039 case Instruction::Or:
8048 case Instruction::Xor:
8051 if (CI->isMinusOne())
8060 if (LBO->getOpcode() == Instruction::And &&
8061 LCI->getValue() == CI->getValue())
8062 if (
const SCEVZeroExtendExpr *Z =
8065 const SCEV *Z0 =
Z->getOperand();
8072 if (CI->getValue().isMask(Z0TySize))
8078 APInt Trunc = CI->getValue().trunc(Z0TySize);
8087 case Instruction::Shl:
8105 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8114 ConstantInt *
X = ConstantInt::get(
8120 case Instruction::AShr:
8142 const SCEV *AddTruncateExpr =
nullptr;
8143 ConstantInt *ShlAmtCI =
nullptr;
8144 const SCEV *AddConstant =
nullptr;
8146 if (L &&
L->getOpcode() == Instruction::Add) {
8154 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8161 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8169 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8174 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8179 if (AddTruncateExpr && ShlAmtCI) {
8191 const APInt &ShlAmt = ShlAmtCI->
getValue();
8195 const SCEV *CompositeExpr =
8197 if (
L->getOpcode() != Instruction::Shl)
8198 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8207 switch (
U->getOpcode()) {
8208 case Instruction::Trunc:
8211 case Instruction::ZExt:
8214 case Instruction::SExt:
8223 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8224 Type *Ty =
U->getType();
8232 case Instruction::BitCast:
8238 case Instruction::PtrToAddr: {
8245 case Instruction::PtrToInt:
8249 case Instruction::IntToPtr:
8253 case Instruction::SDiv:
8260 case Instruction::SRem:
8267 case Instruction::GetElementPtr:
8270 case Instruction::PHI:
8273 case Instruction::Select:
8274 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8277 case Instruction::Call:
8278 case Instruction::Invoke:
8283 switch (
II->getIntrinsicID()) {
8284 case Intrinsic::abs:
8288 case Intrinsic::umax:
8292 case Intrinsic::umin:
8296 case Intrinsic::smax:
8300 case Intrinsic::smin:
8304 case Intrinsic::usub_sat: {
8305 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8306 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8310 case Intrinsic::uadd_sat: {
8311 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8312 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8316 case Intrinsic::start_loop_iterations:
8317 case Intrinsic::annotation:
8318 case Intrinsic::ptr_annotation:
8322 case Intrinsic::vscale:
8342 auto *ExitCountType = ExitCount->
getType();
8343 assert(ExitCountType->isIntegerTy());
8345 1 + ExitCountType->getScalarSizeInBits());
8358 auto CanAddOneWithoutOverflow = [&]() {
8360 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8371 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8401 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8402 assert(L->isLoopExiting(ExitingBlock) &&
8403 "Exiting block must actually branch out of the loop!");
8412 const auto *MaxExitCount =
8420 L->getExitingBlocks(ExitingBlocks);
8423 if (ExitingBlocks.
empty() ||
8438 LoopGuards &Guards) {
8442 const SCEV *TCExpr =
8450 : (
unsigned)Multiple.getZExtValue();
8454 const SCEV *ExitCount) {
8477 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8478 assert(L->isLoopExiting(ExitingBlock) &&
8479 "Exiting block must actually branch out of the loop!");
8489 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8491 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8493 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8503 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8506 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8509 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8517 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8524 return getBackedgeTakenInfo(L).getExact(L,
this);
8526 return getBackedgeTakenInfo(L).getConstantMax(
this);
8528 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8535 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8540 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8544 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8554 for (
PHINode &PN : Header->phis())
8555 if (Visited.
insert(&PN).second)
8559ScalarEvolution::BackedgeTakenInfo &
8560ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8561 auto &BTI = getBackedgeTakenInfo(L);
8562 if (BTI.hasFullInfo())
8565 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8568 return Pair.first->second;
8570 BackedgeTakenInfo
Result =
8571 computeBackedgeTakenCount(L,
true);
8573 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8576ScalarEvolution::BackedgeTakenInfo &
8577ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8583 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8584 BackedgeTakenCounts.try_emplace(L);
8586 return Pair.first->second;
8591 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8598 if (
Result.hasAnyInfo()) {
8601 auto LoopUsersIt = LoopUsers.find(L);
8602 if (LoopUsersIt != LoopUsers.end())
8604 forgetMemoizedResults(ToForget);
8607 for (PHINode &PN :
L->getHeader()->phis())
8608 ConstantEvolutionLoopExitValue.erase(&PN);
8616 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8625 BackedgeTakenCounts.clear();
8626 PredicatedBackedgeTakenCounts.clear();
8627 BECountUsers.clear();
8628 LoopPropertiesCache.clear();
8629 ConstantEvolutionLoopExitValue.clear();
8630 ValueExprMap.clear();
8631 ValuesAtScopes.clear();
8632 ValuesAtScopesUsers.clear();
8633 LoopDispositions.clear();
8634 BlockDispositions.clear();
8635 UnsignedRanges.clear();
8636 SignedRanges.clear();
8637 ExprValueMap.clear();
8639 ConstantMultipleCache.clear();
8640 PredicatedSCEVRewrites.clear();
8642 FoldCacheUser.clear();
8644void ScalarEvolution::visitAndClearUsers(
8649 if (ValueExprMap.
empty()) {
8653 while (!Worklist.
empty()) {
8660 if (It != ValueExprMap.
end()) {
8662 eraseValueFromMap(It->first);
8664 ConstantEvolutionLoopExitValue.erase(PN);
8678 while (!LoopWorklist.
empty()) {
8682 forgetBackedgeTakenCounts(CurrL,
false);
8683 forgetBackedgeTakenCounts(CurrL,
true);
8686 PredicatedSCEVRewrites.remove_if(
8687 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8689 auto LoopUsersItr = LoopUsers.find(CurrL);
8690 if (LoopUsersItr != LoopUsers.end())
8695 visitAndClearUsers(Worklist, Visited, ToForget);
8697 LoopPropertiesCache.erase(CurrL);
8700 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8702 forgetMemoizedResults(ToForget);
8719 visitAndClearUsers(Worklist, Visited, ToForget);
8721 forgetMemoizedResults(ToForget);
8732 visitAndClearUsers(Worklist, Visited, ToForget);
8734 forgetMemoizedResults(ToForget);
8742 auto InvalidateValue = [&](
Value *Val) {
8746 struct InvalidationRootCollector {
8750 InvalidationRootCollector(
Loop *L) : L(L) {}
8752 bool follow(
const SCEV *S) {
8758 if (L->contains(AddRec->
getLoop()))
8763 bool isDone()
const {
return false; }
8766 InvalidationRootCollector
C(L);
8768 forgetMemoizedResults(
C.Roots);
8791 BlockDispositions.clear();
8792 LoopDispositions.clear();
8809 while (!Worklist.
empty()) {
8811 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8812 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8813 if (!LoopDispoRemoved && !BlockDispoRemoved)
8815 auto Users = SCEVUsers.find(Curr);
8816 if (
Users != SCEVUsers.end())
8829const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8833 if (!isComplete() || ExitNotTaken.
empty())
8844 for (
const auto &ENT : ExitNotTaken) {
8845 const SCEV *BECount = ENT.ExactNotTaken;
8848 "We should only have known counts for exiting blocks that dominate "
8851 Ops.push_back(BECount);
8856 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8857 "Predicate should be always true!");
8866const ScalarEvolution::ExitNotTakenInfo *
8867ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8868 const BasicBlock *ExitingBlock,
8869 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8870 for (
const auto &ENT : ExitNotTaken)
8871 if (ENT.ExitingBlock == ExitingBlock) {
8872 if (ENT.hasAlwaysTruePredicate())
8874 else if (Predicates) {
8884const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8886 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8887 if (!getConstantMax())
8890 for (
const auto &ENT : ExitNotTaken)
8891 if (!ENT.hasAlwaysTruePredicate()) {
8899 "No point in having a non-constant max backedge taken count!");
8900 return getConstantMax();
8903const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8905 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8913 for (
const auto &ENT : ExitNotTaken) {
8914 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8917 "We should only have known counts for exiting blocks that "
8923 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8924 "Predicate should be always true!");
8927 if (ExitCounts.
empty())
8936bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8938 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8939 return !ENT.hasAlwaysTruePredicate();
8941 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8957 this->ExactNotTaken = E = ConstantMaxNotTaken;
8958 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8963 "Exact is not allowed to be less precise than Constant Max");
8966 "Exact is not allowed to be less precise than Symbolic Max");
8969 "Symbolic Max is not allowed to be less precise than Constant Max");
8972 "No point in having a non-constant max backedge taken count!");
8974 for (
const auto PredList : PredLists)
8975 for (
const auto *
P : PredList) {
8983 "Backedge count should be int");
8986 "Max backedge count should be int");
8999ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
9001 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
9002 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
9003 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9005 ExitNotTaken.reserve(ExitCounts.
size());
9006 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
9007 std::back_inserter(ExitNotTaken),
9008 [&](
const EdgeExitInfo &EEI) {
9009 BasicBlock *ExitBB = EEI.first;
9010 const ExitLimit &EL = EEI.second;
9011 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
9012 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
9017 "No point in having a non-constant max backedge taken count!");
9021ScalarEvolution::BackedgeTakenInfo
9022ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
9023 bool AllowPredicates) {
9025 L->getExitingBlocks(ExitingBlocks);
9027 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9030 bool CouldComputeBECount =
true;
9032 const SCEV *MustExitMaxBECount =
nullptr;
9033 const SCEV *MayExitMaxBECount =
nullptr;
9034 bool MustExitMaxOrZero =
false;
9035 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9046 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9047 if (ExitIfTrue == CI->
isZero())
9051 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9053 assert((AllowPredicates || EL.Predicates.empty()) &&
9054 "Predicated exit limit when predicates are not allowed!");
9059 ++NumExitCountsComputed;
9063 CouldComputeBECount =
false;
9070 "Exact is known but symbolic isn't?");
9071 ++NumExitCountsNotComputed;
9086 DT.dominates(ExitBB, Latch)) {
9087 if (!MustExitMaxBECount) {
9088 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9089 MustExitMaxOrZero = EL.MaxOrZero;
9092 EL.ConstantMaxNotTaken);
9096 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9099 EL.ConstantMaxNotTaken);
9103 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9107 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9113 for (
const auto &Pair : ExitCounts) {
9115 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9117 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9118 {
L, AllowPredicates});
9120 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9121 MaxBECount, MaxOrZero);
9124ScalarEvolution::ExitLimit
9125ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9126 bool IsOnlyExit,
bool AllowPredicates) {
9127 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9131 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9136 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9137 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9138 "It should have one successor in loop and one exit block!");
9149 if (!
L->contains(SBB)) {
9154 assert(Exit &&
"Exiting block must have at least one exit");
9155 return computeExitLimitFromSingleExitSwitch(
9156 L, SI, Exit, IsOnlyExit);
9163 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9164 bool AllowPredicates) {
9165 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9166 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9167 ControlsOnlyExit, AllowPredicates);
9170std::optional<ScalarEvolution::ExitLimit>
9171ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9172 bool ExitIfTrue,
bool ControlsOnlyExit,
9173 bool AllowPredicates) {
9175 (void)this->ExitIfTrue;
9176 (void)this->AllowPredicates;
9178 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9179 this->AllowPredicates == AllowPredicates &&
9180 "Variance in assumed invariant key components!");
9181 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9182 if (Itr == TripCountMap.end())
9183 return std::nullopt;
9187void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9189 bool ControlsOnlyExit,
9190 bool AllowPredicates,
9192 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9193 this->AllowPredicates == AllowPredicates &&
9194 "Variance in assumed invariant key components!");
9196 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9197 assert(InsertResult.second &&
"Expected successful insertion!");
9202ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9203 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9204 bool ControlsOnlyExit,
bool AllowPredicates) {
9206 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9210 ExitLimit EL = computeExitLimitFromCondImpl(
9211 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9212 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9216ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9217 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9218 bool ControlsOnlyExit,
bool AllowPredicates) {
9220 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9221 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9222 return *LimitFromBinOp;
9228 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9229 if (EL.hasFullInfo() || !AllowPredicates)
9233 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9253 const WithOverflowInst *WO;
9268 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9269 ControlsOnlyExit, AllowPredicates);
9270 if (EL.hasAnyInfo())
9275 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9278std::optional<ScalarEvolution::ExitLimit>
9279ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9283 bool AllowPredicates) {
9292 return std::nullopt;
9296 ExitLimit EL0 = computeExitLimitFromCondCached(
9297 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9298 ExitLimit EL1 = computeExitLimitFromCondCached(
9299 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9304 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9309 if (EitherMayExit) {
9319 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9321 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9324 EL1.ConstantMaxNotTaken);
9326 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9328 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9331 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9335 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9336 BECount = EL0.ExactNotTaken;
9349 SymbolicMaxBECount =
9351 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9355ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9356 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9357 bool AllowPredicates) {
9369 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9371 if (EL.hasAnyInfo())
9374 auto *ExhaustiveCount =
9375 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9378 return ExhaustiveCount;
9380 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9383ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9385 bool ControlsOnlyExit,
bool AllowPredicates) {
9410 ConstantRange CompRange =
9428 InnerLHS = ZExt->getOperand();
9475 if (EL.hasAnyInfo())
9492 if (EL.hasAnyInfo())
return EL;
9525 ControlsOnlyExit, AllowPredicates);
9526 if (EL.hasAnyInfo())
9544 ControlsOnlyExit, AllowPredicates);
9545 if (EL.hasAnyInfo())
9556ScalarEvolution::ExitLimit
9557ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9559 BasicBlock *ExitingBlock,
9560 bool ControlsOnlyExit) {
9561 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9564 if (
Switch->getDefaultDest() == ExitingBlock)
9568 "Default case must not exit the loop!");
9574 if (EL.hasAnyInfo())
9586 "Evaluation of SCEV at constant didn't fold correctly?");
9590ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9600 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9607 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9609 unsigned &OutShiftAmt) {
9610 using namespace PatternMatch;
9612 ConstantInt *ShiftAmt;
9614 OutOpCode = Instruction::LShr;
9616 OutOpCode = Instruction::AShr;
9618 OutOpCode = Instruction::Shl;
9623 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9638 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9640 unsigned &ShiftAmtOut) {
9641 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9657 if (MatchPositiveShift(
LHS, V, OpC, Amt)) {
9658 PostShiftOpCode = OpC;
9664 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9667 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9673 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9680 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9686 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9698 ConstantInt *StableValue =
nullptr;
9703 case Instruction::AShr: {
9710 if (
Known.isNonNegative())
9711 StableValue = ConstantInt::get(Ty, 0);
9712 else if (
Known.isNegative())
9713 StableValue = ConstantInt::get(Ty, -1,
true);
9719 case Instruction::LShr:
9720 case Instruction::Shl:
9730 "Otherwise cannot be an operand to a branch instruction");
9732 if (
Result->isNullValue()) {
9741 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9743 const SCEV *StartSCEV =
getSCEV(StartValue);
9747 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9748 MaxBTC = std::min(MaxBTC, RangeBTC);
9752 const SCEV *UpperBound =
9770 if (
const Function *
F = CI->getCalledFunction())
9780 if (!L->contains(
I))
return false;
9785 return L->getHeader() ==
I->getParent();
9864 if (!
I)
return nullptr;
9878 std::vector<Constant*>
Operands(
I->getNumOperands());
9880 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9889 if (!
C)
return nullptr;
9911 if (IncomingVal != CurrentVal) {
9914 IncomingVal = CurrentVal;
9926ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9929 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9938 DenseMap<Instruction *, Constant *> CurrentIterVals;
9940 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9946 for (PHINode &
PHI : Header->phis()) {
9948 CurrentIterVals[&
PHI] = StartCST;
9950 if (!CurrentIterVals.
count(PN))
9951 return RetVal =
nullptr;
9957 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9960 unsigned IterationNum = 0;
9962 for (; ; ++IterationNum) {
9963 if (IterationNum == NumIterations)
9964 return RetVal = CurrentIterVals[PN];
9968 DenseMap<Instruction *, Constant *> NextIterVals;
9973 NextIterVals[PN] = NextPHI;
9975 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9981 for (
const auto &
I : CurrentIterVals) {
9983 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9988 for (
const auto &
I : PHIsToCompute) {
9989 PHINode *
PHI =
I.first;
9992 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9995 if (NextPHI !=
I.second)
9996 StoppedEvolving =
false;
10001 if (StoppedEvolving)
10002 return RetVal = CurrentIterVals[PN];
10004 CurrentIterVals.swap(NextIterVals);
10008const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
10018 DenseMap<Instruction *, Constant *> CurrentIterVals;
10020 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10023 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
10025 for (PHINode &
PHI : Header->phis()) {
10027 CurrentIterVals[&
PHI] = StartCST;
10029 if (!CurrentIterVals.
count(PN))
10037 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10044 if (CondVal->getValue() ==
uint64_t(ExitWhen)) {
10045 ++NumBruteForceTripCountsComputed;
10050 DenseMap<Instruction *, Constant *> NextIterVals;
10056 for (
const auto &
I : CurrentIterVals) {
10058 if (!
PHI ||
PHI->getParent() != Header)
continue;
10061 for (PHINode *
PHI : PHIsToCompute) {
10063 if (NextPHI)
continue;
10065 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10068 CurrentIterVals.
swap(NextIterVals);
10079 auto &
Values = ValuesAtScopes[V];
10083 return LS.second ? LS.second :
SCEVUse(V);
10085 Values.emplace_back(L,
nullptr);
10088 SCEVUse C = computeSCEVAtScope(V, L);
10089 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10090 if (LS.first == L) {
10096 ValuesAtScopesUsers[
C.getPointer()].push_back({L, V});
10123 switch (V->getSCEVType()) {
10156 assert(!
C->getType()->isPointerTy() &&
10157 "Can only have one pointer, and it must be last");
10182const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10183 SmallVectorImpl<SCEVUse> &NewOps) {
10217SCEVUse ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10218 switch (
V->getSCEVType()) {
10229 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10240 for (++i; i !=
e; ++i)
10280 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10290 for (++i; i !=
e; ++i) {
10295 return getWithOperands(V, NewOps);
10310 const Loop *CurrLoop = this->LI[
I->getParent()];
10321 if (BackedgeTakenCount->
isZero()) {
10322 Value *InitValue =
nullptr;
10323 bool MultipleInitValues =
false;
10329 MultipleInitValues =
true;
10334 if (!MultipleInitValues && InitValue)
10343 unsigned InLoopPred =
10354 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10368 SmallVector<Constant *, 4>
Operands;
10370 bool MadeImprovement =
false;
10385 MadeImprovement |= OrigV != OpV;
10390 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10395 if (!MadeImprovement)
10416const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10418 return stripInjectiveFunctions(ZExt->getOperand());
10420 return stripInjectiveFunctions(SExt->getOperand());
10438 assert(
A != 0 &&
"A must be non-zero.");
10454 if (MinTZ < Mult2 && L->getLoopPredecessor())
10456 if (MinTZ < Mult2) {
10479 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10499static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10505 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10506 << *AddRec <<
'\n');
10509 if (!LC || !MC || !
NC) {
10510 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10511 return std::nullopt;
10517 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10525 N =
N.sext(NewWidth);
10526 M = M.sext(NewWidth);
10527 L = L.sext(NewWidth);
10544 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10545 <<
", multiplied by " <<
T <<
'\n');
10554 std::optional<APInt>
Y) {
10556 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10559 return XW.
slt(YW) ? *
X : *
Y;
10562 return std::nullopt;
10563 return X ? *
X : *
Y;
10580 return std::nullopt;
10581 unsigned W =
X->getBitWidth();
10601static std::optional<APInt>
10607 return std::nullopt;
10610 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10611 std::optional<APInt>
X =
10614 return std::nullopt;
10619 return std::nullopt;
10634static std::optional<APInt>
10638 "Starting value of addrec should be 0");
10639 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10640 <<
Range <<
", addrec " << *AddRec <<
'\n');
10644 "Addrec's initial value should be in range");
10650 return std::nullopt;
10660 auto SolveForBoundary =
10661 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10664 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10665 << Bound <<
" (before multiplying by " << M <<
")\n");
10668 std::optional<APInt> SO;
10671 "signed overflow\n");
10675 "unsigned overflow\n");
10676 std::optional<APInt> UO =
10679 auto LeavesRange = [&] (
const APInt &
X) {
10682 if (
Range.contains(V0->getValue()))
10687 if (
Range.contains(
V1->getValue()))
10696 return {std::nullopt,
false};
10701 if (LeavesRange(*Min))
10702 return { Min,
true };
10703 std::optional<APInt> Max = Min == SO ? UO : SO;
10704 if (LeavesRange(*Max))
10705 return { Max,
true };
10708 return {std::nullopt,
true};
10715 auto SL = SolveForBoundary(
Lower);
10716 auto SU = SolveForBoundary(
Upper);
10719 if (!SL.second || !SU.second)
10720 return std::nullopt;
10763ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10765 bool ControlsOnlyExit,
10766 bool AllowPredicates) {
10777 if (
C->getValue()->isZero())
return C;
10781 const SCEVAddRecExpr *AddRec =
10784 if (!AddRec && AllowPredicates)
10790 if (!AddRec || AddRec->
getLoop() != L)
10801 return ExitLimit(R, R, R,
false, Predicates);
10859 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10889 const SCEV *
Exact =
10897 const SCEV *SymbolicMax =
10899 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10908 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10916 return ExitLimit(
E, M, S,
false, Predicates);
10919ScalarEvolution::ExitLimit
10920ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10928 if (!
C->getValue()->isZero())
10938std::pair<const BasicBlock *, const BasicBlock *>
10939ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10950 if (
const Loop *L = LI.getLoopFor(BB))
10951 return {
L->getLoopPredecessor(),
L->getHeader()};
10953 return {
nullptr, BB};
10962 if (
A ==
B)
return true;
10977 if (ComputesEqualValues(AI, BI))
10985 const SCEV *Op0, *Op1;
11004 auto TrivialCase = [&](
bool TriviallyTrue) {
11013 const SCEV *NewLHS, *NewRHS;
11037 return TrivialCase(
false);
11038 return TrivialCase(
true);
11057 RAdd->hasNoSignedWrap()) ||
11059 RAdd->hasNoUnsignedWrap())) {
11079 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
11080 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
11083 C->getAPInt().isStrictlyPositive()) ||
11107 const APInt &
RA = RC->getAPInt();
11109 bool SimplifiedByConstantRange =
false;
11114 return TrivialCase(
true);
11116 return TrivialCase(
false);
11125 Changed = SimplifiedByConstantRange =
true;
11129 if (!SimplifiedByConstantRange) {
11146 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11152 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11158 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11164 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11184 return TrivialCase(
true);
11186 return TrivialCase(
false);
11291 auto NonRecursive = [OrNegative](
const SCEV *S) {
11293 return C->getAPInt().isPowerOf2() ||
11294 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11300 if (NonRecursive(S))
11310 const SCEV *S, uint64_t M,
11319 APInt C = Cst->getAPInt();
11320 return C.urem(M) == 0;
11326 const SCEV *SmodM =
11347 [&](
SCEVUse Op) { return isKnownMultipleOf(Op, M, Predicates); }))
11354 return isKnownMultipleOf(Op, M, Predicates);
11360 return isKnownMultipleOf(Op, M, Predicates);
11367 for (
auto *
A : *Predicates)
11368 if (
A->implies(
P, *
this))
11381std::pair<const SCEV *, const SCEV *>
11384 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11386 return { Start, Start };
11388 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11397 getUsedLoops(LHS, LoopsUsed);
11398 getUsedLoops(RHS, LoopsUsed);
11400 if (LoopsUsed.
empty())
11405 for (
const auto *L1 : LoopsUsed)
11406 for (
const auto *L2 : LoopsUsed)
11407 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11408 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11409 "Domination relationship is not a linear order");
11439 SplitRHS.second) &&
11449 isKnownPredicateViaSplitting(Pred, LHS, RHS) ||
11450 isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11460 return std::nullopt;
11475 if (KnownWithoutContext)
11476 return KnownWithoutContext;
11483 return std::nullopt;
11489 const Loop *L = LHS->getLoop();
11494std::optional<ScalarEvolution::MonotonicPredicateType>
11497 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11503 auto ResultSwapped =
11506 assert(*ResultSwapped != *Result &&
11507 "monotonicity should flip as we flip the predicate");
11514std::optional<ScalarEvolution::MonotonicPredicateType>
11515ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11529 return std::nullopt;
11533 "Should be greater or less!");
11537 if (!LHS->hasNoUnsignedWrap())
11538 return std::nullopt;
11542 "Relational predicate is either signed or unsigned!");
11543 if (!
LHS->hasNoSignedWrap())
11544 return std::nullopt;
11546 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11554 return std::nullopt;
11557std::optional<ScalarEvolution::LoopInvariantPredicate>
11564 return std::nullopt;
11571 if (!ArLHS || ArLHS->
getLoop() != L)
11572 return std::nullopt;
11577 Pred = Pred.dropSameSign();
11580 return std::nullopt;
11606 return std::nullopt;
11643 return std::nullopt;
11646std::optional<ScalarEvolution::LoopInvariantPredicate>
11651 Pred, LHS, RHS, L, CtxI, MaxIter))
11661 Pred, LHS, RHS, L, CtxI,
Op))
11663 return std::nullopt;
11666std::optional<ScalarEvolution::LoopInvariantPredicate>
11681 return std::nullopt;
11688 if (!AR || AR->
getLoop() != L)
11689 return std::nullopt;
11694 Pred = Pred.dropSameSign();
11698 return std::nullopt;
11704 if (Step != One && Step != MinusOne)
11705 return std::nullopt;
11711 return std::nullopt;
11717 return std::nullopt;
11725 if (Step == MinusOne)
11729 return std::nullopt;
11735bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11741 auto CheckRange = [&](
bool IsSigned) {
11744 return RangeLHS.
icmp(Pred, RangeRHS);
11753 if (CheckRange(
true) || CheckRange(
false))
11762bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11770 SCEVUse XNonConstOp, XConstOp;
11771 SCEVUse YNonConstOp, YConstOp;
11776 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11777 XConstOp =
nullptr;
11784 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11785 YConstOp =
nullptr;
11790 if (YNonConstOp != XNonConstOp)
11863bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11884bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11885 const SCEV *
LHS,
const SCEV *
RHS) {
11890 return any_of(*BB, [&](
const Instruction &
I) {
11891 using namespace llvm::PatternMatch;
11896 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11910 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11915 "This cannot be done on broken IR!");
11918 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11927 if (LoopContinuePredicate &&
11928 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11929 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11934 if (WalkingBEDominatingConds)
11940 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11941 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11948 const SCEV *LoopCounter =
11956 for (
auto &AssumeVH : AC.assumptions()) {
11963 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11967 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11970 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11971 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11972 assert(DTN &&
"should reach the loop header before reaching the root!");
11975 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11993 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
12006 if (!DT.isReachableFromEntry(BB))
12010 "This cannot be done on broken IR!");
12018 const bool ProvingStrictComparison =
12020 bool ProvedNonStrictComparison =
false;
12021 bool ProvedNonEquality =
false;
12024 if (!ProvedNonStrictComparison)
12025 ProvedNonStrictComparison = Fn(NonStrictPredicate);
12026 if (!ProvedNonEquality)
12028 if (ProvedNonStrictComparison && ProvedNonEquality)
12033 if (ProvingStrictComparison) {
12035 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
12037 if (SplitAndProve(ProofFn))
12042 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
12044 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
12046 if (ProvingStrictComparison) {
12048 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
12050 if (SplitAndProve(ProofFn))
12059 const Loop *ContainingLoop = LI.getLoopFor(BB);
12061 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
12065 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
12066 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
12069 if (!BlockEntryPredicate)
12078 for (
auto &AssumeVH : AC.assumptions()) {
12082 if (!DT.dominates(CI, BB))
12085 if (ProveViaCond(CI->getArgOperand(0),
false))
12091 F.getParent(), Intrinsic::experimental_guard);
12093 for (
const auto *GU : GuardDecl->users())
12095 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12096 if (ProveViaCond(Guard->getArgOperand(0),
false))
12111 "LHS is not available at Loop Entry");
12113 "RHS is not available at Loop Entry");
12115 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12126 if (FoundCondValue ==
12130 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12134 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12137 const Value *Op0, *Op1;
12140 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12144 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12145 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12149 if (!ICI)
return false;
12153 CmpPredicate FoundPred;
12162 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12165bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12166 const SCEV *
RHS, CmpPredicate FoundPred,
12167 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12168 const Instruction *CtxI) {
12178 auto *WideType = FoundLHS->
getType();
12190 TruncFoundLHS, TruncFoundRHS, CtxI))
12216 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12220bool ScalarEvolution::isImpliedCondBalancedTypes(
12225 "Types should be balanced!");
12232 if (FoundLHS == FoundRHS)
12236 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12248 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12263 LHS, FoundLHS, FoundRHS, CtxI);
12265 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12277 if (IsSignFlippedPredicate(Pred, FoundPred) &&
12278 isImpliedCondViaSignFlippedPred(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12281 if (IsSignFlippedPredicate(SwappedPred, FoundPred) &&
12282 isImpliedCondViaSignFlippedPred(SwappedPred,
RHS,
LHS, FoundLHS, FoundRHS,
12290 const SCEVConstant *
C =
nullptr;
12291 const SCEV *
V =
nullptr;
12309 if (Min ==
C->getAPInt()) {
12314 APInt SharperMin = Min + 1;
12317 case ICmpInst::ICMP_SGE:
12318 case ICmpInst::ICMP_UGE:
12321 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12326 case ICmpInst::ICMP_SGT:
12327 case ICmpInst::ICMP_UGT:
12337 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12342 case ICmpInst::ICMP_SLE:
12343 case ICmpInst::ICMP_ULE:
12344 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12345 LHS, V, getConstant(SharperMin), CtxI))
12349 case ICmpInst::ICMP_SLT:
12350 case ICmpInst::ICMP_ULT:
12351 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12352 LHS, V, getConstant(Min), CtxI))
12366 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12370 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12373 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12380bool ScalarEvolution::isImpliedCondViaSignFlippedPred(
12381 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12382 const SCEV *FoundRHS,
const Instruction *CtxI) {
12387 isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12411 CmpPredicate BoundPred =
12413 if (isKnownViaNonRecursiveReasoning(BoundPred, FoundRHS, SignedMin)) {
12416 if (isImpliedCondOperands(Pred,
LHS,
RHS, Bound, FoundLHS, CtxI))
12424 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS))
12431 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS))
12446std::optional<APInt>
12453 APInt DiffMul(BW, 1);
12456 for (
unsigned I = 0;
I < 8; ++
I) {
12465 if (LAR->getLoop() != MAR->getLoop())
12466 return std::nullopt;
12470 if (!LAR->isAffine() || !MAR->isAffine())
12471 return std::nullopt;
12473 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12474 return std::nullopt;
12476 Less = LAR->getStart();
12477 More = MAR->getStart();
12482 auto MatchConstMul =
12483 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12488 return std::nullopt;
12490 if (
auto MatchedMore = MatchConstMul(More)) {
12491 if (
auto MatchedLess = MatchConstMul(
Less)) {
12492 if (MatchedMore->second == MatchedLess->second) {
12493 More = MatchedMore->first;
12494 Less = MatchedLess->first;
12495 DiffMul *= MatchedMore->second;
12506 Diff +=
C->getAPInt() * DiffMul;
12509 Diff -=
C->getAPInt() * DiffMul;
12512 Multiplicity[S] +=
Mul;
12514 auto Decompose = [&](
const SCEV *S,
int Mul) {
12521 Decompose(More, 1);
12522 Decompose(
Less, -1);
12526 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12527 for (
const auto &[S,
Mul] : Multiplicity) {
12532 return std::nullopt;
12534 }
else if (
Mul == -1) {
12536 return std::nullopt;
12539 return std::nullopt;
12543 if (NewMore == More || NewLess ==
Less)
12544 return std::nullopt;
12550 if (!More && !
Less)
12554 if (!More || !
Less)
12555 return std::nullopt;
12559 return std::nullopt;
12562bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12584 const auto *Latch = L->getLoopLatch();
12587 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12596 const auto *Latch = L->getLoopLatch();
12599 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12609bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12612 const SCEV *FoundLHS,
12613 const SCEV *FoundRHS) {
12622 if (!AddRecFoundLHS)
12629 const Loop *
L = AddRecFoundLHS->getLoop();
12630 if (L != AddRecLHS->getLoop())
12669 if (!RDiff || *LDiff != *RDiff)
12672 if (LDiff->isMinValue())
12675 APInt FoundRHSLimit;
12678 FoundRHSLimit = -(*RDiff);
12690bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12691 const SCEV *
RHS,
const SCEV *FoundLHS,
12692 const SCEV *FoundRHS,
unsigned Depth) {
12693 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12697 bool Erased = PendingMerges.erase(LPhi);
12698 assert(Erased &&
"Failed to erase LPhi!");
12702 bool Erased = PendingMerges.erase(RPhi);
12703 assert(Erased &&
"Failed to erase RPhi!");
12711 if (!PendingMerges.insert(Phi).second)
12725 if (!PendingMerges.insert(Phi).second)
12731 if (!LPhi && !RPhi)
12742 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12746 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12747 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12748 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12749 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12752 if (RPhi && RPhi->getParent() == LBB) {
12759 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12760 if (!ProvedEasily(L, R))
12771 auto *RLoop = RAR->
getLoop();
12772 auto *Predecessor = RLoop->getLoopPredecessor();
12773 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12775 if (!ProvedEasily(L1, RAR->
getStart()))
12777 auto *Latch = RLoop->getLoopLatch();
12778 assert(Latch &&
"Loop with AddRec with no latch?");
12799 if (
auto *
Loop = LI.getLoopFor(LBB))
12802 if (!ProvedEasily(L,
RHS))
12809bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12812 const SCEV *FoundLHS,
12813 const SCEV *FoundRHS) {
12816 if (
RHS == FoundRHS) {
12821 if (
LHS != FoundLHS)
12828 Value *Shiftee, *ShiftValue;
12830 using namespace PatternMatch;
12831 if (
match(SUFoundRHS->getValue(),
12833 auto *ShifteeS =
getSCEV(Shiftee);
12851bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12852 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12853 const SCEV *FoundRHS) {
12885 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12893 return Diff == FoundDiff;
12896bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12898 const SCEV *FoundLHS,
12899 const SCEV *FoundRHS,
12900 const Instruction *CtxI) {
12901 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12903 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12905 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12906 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12908 isImpliedCondOperandsViaMatchingDiff(Pred,
LHS,
RHS, FoundLHS,
12910 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12914template <
typename MinMaxExprType>
12916 const SCEV *Candidate) {
12921 return is_contained(MinMaxExpr->operands(), Candidate);
12934 const SCEV *LStart, *RStart, *Step;
13031bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
13033 const SCEV *FoundLHS,
13034 const SCEV *FoundRHS,
13038 "LHS and RHS have different sizes?");
13041 "FoundLHS and FoundRHS have different sizes?");
13075 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
13077 return Ext->getOperand();
13084 auto *OrigLHS =
LHS;
13085 auto *OrigFoundLHS = FoundLHS;
13086 LHS = GetOpFromSExt(
LHS);
13087 FoundLHS = GetOpFromSExt(FoundLHS);
13090 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
13093 FoundRHS,
Depth + 1);
13110 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
13111 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
13116 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
13122 using namespace llvm::PatternMatch;
13141 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13149 auto *DTy = Denominator->getType();
13150 auto *FRHSTy = FoundRHS->
getType();
13151 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13170 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13181 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13183 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13191 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13224bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13228 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13232 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13235bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13238 const SCEV *FoundLHS,
13239 const SCEV *FoundRHS) {
13245 if (isKnownViaNonRecursiveReasoning(NonStrictPred,
LHS, FoundLHS) &&
13246 isKnownViaNonRecursiveReasoning(
13252 return isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
13255bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13256 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13257 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13271 ConstantRange FoundLHSRange =
13275 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13282 return LHSRange.
icmp(Pred, ConstRHS);
13285bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13286 bool IsSigned,
bool Invert) {
13293 APInt MaxRHS = getRangeMax(
RHS,
true, Invert);
13298 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13301 APInt MaxRHS = getRangeMax(
RHS,
false, Invert);
13306 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13319ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
const SCEV *Stride,
13321 bool IsSigned,
bool Invert) {
13336 APInt MinStart = getRangeMin(Start, IsSigned, Invert);
13349 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13355 APInt MaxEnd = getRangeMax(
End, IsSigned, Invert);
13361 :
APIntOps::umax(MaxEnd, MinStart);
13363 APInt Delta = MaxEnd - MinStart;
13367 const SCEV *DeltaExpr =
13375ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13376 const Loop *L,
bool IsSigned,
bool Invert,
13377 bool ControlsOnlyExit,
bool AllowPredicates) {
13387 bool PredicatedIV =
false;
13389 if (!
IV && !Invert) {
13393 auto canProveNUW = [&]() {
13396 if (!ControlsOnlyExit)
13417 Limit = Limit.
zext(OuterBitWidth);
13429 Type *Ty = ZExt->getType();
13439 if (!
IV && AllowPredicates) {
13444 PredicatedIV =
true;
13448 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13462 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13469 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13472 const SCEV *GuardedStride = Stride;
13476 bool IVMayOverflow =
true;
13480 if (!PositiveStride) {
13483 GuardedStride = LoopGuardedStride;
13484 PositiveStride =
true;
13491 if (!PositiveStride) {
13540 const SCEVPredicate *
P =
13561 auto wouldZeroStrideBeUB = [&]() {
13573 if (!wouldZeroStrideBeUB()) {
13580 IVMayOverflow = canIVOverflowOnLT(
RHS, GuardedStride, IsSigned, Invert) &&
13582 GuardedStride, IsSigned, Invert);
13583 if (IVMayOverflow && !NoWrap)
13596 const SCEV *
Start =
IV->getStart();
13602 const SCEV *OrigStart =
Start;
13603 const SCEV *OrigRHS =
RHS;
13604 if (
Start->getType()->isPointerTy()) {
13618 assert(!Invert &&
"RHS must be loop-invariant for Invert");
13620 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13621 any(RHSAddRec->getNoWrapFlags())) {
13634 const SCEV *RHSStart = RHSAddRec->getStart();
13635 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13647 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13656 BECountIfBackedgeTaken =
13683 bool AddingStrideMinusOneMayOverflow = IVMayOverflow && [&] {
13730 if (!Invert && (Start == Stride || Start ==
getMinusSCEV(Stride, One))) {
13747 auto StepBack = [&](
const SCEV *
V,
const SCEV *
Offset) ->
const SCEV * {
13752 auto Distance = [&](
const SCEV *From,
const SCEV *To) {
13756 const SCEV *OrigPrevStart = StepBack(OrigStart, Stride);
13763 if ((!AddingStrideMinusOneMayOverflow ||
13795 const SCEV *Numerator =
13801 auto canProveRHSIsAtOrBeyondStart = [&]() {
13806 auto SwapIfInverted = [&](
const SCEV *
A,
const SCEV *
B) {
13807 return Invert ? std::pair(
B,
A) : std::pair(
A,
B);
13816 auto [GELHS, GERHS] = SwapIfInverted(OrigRHS, OrigStart);
13821 if ((GuardedRHS != GELHS || GuardedStart != GERHS) &&
13835 auto [GTLHS, GTRHS] = SwapIfInverted(OrigRHS, StepBack(OrigStart, One));
13841 if (canProveRHSIsAtOrBeyondStart()) {
13864 const SCEV *Delta = Distance(Start,
End);
13865 if (!AddingStrideMinusOneMayOverflow) {
13877 const SCEV *ConstantMaxBECount;
13878 bool MaxOrZero =
false;
13880 ConstantMaxBECount = BECount;
13882 ConstantMaxBECount = computeMaxBECountForLT(
13889 const APInt *IfTaken, *RangeMax;
13892 IfTaken->
ugt(*RangeMax)) {
13893 ConstantMaxBECount =
getZero(BECountIfBackedgeTaken->getType());
13895 ConstantMaxBECount = BECountIfBackedgeTaken;
13905 const SCEV *SymbolicMaxBECount =
13907 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13913 if (
Range.isFullSet())
13918 if (!SC->getValue()->isZero()) {
13924 return ShiftedAddRec->getNumIterationsInRange(
13925 Range.subtract(SC->getAPInt()), SE);
13969 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13970 "Linear scev computation is off in a bad way!");
14001 assert(!
Last->isZero() &&
"Recurrency with zero step?");
14034 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14036 SE->ConstantEvolutionLoopExitValue.erase(PN);
14037 SE->eraseValueFromMap(getValPtr());
14041void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
14042 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14052 : CallbackVH(
V), SE(se) {}
14061 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
14063 LoopDispositions(64), BlockDispositions(64) {
14075 F.getParent(), Intrinsic::experimental_guard);
14076 HasGuards = GuardDecl && !GuardDecl->use_empty();
14080 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
14081 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14082 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14083 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14084 PendingMerges(
std::
move(Arg.PendingMerges)),
14085 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14086 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14087 PredicatedBackedgeTakenCounts(
14088 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14089 BECountUsers(
std::
move(Arg.BECountUsers)),
14090 ConstantEvolutionLoopExitValue(
14091 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14092 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14093 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14094 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14095 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14096 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14097 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14098 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14099 SignedRanges(
std::
move(Arg.SignedRanges)),
14100 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14101 UniquePreds(
std::
move(Arg.UniquePreds)),
14102 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14103 ConstantSCEVs(
std::
move(Arg.ConstantSCEVs)),
14104 LoopUsers(
std::
move(Arg.LoopUsers)),
14105 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14106 FirstUnknown(Arg.FirstUnknown),
14107 NextUnknownOrderID(Arg.NextUnknownOrderID) {
14108 Arg.FirstUnknown =
nullptr;
14117 Tmp->~SCEVUnknown();
14119 FirstUnknown =
nullptr;
14121 ExprValueMap.clear();
14122 ValueExprMap.clear();
14124 BackedgeTakenCounts.clear();
14125 PredicatedBackedgeTakenCounts.clear();
14127 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14128 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14129 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14130 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14152 L->getHeader()->printAsOperand(OS,
false);
14156 L->getExitingBlocks(ExitingBlocks);
14157 if (ExitingBlocks.
size() != 1)
14158 OS <<
"<multiple exits> ";
14162 OS <<
"backedge-taken count is ";
14165 OS <<
"Unpredictable backedge-taken count.";
14168 if (ExitingBlocks.
size() > 1)
14169 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14170 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14178 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14181 OS <<
"\n Predicates:\n";
14182 for (
const auto *
P : Predicates)
14190 L->getHeader()->printAsOperand(OS,
false);
14195 OS <<
"constant max backedge-taken count is ";
14198 OS <<
", actual taken count either this or zero.";
14200 OS <<
"Unpredictable constant max backedge-taken count. ";
14205 L->getHeader()->printAsOperand(OS,
false);
14210 OS <<
"symbolic max backedge-taken count is ";
14213 OS <<
", actual taken count either this or zero.";
14215 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14219 if (ExitingBlocks.
size() > 1)
14220 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14221 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14231 OS <<
"\n predicated symbolic max exit count for "
14232 << ExitingBlock->
getName() <<
": ";
14234 OS <<
"\n Predicates:\n";
14235 for (
const auto *
P : Predicates)
14246 L->getHeader()->printAsOperand(OS,
false);
14249 OS <<
"Predicated backedge-taken count is ";
14252 OS <<
"Unpredictable predicated backedge-taken count.";
14254 OS <<
" Predicates:\n";
14255 for (
const auto *
P : Preds)
14260 auto *PredConstantMax =
14262 if (PredConstantMax != ConstantBTC) {
14264 L->getHeader()->printAsOperand(OS,
false);
14267 OS <<
"Predicated constant max backedge-taken count is ";
14270 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14272 OS <<
" Predicates:\n";
14273 for (
const auto *
P : Preds)
14278 auto *PredSymbolicMax =
14280 if (SymbolicBTC != PredSymbolicMax) {
14282 L->getHeader()->printAsOperand(OS,
false);
14285 OS <<
"Predicated symbolic max backedge-taken count is ";
14288 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14290 OS <<
" Predicates:\n";
14291 for (
const auto *
P : Preds)
14297 L->getHeader()->printAsOperand(OS,
false);
14324 OS <<
"Computable";
14334 OS <<
"DoesNotDominate";
14340 OS <<
"ProperlyDominates";
14357 OS <<
"Classifying expressions for: ";
14358 F.printAsOperand(OS,
false);
14373 const Loop *L = LI.getLoopFor(
I.getParent());
14388 OS <<
"\t\t" "Exits: ";
14391 OS <<
"<<Unknown>>";
14397 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14399 Iter->getHeader()->printAsOperand(OS,
false);
14407 InnerL->getHeader()->printAsOperand(OS,
false);
14418 OS <<
"Determining loop execution counts for: ";
14419 F.printAsOperand(OS,
false);
14430 auto &
Values = LoopDispositions[S];
14431 for (
auto &V :
Values) {
14432 if (V.getPointer() == L)
14437 auto &Values2 = LoopDispositions[S];
14439 if (V.getPointer() == L) {
14448ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14466 if (L->contains(AR->
getLoop()) &&
14468 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14473 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14474 " dominate the contained loop's header?");
14501 bool HasVarying =
false;
14502 bool HasUniform =
false;
14547 auto &
Values = BlockDispositions[S];
14548 for (
auto &V :
Values) {
14549 if (V.getPointer() == BB)
14554 auto &Values2 = BlockDispositions[S];
14556 if (V.getPointer() == BB) {
14565ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14594 bool Proper =
true;
14605 if (Instruction *
I =
14607 if (
I->getParent() == BB)
14609 if (DT.properlyDominates(
I->getParent(), BB))
14628void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14631 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14632 auto It = BECounts.find(L);
14633 if (It != BECounts.end()) {
14634 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14635 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14637 auto UserIt = BECountUsers.find(S);
14638 assert(UserIt != BECountUsers.end());
14643 BECounts.erase(It);
14651 while (!Worklist.
empty()) {
14653 auto Users = SCEVUsers.find(Curr);
14654 if (
Users != SCEVUsers.end())
14655 for (
const auto *User :
Users->second)
14656 if (ToForget.
insert(User).second)
14660 for (
const auto *S : ToForget)
14661 forgetMemoizedResultsImpl(S);
14663 PredicatedSCEVRewrites.remove_if(
14664 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14667void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14668 LoopDispositions.erase(S);
14669 BlockDispositions.erase(S);
14670 UnsignedRanges.erase(S);
14671 SignedRanges.erase(S);
14672 HasRecMap.erase(S);
14673 ConstantMultipleCache.erase(S);
14676 UnsignedWrapViaInductionTried.erase(AR);
14677 SignedWrapViaInductionTried.erase(AR);
14680 auto ExprIt = ExprValueMap.find(S);
14681 if (ExprIt != ExprValueMap.end()) {
14682 for (
Value *V : ExprIt->second) {
14683 auto ValueIt = ValueExprMap.find_as(V);
14684 if (ValueIt != ValueExprMap.end())
14685 ValueExprMap.erase(ValueIt);
14687 ExprValueMap.erase(ExprIt);
14690 auto ScopeIt = ValuesAtScopes.find(S);
14691 if (ScopeIt != ValuesAtScopes.end()) {
14692 for (
const auto &Pair : ScopeIt->second)
14694 llvm::erase(ValuesAtScopesUsers[Pair.second.getPointer()],
14695 std::make_pair(Pair.first, S));
14696 ValuesAtScopes.erase(ScopeIt);
14699 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14700 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14701 for (
const auto &Pair : ScopeUserIt->second)
14704 llvm::erase_if(ValuesAtScopes[Pair.second], [&](
const auto &LS) {
14705 return LS.first == Pair.first && LS.second.getPointer() == S;
14707 ValuesAtScopesUsers.erase(ScopeUserIt);
14710 auto BEUsersIt = BECountUsers.find(S);
14711 if (BEUsersIt != BECountUsers.end()) {
14713 auto Copy = BEUsersIt->second;
14714 for (
const auto &Pair : Copy)
14715 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14716 BECountUsers.erase(BEUsersIt);
14719 auto FoldUser = FoldCacheUser.find(S);
14720 if (FoldUser != FoldCacheUser.end())
14721 for (
auto &KV : FoldUser->second)
14722 FoldCache.erase(KV);
14723 FoldCacheUser.erase(S);
14727ScalarEvolution::getUsedLoops(
const SCEV *S,
14729 struct FindUsedLoops {
14730 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14731 : LoopsUsed(LoopsUsed) {}
14732 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14733 bool follow(
const SCEV *S) {
14739 bool isDone()
const {
return false; }
14742 FindUsedLoops
F(LoopsUsed);
14743 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14746void ScalarEvolution::getReachableBlocks(
14749 Worklist.
push_back(&F.getEntryBlock());
14750 while (!Worklist.
empty()) {
14752 if (!Reachable.
insert(BB).second)
14760 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14767 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14771 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14806 SCEVMapper SCM(SE2);
14808 SE2.getReachableBlocks(ReachableBlocks, F);
14810 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14828 while (!LoopStack.
empty()) {
14834 if (!ReachableBlocks.
contains(L->getHeader()))
14839 auto It = BackedgeTakenCounts.find(L);
14840 if (It == BackedgeTakenCounts.end())
14844 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14864 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14865 if (Delta && !Delta->
isZero()) {
14866 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14867 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14868 dbgs() <<
"New: " << *NewBECount <<
"\n";
14869 dbgs() <<
"Delta: " << *Delta <<
"\n";
14877 while (!Worklist.
empty()) {
14879 if (ValidLoops.
insert(L).second)
14880 Worklist.
append(L->begin(), L->end());
14882 for (
const auto &KV : ValueExprMap) {
14887 "AddRec references invalid loop");
14892 auto It = ExprValueMap.find(KV.second);
14893 if (It == ExprValueMap.end() || !
is_contained(It->second, KV.first)) {
14894 dbgs() <<
"Value " << *KV.first
14895 <<
" is in ValueExprMap but not in ExprValueMap\n";
14900 if (!ReachableBlocks.
contains(
I->getParent()))
14902 const SCEV *OldSCEV = SCM.visit(KV.second);
14904 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14905 if (Delta && !Delta->
isZero()) {
14906 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14907 <<
"Old: " << *OldSCEV <<
"\n"
14908 <<
"New: " << *NewSCEV <<
"\n"
14909 <<
"Delta: " << *Delta <<
"\n";
14915 for (
const auto &KV : ExprValueMap) {
14916 for (
Value *V : KV.second) {
14917 const SCEV *S = ValueExprMap.lookup(V);
14919 dbgs() <<
"Value " << *V
14920 <<
" is in ExprValueMap but not in ValueExprMap\n";
14923 if (S != KV.first) {
14924 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14925 << *KV.first <<
"\n";
14932 for (
const auto &S : UniqueSCEVs) {
14937 auto It = SCEVUsers.find(
Op);
14938 if (It != SCEVUsers.end() && It->second.count(&S))
14940 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14941 <<
" is not being tracked!\n";
14947 for (
const auto &ValueAndVec : ValuesAtScopes) {
14949 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14950 const Loop *L = LoopAndValueAtScope.first;
14951 SCEVUse ValueAtScope = LoopAndValueAtScope.second;
14953 auto It = ValuesAtScopesUsers.find(ValueAtScope.
getPointer());
14954 if (It != ValuesAtScopesUsers.end() &&
14957 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14958 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14964 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14965 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14966 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14967 const Loop *L = LoopAndValue.first;
14968 const SCEV *
Value = LoopAndValue.second;
14970 auto It = ValuesAtScopes.find(
Value);
14973 if (It != ValuesAtScopes.end() &&
any_of(It->second, [&](
const auto &LS) {
14974 return LS.first == L && LS.second.getPointer() == ValueAtScope;
14977 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14978 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14984 auto VerifyBECountUsers = [&](
bool Predicated) {
14986 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14987 for (
const auto &LoopAndBEInfo : BECounts) {
14988 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14989 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14991 auto UserIt = BECountUsers.find(S);
14992 if (UserIt != BECountUsers.end() &&
14993 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14995 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14996 <<
" missing from BECountUsers\n";
15003 VerifyBECountUsers(
false);
15004 VerifyBECountUsers(
true);
15007 for (
auto &[S,
Values] : LoopDispositions) {
15008 for (
auto [
Loop, CachedDisposition] :
Values) {
15010 if (CachedDisposition != RecomputedDisposition) {
15011 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
15012 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
15013 << RecomputedDisposition <<
"\n";
15020 for (
auto &[S,
Values] : BlockDispositions) {
15021 for (
auto [BB, CachedDisposition] :
Values) {
15023 if (CachedDisposition != RecomputedDisposition) {
15024 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
15025 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
15026 <<
", actual " << RecomputedDisposition <<
"\n";
15033 for (
auto [
FoldID, Expr] : FoldCache) {
15034 auto I = FoldCacheUser.find(Expr);
15035 if (
I == FoldCacheUser.end()) {
15036 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
15041 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
15045 for (
auto [Expr, IDs] : FoldCacheUser) {
15046 for (
auto &
FoldID : IDs) {
15049 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
15054 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
15055 <<
" != " << *Expr <<
"!\n";
15066 for (
auto [S, Multiple] : ConstantMultipleCache) {
15068 if ((Multiple != 0 && RecomputedMultiple != 0 &&
15069 Multiple.
urem(RecomputedMultiple) != 0 &&
15070 RecomputedMultiple.
urem(Multiple) != 0)) {
15071 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
15072 << *S <<
" : Computed " << RecomputedMultiple
15073 <<
" but cache contains " << Multiple <<
"!\n";
15081 FunctionAnalysisManager::Invalidator &Inv) {
15113 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15114 <<
F.getName() <<
"':\n";
15120 "Scalar Evolution Analysis",
false,
true)
15169 const SCEV *LHS,
const SCEV *RHS) {
15171 assert(LHS->getType() == RHS->getType() &&
15172 "Type mismatch between LHS and RHS");
15175 ID.AddInteger(Pred);
15176 ID.AddPointer(LHS);
15177 ID.AddPointer(RHS);
15179 if (
const auto *S = UniquePreds.lookup(ID, Token))
15183 UniquePreds.insert(Eq, Token);
15194 ID.AddInteger(AddedFlags);
15196 if (
const auto *S = UniquePreds.lookup(ID, Token))
15198 auto *OF =
new (SCEVAllocator)
15200 UniquePreds.insert(OF, Token);
15220 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15221 return Rewriter.visit(S);
15227 for (
const auto *Pred : U->getPredicates())
15229 if (IPred->getLHS() == Expr &&
15231 return IPred->getRHS();
15233 if (IPred->getLHS() == Expr &&
15234 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15235 return IPred->getRHS();
15238 return convertToAddRecWithPreds(Expr);
15241 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15257 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15274 explicit SCEVPredicateRewriter(
15275 const Loop *L, ScalarEvolution &SE,
15276 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15277 const SCEVPredicate *Pred)
15278 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15280 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15283 return Pred && Pred->
implies(
P, SE);
15289 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15292 return addOverflowAssumption(
A);
15301 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15305 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15307 if (!PredicatedRewrite)
15309 for (
const auto *
P : PredicatedRewrite->second){
15312 if (L != WP->getExpr()->getLoop())
15315 if (!addOverflowAssumption(
P))
15318 return PredicatedRewrite->first;
15321 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15322 const SCEVPredicate *Pred;
15331 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15338 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15358 if (!Step->
isOne())
15383 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15384 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15397 return Op->LHS == LHS &&
Op->RHS == RHS;
15404 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15406 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15431 const SCEV *Start = AR->getStart();
15432 const SCEV *OpStart =
Op->AR->getStart();
15437 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15446 const SCEV *Step = AR->getStepRecurrence(SE);
15447 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15468 SCEVFlags ScevFlags = AR->getNoWrapFlags();
15490 for (
const auto *
P : Preds)
15503 return this->implies(I, SE);
15515 const Loop *L = NWrap->getExpr()->getLoop();
15522 return RewrittenAR &&
15528 for (
const auto *Pred : Preds)
15529 Pred->print(OS,
Depth);
15534 for (
const auto *Pred : Set->Preds)
15542 bool CheckImplies = Preds.
size() < 16;
15545 if (CheckImplies &&
implies(
N, SE))
15551 for (
auto *
P : Preds) {
15552 if (CheckImplies &&
N->implies(
P, SE))
15556 Preds = std::move(PrunedPreds);
15557 Preds.push_back(
N);
15564 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15573 SCEVUsers[
Op].insert(
User);
15577 const SCEV *Expr = SE.getSCEV(V);
15582 RewriteEntry &Entry = RewriteMap[Expr];
15585 if (Entry.second && Generation == Entry.first)
15586 return Entry.second;
15591 Expr = Entry.second;
15593 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15594 Entry = {Generation, NewSCEV};
15600 if (!BackedgeCount) {
15602 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15603 for (
const auto *
P : Preds)
15606 return BackedgeCount;
15610 if (!SymbolicMaxBackedgeCount) {
15612 SymbolicMaxBackedgeCount =
15613 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15614 for (
const auto *
P : Preds)
15617 return SymbolicMaxBackedgeCount;
15621 if (!SmallConstantMaxTripCount) {
15623 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15624 for (
const auto *
P : Preds)
15627 return *SmallConstantMaxTripCount;
15631 if (Preds->implies(&Pred, SE))
15634 Preds = std::make_unique<SCEVUnionPredicate>(Preds->getUnionWith(&Pred, SE));
15635 updateGeneration();
15648void PredicatedScalarEvolution::updateGeneration() {
15650 if (++Generation == 0) {
15651 for (
auto &
II : RewriteMap) {
15652 const SCEV *Rewritten =
II.second.second;
15662 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15668 ExtraPreds->
append(NewPreds);
15674 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15680 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15682 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15686 for (
auto *BB : L.getBlocks())
15687 for (
auto &
I : *BB) {
15688 if (!SE.isSCEVable(
I.getType()))
15691 auto *Expr = SE.getSCEV(&
I);
15692 auto II = RewriteMap.find(Expr);
15694 if (
II == RewriteMap.end())
15698 if (
II->second.second == Expr)
15703 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15707void ScalarEvolution::LoopGuards::collectPending() {
15708 const Loop *L = PendingLoop;
15711 PendingLoop =
nullptr;
15716 collectFromBlock(SE, *
this, L->getHeader(), Pred,
VisitedBlocks);
15719void ScalarEvolution::LoopGuards::collectFromPHI(
15727 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15728 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15742 auto &RewriteMap =
G->second.RewriteMap;
15743 if (RewriteMap.empty())
15745 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15746 if (S == RewriteMap.end())
15752 return {
C0, SM->getSCEVType()};
15755 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15756 MinMaxPattern
P2) -> MinMaxPattern {
15758 auto [C2, T2] =
P2;
15759 if (!
C1 || !C2 ||
T1 != T2)
15763 return {
C1->getAPInt().ult(C2->getAPInt()) ?
C1 : C2,
T1};
15765 return {
C1->getAPInt().slt(C2->getAPInt()) ?
C1 : C2,
T1};
15767 return {
C1->getAPInt().ugt(C2->getAPInt()) ?
C1 : C2,
T1};
15769 return {
C1->getAPInt().sgt(C2->getAPInt()) ?
C1 : C2,
T1};
15774 auto P = GetMinMaxConst(0);
15775 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15778 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15781 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15784 Guards.RewriteMap.insert({
LHS,
RHS});
15792 const APInt &DivisorVal,
15794 const APInt *ExprVal;
15807 const APInt &DivisorVal,
15809 const APInt *ExprVal;
15817 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15831 const SCEV *URemRHS =
nullptr;
15835 const SCEV *Multiple =
15837 DivInfo[URemLHS] = Multiple;
15839 Multiples[URemLHS] =
C->getAPInt();
15859 auto IsMinMaxSCEVWithNonNegativeConstant =
15863 if (
MinMax->getNumOperands() != 2)
15866 if (
C->getAPInt().isNegative())
15868 SCTy =
MinMax->getSCEVType();
15877 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15879 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15884 auto *DivisibleExpr =
15892void ScalarEvolution::LoopGuards::collectFromBlock(
15894 const BasicBlock *
Block,
const BasicBlock *Pred,
15902 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15913 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15915 if (From == FromRewritten)
15917 RewriteMap[From] = To;
15923 auto GetMaybeRewritten = [&](
const SCEV *S) {
15924 return RewriteMap.lookup_or(S, S);
15931 const SCEV *MatchLHS,
15932 const SCEV *MatchRHS) {
15933 const SCEVConstant *
C1;
15936 if (!
match(MatchLHS,
15943 .
sub(
C1->getAPInt());
15948 const SCEV *RewrittenLHS = GetMaybeRewritten(LHSUnknown);
15949 ExactRegion = ExactRegion.intersectWith(SE.
getUnsignedRange(RewrittenLHS),
15954 if (ExactRegion.isEmptySet() || ExactRegion.isWrappedSet() ||
15955 ExactRegion.isFullSet())
15958 const SCEV *RegionMin = SE.
getConstant(ExactRegion.getUnsignedMin());
15959 const SCEV *RegionMax = SE.
getConstant(ExactRegion.getUnsignedMax());
15960 const SCEV *ClampedLHS =
15962 AddRewrite(LHSUnknown, RewrittenLHS, ClampedLHS);
15965 if (MatchRangeCheckIdiom(Predicate,
LHS,
RHS))
15978 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15980 const APInt &DividesBy =
15995 switch (Predicate) {
16024 SmallPtrSet<const SCEV *, 16> Visited;
16026 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
16030 while (!Worklist.
empty()) {
16034 if (!Visited.
insert(From).second)
16036 const SCEV *FromRewritten = GetMaybeRewritten(From);
16037 const SCEV *To =
nullptr;
16039 switch (Predicate) {
16044 EnqueueOperands(
UMax);
16050 EnqueueOperands(
SMax);
16056 EnqueueOperands(
UMin);
16062 EnqueueOperands(
SMin);
16070 const SCEV *OneAlignedUp =
16072 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16084 const SCEVConstant *
C;
16093 Guards.NotEqual.insert({
LHS,
RHS});
16102 AddRewrite(From, FromRewritten, To);
16119 SE.F.
getParent(), Intrinsic::experimental_guard);
16121 for (
const auto *GU : GuardDecl->users())
16123 if (Guard->getFunction() ==
Block->getParent() &&
16133 unsigned NumCollectedConditions = 0;
16134 unsigned NumDomTreeSteps = 0;
16136 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16137 for (;; Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16142 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16143 for (
auto &Phi : Pair.second->phis())
16153 const CondBrInst *LoopEntryPredicate =
16155 if (!LoopEntryPredicate)
16160 NumCollectedConditions++;
16164 if (
Depth > 0 && NumCollectedConditions == 2)
16175 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16176 SmallVector<Value *, 8> Worklist;
16177 SmallPtrSet<Value *, 8> Visited;
16179 while (!Worklist.
empty()) {
16186 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16210 DenseMap<const SCEV *, APInt> Multiples;
16212 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16219 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16220 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16224 for (
const auto &[K, Divisor] : Multiples) {
16225 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16226 Guards.RewriteMap[
K] =
16228 Guards.
rewrite(K), Divisor, SE),
16237 Guards.PreserveNUW =
true;
16238 Guards.PreserveNSW =
true;
16239 for (
const SCEV *Expr : ExprsToRewrite) {
16240 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16241 Guards.PreserveNUW &=
16243 Guards.PreserveNSW &=
16250 if (ExprsToRewrite.size() > 1) {
16251 for (
const SCEV *Expr : ExprsToRewrite) {
16252 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16253 Guards.RewriteMap.erase(Expr);
16254 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16263 class SCEVLoopGuardRewriter
16274 NotEqual(Guards.NotEqual) {
16275 if (Guards.PreserveNUW)
16277 if (Guards.PreserveNSW)
16284 return Map.lookup_or(Expr, Expr);
16288 if (
const SCEV *S = Map.lookup(Expr))
16295 if (
const SCEV *S = Map.lookup(Expr))
16302 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16303 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16304 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16306 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16307 if (
const SCEV *S = Map.lookup(NarrowExt))
16308 return SE.getZeroExtendExpr(S, Ty);
16309 Bitwidth = Bitwidth / 2;
16317 if (
const SCEV *S = Map.lookup(Expr))
16324 if (
const SCEV *S = Map.lookup(Expr))
16330 if (
const SCEV *S = Map.lookup(Expr))
16336 if (
const SCEV *S = Map.lookup(Expr))
16341 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16346 if (NotEqual.contains({LHS, RHS})) {
16348 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16349 return SE.getUMaxExpr(OneAlignedUp, S);
16356 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16367 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16368 return SE.getAddExpr(
16371 if (
const SCEV *S = Map.lookup(
Add))
16372 return SE.getAddExpr(Expr->
getOperand(0), S);
16380 const SCEV *S =
nullptr;
16387 S = Map.lookup(SE.getAddExpr(NewC, Expr->
getOperand(1)));
16390 return SE.getAddExpr(S, SE.getMinusOne(Expr->
getType()));
16425 if (RewriteMap.empty() && NotEqual.empty())
16428 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16429 return Rewriter.visit(Expr);
16443 if (Guards.PendingLoop)
16444 Guards.collectPending();
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 bool hasNoUnsignedWrap(BinaryOperator &I)
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)
MachineBasicBlock * Folded
SmallVector< MachineOperand, 4 > Cond
static DominatorTree getDomTree(Function &F)
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
SI optimize exec mask operations pre RA
static void visit(BasicBlock &Start, std::function< bool(BasicBlock *)> op)
This file provides utility classes that use RAII to save and restore values.
bool SCEVMinMaxExprContains(const SCEV *Root, const SCEV *OperandToFind, SCEVTypes RootKind)
static cl::opt< unsigned > MaxAddRecSize("scalar-evolution-max-add-rec-size", cl::Hidden, cl::desc("Max coefficients in AddRec during evolving"), cl::init(8))
static cl::opt< unsigned > RangeIterThreshold("scev-range-iter-threshold", cl::Hidden, cl::desc("Threshold for switching to iteratively computing SCEV ranges"), cl::init(32))
static const Loop * isIntegerLoopHeaderPHI(const PHINode *PN, LoopInfo &LI)
static unsigned getConstantTripCount(const SCEVConstant *ExitCount)
static int CompareValueComplexity(const LoopInfo *const LI, Value *LV, Value *RV, unsigned Depth)
Compare the two values LV and RV in terms of their "complexity" where "complexity" is a partial (and ...
static const SCEV * getNextSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static void PushLoopPHIs(const Loop *L, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push PHI nodes in the header of the given loop onto the given Worklist.
static void insertFoldCacheEntry(const ScalarEvolution::FoldID &ID, const SCEV *S, DenseMap< ScalarEvolution::FoldID, const SCEV * > &FoldCache, DenseMap< const SCEV *, SmallVector< ScalarEvolution::FoldID, 2 > > &FoldCacheUser)
static cl::opt< bool > ClassifyExpressions("scalar-evolution-classify-expressions", cl::Hidden, cl::init(true), cl::desc("When printing analysis, include information on every instruction"))
static bool hasHugeExpression(ArrayRef< SCEVUse > Ops)
Returns true if Ops contains a huge SCEV (the subtree of S contains at least HugeExprThreshold nodes)...
static cl::opt< unsigned > AddOpsInlineThreshold("scev-addops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining addition operands into a SCEV"), cl::init(500))
static cl::opt< unsigned > MaxLoopGuardCollectionDepth("scalar-evolution-max-loop-guard-collection-depth", cl::Hidden, cl::desc("Maximum depth for recursive loop guard collection"), cl::init(1))
static cl::opt< bool > VerifyIR("scev-verify-ir", cl::Hidden, cl::desc("Verify IR correctness when making sensitive SCEV queries (slow)"), cl::init(false))
static bool RangeRefPHIAllowedOperands(DominatorTree &DT, PHINode *PHI)
static bool IsKnownPredicateViaAddRecMonotonicity(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Is LHS Pred RHS true because one of them is an AddRec that is known not to go below its own start val...
static std::optional< APInt > MinOptional(std::optional< APInt > X, std::optional< APInt > Y)
Helper function to compare optional APInts: (a) if X and Y both exist, return min(X,...
static PHINode * getConstantEvolvingPHI(Value *V, const Loop *L, const TargetLibraryInfo *TLI)
getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node in the loop that V is deri...
static std::optional< BinaryOp > MatchBinaryOp(Value *V, const DominatorTree &DT)
Try to map V into a BinaryOp, and return std::nullopt on failure.
static bool canConstantFold(const Instruction *I, const TargetLibraryInfo *TLI)
Return true if we can constant fold an instruction of the specified type, assuming that all operands ...
static cl::opt< unsigned > MulOpsInlineThreshold("scev-mulops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining multiplication operands into a SCEV"), cl::init(32))
static BinaryOperator * getCommonInstForPHI(PHINode *PN)
static PHINode * getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L, DenseMap< Instruction *, PHINode * > &PHIMap, const TargetLibraryInfo *TLI, unsigned Depth)
getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by recursing through each instructi...
static bool isDivisibilityGuard(const SCEV *LHS, const SCEV *RHS, ScalarEvolution &SE)
static std::optional< const SCEV * > createNodeForSelectViaUMinSeq(ScalarEvolution *SE, const SCEV *CondExpr, const SCEV *TrueExpr, const SCEV *FalseExpr)
static Constant * BuildConstantFromSCEV(const SCEV *V)
This builds up a Constant using the ConstantExpr interface.
static ConstantInt * EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C, ScalarEvolution &SE)
static const SCEV * BinomialCoefficient(const SCEV *It, unsigned K, ScalarEvolution &SE, Type *ResultTy)
Compute BC(It, K). The result has width W. Assume, K > 0.
static cl::opt< unsigned > MaxCastDepth("scalar-evolution-max-cast-depth", cl::Hidden, cl::desc("Maximum depth of recursive SExt/ZExt/Trunc"), cl::init(8))
static bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr, const SCEV *Candidate)
Is MaybeMinMaxExpr an (U|S)(Min|Max) of Candidate and some other values?
static SCEVFlags getNoWrapFlagsForGEP(GEPOperator *GEP, const SCEV *Accum, ScalarEvolution &SE)
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 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 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 CollectAddOperandsWithScales(SmallDenseMap< const SCEV *, 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 bool isKnownPredicateExtendIdiom(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
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 SCEVFlags StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, ArrayRef< SCEVUse > Ops, SCEVFlags Flags)
static APInt extractConstantWithoutWrapping(ScalarEvolution &SE, const SCEVConstant *ConstantTerm, const SCEVAddExpr *WholeAddExpr)
static int CompareSCEVComplexity(const LoopInfo *const LI, SCEVUse LHS, SCEVUse RHS, DominatorTree &DT)
static cl::opt< unsigned > MaxConstantEvolvingDepth("scalar-evolution-max-constant-evolving-depth", cl::Hidden, cl::desc("Maximum depth of recursive constant evolving"), cl::init(32))
static bool canConstantEvolve(Instruction *I, const Loop *L, const TargetLibraryInfo *TLI)
Determine whether this instruction can constant evolve within this loop assuming its operands can all...
static cl::opt< unsigned > MaxGuardDomTreeSteps("scalar-evolution-max-guard-dom-tree-steps", cl::Hidden, cl::desc("Maximum number of immediate dominator steps taken when " "collecting loop guards"), cl::init(8))
static bool MatchBinarySub(const SCEV *S, SCEVUse &LHS, SCEVUse &RHS)
static std::optional< ConstantRange > GetRangeFromMetadata(Value *V)
Helper method to assign a range to V from metadata present in the IR.
static cl::opt< unsigned > HugeExprThreshold("scalar-evolution-huge-expr-threshold", cl::Hidden, cl::desc("Size of the expression which is considered huge"), cl::init(4096))
static Type * isSimpleCastedPHI(const SCEV *Op, const SCEVUnknown *SymbolicPHI, bool &Signed, ScalarEvolution &SE)
Helper function to createAddRecFromPHIWithCasts.
static Constant * EvaluateExpression(Value *V, const Loop *L, DenseMap< Instruction *, Constant * > &Vals, const DataLayout &DL, const TargetLibraryInfo *TLI)
EvaluateExpression - Given an expression that passes the getConstantEvolvingPHI predicate,...
static const SCEV * getPreviousSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static const SCEV * MatchNotExpr(const SCEV *Expr)
If Expr computes ~A, return A else return nullptr.
static std::pair< ConstantRange, bool > getRangeForAffineARHelper(APInt Step, const ConstantRange &StartRange, const APInt &MaxBECount, bool Signed)
static cl::opt< unsigned > MaxValueCompareDepth("scalar-evolution-max-value-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive value complexity comparisons"), cl::init(2))
static const SCEV * applyDivisibilityOnMinMaxExpr(const SCEV *MinMaxExpr, APInt Divisor, ScalarEvolution &SE)
static cl::opt< bool, true > VerifySCEVOpt("verify-scev", cl::Hidden, cl::location(VerifySCEV), cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"))
static const SCEV * getSignedOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static cl::opt< unsigned > MaxArithDepth("scalar-evolution-max-arith-depth", cl::Hidden, cl::desc("Maximum depth of recursive arithmetics"), cl::init(32))
static bool HasSameValue(const SCEV *A, const SCEV *B)
SCEV structural equivalence is usually sufficient for testing whether two expressions are equal,...
static uint64_t Choose(uint64_t n, uint64_t k, bool &Overflow)
Compute the result of "n choose k", the binomial coefficient.
static 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.
virt reg 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.
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 getNonStrictPredicate() const
For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.
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.
bool isSingleElement() const
Return true if this set contains exactly one member.
LLVM_ABI ConstantRange truncate(uint32_t BitWidth, unsigned NoWrapKind=0) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
LLVM_ABI ConstantRange signExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI bool contains(const APInt &Val) const
Return true if the specified value is in the set.
LLVM_ABI APInt 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:
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
iterator find(const_arg_type_t< KeyT > Val)
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
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_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive,...
void swap(DenseMapBase &RHS)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
DomTreeNodeBase * getIDom() const
Analysis pass which computes a DominatorTree.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
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 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(SCEVFlags 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(SCEVFlags 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
SCEVFlags getNoWrapFlags(SCEVFlags Mask=FlagsNoWrapMask) const
bool hasNoSelfWrap() const
size_t getNumOperands() const
bool hasNoSignedWrap() 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 * visitPtrToAddrExpr(const SCEVPtrToAddrExpr *Expr)
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...
unsigned getOrderID() const
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 SCEVFlags, 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.
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
static constexpr auto FlagsNoWrapMask
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 * getCanonical() const
Return the canonical SCEV.
const SCEV * CanonicalSCEV
Pointer to the canonical version of the SCEV, i.e.
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.
static constexpr auto FlagNone
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()
friend class ScalarEvolution
static LoopGuards collectOnDemand(const Loop *L, ScalarEvolution &SE)
Return loop guards for loop L, which are collected on first use.
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.
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 ...
static bool hasFlags(SCEVFlags Flags, SCEVFlags TestFlags)
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 const SCEV * getElementCount(Type *Ty, ElementCount EC, SCEVFlags Flags=SCEV::FlagNone)
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 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 const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEVFlags Flags=SCEV::FlagNone, unsigned Depth=0)
Return LHS-RHS.
LLVM_ABI ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsOnlyExit, bool AllowPredicates=false)
Compute the number of times the backedge of the specified loop will execute if its exit condition wer...
LLVM_ABI const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &Operands)
LLVM_ABI const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
LLVM_ABI SCEVUse getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
LLVM_ABI uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
LLVM_ABI void registerUser(const SCEV *User, ArrayRef< SCEVUse > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
LLVM_ABI const SCEV * getConstant(ConstantInt *V)
LLVM_ABI const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
LLVM_ABI const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
static SCEVFlags setFlags(SCEVFlags Flags, SCEVFlags OnFlags)
static LLVM_ABI bool isGuaranteedNotToBePoison(const SCEV *Op)
Returns true if Op is guaranteed to not be poison.
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
LLVM_ABI const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
LLVM_ABI ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI)
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LLVM_ABI const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI void forgetValues(ArrayRef< Value * > Values)
Batched forgetValue: invalidates all Values in one shared def-use walk, avoiding the redundant re-tra...
LLVM_ABI const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &Operands)
LLVM_ABI const SCEV * getCastExpr(SCEVTypes Kind, SCEVUse Op, Type *Ty)
LLVM_ABI std::optional< bool > evaluatePredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Check whether the condition described by Pred, LHS, and RHS is true or false in the given Context.
LLVM_ABI SCEVUse getAddRecExpr(SCEVUse Start, SCEVUse Step, const Loop *L, SCEVFlagsPair Flags)
Get an add recurrence expression for the specified loop.
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.
static SCEVFlags clearFlags(SCEVFlags Flags, SCEVFlags OffFlags)
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.
static SCEVFlags maskFlags(SCEVFlags Flags, SCEVFlags Mask)
Convenient SCEVFlags manipulation.
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 SCEVUse getAddExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlagsPair Flags={}, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
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 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...
LLVM_ABI std::optional< SCEVFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
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.
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)
@ 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.
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 SCEVUse getSCEVAtExit(const SCEV *S, const Loop *L, const BasicBlock *ExitingBlock)
Return the SCEV expression at the specified loop exit.
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.
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 void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)
Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...
LLVM_ABI bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
LLVM_ABI std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
LLVM_ABI const SCEV * getCouldNotCompute()
LLVM_ABI bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
LLVM_ABI uint32_t getMinTrailingZeros(const SCEV *S, const Instruction *CtxI=nullptr)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
@ DominatesBlock
The SCEV dominates the block.
@ ProperlyDominatesBlock
The SCEV properly dominates the block.
@ DoesNotDominateBlock
The SCEV does not dominate the block.
LLVM_ABI const SCEV * 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 setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEVFlags Flags)
Update no-wrap flags of an AddRec.
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 SCEVUse getMulExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlagsPair Flags={}, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
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.
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 * getNegativeSCEV(const SCEV *V, SCEVFlags Flags=SCEV::FlagNone)
Return the SCEV object corresponding to -V.
LLVM_ABI const SCEV * getUDivExactExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
LLVM_ABI const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
LLVM_ABI std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
LLVM_ABI bool canReuseInstruction(const SCEV *S, Instruction *I, SmallVectorImpl< Instruction * > &DropPoisonGeneratingInsts)
Check whether it is poison-safe to represent the expression S using the instruction I.
LLVM_ABI bool isKnownPredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * getPredicatedSymbolicMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getSymbolicMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI ~ScalarEvolution()
LLVM_ABI const SCEV * getGEPExpr(GEPOperator *GEP, ArrayRef< SCEVUse > IndexExprs)
Returns an expression for a GEP.
LLVM_ABI const SCEV * getUMinExpr(SCEVUse LHS, SCEVUse RHS, bool Sequential=false)
LLVM_ABI bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the basic block is protected by a conditional between LHS and RHS.
LLVM_ABI const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool containsErasedValue(const SCEV *S) const
Return true if the SCEV expression contains a Value that has been optimised out and is now a nullptr.
const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
LLVM_ABI void verify() const
LLVMContext & getContext() const
This class represents the LLVM 'select' instruction.
Implements a dense probed hash-table based set with some number of buckets stored inline.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
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)
@ 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)
SCEVBinaryExpr_match< SCEVAddExpr, Op0_t, Op1_t, SCEV::FlagNSW > m_scev_NSWAdd(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)
SCEVBinaryExpr_match< SCEVSMaxExpr, Op0_t, Op1_t, SCEV::FlagNone, true > m_scev_SMax(const Op0_t &Op0, const Op1_t &Op1)
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagNone, true > m_scev_c_Mul(const Op0_t &Op0, const Op1_t &Op1)
match_bind< const SCEVAddExpr > m_scev_Add(const SCEVAddExpr *&V)
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.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
SaveAndRestore(T &) -> SaveAndRestore< T >
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)
LLVM_ABI bool canCreatePoison(const Operator *Op, bool ConsiderFlagsAndMetadata=true)
LLVM_ABI bool mustTriggerUB(const Instruction *I, const SmallPtrSetImpl< const Value * > &KnownPoison)
Return true if the given instruction must trigger undefined behavior when I is executed with any oper...
RelativeUniformCounterPtr Values
@ Known
Known to have no common set bits.
InterleavedRange< Range > interleaved(const Range &R, StringRef Separator=", ", StringRef Prefix="", StringRef Suffix="")
Output range R as a sequence of interleaved elements.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
auto successors(const MachineBasicBlock *BB)
scope_exit(Callable) -> scope_exit< Callable >
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
@ BinaryOp
One of the operands is a binary op.
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 void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CtxI=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...
auto uninitialized_copy(R &&Src, IterTy Dst)
bool isa_and_nonnull(const Y &Val)
LLVM_ABI unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CtxI=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.
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
auto map_range(ContainerTy &&C, FuncTy F)
Return a range that applies F to the elements of C.
LLVM_ABI bool canConstantFoldCallTo(const CallBase *Call, const Function *F, const TargetLibraryInfo *TLI=nullptr)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO, const DominatorTree &DT)
Returns true if the arithmetic part of the WO 's result is used only along the paths control dependen...
DomTreeNodeBase< BasicBlock > DomTreeNode
LLVM_ABI bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step)
Attempt to match a simple first order recurrence cycle of the form: iv = phi Ty [Start,...
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Function *CtxF=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
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.
void sort(IteratorTy Start, IteratorTy End)
LLVM_ABI bool isFinite(const Loop *L)
Return true if this loop can be assumed to run for a finite number of iterations.
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)
SCEVFlags
SCEVFlags are bitfield indices into SCEV's SubclassData.
ArrayRef(const T &OneElt) -> ArrayRef< T >
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.
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
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.
@ End
Run the machine verifier once, at the end of the pipeline.
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:
The no-wrap flags to apply when creating a SCEV expression, to the expression and use respectively.
SCEVFlags ExprFlags
Flags applied directly to a SCEV expression, must be valid wherever the expression is valid.
SCEVFlags UseFlags
Flags only applied to a SCEVUse.
static SCEVUseT getCommon(SCEVUseT A, SCEVUseT B)
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