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);
824 assert(Folded &&
"Must have folded value");
828 if (Folded && IsAbsorber(Folded->
getAPInt()))
832 if (Folded && !IsIdentity(Folded->
getAPInt()))
833 Ops.insert(
Ops.begin(), Folded);
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");
2503 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
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();
2642 APInt ConstAdd = C1 + C2;
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!");
3125 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
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};
3774 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3778 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3792 bool FirstIter =
true;
3794 for (
SCEVUse IndexExpr : IndexExprs) {
3801 Offsets.push_back(FieldOffset);
3804 CurTy = STy->getTypeAtIndex(Index);
3809 "The first index of a GEP indexes a pointer");
3810 CurTy = SrcElementTy;
3821 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3822 Offsets.push_back(LocalOffset);
3827 if (Offsets.empty())
3840 "GEP should not change type mid-flight.");
3844SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3848 "L must be passed to find existing AddRecs");
3852 ID.AddPointer(
Op.getOpaqueValue());
3856 return UniqueSCEVs.lookup(ID, Token);
3866 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3867 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3868 if (
Ops.size() == 1)
return Ops[0];
3871 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3873 "Operand types don't match!");
3876 "min/max should be consistently pointerish");
3902 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3904 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3909 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3911 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3917 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3923 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3928 if (Idx <
Ops.size()) {
3929 bool DeletedAny =
false;
3930 while (
Ops[Idx]->getSCEVType() == Kind) {
3932 Ops.erase(
Ops.begin()+Idx);
3950 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3952 Ops[i] =
Ops[i + 1] = Common;
3953 if (
Ops[i] ==
Ops[i + 1] ||
3954 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3957 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3960 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3963 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3969 if (
Ops.size() == 1)
return Ops[0];
3971 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
3978 ID.AddPointer(
Op.getOpaqueValue());
3980 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
3982 return ExistingSCEV;
3985 SCEV *S =
new (SCEVAllocator)
3988 UniqueSCEVs.insert(S, Token);
3996class SCEVSequentialMinMaxDeduplicatingVisitor final
3997 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
3998 std::optional<const SCEV *>> {
3999 using RetVal = std::optional<const SCEV *>;
4006 bool canRecurseInto(
SCEVTypes Kind)
const {
4009 return RootKind == Kind || NonSequentialRootKind == Kind;
4014 if (!SeenOps.
insert(S).second)
4015 return std::nullopt;
4019 if (!canRecurseInto(Kind))
4029 return std::nullopt;
4039 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4041 : SE(SE), RootKind(RootKind),
4042 NonSequentialRootKind(
4043 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4047 SmallVectorImpl<SCEVUse> &NewOps) {
4052 for (
const SCEV *
Op : OrigOps) {
4057 Ops.emplace_back(*NewOp);
4061 NewOps = std::move(
Ops);
4105struct SCEVPoisonCollector {
4106 bool LookThroughMaybePoisonBlocking;
4107 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4108 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4109 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4111 bool follow(
const SCEV *S) {
4112 if (!LookThroughMaybePoisonBlocking &&
4122 bool isDone()
const {
return false; }
4132 SCEVPoisonCollector PC1(
true);
4137 if (PC1.MaybePoison.
empty())
4143 SCEVPoisonCollector PC2(
false);
4153 SCEVPoisonCollector PC(
false);
4176 unsigned NumVisitedInsts = 0;
4178 while (!Worklist.
empty()) {
4180 if (!Visited.
insert(V).second)
4189 if (++NumVisitedInsts > InstLimit)
4200 if (PDI->isDisjoint())
4207 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4214 if (
I->hasPoisonGeneratingAnnotations())
4225 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4226 "Not a SCEVSequentialMinMaxExpr!");
4227 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4228 if (
Ops.size() == 1)
4232 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4234 "Operand types don't match!");
4237 "min/max should be consistently pointerish");
4245 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4252 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4262 bool DeletedAny =
false;
4263 while (Idx <
Ops.size()) {
4264 if (
Ops[Idx]->getSCEVType() != Kind) {
4269 Ops.erase(
Ops.begin() + Idx);
4270 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4271 SMME->operands().end());
4279 const SCEV *SaturationPoint;
4290 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4291 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4303 Ops.erase(
Ops.begin() + i);
4308 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4309 Ops.erase(
Ops.begin() + i);
4319 ID.AddPointer(
Op.getOpaqueValue());
4321 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
4323 return ExistingSCEV;
4327 SCEV *S =
new (SCEVAllocator)
4330 UniqueSCEVs.insert(S, Token);
4378 if (
Size.isScalable())
4399 "Cannot get offset for structure containing scalable vector types");
4413 if (
SCEV *S = UniqueSCEVs.lookup(ID, Token)) {
4415 "Stale SCEVUnknown in uniquing map!");
4418 SCEV *S =
new (SCEVAllocator)
SCEVUnknown(ID.Intern(SCEVAllocator), V,
this,
4419 FirstUnknown, NextUnknownOrderID++);
4421 UniqueSCEVs.insert(S, Token);
4436 return Ty->isIntOrPtrTy();
4443 if (Ty->isPointerTy())
4454 if (Ty->isIntegerTy())
4458 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4470 bool PreciseA, PreciseB;
4471 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4472 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4473 if (!PreciseA || !PreciseB)
4476 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4477 DT.dominates(ScopeB, ScopeA);
4481 return CouldNotCompute.get();
4484bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4487 return SU && SU->getValue() ==
nullptr;
4490 return !ContainsNulls;
4495 if (
I != HasRecMap.end())
4500 HasRecMap.insert({S, FoundAddRec});
4507 ExprValueMapType::iterator
SI = ExprValueMap.find_as(S);
4508 if (
SI == ExprValueMap.end())
4516void ScalarEvolution::eraseValueFromMap(
Value *V) {
4518 if (
I != ValueExprMap.end()) {
4519 auto EVIt = ExprValueMap.find(
I->second);
4522 ValueExprMap.erase(
I);
4526void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4530 if (ValueExprMap.insert({SCEVCallbackVH(V, this), S}).second)
4531 ExprValueMap[S].push_back(V);
4541 return createSCEVIter(V);
4548 if (
I != ValueExprMap.end()) {
4549 const SCEV *S =
I->second;
4550 assert(checkValidity(S) &&
4551 "existing SCEV has not been properly invalidated");
4563 Type *Ty = V->getType();
4579 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4592 return (
const SCEV *)
nullptr;
4598 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4602 Type *Ty = V->getType();
4608 assert(
P->getType()->isPointerTy());
4623 if (AddOp->getType()->isPointerTy()) {
4624 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4641 return getZero(LHS->getType());
4646 if (RHS->getType()->isPointerTy()) {
4647 if (!LHS->getType()->isPointerTy() ||
4657 const bool RHSIsNotMinSigned =
4688 Type *SrcTy = V->getType();
4689 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4690 "Cannot truncate or zero extend with non-integer arguments!");
4700 Type *SrcTy = V->getType();
4701 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4702 "Cannot truncate or zero extend with non-integer arguments!");
4711 Type *SrcTy = V->getType();
4712 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4713 "Cannot noop or zero extend with non-integer arguments!");
4715 "getNoopOrZeroExtend cannot truncate!");
4722 Type *SrcTy = V->getType();
4723 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4724 "Cannot noop or sign extend with non-integer arguments!");
4726 "getNoopOrSignExtend cannot truncate!");
4733 Type *SrcTy = V->getType();
4734 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4735 "Cannot noop or any extend with non-integer arguments!");
4737 "getNoopOrAnyExtend cannot truncate!");
4744 Type *SrcTy = V->getType();
4745 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4746 "Cannot truncate or noop with non-integer arguments!");
4748 "getTruncateOrNoop cannot extend!");
4756 const SCEV *PromotedLHS = LHS;
4757 const SCEV *PromotedRHS = RHS;
4777 assert(!
Ops.empty() &&
"At least one operand must be!");
4779 if (
Ops.size() == 1)
4783 Type *MaxType =
nullptr;
4789 assert(MaxType &&
"Failed to find maximum type!");
4802 if (!V->getType()->isPointerTy())
4807 V = AddRec->getStart();
4809 const SCEV *PtrOp =
nullptr;
4810 for (
const SCEV *AddOp :
Add->operands()) {
4811 if (AddOp->getType()->isPointerTy()) {
4812 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4816 assert(PtrOp &&
"Must have pointer op");
4828 for (
User *U :
I->users()) {
4830 if (Visited.
insert(UserInsn).second)
4844 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4845 bool IgnoreOtherLoops =
true) {
4848 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4850 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4855 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4857 SeenLoopVariantSCEVUnknown =
true;
4861 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4865 SeenOtherLoops =
true;
4869 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4871 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4874 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4875 : SCEVRewriteVisitor(SE),
L(
L) {}
4878 bool SeenLoopVariantSCEVUnknown =
false;
4879 bool SeenOtherLoops =
false;
4888 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4889 SCEVPostIncRewriter
Rewriter(L, SE);
4891 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4896 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4898 SeenLoopVariantSCEVUnknown =
true;
4902 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4906 SeenOtherLoops =
true;
4910 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4912 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4915 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4916 : SCEVRewriteVisitor(SE),
L(
L) {}
4919 bool SeenLoopVariantSCEVUnknown =
false;
4920 bool SeenOtherLoops =
false;
4926class SCEVBackedgeConditionFolder
4929 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4930 ScalarEvolution &SE) {
4931 bool IsPosBECond =
false;
4932 Value *BECond =
nullptr;
4933 if (BasicBlock *Latch =
L->getLoopLatch()) {
4935 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
4936 "Both outgoing branches should not target same header!");
4937 BECond = BI->getCondition();
4938 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
4943 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
4947 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4948 const SCEV *
Result = Expr;
4953 switch (
I->getOpcode()) {
4954 case Instruction::Select: {
4956 std::optional<const SCEV *> Res =
4957 compareWithBackedgeCondition(
SI->getCondition());
4965 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
4976 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
4977 bool IsPosBECond, ScalarEvolution &SE)
4978 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
4979 IsPositiveBECond(IsPosBECond) {}
4981 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
4985 Value *BackedgeCond =
nullptr;
4987 bool IsPositiveBECond;
4990std::optional<const SCEV *>
4991SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
4996 if (BackedgeCond == IC)
4999 return std::nullopt;
5004 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5005 ScalarEvolution &SE) {
5011 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5018 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5028 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5029 : SCEVRewriteVisitor(SE),
L(
L) {}
5037void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5053 const APInt &BECountAP = BECountMax->getAPInt();
5054 unsigned NoOverflowBitWidth =
5063ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5073 if (!SignedWrapViaInductionTried.insert(AR).second)
5098 AC.assumptions().empty())
5106 const SCEV *OverflowLimit =
5108 if (OverflowLimit &&
5116ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5126 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5151 AC.assumptions().empty())
5160 const SCEV *OverflowLimit =
5189 IsNSW = OBO->hasNoSignedWrap();
5190 IsNUW = OBO->hasNoUnsignedWrap();
5196 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5208 return std::nullopt;
5214 switch (
Op->getOpcode()) {
5215 case Instruction::Add:
5216 case Instruction::Sub:
5217 case Instruction::Mul:
5218 case Instruction::UDiv:
5219 case Instruction::URem:
5220 case Instruction::And:
5221 case Instruction::AShr:
5222 case Instruction::Shl:
5225 case Instruction::Or: {
5228 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5238 case Instruction::Xor:
5242 if (RHSC->getValue().isSignMask())
5243 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5245 if (V->getType()->isIntegerTy(1))
5246 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5249 case Instruction::LShr:
5258 if (SA->getValue().ult(
BitWidth)) {
5260 ConstantInt::get(SA->getContext(),
5262 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5267 case Instruction::ExtractValue: {
5269 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5277 bool Signed = WO->isSigned();
5280 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5285 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5296 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5297 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5299 return std::nullopt;
5325 if (
Op == SymbolicPHI)
5330 if (SourceBits != NewBits)
5348 if (!L || L->getHeader() != PN->
getParent())
5406std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5407ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5415 assert(L &&
"Expecting an integer loop header phi");
5420 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5421 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5422 Value *
V = PN->getIncomingValue(i);
5423 if (
L->contains(PN->getIncomingBlock(i))) {
5426 }
else if (BEValueV != V) {
5430 }
else if (!StartValueV) {
5432 }
else if (StartValueV != V) {
5433 StartValueV =
nullptr;
5437 if (!BEValueV || !StartValueV)
5438 return std::nullopt;
5440 const SCEV *BEValue =
getSCEV(BEValueV);
5447 return std::nullopt;
5451 unsigned FoundIndex =
Add->getNumOperands();
5452 Type *TruncTy =
nullptr;
5454 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5457 if (FoundIndex == e) {
5462 if (FoundIndex ==
Add->getNumOperands())
5463 return std::nullopt;
5467 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5468 if (i != FoundIndex)
5469 Ops.push_back(
Add->getOperand(i));
5475 return std::nullopt;
5528 const SCEV *StartVal =
getSCEV(StartValueV);
5529 const SCEV *PHISCEV =
5556 auto getExtendedExpr = [&](
const SCEV *Expr,
5557 bool CreateSignExtend) ->
const SCEV * {
5560 const SCEV *ExtendedExpr =
5563 return ExtendedExpr;
5571 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5572 const SCEV *ExtendedExpr) ->
bool {
5573 return Expr != ExtendedExpr &&
5577 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5578 if (PredIsKnownFalse(StartVal, StartExtended)) {
5580 return std::nullopt;
5585 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5586 if (PredIsKnownFalse(Accum, AccumExtended)) {
5588 return std::nullopt;
5591 auto AppendPredicate = [&](
const SCEV *Expr,
5592 const SCEV *ExtendedExpr) ->
void {
5593 if (Expr != ExtendedExpr &&
5601 AppendPredicate(StartVal, StartExtended);
5602 AppendPredicate(Accum, AccumExtended);
5610 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5611 std::make_pair(NewAR, Predicates);
5613 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5617std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5622 return std::nullopt;
5625 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5626 if (
I != PredicatedSCEVRewrites.end()) {
5627 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5630 if (Rewrite.first == SymbolicPHI)
5631 return std::nullopt;
5635 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5639 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5640 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5645 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5646 return std::nullopt;
5666 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5667 if (Expr1 != Expr2 &&
5668 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5669 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5704const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5706 Value *StartValueV) {
5709 assert(BEValueV && StartValueV);
5711 const SCEV *Accum =
nullptr;
5714 if (BO->Opcode != Instruction::Add)
5717 if (BO->LHS == PN &&
L->isLoopInvariant(BO->RHS))
5719 else if (BO->RHS == PN &&
L->isLoopInvariant(BO->LHS))
5733 if (!
GEP ||
GEP->getPointerOperand() != PN ||
GEP->getNumIndices() != 1)
5736 if (!
L->isLoopInvariant(Idx))
5745 const SCEV *StartVal =
getSCEV(StartValueV);
5746 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5747 insertValueToMap(PN, PHISCEV);
5750 inferNoWrapViaConstantRanges(AR);
5757 "Accum is defined outside L, but is not invariant?");
5758 if (isAddRecNeverPoison(BEInst, L))
5765const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5773 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5779 }
else if (BEValueV != V) {
5783 }
else if (!StartValueV) {
5785 }
else if (StartValueV != V) {
5786 StartValueV =
nullptr;
5790 if (!BEValueV || !StartValueV)
5793 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5794 "PHI node already processed?");
5798 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5803 insertValueToMap(PN, SymbolicName);
5807 const SCEV *BEValue =
getSCEV(BEValueV);
5817 unsigned FoundIndex =
Add->getNumOperands();
5818 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5819 if (
Add->getOperand(i) == SymbolicName)
5820 if (FoundIndex == e) {
5825 if (FoundIndex !=
Add->getNumOperands()) {
5828 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5829 if (i != FoundIndex)
5830 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5842 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5849 if (
GEP->getOperand(0) == PN)
5857 const SCEV *StartVal =
getSCEV(StartValueV);
5858 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5863 forgetMemoizedResults({SymbolicName});
5864 insertValueToMap(PN, PHISCEV);
5867 inferNoWrapViaConstantRanges(AR);
5891 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5892 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5894 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5895 const SCEV *StartVal =
getSCEV(StartValueV);
5896 if (Start == StartVal) {
5900 forgetMemoizedResults({SymbolicName});
5901 insertValueToMap(PN, Shifted);
5911 eraseValueFromMap(PN);
5926 Use &LeftUse =
Merge->getOperandUse(0);
5927 Use &RightUse =
Merge->getOperandUse(1);
5963 assert(IDom &&
"At least the entry block should dominate PN");
5971const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
5976 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
5993 CommonInst = IncomingInst;
6009ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6015 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6016 bool SCEVExprsIdentical =
6018 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6019 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6022const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6023 if (
const SCEV *S = createAddRecFromPHI(PN))
6033 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6036 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6045 struct FindClosure {
6046 const SCEV *OperandToFind;
6052 bool canRecurseInto(
SCEVTypes Kind)
const {
6055 return RootKind == Kind || NonSequentialRootKind == Kind ||
6060 : OperandToFind(OperandToFind), RootKind(RootKind),
6061 NonSequentialRootKind(
6065 bool follow(
const SCEV *S) {
6066 Found = S == OperandToFind;
6068 return !isDone() && canRecurseInto(S->
getSCEVType());
6071 bool isDone()
const {
return Found; }
6074 FindClosure FC(OperandToFind, RootKind);
6079std::optional<const SCEV *>
6080ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6090 switch (ICI->getPredicate()) {
6104 bool Signed = ICI->isSigned();
6105 const SCEV *LA =
getSCEV(TrueVal);
6113 if (LA == LS &&
RA == RS)
6115 if (LA == RS &&
RA == LS)
6118 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6119 if (
Op->getType()->isPointerTy()) {
6130 LS = CoerceOperand(LS);
6131 RS = CoerceOperand(RS);
6155 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6156 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6170 X = ZExt->getOperand();
6172 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6183 return std::nullopt;
6186static std::optional<const SCEV *>
6188 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6192 "Unexpected operands of a select.");
6204 return std::nullopt;
6219static std::optional<const SCEV *>
6223 return std::nullopt;
6226 const auto *SETrue = SE->
getSCEV(TrueVal);
6227 const auto *SEFalse = SE->
getSCEV(FalseVal);
6231const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6233 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6235 V->getType() ==
TrueVal->getType() &&
6236 "Types of select hands and of the result must match.");
6239 if (!
V->getType()->isIntegerTy(1))
6242 if (std::optional<const SCEV *> S =
6255 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6259 if (std::optional<const SCEV *> S =
6260 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6266 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6272 assert(
GEP->getSourceElementType()->isSized() &&
6273 "GEP source element type must be sized");
6276 for (
Value *Index :
GEP->indices())
6281APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6284 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6287 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6289 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6292 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6310 return GetShiftedByZeros(TZ);
6320 return GetShiftedByZeros(TZ);
6324 if (
M->hasNoUnsignedWrap()) {
6327 for (
const SCEV *Operand :
M->operands().drop_front())
6335 for (
const SCEV *Operand :
M->operands())
6337 return GetShiftedByZeros(TZ);
6342 if (
N->hasNoUnsignedWrap())
6343 return GetGCDMultiple(
N);
6346 for (
const SCEV *Operand :
N->operands().drop_front())
6348 return GetShiftedByZeros(TZ);
6365 CtxI = &*F.getEntryBlock().begin();
6372 .allowEphemerals(
true))
6373 .countMinTrailingZeros();
6374 return GetShiftedByZeros(
Known);
6387 return getConstantMultipleImpl(S, CtxI);
6389 auto I = ConstantMultipleCache.find(S);
6390 if (
I != ConstantMultipleCache.end())
6393 APInt Result = getConstantMultipleImpl(S, CtxI);
6394 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6395 assert(InsertPair.second &&
"Should insert a new key");
6396 return InsertPair.first->second;
6413 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6416 if (std::optional<ConstantRange>
Range = CB->getRange())
6420 if (std::optional<ConstantRange>
Range =
A->getRange())
6423 return std::nullopt;
6430 UnsignedRanges.erase(AddRec);
6431 SignedRanges.erase(AddRec);
6432 ConstantMultipleCache.erase(AddRec);
6437getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6463 Value *Start, *Step;
6470 assert(L && L->getHeader() ==
P->getParent());
6483 case Instruction::AShr:
6484 case Instruction::LShr:
6485 case Instruction::Shl:
6500 KnownStep.getBitWidth() ==
BitWidth);
6503 auto MaxShiftAmt = KnownStep.getMaxValue();
6505 bool Overflow =
false;
6506 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6513 case Instruction::AShr: {
6521 if (KnownStart.isNonNegative())
6524 KnownStart.getMaxValue() + 1);
6525 if (KnownStart.isNegative())
6528 KnownEnd.getMaxValue() + 1);
6531 case Instruction::LShr: {
6540 KnownStart.getMaxValue() + 1);
6542 case Instruction::Shl: {
6546 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6547 return ConstantRange(KnownStart.getMinValue(),
6548 KnownEnd.getMaxValue() + 1);
6573 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6580ScalarEvolution::getRangeRefIter(
const SCEV *S,
6581 ScalarEvolution::RangeSignHint SignHint) {
6582 DenseMap<const SCEV *, ConstantRange> &Cache =
6583 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6586 SmallPtrSet<const SCEV *, 8> Seen;
6590 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6591 if (!Seen.
insert(Expr).second)
6624 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6625 const SCEV *
P = WorkList[
I];
6629 for (
const SCEV *
Op :
P->operands())
6642 if (!WorkList.
empty()) {
6647 getRangeRef(
P, SignHint);
6651 return getRangeRef(S, SignHint, 0);
6654const APInt *ScalarEvolution::getConstantAPIntOrNull(
const SCEV *S) {
6656 return &
C->getAPInt();
6664 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6665 DenseMap<const SCEV *, ConstantRange> &Cache =
6666 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6673 auto I = Cache.
find(S);
6674 if (
I != Cache.
end())
6678 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6683 return getRangeRefIter(S, SignHint);
6686 ConstantRange ConservativeResult(
BitWidth,
true);
6687 using OBO = OverflowingBinaryOperator;
6691 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6695 ConservativeResult =
6702 ConservativeResult = ConstantRange(
6718 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6725 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6732 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6737 return setRange(Cast, SignHint,
X);
6742 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6743 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6745 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6746 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6747 ConservativeResult =
6748 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6750 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6751 unsigned WrapType = OBO::AnyWrap;
6752 if (
Add->hasNoSignedWrap())
6753 WrapType |= OBO::NoSignedWrap;
6754 if (
Add->hasNoUnsignedWrap())
6755 WrapType |= OBO::NoUnsignedWrap;
6757 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6759 return setRange(
Add, SignHint,
6760 ConservativeResult.intersectWith(
X, RangeType));
6764 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6766 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6767 return setRange(
Mul, SignHint,
6768 ConservativeResult.intersectWith(
X, RangeType));
6772 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6773 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6774 return setRange(UDiv, SignHint,
6775 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6783 if (!UnsignedMinValue.
isZero())
6784 ConservativeResult = ConservativeResult.intersectWith(
6785 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6794 bool AllNonNeg =
true;
6795 bool AllNonPos =
true;
6796 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6803 ConservativeResult = ConservativeResult.intersectWith(
6808 ConservativeResult = ConservativeResult.intersectWith(
6817 const SCEV *MaxBEScev =
6831 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6833 ConservativeResult =
6834 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6837 auto RangeFromFactoring = getRangeViaFactoring(
6839 ConservativeResult =
6840 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6846 const SCEV *SymbolicMaxBECount =
6851 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6852 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6853 ConservativeResult =
6854 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6859 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6869 ID = Intrinsic::umax;
6872 ID = Intrinsic::smax;
6876 ID = Intrinsic::umin;
6879 ID = Intrinsic::smin;
6886 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6887 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6889 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6890 return setRange(S, SignHint,
6891 ConservativeResult.intersectWith(
X, RangeType));
6900 ConservativeResult =
6901 ConservativeResult.intersectWith(*MDRange, RangeType);
6906 auto CR = getRangeForUnknownRecurrence(U);
6907 ConservativeResult = ConservativeResult.intersectWith(CR);
6918 if (
U->getType()->isPointerTy()) {
6921 unsigned PtrIdxDiff =
6922 DL.getPointerTypeSizeInBits(
U->getType()) -
BitWidth;
6923 NS = NS > PtrIdxDiff ? NS - PtrIdxDiff : 1;
6928 if (!
Known.Zero.getHiBits(NS).isZero())
6929 Known.Zero.setHighBits(NS);
6930 if (!
Known.One.getHiBits(NS).isZero())
6931 Known.One.setHighBits(NS);
6934 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
6935 ConservativeResult = ConservativeResult.intersectWith(
6936 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
6939 ConservativeResult = ConservativeResult.intersectWith(
6944 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6948 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
6949 DL, CanBeNull,
nullptr);
6965 ConservativeResult = ConservativeResult.intersectWith(
6975 return getRangeRef(AR, SignHint,
Depth + 1);
6979 ConstantRange RangeFromOps(
BitWidth,
false);
6981 for (
const auto &
Op :
Phi->operands()) {
6983 RangeFromOps = RangeFromOps.unionWith(OpRange);
6985 if (RangeFromOps.isFullSet())
6988 ConservativeResult =
6989 ConservativeResult.intersectWith(RangeFromOps, RangeType);
6995 if (
II->getIntrinsicID() == Intrinsic::vscale) {
6997 ConservativeResult = ConservativeResult.difference(Disallowed);
7000 return setRange(U, SignHint, std::move(ConservativeResult));
7006 return setRange(S, SignHint, std::move(ConservativeResult));
7014static std::pair<ConstantRange, bool>
7022 if (Step == 0 || MaxBECount == 0)
7023 return {StartRange,
true};
7029 return {ConstantRange::getFull(
BitWidth),
false};
7045 return {ConstantRange::getFull(
BitWidth),
false};
7058 APInt MovedBoundary;
7063 MovedBoundary = StartLower - std::move(
Offset);
7066 MovedBoundary = StartUpper + std::move(
Offset);
7070 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7077 if (StartRange.
contains(MovedBoundary))
7078 return {ConstantRange::getFull(
BitWidth),
false};
7081 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7083 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7091std::pair<ConstantRange, SCEVFlags>
7092ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7093 const APInt &MaxBECount) {
7097 "mismatched bit widths");
7106 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7111 StepSRange.
getSignedMax(), StartSRange, MaxBECount,
true);
7112 SR = SR.unionWith(SRMax);
7131ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7133 ScalarEvolution::RangeSignHint SignHint) {
7134 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7136 "This only works for non-self-wrapping AddRecs!");
7137 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7141 return ConstantRange::getFull(
BitWidth);
7149 return ConstantRange::getFull(
BitWidth);
7153 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7155 MaxItersWithoutWrap))
7156 return ConstantRange::getFull(
BitWidth);
7177 ConstantRange StartRange = getRangeRef(Start, SignHint);
7178 ConstantRange EndRange = getRangeRef(
End, SignHint);
7179 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7183 return RangeBetween;
7188 return ConstantRange::getFull(
BitWidth);
7191 isKnownPredicateViaConstantRanges(LEPred, Start,
End))
7192 return RangeBetween;
7194 isKnownPredicateViaConstantRanges(GEPred, Start,
End))
7195 return RangeBetween;
7196 return ConstantRange::getFull(
BitWidth);
7201 const APInt &MaxBECount) {
7208 "mismatched bit widths");
7210 struct SelectPattern {
7211 Value *Condition =
nullptr;
7215 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7217 std::optional<unsigned> CastOp;
7231 CastOp = SCast->getSCEVType();
7232 S = SCast->getOperand();
7235 using namespace llvm::PatternMatch;
7242 Condition =
nullptr;
7274 bool isRecognized() {
return Condition !=
nullptr; }
7277 SelectPattern StartPattern(*
this,
BitWidth, Start);
7278 if (!StartPattern.isRecognized())
7279 return ConstantRange::getFull(
BitWidth);
7281 SelectPattern StepPattern(*
this,
BitWidth, Step);
7282 if (!StepPattern.isRecognized())
7283 return ConstantRange::getFull(
BitWidth);
7285 if (StartPattern.Condition != StepPattern.Condition) {
7289 return ConstantRange::getFull(
BitWidth);
7300 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7301 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7302 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7303 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7305 ConstantRange TrueRange =
7306 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7307 ConstantRange FalseRange =
7308 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7321 PDI && PDI->isDisjoint()) {
7336ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7349 SmallPtrSet<const SCEV *, 16> Visited;
7351 auto pushOp = [&](
const SCEV *S) {
7352 if (!Visited.
insert(S).second)
7355 if (Visited.
size() > 30) {
7366 while (!Worklist.
empty()) {
7368 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7369 if (!Bound || DT.dominates(Bound, DefI))
7376 return Bound ? Bound : &*F.getEntryBlock().begin();
7382 return getDefiningScopeBound(
Ops, Discard);
7385bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7387 if (
A->getParent() ==
B->getParent() &&
7392 auto *BLoop = LI.getLoopFor(
B->getParent());
7393 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7394 BLoop->getLoopPreheader() ==
A->getParent() &&
7396 A->getParent()->end()) &&
7404 SCEVPoisonCollector PC(
true);
7406 return PC.MaybePoison.
empty();
7409bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7419bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7436 for (
const Use &
Op :
I->operands()) {
7442 auto *DefI = getDefiningScopeBound(SCEVOps);
7443 return isGuaranteedToTransferExecutionTo(DefI,
I);
7446bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7448 if (isSCEVExprNeverPoison(
I))
7459 auto *ExitingBB =
L->getExitingBlock();
7463 SmallPtrSet<const Value *, 16> KnownPoison;
7472 while (!Worklist.
empty()) {
7475 for (
const Use &U :
Poison->uses()) {
7478 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7482 if (KnownPoison.
insert(PoisonUser).second)
7490ScalarEvolution::LoopProperties
7491ScalarEvolution::getLoopProperties(
const Loop *L) {
7492 using LoopProperties = ScalarEvolution::LoopProperties;
7494 auto Itr = LoopPropertiesCache.find(L);
7495 if (Itr == LoopPropertiesCache.end()) {
7498 return !
SI->isSimple();
7509 if (
I->isDroppable())
7512 return I->mayWriteToMemory();
7515 LoopProperties LP = {
true,
7518 for (
auto *BB :
L->getBlocks())
7519 for (
auto &
I : *BB) {
7521 LP.HasNoAbnormalExits =
false;
7522 if (HasSideEffects(&
I))
7523 LP.HasNoSideEffects =
false;
7524 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7528 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7529 assert(InsertPair.second &&
"We just checked!");
7530 Itr = InsertPair.first;
7543const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7549 Stack.emplace_back(V,
false);
7550 while (!Stack.empty()) {
7551 auto E = Stack.back();
7552 Value *CurV = E.getPointer();
7560 const SCEV *CreatedSCEV =
nullptr;
7563 CreatedSCEV = createSCEV(CurV);
7568 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7572 insertValueToMap(CurV, CreatedSCEV);
7575 Stack.back().setInt(
true);
7578 Stack.emplace_back(
Op,
false);
7595 if (!DT.isReachableFromEntry(
I->getParent()))
7608 switch (BO->Opcode) {
7609 case Instruction::Add:
7610 case Instruction::Mul: {
7617 Ops.push_back(BO->
Op);
7621 Ops.push_back(BO->RHS);
7625 (BO->Opcode == Instruction::Add &&
7626 (NewBO->Opcode != Instruction::Add &&
7627 NewBO->Opcode != Instruction::Sub)) ||
7628 (BO->Opcode == Instruction::Mul &&
7629 NewBO->Opcode != Instruction::Mul)) {
7630 Ops.push_back(BO->LHS);
7635 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7638 Ops.push_back(BO->LHS);
7646 case Instruction::Sub:
7647 case Instruction::UDiv:
7648 case Instruction::URem:
7650 case Instruction::AShr:
7651 case Instruction::Shl:
7652 case Instruction::Xor:
7656 case Instruction::And:
7657 case Instruction::Or:
7661 case Instruction::LShr:
7668 Ops.push_back(BO->LHS);
7669 Ops.push_back(BO->RHS);
7673 switch (
U->getOpcode()) {
7674 case Instruction::Trunc:
7675 case Instruction::ZExt:
7676 case Instruction::SExt:
7677 case Instruction::PtrToAddr:
7678 case Instruction::PtrToInt:
7679 Ops.push_back(
U->getOperand(0));
7682 case Instruction::BitCast:
7684 Ops.push_back(
U->getOperand(0));
7689 case Instruction::SDiv:
7690 case Instruction::SRem:
7691 Ops.push_back(
U->getOperand(0));
7692 Ops.push_back(
U->getOperand(1));
7695 case Instruction::GetElementPtr:
7697 "GEP source element type must be sized");
7701 case Instruction::IntToPtr:
7704 case Instruction::PHI:
7735 Ops.push_back(CondICmp->getOperand(0));
7736 Ops.push_back(CondICmp->getOperand(1));
7756 case Instruction::Select: {
7758 auto CanSimplifyToUnknown = [
this,
U]() {
7776 if (CanSimplifyToUnknown())
7783 case Instruction::Call:
7784 case Instruction::Invoke:
7791 switch (
II->getIntrinsicID()) {
7792 case Intrinsic::abs:
7793 Ops.push_back(
II->getArgOperand(0));
7795 case Intrinsic::umax:
7796 case Intrinsic::umin:
7797 case Intrinsic::smax:
7798 case Intrinsic::smin:
7799 case Intrinsic::usub_sat:
7800 case Intrinsic::uadd_sat:
7801 Ops.push_back(
II->getArgOperand(0));
7802 Ops.push_back(
II->getArgOperand(1));
7804 case Intrinsic::start_loop_iterations:
7805 case Intrinsic::annotation:
7806 case Intrinsic::ptr_annotation:
7807 Ops.push_back(
II->getArgOperand(0));
7819const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7828 if (!DT.isReachableFromEntry(
I->getParent()))
7843 switch (BO->Opcode) {
7844 case Instruction::Add: {
7870 if (BO->Opcode == Instruction::Sub)
7878 if (BO->Opcode == Instruction::Sub)
7885 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7886 NewBO->Opcode != Instruction::Sub)) {
7896 case Instruction::Mul: {
7917 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7926 case Instruction::UDiv:
7930 case Instruction::URem:
7934 case Instruction::Sub: {
7937 Flags = getNoWrapFlagsFromUB(BO->
Op);
7942 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
7945 if (HasPtrLHS || HasPtrRHS) {
7950 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
7951 bool BothPtr) ->
const SCEV * {
7954 const SCEV *PtrSCEV =
getSCEV(PtrOp);
7964 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
7965 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
7973 case Instruction::And:
7979 if (CI->isMinusOne())
7981 const APInt &
A = CI->getValue();
7987 unsigned LZ =
A.countl_zero();
7988 unsigned TZ =
A.countr_zero();
7993 APInt EffectiveMask =
7995 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
7998 const SCEV *ShiftedLHS =
nullptr;
8002 unsigned MulZeros = OpC->getAPInt().countr_zero();
8003 unsigned GCD = std::min(MulZeros, TZ);
8008 const SCEV *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8030 case Instruction::Or:
8039 case Instruction::Xor:
8042 if (CI->isMinusOne())
8051 if (LBO->getOpcode() == Instruction::And &&
8052 LCI->getValue() == CI->getValue())
8053 if (
const SCEVZeroExtendExpr *Z =
8056 const SCEV *Z0 =
Z->getOperand();
8063 if (CI->getValue().isMask(Z0TySize))
8069 APInt Trunc = CI->getValue().trunc(Z0TySize);
8078 case Instruction::Shl:
8096 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8105 ConstantInt *
X = ConstantInt::get(
8111 case Instruction::AShr:
8133 const SCEV *AddTruncateExpr =
nullptr;
8134 ConstantInt *ShlAmtCI =
nullptr;
8135 const SCEV *AddConstant =
nullptr;
8137 if (L &&
L->getOpcode() == Instruction::Add) {
8145 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8152 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8160 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8165 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8170 if (AddTruncateExpr && ShlAmtCI) {
8182 const APInt &ShlAmt = ShlAmtCI->
getValue();
8186 const SCEV *CompositeExpr =
8188 if (
L->getOpcode() != Instruction::Shl)
8189 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8198 switch (
U->getOpcode()) {
8199 case Instruction::Trunc:
8202 case Instruction::ZExt:
8205 case Instruction::SExt:
8215 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8216 Type *Ty =
U->getType();
8224 case Instruction::BitCast:
8230 case Instruction::PtrToAddr: {
8237 case Instruction::PtrToInt:
8241 case Instruction::IntToPtr:
8245 case Instruction::SDiv:
8252 case Instruction::SRem:
8259 case Instruction::GetElementPtr:
8262 case Instruction::PHI:
8265 case Instruction::Select:
8266 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8269 case Instruction::Call:
8270 case Instruction::Invoke:
8275 switch (
II->getIntrinsicID()) {
8276 case Intrinsic::abs:
8280 case Intrinsic::umax:
8284 case Intrinsic::umin:
8288 case Intrinsic::smax:
8292 case Intrinsic::smin:
8296 case Intrinsic::usub_sat: {
8297 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8298 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8302 case Intrinsic::uadd_sat: {
8303 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8304 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8308 case Intrinsic::start_loop_iterations:
8309 case Intrinsic::annotation:
8310 case Intrinsic::ptr_annotation:
8314 case Intrinsic::vscale:
8334 auto *ExitCountType = ExitCount->
getType();
8335 assert(ExitCountType->isIntegerTy());
8337 1 + ExitCountType->getScalarSizeInBits());
8350 auto CanAddOneWithoutOverflow = [&]() {
8352 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8363 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8393 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8394 assert(L->isLoopExiting(ExitingBlock) &&
8395 "Exiting block must actually branch out of the loop!");
8404 const auto *MaxExitCount =
8412 L->getExitingBlocks(ExitingBlocks);
8415 if (ExitingBlocks.
empty() ||
8430 LoopGuards &Guards) {
8434 const SCEV *TCExpr =
8442 : (
unsigned)Multiple.getZExtValue();
8446 const SCEV *ExitCount) {
8469 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8470 assert(L->isLoopExiting(ExitingBlock) &&
8471 "Exiting block must actually branch out of the loop!");
8481 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8483 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8485 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8495 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8498 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8501 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8509 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8516 return getBackedgeTakenInfo(L).getExact(L,
this);
8518 return getBackedgeTakenInfo(L).getConstantMax(
this);
8520 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8527 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8532 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8536 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8546 for (
PHINode &PN : Header->phis())
8547 if (Visited.
insert(&PN).second)
8551ScalarEvolution::BackedgeTakenInfo &
8552ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8553 auto &BTI = getBackedgeTakenInfo(L);
8554 if (BTI.hasFullInfo())
8557 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8560 return Pair.first->second;
8562 BackedgeTakenInfo
Result =
8563 computeBackedgeTakenCount(L,
true);
8565 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8568ScalarEvolution::BackedgeTakenInfo &
8569ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8575 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8576 BackedgeTakenCounts.try_emplace(L);
8578 return Pair.first->second;
8583 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8590 if (
Result.hasAnyInfo()) {
8593 auto LoopUsersIt = LoopUsers.find(L);
8594 if (LoopUsersIt != LoopUsers.end())
8596 forgetMemoizedResults(ToForget);
8599 for (PHINode &PN :
L->getHeader()->phis())
8600 ConstantEvolutionLoopExitValue.erase(&PN);
8608 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8617 BackedgeTakenCounts.clear();
8618 PredicatedBackedgeTakenCounts.clear();
8619 BECountUsers.clear();
8620 LoopPropertiesCache.clear();
8621 ConstantEvolutionLoopExitValue.clear();
8622 ValueExprMap.clear();
8623 ValuesAtScopes.clear();
8624 ValuesAtScopesUsers.clear();
8625 LoopDispositions.clear();
8626 BlockDispositions.clear();
8627 UnsignedRanges.clear();
8628 SignedRanges.clear();
8629 ExprValueMap.clear();
8631 ConstantMultipleCache.clear();
8632 PredicatedSCEVRewrites.clear();
8634 FoldCacheUser.clear();
8636void ScalarEvolution::visitAndClearUsers(
8641 if (ValueExprMap.
empty()) {
8645 while (!Worklist.
empty()) {
8652 if (It != ValueExprMap.
end()) {
8654 eraseValueFromMap(It->first);
8656 ConstantEvolutionLoopExitValue.erase(PN);
8670 while (!LoopWorklist.
empty()) {
8674 forgetBackedgeTakenCounts(CurrL,
false);
8675 forgetBackedgeTakenCounts(CurrL,
true);
8678 PredicatedSCEVRewrites.remove_if(
8679 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8681 auto LoopUsersItr = LoopUsers.find(CurrL);
8682 if (LoopUsersItr != LoopUsers.end())
8687 visitAndClearUsers(Worklist, Visited, ToForget);
8689 LoopPropertiesCache.erase(CurrL);
8692 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8694 forgetMemoizedResults(ToForget);
8711 visitAndClearUsers(Worklist, Visited, ToForget);
8713 forgetMemoizedResults(ToForget);
8724 visitAndClearUsers(Worklist, Visited, ToForget);
8726 forgetMemoizedResults(ToForget);
8734 auto InvalidateValue = [&](
Value *Val) {
8738 struct InvalidationRootCollector {
8742 InvalidationRootCollector(
Loop *L) : L(L) {}
8744 bool follow(
const SCEV *S) {
8750 if (L->contains(AddRec->
getLoop()))
8755 bool isDone()
const {
return false; }
8758 InvalidationRootCollector
C(L);
8760 forgetMemoizedResults(
C.Roots);
8783 BlockDispositions.clear();
8784 LoopDispositions.clear();
8801 while (!Worklist.
empty()) {
8803 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8804 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8805 if (!LoopDispoRemoved && !BlockDispoRemoved)
8807 auto Users = SCEVUsers.find(Curr);
8808 if (
Users != SCEVUsers.end())
8821const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8825 if (!isComplete() || ExitNotTaken.
empty())
8836 for (
const auto &ENT : ExitNotTaken) {
8837 const SCEV *BECount = ENT.ExactNotTaken;
8840 "We should only have known counts for exiting blocks that dominate "
8843 Ops.push_back(BECount);
8848 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8849 "Predicate should be always true!");
8858const ScalarEvolution::ExitNotTakenInfo *
8859ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8860 const BasicBlock *ExitingBlock,
8861 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8862 for (
const auto &ENT : ExitNotTaken)
8863 if (ENT.ExitingBlock == ExitingBlock) {
8864 if (ENT.hasAlwaysTruePredicate())
8866 else if (Predicates) {
8876const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8878 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8879 if (!getConstantMax())
8882 for (
const auto &ENT : ExitNotTaken)
8883 if (!ENT.hasAlwaysTruePredicate()) {
8891 "No point in having a non-constant max backedge taken count!");
8892 return getConstantMax();
8895const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8897 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8905 for (
const auto &ENT : ExitNotTaken) {
8906 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8909 "We should only have known counts for exiting blocks that "
8915 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8916 "Predicate should be always true!");
8919 if (ExitCounts.
empty())
8928bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8930 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8931 return !ENT.hasAlwaysTruePredicate();
8933 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8949 this->ExactNotTaken = E = ConstantMaxNotTaken;
8950 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8955 "Exact is not allowed to be less precise than Constant Max");
8958 "Exact is not allowed to be less precise than Symbolic Max");
8961 "Symbolic Max is not allowed to be less precise than Constant Max");
8964 "No point in having a non-constant max backedge taken count!");
8966 for (
const auto PredList : PredLists)
8967 for (
const auto *
P : PredList) {
8975 "Backedge count should be int");
8978 "Max backedge count should be int");
8991ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8993 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8994 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8995 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8997 ExitNotTaken.reserve(ExitCounts.
size());
8998 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8999 std::back_inserter(ExitNotTaken),
9000 [&](
const EdgeExitInfo &EEI) {
9001 BasicBlock *ExitBB = EEI.first;
9002 const ExitLimit &EL = EEI.second;
9003 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
9004 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
9009 "No point in having a non-constant max backedge taken count!");
9013ScalarEvolution::BackedgeTakenInfo
9014ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
9015 bool AllowPredicates) {
9017 L->getExitingBlocks(ExitingBlocks);
9019 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9022 bool CouldComputeBECount =
true;
9024 const SCEV *MustExitMaxBECount =
nullptr;
9025 const SCEV *MayExitMaxBECount =
nullptr;
9026 bool MustExitMaxOrZero =
false;
9027 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9038 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9039 if (ExitIfTrue == CI->
isZero())
9043 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9045 assert((AllowPredicates || EL.Predicates.empty()) &&
9046 "Predicated exit limit when predicates are not allowed!");
9051 ++NumExitCountsComputed;
9055 CouldComputeBECount =
false;
9062 "Exact is known but symbolic isn't?");
9063 ++NumExitCountsNotComputed;
9078 DT.dominates(ExitBB, Latch)) {
9079 if (!MustExitMaxBECount) {
9080 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9081 MustExitMaxOrZero = EL.MaxOrZero;
9084 EL.ConstantMaxNotTaken);
9088 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9091 EL.ConstantMaxNotTaken);
9095 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9099 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9105 for (
const auto &Pair : ExitCounts) {
9107 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9109 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9110 {
L, AllowPredicates});
9112 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9113 MaxBECount, MaxOrZero);
9116ScalarEvolution::ExitLimit
9117ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9118 bool IsOnlyExit,
bool AllowPredicates) {
9119 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9123 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9128 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9129 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9130 "It should have one successor in loop and one exit block!");
9141 if (!
L->contains(SBB)) {
9146 assert(Exit &&
"Exiting block must have at least one exit");
9147 return computeExitLimitFromSingleExitSwitch(
9148 L, SI, Exit, IsOnlyExit);
9155 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9156 bool AllowPredicates) {
9157 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9158 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9159 ControlsOnlyExit, AllowPredicates);
9162std::optional<ScalarEvolution::ExitLimit>
9163ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9164 bool ExitIfTrue,
bool ControlsOnlyExit,
9165 bool AllowPredicates) {
9167 (void)this->ExitIfTrue;
9168 (void)this->AllowPredicates;
9170 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9171 this->AllowPredicates == AllowPredicates &&
9172 "Variance in assumed invariant key components!");
9173 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9174 if (Itr == TripCountMap.end())
9175 return std::nullopt;
9179void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9181 bool ControlsOnlyExit,
9182 bool AllowPredicates,
9184 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9185 this->AllowPredicates == AllowPredicates &&
9186 "Variance in assumed invariant key components!");
9188 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9189 assert(InsertResult.second &&
"Expected successful insertion!");
9194ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9195 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9196 bool ControlsOnlyExit,
bool AllowPredicates) {
9198 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9202 ExitLimit EL = computeExitLimitFromCondImpl(
9203 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9204 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9208ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9209 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9210 bool ControlsOnlyExit,
bool AllowPredicates) {
9212 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9213 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9214 return *LimitFromBinOp;
9220 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9221 if (EL.hasFullInfo() || !AllowPredicates)
9225 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9245 const WithOverflowInst *WO;
9260 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9261 ControlsOnlyExit, AllowPredicates);
9262 if (EL.hasAnyInfo())
9267 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9270std::optional<ScalarEvolution::ExitLimit>
9271ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9275 bool AllowPredicates) {
9284 return std::nullopt;
9288 ExitLimit EL0 = computeExitLimitFromCondCached(
9289 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9290 ExitLimit EL1 = computeExitLimitFromCondCached(
9291 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9296 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9301 if (EitherMayExit) {
9311 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9313 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9316 EL1.ConstantMaxNotTaken);
9318 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9320 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9323 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9327 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9328 BECount = EL0.ExactNotTaken;
9341 SymbolicMaxBECount =
9343 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9347ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9348 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9349 bool AllowPredicates) {
9361 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9363 if (EL.hasAnyInfo())
9366 auto *ExhaustiveCount =
9367 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9370 return ExhaustiveCount;
9372 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9375ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9377 bool ControlsOnlyExit,
bool AllowPredicates) {
9402 ConstantRange CompRange =
9420 InnerLHS = ZExt->getOperand();
9467 if (EL.hasAnyInfo())
9484 if (EL.hasAnyInfo())
return EL;
9517 ControlsOnlyExit, AllowPredicates);
9518 if (EL.hasAnyInfo())
9536 ControlsOnlyExit, AllowPredicates);
9537 if (EL.hasAnyInfo())
9548ScalarEvolution::ExitLimit
9549ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9551 BasicBlock *ExitingBlock,
9552 bool ControlsOnlyExit) {
9553 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9556 if (
Switch->getDefaultDest() == ExitingBlock)
9560 "Default case must not exit the loop!");
9566 if (EL.hasAnyInfo())
9578 "Evaluation of SCEV at constant didn't fold correctly?");
9582ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9592 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9599 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9601 unsigned &OutShiftAmt) {
9602 using namespace PatternMatch;
9604 ConstantInt *ShiftAmt;
9606 OutOpCode = Instruction::LShr;
9608 OutOpCode = Instruction::AShr;
9610 OutOpCode = Instruction::Shl;
9615 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9630 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9632 unsigned &ShiftAmtOut) {
9633 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9649 if (MatchPositiveShift(
LHS, V, OpC, Amt)) {
9650 PostShiftOpCode = OpC;
9656 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9659 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9665 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9672 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9678 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9690 ConstantInt *StableValue =
nullptr;
9695 case Instruction::AShr: {
9702 if (
Known.isNonNegative())
9703 StableValue = ConstantInt::get(Ty, 0);
9704 else if (
Known.isNegative())
9705 StableValue = ConstantInt::get(Ty, -1,
true);
9711 case Instruction::LShr:
9712 case Instruction::Shl:
9722 "Otherwise cannot be an operand to a branch instruction");
9724 if (
Result->isNullValue()) {
9733 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9735 const SCEV *StartSCEV =
getSCEV(StartValue);
9739 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9740 MaxBTC = std::min(MaxBTC, RangeBTC);
9744 const SCEV *UpperBound =
9762 if (
const Function *
F = CI->getCalledFunction())
9772 if (!L->contains(
I))
return false;
9777 return L->getHeader() ==
I->getParent();
9856 if (!
I)
return nullptr;
9870 std::vector<Constant*>
Operands(
I->getNumOperands());
9872 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9881 if (!
C)
return nullptr;
9903 if (IncomingVal != CurrentVal) {
9906 IncomingVal = CurrentVal;
9918ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9921 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9930 DenseMap<Instruction *, Constant *> CurrentIterVals;
9932 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9938 for (PHINode &
PHI : Header->phis()) {
9940 CurrentIterVals[&
PHI] = StartCST;
9942 if (!CurrentIterVals.
count(PN))
9943 return RetVal =
nullptr;
9949 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9952 unsigned IterationNum = 0;
9954 for (; ; ++IterationNum) {
9955 if (IterationNum == NumIterations)
9956 return RetVal = CurrentIterVals[PN];
9960 DenseMap<Instruction *, Constant *> NextIterVals;
9965 NextIterVals[PN] = NextPHI;
9967 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9973 for (
const auto &
I : CurrentIterVals) {
9975 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9980 for (
const auto &
I : PHIsToCompute) {
9981 PHINode *
PHI =
I.first;
9984 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9987 if (NextPHI !=
I.second)
9988 StoppedEvolving =
false;
9993 if (StoppedEvolving)
9994 return RetVal = CurrentIterVals[PN];
9996 CurrentIterVals.swap(NextIterVals);
10000const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
10010 DenseMap<Instruction *, Constant *> CurrentIterVals;
10012 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10015 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
10017 for (PHINode &
PHI : Header->phis()) {
10019 CurrentIterVals[&
PHI] = StartCST;
10021 if (!CurrentIterVals.
count(PN))
10029 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10036 if (CondVal->getValue() ==
uint64_t(ExitWhen)) {
10037 ++NumBruteForceTripCountsComputed;
10042 DenseMap<Instruction *, Constant *> NextIterVals;
10048 for (
const auto &
I : CurrentIterVals) {
10050 if (!
PHI ||
PHI->getParent() != Header)
continue;
10053 for (PHINode *
PHI : PHIsToCompute) {
10055 if (NextPHI)
continue;
10057 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10060 CurrentIterVals.
swap(NextIterVals);
10071 auto &
Values = ValuesAtScopes[V];
10075 return LS.second ? LS.second :
SCEVUse(V);
10077 Values.emplace_back(L,
nullptr);
10080 SCEVUse C = computeSCEVAtScope(V, L);
10081 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10082 if (LS.first == L) {
10088 ValuesAtScopesUsers[
C.getPointer()].push_back({L, V});
10115 switch (V->getSCEVType()) {
10148 assert(!
C->getType()->isPointerTy() &&
10149 "Can only have one pointer, and it must be last");
10174const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10175 SmallVectorImpl<SCEVUse> &NewOps) {
10209SCEVUse ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10210 switch (
V->getSCEVType()) {
10221 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10232 for (++i; i !=
e; ++i)
10272 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10282 for (++i; i !=
e; ++i) {
10287 return getWithOperands(V, NewOps);
10302 const Loop *CurrLoop = this->LI[
I->getParent()];
10313 if (BackedgeTakenCount->
isZero()) {
10314 Value *InitValue =
nullptr;
10315 bool MultipleInitValues =
false;
10321 MultipleInitValues =
true;
10326 if (!MultipleInitValues && InitValue)
10335 unsigned InLoopPred =
10346 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10360 SmallVector<Constant *, 4>
Operands;
10362 bool MadeImprovement =
false;
10377 MadeImprovement |= OrigV != OpV;
10382 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10387 if (!MadeImprovement)
10408const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10410 return stripInjectiveFunctions(ZExt->getOperand());
10412 return stripInjectiveFunctions(SExt->getOperand());
10430 assert(
A != 0 &&
"A must be non-zero.");
10446 if (MinTZ < Mult2 && L->getLoopPredecessor())
10448 if (MinTZ < Mult2) {
10471 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10491static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10497 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10498 << *AddRec <<
'\n');
10501 if (!LC || !MC || !
NC) {
10502 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10503 return std::nullopt;
10509 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10517 N =
N.sext(NewWidth);
10518 M = M.sext(NewWidth);
10519 L = L.sext(NewWidth);
10536 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10537 <<
", multiplied by " <<
T <<
'\n');
10546 std::optional<APInt>
Y) {
10548 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10551 return XW.
slt(YW) ? *
X : *
Y;
10554 return std::nullopt;
10555 return X ? *
X : *
Y;
10572 return std::nullopt;
10573 unsigned W =
X->getBitWidth();
10593static std::optional<APInt>
10599 return std::nullopt;
10602 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10603 std::optional<APInt>
X =
10606 return std::nullopt;
10611 return std::nullopt;
10626static std::optional<APInt>
10630 "Starting value of addrec should be 0");
10631 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10632 <<
Range <<
", addrec " << *AddRec <<
'\n');
10636 "Addrec's initial value should be in range");
10642 return std::nullopt;
10652 auto SolveForBoundary =
10653 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10656 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10657 << Bound <<
" (before multiplying by " << M <<
")\n");
10660 std::optional<APInt> SO;
10663 "signed overflow\n");
10667 "unsigned overflow\n");
10668 std::optional<APInt> UO =
10671 auto LeavesRange = [&] (
const APInt &
X) {
10674 if (
Range.contains(V0->getValue()))
10679 if (
Range.contains(
V1->getValue()))
10688 return {std::nullopt,
false};
10693 if (LeavesRange(*Min))
10694 return { Min,
true };
10695 std::optional<APInt> Max = Min == SO ? UO : SO;
10696 if (LeavesRange(*Max))
10697 return { Max,
true };
10700 return {std::nullopt,
true};
10707 auto SL = SolveForBoundary(
Lower);
10708 auto SU = SolveForBoundary(
Upper);
10711 if (!SL.second || !SU.second)
10712 return std::nullopt;
10755ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10757 bool ControlsOnlyExit,
10758 bool AllowPredicates) {
10769 if (
C->getValue()->isZero())
return C;
10773 const SCEVAddRecExpr *AddRec =
10776 if (!AddRec && AllowPredicates)
10782 if (!AddRec || AddRec->
getLoop() != L)
10793 return ExitLimit(R, R, R,
false, Predicates);
10851 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10881 const SCEV *
Exact =
10889 const SCEV *SymbolicMax =
10891 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10900 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10908 return ExitLimit(
E, M, S,
false, Predicates);
10911ScalarEvolution::ExitLimit
10912ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10920 if (!
C->getValue()->isZero())
10930std::pair<const BasicBlock *, const BasicBlock *>
10931ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10942 if (
const Loop *L = LI.getLoopFor(BB))
10943 return {
L->getLoopPredecessor(),
L->getHeader()};
10945 return {
nullptr, BB};
10954 if (
A ==
B)
return true;
10969 if (ComputesEqualValues(AI, BI))
10977 const SCEV *Op0, *Op1;
10996 auto TrivialCase = [&](
bool TriviallyTrue) {
11005 const SCEV *NewLHS, *NewRHS;
11029 return TrivialCase(
false);
11030 return TrivialCase(
true);
11049 RAdd->hasNoSignedWrap()) ||
11051 RAdd->hasNoUnsignedWrap())) {
11071 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
11072 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
11075 C->getAPInt().isStrictlyPositive()) ||
11099 const APInt &
RA = RC->getAPInt();
11101 bool SimplifiedByConstantRange =
false;
11106 return TrivialCase(
true);
11108 return TrivialCase(
false);
11117 Changed = SimplifiedByConstantRange =
true;
11121 if (!SimplifiedByConstantRange) {
11138 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11144 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11150 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11156 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11176 return TrivialCase(
true);
11178 return TrivialCase(
false);
11283 auto NonRecursive = [OrNegative](
const SCEV *S) {
11285 return C->getAPInt().isPowerOf2() ||
11286 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11292 if (NonRecursive(S))
11302 const SCEV *S, uint64_t M,
11311 APInt C = Cst->getAPInt();
11312 return C.urem(M) == 0;
11318 const SCEV *SmodM =
11339 [&](
SCEVUse Op) { return isKnownMultipleOf(Op, M, Predicates); }))
11346 return isKnownMultipleOf(Op, M, Predicates);
11352 return isKnownMultipleOf(Op, M, Predicates);
11359 for (
auto *
A : *Predicates)
11360 if (
A->implies(
P, *
this))
11373std::pair<const SCEV *, const SCEV *>
11376 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11378 return { Start, Start };
11380 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11389 getUsedLoops(LHS, LoopsUsed);
11390 getUsedLoops(RHS, LoopsUsed);
11392 if (LoopsUsed.
empty())
11397 for (
const auto *L1 : LoopsUsed)
11398 for (
const auto *L2 : LoopsUsed)
11399 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11400 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11401 "Domination relationship is not a linear order");
11431 SplitRHS.second) &&
11441 isKnownPredicateViaSplitting(Pred, LHS, RHS) ||
11442 isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11452 return std::nullopt;
11467 if (KnownWithoutContext)
11468 return KnownWithoutContext;
11475 return std::nullopt;
11481 const Loop *L = LHS->getLoop();
11486std::optional<ScalarEvolution::MonotonicPredicateType>
11489 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11495 auto ResultSwapped =
11498 assert(*ResultSwapped != *Result &&
11499 "monotonicity should flip as we flip the predicate");
11506std::optional<ScalarEvolution::MonotonicPredicateType>
11507ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11521 return std::nullopt;
11525 "Should be greater or less!");
11529 if (!LHS->hasNoUnsignedWrap())
11530 return std::nullopt;
11534 "Relational predicate is either signed or unsigned!");
11535 if (!
LHS->hasNoSignedWrap())
11536 return std::nullopt;
11538 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11546 return std::nullopt;
11549std::optional<ScalarEvolution::LoopInvariantPredicate>
11556 return std::nullopt;
11563 if (!ArLHS || ArLHS->
getLoop() != L)
11564 return std::nullopt;
11568 return std::nullopt;
11594 return std::nullopt;
11631 return std::nullopt;
11634std::optional<ScalarEvolution::LoopInvariantPredicate>
11639 Pred, LHS, RHS, L, CtxI, MaxIter))
11649 Pred, LHS, RHS, L, CtxI,
Op))
11651 return std::nullopt;
11654std::optional<ScalarEvolution::LoopInvariantPredicate>
11669 return std::nullopt;
11676 if (!AR || AR->
getLoop() != L)
11677 return std::nullopt;
11682 Pred = Pred.dropSameSign();
11686 return std::nullopt;
11692 if (Step != One && Step != MinusOne)
11693 return std::nullopt;
11699 return std::nullopt;
11705 return std::nullopt;
11713 if (Step == MinusOne)
11717 return std::nullopt;
11723bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11729 auto CheckRange = [&](
bool IsSigned) {
11732 return RangeLHS.
icmp(Pred, RangeRHS);
11741 if (CheckRange(
true) || CheckRange(
false))
11750bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11757 APInt &OutC2,
SCEVFlags ExpectedFlags) {
11758 SCEVUse XNonConstOp, XConstOp;
11759 SCEVUse YNonConstOp, YConstOp;
11764 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11765 XConstOp =
nullptr;
11767 XFlagsPresent = ExpectedFlags;
11772 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11773 YConstOp =
nullptr;
11775 YFlagsPresent = ExpectedFlags;
11778 if (YNonConstOp != XNonConstOp)
11786 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11789 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11851bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11872bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11873 const SCEV *
LHS,
const SCEV *
RHS) {
11878 return any_of(*BB, [&](
const Instruction &
I) {
11879 using namespace llvm::PatternMatch;
11884 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11898 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11903 "This cannot be done on broken IR!");
11906 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11915 if (LoopContinuePredicate &&
11916 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11917 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11922 if (WalkingBEDominatingConds)
11928 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11929 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11936 const SCEV *LoopCounter =
11944 for (
auto &AssumeVH : AC.assumptions()) {
11951 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11955 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11958 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11959 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11960 assert(DTN &&
"should reach the loop header before reaching the root!");
11963 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11981 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
11994 if (!DT.isReachableFromEntry(BB))
11998 "This cannot be done on broken IR!");
12006 const bool ProvingStrictComparison =
12008 bool ProvedNonStrictComparison =
false;
12009 bool ProvedNonEquality =
false;
12012 if (!ProvedNonStrictComparison)
12013 ProvedNonStrictComparison = Fn(NonStrictPredicate);
12014 if (!ProvedNonEquality)
12016 if (ProvedNonStrictComparison && ProvedNonEquality)
12021 if (ProvingStrictComparison) {
12023 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
12025 if (SplitAndProve(ProofFn))
12030 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
12032 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
12034 if (ProvingStrictComparison) {
12036 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
12038 if (SplitAndProve(ProofFn))
12047 const Loop *ContainingLoop = LI.getLoopFor(BB);
12049 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
12053 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
12054 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
12057 if (!BlockEntryPredicate)
12066 for (
auto &AssumeVH : AC.assumptions()) {
12070 if (!DT.dominates(CI, BB))
12073 if (ProveViaCond(CI->getArgOperand(0),
false))
12079 F.getParent(), Intrinsic::experimental_guard);
12081 for (
const auto *GU : GuardDecl->users())
12083 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12084 if (ProveViaCond(Guard->getArgOperand(0),
false))
12099 "LHS is not available at Loop Entry");
12101 "RHS is not available at Loop Entry");
12103 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12114 if (FoundCondValue ==
12118 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12122 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12125 const Value *Op0, *Op1;
12128 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12132 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12133 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12137 if (!ICI)
return false;
12141 CmpPredicate FoundPred;
12150 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12153bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12154 const SCEV *
RHS, CmpPredicate FoundPred,
12155 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12156 const Instruction *CtxI) {
12166 auto *WideType = FoundLHS->
getType();
12178 TruncFoundLHS, TruncFoundRHS, CtxI))
12204 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12208bool ScalarEvolution::isImpliedCondBalancedTypes(
12213 "Types should be balanced!");
12220 if (FoundLHS == FoundRHS)
12224 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12236 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12251 LHS, FoundLHS, FoundRHS, CtxI);
12253 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12265 if (IsSignFlippedPredicate(Pred, FoundPred) &&
12266 isImpliedCondViaSignFlippedPred(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12269 if (IsSignFlippedPredicate(SwappedPred, FoundPred) &&
12270 isImpliedCondViaSignFlippedPred(SwappedPred,
RHS,
LHS, FoundLHS, FoundRHS,
12278 const SCEVConstant *
C =
nullptr;
12279 const SCEV *
V =
nullptr;
12297 if (Min ==
C->getAPInt()) {
12302 APInt SharperMin = Min + 1;
12305 case ICmpInst::ICMP_SGE:
12306 case ICmpInst::ICMP_UGE:
12309 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12314 case ICmpInst::ICMP_SGT:
12315 case ICmpInst::ICMP_UGT:
12325 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12330 case ICmpInst::ICMP_SLE:
12331 case ICmpInst::ICMP_ULE:
12332 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12333 LHS, V, getConstant(SharperMin), CtxI))
12337 case ICmpInst::ICMP_SLT:
12338 case ICmpInst::ICMP_ULT:
12339 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12340 LHS, V, getConstant(Min), CtxI))
12354 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12358 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12361 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12368bool ScalarEvolution::isImpliedCondViaSignFlippedPred(
12369 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12370 const SCEV *FoundRHS,
const Instruction *CtxI) {
12375 isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12399 CmpPredicate BoundPred =
12401 if (isKnownViaNonRecursiveReasoning(BoundPred, FoundRHS, SignedMin)) {
12404 if (isImpliedCondOperands(Pred,
LHS,
RHS, Bound, FoundLHS, CtxI))
12412 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS))
12419 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS))
12434std::optional<APInt>
12441 APInt DiffMul(BW, 1);
12444 for (
unsigned I = 0;
I < 8; ++
I) {
12453 if (LAR->getLoop() != MAR->getLoop())
12454 return std::nullopt;
12458 if (!LAR->isAffine() || !MAR->isAffine())
12459 return std::nullopt;
12461 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12462 return std::nullopt;
12464 Less = LAR->getStart();
12465 More = MAR->getStart();
12470 auto MatchConstMul =
12471 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12476 return std::nullopt;
12478 if (
auto MatchedMore = MatchConstMul(More)) {
12479 if (
auto MatchedLess = MatchConstMul(
Less)) {
12480 if (MatchedMore->second == MatchedLess->second) {
12481 More = MatchedMore->first;
12482 Less = MatchedLess->first;
12483 DiffMul *= MatchedMore->second;
12494 Diff +=
C->getAPInt() * DiffMul;
12497 Diff -=
C->getAPInt() * DiffMul;
12500 Multiplicity[S] +=
Mul;
12502 auto Decompose = [&](
const SCEV *S,
int Mul) {
12509 Decompose(More, 1);
12510 Decompose(
Less, -1);
12514 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12515 for (
const auto &[S,
Mul] : Multiplicity) {
12520 return std::nullopt;
12522 }
else if (
Mul == -1) {
12524 return std::nullopt;
12527 return std::nullopt;
12531 if (NewMore == More || NewLess ==
Less)
12532 return std::nullopt;
12538 if (!More && !
Less)
12542 if (!More || !
Less)
12543 return std::nullopt;
12547 return std::nullopt;
12550bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12572 const auto *Latch = L->getLoopLatch();
12575 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12584 const auto *Latch = L->getLoopLatch();
12587 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12597bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12600 const SCEV *FoundLHS,
12601 const SCEV *FoundRHS) {
12610 if (!AddRecFoundLHS)
12617 const Loop *
L = AddRecFoundLHS->getLoop();
12618 if (L != AddRecLHS->getLoop())
12657 if (!RDiff || *LDiff != *RDiff)
12660 if (LDiff->isMinValue())
12663 APInt FoundRHSLimit;
12666 FoundRHSLimit = -(*RDiff);
12678bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12679 const SCEV *
RHS,
const SCEV *FoundLHS,
12680 const SCEV *FoundRHS,
unsigned Depth) {
12681 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12685 bool Erased = PendingMerges.erase(LPhi);
12686 assert(Erased &&
"Failed to erase LPhi!");
12690 bool Erased = PendingMerges.erase(RPhi);
12691 assert(Erased &&
"Failed to erase RPhi!");
12699 if (!PendingMerges.insert(Phi).second)
12713 if (!PendingMerges.insert(Phi).second)
12719 if (!LPhi && !RPhi)
12730 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12734 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12735 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12736 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12737 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12740 if (RPhi && RPhi->getParent() == LBB) {
12747 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12748 if (!ProvedEasily(L, R))
12759 auto *RLoop = RAR->
getLoop();
12760 auto *Predecessor = RLoop->getLoopPredecessor();
12761 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12763 if (!ProvedEasily(L1, RAR->
getStart()))
12765 auto *Latch = RLoop->getLoopLatch();
12766 assert(Latch &&
"Loop with AddRec with no latch?");
12787 if (
auto *
Loop = LI.getLoopFor(LBB))
12790 if (!ProvedEasily(L,
RHS))
12797bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12800 const SCEV *FoundLHS,
12801 const SCEV *FoundRHS) {
12804 if (
RHS == FoundRHS) {
12809 if (
LHS != FoundLHS)
12816 Value *Shiftee, *ShiftValue;
12818 using namespace PatternMatch;
12819 if (
match(SUFoundRHS->getValue(),
12821 auto *ShifteeS =
getSCEV(Shiftee);
12839bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12840 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12841 const SCEV *FoundRHS) {
12873 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12881 return Diff == FoundDiff;
12884bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12886 const SCEV *FoundLHS,
12887 const SCEV *FoundRHS,
12888 const Instruction *CtxI) {
12889 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12891 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12893 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12894 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12896 isImpliedCondOperandsViaMatchingDiff(Pred,
LHS,
RHS, FoundLHS,
12898 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12902template <
typename MinMaxExprType>
12904 const SCEV *Candidate) {
12909 return is_contained(MinMaxExpr->operands(), Candidate);
12922 const SCEV *LStart, *RStart, *Step;
13019bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
13021 const SCEV *FoundLHS,
13022 const SCEV *FoundRHS,
13026 "LHS and RHS have different sizes?");
13029 "FoundLHS and FoundRHS have different sizes?");
13063 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
13065 return Ext->getOperand();
13072 auto *OrigLHS =
LHS;
13073 auto *OrigFoundLHS = FoundLHS;
13074 LHS = GetOpFromSExt(
LHS);
13075 FoundLHS = GetOpFromSExt(FoundLHS);
13078 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
13081 FoundRHS,
Depth + 1);
13094 if (!LHSAddExpr->hasNoSignedWrap())
13097 SCEVUse LL = LHSAddExpr->getOperand(0);
13098 SCEVUse LR = LHSAddExpr->getOperand(1);
13102 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
13103 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
13108 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
13114 using namespace llvm::PatternMatch;
13133 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13141 auto *DTy = Denominator->getType();
13142 auto *FRHSTy = FoundRHS->
getType();
13143 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13162 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13173 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13175 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13183 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13216bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13220 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13224 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13227bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13230 const SCEV *FoundLHS,
13231 const SCEV *FoundRHS) {
13267 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13273bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13274 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13275 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13289 ConstantRange FoundLHSRange =
13293 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13300 return LHSRange.
icmp(Pred, ConstRHS);
13303bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13304 bool IsSigned,
bool Invert) {
13311 APInt MaxRHS = getRangeMax(
RHS,
true, Invert);
13316 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13319 APInt MaxRHS = getRangeMax(
RHS,
false, Invert);
13324 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13337ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
const SCEV *Stride,
13339 bool IsSigned,
bool Invert) {
13354 APInt MinStart = getRangeMin(Start, IsSigned, Invert);
13367 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13373 APInt MaxEnd = getRangeMax(
End, IsSigned, Invert);
13379 :
APIntOps::umax(MaxEnd, MinStart);
13381 APInt Delta = MaxEnd - MinStart;
13385 const SCEV *DeltaExpr =
13393ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13394 const Loop *L,
bool IsSigned,
bool Invert,
13395 bool ControlsOnlyExit,
bool AllowPredicates) {
13405 bool PredicatedIV =
false;
13407 if (!
IV && !Invert) {
13411 auto canProveNUW = [&]() {
13414 if (!ControlsOnlyExit)
13435 Limit = Limit.
zext(OuterBitWidth);
13447 Type *Ty = ZExt->getType();
13457 if (!
IV && AllowPredicates) {
13462 PredicatedIV =
true;
13466 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13480 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13487 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13490 const SCEV *GuardedStride = Stride;
13494 bool IVMayOverflow =
true;
13498 if (!PositiveStride) {
13501 GuardedStride = LoopGuardedStride;
13502 PositiveStride =
true;
13509 if (!PositiveStride) {
13558 const SCEVPredicate *
P =
13579 auto wouldZeroStrideBeUB = [&]() {
13591 if (!wouldZeroStrideBeUB()) {
13598 IVMayOverflow = canIVOverflowOnLT(
RHS, GuardedStride, IsSigned, Invert) &&
13600 GuardedStride, IsSigned, Invert);
13601 if (IVMayOverflow && !NoWrap)
13614 const SCEV *
Start =
IV->getStart();
13620 const SCEV *OrigStart =
Start;
13621 const SCEV *OrigRHS =
RHS;
13622 if (
Start->getType()->isPointerTy()) {
13636 assert(!Invert &&
"RHS must be loop-invariant for Invert");
13638 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13639 any(RHSAddRec->getNoWrapFlags())) {
13652 const SCEV *RHSStart = RHSAddRec->getStart();
13653 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13665 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13674 BECountIfBackedgeTaken =
13701 bool AddingStrideMinusOneMayOverflow = IVMayOverflow && [&] {
13748 if (!Invert && (Start == Stride || Start ==
getMinusSCEV(Stride, One))) {
13765 auto StepBack = [&](
const SCEV *
V,
const SCEV *
Offset) ->
const SCEV * {
13770 auto Distance = [&](
const SCEV *From,
const SCEV *To) {
13774 const SCEV *OrigPrevStart = StepBack(OrigStart, Stride);
13781 if ((!AddingStrideMinusOneMayOverflow ||
13813 const SCEV *Numerator =
13819 auto canProveRHSIsAtOrBeyondStart = [&]() {
13824 auto SwapIfInverted = [&](
const SCEV *
A,
const SCEV *
B) {
13825 return Invert ? std::pair(
B,
A) : std::pair(
A,
B);
13834 auto [GELHS, GERHS] = SwapIfInverted(OrigRHS, OrigStart);
13849 auto [GTLHS, GTRHS] = SwapIfInverted(OrigRHS, StepBack(OrigStart, One));
13855 if (canProveRHSIsAtOrBeyondStart()) {
13878 const SCEV *Delta = Distance(Start,
End);
13879 if (!AddingStrideMinusOneMayOverflow) {
13891 const SCEV *ConstantMaxBECount;
13892 bool MaxOrZero =
false;
13894 ConstantMaxBECount = BECount;
13896 ConstantMaxBECount = computeMaxBECountForLT(
13903 const APInt *IfTaken, *RangeMax;
13906 IfTaken->
ugt(*RangeMax)) {
13907 ConstantMaxBECount =
getZero(BECountIfBackedgeTaken->getType());
13909 ConstantMaxBECount = BECountIfBackedgeTaken;
13919 const SCEV *SymbolicMaxBECount =
13921 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13927 if (
Range.isFullSet())
13932 if (!SC->getValue()->isZero()) {
13938 return ShiftedAddRec->getNumIterationsInRange(
13939 Range.subtract(SC->getAPInt()), SE);
13983 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13984 "Linear scev computation is off in a bad way!");
14015 assert(!
Last->isZero() &&
"Recurrency with zero step?");
14048 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14050 SE->ConstantEvolutionLoopExitValue.erase(PN);
14051 SE->eraseValueFromMap(getValPtr());
14055void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
14056 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14066 : CallbackVH(
V), SE(se) {}
14075 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
14077 LoopDispositions(64), BlockDispositions(64) {
14089 F.getParent(), Intrinsic::experimental_guard);
14090 HasGuards = GuardDecl && !GuardDecl->use_empty();
14094 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
14095 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14096 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14097 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14098 PendingMerges(
std::
move(Arg.PendingMerges)),
14099 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14100 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14101 PredicatedBackedgeTakenCounts(
14102 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14103 BECountUsers(
std::
move(Arg.BECountUsers)),
14104 ConstantEvolutionLoopExitValue(
14105 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14106 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14107 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14108 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14109 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14110 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14111 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14112 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14113 SignedRanges(
std::
move(Arg.SignedRanges)),
14114 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14115 UniquePreds(
std::
move(Arg.UniquePreds)),
14116 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14117 ConstantSCEVs(
std::
move(Arg.ConstantSCEVs)),
14118 LoopUsers(
std::
move(Arg.LoopUsers)),
14119 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14120 FirstUnknown(Arg.FirstUnknown),
14121 NextUnknownOrderID(Arg.NextUnknownOrderID) {
14122 Arg.FirstUnknown =
nullptr;
14131 Tmp->~SCEVUnknown();
14133 FirstUnknown =
nullptr;
14135 ExprValueMap.clear();
14136 ValueExprMap.clear();
14138 BackedgeTakenCounts.clear();
14139 PredicatedBackedgeTakenCounts.clear();
14141 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14142 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14143 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14144 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14166 L->getHeader()->printAsOperand(OS,
false);
14170 L->getExitingBlocks(ExitingBlocks);
14171 if (ExitingBlocks.
size() != 1)
14172 OS <<
"<multiple exits> ";
14176 OS <<
"backedge-taken count is ";
14179 OS <<
"Unpredictable backedge-taken count.";
14182 if (ExitingBlocks.
size() > 1)
14183 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14184 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14192 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14195 OS <<
"\n Predicates:\n";
14196 for (
const auto *
P : Predicates)
14204 L->getHeader()->printAsOperand(OS,
false);
14209 OS <<
"constant max backedge-taken count is ";
14212 OS <<
", actual taken count either this or zero.";
14214 OS <<
"Unpredictable constant max backedge-taken count. ";
14219 L->getHeader()->printAsOperand(OS,
false);
14224 OS <<
"symbolic max backedge-taken count is ";
14227 OS <<
", actual taken count either this or zero.";
14229 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14233 if (ExitingBlocks.
size() > 1)
14234 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14235 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14245 OS <<
"\n predicated symbolic max exit count for "
14246 << ExitingBlock->
getName() <<
": ";
14248 OS <<
"\n Predicates:\n";
14249 for (
const auto *
P : Predicates)
14260 L->getHeader()->printAsOperand(OS,
false);
14263 OS <<
"Predicated backedge-taken count is ";
14266 OS <<
"Unpredictable predicated backedge-taken count.";
14268 OS <<
" Predicates:\n";
14269 for (
const auto *
P : Preds)
14274 auto *PredConstantMax =
14276 if (PredConstantMax != ConstantBTC) {
14278 L->getHeader()->printAsOperand(OS,
false);
14281 OS <<
"Predicated constant max backedge-taken count is ";
14284 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14286 OS <<
" Predicates:\n";
14287 for (
const auto *
P : Preds)
14292 auto *PredSymbolicMax =
14294 if (SymbolicBTC != PredSymbolicMax) {
14296 L->getHeader()->printAsOperand(OS,
false);
14299 OS <<
"Predicated symbolic max backedge-taken count is ";
14302 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14304 OS <<
" Predicates:\n";
14305 for (
const auto *
P : Preds)
14311 L->getHeader()->printAsOperand(OS,
false);
14338 OS <<
"Computable";
14348 OS <<
"DoesNotDominate";
14354 OS <<
"ProperlyDominates";
14371 OS <<
"Classifying expressions for: ";
14372 F.printAsOperand(OS,
false);
14387 const Loop *L = LI.getLoopFor(
I.getParent());
14402 OS <<
"\t\t" "Exits: ";
14405 OS <<
"<<Unknown>>";
14411 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14413 Iter->getHeader()->printAsOperand(OS,
false);
14421 InnerL->getHeader()->printAsOperand(OS,
false);
14432 OS <<
"Determining loop execution counts for: ";
14433 F.printAsOperand(OS,
false);
14444 auto &
Values = LoopDispositions[S];
14445 for (
auto &V :
Values) {
14446 if (V.getPointer() == L)
14451 auto &Values2 = LoopDispositions[S];
14453 if (V.getPointer() == L) {
14462ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14480 if (L->contains(AR->
getLoop()) &&
14482 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14487 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14488 " dominate the contained loop's header?");
14515 bool HasVarying =
false;
14516 bool HasUniform =
false;
14561 auto &
Values = BlockDispositions[S];
14562 for (
auto &V :
Values) {
14563 if (V.getPointer() == BB)
14568 auto &Values2 = BlockDispositions[S];
14570 if (V.getPointer() == BB) {
14579ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14608 bool Proper =
true;
14619 if (Instruction *
I =
14621 if (
I->getParent() == BB)
14623 if (DT.properlyDominates(
I->getParent(), BB))
14642void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14645 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14646 auto It = BECounts.find(L);
14647 if (It != BECounts.end()) {
14648 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14649 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14651 auto UserIt = BECountUsers.find(S);
14652 assert(UserIt != BECountUsers.end());
14657 BECounts.erase(It);
14665 while (!Worklist.
empty()) {
14667 auto Users = SCEVUsers.find(Curr);
14668 if (
Users != SCEVUsers.end())
14669 for (
const auto *User :
Users->second)
14670 if (ToForget.
insert(User).second)
14674 for (
const auto *S : ToForget)
14675 forgetMemoizedResultsImpl(S);
14677 PredicatedSCEVRewrites.remove_if(
14678 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14681void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14682 LoopDispositions.erase(S);
14683 BlockDispositions.erase(S);
14684 UnsignedRanges.erase(S);
14685 SignedRanges.erase(S);
14686 HasRecMap.erase(S);
14687 ConstantMultipleCache.erase(S);
14690 UnsignedWrapViaInductionTried.erase(AR);
14691 SignedWrapViaInductionTried.erase(AR);
14694 auto ExprIt = ExprValueMap.find(S);
14695 if (ExprIt != ExprValueMap.end()) {
14696 for (
Value *V : ExprIt->second) {
14697 auto ValueIt = ValueExprMap.find_as(V);
14698 if (ValueIt != ValueExprMap.end())
14699 ValueExprMap.erase(ValueIt);
14701 ExprValueMap.erase(ExprIt);
14704 auto ScopeIt = ValuesAtScopes.find(S);
14705 if (ScopeIt != ValuesAtScopes.end()) {
14706 for (
const auto &Pair : ScopeIt->second)
14708 llvm::erase(ValuesAtScopesUsers[Pair.second.getPointer()],
14709 std::make_pair(Pair.first, S));
14710 ValuesAtScopes.erase(ScopeIt);
14713 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14714 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14715 for (
const auto &Pair : ScopeUserIt->second)
14718 llvm::erase_if(ValuesAtScopes[Pair.second], [&](
const auto &LS) {
14719 return LS.first == Pair.first && LS.second.getPointer() == S;
14721 ValuesAtScopesUsers.erase(ScopeUserIt);
14724 auto BEUsersIt = BECountUsers.find(S);
14725 if (BEUsersIt != BECountUsers.end()) {
14727 auto Copy = BEUsersIt->second;
14728 for (
const auto &Pair : Copy)
14729 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14730 BECountUsers.erase(BEUsersIt);
14733 auto FoldUser = FoldCacheUser.find(S);
14734 if (FoldUser != FoldCacheUser.end())
14735 for (
auto &KV : FoldUser->second)
14736 FoldCache.erase(KV);
14737 FoldCacheUser.erase(S);
14741ScalarEvolution::getUsedLoops(
const SCEV *S,
14743 struct FindUsedLoops {
14744 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14745 : LoopsUsed(LoopsUsed) {}
14746 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14747 bool follow(
const SCEV *S) {
14753 bool isDone()
const {
return false; }
14756 FindUsedLoops
F(LoopsUsed);
14757 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14760void ScalarEvolution::getReachableBlocks(
14763 Worklist.
push_back(&F.getEntryBlock());
14764 while (!Worklist.
empty()) {
14766 if (!Reachable.
insert(BB).second)
14774 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14781 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14785 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14820 SCEVMapper SCM(SE2);
14822 SE2.getReachableBlocks(ReachableBlocks, F);
14824 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14842 while (!LoopStack.
empty()) {
14848 if (!ReachableBlocks.
contains(L->getHeader()))
14853 auto It = BackedgeTakenCounts.find(L);
14854 if (It == BackedgeTakenCounts.end())
14858 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14878 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14879 if (Delta && !Delta->
isZero()) {
14880 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14881 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14882 dbgs() <<
"New: " << *NewBECount <<
"\n";
14883 dbgs() <<
"Delta: " << *Delta <<
"\n";
14891 while (!Worklist.
empty()) {
14893 if (ValidLoops.
insert(L).second)
14894 Worklist.
append(L->begin(), L->end());
14896 for (
const auto &KV : ValueExprMap) {
14901 "AddRec references invalid loop");
14906 auto It = ExprValueMap.find(KV.second);
14907 if (It == ExprValueMap.end() || !
is_contained(It->second, KV.first)) {
14908 dbgs() <<
"Value " << *KV.first
14909 <<
" is in ValueExprMap but not in ExprValueMap\n";
14914 if (!ReachableBlocks.
contains(
I->getParent()))
14916 const SCEV *OldSCEV = SCM.visit(KV.second);
14918 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14919 if (Delta && !Delta->
isZero()) {
14920 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14921 <<
"Old: " << *OldSCEV <<
"\n"
14922 <<
"New: " << *NewSCEV <<
"\n"
14923 <<
"Delta: " << *Delta <<
"\n";
14929 for (
const auto &KV : ExprValueMap) {
14930 for (
Value *V : KV.second) {
14931 const SCEV *S = ValueExprMap.lookup(V);
14933 dbgs() <<
"Value " << *V
14934 <<
" is in ExprValueMap but not in ValueExprMap\n";
14937 if (S != KV.first) {
14938 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14939 << *KV.first <<
"\n";
14946 for (
const auto &S : UniqueSCEVs) {
14951 auto It = SCEVUsers.find(
Op);
14952 if (It != SCEVUsers.end() && It->second.count(&S))
14954 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14955 <<
" is not being tracked!\n";
14961 for (
const auto &ValueAndVec : ValuesAtScopes) {
14963 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14964 const Loop *L = LoopAndValueAtScope.first;
14965 SCEVUse ValueAtScope = LoopAndValueAtScope.second;
14967 auto It = ValuesAtScopesUsers.find(ValueAtScope.
getPointer());
14968 if (It != ValuesAtScopesUsers.end() &&
14971 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14972 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14978 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14979 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14980 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14981 const Loop *L = LoopAndValue.first;
14982 const SCEV *
Value = LoopAndValue.second;
14984 auto It = ValuesAtScopes.find(
Value);
14987 if (It != ValuesAtScopes.end() &&
any_of(It->second, [&](
const auto &LS) {
14988 return LS.first == L && LS.second.getPointer() == ValueAtScope;
14991 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14992 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14998 auto VerifyBECountUsers = [&](
bool Predicated) {
15000 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
15001 for (
const auto &LoopAndBEInfo : BECounts) {
15002 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
15003 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
15005 auto UserIt = BECountUsers.find(S);
15006 if (UserIt != BECountUsers.end() &&
15007 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
15009 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
15010 <<
" missing from BECountUsers\n";
15017 VerifyBECountUsers(
false);
15018 VerifyBECountUsers(
true);
15021 for (
auto &[S,
Values] : LoopDispositions) {
15022 for (
auto [
Loop, CachedDisposition] :
Values) {
15024 if (CachedDisposition != RecomputedDisposition) {
15025 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
15026 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
15027 << RecomputedDisposition <<
"\n";
15034 for (
auto &[S,
Values] : BlockDispositions) {
15035 for (
auto [BB, CachedDisposition] :
Values) {
15037 if (CachedDisposition != RecomputedDisposition) {
15038 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
15039 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
15040 <<
", actual " << RecomputedDisposition <<
"\n";
15047 for (
auto [
FoldID, Expr] : FoldCache) {
15048 auto I = FoldCacheUser.find(Expr);
15049 if (
I == FoldCacheUser.end()) {
15050 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
15055 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
15059 for (
auto [Expr, IDs] : FoldCacheUser) {
15060 for (
auto &
FoldID : IDs) {
15063 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
15068 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
15069 <<
" != " << *Expr <<
"!\n";
15080 for (
auto [S, Multiple] : ConstantMultipleCache) {
15082 if ((Multiple != 0 && RecomputedMultiple != 0 &&
15083 Multiple.
urem(RecomputedMultiple) != 0 &&
15084 RecomputedMultiple.
urem(Multiple) != 0)) {
15085 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
15086 << *S <<
" : Computed " << RecomputedMultiple
15087 <<
" but cache contains " << Multiple <<
"!\n";
15095 FunctionAnalysisManager::Invalidator &Inv) {
15127 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15128 <<
F.getName() <<
"':\n";
15134 "Scalar Evolution Analysis",
false,
true)
15183 const SCEV *LHS,
const SCEV *RHS) {
15185 assert(LHS->getType() == RHS->getType() &&
15186 "Type mismatch between LHS and RHS");
15189 ID.AddInteger(Pred);
15190 ID.AddPointer(LHS);
15191 ID.AddPointer(RHS);
15193 if (
const auto *S = UniquePreds.lookup(ID, Token))
15197 UniquePreds.insert(Eq, Token);
15208 ID.AddInteger(AddedFlags);
15210 if (
const auto *S = UniquePreds.lookup(ID, Token))
15212 auto *OF =
new (SCEVAllocator)
15214 UniquePreds.insert(OF, Token);
15234 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15235 return Rewriter.visit(S);
15241 for (
const auto *Pred : U->getPredicates())
15243 if (IPred->getLHS() == Expr &&
15245 return IPred->getRHS();
15247 if (IPred->getLHS() == Expr &&
15248 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15249 return IPred->getRHS();
15252 return convertToAddRecWithPreds(Expr);
15255 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15271 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15288 explicit SCEVPredicateRewriter(
15289 const Loop *L, ScalarEvolution &SE,
15290 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15291 const SCEVPredicate *Pred)
15292 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15294 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15297 return Pred && Pred->
implies(
P, SE);
15303 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15306 return addOverflowAssumption(
A);
15315 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15319 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15321 if (!PredicatedRewrite)
15323 for (
const auto *
P : PredicatedRewrite->second){
15326 if (L != WP->getExpr()->getLoop())
15329 if (!addOverflowAssumption(
P))
15332 return PredicatedRewrite->first;
15335 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15336 const SCEVPredicate *Pred;
15345 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15352 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15372 if (!Step->
isOne())
15397 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15398 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15411 return Op->LHS == LHS &&
Op->RHS == RHS;
15418 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15420 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15445 const SCEV *Start = AR->getStart();
15446 const SCEV *OpStart =
Op->AR->getStart();
15451 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15460 const SCEV *Step = AR->getStepRecurrence(SE);
15461 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15482 SCEVFlags ScevFlags = AR->getNoWrapFlags();
15504 for (
const auto *
P : Preds)
15517 return this->implies(I, SE);
15529 const Loop *L = NWrap->getExpr()->getLoop();
15536 return RewrittenAR &&
15542 for (
const auto *Pred : Preds)
15543 Pred->print(OS,
Depth);
15548 for (
const auto *Pred : Set->Preds)
15556 bool CheckImplies = Preds.
size() < 16;
15559 if (CheckImplies &&
implies(
N, SE))
15565 for (
auto *
P : Preds) {
15566 if (CheckImplies &&
N->implies(
P, SE))
15570 Preds = std::move(PrunedPreds);
15571 Preds.push_back(
N);
15578 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15587 SCEVUsers[
Op].insert(
User);
15591 const SCEV *Expr = SE.getSCEV(V);
15596 RewriteEntry &Entry = RewriteMap[Expr];
15599 if (Entry.second && Generation == Entry.first)
15600 return Entry.second;
15605 Expr = Entry.second;
15607 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15608 Entry = {Generation, NewSCEV};
15614 if (!BackedgeCount) {
15616 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15617 for (
const auto *
P : Preds)
15620 return BackedgeCount;
15624 if (!SymbolicMaxBackedgeCount) {
15626 SymbolicMaxBackedgeCount =
15627 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15628 for (
const auto *
P : Preds)
15631 return SymbolicMaxBackedgeCount;
15635 if (!SmallConstantMaxTripCount) {
15637 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15638 for (
const auto *
P : Preds)
15641 return *SmallConstantMaxTripCount;
15645 if (Preds->implies(&Pred, SE))
15648 Preds = std::make_unique<SCEVUnionPredicate>(Preds->getUnionWith(&Pred, SE));
15649 updateGeneration();
15662void PredicatedScalarEvolution::updateGeneration() {
15664 if (++Generation == 0) {
15665 for (
auto &
II : RewriteMap) {
15666 const SCEV *Rewritten =
II.second.second;
15676 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15682 ExtraPreds->
append(NewPreds);
15688 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15694 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15696 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15700 for (
auto *BB : L.getBlocks())
15701 for (
auto &
I : *BB) {
15702 if (!SE.isSCEVable(
I.getType()))
15705 auto *Expr = SE.getSCEV(&
I);
15706 auto II = RewriteMap.find(Expr);
15708 if (
II == RewriteMap.end())
15712 if (
II->second.second == Expr)
15717 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15721void ScalarEvolution::LoopGuards::collectPending() {
15722 const Loop *L = PendingLoop;
15725 PendingLoop =
nullptr;
15730 collectFromBlock(SE, *
this, L->getHeader(), Pred,
VisitedBlocks);
15733void ScalarEvolution::LoopGuards::collectFromPHI(
15741 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15742 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15756 auto &RewriteMap =
G->second.RewriteMap;
15757 if (RewriteMap.empty())
15759 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15760 if (S == RewriteMap.end())
15766 return {C0, SM->getSCEVType()};
15769 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15770 MinMaxPattern
P2) -> MinMaxPattern {
15771 auto [C1,
T1] =
P1;
15772 auto [C2, T2] =
P2;
15773 if (!C1 || !C2 ||
T1 != T2)
15777 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15779 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15781 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15783 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15788 auto P = GetMinMaxConst(0);
15789 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15792 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15795 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15798 Guards.RewriteMap.insert({
LHS,
RHS});
15806 const APInt &DivisorVal,
15808 const APInt *ExprVal;
15821 const APInt &DivisorVal,
15823 const APInt *ExprVal;
15831 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15845 const SCEV *URemRHS =
nullptr;
15849 const SCEV *Multiple =
15851 DivInfo[URemLHS] = Multiple;
15853 Multiples[URemLHS] =
C->getAPInt();
15873 auto IsMinMaxSCEVWithNonNegativeConstant =
15877 if (
MinMax->getNumOperands() != 2)
15880 if (
C->getAPInt().isNegative())
15882 SCTy =
MinMax->getSCEVType();
15891 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15893 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15898 auto *DivisibleExpr =
15906void ScalarEvolution::LoopGuards::collectFromBlock(
15908 const BasicBlock *
Block,
const BasicBlock *Pred,
15916 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15927 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15929 if (From == FromRewritten)
15931 RewriteMap[From] = To;
15937 auto GetMaybeRewritten = [&](
const SCEV *S) {
15938 return RewriteMap.lookup_or(S, S);
15945 const SCEV *MatchLHS,
15946 const SCEV *MatchRHS) {
15947 const SCEVConstant *C1;
15950 if (!
match(MatchLHS,
15962 const SCEV *RewrittenLHS = GetMaybeRewritten(LHSUnknown);
15963 ExactRegion = ExactRegion.intersectWith(SE.
getUnsignedRange(RewrittenLHS),
15968 if (ExactRegion.isEmptySet() || ExactRegion.isWrappedSet() ||
15969 ExactRegion.isFullSet())
15972 const SCEV *RegionMin = SE.
getConstant(ExactRegion.getUnsignedMin());
15973 const SCEV *RegionMax = SE.
getConstant(ExactRegion.getUnsignedMax());
15974 const SCEV *ClampedLHS =
15976 AddRewrite(LHSUnknown, RewrittenLHS, ClampedLHS);
15979 if (MatchRangeCheckIdiom(Predicate,
LHS,
RHS))
15992 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15994 const APInt &DividesBy =
16009 switch (Predicate) {
16038 SmallPtrSet<const SCEV *, 16> Visited;
16040 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
16044 while (!Worklist.
empty()) {
16048 if (!Visited.
insert(From).second)
16050 const SCEV *FromRewritten = GetMaybeRewritten(From);
16051 const SCEV *To =
nullptr;
16053 switch (Predicate) {
16058 EnqueueOperands(
UMax);
16064 EnqueueOperands(
SMax);
16070 EnqueueOperands(
UMin);
16076 EnqueueOperands(
SMin);
16084 const SCEV *OneAlignedUp =
16086 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16098 const SCEVConstant *
C;
16107 Guards.NotEqual.insert({
LHS,
RHS});
16116 AddRewrite(From, FromRewritten, To);
16133 SE.F.
getParent(), Intrinsic::experimental_guard);
16135 for (
const auto *GU : GuardDecl->users())
16137 if (Guard->getFunction() ==
Block->getParent() &&
16147 unsigned NumCollectedConditions = 0;
16148 unsigned NumDomTreeSteps = 0;
16150 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16151 for (;; Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16156 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16157 for (
auto &Phi : Pair.second->phis())
16167 const CondBrInst *LoopEntryPredicate =
16169 if (!LoopEntryPredicate)
16174 NumCollectedConditions++;
16178 if (
Depth > 0 && NumCollectedConditions == 2)
16189 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16190 SmallVector<Value *, 8> Worklist;
16191 SmallPtrSet<Value *, 8> Visited;
16193 while (!Worklist.
empty()) {
16200 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16224 DenseMap<const SCEV *, APInt> Multiples;
16226 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16233 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16234 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16238 for (
const auto &[K, Divisor] : Multiples) {
16239 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16240 Guards.RewriteMap[
K] =
16242 Guards.
rewrite(K), Divisor, SE),
16251 Guards.PreserveNUW =
true;
16252 Guards.PreserveNSW =
true;
16253 for (
const SCEV *Expr : ExprsToRewrite) {
16254 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16255 Guards.PreserveNUW &=
16257 Guards.PreserveNSW &=
16264 if (ExprsToRewrite.size() > 1) {
16265 for (
const SCEV *Expr : ExprsToRewrite) {
16266 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16267 Guards.RewriteMap.erase(Expr);
16268 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16277 class SCEVLoopGuardRewriter
16288 NotEqual(Guards.NotEqual) {
16289 if (Guards.PreserveNUW)
16291 if (Guards.PreserveNSW)
16298 return Map.lookup_or(Expr, Expr);
16302 if (
const SCEV *S = Map.lookup(Expr))
16309 if (
const SCEV *S = Map.lookup(Expr))
16316 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16317 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16318 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16320 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16321 if (
const SCEV *S = Map.lookup(NarrowExt))
16322 return SE.getZeroExtendExpr(S, Ty);
16323 Bitwidth = Bitwidth / 2;
16331 if (
const SCEV *S = Map.lookup(Expr))
16338 if (
const SCEV *S = Map.lookup(Expr))
16344 if (
const SCEV *S = Map.lookup(Expr))
16350 if (
const SCEV *S = Map.lookup(Expr))
16355 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16360 if (NotEqual.contains({LHS, RHS})) {
16362 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16363 return SE.getUMaxExpr(OneAlignedUp, S);
16370 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16381 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16382 return SE.getAddExpr(
16385 if (
const SCEV *S = Map.lookup(
Add))
16386 return SE.getAddExpr(Expr->
getOperand(0), S);
16394 const SCEV *S =
nullptr;
16401 S = Map.lookup(SE.getAddExpr(NewC, Expr->
getOperand(1)));
16404 return SE.getAddExpr(S, SE.getMinusOne(Expr->
getType()));
16439 if (RewriteMap.empty() && NotEqual.empty())
16442 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16443 return Rewriter.visit(Expr);
16457 if (Guards.PendingLoop)
16458 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)
const SmallVectorImpl< MachineOperand > & Cond
static DominatorTree getDomTree(Function &F)
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
SI optimize exec mask operations pre RA
static void visit(BasicBlock &Start, std::function< bool(BasicBlock *)> op)
This file provides utility classes that use RAII to save and restore values.
bool SCEVMinMaxExprContains(const SCEV *Root, const SCEV *OperandToFind, SCEVTypes RootKind)
static cl::opt< unsigned > MaxAddRecSize("scalar-evolution-max-add-rec-size", cl::Hidden, cl::desc("Max coefficients in AddRec during evolving"), cl::init(8))
static cl::opt< unsigned > RangeIterThreshold("scev-range-iter-threshold", cl::Hidden, cl::desc("Threshold for switching to iteratively computing SCEV ranges"), cl::init(32))
static const Loop * isIntegerLoopHeaderPHI(const PHINode *PN, LoopInfo &LI)
static unsigned getConstantTripCount(const SCEVConstant *ExitCount)
static int CompareValueComplexity(const LoopInfo *const LI, Value *LV, Value *RV, unsigned Depth)
Compare the two values LV and RV in terms of their "complexity" where "complexity" is a partial (and ...
static const SCEV * getNextSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static void PushLoopPHIs(const Loop *L, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push PHI nodes in the header of the given loop onto the given Worklist.
static void insertFoldCacheEntry(const ScalarEvolution::FoldID &ID, const SCEV *S, DenseMap< ScalarEvolution::FoldID, const SCEV * > &FoldCache, DenseMap< const SCEV *, SmallVector< ScalarEvolution::FoldID, 2 > > &FoldCacheUser)
static cl::opt< bool > ClassifyExpressions("scalar-evolution-classify-expressions", cl::Hidden, cl::init(true), cl::desc("When printing analysis, include information on every instruction"))
static bool hasHugeExpression(ArrayRef< SCEVUse > Ops)
Returns true if Ops contains a huge SCEV (the subtree of S contains at least HugeExprThreshold nodes)...
static cl::opt< unsigned > AddOpsInlineThreshold("scev-addops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining addition operands into a SCEV"), cl::init(500))
static cl::opt< unsigned > MaxLoopGuardCollectionDepth("scalar-evolution-max-loop-guard-collection-depth", cl::Hidden, cl::desc("Maximum depth for recursive loop guard collection"), cl::init(1))
static cl::opt< bool > VerifyIR("scev-verify-ir", cl::Hidden, cl::desc("Verify IR correctness when making sensitive SCEV queries (slow)"), cl::init(false))
static bool RangeRefPHIAllowedOperands(DominatorTree &DT, PHINode *PHI)
static bool IsKnownPredicateViaAddRecMonotonicity(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Is LHS Pred RHS true because one of them is an AddRec that is known not to go below its own start val...
static std::optional< APInt > MinOptional(std::optional< APInt > X, std::optional< APInt > Y)
Helper function to compare optional APInts: (a) if X and Y both exist, return min(X,...
static PHINode * getConstantEvolvingPHI(Value *V, const Loop *L, const TargetLibraryInfo *TLI)
getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node in the loop that V is deri...
static bool canConstantFold(const Instruction *I, const TargetLibraryInfo *TLI)
Return true if we can constant fold an instruction of the specified type, assuming that all operands ...
static cl::opt< unsigned > MulOpsInlineThreshold("scev-mulops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining multiplication operands into a SCEV"), cl::init(32))
static BinaryOperator * getCommonInstForPHI(PHINode *PN)
static PHINode * getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L, DenseMap< Instruction *, PHINode * > &PHIMap, const TargetLibraryInfo *TLI, unsigned Depth)
getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by recursing through each instructi...
static bool isDivisibilityGuard(const SCEV *LHS, const SCEV *RHS, ScalarEvolution &SE)
static std::optional< const SCEV * > createNodeForSelectViaUMinSeq(ScalarEvolution *SE, const SCEV *CondExpr, const SCEV *TrueExpr, const SCEV *FalseExpr)
static Constant * BuildConstantFromSCEV(const SCEV *V)
This builds up a Constant using the ConstantExpr interface.
static ConstantInt * EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C, ScalarEvolution &SE)
static const SCEV * BinomialCoefficient(const SCEV *It, unsigned K, ScalarEvolution &SE, Type *ResultTy)
Compute BC(It, K). The result has width W. Assume, K > 0.
static cl::opt< unsigned > MaxCastDepth("scalar-evolution-max-cast-depth", cl::Hidden, cl::desc("Maximum depth of recursive SExt/ZExt/Trunc"), cl::init(8))
static bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr, const SCEV *Candidate)
Is MaybeMinMaxExpr an (U|S)(Min|Max) of Candidate and some other values?
static 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 std::optional< BinaryOp > MatchBinaryOp(Value *V, const DataLayout &DL, AssumptionCache &AC, const DominatorTree &DT, const Instruction *CtxI)
Try to map V into a BinaryOp, and return std::nullopt on failure.
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.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
LLVM_ABI APInt uadd_ov(const APInt &RHS, bool &Overflow) const
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
bool isNonPositive() const
Determine if this APInt Value is non-positive (<= 0).
unsigned countTrailingZeros() const
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
unsigned logBase2() const
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
LLVM_ABI APInt multiplicativeInverse() const
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
LLVM_ABI APInt sext(unsigned width) const
Sign extend to a new width.
APInt shl(unsigned shiftAmt) const
Left-shift function.
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
bool isSignBitSet() const
Determine if sign bit of this APInt is set.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
This templated class represents "all analyses that operate over <aparticular IR unit>" (e....
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
AnalysisUsage & addRequiredTransitive()
Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
Get the array size.
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
MutableArrayRef< WeakVH > assumptions()
Access the list of assumption handles currently tracked for this function.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
LLVM_ABI unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
LLVM_ABI Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
BinaryOps getOpcode() const
This class represents a function call, abstracting a target machine's calling convention.
virtual void deleted()
Callback for Value destruction.
This is the base class for all instructions that perform data casts.
This class is the base class for the comparison instructions.
bool isFalseWhenEqual() const
This is just a convenience.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ ICMP_UGE
unsigned greater or equal
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
@ ICMP_SGE
signed greater or equal
@ ICMP_ULE
unsigned less or equal
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
bool isTrueWhenEqual() const
This is just a convenience.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
static LLVM_ABI std::optional< CmpPredicate > getMatching(CmpPredicate A, CmpPredicate B)
Compares two CmpPredicates taking samesign into account and returns the canonicalized CmpPredicate if...
LLVM_ABI CmpInst::Predicate getPreferredSignedPredicate() const
Attempts to return a signed CmpInst::Predicate from the CmpPredicate.
CmpInst::Predicate dropSameSign() const
Drops samesign information.
Conditional Branch instruction.
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
static LLVM_ABI Constant * getNot(Constant *C)
static Constant * getPtrAdd(Constant *Ptr, Constant *Offset, GEPNoWrapFlags NW=GEPNoWrapFlags::none(), std::optional< ConstantRange > InRange=std::nullopt, Type *OnlyIfReduced=nullptr)
Create a getelementptr i8, ptr, offset constant expression.
static LLVM_ABI Constant * getPtrToAddr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static LLVM_ABI Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
static LLVM_ABI Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
This is the shared class of boolean and integer constants.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
static LLVM_ABI ConstantInt * getBool(LLVMContext &Context, bool V)
This class represents a range of values.
LLVM_ABI ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
LLVM_ABI ConstantRange zextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
PreferredRangeType
If represented precisely, the result of some range operations may consist of multiple disjoint ranges...
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI ConstantRange urem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned remainder operation of...
LLVM_ABI bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
LLVM_ABI bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other?
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI ConstantRange zeroExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
LLVM_ABI bool isSignWrappedSet() const
Return true if this set wraps around the signed domain.
LLVM_ABI APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
LLVM_ABI bool isWrappedSet() const
Return true if this set wraps around the unsigned domain.
LLVM_ABI void print(raw_ostream &OS) const
Print out the bounds to a stream.
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)
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