83#include "llvm/Config/llvm-config.h"
138#define DEBUG_TYPE "scalar-evolution"
141 "Number of loop exits with predictable exit counts");
143 "Number of loop exits without predictable exit counts");
145 "Number of loops with trip counts computed by force");
147#ifdef EXPENSIVE_CHECKS
155 cl::desc(
"Maximum number of iterations SCEV will "
156 "symbolically execute a constant "
162 cl::desc(
"Verify ScalarEvolution's backedge taken counts (slow)"));
165 cl::desc(
"Enable stricter verification with -verify-scev is passed"));
169 cl::desc(
"Verify IR correctness when making sensitive SCEV queries (slow)"),
174 cl::desc(
"Threshold for inlining multiplication operands into a SCEV"),
179 cl::desc(
"Threshold for inlining addition operands into a SCEV"),
183 "scalar-evolution-max-scev-compare-depth",
cl::Hidden,
184 cl::desc(
"Maximum depth of recursive SCEV complexity comparisons"),
188 "scalar-evolution-max-scev-operations-implication-depth",
cl::Hidden,
189 cl::desc(
"Maximum depth of recursive SCEV operations implication analysis"),
193 "scalar-evolution-max-value-compare-depth",
cl::Hidden,
194 cl::desc(
"Maximum depth of recursive value complexity comparisons"),
199 cl::desc(
"Maximum depth of recursive arithmetics"),
203 "scalar-evolution-max-constant-evolving-depth",
cl::Hidden,
208 cl::desc(
"Maximum depth of recursive SExt/ZExt/Trunc"),
213 cl::desc(
"Max coefficients in AddRec during evolving"),
218 cl::desc(
"Size of the expression which is considered huge"),
223 cl::desc(
"Threshold for switching to iteratively computing SCEV ranges"),
227 "scalar-evolution-max-loop-guard-collection-depth",
cl::Hidden,
228 cl::desc(
"Maximum depth for recursive loop guard collection"),
cl::init(1));
233 cl::desc(
"When printing analysis, include information on every instruction"));
236 "scalar-evolution-use-expensive-range-sharpening",
cl::Hidden,
238 cl::desc(
"Use more powerful methods of sharpening expression ranges. May "
239 "be costly in terms of compile time"));
243 cl::desc(
"Handle <= and >= in finite loops"),
247 "scalar-evolution-use-context-for-no-wrap-flag-strenghening",
cl::Hidden,
248 cl::desc(
"Infer nuw/nsw flags using context where suitable"),
290#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
308 OS <<
"(ptrtoaddr " << *
Op->getType() <<
" " <<
Op <<
" to "
315 OS <<
"(trunc " << *
Op->getType() <<
" " <<
Op <<
" to "
322 OS <<
"(zext " << *
Op->getType() <<
" " <<
Op <<
" to " << *ZExt->
getType()
329 OS <<
"(sext " << *
Op->getType() <<
" " <<
Op <<
" to " << *SExt->
getType()
358 const char *OpStr =
nullptr;
371 OpStr =
" umin_seq ";
393 OS <<
"(" << UDiv->
getLHS() <<
" /u " << UDiv->
getRHS() <<
")";
400 OS <<
"***COULDNOTCOMPUTE***";
442 if (!
Mul)
return false;
446 if (!SC)
return false;
460 auto &Entry = ConstantSCEVs[V];
469 static_cast<SCEVConstant *
>(UniqueSCEVs.lookup(ID, Token)))
472 new (SCEVAllocator)
SCEVConstant(ID.Intern(SCEVAllocator), V);
473 UniqueSCEVs.insert(S, Token);
488 ConstantInt::get(ITy, V,
isSigned,
true));
496 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
498 SCEV *S =
new (SCEVAllocator)
SCEVVScale(ID.Intern(SCEVAllocator), Ty);
499 UniqueSCEVs.insert(S, Token);
520 "Must be a non-bit-width-changing pointer-to-integer cast!");
532 "Cannot truncate non-integer value!");
539 "Cannot zero extend non-integer value!");
546 "Cannot sign extend non-integer value!");
551 SE->forgetMemoizedResults({
this});
554 SE->UniqueSCEVs.erase(
this);
560void SCEVUnknown::allUsesReplacedWith(
Value *New) {
562 SE->forgetMemoizedResults({
this});
565 SE->UniqueSCEVs.erase(
this);
587 if (LIsPointer != RIsPointer)
588 return (
int)LIsPointer - (int)RIsPointer;
593 return (
int)LID - (int)RID;
598 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
599 return (
int)LArgNo - (int)RArgNo;
605 if (
auto L = LGV->getLinkage() - RGV->getLinkage())
608 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
609 auto LT = GV->getLinkage();
616 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
617 return LGV->getName().compare(RGV->getName());
628 if (LParent != RParent) {
631 if (LDepth != RDepth)
632 return (
int)LDepth - (int)RDepth;
636 unsigned LNumOps = LInst->getNumOperands(),
637 RNumOps = RInst->getNumOperands();
638 if (LNumOps != RNumOps)
639 return (
int)LNumOps - (int)RNumOps;
641 for (
unsigned Idx :
seq(LNumOps)) {
643 RInst->getOperand(Idx),
Depth + 1);
657static std::optional<int>
667 return (
int)LType - (int)RType;
692 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
693 if (LBitWidth != RBitWidth)
694 return (
int)LBitWidth - (int)RBitWidth;
695 return LA.
ult(
RA) ? -1 : 1;
701 return LTy->getBitWidth() - RTy->getBitWidth();
712 if (LLoop != RLoop) {
714 assert(LHead != RHead &&
"Two loops share the same header?");
718 "No dominance between recurrences used by one SCEV?");
741 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
742 if (LNumOps != RNumOps)
743 return (
int)LNumOps - (int)RNumOps;
745 for (
unsigned i = 0; i != LNumOps; ++i) {
771 if (
Ops.size() < 2)
return;
776 return Complexity && *Complexity < 0;
778 if (
Ops.size() == 2) {
782 if (IsLessComplex(
RHS,
LHS))
795 for (
unsigned i = 0, e =
Ops.size(); i != e-2; ++i) {
801 for (
unsigned j = i+1; j != e &&
Ops[j]->getSCEVType() == Complexity; ++j) {
806 if (i == e-2)
return;
828template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
832 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
834 for (
unsigned Idx = 0; Idx <
Ops.size();) {
842 Ops.erase(
Ops.begin() + Idx);
849 assert(Folded &&
"Must have folded value");
853 if (Folded && IsAbsorber(Folded->
getAPInt()))
857 if (Folded && !IsIdentity(Folded->
getAPInt()))
858 Ops.insert(
Ops.begin(), Folded);
860 return Ops.size() == 1 ?
Ops[0] :
nullptr;
935 APInt OddFactorial(W, 1);
937 for (
unsigned i = 3; i <=
K; ++i) {
940 OddFactorial *= (i >> TwoFactors);
944 unsigned CalculationBits = W +
T;
958 for (
unsigned i = 1; i !=
K; ++i) {
991 "use-specific flags only supported for affine AddRecs");
993 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1034 ConversionFn CreatePtrCast;
1038 ConversionFn CreatePtrCast)
1039 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
1042 Type *TargetTy, ConversionFn CreatePtrCast) {
1044 return Rewriter.visit(Scev);
1070 "Should only reach pointer-typed SCEVUnknown's.");
1075 return SE.getZero(TargetTy);
1076 return CreatePtrCast(Expr);
1081 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1085 if (DL.hasUnstableRepresentation(
Op->getType()))
1088 Type *Ty = DL.getAddressType(
Op->getType());
1099 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1101 SCEV *S =
new (SCEVAllocator)
1103 UniqueSCEVs.insert(S, Token);
1106 return static_cast<const SCEV *
>(S);
1109 "We must have succeeded in sinking the cast, "
1110 "and ending up with an integer-typed expression!");
1117 "This is not a truncating conversion!");
1119 "This is not a conversion to a SCEVable type!");
1120 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1125 ID.AddPointer(
Op.getOpaqueValue());
1128 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1151 UniqueSCEVs.insert(S, Token);
1164 unsigned numTruncs = 0;
1165 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1173 if (numTruncs < 2) {
1183 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1190 for (
const SCEV *
Op : AddRec->operands())
1205 UniqueSCEVs.insert(S, Token);
1246struct ExtendOpTraitsBase {
1247 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
SCEVUse,
Type *,
1252template <
typename ExtendOp>
struct ExtendOpTraits {
1268 static const GetExtendExprTy GetExtendExpr;
1270 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1271 ICmpInst::Predicate *Pred,
1272 ScalarEvolution *SE) {
1277const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1284 static const GetExtendExprTy GetExtendExpr;
1286 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1287 ICmpInst::Predicate *Pred,
1288 ScalarEvolution *SE) {
1293const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1305template <
typename ExtendOpTy>
1308 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1309 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1325 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1338 auto PreStartFlags =
1356 const SCEV *OperandExtendedStart =
1358 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1359 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1371 const SCEV *OverflowLimit =
1372 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1374 if (OverflowLimit &&
1382template <
typename ExtendOpTy>
1386 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1394 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1429template <
typename ExtendOpTy>
1430bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1433 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1443 APInt StartAI = StartC->
getAPInt();
1445 for (
unsigned Delta : {-2, -1, 1, 2}) {
1446 const SCEV *PreStart =
getConstant(StartAI - Delta);
1447 const auto *PreAR =
static_cast<SCEVAddRecExpr *
>(
1448 findExistingSCEVInCache(
scAddRecExpr, {PreStart, Step},
L));
1452 if (PreAR &&
any(PreAR->getNoWrapFlags(WrapType))) {
1455 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1456 DeltaS, &Pred,
this);
1474 const unsigned BitWidth =
C.getBitWidth();
1492 const APInt &ConstantStart,
1507 auto I = FoldCache.
insert({ID, S});
1511 auto &UserIDs = FoldCacheUser[
I.first->second];
1512 assert(
count(UserIDs, ID) == 1 &&
"unexpected duplicates in UserIDs");
1513 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1514 if (UserIDs[
I] == ID) {
1519 I.first->second = S;
1521 FoldCacheUser[S].push_back(ID);
1527 "This is not an extending conversion!");
1529 "This is not a conversion to a SCEVable type!");
1530 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1534 if (
const SCEV *S = FoldCache.lookup(ID))
1546 "This is not an extending conversion!");
1548 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1560 const SCEV *Start, *Step;
1565 if (AR->hasNoUnsignedWrap()) {
1576 ID.AddPointer(
Op.getOpaqueValue());
1579 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1584 UniqueSCEVs.insert(S, Token);
1594 const SCEV *
X = ST->getOperand();
1627 const SCEV *CastedMaxBECount =
1631 if (MaxBECount == RecastedMaxBECount) {
1640 const SCEV *WideMaxBECount =
1642 const SCEV *OperandExtendedAdd =
1648 if (ZAdd == OperandExtendedAdd) {
1659 OperandExtendedAdd =
1665 if (ZAdd == OperandExtendedAdd) {
1686 !AC.assumptions().empty()) {
1688 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1690 if (AR->hasNoUnsignedWrap()) {
1725 const APInt &
C = SC->getAPInt();
1729 const SCEV *SResidual =
1737 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1761 if (SA->hasNoUnsignedWrap()) {
1774 if (SA->hasNoSignedWrap() &&
1777 C->isNegative() && !
C->isMinSignedValue() && C2->
sge(
C->abs())) {
1796 const SCEV *SResidual =
1807 if (SM->hasNoUnsignedWrap()) {
1829 const SCEV *TruncRHS;
1866 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1870 UniqueSCEVs.insert(S, Token);
1879 "This is not an extending conversion!");
1881 "This is not a conversion to a SCEVable type!");
1882 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1886 if (
const SCEV *S = FoldCache.lookup(ID))
1898 "This is not an extending conversion!");
1900 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1917 const SCEV *Start, *Step;
1922 if (AR->hasNoSignedWrap()) {
1933 ID.AddPointer(
Op.getOpaqueValue());
1936 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1942 UniqueSCEVs.insert(S, Token);
1952 const SCEV *
X = ST->getOperand();
1963 if (SA->hasNoSignedWrap()) {
1985 const SCEV *SResidual =
2018 const SCEV *CastedMaxBECount =
2022 if (MaxBECount == RecastedMaxBECount) {
2031 const SCEV *WideMaxBECount =
2033 const SCEV *OperandExtendedAdd =
2039 if (SAdd == OperandExtendedAdd) {
2050 OperandExtendedAdd =
2056 if (SAdd == OperandExtendedAdd) {
2076 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2078 if (AR->hasNoSignedWrap()) {
2092 const APInt &
C = SC->getAPInt();
2096 const SCEV *SResidual =
2104 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2131 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
2135 UniqueSCEVs.insert(S, Token);
2151 assert(Expr->
getType() == Ty &&
"requested type must match");
2163 "This is not an extending conversion!");
2165 "This is not a conversion to a SCEVable type!");
2170 if (SC->getAPInt().isNegative())
2175 const SCEV *NewOp =
T->getOperand();
2194 for (
const SCEV *
Op : AR->operands())
2232 APInt &AccumulatedConstant,
2236 bool Interesting =
false;
2243 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2245 AccumulatedConstant += Scale *
C->getAPInt();
2250 for (; i !=
Ops.size(); ++i) {
2259 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2265 auto Pair = M.insert({
Key, NewScale});
2269 Pair.first->second += NewScale;
2277 auto Pair = M.insert({
Ops[i], Scale});
2281 Pair.first->second += Scale;
2299 case Instruction::Add:
2301 case Instruction::Sub:
2303 case Instruction::Mul:
2317 const SCEV *
A = (this->*Extension)(
Operation(LHS, RHS), WideTy, 0);
2318 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2319 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2327 if (BinOp == Instruction::Mul)
2333 APInt C = RHSC->getAPInt();
2334 unsigned NumBits =
C.getBitWidth();
2335 bool IsSub = (BinOp == Instruction::Sub);
2336 bool IsNegativeConst = (
Signed &&
C.isNegative());
2338 bool OverflowDown = IsSub ^ IsNegativeConst;
2340 if (IsNegativeConst) {
2353 APInt Limit = Min + Magnitude;
2359 APInt Limit = Max - Magnitude;
2368 return std::nullopt;
2377 bool Deduced =
false;
2383 bool CanUseNSW =
true;
2384 const APInt *ShiftAmt;
2389 return std::nullopt;
2393 Opcode = Instruction::Mul;
2395 }
else if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
2396 Opcode != Instruction::Mul) {
2397 return std::nullopt;
2416 return std::nullopt;
2424 using namespace std::placeholders;
2431 assert(CanAnalyze &&
"don't call from other places!");
2438 auto IsKnownNonNegative = [&](
SCEVUse U) {
2447 if (SignOrUnsignWrap != SignOrUnsignMask &&
2454 return Instruction::Add;
2456 return Instruction::Mul;
2485 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2492 if (UDiv->getOperand(1) ==
Ops[1])
2495 if (UDiv->getOperand(1) ==
Ops[0])
2512 "only nuw or nsw allowed");
2514 "only nuw or nsw allowed");
2515 assert(!
Ops.empty() &&
"Cannot get empty add!");
2516 if (
Ops.size() == 1)
return Ops[0];
2519 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2521 "SCEVAddExpr operand types don't match!");
2523 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2524 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2529 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2530 [](
const APInt &
C) {
return C.isZero(); },
2531 [](
const APInt &
C) {
return false; });
2550 return {getOrCreateAddExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
2555 if (
Add->getNoWrapFlags(ExprFlags) != ExprFlags)
2556 Add->setNoWrapFlags(ComputeFlags(
Ops));
2557 return {S, UseFlags};
2564 bool FoundMatch =
false;
2565 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2566 if (
Ops[i] ==
Ops[i+1]) {
2578 --i; e -=
Count - 1;
2588 auto FindTruncSrcType = [&]() ->
Type * {
2594 return T->getOperand()->getType();
2596 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2598 return T->getOperand()->getType();
2602 if (
auto *SrcType = FindTruncSrcType()) {
2609 if (
T->getOperand()->getType() != SrcType) {
2618 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2621 if (
T->getOperand()->getType() != SrcType) {
2650 if (
Ops.size() == 2) {
2660 auto C2 =
C->getAPInt();
2663 APInt ConstAdd = C1 + C2;
2664 auto AddFlags = AddExpr->getNoWrapFlags();
2705 if (
Ops.size() == 2 &&
2716 if (Idx <
Ops.size()) {
2717 bool DeletedAdd =
false;
2728 Ops.erase(
Ops.begin()+Idx);
2731 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2754 struct APIntCompare {
2755 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2756 return LHS.ult(RHS);
2763 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2765 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2768 if (AccumulatedConstant != 0)
2770 for (
auto &MulOp : MulOpLists) {
2771 if (MulOp.first == 1) {
2773 }
else if (MulOp.first != 0) {
2782 if (
Ops.size() == 1)
2791 if (M->getNumOperands() == 2)
2792 return M->getOperand(OpIdx == 0);
2794 append_range(Remaining, M->operands().drop_front(OpIdx + 1));
2803 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2807 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2815 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp) {
2816 if (MulOpSCEV ==
Ops[AddOp]) {
2827 for (
unsigned OMulOp = 0, OE = OtherMul->
getNumOperands(); OMulOp != OE;
2829 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2831 Cofactors.
push_back(StripFactor(OtherMul, OMulOp));
2840 if (!Cofactors.
empty()) {
2848 if (
Ops.size() == DeadIndices.
size() + 1)
2855 Ops.erase(
Ops.begin() + Idx);
2859 Ops.push_back(OuterMul);
2878 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2881 Ops.erase(
Ops.begin()+i);
2886 if (!LIOps.
empty()) {
2911 auto *DefI = getDefiningScopeBound(LIOps);
2913 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2925 if (
Ops.size() == 1)
return NewRec;
2928 for (
unsigned i = 0;; ++i)
2929 if (
Ops[i] == AddRec) {
2939 for (
unsigned OtherIdx = Idx+1;
2947 "AddRecExprs are not sorted in reverse dominance order?");
2954 if (OtherAddRec->getLoop() == AddRecLoop) {
2955 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2957 if (i >= AddRecOps.
size()) {
2958 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2962 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
2965 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
2981 "Tried to add SCEVUse flags after operands changed");
2982 return {getOrCreateAddExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
2990 ID.AddPointer(
Op.getOpaqueValue());
2996 S =
new (SCEVAllocator)
2998 UniqueSCEVs.insert(S, Token);
3009 FoldingSetNodeID
ID;
3012 ID.AddPointer(
Op.getOpaqueValue());
3014 FoldingSetInsertToken Token;
3016 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.lookup(ID, Token));
3020 S =
new (SCEVAllocator)
3021 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3022 UniqueSCEVs.insert(S, Token);
3024 LoopUsers[
L].push_back(S);
3033 FoldingSetNodeID
ID;
3036 ID.AddPointer(
Op.getOpaqueValue());
3037 FoldingSetInsertToken Token;
3038 SCEVMulExpr *S =
static_cast<SCEVMulExpr *
>(UniqueSCEVs.lookup(ID, Token));
3042 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3044 UniqueSCEVs.insert(S, Token);
3053 FoldingSetNodeID
ID;
3055 ID.AddPointer(
LHS.getOpaqueValue());
3056 ID.AddPointer(
RHS.getOpaqueValue());
3057 FoldingSetInsertToken Token;
3058 SCEV *S = UniqueSCEVs.lookup(ID, Token);
3060 S =
new (SCEVAllocator) SCEVUDivExpr(
ID.Intern(SCEVAllocator),
LHS,
RHS);
3061 UniqueSCEVs.insert(S, Token);
3070 if (j > 1 && k / j != i) Overflow =
true;
3086 if (n == 0 || n == k)
return 1;
3087 if (k > n)
return 0;
3093 for (
uint64_t i = 1; i <= k; ++i) {
3094 r =
umul_ov(r, n-(i-1), Overflow);
3103 struct FindConstantInAddMulChain {
3104 bool FoundConstant =
false;
3106 bool follow(
const SCEV *S) {
3111 bool isDone()
const {
3112 return FoundConstant;
3116 FindConstantInAddMulChain
F;
3118 ST.visitAll(StartExpr);
3119 return F.FoundConstant;
3128 "only nuw or nsw allowed");
3130 "only nuw or nsw allowed");
3131 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3132 if (
Ops.size() == 1)
return Ops[0];
3134 Type *ETy =
Ops[0]->getType();
3136 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3138 "SCEVMulExpr operand types don't match!");
3143 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3144 [](
const APInt &
C) {
return C.isOne(); },
3145 [](
const APInt &
C) {
return C.isZero(); });
3162 return {getOrCreateMulExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
3167 if (
Mul->getNoWrapFlags(ExprFlags) != ExprFlags)
3168 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3169 return {S, UseFlags};
3173 if (
Ops.size() == 2) {
3181 const SCEV *Op0, *Op1;
3189 if (
Ops[0]->isAllOnesValue()) {
3194 bool AnyFolded =
false;
3195 for (
const SCEV *AddOp :
Add->operands()) {
3215 if (AddRec->hasNoSignedWrap()) {
3246 APInt C1V = LHSC->getAPInt();
3256 const SCEV *NewMul =
nullptr;
3260 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3275 if (Idx <
Ops.size()) {
3276 bool DeletedMul =
false;
3282 Ops.erase(
Ops.begin()+Idx);
3306 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3309 Ops.erase(
Ops.begin()+i);
3314 if (!LIOps.
empty()) {
3326 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3342 if (
Ops.size() == 1)
return NewRec;
3345 for (
unsigned i = 0;; ++i)
3346 if (
Ops[i] == AddRec) {
3367 bool OpsModified =
false;
3368 for (
unsigned OtherIdx = Idx+1;
3382 bool Overflow =
false;
3389 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3390 uint64_t Coeff1 =
Choose(x, 2*x - y, Overflow);
3393 z < ze && !Overflow; ++z) {
3394 uint64_t Coeff2 =
Choose(2*x - y, x-z, Overflow);
3396 if (LargerThan64Bits)
3397 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3399 Coeff = Coeff1*Coeff2;
3412 const SCEV *NewAddRec =
3414 if (
Ops.size() == 2)
return NewAddRec;
3415 Ops[Idx] = NewAddRec;
3416 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3433 "Tried to add SCEVUse flags after operands changed");
3434 return {getOrCreateMulExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
3441 "SCEVURemExpr operand types don't match!");
3446 if (RHSC->getValue()->isOne())
3447 return getZero(LHS->getType());
3450 if (RHSC->getAPInt().isPowerOf2()) {
3451 Type *FullTy = LHS->getType();
3467 assert(!LHS->getType()->isPointerTy() &&
3468 "SCEVUDivExpr operand can't be pointer!");
3469 assert(LHS->getType() == RHS->getType() &&
3470 "SCEVUDivExpr operand types don't match!");
3480 if (RHSC->getValue()->isOne())
3485 if (!RHSC->getValue()->isZero()) {
3489 Type *Ty = LHS->getType();
3490 unsigned LZ = RHSC->getAPInt().countl_zero();
3494 if (!RHSC->getAPInt().isPowerOf2())
3502 const APInt &StepInt = Step->getAPInt();
3503 const APInt &DivInt = RHSC->getAPInt();
3504 if (!StepInt.
urem(DivInt) &&
3510 for (
const SCEV *
Op : AR->operands())
3516 const APInt *StartRem;
3529 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3533 const SCEV *NewStart =
3535 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3537 const SCEV *NewLHS =
3547 if (M->hasNoUnsignedWrap()) {
3549 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3550 const SCEV *
Op = M->getOperand(i);
3577 if (
auto *DivisorConstant =
3579 bool Overflow =
false;
3581 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3592 if (
A->hasNoUnsignedWrap()) {
3594 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3601 if (
Operands.size() ==
A->getNumOperands())
3613 const APInt &
N = RHSC->getAPInt();
3614 const APInt *NMinusM, *M;
3618 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3619 *NMinusM ==
N - *M) {
3628 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3638 return getZero(LHS->getType());
3642 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3643 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3644 if (
Mul->getOperand(i) == RHS) {
3655 const SCEV *NewLHS, *NewRHS;
3660 return getOrCreateUDivExpr(LHS, RHS);
3679 if (StepChrec->getLoop() == L) {
3698 "only nuw or nsw allowed");
3704 "SCEVAddRecExpr operand types don't match!");
3705 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3709 "SCEVAddRecExpr operand is not available at loop entry!");
3731 const Loop *NestedLoop = NestedAR->getLoop();
3732 if (L->contains(NestedLoop)
3735 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3737 Operands[0] = NestedAR->getStart();
3741 bool AllInvariant =
all_of(
3753 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3764 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3775 "Tried to add SCEVUse flags after operands changed");
3776 return {getOrCreateAddRecExpr(
Operands, L, ExprFlags), UseFlags};
3792 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3796 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3810 bool FirstIter =
true;
3812 for (
SCEVUse IndexExpr : IndexExprs) {
3819 Offsets.push_back(FieldOffset);
3822 CurTy = STy->getTypeAtIndex(Index);
3827 "The first index of a GEP indexes a pointer");
3828 CurTy = SrcElementTy;
3839 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3840 Offsets.push_back(LocalOffset);
3845 if (Offsets.empty())
3858 "GEP should not change type mid-flight.");
3862SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3866 "L must be passed to find existing AddRecs");
3870 ID.AddPointer(
Op.getOpaqueValue());
3874 return UniqueSCEVs.lookup(ID, Token);
3884 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3885 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3886 if (
Ops.size() == 1)
return Ops[0];
3889 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3891 "Operand types don't match!");
3894 "min/max should be consistently pointerish");
3920 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3922 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3927 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3929 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3935 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3941 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3946 if (Idx <
Ops.size()) {
3947 bool DeletedAny =
false;
3948 while (
Ops[Idx]->getSCEVType() == Kind) {
3950 Ops.erase(
Ops.begin()+Idx);
3968 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3969 if (
Ops[i] ==
Ops[i + 1] ||
3970 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3973 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3976 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3979 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3985 if (
Ops.size() == 1)
return Ops[0];
3987 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
3994 ID.AddPointer(
Op.getOpaqueValue());
3996 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
3998 return ExistingSCEV;
4001 SCEV *S =
new (SCEVAllocator)
4004 UniqueSCEVs.insert(S, Token);
4012class SCEVSequentialMinMaxDeduplicatingVisitor final
4013 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4014 std::optional<const SCEV *>> {
4015 using RetVal = std::optional<const SCEV *>;
4022 bool canRecurseInto(
SCEVTypes Kind)
const {
4025 return RootKind == Kind || NonSequentialRootKind == Kind;
4030 if (!SeenOps.
insert(S).second)
4031 return std::nullopt;
4035 if (!canRecurseInto(Kind))
4045 return std::nullopt;
4055 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4057 : SE(SE), RootKind(RootKind),
4058 NonSequentialRootKind(
4059 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4063 SmallVectorImpl<SCEVUse> &NewOps) {
4068 for (
const SCEV *
Op : OrigOps) {
4073 Ops.emplace_back(*NewOp);
4077 NewOps = std::move(
Ops);
4121struct SCEVPoisonCollector {
4122 bool LookThroughMaybePoisonBlocking;
4123 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4124 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4125 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4127 bool follow(
const SCEV *S) {
4128 if (!LookThroughMaybePoisonBlocking &&
4138 bool isDone()
const {
return false; }
4148 SCEVPoisonCollector PC1(
true);
4153 if (PC1.MaybePoison.
empty())
4159 SCEVPoisonCollector PC2(
false);
4169 SCEVPoisonCollector PC(
false);
4192 while (!Worklist.
empty()) {
4194 if (!Visited.
insert(V).second)
4198 if (Visited.
size() > 16)
4214 if (PDI->isDisjoint())
4221 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4228 if (
I->hasPoisonGeneratingAnnotations())
4239 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4240 "Not a SCEVSequentialMinMaxExpr!");
4241 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4242 if (
Ops.size() == 1)
4246 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4248 "Operand types don't match!");
4251 "min/max should be consistently pointerish");
4259 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4266 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4276 bool DeletedAny =
false;
4277 while (Idx <
Ops.size()) {
4278 if (
Ops[Idx]->getSCEVType() != Kind) {
4283 Ops.erase(
Ops.begin() + Idx);
4284 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4285 SMME->operands().end());
4293 const SCEV *SaturationPoint;
4304 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4305 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4317 Ops.erase(
Ops.begin() + i);
4322 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4323 Ops.erase(
Ops.begin() + i);
4333 ID.AddPointer(
Op.getOpaqueValue());
4335 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
4337 return ExistingSCEV;
4341 SCEV *S =
new (SCEVAllocator)
4344 UniqueSCEVs.insert(S, Token);
4392 if (
Size.isScalable())
4413 "Cannot get offset for structure containing scalable vector types");
4427 if (
SCEV *S = UniqueSCEVs.lookup(ID, Token)) {
4429 "Stale SCEVUnknown in uniquing map!");
4432 SCEV *S =
new (SCEVAllocator)
SCEVUnknown(ID.Intern(SCEVAllocator), V,
this,
4435 UniqueSCEVs.insert(S, Token);
4450 return Ty->isIntOrPtrTy();
4457 if (Ty->isPointerTy())
4468 if (Ty->isIntegerTy())
4472 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4484 bool PreciseA, PreciseB;
4485 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4486 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4487 if (!PreciseA || !PreciseB)
4490 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4491 DT.dominates(ScopeB, ScopeA);
4495 return CouldNotCompute.get();
4498bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4501 return SU && SU->getValue() ==
nullptr;
4504 return !ContainsNulls;
4509 if (
I != HasRecMap.end())
4514 HasRecMap.insert({S, FoundAddRec});
4522 if (
SI == ExprValueMap.
end())
4524 return SI->second.getArrayRef();
4530void ScalarEvolution::eraseValueFromMap(
Value *V) {
4532 if (
I != ValueExprMap.end()) {
4533 auto EVIt = ExprValueMap.find(
I->second);
4534 bool Removed = EVIt->second.remove(V);
4536 assert(Removed &&
"Value not in ExprValueMap?");
4537 ValueExprMap.erase(
I);
4541void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4545 auto It = ValueExprMap.find_as(V);
4546 if (It == ValueExprMap.end()) {
4548 ExprValueMap[S].insert(V);
4559 return createSCEVIter(V);
4566 if (
I != ValueExprMap.end()) {
4567 const SCEV *S =
I->second;
4568 assert(checkValidity(S) &&
4569 "existing SCEV has not been properly invalidated");
4581 Type *Ty = V->getType();
4597 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4610 return (
const SCEV *)
nullptr;
4616 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4620 Type *Ty = V->getType();
4626 assert(
P->getType()->isPointerTy());
4641 if (AddOp->getType()->isPointerTy()) {
4642 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4659 return getZero(LHS->getType());
4664 if (RHS->getType()->isPointerTy()) {
4665 if (!LHS->getType()->isPointerTy() ||
4675 const bool RHSIsNotMinSigned =
4706 Type *SrcTy = V->getType();
4707 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4708 "Cannot truncate or zero extend with non-integer arguments!");
4718 Type *SrcTy = V->getType();
4719 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4720 "Cannot truncate or zero extend with non-integer arguments!");
4729 Type *SrcTy = V->getType();
4730 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4731 "Cannot noop or zero extend with non-integer arguments!");
4733 "getNoopOrZeroExtend cannot truncate!");
4740 Type *SrcTy = V->getType();
4741 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4742 "Cannot noop or sign extend with non-integer arguments!");
4744 "getNoopOrSignExtend cannot truncate!");
4751 Type *SrcTy = V->getType();
4752 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4753 "Cannot noop or any extend with non-integer arguments!");
4755 "getNoopOrAnyExtend cannot truncate!");
4762 Type *SrcTy = V->getType();
4763 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4764 "Cannot truncate or noop with non-integer arguments!");
4766 "getTruncateOrNoop cannot extend!");
4774 const SCEV *PromotedLHS = LHS;
4775 const SCEV *PromotedRHS = RHS;
4795 assert(!
Ops.empty() &&
"At least one operand must be!");
4797 if (
Ops.size() == 1)
4801 Type *MaxType =
nullptr;
4807 assert(MaxType &&
"Failed to find maximum type!");
4820 if (!V->getType()->isPointerTy())
4825 V = AddRec->getStart();
4827 const SCEV *PtrOp =
nullptr;
4828 for (
const SCEV *AddOp :
Add->operands()) {
4829 if (AddOp->getType()->isPointerTy()) {
4830 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4834 assert(PtrOp &&
"Must have pointer op");
4846 for (
User *U :
I->users()) {
4848 if (Visited.
insert(UserInsn).second)
4862 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4863 bool IgnoreOtherLoops =
true) {
4866 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4868 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4873 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4875 SeenLoopVariantSCEVUnknown =
true;
4879 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4883 SeenOtherLoops =
true;
4887 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4889 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4892 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4893 : SCEVRewriteVisitor(SE),
L(
L) {}
4896 bool SeenLoopVariantSCEVUnknown =
false;
4897 bool SeenOtherLoops =
false;
4906 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4907 SCEVPostIncRewriter
Rewriter(L, SE);
4909 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4914 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4916 SeenLoopVariantSCEVUnknown =
true;
4920 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4924 SeenOtherLoops =
true;
4928 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4930 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4933 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4934 : SCEVRewriteVisitor(SE),
L(
L) {}
4937 bool SeenLoopVariantSCEVUnknown =
false;
4938 bool SeenOtherLoops =
false;
4944class SCEVBackedgeConditionFolder
4947 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4948 ScalarEvolution &SE) {
4949 bool IsPosBECond =
false;
4950 Value *BECond =
nullptr;
4951 if (BasicBlock *Latch =
L->getLoopLatch()) {
4953 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
4954 "Both outgoing branches should not target same header!");
4955 BECond = BI->getCondition();
4956 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
4961 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
4965 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4966 const SCEV *
Result = Expr;
4971 switch (
I->getOpcode()) {
4972 case Instruction::Select: {
4974 std::optional<const SCEV *> Res =
4975 compareWithBackedgeCondition(
SI->getCondition());
4983 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
4994 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
4995 bool IsPosBECond, ScalarEvolution &SE)
4996 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
4997 IsPositiveBECond(IsPosBECond) {}
4999 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5003 Value *BackedgeCond =
nullptr;
5005 bool IsPositiveBECond;
5008std::optional<const SCEV *>
5009SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5014 if (BackedgeCond == IC)
5017 return std::nullopt;
5022 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5023 ScalarEvolution &SE) {
5029 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5036 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5046 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5047 : SCEVRewriteVisitor(SE),
L(
L) {}
5055void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5071 const APInt &BECountAP = BECountMax->getAPInt();
5072 unsigned NoOverflowBitWidth =
5081ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5091 if (!SignedWrapViaInductionTried.insert(AR).second)
5116 AC.assumptions().empty())
5124 const SCEV *OverflowLimit =
5126 if (OverflowLimit &&
5134ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5144 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5169 AC.assumptions().empty())
5178 const SCEV *OverflowLimit =
5207 IsNSW = OBO->hasNoSignedWrap();
5208 IsNUW = OBO->hasNoUnsignedWrap();
5214 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5226 return std::nullopt;
5232 switch (
Op->getOpcode()) {
5233 case Instruction::Add:
5234 case Instruction::Sub:
5235 case Instruction::Mul:
5236 case Instruction::UDiv:
5237 case Instruction::URem:
5238 case Instruction::And:
5239 case Instruction::AShr:
5240 case Instruction::Shl:
5243 case Instruction::Or: {
5246 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5256 case Instruction::Xor:
5260 if (RHSC->getValue().isSignMask())
5261 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5263 if (V->getType()->isIntegerTy(1))
5264 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5267 case Instruction::LShr:
5276 if (SA->getValue().ult(
BitWidth)) {
5278 ConstantInt::get(SA->getContext(),
5280 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5285 case Instruction::ExtractValue: {
5287 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5295 bool Signed = WO->isSigned();
5298 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5303 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5314 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5315 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5317 return std::nullopt;
5343 if (
Op == SymbolicPHI)
5348 if (SourceBits != NewBits)
5366 if (!L || L->getHeader() != PN->
getParent())
5424std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5425ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5433 assert(L &&
"Expecting an integer loop header phi");
5438 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5439 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5440 Value *
V = PN->getIncomingValue(i);
5441 if (
L->contains(PN->getIncomingBlock(i))) {
5444 }
else if (BEValueV != V) {
5448 }
else if (!StartValueV) {
5450 }
else if (StartValueV != V) {
5451 StartValueV =
nullptr;
5455 if (!BEValueV || !StartValueV)
5456 return std::nullopt;
5458 const SCEV *BEValue =
getSCEV(BEValueV);
5465 return std::nullopt;
5469 unsigned FoundIndex =
Add->getNumOperands();
5470 Type *TruncTy =
nullptr;
5472 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5475 if (FoundIndex == e) {
5480 if (FoundIndex ==
Add->getNumOperands())
5481 return std::nullopt;
5485 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5486 if (i != FoundIndex)
5487 Ops.push_back(
Add->getOperand(i));
5493 return std::nullopt;
5546 const SCEV *StartVal =
getSCEV(StartValueV);
5547 const SCEV *PHISCEV =
5574 auto getExtendedExpr = [&](
const SCEV *Expr,
5575 bool CreateSignExtend) ->
const SCEV * {
5578 const SCEV *ExtendedExpr =
5581 return ExtendedExpr;
5589 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5590 const SCEV *ExtendedExpr) ->
bool {
5591 return Expr != ExtendedExpr &&
5595 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5596 if (PredIsKnownFalse(StartVal, StartExtended)) {
5598 return std::nullopt;
5603 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5604 if (PredIsKnownFalse(Accum, AccumExtended)) {
5606 return std::nullopt;
5609 auto AppendPredicate = [&](
const SCEV *Expr,
5610 const SCEV *ExtendedExpr) ->
void {
5611 if (Expr != ExtendedExpr &&
5619 AppendPredicate(StartVal, StartExtended);
5620 AppendPredicate(Accum, AccumExtended);
5628 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5629 std::make_pair(NewAR, Predicates);
5631 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5635std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5640 return std::nullopt;
5643 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5644 if (
I != PredicatedSCEVRewrites.end()) {
5645 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5648 if (Rewrite.first == SymbolicPHI)
5649 return std::nullopt;
5653 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5657 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5658 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5663 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5664 return std::nullopt;
5684 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5685 if (Expr1 != Expr2 &&
5686 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5687 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5722const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5724 Value *StartValueV) {
5727 assert(BEValueV && StartValueV);
5729 const SCEV *Accum =
nullptr;
5732 if (BO->Opcode != Instruction::Add)
5735 if (BO->LHS == PN &&
L->isLoopInvariant(BO->RHS))
5737 else if (BO->RHS == PN &&
L->isLoopInvariant(BO->LHS))
5751 if (!
GEP ||
GEP->getPointerOperand() != PN ||
GEP->getNumIndices() != 1)
5754 if (!
L->isLoopInvariant(Idx))
5763 const SCEV *StartVal =
getSCEV(StartValueV);
5764 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5765 insertValueToMap(PN, PHISCEV);
5768 inferNoWrapViaConstantRanges(AR);
5775 "Accum is defined outside L, but is not invariant?");
5776 if (isAddRecNeverPoison(BEInst, L))
5783const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5791 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5797 }
else if (BEValueV != V) {
5801 }
else if (!StartValueV) {
5803 }
else if (StartValueV != V) {
5804 StartValueV =
nullptr;
5808 if (!BEValueV || !StartValueV)
5811 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5812 "PHI node already processed?");
5816 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5821 insertValueToMap(PN, SymbolicName);
5825 const SCEV *BEValue =
getSCEV(BEValueV);
5835 unsigned FoundIndex =
Add->getNumOperands();
5836 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5837 if (
Add->getOperand(i) == SymbolicName)
5838 if (FoundIndex == e) {
5843 if (FoundIndex !=
Add->getNumOperands()) {
5846 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5847 if (i != FoundIndex)
5848 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5860 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5867 if (
GEP->getOperand(0) == PN)
5875 const SCEV *StartVal =
getSCEV(StartValueV);
5876 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5881 forgetMemoizedResults({SymbolicName});
5882 insertValueToMap(PN, PHISCEV);
5885 inferNoWrapViaConstantRanges(AR);
5909 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5910 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5912 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5913 const SCEV *StartVal =
getSCEV(StartValueV);
5914 if (Start == StartVal) {
5918 forgetMemoizedResults({SymbolicName});
5919 insertValueToMap(PN, Shifted);
5929 eraseValueFromMap(PN);
5944 Use &LeftUse =
Merge->getOperandUse(0);
5945 Use &RightUse =
Merge->getOperandUse(1);
5981 assert(IDom &&
"At least the entry block should dominate PN");
5989const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
5994 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6011 CommonInst = IncomingInst;
6027ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6033 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6034 bool SCEVExprsIdentical =
6036 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6037 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6040const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6041 if (
const SCEV *S = createAddRecFromPHI(PN))
6051 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6054 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6063 struct FindClosure {
6064 const SCEV *OperandToFind;
6070 bool canRecurseInto(
SCEVTypes Kind)
const {
6073 return RootKind == Kind || NonSequentialRootKind == Kind ||
6078 : OperandToFind(OperandToFind), RootKind(RootKind),
6079 NonSequentialRootKind(
6083 bool follow(
const SCEV *S) {
6084 Found = S == OperandToFind;
6086 return !isDone() && canRecurseInto(S->
getSCEVType());
6089 bool isDone()
const {
return Found; }
6092 FindClosure FC(OperandToFind, RootKind);
6097std::optional<const SCEV *>
6098ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6108 switch (ICI->getPredicate()) {
6122 bool Signed = ICI->isSigned();
6123 const SCEV *LA =
getSCEV(TrueVal);
6131 if (LA == LS &&
RA == RS)
6133 if (LA == RS &&
RA == LS)
6136 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6137 if (
Op->getType()->isPointerTy()) {
6148 LS = CoerceOperand(LS);
6149 RS = CoerceOperand(RS);
6173 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6174 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6188 X = ZExt->getOperand();
6190 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6201 return std::nullopt;
6204static std::optional<const SCEV *>
6206 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6210 "Unexpected operands of a select.");
6222 return std::nullopt;
6237static std::optional<const SCEV *>
6241 return std::nullopt;
6244 const auto *SETrue = SE->
getSCEV(TrueVal);
6245 const auto *SEFalse = SE->
getSCEV(FalseVal);
6249const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6251 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6253 V->getType() ==
TrueVal->getType() &&
6254 "Types of select hands and of the result must match.");
6257 if (!
V->getType()->isIntegerTy(1))
6260 if (std::optional<const SCEV *> S =
6273 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6277 if (std::optional<const SCEV *> S =
6278 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6284 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6290 assert(
GEP->getSourceElementType()->isSized() &&
6291 "GEP source element type must be sized");
6294 for (
Value *Index :
GEP->indices())
6299APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6302 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6305 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6307 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6310 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6328 return GetShiftedByZeros(TZ);
6338 return GetShiftedByZeros(TZ);
6342 if (
M->hasNoUnsignedWrap()) {
6345 for (
const SCEV *Operand :
M->operands().drop_front())
6353 for (
const SCEV *Operand :
M->operands())
6355 return GetShiftedByZeros(TZ);
6360 if (
N->hasNoUnsignedWrap())
6361 return GetGCDMultiple(
N);
6364 for (
const SCEV *Operand :
N->operands().drop_front())
6366 return GetShiftedByZeros(TZ);
6383 CtxI = &*F.getEntryBlock().begin();
6390 .allowEphemerals(
true))
6391 .countMinTrailingZeros();
6392 return GetShiftedByZeros(
Known);
6405 return getConstantMultipleImpl(S, CtxI);
6407 auto I = ConstantMultipleCache.find(S);
6408 if (
I != ConstantMultipleCache.end())
6411 APInt Result = getConstantMultipleImpl(S, CtxI);
6412 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6413 assert(InsertPair.second &&
"Should insert a new key");
6414 return InsertPair.first->second;
6431 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6434 if (std::optional<ConstantRange>
Range = CB->getRange())
6438 if (std::optional<ConstantRange>
Range =
A->getRange())
6441 return std::nullopt;
6448 UnsignedRanges.erase(AddRec);
6449 SignedRanges.erase(AddRec);
6450 ConstantMultipleCache.erase(AddRec);
6455getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6481 Value *Start, *Step;
6488 assert(L && L->getHeader() ==
P->getParent());
6501 case Instruction::AShr:
6502 case Instruction::LShr:
6503 case Instruction::Shl:
6518 KnownStep.getBitWidth() ==
BitWidth);
6521 auto MaxShiftAmt = KnownStep.getMaxValue();
6523 bool Overflow =
false;
6524 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6531 case Instruction::AShr: {
6539 if (KnownStart.isNonNegative())
6542 KnownStart.getMaxValue() + 1);
6543 if (KnownStart.isNegative())
6546 KnownEnd.getMaxValue() + 1);
6549 case Instruction::LShr: {
6558 KnownStart.getMaxValue() + 1);
6560 case Instruction::Shl: {
6564 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6565 return ConstantRange(KnownStart.getMinValue(),
6566 KnownEnd.getMaxValue() + 1);
6591 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6598ScalarEvolution::getRangeRefIter(
const SCEV *S,
6599 ScalarEvolution::RangeSignHint SignHint) {
6600 DenseMap<const SCEV *, ConstantRange> &Cache =
6601 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6604 SmallPtrSet<const SCEV *, 8> Seen;
6608 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6609 if (!Seen.
insert(Expr).second)
6642 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6643 const SCEV *
P = WorkList[
I];
6647 for (
const SCEV *
Op :
P->operands())
6660 if (!WorkList.
empty()) {
6665 getRangeRef(
P, SignHint);
6669 return getRangeRef(S, SignHint, 0);
6672const APInt *ScalarEvolution::getConstantAPIntOrNull(
const SCEV *S) {
6674 return &
C->getAPInt();
6682 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6683 DenseMap<const SCEV *, ConstantRange> &Cache =
6684 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6691 auto I = Cache.
find(S);
6692 if (
I != Cache.
end())
6696 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6701 return getRangeRefIter(S, SignHint);
6704 ConstantRange ConservativeResult(
BitWidth,
true);
6705 using OBO = OverflowingBinaryOperator;
6709 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6713 ConservativeResult =
6720 ConservativeResult = ConstantRange(
6736 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6743 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6750 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6755 return setRange(Cast, SignHint,
X);
6760 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6761 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6763 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6764 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6765 ConservativeResult =
6766 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6768 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6769 unsigned WrapType = OBO::AnyWrap;
6770 if (
Add->hasNoSignedWrap())
6771 WrapType |= OBO::NoSignedWrap;
6772 if (
Add->hasNoUnsignedWrap())
6773 WrapType |= OBO::NoUnsignedWrap;
6775 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6777 return setRange(
Add, SignHint,
6778 ConservativeResult.intersectWith(
X, RangeType));
6782 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6784 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6785 return setRange(
Mul, SignHint,
6786 ConservativeResult.intersectWith(
X, RangeType));
6790 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6791 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6792 return setRange(UDiv, SignHint,
6793 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6801 if (!UnsignedMinValue.
isZero())
6802 ConservativeResult = ConservativeResult.intersectWith(
6803 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6812 bool AllNonNeg =
true;
6813 bool AllNonPos =
true;
6814 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6821 ConservativeResult = ConservativeResult.intersectWith(
6826 ConservativeResult = ConservativeResult.intersectWith(
6835 const SCEV *MaxBEScev =
6849 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6851 ConservativeResult =
6852 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6855 auto RangeFromFactoring = getRangeViaFactoring(
6857 ConservativeResult =
6858 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6864 const SCEV *SymbolicMaxBECount =
6869 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6870 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6871 ConservativeResult =
6872 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6877 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6887 ID = Intrinsic::umax;
6890 ID = Intrinsic::smax;
6894 ID = Intrinsic::umin;
6897 ID = Intrinsic::smin;
6904 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6905 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6907 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6908 return setRange(S, SignHint,
6909 ConservativeResult.intersectWith(
X, RangeType));
6918 ConservativeResult =
6919 ConservativeResult.intersectWith(*MDRange, RangeType);
6924 auto CR = getRangeForUnknownRecurrence(U);
6925 ConservativeResult = ConservativeResult.intersectWith(CR);
6936 if (
U->getType()->isPointerTy()) {
6939 unsigned PtrIdxDiff =
6940 DL.getPointerTypeSizeInBits(
U->getType()) -
BitWidth;
6941 NS = NS > PtrIdxDiff ? NS - PtrIdxDiff : 1;
6946 if (!
Known.Zero.getHiBits(NS).isZero())
6947 Known.Zero.setHighBits(NS);
6948 if (!
Known.One.getHiBits(NS).isZero())
6949 Known.One.setHighBits(NS);
6952 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
6953 ConservativeResult = ConservativeResult.intersectWith(
6954 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
6957 ConservativeResult = ConservativeResult.intersectWith(
6962 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6966 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
6967 DL, CanBeNull,
nullptr);
6983 ConservativeResult = ConservativeResult.intersectWith(
6993 return getRangeRef(AR, SignHint,
Depth + 1);
6997 ConstantRange RangeFromOps(
BitWidth,
false);
6999 for (
const auto &
Op :
Phi->operands()) {
7001 RangeFromOps = RangeFromOps.unionWith(OpRange);
7003 if (RangeFromOps.isFullSet())
7006 ConservativeResult =
7007 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7013 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7015 ConservativeResult = ConservativeResult.difference(Disallowed);
7018 return setRange(U, SignHint, std::move(ConservativeResult));
7024 return setRange(S, SignHint, std::move(ConservativeResult));
7032static std::pair<ConstantRange, bool>
7040 if (Step == 0 || MaxBECount == 0)
7041 return {StartRange,
true};
7047 return {ConstantRange::getFull(
BitWidth),
false};
7063 return {ConstantRange::getFull(
BitWidth),
false};
7076 APInt MovedBoundary;
7081 MovedBoundary = StartLower - std::move(
Offset);
7084 MovedBoundary = StartUpper + std::move(
Offset);
7088 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7095 if (StartRange.
contains(MovedBoundary))
7096 return {ConstantRange::getFull(
BitWidth),
false};
7099 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7101 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7109std::pair<ConstantRange, SCEVFlags>
7110ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7111 const APInt &MaxBECount) {
7115 "mismatched bit widths");
7124 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7126 StartSRange, MaxBECount,
7128 ConstantRange SR = SR1.unionWith(SR2);
7145ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7147 ScalarEvolution::RangeSignHint SignHint) {
7148 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7150 "This only works for non-self-wrapping AddRecs!");
7151 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7155 return ConstantRange::getFull(
BitWidth);
7163 return ConstantRange::getFull(
BitWidth);
7167 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7169 MaxItersWithoutWrap))
7170 return ConstantRange::getFull(
BitWidth);
7191 ConstantRange StartRange = getRangeRef(Start, SignHint);
7192 ConstantRange EndRange = getRangeRef(End, SignHint);
7193 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7197 return RangeBetween;
7202 return ConstantRange::getFull(
BitWidth);
7205 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7206 return RangeBetween;
7208 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7209 return RangeBetween;
7210 return ConstantRange::getFull(
BitWidth);
7215 const APInt &MaxBECount) {
7222 "mismatched bit widths");
7224 struct SelectPattern {
7225 Value *Condition =
nullptr;
7229 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7231 std::optional<unsigned> CastOp;
7245 CastOp = SCast->getSCEVType();
7246 S = SCast->getOperand();
7249 using namespace llvm::PatternMatch;
7256 Condition =
nullptr;
7288 bool isRecognized() {
return Condition !=
nullptr; }
7291 SelectPattern StartPattern(*
this,
BitWidth, Start);
7292 if (!StartPattern.isRecognized())
7293 return ConstantRange::getFull(
BitWidth);
7295 SelectPattern StepPattern(*
this,
BitWidth, Step);
7296 if (!StepPattern.isRecognized())
7297 return ConstantRange::getFull(
BitWidth);
7299 if (StartPattern.Condition != StepPattern.Condition) {
7303 return ConstantRange::getFull(
BitWidth);
7314 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7315 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7316 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7317 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7319 ConstantRange TrueRange =
7320 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7321 ConstantRange FalseRange =
7322 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7335 PDI && PDI->isDisjoint()) {
7350ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7363 SmallPtrSet<const SCEV *, 16> Visited;
7365 auto pushOp = [&](
const SCEV *S) {
7366 if (!Visited.
insert(S).second)
7369 if (Visited.
size() > 30) {
7380 while (!Worklist.
empty()) {
7382 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7383 if (!Bound || DT.dominates(Bound, DefI))
7390 return Bound ? Bound : &*F.getEntryBlock().begin();
7396 return getDefiningScopeBound(
Ops, Discard);
7399bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7401 if (
A->getParent() ==
B->getParent() &&
7406 auto *BLoop = LI.getLoopFor(
B->getParent());
7407 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7408 BLoop->getLoopPreheader() ==
A->getParent() &&
7410 A->getParent()->end()) &&
7418 SCEVPoisonCollector PC(
true);
7420 return PC.MaybePoison.
empty();
7423bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7433bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7450 for (
const Use &
Op :
I->operands()) {
7456 auto *DefI = getDefiningScopeBound(SCEVOps);
7457 return isGuaranteedToTransferExecutionTo(DefI,
I);
7460bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7462 if (isSCEVExprNeverPoison(
I))
7473 auto *ExitingBB =
L->getExitingBlock();
7477 SmallPtrSet<const Value *, 16> KnownPoison;
7486 while (!Worklist.
empty()) {
7489 for (
const Use &U :
Poison->uses()) {
7492 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7496 if (KnownPoison.
insert(PoisonUser).second)
7504ScalarEvolution::LoopProperties
7505ScalarEvolution::getLoopProperties(
const Loop *L) {
7506 using LoopProperties = ScalarEvolution::LoopProperties;
7508 auto Itr = LoopPropertiesCache.find(L);
7509 if (Itr == LoopPropertiesCache.end()) {
7512 return !
SI->isSimple();
7522 return I->mayWriteToMemory();
7525 LoopProperties LP = {
true,
7528 for (
auto *BB :
L->getBlocks())
7529 for (
auto &
I : *BB) {
7531 LP.HasNoAbnormalExits =
false;
7532 if (HasSideEffects(&
I))
7533 LP.HasNoSideEffects =
false;
7534 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7538 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7539 assert(InsertPair.second &&
"We just checked!");
7540 Itr = InsertPair.first;
7553const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7559 Stack.emplace_back(V,
false);
7560 while (!Stack.empty()) {
7561 auto E = Stack.back();
7562 Value *CurV = E.getPointer();
7570 const SCEV *CreatedSCEV =
nullptr;
7573 CreatedSCEV = createSCEV(CurV);
7578 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7582 insertValueToMap(CurV, CreatedSCEV);
7585 Stack.back().setInt(
true);
7588 Stack.emplace_back(
Op,
false);
7605 if (!DT.isReachableFromEntry(
I->getParent()))
7618 switch (BO->Opcode) {
7619 case Instruction::Add:
7620 case Instruction::Mul: {
7627 Ops.push_back(BO->
Op);
7631 Ops.push_back(BO->RHS);
7635 (BO->Opcode == Instruction::Add &&
7636 (NewBO->Opcode != Instruction::Add &&
7637 NewBO->Opcode != Instruction::Sub)) ||
7638 (BO->Opcode == Instruction::Mul &&
7639 NewBO->Opcode != Instruction::Mul)) {
7640 Ops.push_back(BO->LHS);
7645 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7648 Ops.push_back(BO->LHS);
7656 case Instruction::Sub:
7657 case Instruction::UDiv:
7658 case Instruction::URem:
7660 case Instruction::AShr:
7661 case Instruction::Shl:
7662 case Instruction::Xor:
7666 case Instruction::And:
7667 case Instruction::Or:
7671 case Instruction::LShr:
7678 Ops.push_back(BO->LHS);
7679 Ops.push_back(BO->RHS);
7683 switch (
U->getOpcode()) {
7684 case Instruction::Trunc:
7685 case Instruction::ZExt:
7686 case Instruction::SExt:
7687 case Instruction::PtrToAddr:
7688 case Instruction::PtrToInt:
7689 Ops.push_back(
U->getOperand(0));
7692 case Instruction::BitCast:
7694 Ops.push_back(
U->getOperand(0));
7699 case Instruction::SDiv:
7700 case Instruction::SRem:
7701 Ops.push_back(
U->getOperand(0));
7702 Ops.push_back(
U->getOperand(1));
7705 case Instruction::GetElementPtr:
7707 "GEP source element type must be sized");
7711 case Instruction::IntToPtr:
7714 case Instruction::PHI:
7745 Ops.push_back(CondICmp->getOperand(0));
7746 Ops.push_back(CondICmp->getOperand(1));
7766 case Instruction::Select: {
7768 auto CanSimplifyToUnknown = [
this,
U]() {
7786 if (CanSimplifyToUnknown())
7793 case Instruction::Call:
7794 case Instruction::Invoke:
7801 switch (
II->getIntrinsicID()) {
7802 case Intrinsic::abs:
7803 Ops.push_back(
II->getArgOperand(0));
7805 case Intrinsic::umax:
7806 case Intrinsic::umin:
7807 case Intrinsic::smax:
7808 case Intrinsic::smin:
7809 case Intrinsic::usub_sat:
7810 case Intrinsic::uadd_sat:
7811 Ops.push_back(
II->getArgOperand(0));
7812 Ops.push_back(
II->getArgOperand(1));
7814 case Intrinsic::start_loop_iterations:
7815 case Intrinsic::annotation:
7816 case Intrinsic::ptr_annotation:
7817 Ops.push_back(
II->getArgOperand(0));
7829const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7838 if (!DT.isReachableFromEntry(
I->getParent()))
7853 switch (BO->Opcode) {
7854 case Instruction::Add: {
7880 if (BO->Opcode == Instruction::Sub)
7888 if (BO->Opcode == Instruction::Sub)
7895 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7896 NewBO->Opcode != Instruction::Sub)) {
7906 case Instruction::Mul: {
7927 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7936 case Instruction::UDiv:
7940 case Instruction::URem:
7944 case Instruction::Sub: {
7947 Flags = getNoWrapFlagsFromUB(BO->
Op);
7952 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
7955 if (HasPtrLHS || HasPtrRHS) {
7960 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
7961 bool BothPtr) ->
const SCEV * {
7964 const SCEV *PtrSCEV =
getSCEV(PtrOp);
7974 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
7975 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
7983 case Instruction::And:
7989 if (CI->isMinusOne())
7991 const APInt &
A = CI->getValue();
7997 unsigned LZ =
A.countl_zero();
7998 unsigned TZ =
A.countr_zero();
8003 APInt EffectiveMask =
8005 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
8008 const SCEV *ShiftedLHS =
nullptr;
8012 unsigned MulZeros = OpC->getAPInt().countr_zero();
8013 unsigned GCD = std::min(MulZeros, TZ);
8018 const SCEV *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8040 case Instruction::Or:
8049 case Instruction::Xor:
8052 if (CI->isMinusOne())
8061 if (LBO->getOpcode() == Instruction::And &&
8062 LCI->getValue() == CI->getValue())
8063 if (
const SCEVZeroExtendExpr *Z =
8066 const SCEV *Z0 =
Z->getOperand();
8073 if (CI->getValue().isMask(Z0TySize))
8079 APInt Trunc = CI->getValue().trunc(Z0TySize);
8088 case Instruction::Shl:
8106 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8115 ConstantInt *
X = ConstantInt::get(
8121 case Instruction::AShr:
8143 const SCEV *AddTruncateExpr =
nullptr;
8144 ConstantInt *ShlAmtCI =
nullptr;
8145 const SCEV *AddConstant =
nullptr;
8147 if (L &&
L->getOpcode() == Instruction::Add) {
8155 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8162 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8170 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8175 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8180 if (AddTruncateExpr && ShlAmtCI) {
8192 const APInt &ShlAmt = ShlAmtCI->
getValue();
8196 const SCEV *CompositeExpr =
8198 if (
L->getOpcode() != Instruction::Shl)
8199 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8208 switch (
U->getOpcode()) {
8209 case Instruction::Trunc:
8212 case Instruction::ZExt:
8215 case Instruction::SExt:
8225 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8226 Type *Ty =
U->getType();
8234 case Instruction::BitCast:
8240 case Instruction::PtrToAddr: {
8247 case Instruction::PtrToInt:
8251 case Instruction::IntToPtr:
8255 case Instruction::SDiv:
8262 case Instruction::SRem:
8269 case Instruction::GetElementPtr:
8272 case Instruction::PHI:
8275 case Instruction::Select:
8276 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8279 case Instruction::Call:
8280 case Instruction::Invoke:
8285 switch (
II->getIntrinsicID()) {
8286 case Intrinsic::abs:
8290 case Intrinsic::umax:
8294 case Intrinsic::umin:
8298 case Intrinsic::smax:
8302 case Intrinsic::smin:
8306 case Intrinsic::usub_sat: {
8307 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8308 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8312 case Intrinsic::uadd_sat: {
8313 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8314 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8318 case Intrinsic::start_loop_iterations:
8319 case Intrinsic::annotation:
8320 case Intrinsic::ptr_annotation:
8324 case Intrinsic::vscale:
8344 auto *ExitCountType = ExitCount->
getType();
8345 assert(ExitCountType->isIntegerTy());
8347 1 + ExitCountType->getScalarSizeInBits());
8360 auto CanAddOneWithoutOverflow = [&]() {
8362 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8373 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8403 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8404 assert(L->isLoopExiting(ExitingBlock) &&
8405 "Exiting block must actually branch out of the loop!");
8414 const auto *MaxExitCount =
8422 L->getExitingBlocks(ExitingBlocks);
8425 if (ExitingBlocks.
empty() ||
8441 const LoopGuards &Guards) {
8445 const SCEV *TCExpr =
8453 : (
unsigned)Multiple.getZExtValue();
8457 const SCEV *ExitCount) {
8479 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8480 assert(L->isLoopExiting(ExitingBlock) &&
8481 "Exiting block must actually branch out of the loop!");
8491 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8493 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8495 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8505 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8508 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8511 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8519 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8526 return getBackedgeTakenInfo(L).getExact(L,
this);
8528 return getBackedgeTakenInfo(L).getConstantMax(
this);
8530 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8537 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8542 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8546 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8556 for (
PHINode &PN : Header->phis())
8557 if (Visited.
insert(&PN).second)
8561ScalarEvolution::BackedgeTakenInfo &
8562ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8563 auto &BTI = getBackedgeTakenInfo(L);
8564 if (BTI.hasFullInfo())
8567 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8570 return Pair.first->second;
8572 BackedgeTakenInfo
Result =
8573 computeBackedgeTakenCount(L,
true);
8575 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8578ScalarEvolution::BackedgeTakenInfo &
8579ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8585 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8586 BackedgeTakenCounts.try_emplace(L);
8588 return Pair.first->second;
8593 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8600 if (
Result.hasAnyInfo()) {
8603 auto LoopUsersIt = LoopUsers.find(L);
8604 if (LoopUsersIt != LoopUsers.end())
8606 forgetMemoizedResults(ToForget);
8609 for (PHINode &PN :
L->getHeader()->phis())
8610 ConstantEvolutionLoopExitValue.erase(&PN);
8618 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8627 BackedgeTakenCounts.clear();
8628 PredicatedBackedgeTakenCounts.clear();
8629 BECountUsers.clear();
8630 LoopPropertiesCache.clear();
8631 ConstantEvolutionLoopExitValue.clear();
8632 ValueExprMap.clear();
8633 ValuesAtScopes.clear();
8634 ValuesAtScopesUsers.clear();
8635 LoopDispositions.clear();
8636 BlockDispositions.clear();
8637 UnsignedRanges.clear();
8638 SignedRanges.clear();
8639 ExprValueMap.clear();
8641 ConstantMultipleCache.clear();
8642 PredicatedSCEVRewrites.clear();
8644 FoldCacheUser.clear();
8646void ScalarEvolution::visitAndClearUsers(
8651 if (ValueExprMap.
empty()) {
8655 while (!Worklist.
empty()) {
8662 if (It != ValueExprMap.
end()) {
8664 eraseValueFromMap(It->first);
8666 ConstantEvolutionLoopExitValue.erase(PN);
8680 while (!LoopWorklist.
empty()) {
8684 forgetBackedgeTakenCounts(CurrL,
false);
8685 forgetBackedgeTakenCounts(CurrL,
true);
8688 PredicatedSCEVRewrites.remove_if(
8689 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8691 auto LoopUsersItr = LoopUsers.find(CurrL);
8692 if (LoopUsersItr != LoopUsers.end())
8697 visitAndClearUsers(Worklist, Visited, ToForget);
8699 LoopPropertiesCache.erase(CurrL);
8702 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8704 forgetMemoizedResults(ToForget);
8721 visitAndClearUsers(Worklist, Visited, ToForget);
8723 forgetMemoizedResults(ToForget);
8734 visitAndClearUsers(Worklist, Visited, ToForget);
8736 forgetMemoizedResults(ToForget);
8744 auto InvalidateValue = [&](
Value *Val) {
8748 struct InvalidationRootCollector {
8752 InvalidationRootCollector(
Loop *L) : L(L) {}
8754 bool follow(
const SCEV *S) {
8760 if (L->contains(AddRec->
getLoop()))
8765 bool isDone()
const {
return false; }
8768 InvalidationRootCollector
C(L);
8770 forgetMemoizedResults(
C.Roots);
8793 BlockDispositions.clear();
8794 LoopDispositions.clear();
8811 while (!Worklist.
empty()) {
8813 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8814 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8815 if (!LoopDispoRemoved && !BlockDispoRemoved)
8817 auto Users = SCEVUsers.find(Curr);
8818 if (
Users != SCEVUsers.end())
8831const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8835 if (!isComplete() || ExitNotTaken.
empty())
8846 for (
const auto &ENT : ExitNotTaken) {
8847 const SCEV *BECount = ENT.ExactNotTaken;
8850 "We should only have known counts for exiting blocks that dominate "
8853 Ops.push_back(BECount);
8858 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8859 "Predicate should be always true!");
8868const ScalarEvolution::ExitNotTakenInfo *
8869ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8870 const BasicBlock *ExitingBlock,
8871 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8872 for (
const auto &ENT : ExitNotTaken)
8873 if (ENT.ExitingBlock == ExitingBlock) {
8874 if (ENT.hasAlwaysTruePredicate())
8876 else if (Predicates) {
8886const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8888 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8889 if (!getConstantMax())
8892 for (
const auto &ENT : ExitNotTaken)
8893 if (!ENT.hasAlwaysTruePredicate()) {
8901 "No point in having a non-constant max backedge taken count!");
8902 return getConstantMax();
8905const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8907 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8915 for (
const auto &ENT : ExitNotTaken) {
8916 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8919 "We should only have known counts for exiting blocks that "
8925 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8926 "Predicate should be always true!");
8929 if (ExitCounts.
empty())
8938bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8940 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8941 return !ENT.hasAlwaysTruePredicate();
8943 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8959 this->ExactNotTaken = E = ConstantMaxNotTaken;
8960 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8965 "Exact is not allowed to be less precise than Constant Max");
8968 "Exact is not allowed to be less precise than Symbolic Max");
8971 "Symbolic Max is not allowed to be less precise than Constant Max");
8974 "No point in having a non-constant max backedge taken count!");
8976 for (
const auto PredList : PredLists)
8977 for (
const auto *
P : PredList) {
8985 "Backedge count should be int");
8988 "Max backedge count should be int");
9001ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
9003 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
9004 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
9005 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9007 ExitNotTaken.reserve(ExitCounts.
size());
9008 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
9009 std::back_inserter(ExitNotTaken),
9010 [&](
const EdgeExitInfo &EEI) {
9011 BasicBlock *ExitBB = EEI.first;
9012 const ExitLimit &EL = EEI.second;
9013 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
9014 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
9019 "No point in having a non-constant max backedge taken count!");
9023ScalarEvolution::BackedgeTakenInfo
9024ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
9025 bool AllowPredicates) {
9027 L->getExitingBlocks(ExitingBlocks);
9029 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9032 bool CouldComputeBECount =
true;
9034 const SCEV *MustExitMaxBECount =
nullptr;
9035 const SCEV *MayExitMaxBECount =
nullptr;
9036 bool MustExitMaxOrZero =
false;
9037 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9048 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9049 if (ExitIfTrue == CI->
isZero())
9053 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9055 assert((AllowPredicates || EL.Predicates.empty()) &&
9056 "Predicated exit limit when predicates are not allowed!");
9061 ++NumExitCountsComputed;
9065 CouldComputeBECount =
false;
9072 "Exact is known but symbolic isn't?");
9073 ++NumExitCountsNotComputed;
9088 DT.dominates(ExitBB, Latch)) {
9089 if (!MustExitMaxBECount) {
9090 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9091 MustExitMaxOrZero = EL.MaxOrZero;
9094 EL.ConstantMaxNotTaken);
9098 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9101 EL.ConstantMaxNotTaken);
9105 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9109 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9115 for (
const auto &Pair : ExitCounts) {
9117 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9119 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9120 {
L, AllowPredicates});
9122 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9123 MaxBECount, MaxOrZero);
9126ScalarEvolution::ExitLimit
9127ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9128 bool IsOnlyExit,
bool AllowPredicates) {
9129 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9133 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9138 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9139 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9140 "It should have one successor in loop and one exit block!");
9151 if (!
L->contains(SBB)) {
9156 assert(Exit &&
"Exiting block must have at least one exit");
9157 return computeExitLimitFromSingleExitSwitch(
9158 L, SI, Exit, IsOnlyExit);
9165 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9166 bool AllowPredicates) {
9167 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9168 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9169 ControlsOnlyExit, AllowPredicates);
9172std::optional<ScalarEvolution::ExitLimit>
9173ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9174 bool ExitIfTrue,
bool ControlsOnlyExit,
9175 bool AllowPredicates) {
9177 (void)this->ExitIfTrue;
9178 (void)this->AllowPredicates;
9180 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9181 this->AllowPredicates == AllowPredicates &&
9182 "Variance in assumed invariant key components!");
9183 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9184 if (Itr == TripCountMap.end())
9185 return std::nullopt;
9189void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9191 bool ControlsOnlyExit,
9192 bool AllowPredicates,
9194 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9195 this->AllowPredicates == AllowPredicates &&
9196 "Variance in assumed invariant key components!");
9198 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9199 assert(InsertResult.second &&
"Expected successful insertion!");
9204ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9205 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9206 bool ControlsOnlyExit,
bool AllowPredicates) {
9208 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9212 ExitLimit EL = computeExitLimitFromCondImpl(
9213 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9214 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9218ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9219 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9220 bool ControlsOnlyExit,
bool AllowPredicates) {
9222 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9223 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9224 return *LimitFromBinOp;
9230 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9231 if (EL.hasFullInfo() || !AllowPredicates)
9235 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9255 const WithOverflowInst *WO;
9270 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9271 ControlsOnlyExit, AllowPredicates);
9272 if (EL.hasAnyInfo())
9277 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9280std::optional<ScalarEvolution::ExitLimit>
9281ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9285 bool AllowPredicates) {
9294 return std::nullopt;
9298 ExitLimit EL0 = computeExitLimitFromCondCached(
9299 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9300 ExitLimit EL1 = computeExitLimitFromCondCached(
9301 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9306 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9311 if (EitherMayExit) {
9321 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9323 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9326 EL1.ConstantMaxNotTaken);
9328 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9330 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9333 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9337 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9338 BECount = EL0.ExactNotTaken;
9351 SymbolicMaxBECount =
9353 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9357ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9358 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9359 bool AllowPredicates) {
9371 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9373 if (EL.hasAnyInfo())
9376 auto *ExhaustiveCount =
9377 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9380 return ExhaustiveCount;
9382 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9385ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9387 bool ControlsOnlyExit,
bool AllowPredicates) {
9412 ConstantRange CompRange =
9430 InnerLHS = ZExt->getOperand();
9477 if (EL.hasAnyInfo())
9494 if (EL.hasAnyInfo())
return EL;
9527 ControlsOnlyExit, AllowPredicates);
9528 if (EL.hasAnyInfo())
9546 ControlsOnlyExit, AllowPredicates);
9547 if (EL.hasAnyInfo())
9558ScalarEvolution::ExitLimit
9559ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9561 BasicBlock *ExitingBlock,
9562 bool ControlsOnlyExit) {
9563 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9566 if (
Switch->getDefaultDest() == ExitingBlock)
9570 "Default case must not exit the loop!");
9576 if (EL.hasAnyInfo())
9588 "Evaluation of SCEV at constant didn't fold correctly?");
9592ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9602 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9609 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9611 unsigned &OutShiftAmt) {
9612 using namespace PatternMatch;
9614 ConstantInt *ShiftAmt;
9616 OutOpCode = Instruction::LShr;
9618 OutOpCode = Instruction::AShr;
9620 OutOpCode = Instruction::Shl;
9625 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9640 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9642 unsigned &ShiftAmtOut) {
9643 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9659 if (MatchPositiveShift(
LHS, V, OpC, Amt)) {
9660 PostShiftOpCode = OpC;
9666 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9669 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9675 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9682 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9688 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9700 ConstantInt *StableValue =
nullptr;
9705 case Instruction::AShr: {
9712 if (
Known.isNonNegative())
9713 StableValue = ConstantInt::get(Ty, 0);
9714 else if (
Known.isNegative())
9715 StableValue = ConstantInt::get(Ty, -1,
true);
9721 case Instruction::LShr:
9722 case Instruction::Shl:
9732 "Otherwise cannot be an operand to a branch instruction");
9734 if (
Result->isNullValue()) {
9743 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9745 const SCEV *StartSCEV =
getSCEV(StartValue);
9749 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9750 MaxBTC = std::min(MaxBTC, RangeBTC);
9754 const SCEV *UpperBound =
9772 if (
const Function *
F = CI->getCalledFunction())
9782 if (!L->contains(
I))
return false;
9787 return L->getHeader() ==
I->getParent();
9866 if (!
I)
return nullptr;
9880 std::vector<Constant*>
Operands(
I->getNumOperands());
9882 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9891 if (!
C)
return nullptr;
9913 if (IncomingVal != CurrentVal) {
9916 IncomingVal = CurrentVal;
9928ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9931 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9940 DenseMap<Instruction *, Constant *> CurrentIterVals;
9942 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9948 for (PHINode &
PHI : Header->phis()) {
9950 CurrentIterVals[&
PHI] = StartCST;
9952 if (!CurrentIterVals.
count(PN))
9953 return RetVal =
nullptr;
9959 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9962 unsigned IterationNum = 0;
9964 for (; ; ++IterationNum) {
9965 if (IterationNum == NumIterations)
9966 return RetVal = CurrentIterVals[PN];
9970 DenseMap<Instruction *, Constant *> NextIterVals;
9975 NextIterVals[PN] = NextPHI;
9977 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9983 for (
const auto &
I : CurrentIterVals) {
9985 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9990 for (
const auto &
I : PHIsToCompute) {
9991 PHINode *
PHI =
I.first;
9994 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9997 if (NextPHI !=
I.second)
9998 StoppedEvolving =
false;
10003 if (StoppedEvolving)
10004 return RetVal = CurrentIterVals[PN];
10006 CurrentIterVals.swap(NextIterVals);
10010const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
10020 DenseMap<Instruction *, Constant *> CurrentIterVals;
10022 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10025 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
10027 for (PHINode &
PHI : Header->phis()) {
10029 CurrentIterVals[&
PHI] = StartCST;
10031 if (!CurrentIterVals.
count(PN))
10039 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10046 if (CondVal->getValue() ==
uint64_t(ExitWhen)) {
10047 ++NumBruteForceTripCountsComputed;
10052 DenseMap<Instruction *, Constant *> NextIterVals;
10058 for (
const auto &
I : CurrentIterVals) {
10060 if (!
PHI ||
PHI->getParent() != Header)
continue;
10063 for (PHINode *
PHI : PHIsToCompute) {
10065 if (NextPHI)
continue;
10067 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10070 CurrentIterVals.
swap(NextIterVals);
10078 auto &
Values = ValuesAtScopes[V];
10082 return LS.second ? LS.second :
SCEVUse(V);
10084 Values.emplace_back(L,
nullptr);
10087 SCEVUse C = computeSCEVAtScope(V, L);
10088 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10089 if (LS.first == L) {
10095 ValuesAtScopesUsers[
C.getPointer()].push_back({L, V});
10122 switch (V->getSCEVType()) {
10155 assert(!
C->getType()->isPointerTy() &&
10156 "Can only have one pointer, and it must be last");
10181const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10182 SmallVectorImpl<SCEVUse> &NewOps) {
10216SCEVUse ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10217 switch (
V->getSCEVType()) {
10228 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10239 for (++i; i !=
e; ++i)
10279 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10289 for (++i; i !=
e; ++i) {
10294 return getWithOperands(V, NewOps);
10309 const Loop *CurrLoop = this->LI[
I->getParent()];
10320 if (BackedgeTakenCount->
isZero()) {
10321 Value *InitValue =
nullptr;
10322 bool MultipleInitValues =
false;
10328 MultipleInitValues =
true;
10333 if (!MultipleInitValues && InitValue)
10342 unsigned InLoopPred =
10353 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10367 SmallVector<Constant *, 4>
Operands;
10369 bool MadeImprovement =
false;
10384 MadeImprovement |= OrigV != OpV;
10389 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10394 if (!MadeImprovement)
10415const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10417 return stripInjectiveFunctions(ZExt->getOperand());
10419 return stripInjectiveFunctions(SExt->getOperand());
10437 assert(
A != 0 &&
"A must be non-zero.");
10453 if (MinTZ < Mult2 && L->getLoopPredecessor())
10455 if (MinTZ < Mult2) {
10478 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10498static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10504 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10505 << *AddRec <<
'\n');
10508 if (!LC || !MC || !
NC) {
10509 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10510 return std::nullopt;
10516 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10524 N =
N.sext(NewWidth);
10525 M = M.sext(NewWidth);
10526 L = L.sext(NewWidth);
10543 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10544 <<
", multiplied by " <<
T <<
'\n');
10553 std::optional<APInt>
Y) {
10555 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10558 return XW.
slt(YW) ? *
X : *
Y;
10561 return std::nullopt;
10562 return X ? *
X : *
Y;
10579 return std::nullopt;
10580 unsigned W =
X->getBitWidth();
10600static std::optional<APInt>
10606 return std::nullopt;
10609 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10610 std::optional<APInt>
X =
10613 return std::nullopt;
10618 return std::nullopt;
10633static std::optional<APInt>
10637 "Starting value of addrec should be 0");
10638 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10639 <<
Range <<
", addrec " << *AddRec <<
'\n');
10643 "Addrec's initial value should be in range");
10649 return std::nullopt;
10659 auto SolveForBoundary =
10660 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10663 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10664 << Bound <<
" (before multiplying by " << M <<
")\n");
10667 std::optional<APInt> SO;
10670 "signed overflow\n");
10674 "unsigned overflow\n");
10675 std::optional<APInt> UO =
10678 auto LeavesRange = [&] (
const APInt &
X) {
10681 if (
Range.contains(V0->getValue()))
10686 if (
Range.contains(
V1->getValue()))
10695 return {std::nullopt,
false};
10700 if (LeavesRange(*Min))
10701 return { Min,
true };
10702 std::optional<APInt> Max = Min == SO ? UO : SO;
10703 if (LeavesRange(*Max))
10704 return { Max,
true };
10707 return {std::nullopt,
true};
10714 auto SL = SolveForBoundary(
Lower);
10715 auto SU = SolveForBoundary(
Upper);
10718 if (!SL.second || !SU.second)
10719 return std::nullopt;
10762ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10764 bool ControlsOnlyExit,
10765 bool AllowPredicates) {
10776 if (
C->getValue()->isZero())
return C;
10780 const SCEVAddRecExpr *AddRec =
10783 if (!AddRec && AllowPredicates)
10789 if (!AddRec || AddRec->
getLoop() != L)
10800 return ExitLimit(R, R, R,
false, Predicates);
10858 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10888 const SCEV *
Exact =
10896 const SCEV *SymbolicMax =
10898 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10907 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10915 return ExitLimit(
E, M, S,
false, Predicates);
10918ScalarEvolution::ExitLimit
10919ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10927 if (!
C->getValue()->isZero())
10937std::pair<const BasicBlock *, const BasicBlock *>
10938ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10949 if (
const Loop *L = LI.getLoopFor(BB))
10950 return {
L->getLoopPredecessor(),
L->getHeader()};
10952 return {
nullptr, BB};
10961 if (
A ==
B)
return true;
10976 if (ComputesEqualValues(AI, BI))
10984 const SCEV *Op0, *Op1;
11003 auto TrivialCase = [&](
bool TriviallyTrue) {
11012 const SCEV *NewLHS, *NewRHS;
11036 return TrivialCase(
false);
11037 return TrivialCase(
true);
11056 RAdd->hasNoSignedWrap()) ||
11058 RAdd->hasNoUnsignedWrap())) {
11078 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
11079 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
11082 C->getAPInt().isStrictlyPositive()) ||
11106 const APInt &
RA = RC->getAPInt();
11108 bool SimplifiedByConstantRange =
false;
11113 return TrivialCase(
true);
11115 return TrivialCase(
false);
11124 Changed = SimplifiedByConstantRange =
true;
11128 if (!SimplifiedByConstantRange) {
11145 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11151 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11157 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11163 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11183 return TrivialCase(
true);
11185 return TrivialCase(
false);
11290 auto NonRecursive = [OrNegative](
const SCEV *S) {
11292 return C->getAPInt().isPowerOf2() ||
11293 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11299 if (NonRecursive(S))
11309 const SCEV *S, uint64_t M,
11318 APInt C = Cst->getAPInt();
11319 return C.urem(M) == 0;
11325 const SCEV *SmodM =
11346 [&](
SCEVUse Op) { return isKnownMultipleOf(Op, M, Predicates); }))
11353 return isKnownMultipleOf(Op, M, Predicates);
11359 return isKnownMultipleOf(Op, M, Predicates);
11366 for (
auto *
A : *Predicates)
11367 if (
A->implies(
P, *
this))
11380std::pair<const SCEV *, const SCEV *>
11383 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11385 return { Start, Start };
11387 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11396 getUsedLoops(LHS, LoopsUsed);
11397 getUsedLoops(RHS, LoopsUsed);
11399 if (LoopsUsed.
empty())
11404 for (
const auto *L1 : LoopsUsed)
11405 for (
const auto *L2 : LoopsUsed)
11406 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11407 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11408 "Domination relationship is not a linear order");
11438 SplitRHS.second) &&
11448 isKnownPredicateViaSplitting(Pred, LHS, RHS) ||
11449 isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11459 return std::nullopt;
11474 if (KnownWithoutContext)
11475 return KnownWithoutContext;
11482 return std::nullopt;
11488 const Loop *L = LHS->getLoop();
11493std::optional<ScalarEvolution::MonotonicPredicateType>
11496 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11502 auto ResultSwapped =
11505 assert(*ResultSwapped != *Result &&
11506 "monotonicity should flip as we flip the predicate");
11513std::optional<ScalarEvolution::MonotonicPredicateType>
11514ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11528 return std::nullopt;
11532 "Should be greater or less!");
11536 if (!LHS->hasNoUnsignedWrap())
11537 return std::nullopt;
11541 "Relational predicate is either signed or unsigned!");
11542 if (!
LHS->hasNoSignedWrap())
11543 return std::nullopt;
11545 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11553 return std::nullopt;
11556std::optional<ScalarEvolution::LoopInvariantPredicate>
11563 return std::nullopt;
11570 if (!ArLHS || ArLHS->
getLoop() != L)
11571 return std::nullopt;
11575 return std::nullopt;
11601 return std::nullopt;
11638 return std::nullopt;
11641std::optional<ScalarEvolution::LoopInvariantPredicate>
11646 Pred, LHS, RHS, L, CtxI, MaxIter))
11656 Pred, LHS, RHS, L, CtxI,
Op))
11658 return std::nullopt;
11661std::optional<ScalarEvolution::LoopInvariantPredicate>
11676 return std::nullopt;
11683 if (!AR || AR->
getLoop() != L)
11684 return std::nullopt;
11689 Pred = Pred.dropSameSign();
11693 return std::nullopt;
11699 if (Step != One && Step != MinusOne)
11700 return std::nullopt;
11706 return std::nullopt;
11712 return std::nullopt;
11720 if (Step == MinusOne)
11724 return std::nullopt;
11730bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11736 auto CheckRange = [&](
bool IsSigned) {
11739 return RangeLHS.
icmp(Pred, RangeRHS);
11748 if (CheckRange(
true) || CheckRange(
false))
11757bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11764 APInt &OutC2,
SCEVFlags ExpectedFlags) {
11765 SCEVUse XNonConstOp, XConstOp;
11766 SCEVUse YNonConstOp, YConstOp;
11770 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11773 XFlagsPresent = ExpectedFlags;
11778 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11781 YFlagsPresent = ExpectedFlags;
11784 if (YNonConstOp != XNonConstOp)
11792 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11795 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11855bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11876bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11877 const SCEV *
LHS,
const SCEV *
RHS) {
11882 return any_of(*BB, [&](
const Instruction &
I) {
11883 using namespace llvm::PatternMatch;
11888 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11902 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11907 "This cannot be done on broken IR!");
11910 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11919 if (LoopContinuePredicate &&
11920 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11921 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11926 if (WalkingBEDominatingConds)
11932 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11933 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11940 const SCEV *LoopCounter =
11948 for (
auto &AssumeVH : AC.assumptions()) {
11955 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11959 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11962 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11963 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11964 assert(DTN &&
"should reach the loop header before reaching the root!");
11967 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11985 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
11998 if (!DT.isReachableFromEntry(BB))
12002 "This cannot be done on broken IR!");
12010 const bool ProvingStrictComparison =
12012 bool ProvedNonStrictComparison =
false;
12013 bool ProvedNonEquality =
false;
12016 if (!ProvedNonStrictComparison)
12017 ProvedNonStrictComparison = Fn(NonStrictPredicate);
12018 if (!ProvedNonEquality)
12020 if (ProvedNonStrictComparison && ProvedNonEquality)
12025 if (ProvingStrictComparison) {
12027 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
12029 if (SplitAndProve(ProofFn))
12034 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
12036 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
12038 if (ProvingStrictComparison) {
12040 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
12042 if (SplitAndProve(ProofFn))
12051 const Loop *ContainingLoop = LI.getLoopFor(BB);
12053 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
12057 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
12058 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
12061 if (!BlockEntryPredicate)
12070 for (
auto &AssumeVH : AC.assumptions()) {
12074 if (!DT.dominates(CI, BB))
12077 if (ProveViaCond(CI->getArgOperand(0),
false))
12083 F.getParent(), Intrinsic::experimental_guard);
12085 for (
const auto *GU : GuardDecl->users())
12087 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12088 if (ProveViaCond(Guard->getArgOperand(0),
false))
12103 "LHS is not available at Loop Entry");
12105 "RHS is not available at Loop Entry");
12107 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12118 if (FoundCondValue ==
12122 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12126 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12129 const Value *Op0, *Op1;
12132 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12136 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12137 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12141 if (!ICI)
return false;
12145 CmpPredicate FoundPred;
12154 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12157bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12158 const SCEV *
RHS, CmpPredicate FoundPred,
12159 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12160 const Instruction *CtxI) {
12170 auto *WideType = FoundLHS->
getType();
12182 TruncFoundLHS, TruncFoundRHS, CtxI))
12208 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12212bool ScalarEvolution::isImpliedCondBalancedTypes(
12217 "Types should be balanced!");
12224 if (FoundLHS == FoundRHS)
12228 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12240 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12255 LHS, FoundLHS, FoundRHS, CtxI);
12257 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12264 assert(P1 != P2 &&
"Handled earlier!");
12268 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12272 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12275 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12276 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12277 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12282 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12293 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12294 CanonicalRHS, CanonicalFoundLHS,
12295 CanonicalFoundRHS);
12300 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12301 CanonicalRHS, CanonicalFoundLHS,
12302 CanonicalFoundRHS);
12309 const SCEVConstant *
C =
nullptr;
12310 const SCEV *
V =
nullptr;
12328 if (Min ==
C->getAPInt()) {
12333 APInt SharperMin = Min + 1;
12336 case ICmpInst::ICMP_SGE:
12337 case ICmpInst::ICMP_UGE:
12340 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12345 case ICmpInst::ICMP_SGT:
12346 case ICmpInst::ICMP_UGT:
12356 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12361 case ICmpInst::ICMP_SLE:
12362 case ICmpInst::ICMP_ULE:
12363 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12364 LHS, V, getConstant(SharperMin), CtxI))
12368 case ICmpInst::ICMP_SLT:
12369 case ICmpInst::ICMP_ULT:
12370 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12371 LHS, V, getConstant(Min), CtxI))
12385 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12389 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12392 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12408std::optional<APInt>
12415 APInt DiffMul(BW, 1);
12418 for (
unsigned I = 0;
I < 8; ++
I) {
12427 if (LAR->getLoop() != MAR->getLoop())
12428 return std::nullopt;
12432 if (!LAR->isAffine() || !MAR->isAffine())
12433 return std::nullopt;
12435 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12436 return std::nullopt;
12438 Less = LAR->getStart();
12439 More = MAR->getStart();
12444 auto MatchConstMul =
12445 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12450 return std::nullopt;
12452 if (
auto MatchedMore = MatchConstMul(More)) {
12453 if (
auto MatchedLess = MatchConstMul(
Less)) {
12454 if (MatchedMore->second == MatchedLess->second) {
12455 More = MatchedMore->first;
12456 Less = MatchedLess->first;
12457 DiffMul *= MatchedMore->second;
12468 Diff +=
C->getAPInt() * DiffMul;
12471 Diff -=
C->getAPInt() * DiffMul;
12474 Multiplicity[S] +=
Mul;
12476 auto Decompose = [&](
const SCEV *S,
int Mul) {
12483 Decompose(More, 1);
12484 Decompose(
Less, -1);
12488 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12489 for (
const auto &[S,
Mul] : Multiplicity) {
12494 return std::nullopt;
12496 }
else if (
Mul == -1) {
12498 return std::nullopt;
12501 return std::nullopt;
12505 if (NewMore == More || NewLess ==
Less)
12506 return std::nullopt;
12512 if (!More && !
Less)
12516 if (!More || !
Less)
12517 return std::nullopt;
12521 return std::nullopt;
12524bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12546 const auto *Latch = L->getLoopLatch();
12549 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12558 const auto *Latch = L->getLoopLatch();
12561 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12571bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12574 const SCEV *FoundLHS,
12575 const SCEV *FoundRHS) {
12584 if (!AddRecFoundLHS)
12591 const Loop *
L = AddRecFoundLHS->getLoop();
12592 if (L != AddRecLHS->getLoop())
12631 if (!RDiff || *LDiff != *RDiff)
12634 if (LDiff->isMinValue())
12637 APInt FoundRHSLimit;
12640 FoundRHSLimit = -(*RDiff);
12652bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12653 const SCEV *
RHS,
const SCEV *FoundLHS,
12654 const SCEV *FoundRHS,
unsigned Depth) {
12655 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12659 bool Erased = PendingMerges.erase(LPhi);
12660 assert(Erased &&
"Failed to erase LPhi!");
12664 bool Erased = PendingMerges.erase(RPhi);
12665 assert(Erased &&
"Failed to erase RPhi!");
12673 if (!PendingMerges.insert(Phi).second)
12687 if (!PendingMerges.insert(Phi).second)
12693 if (!LPhi && !RPhi)
12704 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12708 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12709 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12710 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12711 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12714 if (RPhi && RPhi->getParent() == LBB) {
12721 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12722 if (!ProvedEasily(L, R))
12733 auto *RLoop = RAR->
getLoop();
12734 auto *Predecessor = RLoop->getLoopPredecessor();
12735 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12737 if (!ProvedEasily(L1, RAR->
getStart()))
12739 auto *Latch = RLoop->getLoopLatch();
12740 assert(Latch &&
"Loop with AddRec with no latch?");
12761 if (
auto *
Loop = LI.getLoopFor(LBB))
12764 if (!ProvedEasily(L,
RHS))
12771bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12774 const SCEV *FoundLHS,
12775 const SCEV *FoundRHS) {
12778 if (
RHS == FoundRHS) {
12783 if (
LHS != FoundLHS)
12790 Value *Shiftee, *ShiftValue;
12792 using namespace PatternMatch;
12793 if (
match(SUFoundRHS->getValue(),
12795 auto *ShifteeS =
getSCEV(Shiftee);
12813bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12814 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12815 const SCEV *FoundRHS) {
12847 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12855 return Diff == FoundDiff;
12858bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12860 const SCEV *FoundLHS,
12861 const SCEV *FoundRHS,
12862 const Instruction *CtxI) {
12863 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12865 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12867 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12868 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12870 isImpliedCondOperandsViaMatchingDiff(Pred,
LHS,
RHS, FoundLHS,
12872 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12876template <
typename MinMaxExprType>
12878 const SCEV *Candidate) {
12883 return is_contained(MinMaxExpr->operands(), Candidate);
12896 const SCEV *LStart, *RStart, *Step;
12993bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12995 const SCEV *FoundLHS,
12996 const SCEV *FoundRHS,
13000 "LHS and RHS have different sizes?");
13003 "FoundLHS and FoundRHS have different sizes?");
13037 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
13039 return Ext->getOperand();
13046 auto *OrigLHS =
LHS;
13047 auto *OrigFoundLHS = FoundLHS;
13048 LHS = GetOpFromSExt(
LHS);
13049 FoundLHS = GetOpFromSExt(FoundLHS);
13052 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
13055 FoundRHS,
Depth + 1);
13068 if (!LHSAddExpr->hasNoSignedWrap())
13071 SCEVUse LL = LHSAddExpr->getOperand(0);
13072 SCEVUse LR = LHSAddExpr->getOperand(1);
13076 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
13077 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
13082 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
13088 using namespace llvm::PatternMatch;
13107 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13115 auto *DTy = Denominator->getType();
13116 auto *FRHSTy = FoundRHS->
getType();
13117 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13136 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13147 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13149 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13157 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13190bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13194 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13198 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13201bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13204 const SCEV *FoundLHS,
13205 const SCEV *FoundRHS) {
13241 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13247bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13248 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13249 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13263 ConstantRange FoundLHSRange =
13267 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13274 return LHSRange.
icmp(Pred, ConstRHS);
13277bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13278 bool IsSigned,
bool Invert) {
13285 APInt MaxRHS = getRangeMax(
RHS,
true, Invert);
13290 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13293 APInt MaxRHS = getRangeMax(
RHS,
false, Invert);
13298 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13311ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
const SCEV *Stride,
13313 bool IsSigned,
bool Invert) {
13328 APInt MinStart = getRangeMin(Start, IsSigned, Invert);
13341 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13347 APInt MaxEnd = getRangeMax(End, IsSigned, Invert);
13353 :
APIntOps::umax(MaxEnd, MinStart);
13355 APInt Delta = MaxEnd - MinStart;
13359 const SCEV *DeltaExpr =
13367ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13368 const Loop *L,
bool IsSigned,
bool Invert,
13369 bool ControlsOnlyExit,
bool AllowPredicates) {
13373 std::optional<LoopGuards> CachedGuards;
13374 auto getGuards = [&]() ->
const LoopGuards & {
13377 return *CachedGuards;
13385 bool PredicatedIV =
false;
13387 if (!
IV && !Invert) {
13391 auto canProveNUW = [&]() {
13394 if (!ControlsOnlyExit)
13415 Limit = Limit.
zext(OuterBitWidth);
13428 Type *Ty = ZExt->getType();
13438 if (!
IV && AllowPredicates) {
13443 PredicatedIV =
true;
13447 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13461 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13468 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13471 const SCEV *GuardedStride = Stride;
13475 bool IVMayOverflow =
true;
13479 if (!PositiveStride) {
13480 const SCEV *LoopGuardedStride =
applyLoopGuards(Stride, getGuards());
13482 GuardedStride = LoopGuardedStride;
13483 PositiveStride =
true;
13490 if (!PositiveStride) {
13539 const SCEVPredicate *
P =
13560 auto wouldZeroStrideBeUB = [&]() {
13572 if (!wouldZeroStrideBeUB()) {
13579 IVMayOverflow = canIVOverflowOnLT(
RHS, GuardedStride, IsSigned, Invert);
13580 if (IVMayOverflow && !NoWrap)
13593 const SCEV *
Start =
IV->getStart();
13599 const SCEV *OrigStart =
Start;
13600 const SCEV *OrigRHS =
RHS;
13601 if (
Start->getType()->isPointerTy()) {
13615 assert(!Invert &&
"RHS must be loop-invariant for Invert");
13617 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13618 any(RHSAddRec->getNoWrapFlags())) {
13631 const SCEV *RHSStart = RHSAddRec->getStart();
13632 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13644 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13653 BECountIfBackedgeTaken =
13680 bool AddingStrideMinusOneMayOverflow = IVMayOverflow && [&] {
13727 if (!Invert && (Start == Stride || Start ==
getMinusSCEV(Stride, One))) {
13744 auto StepBack = [&](
const SCEV *
V,
const SCEV *
Offset) ->
const SCEV * {
13749 auto Distance = [&](
const SCEV *From,
const SCEV *To) {
13753 const SCEV *OrigPrevStart = StepBack(OrigStart, Stride);
13760 if ((!AddingStrideMinusOneMayOverflow ||
13792 const SCEV *Numerator =
13798 auto canProveRHSIsAtOrBeyondStart = [&]() {
13803 auto SwapIfInverted = [&](
const SCEV *
A,
const SCEV *
B) {
13804 return Invert ? std::pair(
B,
A) : std::pair(
A,
B);
13813 auto [GELHS, GERHS] = SwapIfInverted(OrigRHS, OrigStart);
13828 auto [GTLHS, GTRHS] = SwapIfInverted(OrigRHS, StepBack(OrigStart, One));
13834 if (canProveRHSIsAtOrBeyondStart()) {
13857 const SCEV *Delta = Distance(Start, End);
13858 if (!AddingStrideMinusOneMayOverflow) {
13870 const SCEV *ConstantMaxBECount;
13871 bool MaxOrZero =
false;
13873 ConstantMaxBECount = BECount;
13875 ConstantMaxBECount = computeMaxBECountForLT(
13882 const APInt *IfTaken, *RangeMax;
13885 IfTaken->
ugt(*RangeMax)) {
13886 ConstantMaxBECount =
getZero(BECountIfBackedgeTaken->getType());
13888 ConstantMaxBECount = BECountIfBackedgeTaken;
13898 const SCEV *SymbolicMaxBECount =
13900 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13906 if (
Range.isFullSet())
13911 if (!SC->getValue()->isZero()) {
13917 return ShiftedAddRec->getNumIterationsInRange(
13918 Range.subtract(SC->getAPInt()), SE);
13949 APInt ExitVal = (End +
A).udiv(
A);
13962 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13963 "Linear scev computation is off in a bad way!");
13994 assert(!
Last->isZero() &&
"Recurrency with zero step?");
14027 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14029 SE->ConstantEvolutionLoopExitValue.erase(PN);
14030 SE->eraseValueFromMap(getValPtr());
14034void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
14035 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14045 : CallbackVH(
V), SE(se) {}
14054 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
14056 LoopDispositions(64), BlockDispositions(64) {
14068 F.getParent(), Intrinsic::experimental_guard);
14069 HasGuards = GuardDecl && !GuardDecl->use_empty();
14073 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
14074 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14075 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14076 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14077 PendingMerges(
std::
move(Arg.PendingMerges)),
14078 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14079 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14080 PredicatedBackedgeTakenCounts(
14081 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14082 BECountUsers(
std::
move(Arg.BECountUsers)),
14083 ConstantEvolutionLoopExitValue(
14084 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14085 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14086 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14087 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14088 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14089 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14090 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14091 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14092 SignedRanges(
std::
move(Arg.SignedRanges)),
14093 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14094 UniquePreds(
std::
move(Arg.UniquePreds)),
14095 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14096 ConstantSCEVs(
std::
move(Arg.ConstantSCEVs)),
14097 LoopUsers(
std::
move(Arg.LoopUsers)),
14098 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14099 FirstUnknown(Arg.FirstUnknown) {
14100 Arg.FirstUnknown =
nullptr;
14109 Tmp->~SCEVUnknown();
14111 FirstUnknown =
nullptr;
14113 ExprValueMap.clear();
14114 ValueExprMap.clear();
14116 BackedgeTakenCounts.clear();
14117 PredicatedBackedgeTakenCounts.clear();
14119 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14120 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14121 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14122 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14144 L->getHeader()->printAsOperand(OS,
false);
14148 L->getExitingBlocks(ExitingBlocks);
14149 if (ExitingBlocks.
size() != 1)
14150 OS <<
"<multiple exits> ";
14154 OS <<
"backedge-taken count is ";
14157 OS <<
"Unpredictable backedge-taken count.";
14160 if (ExitingBlocks.
size() > 1)
14161 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14162 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14170 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14173 OS <<
"\n Predicates:\n";
14174 for (
const auto *
P : Predicates)
14182 L->getHeader()->printAsOperand(OS,
false);
14187 OS <<
"constant max backedge-taken count is ";
14190 OS <<
", actual taken count either this or zero.";
14192 OS <<
"Unpredictable constant max backedge-taken count. ";
14197 L->getHeader()->printAsOperand(OS,
false);
14202 OS <<
"symbolic max backedge-taken count is ";
14205 OS <<
", actual taken count either this or zero.";
14207 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14211 if (ExitingBlocks.
size() > 1)
14212 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14213 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14223 OS <<
"\n predicated symbolic max exit count for "
14224 << ExitingBlock->
getName() <<
": ";
14226 OS <<
"\n Predicates:\n";
14227 for (
const auto *
P : Predicates)
14238 L->getHeader()->printAsOperand(OS,
false);
14241 OS <<
"Predicated backedge-taken count is ";
14244 OS <<
"Unpredictable predicated backedge-taken count.";
14246 OS <<
" Predicates:\n";
14247 for (
const auto *
P : Preds)
14252 auto *PredConstantMax =
14254 if (PredConstantMax != ConstantBTC) {
14256 L->getHeader()->printAsOperand(OS,
false);
14259 OS <<
"Predicated constant max backedge-taken count is ";
14262 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14264 OS <<
" Predicates:\n";
14265 for (
const auto *
P : Preds)
14270 auto *PredSymbolicMax =
14272 if (SymbolicBTC != PredSymbolicMax) {
14274 L->getHeader()->printAsOperand(OS,
false);
14277 OS <<
"Predicated symbolic max backedge-taken count is ";
14280 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14282 OS <<
" Predicates:\n";
14283 for (
const auto *
P : Preds)
14289 L->getHeader()->printAsOperand(OS,
false);
14316 OS <<
"Computable";
14326 OS <<
"DoesNotDominate";
14332 OS <<
"ProperlyDominates";
14349 OS <<
"Classifying expressions for: ";
14350 F.printAsOperand(OS,
false);
14365 const Loop *L = LI.getLoopFor(
I.getParent());
14380 OS <<
"\t\t" "Exits: ";
14383 OS <<
"<<Unknown>>";
14389 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14391 Iter->getHeader()->printAsOperand(OS,
false);
14399 InnerL->getHeader()->printAsOperand(OS,
false);
14410 OS <<
"Determining loop execution counts for: ";
14411 F.printAsOperand(OS,
false);
14419 auto &
Values = LoopDispositions[S];
14420 for (
auto &V :
Values) {
14421 if (V.getPointer() == L)
14426 auto &Values2 = LoopDispositions[S];
14428 if (V.getPointer() == L) {
14437ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14455 if (L->contains(AR->
getLoop()) &&
14457 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14462 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14463 " dominate the contained loop's header?");
14490 bool HasVarying =
false;
14491 bool HasUniform =
false;
14533 auto &
Values = BlockDispositions[S];
14534 for (
auto &V :
Values) {
14535 if (V.getPointer() == BB)
14540 auto &Values2 = BlockDispositions[S];
14542 if (V.getPointer() == BB) {
14551ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14580 bool Proper =
true;
14591 if (Instruction *
I =
14593 if (
I->getParent() == BB)
14595 if (DT.properlyDominates(
I->getParent(), BB))
14614void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14617 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14618 auto It = BECounts.find(L);
14619 if (It != BECounts.end()) {
14620 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14621 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14623 auto UserIt = BECountUsers.find(S);
14624 assert(UserIt != BECountUsers.end());
14629 BECounts.erase(It);
14637 while (!Worklist.
empty()) {
14639 auto Users = SCEVUsers.find(Curr);
14640 if (
Users != SCEVUsers.end())
14641 for (
const auto *User :
Users->second)
14642 if (ToForget.
insert(User).second)
14646 for (
const auto *S : ToForget)
14647 forgetMemoizedResultsImpl(S);
14649 PredicatedSCEVRewrites.remove_if(
14650 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14653void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14654 LoopDispositions.erase(S);
14655 BlockDispositions.erase(S);
14656 UnsignedRanges.erase(S);
14657 SignedRanges.erase(S);
14658 HasRecMap.erase(S);
14659 ConstantMultipleCache.erase(S);
14662 UnsignedWrapViaInductionTried.erase(AR);
14663 SignedWrapViaInductionTried.erase(AR);
14666 auto ExprIt = ExprValueMap.find(S);
14667 if (ExprIt != ExprValueMap.end()) {
14668 for (
Value *V : ExprIt->second) {
14669 auto ValueIt = ValueExprMap.find_as(V);
14670 if (ValueIt != ValueExprMap.end())
14671 ValueExprMap.erase(ValueIt);
14673 ExprValueMap.erase(ExprIt);
14676 auto ScopeIt = ValuesAtScopes.find(S);
14677 if (ScopeIt != ValuesAtScopes.end()) {
14678 for (
const auto &Pair : ScopeIt->second)
14680 llvm::erase(ValuesAtScopesUsers[Pair.second.getPointer()],
14681 std::make_pair(Pair.first, S));
14682 ValuesAtScopes.erase(ScopeIt);
14685 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14686 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14687 for (
const auto &Pair : ScopeUserIt->second)
14690 llvm::erase_if(ValuesAtScopes[Pair.second], [&](
const auto &LS) {
14691 return LS.first == Pair.first && LS.second.getPointer() == S;
14693 ValuesAtScopesUsers.erase(ScopeUserIt);
14696 auto BEUsersIt = BECountUsers.find(S);
14697 if (BEUsersIt != BECountUsers.end()) {
14699 auto Copy = BEUsersIt->second;
14700 for (
const auto &Pair : Copy)
14701 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14702 BECountUsers.erase(BEUsersIt);
14705 auto FoldUser = FoldCacheUser.find(S);
14706 if (FoldUser != FoldCacheUser.end())
14707 for (
auto &KV : FoldUser->second)
14708 FoldCache.erase(KV);
14709 FoldCacheUser.erase(S);
14713ScalarEvolution::getUsedLoops(
const SCEV *S,
14715 struct FindUsedLoops {
14716 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14717 : LoopsUsed(LoopsUsed) {}
14718 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14719 bool follow(
const SCEV *S) {
14725 bool isDone()
const {
return false; }
14728 FindUsedLoops
F(LoopsUsed);
14729 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14732void ScalarEvolution::getReachableBlocks(
14735 Worklist.
push_back(&F.getEntryBlock());
14736 while (!Worklist.
empty()) {
14738 if (!Reachable.
insert(BB).second)
14746 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14753 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14757 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14792 SCEVMapper SCM(SE2);
14794 SE2.getReachableBlocks(ReachableBlocks, F);
14796 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14814 while (!LoopStack.
empty()) {
14820 if (!ReachableBlocks.
contains(L->getHeader()))
14825 auto It = BackedgeTakenCounts.find(L);
14826 if (It == BackedgeTakenCounts.end())
14830 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14850 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14851 if (Delta && !Delta->
isZero()) {
14852 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14853 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14854 dbgs() <<
"New: " << *NewBECount <<
"\n";
14855 dbgs() <<
"Delta: " << *Delta <<
"\n";
14863 while (!Worklist.
empty()) {
14865 if (ValidLoops.
insert(L).second)
14866 Worklist.
append(L->begin(), L->end());
14868 for (
const auto &KV : ValueExprMap) {
14873 "AddRec references invalid loop");
14878 auto It = ExprValueMap.find(KV.second);
14879 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14880 dbgs() <<
"Value " << *KV.first
14881 <<
" is in ValueExprMap but not in ExprValueMap\n";
14886 if (!ReachableBlocks.
contains(
I->getParent()))
14888 const SCEV *OldSCEV = SCM.visit(KV.second);
14890 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14891 if (Delta && !Delta->
isZero()) {
14892 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14893 <<
"Old: " << *OldSCEV <<
"\n"
14894 <<
"New: " << *NewSCEV <<
"\n"
14895 <<
"Delta: " << *Delta <<
"\n";
14901 for (
const auto &KV : ExprValueMap) {
14902 for (
Value *V : KV.second) {
14903 const SCEV *S = ValueExprMap.lookup(V);
14905 dbgs() <<
"Value " << *V
14906 <<
" is in ExprValueMap but not in ValueExprMap\n";
14909 if (S != KV.first) {
14910 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14911 << *KV.first <<
"\n";
14918 for (
const auto &S : UniqueSCEVs) {
14923 auto It = SCEVUsers.find(
Op);
14924 if (It != SCEVUsers.end() && It->second.count(&S))
14926 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14927 <<
" is not being tracked!\n";
14933 for (
const auto &ValueAndVec : ValuesAtScopes) {
14935 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14936 const Loop *L = LoopAndValueAtScope.first;
14937 SCEVUse ValueAtScope = LoopAndValueAtScope.second;
14939 auto It = ValuesAtScopesUsers.find(ValueAtScope.
getPointer());
14940 if (It != ValuesAtScopesUsers.end() &&
14943 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14944 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14950 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14951 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14952 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14953 const Loop *L = LoopAndValue.first;
14954 const SCEV *
Value = LoopAndValue.second;
14956 auto It = ValuesAtScopes.find(
Value);
14959 if (It != ValuesAtScopes.end() &&
any_of(It->second, [&](
const auto &LS) {
14960 return LS.first == L && LS.second.getPointer() == ValueAtScope;
14963 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14964 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14970 auto VerifyBECountUsers = [&](
bool Predicated) {
14972 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14973 for (
const auto &LoopAndBEInfo : BECounts) {
14974 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14975 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14977 auto UserIt = BECountUsers.find(S);
14978 if (UserIt != BECountUsers.end() &&
14979 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14981 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14982 <<
" missing from BECountUsers\n";
14989 VerifyBECountUsers(
false);
14990 VerifyBECountUsers(
true);
14993 for (
auto &[S,
Values] : LoopDispositions) {
14994 for (
auto [
Loop, CachedDisposition] :
Values) {
14996 if (CachedDisposition != RecomputedDisposition) {
14997 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
14998 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
14999 << RecomputedDisposition <<
"\n";
15006 for (
auto &[S,
Values] : BlockDispositions) {
15007 for (
auto [BB, CachedDisposition] :
Values) {
15009 if (CachedDisposition != RecomputedDisposition) {
15010 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
15011 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
15012 <<
", actual " << RecomputedDisposition <<
"\n";
15019 for (
auto [
FoldID, Expr] : FoldCache) {
15020 auto I = FoldCacheUser.find(Expr);
15021 if (
I == FoldCacheUser.end()) {
15022 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
15027 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
15031 for (
auto [Expr, IDs] : FoldCacheUser) {
15032 for (
auto &
FoldID : IDs) {
15035 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
15040 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
15041 <<
" != " << *Expr <<
"!\n";
15052 for (
auto [S, Multiple] : ConstantMultipleCache) {
15054 if ((Multiple != 0 && RecomputedMultiple != 0 &&
15055 Multiple.
urem(RecomputedMultiple) != 0 &&
15056 RecomputedMultiple.
urem(Multiple) != 0)) {
15057 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
15058 << *S <<
" : Computed " << RecomputedMultiple
15059 <<
" but cache contains " << Multiple <<
"!\n";
15067 FunctionAnalysisManager::Invalidator &Inv) {
15099 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15100 <<
F.getName() <<
"':\n";
15106 "Scalar Evolution Analysis",
false,
true)
15155 const SCEV *LHS,
const SCEV *RHS) {
15157 assert(LHS->getType() == RHS->getType() &&
15158 "Type mismatch between LHS and RHS");
15161 ID.AddInteger(Pred);
15162 ID.AddPointer(LHS);
15163 ID.AddPointer(RHS);
15165 if (
const auto *S = UniquePreds.lookup(ID, Token))
15169 UniquePreds.insert(Eq, Token);
15180 ID.AddInteger(AddedFlags);
15182 if (
const auto *S = UniquePreds.lookup(ID, Token))
15184 auto *OF =
new (SCEVAllocator)
15186 UniquePreds.insert(OF, Token);
15206 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15207 return Rewriter.visit(S);
15213 for (
const auto *Pred : U->getPredicates())
15215 if (IPred->getLHS() == Expr &&
15217 return IPred->getRHS();
15219 if (IPred->getLHS() == Expr &&
15220 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15221 return IPred->getRHS();
15224 return convertToAddRecWithPreds(Expr);
15227 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15243 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15260 explicit SCEVPredicateRewriter(
15261 const Loop *L, ScalarEvolution &SE,
15262 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15263 const SCEVPredicate *Pred)
15264 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15266 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15269 return Pred && Pred->
implies(
P, SE);
15275 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15278 return addOverflowAssumption(
A);
15287 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15291 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15293 if (!PredicatedRewrite)
15295 for (
const auto *
P : PredicatedRewrite->second){
15298 if (L != WP->getExpr()->getLoop())
15301 if (!addOverflowAssumption(
P))
15304 return PredicatedRewrite->first;
15307 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15308 const SCEVPredicate *Pred;
15317 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15324 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15344 if (!Step->
isOne())
15369 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15370 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15383 return Op->LHS == LHS &&
Op->RHS == RHS;
15390 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15392 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15417 const SCEV *Start = AR->getStart();
15418 const SCEV *OpStart =
Op->AR->getStart();
15423 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15432 const SCEV *Step = AR->getStepRecurrence(SE);
15433 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15454 SCEVFlags ScevFlags = AR->getNoWrapFlags();
15476 for (
const auto *
P : Preds)
15489 return this->implies(I, SE);
15501 const Loop *L = NWrap->getExpr()->getLoop();
15508 return RewrittenAR &&
15514 for (
const auto *Pred : Preds)
15515 Pred->print(OS,
Depth);
15520 for (
const auto *Pred : Set->Preds)
15528 bool CheckImplies = Preds.
size() < 16;
15531 if (CheckImplies &&
implies(
N, SE))
15537 for (
auto *
P : Preds) {
15538 if (CheckImplies &&
N->implies(
P, SE))
15542 Preds = std::move(PrunedPreds);
15543 Preds.push_back(
N);
15550 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15559 SCEVUsers[
Op].insert(
User);
15563 const SCEV *Expr = SE.getSCEV(V);
15568 RewriteEntry &Entry = RewriteMap[Expr];
15571 if (Entry.second && Generation == Entry.first)
15572 return Entry.second;
15577 Expr = Entry.second;
15579 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15580 Entry = {Generation, NewSCEV};
15586 if (!BackedgeCount) {
15588 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15589 for (
const auto *
P : Preds)
15592 return BackedgeCount;
15596 if (!SymbolicMaxBackedgeCount) {
15598 SymbolicMaxBackedgeCount =
15599 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15600 for (
const auto *
P : Preds)
15603 return SymbolicMaxBackedgeCount;
15607 if (!SmallConstantMaxTripCount) {
15609 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15610 for (
const auto *
P : Preds)
15613 return *SmallConstantMaxTripCount;
15617 if (Preds->implies(&Pred, SE))
15622 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15623 updateGeneration();
15636void PredicatedScalarEvolution::updateGeneration() {
15638 if (++Generation == 0) {
15639 for (
auto &
II : RewriteMap) {
15640 const SCEV *Rewritten =
II.second.second;
15650 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15656 ExtraPreds->
append(NewPreds);
15662 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15668 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15671 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15675 for (
auto *BB : L.getBlocks())
15676 for (
auto &
I : *BB) {
15677 if (!SE.isSCEVable(
I.getType()))
15680 auto *Expr = SE.getSCEV(&
I);
15681 auto II = RewriteMap.find(Expr);
15683 if (
II == RewriteMap.end())
15687 if (
II->second.second == Expr)
15692 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15700 LoopGuards Guards(SE);
15708void ScalarEvolution::LoopGuards::collectFromPHI(
15716 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15717 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15731 auto &RewriteMap =
G->second.RewriteMap;
15732 if (RewriteMap.empty())
15734 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15735 if (S == RewriteMap.end())
15741 return {C0, SM->getSCEVType()};
15744 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15745 MinMaxPattern
P2) -> MinMaxPattern {
15746 auto [C1,
T1] =
P1;
15747 auto [C2, T2] =
P2;
15748 if (!C1 || !C2 ||
T1 != T2)
15752 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15754 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15756 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15758 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15763 auto P = GetMinMaxConst(0);
15764 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15767 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15770 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15773 Guards.RewriteMap.insert({
LHS,
RHS});
15781 const APInt &DivisorVal,
15783 const APInt *ExprVal;
15796 const APInt &DivisorVal,
15798 const APInt *ExprVal;
15806 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15820 const SCEV *URemRHS =
nullptr;
15824 const SCEV *Multiple =
15826 DivInfo[URemLHS] = Multiple;
15828 Multiples[URemLHS] =
C->getAPInt();
15848 auto IsMinMaxSCEVWithNonNegativeConstant =
15852 if (
MinMax->getNumOperands() != 2)
15855 if (
C->getAPInt().isNegative())
15857 SCTy =
MinMax->getSCEVType();
15866 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15868 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15873 auto *DivisibleExpr =
15881void ScalarEvolution::LoopGuards::collectFromBlock(
15883 const BasicBlock *
Block,
const BasicBlock *Pred,
15891 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15902 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15904 if (From == FromRewritten)
15906 RewriteMap[From] = To;
15912 auto GetMaybeRewritten = [&](
const SCEV *S) {
15913 return RewriteMap.lookup_or(S, S);
15920 const SCEV *MatchLHS,
15921 const SCEV *MatchRHS) {
15922 const SCEVConstant *C1;
15925 if (!
match(MatchLHS,
15937 const SCEV *RewrittenLHS = GetMaybeRewritten(LHSUnknown);
15938 ExactRegion = ExactRegion.intersectWith(SE.
getUnsignedRange(RewrittenLHS),
15943 if (ExactRegion.isEmptySet() || ExactRegion.isWrappedSet() ||
15944 ExactRegion.isFullSet())
15947 const SCEV *RegionMin = SE.
getConstant(ExactRegion.getUnsignedMin());
15948 const SCEV *RegionMax = SE.
getConstant(ExactRegion.getUnsignedMax());
15949 const SCEV *ClampedLHS =
15951 AddRewrite(LHSUnknown, RewrittenLHS, ClampedLHS);
15954 if (MatchRangeCheckIdiom(Predicate,
LHS,
RHS))
15967 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15969 const APInt &DividesBy =
15984 switch (Predicate) {
16013 SmallPtrSet<const SCEV *, 16> Visited;
16015 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
16019 while (!Worklist.
empty()) {
16023 if (!Visited.
insert(From).second)
16025 const SCEV *FromRewritten = GetMaybeRewritten(From);
16026 const SCEV *To =
nullptr;
16028 switch (Predicate) {
16033 EnqueueOperands(
UMax);
16039 EnqueueOperands(
SMax);
16045 EnqueueOperands(
UMin);
16051 EnqueueOperands(
SMin);
16059 const SCEV *OneAlignedUp =
16061 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16073 const SCEVConstant *
C;
16082 Guards.NotEqual.insert({
LHS,
RHS});
16091 AddRewrite(From, FromRewritten, To);
16108 SE.F.
getParent(), Intrinsic::experimental_guard);
16110 for (
const auto *GU : GuardDecl->users())
16112 if (Guard->getFunction() ==
Block->getParent() &&
16121 unsigned NumCollectedConditions = 0;
16123 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16125 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16127 const CondBrInst *LoopEntryPredicate =
16129 if (!LoopEntryPredicate)
16134 NumCollectedConditions++;
16138 if (
Depth > 0 && NumCollectedConditions == 2)
16146 if (Pair.second->hasNPredecessorsOrMore(2) &&
16148 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16149 for (
auto &Phi : Pair.second->phis())
16160 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16161 SmallVector<Value *, 8> Worklist;
16162 SmallPtrSet<Value *, 8> Visited;
16164 while (!Worklist.
empty()) {
16171 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16195 DenseMap<const SCEV *, APInt> Multiples;
16197 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16204 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16205 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16209 for (
const auto &[K, Divisor] : Multiples) {
16210 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16211 Guards.RewriteMap[
K] =
16213 Guards.
rewrite(K), Divisor, SE),
16222 Guards.PreserveNUW =
true;
16223 Guards.PreserveNSW =
true;
16224 for (
const SCEV *Expr : ExprsToRewrite) {
16225 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16226 Guards.PreserveNUW &=
16228 Guards.PreserveNSW &=
16235 if (ExprsToRewrite.size() > 1) {
16236 for (
const SCEV *Expr : ExprsToRewrite) {
16237 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16238 Guards.RewriteMap.erase(Expr);
16239 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16248 class SCEVLoopGuardRewriter
16259 NotEqual(Guards.NotEqual) {
16260 if (Guards.PreserveNUW)
16262 if (Guards.PreserveNSW)
16269 return Map.lookup_or(Expr, Expr);
16273 if (
const SCEV *S = Map.lookup(Expr))
16280 if (
const SCEV *S = Map.lookup(Expr))
16287 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16288 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16289 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16291 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16292 if (
const SCEV *S = Map.lookup(NarrowExt))
16293 return SE.getZeroExtendExpr(S, Ty);
16294 Bitwidth = Bitwidth / 2;
16302 if (
const SCEV *S = Map.lookup(Expr))
16309 if (
const SCEV *S = Map.lookup(Expr))
16315 if (
const SCEV *S = Map.lookup(Expr))
16321 if (
const SCEV *S = Map.lookup(Expr))
16326 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16331 if (NotEqual.contains({LHS, RHS})) {
16333 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16334 return SE.getUMaxExpr(OneAlignedUp, S);
16341 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16352 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16353 return SE.getAddExpr(
16356 if (
const SCEV *S = Map.lookup(
Add))
16357 return SE.getAddExpr(Expr->
getOperand(0), S);
16365 const SCEV *S =
nullptr;
16372 S = Map.lookup(SE.getAddExpr(NewC, Expr->
getOperand(1)));
16375 return SE.getAddExpr(S, SE.getMinusOne(Expr->
getType()));
16410 if (RewriteMap.empty() && NotEqual.empty())
16413 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16414 return Rewriter.visit(Expr);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Expand Atomic instructions
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
static bool isSigned(unsigned Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
Value * getPointer(Value *Ptr)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This defines the Use class.
iv Induction Variable Users
static 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 bool CollectAddOperandsWithScales(SmallDenseMap< SCEVUse, APInt, 16 > &M, SmallVectorImpl< SCEVUse > &NewOps, APInt &AccumulatedConstant, ArrayRef< SCEVUse > Ops, const APInt &Scale, ScalarEvolution &SE)
Process the given Ops list, which is a list of operands to be added under the given scale,...
static const SCEV * constantFoldAndGroupOps(ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT, SmallVectorImpl< SCEVUse > &Ops, FoldT Fold, IsIdentityT IsIdentity, IsAbsorberT IsAbsorber)
Performs a number of common optimizations on the passed Ops.
static bool IsKnownPredicateViaAddRecStart(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
static const SCEV * getPreStartForExtend(const SCEVAddRecExpr *AR, ScalarEvolution *SE, unsigned Depth)
static void GroupByComplexity(SmallVectorImpl< SCEVUse > &Ops, LoopInfo *LI, DominatorTree &DT)
Given a list of SCEV objects, order them by their complexity, and group objects of the same complexit...
static bool collectDivisibilityInformation(ICmpInst::Predicate Predicate, const SCEV *LHS, const SCEV *RHS, DenseMap< const SCEV *, const SCEV * > &DivInfo, DenseMap< const SCEV *, APInt > &Multiples, ScalarEvolution &SE)
static cl::opt< unsigned > MaxSCEVOperationsImplicationDepth("scalar-evolution-max-scev-operations-implication-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV operations implication analysis"), cl::init(2))
static void PushDefUseChildren(Instruction *I, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push users of the given Instruction onto the given Worklist.
static std::optional< APInt > SolveQuadraticAddRecRange(const SCEVAddRecExpr *AddRec, const ConstantRange &Range, ScalarEvolution &SE)
Let c(n) be the value of the quadratic chrec {0,+,M,+,N} after n iterations.
static cl::opt< bool > UseContextForNoWrapFlagInference("scalar-evolution-use-context-for-no-wrap-flag-strenghening", cl::Hidden, cl::desc("Infer nuw/nsw flags using context where suitable"), cl::init(true))
static cl::opt< bool > EnableFiniteLoopControl("scalar-evolution-finite-loop", cl::Hidden, cl::desc("Handle <= and >= in finite loops"), cl::init(true))
static bool getOperandsForSelectLikePHI(DominatorTree &DT, PHINode *PN, Value *&Cond, Value *&LHS, Value *&RHS)
static std::optional< std::tuple< APInt, APInt, APInt, APInt, unsigned > > GetQuadraticEquation(const SCEVAddRecExpr *AddRec)
For a given quadratic addrec, generate coefficients of the corresponding quadratic equation,...
static bool isKnownPredicateExtendIdiom(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
static std::optional< APInt > SolveQuadraticAddRecExact(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE)
Let c(n) be the value of the quadratic chrec {L,+,M,+,N} after n iterations.
static std::optional< APInt > TruncIfPossible(std::optional< APInt > X, unsigned BitWidth)
Helper function to truncate an optional APInt to a given BitWidth.
static cl::opt< unsigned > MaxSCEVCompareDepth("scalar-evolution-max-scev-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV complexity comparisons"), cl::init(32))
static SCEVFlags StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, ArrayRef< SCEVUse > Ops, SCEVFlags Flags)
static APInt extractConstantWithoutWrapping(ScalarEvolution &SE, const SCEVConstant *ConstantTerm, const SCEVAddExpr *WholeAddExpr)
static cl::opt< unsigned > MaxConstantEvolvingDepth("scalar-evolution-max-constant-evolving-depth", cl::Hidden, cl::desc("Maximum depth of recursive constant evolving"), cl::init(32))
static bool canConstantEvolve(Instruction *I, const Loop *L, const TargetLibraryInfo *TLI)
Determine whether this instruction can constant evolve within this loop assuming its operands can all...
static bool MatchBinarySub(const SCEV *S, SCEVUse &LHS, SCEVUse &RHS)
static std::optional< ConstantRange > GetRangeFromMetadata(Value *V)
Helper method to assign a range to V from metadata present in the IR.
static cl::opt< unsigned > HugeExprThreshold("scalar-evolution-huge-expr-threshold", cl::Hidden, cl::desc("Size of the expression which is considered huge"), cl::init(4096))
static Type * isSimpleCastedPHI(const SCEV *Op, const SCEVUnknown *SymbolicPHI, bool &Signed, ScalarEvolution &SE)
Helper function to createAddRecFromPHIWithCasts.
static Constant * EvaluateExpression(Value *V, const Loop *L, DenseMap< Instruction *, Constant * > &Vals, const DataLayout &DL, const TargetLibraryInfo *TLI)
EvaluateExpression - Given an expression that passes the getConstantEvolvingPHI predicate,...
static const SCEV * getPreviousSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static const SCEV * MatchNotExpr(const SCEV *Expr)
If Expr computes ~A, return A else return nullptr.
static std::pair< ConstantRange, bool > getRangeForAffineARHelper(APInt Step, const ConstantRange &StartRange, const APInt &MaxBECount, bool Signed)
static cl::opt< unsigned > MaxValueCompareDepth("scalar-evolution-max-value-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive value complexity comparisons"), cl::init(2))
static const SCEV * applyDivisibilityOnMinMaxExpr(const SCEV *MinMaxExpr, APInt Divisor, ScalarEvolution &SE)
static cl::opt< bool, true > VerifySCEVOpt("verify-scev", cl::Hidden, cl::location(VerifySCEV), cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"))
static const SCEV * getSignedOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static cl::opt< unsigned > MaxArithDepth("scalar-evolution-max-arith-depth", cl::Hidden, cl::desc("Maximum depth of recursive arithmetics"), cl::init(32))
static bool HasSameValue(const SCEV *A, const SCEV *B)
SCEV structural equivalence is usually sufficient for testing whether two expressions are equal,...
static uint64_t Choose(uint64_t n, uint64_t k, bool &Overflow)
Compute the result of "n choose k", the binomial coefficient.
static std::optional< int > CompareSCEVComplexity(const LoopInfo *const LI, const SCEV *LHS, const SCEV *RHS, DominatorTree &DT, unsigned Depth=0)
static bool scevUnconditionallyPropagatesPoisonFromOperands(SCEVTypes Kind)
static cl::opt< bool > VerifySCEVStrict("verify-scev-strict", cl::Hidden, cl::desc("Enable stricter verification with -verify-scev is passed"))
static Constant * getOtherIncomingValue(PHINode *PN, BasicBlock *BB)
static 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.
Virtual Register Rewriter
static const uint32_t IV[8]
SCEVCastSinkingRewriter(ScalarEvolution &SE, Type *TargetTy, ConversionFn CreatePtrCast)
static const SCEV * rewrite(const SCEV *Scev, ScalarEvolution &SE, Type *TargetTy, ConversionFn CreatePtrCast)
const SCEV * visitUnknown(const SCEVUnknown *Expr)
const SCEV * visitAddExpr(const SCEVAddExpr *Expr)
const SCEV * visit(const SCEV *S)
Class for arbitrary precision integers.
LLVM_ABI APInt umul_ov(const APInt &RHS, bool &Overflow) const
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
uint64_t getZExtValue() const
Get zero extended value.
unsigned getActiveBits() const
Compute the number of active bits in the value.
LLVM_ABI APInt trunc(unsigned width) const
Truncate to new width.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
APInt abs() const
Get the absolute value.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool isSignMask() const
Check if the APInt's value is returned by getSignMask.
LLVM_ABI APInt urem(const APInt &RHS) const
Unsigned remainder operation.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
bool isNegative() const
Determine sign of this APInt.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
LLVM_ABI APInt uadd_ov(const APInt &RHS, bool &Overflow) const
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
bool isNonPositive() const
Determine if this APInt Value is non-positive (<= 0).
unsigned countTrailingZeros() const
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
unsigned logBase2() const
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
LLVM_ABI APInt multiplicativeInverse() const
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
LLVM_ABI APInt sext(unsigned width) const
Sign extend to a new width.
APInt shl(unsigned shiftAmt) const
Left-shift function.
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
bool isSignBitSet() const
Determine if sign bit of this APInt is set.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
This templated class represents "all analyses that operate over <aparticular IR unit>" (e....
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
AnalysisUsage & addRequiredTransitive()
Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
Get the array size.
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
MutableArrayRef< WeakVH > assumptions()
Access the list of assumption handles currently tracked for this function.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
LLVM_ABI unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
LLVM_ABI Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
BinaryOps getOpcode() const
This class represents a function call, abstracting a target machine's calling convention.
virtual void deleted()
Callback for Value destruction.
This is the base class for all instructions that perform data casts.
This class is the base class for the comparison instructions.
bool isFalseWhenEqual() const
This is just a convenience.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ ICMP_UGE
unsigned greater or equal
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
@ ICMP_SGE
signed greater or equal
@ ICMP_ULE
unsigned less or equal
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
bool isTrueWhenEqual() const
This is just a convenience.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
static LLVM_ABI std::optional< CmpPredicate > getMatching(CmpPredicate A, CmpPredicate B)
Compares two CmpPredicates taking samesign into account and returns the canonicalized CmpPredicate if...
LLVM_ABI CmpInst::Predicate getPreferredSignedPredicate() const
Attempts to return a signed CmpInst::Predicate from the CmpPredicate.
CmpInst::Predicate dropSameSign() const
Drops samesign information.
Conditional Branch instruction.
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
static LLVM_ABI Constant * getNot(Constant *C)
static Constant * getPtrAdd(Constant *Ptr, Constant *Offset, GEPNoWrapFlags NW=GEPNoWrapFlags::none(), std::optional< ConstantRange > InRange=std::nullopt, Type *OnlyIfReduced=nullptr)
Create a getelementptr i8, ptr, offset constant expression.
static LLVM_ABI Constant * getPtrToAddr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static LLVM_ABI Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
static LLVM_ABI Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
This is the shared class of boolean and integer constants.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
static LLVM_ABI ConstantInt * getBool(LLVMContext &Context, bool V)
This class represents a range of values.
LLVM_ABI ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
LLVM_ABI ConstantRange zextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
PreferredRangeType
If represented precisely, the result of some range operations may consist of multiple disjoint ranges...
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI ConstantRange urem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned remainder operation of...
LLVM_ABI bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
LLVM_ABI bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other?
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI ConstantRange zeroExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
LLVM_ABI bool isSignWrappedSet() const
Return true if this set wraps around the signed domain.
LLVM_ABI APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
LLVM_ABI bool isWrappedSet() const
Return true if this set wraps around the unsigned domain.
LLVM_ABI void print(raw_ostream &OS) const
Print out the bounds to a stream.
LLVM_ABI ConstantRange truncate(uint32_t BitWidth, unsigned NoWrapKind=0) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
LLVM_ABI ConstantRange signExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI bool contains(const APInt &Val) const
Return true if the specified value is in the set.
LLVM_ABI ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
LLVM_ABI APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
static LLVM_ABI ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
LLVM_ABI unsigned getMinSignedBits() const
Compute the maximal number of bits needed to represent every value in this signed range.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
LLVM_ABI ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
LLVM_ABI ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
static LLVM_ABI ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)
Produce the range that contains X if and only if "X BinOp Other" does not wrap.
This is an important base class in LLVM.
A parsed version of the target data layout string in and methods for querying it.
LLVM_ABI const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
LLVM_ABI unsigned getIndexTypeSizeInBits(Type *Ty) const
The size in bits of the index used in GEP calculation for this type.
LLVM_ABI IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
TypeSize getTypeSizeInBits(Type *Ty) const
Size examples:
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)
Analysis pass which computes a DominatorTree.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Insertion token: a failed lookup fills it in, the matching insert consumes it.
This class describes a reference to an interned FoldingSetNodeID, which can be a useful to store node...
This class is used to gather all the unique data bits of a node.
void AddInteger(signed I)
This class represents a freeze function that returns random concrete value if an operand is either a ...
Represents flags for the getelementptr instruction/expression.
bool hasNoUnsignedSignedWrap() const
bool hasNoUnsignedWrap() const
static GEPNoWrapFlags none()
static LLVM_ABI Type * getTypeAtIndex(Type *Ty, Value *Idx)
Return the type of the element at the given index of an indexable type.
Module * getParent()
Get the module that this global value is contained inside of...
static bool isPrivateLinkage(LinkageTypes Linkage)
static bool isInternalLinkage(LinkageTypes Linkage)
This instruction compares its operands according to the predicate given to the constructor.
CmpPredicate getCmpPredicate() const
static bool isGE(Predicate P)
Return true if the predicate is SGE or UGE.
CmpPredicate getSwappedCmpPredicate() const
static LLVM_ABI bool compare(const APInt &LHS, const APInt &RHS, ICmpInst::Predicate Pred)
Return result of LHS Pred RHS comparison.
static bool isLT(Predicate P)
Return true if the predicate is SLT or ULT.
CmpPredicate getInverseCmpPredicate() const
Predicate getNonStrictCmpPredicate() const
For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.
static bool isGT(Predicate P)
Return true if the predicate is SGT or UGT.
Predicate getFlippedSignednessPredicate() const
For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->EQ.
static CmpPredicate getInverseCmpPredicate(CmpPredicate Pred)
bool isEquality() const
Return true if this predicate is either EQ or NE.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
static bool isLE(Predicate P)
Return true if the predicate is SLE or ULE.
This instruction inserts a single (scalar) element into a VectorType value.
This instruction inserts a struct field of array element value into an aggregate value.
LLVM_ABI bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
LLVM_ABI bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
LLVM_ABI bool isIdenticalToWhenDefined(const Instruction *I, bool IntersectAttrs=false) const LLVM_READONLY
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...
Class to represent integer types.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
A helper class to return the specified delimiter string after the first invocation of operator String...
An instruction for reading from memory.
Analysis pass that exposes the LoopInfo for a function.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within this loop.
BlockT * getHeader() const
unsigned getLoopDepth() const
Return the nesting level of this loop.
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
A Module instance is used to store all the information related to an LLVM module.
unsigned getOpcode() const
Return the opcode for this Instruction or ConstantExpr.
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
bool hasNoSignedWrap() const
Test whether this operation is known to never undergo signed overflow, aka the nsw property.
bool hasNoUnsignedWrap() const
Test whether this operation is known to never undergo unsigned overflow, aka the nuw property.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
PointerIntPair - This class implements a pair of a pointer and small integer.
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
LLVM_ABI void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
LLVM_ABI const SCEVPredicate & getPredicate() const
LLVM_ABI const SCEV * getPredicatedSCEV(const SCEV *Expr)
Returns the rewritten SCEV for Expr in the context of the current SCEV predicate.
LLVM_ABI bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2, ArrayRef< const SCEVPredicate * > ExtraPreds={}) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds and ExtraPreds.
LLVM_ABI 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...
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 * 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()
static LLVM_ABI LoopGuards collect(const Loop *L, ScalarEvolution &SE)
Collect rewrite map for loop guards for loop L, together with flags indicating if NUW and NSW can be ...
LLVM_ABI const SCEV * rewrite(const SCEV *Expr) const
Try to apply the collected loop guards to Expr.
The main scalar evolution driver.
LLVM_ABI const SCEV * getUDivExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
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.
friend class SCEVCallbackVH
LLVM_ABI bool isKnownToBeAPowerOfTwo(const SCEV *S, bool OrZero=false, bool OrNegative=false)
Test if the given expression is known to be a power of 2.
LLVM_ABI 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.
void stable_sort(R &&Range)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
SaveAndRestore(T &) -> SaveAndRestore< T >
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)
LLVM_ABI bool canCreatePoison(const Operator *Op, bool ConsiderFlagsAndMetadata=true)
LLVM_ABI bool mustTriggerUB(const Instruction *I, const SmallPtrSetImpl< const Value * > &KnownPoison)
Return true if the given instruction must trigger undefined behavior when I is executed with any oper...
RelativeUniformCounterPtr Values
@ Known
Known to have no common set bits.
InterleavedRange< Range > interleaved(const Range &R, StringRef Separator=", ", StringRef Prefix="", StringRef Suffix="")
Output range R as a sequence of interleaved elements.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
auto successors(const MachineBasicBlock *BB)
scope_exit(Callable) -> scope_exit< Callable >
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.
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.
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.
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.
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