83#include "llvm/Config/llvm-config.h"
138#define DEBUG_TYPE "scalar-evolution"
141 "Number of loop exits with predictable exit counts");
143 "Number of loop exits without predictable exit counts");
145 "Number of loops with trip counts computed by force");
147#ifdef EXPENSIVE_CHECKS
155 cl::desc(
"Maximum number of iterations SCEV will "
156 "symbolically execute a constant "
162 cl::desc(
"Verify ScalarEvolution's backedge taken counts (slow)"));
165 cl::desc(
"Enable stricter verification with -verify-scev is passed"));
169 cl::desc(
"Verify IR correctness when making sensitive SCEV queries (slow)"),
174 cl::desc(
"Threshold for inlining multiplication operands into a SCEV"),
179 cl::desc(
"Threshold for inlining addition operands into a SCEV"),
183 "scalar-evolution-max-scev-compare-depth",
cl::Hidden,
184 cl::desc(
"Maximum depth of recursive SCEV complexity comparisons"),
188 "scalar-evolution-max-scev-operations-implication-depth",
cl::Hidden,
189 cl::desc(
"Maximum depth of recursive SCEV operations implication analysis"),
193 "scalar-evolution-max-value-compare-depth",
cl::Hidden,
194 cl::desc(
"Maximum depth of recursive value complexity comparisons"),
199 cl::desc(
"Maximum depth of recursive arithmetics"),
203 "scalar-evolution-max-constant-evolving-depth",
cl::Hidden,
208 cl::desc(
"Maximum depth of recursive SExt/ZExt/Trunc"),
213 cl::desc(
"Max coefficients in AddRec during evolving"),
218 cl::desc(
"Size of the expression which is considered huge"),
223 cl::desc(
"Threshold for switching to iteratively computing SCEV ranges"),
227 "scalar-evolution-max-loop-guard-collection-depth",
cl::Hidden,
228 cl::desc(
"Maximum depth for recursive loop guard collection"),
cl::init(1));
233 cl::desc(
"When printing analysis, include information on every instruction"));
236 "scalar-evolution-use-expensive-range-sharpening",
cl::Hidden,
238 cl::desc(
"Use more powerful methods of sharpening expression ranges. May "
239 "be costly in terms of compile time"));
243 cl::desc(
"Handle <= and >= in finite loops"),
247 "scalar-evolution-use-context-for-no-wrap-flag-strenghening",
cl::Hidden,
248 cl::desc(
"Infer nuw/nsw flags using context where suitable"),
290#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
308 OS <<
"(ptrtoaddr " << *
Op->getType() <<
" " <<
Op <<
" to "
315 OS <<
"(trunc " << *
Op->getType() <<
" " <<
Op <<
" to "
322 OS <<
"(zext " << *
Op->getType() <<
" " <<
Op <<
" to " << *ZExt->
getType()
329 OS <<
"(sext " << *
Op->getType() <<
" " <<
Op <<
" to " << *SExt->
getType()
358 const char *OpStr =
nullptr;
371 OpStr =
" umin_seq ";
393 OS <<
"(" << UDiv->
getLHS() <<
" /u " << UDiv->
getRHS() <<
")";
400 OS <<
"***COULDNOTCOMPUTE***";
442 if (!
Mul)
return false;
446 if (!SC)
return false;
460 auto &Entry = ConstantSCEVs[V];
469 static_cast<SCEVConstant *
>(UniqueSCEVs.lookup(ID, Token)))
472 new (SCEVAllocator)
SCEVConstant(ID.Intern(SCEVAllocator), V);
473 UniqueSCEVs.insert(S, Token);
488 ConstantInt::get(ITy, V,
isSigned,
true));
496 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
498 SCEV *S =
new (SCEVAllocator)
SCEVVScale(ID.Intern(SCEVAllocator), Ty);
499 UniqueSCEVs.insert(S, Token);
520 "Must be a non-bit-width-changing pointer-to-integer cast!");
532 "Cannot truncate non-integer value!");
539 "Cannot zero extend non-integer value!");
546 "Cannot sign extend non-integer value!");
551 SE->forgetMemoizedResults({
this});
554 SE->UniqueSCEVs.erase(
this);
560void SCEVUnknown::allUsesReplacedWith(
Value *New) {
562 SE->forgetMemoizedResults({
this});
565 SE->UniqueSCEVs.erase(
this);
587 if (LIsPointer != RIsPointer)
588 return (
int)LIsPointer - (int)RIsPointer;
593 return (
int)LID - (int)RID;
598 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
599 return (
int)LArgNo - (int)RArgNo;
605 if (
auto L = LGV->getLinkage() - RGV->getLinkage())
608 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
609 auto LT = GV->getLinkage();
616 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
617 return LGV->getName().compare(RGV->getName());
628 if (LParent != RParent) {
631 if (LDepth != RDepth)
632 return (
int)LDepth - (int)RDepth;
636 unsigned LNumOps = LInst->getNumOperands(),
637 RNumOps = RInst->getNumOperands();
638 if (LNumOps != RNumOps)
639 return (
int)LNumOps - (int)RNumOps;
641 for (
unsigned Idx :
seq(LNumOps)) {
643 RInst->getOperand(Idx),
Depth + 1);
657static std::optional<int>
667 return (
int)LType - (int)RType;
692 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
693 if (LBitWidth != RBitWidth)
694 return (
int)LBitWidth - (int)RBitWidth;
695 return LA.
ult(
RA) ? -1 : 1;
701 return LTy->getBitWidth() - RTy->getBitWidth();
712 if (LLoop != RLoop) {
714 assert(LHead != RHead &&
"Two loops share the same header?");
718 "No dominance between recurrences used by one SCEV?");
741 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
742 if (LNumOps != RNumOps)
743 return (
int)LNumOps - (int)RNumOps;
745 for (
unsigned i = 0; i != LNumOps; ++i) {
771 if (
Ops.size() < 2)
return;
776 return Complexity && *Complexity < 0;
778 if (
Ops.size() == 2) {
782 if (IsLessComplex(
RHS,
LHS))
795 for (
unsigned i = 0, e =
Ops.size(); i != e-2; ++i) {
801 for (
unsigned j = i+1; j != e &&
Ops[j]->getSCEVType() == Complexity; ++j) {
806 if (i == e-2)
return;
828template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
832 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
834 for (
unsigned Idx = 0; Idx <
Ops.size();) {
842 Ops.erase(
Ops.begin() + Idx);
849 assert(Folded &&
"Must have folded value");
853 if (Folded && IsAbsorber(Folded->
getAPInt()))
857 if (Folded && !IsIdentity(Folded->
getAPInt()))
858 Ops.insert(
Ops.begin(), Folded);
860 return Ops.size() == 1 ?
Ops[0] :
nullptr;
935 APInt OddFactorial(W, 1);
937 for (
unsigned i = 3; i <= K; ++i) {
940 OddFactorial *= (i >> TwoFactors);
944 unsigned CalculationBits = W +
T;
958 for (
unsigned i = 1; i != K; ++i) {
983template <
typename ExprT>
990 return {Res, UseFlags};
1012 "use-specific flags only supported for affine AddRecs");
1014 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1024 Result,
Mul, UseFlags);
1055 ConversionFn CreatePtrCast;
1059 ConversionFn CreatePtrCast)
1060 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
1063 Type *TargetTy, ConversionFn CreatePtrCast) {
1065 return Rewriter.visit(Scev);
1091 "Should only reach pointer-typed SCEVUnknown's.");
1096 return SE.getZero(TargetTy);
1097 return CreatePtrCast(Expr);
1102 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1106 if (DL.hasUnstableRepresentation(
Op->getType()))
1109 Type *Ty = DL.getAddressType(
Op->getType());
1120 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1122 SCEV *S =
new (SCEVAllocator)
1124 UniqueSCEVs.insert(S, Token);
1127 return static_cast<const SCEV *
>(S);
1130 "We must have succeeded in sinking the cast, "
1131 "and ending up with an integer-typed expression!");
1138 "This is not a truncating conversion!");
1140 "This is not a conversion to a SCEVable type!");
1141 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1146 ID.AddPointer(
Op.getOpaqueValue());
1149 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1172 UniqueSCEVs.insert(S, Token);
1185 unsigned numTruncs = 0;
1186 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1194 if (numTruncs < 2) {
1204 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1211 for (
const SCEV *
Op : AddRec->operands())
1226 UniqueSCEVs.insert(S, Token);
1267struct ExtendOpTraitsBase {
1268 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
SCEVUse,
Type *,
1273template <
typename ExtendOp>
struct ExtendOpTraits {
1289 static const GetExtendExprTy GetExtendExpr;
1291 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1292 ICmpInst::Predicate *Pred,
1293 ScalarEvolution *SE) {
1298const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1305 static const GetExtendExprTy GetExtendExpr;
1307 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1308 ICmpInst::Predicate *Pred,
1309 ScalarEvolution *SE) {
1314const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1326template <
typename ExtendOpTy>
1329 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1330 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1346 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1359 auto PreStartFlags =
1377 const SCEV *OperandExtendedStart =
1379 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1380 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1392 const SCEV *OverflowLimit =
1393 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1395 if (OverflowLimit &&
1403template <
typename ExtendOpTy>
1407 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1415 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1450template <
typename ExtendOpTy>
1451bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1454 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1464 APInt StartAI = StartC->
getAPInt();
1466 for (
unsigned Delta : {-2, -1, 1, 2}) {
1467 const SCEV *PreStart =
getConstant(StartAI - Delta);
1469 FoldingSetNodeID
ID;
1471 ID.AddPointer(PreStart);
1472 ID.AddPointer(Step);
1474 FoldingSetInsertToken Token;
1476 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.lookup(ID, Token));
1480 if (PreAR &&
any(PreAR->getNoWrapFlags(WrapType))) {
1483 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1484 DeltaS, &Pred,
this);
1502 const unsigned BitWidth =
C.getBitWidth();
1520 const APInt &ConstantStart,
1535 auto I = FoldCache.
insert({ID, S});
1539 auto &UserIDs = FoldCacheUser[
I.first->second];
1540 assert(
count(UserIDs, ID) == 1 &&
"unexpected duplicates in UserIDs");
1541 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1542 if (UserIDs[
I] == ID) {
1547 I.first->second = S;
1549 FoldCacheUser[S].push_back(ID);
1555 "This is not an extending conversion!");
1557 "This is not a conversion to a SCEVable type!");
1558 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1562 if (
const SCEV *S = FoldCache.lookup(ID))
1574 "This is not an extending conversion!");
1576 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1588 const SCEV *Start, *Step;
1593 if (AR->hasNoUnsignedWrap()) {
1604 ID.AddPointer(
Op.getOpaqueValue());
1607 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1612 UniqueSCEVs.insert(S, Token);
1622 const SCEV *
X = ST->getOperand();
1655 const SCEV *CastedMaxBECount =
1659 if (MaxBECount == RecastedMaxBECount) {
1668 const SCEV *WideMaxBECount =
1670 const SCEV *OperandExtendedAdd =
1676 if (ZAdd == OperandExtendedAdd) {
1687 OperandExtendedAdd =
1693 if (ZAdd == OperandExtendedAdd) {
1714 !AC.assumptions().empty()) {
1716 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1718 if (AR->hasNoUnsignedWrap()) {
1753 const APInt &
C = SC->getAPInt();
1757 const SCEV *SResidual =
1765 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1789 if (SA->hasNoUnsignedWrap()) {
1802 if (SA->hasNoSignedWrap() &&
1805 C->isNegative() && !
C->isMinSignedValue() && C2->
sge(
C->abs())) {
1824 const SCEV *SResidual =
1835 if (SM->hasNoUnsignedWrap()) {
1857 const SCEV *TruncRHS;
1894 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1898 UniqueSCEVs.insert(S, Token);
1907 "This is not an extending conversion!");
1909 "This is not a conversion to a SCEVable type!");
1910 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1914 if (
const SCEV *S = FoldCache.lookup(ID))
1926 "This is not an extending conversion!");
1928 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1945 const SCEV *Start, *Step;
1950 if (AR->hasNoSignedWrap()) {
1961 ID.AddPointer(
Op.getOpaqueValue());
1964 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1970 UniqueSCEVs.insert(S, Token);
1980 const SCEV *
X = ST->getOperand();
1991 if (SA->hasNoSignedWrap()) {
2013 const SCEV *SResidual =
2046 const SCEV *CastedMaxBECount =
2050 if (MaxBECount == RecastedMaxBECount) {
2059 const SCEV *WideMaxBECount =
2061 const SCEV *OperandExtendedAdd =
2067 if (SAdd == OperandExtendedAdd) {
2078 OperandExtendedAdd =
2084 if (SAdd == OperandExtendedAdd) {
2104 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2106 if (AR->hasNoSignedWrap()) {
2120 const APInt &
C = SC->getAPInt();
2124 const SCEV *SResidual =
2132 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2159 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
2163 UniqueSCEVs.insert(S, Token);
2179 assert(Expr->
getType() == Ty &&
"requested type must match");
2191 "This is not an extending conversion!");
2193 "This is not a conversion to a SCEVable type!");
2198 if (SC->getAPInt().isNegative())
2203 const SCEV *NewOp =
T->getOperand();
2222 for (
const SCEV *
Op : AR->operands())
2260 APInt &AccumulatedConstant,
2264 bool Interesting =
false;
2271 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2273 AccumulatedConstant += Scale *
C->getAPInt();
2278 for (; i !=
Ops.size(); ++i) {
2287 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2293 auto Pair = M.insert({
Key, NewScale});
2297 Pair.first->second += NewScale;
2305 auto Pair = M.insert({
Ops[i], Scale});
2309 Pair.first->second += Scale;
2328 case Instruction::Add:
2331 case Instruction::Sub:
2334 case Instruction::Mul:
2348 const SCEV *
A = (this->*Extension)(
2350 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2351 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2359 if (BinOp == Instruction::Mul)
2365 APInt C = RHSC->getAPInt();
2366 unsigned NumBits =
C.getBitWidth();
2367 bool IsSub = (BinOp == Instruction::Sub);
2368 bool IsNegativeConst = (
Signed &&
C.isNegative());
2370 bool OverflowDown = IsSub ^ IsNegativeConst;
2372 if (IsNegativeConst) {
2385 APInt Limit = Min + Magnitude;
2391 APInt Limit = Max - Magnitude;
2396std::optional<SCEV::NoWrapFlags>
2401 return std::nullopt;
2410 bool Deduced =
false;
2416 bool CanUseNSW =
true;
2417 const APInt *ShiftAmt;
2422 return std::nullopt;
2426 Opcode = Instruction::Mul;
2428 }
else if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
2429 Opcode != Instruction::Mul) {
2430 return std::nullopt;
2449 return std::nullopt;
2459 using namespace std::placeholders;
2466 assert(CanAnalyze &&
"don't call from other places!");
2473 auto IsKnownNonNegative = [&](
SCEVUse U) {
2482 if (SignOrUnsignWrap != SignOrUnsignMask &&
2489 return Instruction::Add;
2491 return Instruction::Mul;
2502 Opcode,
C, OBO::NoSignedWrap);
2510 Opcode,
C, OBO::NoUnsignedWrap);
2520 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2527 if (UDiv->getOperand(1) ==
Ops[1])
2530 if (UDiv->getOperand(1) ==
Ops[0])
2546 "only nuw or nsw allowed");
2547 assert(!
Ops.empty() &&
"Cannot get empty add!");
2548 if (
Ops.size() == 1)
return Ops[0];
2551 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2553 "SCEVAddExpr operand types don't match!");
2555 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2556 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2561 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2562 [](
const APInt &
C) {
return C.isZero(); },
2563 [](
const APInt &
C) {
return false; });
2576 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2581 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2582 Add->setNoWrapFlags(ComputeFlags(
Ops));
2590 bool FoundMatch =
false;
2591 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2592 if (
Ops[i] ==
Ops[i+1]) {
2604 --i; e -=
Count - 1;
2614 auto FindTruncSrcType = [&]() ->
Type * {
2620 return T->getOperand()->getType();
2622 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2624 return T->getOperand()->getType();
2628 if (
auto *SrcType = FindTruncSrcType()) {
2635 if (
T->getOperand()->getType() != SrcType) {
2644 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2647 if (
T->getOperand()->getType() != SrcType) {
2675 if (
Ops.size() == 2) {
2685 auto C2 =
C->getAPInt();
2688 APInt ConstAdd = C1 + C2;
2689 auto AddFlags = AddExpr->getNoWrapFlags();
2730 if (
Ops.size() == 2 &&
2741 if (Idx <
Ops.size()) {
2742 bool DeletedAdd =
false;
2753 Ops.erase(
Ops.begin()+Idx);
2756 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2779 struct APIntCompare {
2780 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2781 return LHS.ult(RHS);
2788 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2789 for (
const SCEV *NewOp : NewOps)
2790 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2793 if (AccumulatedConstant != 0)
2795 for (
auto &MulOp : MulOpLists) {
2796 if (MulOp.first == 1) {
2798 }
else if (MulOp.first != 0) {
2807 if (
Ops.size() == 1)
2816 if (M->getNumOperands() == 2)
2817 return M->getOperand(OpIdx == 0);
2819 append_range(Remaining, M->operands().drop_front(OpIdx + 1));
2828 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2832 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2840 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp) {
2841 if (MulOpSCEV ==
Ops[AddOp]) {
2852 for (
unsigned OMulOp = 0, OE = OtherMul->
getNumOperands(); OMulOp != OE;
2854 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2856 Cofactors.
push_back(StripFactor(OtherMul, OMulOp));
2865 if (!Cofactors.
empty()) {
2873 if (
Ops.size() == DeadIndices.
size() + 1)
2880 Ops.erase(
Ops.begin() + Idx);
2884 Ops.push_back(OuterMul);
2903 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2906 Ops.erase(
Ops.begin()+i);
2911 if (!LIOps.
empty()) {
2936 auto *DefI = getDefiningScopeBound(LIOps);
2938 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2950 if (
Ops.size() == 1)
return NewRec;
2953 for (
unsigned i = 0;; ++i)
2954 if (
Ops[i] == AddRec) {
2964 for (
unsigned OtherIdx = Idx+1;
2972 "AddRecExprs are not sorted in reverse dominance order?");
2979 if (OtherAddRec->getLoop() == AddRecLoop) {
2980 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2982 if (i >= AddRecOps.
size()) {
2983 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2987 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
2990 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3005 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
3013 ID.AddPointer(
Op.getOpaqueValue());
3019 S =
new (SCEVAllocator)
3021 UniqueSCEVs.insert(S, Token);
3032 FoldingSetNodeID
ID;
3035 ID.AddPointer(
Op.getOpaqueValue());
3037 FoldingSetInsertToken Token;
3039 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.lookup(ID, Token));
3043 S =
new (SCEVAllocator)
3044 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3045 UniqueSCEVs.insert(S, Token);
3047 LoopUsers[
L].push_back(S);
3056 FoldingSetNodeID
ID;
3059 ID.AddPointer(
Op.getOpaqueValue());
3060 FoldingSetInsertToken Token;
3061 SCEVMulExpr *S =
static_cast<SCEVMulExpr *
>(UniqueSCEVs.lookup(ID, Token));
3065 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3067 UniqueSCEVs.insert(S, Token);
3076 FoldingSetNodeID
ID;
3078 ID.AddPointer(
LHS.getOpaqueValue());
3079 ID.AddPointer(
RHS.getOpaqueValue());
3080 FoldingSetInsertToken Token;
3081 SCEV *S = UniqueSCEVs.lookup(ID, Token);
3083 S =
new (SCEVAllocator) SCEVUDivExpr(
ID.Intern(SCEVAllocator),
LHS,
RHS);
3084 UniqueSCEVs.insert(S, Token);
3093 if (j > 1 && k / j != i) Overflow =
true;
3109 if (n == 0 || n == k)
return 1;
3110 if (k > n)
return 0;
3116 for (
uint64_t i = 1; i <= k; ++i) {
3117 r =
umul_ov(r, n-(i-1), Overflow);
3126 struct FindConstantInAddMulChain {
3127 bool FoundConstant =
false;
3129 bool follow(
const SCEV *S) {
3134 bool isDone()
const {
3135 return FoundConstant;
3139 FindConstantInAddMulChain
F;
3141 ST.visitAll(StartExpr);
3142 return F.FoundConstant;
3150 "only nuw or nsw allowed");
3151 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3152 if (
Ops.size() == 1)
return Ops[0];
3154 Type *ETy =
Ops[0]->getType();
3156 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3158 "SCEVMulExpr operand types don't match!");
3163 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3164 [](
const APInt &
C) {
return C.isOne(); },
3165 [](
const APInt &
C) {
return C.isZero(); });
3176 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3181 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3182 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3187 if (
Ops.size() == 2) {
3195 const SCEV *Op0, *Op1;
3203 if (
Ops[0]->isAllOnesValue()) {
3208 bool AnyFolded =
false;
3209 for (
const SCEV *AddOp :
Add->operands()) {
3229 if (AddRec->hasNoSignedWrap()) {
3236 AddRec->getNoWrapFlags(FlagsMask));
3259 APInt C1V = LHSC->getAPInt();
3269 const SCEV *NewMul =
nullptr;
3273 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3288 if (Idx <
Ops.size()) {
3289 bool DeletedMul =
false;
3295 Ops.erase(
Ops.begin()+Idx);
3319 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3322 Ops.erase(
Ops.begin()+i);
3327 if (!LIOps.
empty()) {
3340 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3356 if (
Ops.size() == 1)
return NewRec;
3359 for (
unsigned i = 0;; ++i)
3360 if (
Ops[i] == AddRec) {
3381 bool OpsModified =
false;
3382 for (
unsigned OtherIdx = Idx+1;
3396 bool Overflow =
false;
3403 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3404 uint64_t Coeff1 =
Choose(x, 2*x - y, Overflow);
3407 z < ze && !Overflow; ++z) {
3408 uint64_t Coeff2 =
Choose(2*x - y, x-z, Overflow);
3410 if (LargerThan64Bits)
3411 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3413 Coeff = Coeff1*Coeff2;
3428 if (
Ops.size() == 2)
return NewAddRec;
3429 Ops[Idx] = NewAddRec;
3430 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3446 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3453 "SCEVURemExpr operand types don't match!");
3458 if (RHSC->getValue()->isOne())
3459 return getZero(LHS->getType());
3462 if (RHSC->getAPInt().isPowerOf2()) {
3463 Type *FullTy = LHS->getType();
3479 assert(!LHS->getType()->isPointerTy() &&
3480 "SCEVUDivExpr operand can't be pointer!");
3481 assert(LHS->getType() == RHS->getType() &&
3482 "SCEVUDivExpr operand types don't match!");
3493 if (RHSC->getValue()->isOne())
3498 if (!RHSC->getValue()->isZero()) {
3502 Type *Ty = LHS->getType();
3503 unsigned LZ = RHSC->getAPInt().countl_zero();
3507 if (!RHSC->getAPInt().isPowerOf2())
3515 const APInt &StepInt = Step->getAPInt();
3516 const APInt &DivInt = RHSC->getAPInt();
3517 if (!StepInt.
urem(DivInt) &&
3523 for (
const SCEV *
Op : AR->operands())
3529 const APInt *StartRem;
3542 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3546 const SCEV *NewStart =
3548 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3550 const SCEV *NewLHS =
3560 if (M->hasNoUnsignedWrap()) {
3562 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3563 const SCEV *
Op = M->getOperand(i);
3590 if (
auto *DivisorConstant =
3592 bool Overflow =
false;
3594 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3605 if (
A->hasNoUnsignedWrap()) {
3607 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3614 if (
Operands.size() ==
A->getNumOperands())
3626 const APInt &
N = RHSC->getAPInt();
3627 const APInt *NMinusM, *M;
3631 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3632 *NMinusM ==
N - *M) {
3641 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3651 return getZero(LHS->getType());
3655 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3656 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3657 if (
Mul->getOperand(i) == RHS) {
3668 const SCEV *NewLHS, *NewRHS;
3673 return getOrCreateUDivExpr(LHS, RHS);
3693 if (StepChrec->getLoop() == L) {
3712 "SCEVAddRecExpr operand types don't match!");
3713 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3717 "SCEVAddRecExpr operand is not available at loop entry!");
3735 const Loop *NestedLoop = NestedAR->getLoop();
3736 if (L->contains(NestedLoop)
3739 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3741 Operands[0] = NestedAR->getStart();
3745 bool AllInvariant =
all_of(
3757 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3768 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3778 return getOrCreateAddRecExpr(
Operands, L, Flags);
3794 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3798 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3812 bool FirstIter =
true;
3814 for (
SCEVUse IndexExpr : IndexExprs) {
3821 Offsets.push_back(FieldOffset);
3824 CurTy = STy->getTypeAtIndex(Index);
3829 "The first index of a GEP indexes a pointer");
3830 CurTy = SrcElementTy;
3841 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3842 Offsets.push_back(LocalOffset);
3847 if (Offsets.empty())
3860 "GEP should not change type mid-flight.");
3864SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3869 ID.AddPointer(
Op.getOpaqueValue());
3871 return UniqueSCEVs.lookup(ID, Token);
3881 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3882 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3883 if (
Ops.size() == 1)
return Ops[0];
3886 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3888 "Operand types don't match!");
3891 "min/max should be consistently pointerish");
3917 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3919 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3924 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3926 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3932 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3938 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3943 if (Idx <
Ops.size()) {
3944 bool DeletedAny =
false;
3945 while (
Ops[Idx]->getSCEVType() == Kind) {
3947 Ops.erase(
Ops.begin()+Idx);
3965 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3966 if (
Ops[i] ==
Ops[i + 1] ||
3967 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3970 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3973 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3976 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3982 if (
Ops.size() == 1)
return Ops[0];
3984 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
3991 ID.AddPointer(
Op.getOpaqueValue());
3993 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
3995 return ExistingSCEV;
3998 SCEV *S =
new (SCEVAllocator)
4001 UniqueSCEVs.insert(S, Token);
4009class SCEVSequentialMinMaxDeduplicatingVisitor final
4010 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4011 std::optional<const SCEV *>> {
4012 using RetVal = std::optional<const SCEV *>;
4019 bool canRecurseInto(
SCEVTypes Kind)
const {
4022 return RootKind == Kind || NonSequentialRootKind == Kind;
4027 if (!SeenOps.
insert(S).second)
4028 return std::nullopt;
4032 if (!canRecurseInto(Kind))
4042 return std::nullopt;
4052 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4054 : SE(SE), RootKind(RootKind),
4055 NonSequentialRootKind(
4056 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4060 SmallVectorImpl<SCEVUse> &NewOps) {
4065 for (
const SCEV *
Op : OrigOps) {
4070 Ops.emplace_back(*NewOp);
4074 NewOps = std::move(
Ops);
4118struct SCEVPoisonCollector {
4119 bool LookThroughMaybePoisonBlocking;
4120 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4121 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4122 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4124 bool follow(
const SCEV *S) {
4125 if (!LookThroughMaybePoisonBlocking &&
4135 bool isDone()
const {
return false; }
4145 SCEVPoisonCollector PC1(
true);
4150 if (PC1.MaybePoison.
empty())
4156 SCEVPoisonCollector PC2(
false);
4166 SCEVPoisonCollector PC(
false);
4189 while (!Worklist.
empty()) {
4191 if (!Visited.
insert(V).second)
4195 if (Visited.
size() > 16)
4211 if (PDI->isDisjoint())
4218 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4225 if (
I->hasPoisonGeneratingAnnotations())
4236 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4237 "Not a SCEVSequentialMinMaxExpr!");
4238 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4239 if (
Ops.size() == 1)
4243 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4245 "Operand types don't match!");
4248 "min/max should be consistently pointerish");
4256 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4263 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4273 bool DeletedAny =
false;
4274 while (Idx <
Ops.size()) {
4275 if (
Ops[Idx]->getSCEVType() != Kind) {
4280 Ops.erase(
Ops.begin() + Idx);
4281 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4282 SMME->operands().end());
4290 const SCEV *SaturationPoint;
4301 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4302 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4314 Ops.erase(
Ops.begin() + i);
4319 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4320 Ops.erase(
Ops.begin() + i);
4330 ID.AddPointer(
Op.getOpaqueValue());
4332 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
4334 return ExistingSCEV;
4338 SCEV *S =
new (SCEVAllocator)
4341 UniqueSCEVs.insert(S, Token);
4389 if (
Size.isScalable())
4410 "Cannot get offset for structure containing scalable vector types");
4424 if (
SCEV *S = UniqueSCEVs.lookup(ID, Token)) {
4426 "Stale SCEVUnknown in uniquing map!");
4429 SCEV *S =
new (SCEVAllocator)
SCEVUnknown(ID.Intern(SCEVAllocator), V,
this,
4432 UniqueSCEVs.insert(S, Token);
4447 return Ty->isIntOrPtrTy();
4454 if (Ty->isPointerTy())
4465 if (Ty->isIntegerTy())
4469 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4481 bool PreciseA, PreciseB;
4482 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4483 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4484 if (!PreciseA || !PreciseB)
4487 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4488 DT.dominates(ScopeB, ScopeA);
4492 return CouldNotCompute.get();
4495bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4498 return SU && SU->getValue() ==
nullptr;
4501 return !ContainsNulls;
4506 if (
I != HasRecMap.end())
4511 HasRecMap.insert({S, FoundAddRec});
4519 if (
SI == ExprValueMap.
end())
4521 return SI->second.getArrayRef();
4527void ScalarEvolution::eraseValueFromMap(
Value *V) {
4529 if (
I != ValueExprMap.end()) {
4530 auto EVIt = ExprValueMap.find(
I->second);
4531 bool Removed = EVIt->second.remove(V);
4533 assert(Removed &&
"Value not in ExprValueMap?");
4534 ValueExprMap.erase(
I);
4538void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4542 auto It = ValueExprMap.find_as(V);
4543 if (It == ValueExprMap.end()) {
4545 ExprValueMap[S].insert(V);
4556 return createSCEVIter(V);
4563 if (
I != ValueExprMap.end()) {
4564 const SCEV *S =
I->second;
4565 assert(checkValidity(S) &&
4566 "existing SCEV has not been properly invalidated");
4579 Type *Ty = V->getType();
4595 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4608 return (
const SCEV *)
nullptr;
4614 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4618 Type *Ty = V->getType();
4624 assert(
P->getType()->isPointerTy());
4639 if (AddOp->getType()->isPointerTy()) {
4640 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4658 return getZero(LHS->getType());
4663 if (RHS->getType()->isPointerTy()) {
4664 if (!LHS->getType()->isPointerTy() ||
4674 const bool RHSIsNotMinSigned =
4705 Type *SrcTy = V->getType();
4706 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4707 "Cannot truncate or zero extend with non-integer arguments!");
4717 Type *SrcTy = V->getType();
4718 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4719 "Cannot truncate or zero extend with non-integer arguments!");
4728 Type *SrcTy = V->getType();
4729 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4730 "Cannot noop or zero extend with non-integer arguments!");
4732 "getNoopOrZeroExtend cannot truncate!");
4739 Type *SrcTy = V->getType();
4740 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4741 "Cannot noop or sign extend with non-integer arguments!");
4743 "getNoopOrSignExtend cannot truncate!");
4750 Type *SrcTy = V->getType();
4751 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4752 "Cannot noop or any extend with non-integer arguments!");
4754 "getNoopOrAnyExtend cannot truncate!");
4761 Type *SrcTy = V->getType();
4762 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4763 "Cannot truncate or noop with non-integer arguments!");
4765 "getTruncateOrNoop cannot extend!");
4773 const SCEV *PromotedLHS = LHS;
4774 const SCEV *PromotedRHS = RHS;
4794 assert(!
Ops.empty() &&
"At least one operand must be!");
4796 if (
Ops.size() == 1)
4800 Type *MaxType =
nullptr;
4806 assert(MaxType &&
"Failed to find maximum type!");
4819 if (!V->getType()->isPointerTy())
4824 V = AddRec->getStart();
4826 const SCEV *PtrOp =
nullptr;
4827 for (
const SCEV *AddOp :
Add->operands()) {
4828 if (AddOp->getType()->isPointerTy()) {
4829 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4833 assert(PtrOp &&
"Must have pointer op");
4845 for (
User *U :
I->users()) {
4847 if (Visited.
insert(UserInsn).second)
4861 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4862 bool IgnoreOtherLoops =
true) {
4865 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4867 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4872 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4874 SeenLoopVariantSCEVUnknown =
true;
4878 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4882 SeenOtherLoops =
true;
4886 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4888 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4891 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4892 : SCEVRewriteVisitor(SE),
L(
L) {}
4895 bool SeenLoopVariantSCEVUnknown =
false;
4896 bool SeenOtherLoops =
false;
4905 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4906 SCEVPostIncRewriter
Rewriter(L, SE);
4908 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4913 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4915 SeenLoopVariantSCEVUnknown =
true;
4919 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4923 SeenOtherLoops =
true;
4927 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4929 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4932 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4933 : SCEVRewriteVisitor(SE),
L(
L) {}
4936 bool SeenLoopVariantSCEVUnknown =
false;
4937 bool SeenOtherLoops =
false;
4943class SCEVBackedgeConditionFolder
4946 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4947 ScalarEvolution &SE) {
4948 bool IsPosBECond =
false;
4949 Value *BECond =
nullptr;
4950 if (BasicBlock *Latch =
L->getLoopLatch()) {
4952 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
4953 "Both outgoing branches should not target same header!");
4954 BECond = BI->getCondition();
4955 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
4960 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
4964 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4965 const SCEV *
Result = Expr;
4970 switch (
I->getOpcode()) {
4971 case Instruction::Select: {
4973 std::optional<const SCEV *> Res =
4974 compareWithBackedgeCondition(
SI->getCondition());
4982 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
4993 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
4994 bool IsPosBECond, ScalarEvolution &SE)
4995 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
4996 IsPositiveBECond(IsPosBECond) {}
4998 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5002 Value *BackedgeCond =
nullptr;
5004 bool IsPositiveBECond;
5007std::optional<const SCEV *>
5008SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5013 if (BackedgeCond == IC)
5016 return std::nullopt;
5021 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5022 ScalarEvolution &SE) {
5028 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5035 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5045 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5046 : SCEVRewriteVisitor(SE),
L(
L) {}
5054void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5070 const APInt &BECountAP = BECountMax->getAPInt();
5071 unsigned NoOverflowBitWidth =
5080ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5090 if (!SignedWrapViaInductionTried.insert(AR).second)
5115 AC.assumptions().empty())
5123 const SCEV *OverflowLimit =
5125 if (OverflowLimit &&
5133ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5143 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5168 AC.assumptions().empty())
5177 const SCEV *OverflowLimit =
5206 IsNSW = OBO->hasNoSignedWrap();
5207 IsNUW = OBO->hasNoUnsignedWrap();
5213 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5225 return std::nullopt;
5231 switch (
Op->getOpcode()) {
5232 case Instruction::Add:
5233 case Instruction::Sub:
5234 case Instruction::Mul:
5235 case Instruction::UDiv:
5236 case Instruction::URem:
5237 case Instruction::And:
5238 case Instruction::AShr:
5239 case Instruction::Shl:
5242 case Instruction::Or: {
5245 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5255 case Instruction::Xor:
5259 if (RHSC->getValue().isSignMask())
5260 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5262 if (V->getType()->isIntegerTy(1))
5263 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5266 case Instruction::LShr:
5275 if (SA->getValue().ult(
BitWidth)) {
5277 ConstantInt::get(SA->getContext(),
5279 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5284 case Instruction::ExtractValue: {
5286 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5294 bool Signed = WO->isSigned();
5297 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5302 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5313 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5314 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5316 return std::nullopt;
5342 if (
Op == SymbolicPHI)
5347 if (SourceBits != NewBits)
5365 if (!L || L->getHeader() != PN->
getParent())
5423std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5424ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5432 assert(L &&
"Expecting an integer loop header phi");
5437 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5438 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5439 Value *
V = PN->getIncomingValue(i);
5440 if (
L->contains(PN->getIncomingBlock(i))) {
5443 }
else if (BEValueV != V) {
5447 }
else if (!StartValueV) {
5449 }
else if (StartValueV != V) {
5450 StartValueV =
nullptr;
5454 if (!BEValueV || !StartValueV)
5455 return std::nullopt;
5457 const SCEV *BEValue =
getSCEV(BEValueV);
5464 return std::nullopt;
5468 unsigned FoundIndex =
Add->getNumOperands();
5469 Type *TruncTy =
nullptr;
5471 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5474 if (FoundIndex == e) {
5479 if (FoundIndex ==
Add->getNumOperands())
5480 return std::nullopt;
5484 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5485 if (i != FoundIndex)
5486 Ops.push_back(
Add->getOperand(i));
5492 return std::nullopt;
5545 const SCEV *StartVal =
getSCEV(StartValueV);
5546 const SCEV *PHISCEV =
5573 auto getExtendedExpr = [&](
const SCEV *Expr,
5574 bool CreateSignExtend) ->
const SCEV * {
5577 const SCEV *ExtendedExpr =
5580 return ExtendedExpr;
5588 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5589 const SCEV *ExtendedExpr) ->
bool {
5590 return Expr != ExtendedExpr &&
5594 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5595 if (PredIsKnownFalse(StartVal, StartExtended)) {
5597 return std::nullopt;
5602 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5603 if (PredIsKnownFalse(Accum, AccumExtended)) {
5605 return std::nullopt;
5608 auto AppendPredicate = [&](
const SCEV *Expr,
5609 const SCEV *ExtendedExpr) ->
void {
5610 if (Expr != ExtendedExpr &&
5618 AppendPredicate(StartVal, StartExtended);
5619 AppendPredicate(Accum, AccumExtended);
5627 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5628 std::make_pair(NewAR, Predicates);
5630 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5634std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5639 return std::nullopt;
5642 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5643 if (
I != PredicatedSCEVRewrites.end()) {
5644 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5647 if (Rewrite.first == SymbolicPHI)
5648 return std::nullopt;
5652 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5656 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5657 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5662 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5663 return std::nullopt;
5683 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5684 if (Expr1 != Expr2 &&
5685 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5686 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5703const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5705 Value *StartValueV) {
5708 assert(BEValueV && StartValueV);
5714 if (BO->Opcode != Instruction::Add)
5717 const SCEV *Accum =
nullptr;
5718 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5720 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5734 insertValueToMap(PN, PHISCEV);
5737 inferNoWrapViaConstantRanges(AR);
5744 "Accum is defined outside L, but is not invariant?");
5745 if (isAddRecNeverPoison(BEInst, L))
5752const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5760 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5766 }
else if (BEValueV != V) {
5770 }
else if (!StartValueV) {
5772 }
else if (StartValueV != V) {
5773 StartValueV =
nullptr;
5777 if (!BEValueV || !StartValueV)
5780 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5781 "PHI node already processed?");
5785 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5790 insertValueToMap(PN, SymbolicName);
5794 const SCEV *BEValue =
getSCEV(BEValueV);
5804 unsigned FoundIndex =
Add->getNumOperands();
5805 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5806 if (
Add->getOperand(i) == SymbolicName)
5807 if (FoundIndex == e) {
5812 if (FoundIndex !=
Add->getNumOperands()) {
5815 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5816 if (i != FoundIndex)
5817 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5829 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5836 if (
GEP->getOperand(0) == PN) {
5837 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
5855 const SCEV *StartVal =
getSCEV(StartValueV);
5856 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5861 forgetMemoizedResults({SymbolicName});
5862 insertValueToMap(PN, PHISCEV);
5865 inferNoWrapViaConstantRanges(AR);
5889 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5890 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5892 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5893 const SCEV *StartVal =
getSCEV(StartValueV);
5894 if (Start == StartVal) {
5898 forgetMemoizedResults({SymbolicName});
5899 insertValueToMap(PN, Shifted);
5909 eraseValueFromMap(PN);
5924 Use &LeftUse =
Merge->getOperandUse(0);
5925 Use &RightUse =
Merge->getOperandUse(1);
5961 assert(IDom &&
"At least the entry block should dominate PN");
5969const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
5974 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
5991 CommonInst = IncomingInst;
6007ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6013 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6014 bool SCEVExprsIdentical =
6016 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6017 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6020const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6021 if (
const SCEV *S = createAddRecFromPHI(PN))
6031 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6034 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6043 struct FindClosure {
6044 const SCEV *OperandToFind;
6050 bool canRecurseInto(
SCEVTypes Kind)
const {
6053 return RootKind == Kind || NonSequentialRootKind == Kind ||
6058 : OperandToFind(OperandToFind), RootKind(RootKind),
6059 NonSequentialRootKind(
6063 bool follow(
const SCEV *S) {
6064 Found = S == OperandToFind;
6066 return !isDone() && canRecurseInto(S->
getSCEVType());
6069 bool isDone()
const {
return Found; }
6072 FindClosure FC(OperandToFind, RootKind);
6077std::optional<const SCEV *>
6078ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6088 switch (ICI->getPredicate()) {
6102 bool Signed = ICI->isSigned();
6103 const SCEV *LA =
getSCEV(TrueVal);
6111 if (LA == LS &&
RA == RS)
6113 if (LA == RS &&
RA == LS)
6116 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6117 if (
Op->getType()->isPointerTy()) {
6128 LS = CoerceOperand(LS);
6129 RS = CoerceOperand(RS);
6153 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6154 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6168 X = ZExt->getOperand();
6170 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6181 return std::nullopt;
6184static std::optional<const SCEV *>
6186 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6190 "Unexpected operands of a select.");
6202 return std::nullopt;
6217static std::optional<const SCEV *>
6221 return std::nullopt;
6224 const auto *SETrue = SE->
getSCEV(TrueVal);
6225 const auto *SEFalse = SE->
getSCEV(FalseVal);
6229const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6231 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6233 V->getType() ==
TrueVal->getType() &&
6234 "Types of select hands and of the result must match.");
6237 if (!
V->getType()->isIntegerTy(1))
6240 if (std::optional<const SCEV *> S =
6253 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6257 if (std::optional<const SCEV *> S =
6258 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6264 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6270 assert(
GEP->getSourceElementType()->isSized() &&
6271 "GEP source element type must be sized");
6274 for (
Value *Index :
GEP->indices())
6279APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6282 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6285 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6287 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6290 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6308 return GetShiftedByZeros(TZ);
6318 return GetShiftedByZeros(TZ);
6322 if (
M->hasNoUnsignedWrap()) {
6325 for (
const SCEV *Operand :
M->operands().drop_front())
6333 for (
const SCEV *Operand :
M->operands())
6335 return GetShiftedByZeros(TZ);
6340 if (
N->hasNoUnsignedWrap())
6341 return GetGCDMultiple(
N);
6344 for (
const SCEV *Operand :
N->operands().drop_front())
6346 return GetShiftedByZeros(TZ);
6363 CtxI = &*F.getEntryBlock().begin();
6370 .allowEphemerals(
true))
6371 .countMinTrailingZeros();
6372 return GetShiftedByZeros(
Known);
6385 return getConstantMultipleImpl(S, CtxI);
6387 auto I = ConstantMultipleCache.find(S);
6388 if (
I != ConstantMultipleCache.end())
6391 APInt Result = getConstantMultipleImpl(S, CtxI);
6392 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6393 assert(InsertPair.second &&
"Should insert a new key");
6394 return InsertPair.first->second;
6411 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6414 if (std::optional<ConstantRange>
Range = CB->getRange())
6418 if (std::optional<ConstantRange>
Range =
A->getRange())
6421 return std::nullopt;
6428 UnsignedRanges.erase(AddRec);
6429 SignedRanges.erase(AddRec);
6430 ConstantMultipleCache.erase(AddRec);
6435getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6461 Value *Start, *Step;
6468 assert(L && L->getHeader() ==
P->getParent());
6481 case Instruction::AShr:
6482 case Instruction::LShr:
6483 case Instruction::Shl:
6498 KnownStep.getBitWidth() ==
BitWidth);
6501 auto MaxShiftAmt = KnownStep.getMaxValue();
6503 bool Overflow =
false;
6504 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6511 case Instruction::AShr: {
6519 if (KnownStart.isNonNegative())
6522 KnownStart.getMaxValue() + 1);
6523 if (KnownStart.isNegative())
6526 KnownEnd.getMaxValue() + 1);
6529 case Instruction::LShr: {
6538 KnownStart.getMaxValue() + 1);
6540 case Instruction::Shl: {
6544 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6545 return ConstantRange(KnownStart.getMinValue(),
6546 KnownEnd.getMaxValue() + 1);
6571 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6578ScalarEvolution::getRangeRefIter(
const SCEV *S,
6579 ScalarEvolution::RangeSignHint SignHint) {
6580 DenseMap<const SCEV *, ConstantRange> &Cache =
6581 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6584 SmallPtrSet<const SCEV *, 8> Seen;
6588 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6589 if (!Seen.
insert(Expr).second)
6622 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6623 const SCEV *
P = WorkList[
I];
6627 for (
const SCEV *
Op :
P->operands())
6640 if (!WorkList.
empty()) {
6645 getRangeRef(
P, SignHint);
6649 return getRangeRef(S, SignHint, 0);
6652const APInt *ScalarEvolution::getConstantAPIntOrNull(
const SCEV *S) {
6654 return &
C->getAPInt();
6662 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6663 DenseMap<const SCEV *, ConstantRange> &Cache =
6664 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6671 auto I = Cache.
find(S);
6672 if (
I != Cache.
end())
6676 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6681 return getRangeRefIter(S, SignHint);
6684 ConstantRange ConservativeResult(
BitWidth,
true);
6685 using OBO = OverflowingBinaryOperator;
6689 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6693 ConservativeResult =
6700 ConservativeResult = ConstantRange(
6716 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6723 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6730 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6735 return setRange(Cast, SignHint,
X);
6740 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6741 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6743 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6744 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6745 ConservativeResult =
6746 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6748 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6749 unsigned WrapType = OBO::AnyWrap;
6750 if (
Add->hasNoSignedWrap())
6751 WrapType |= OBO::NoSignedWrap;
6752 if (
Add->hasNoUnsignedWrap())
6753 WrapType |= OBO::NoUnsignedWrap;
6755 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6757 return setRange(
Add, SignHint,
6758 ConservativeResult.intersectWith(
X, RangeType));
6762 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6764 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6765 return setRange(
Mul, SignHint,
6766 ConservativeResult.intersectWith(
X, RangeType));
6770 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6771 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6772 return setRange(UDiv, SignHint,
6773 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6781 if (!UnsignedMinValue.
isZero())
6782 ConservativeResult = ConservativeResult.intersectWith(
6783 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6792 bool AllNonNeg =
true;
6793 bool AllNonPos =
true;
6794 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6801 ConservativeResult = ConservativeResult.intersectWith(
6806 ConservativeResult = ConservativeResult.intersectWith(
6815 const SCEV *MaxBEScev =
6829 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6831 ConservativeResult =
6832 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6835 auto RangeFromFactoring = getRangeViaFactoring(
6837 ConservativeResult =
6838 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6844 const SCEV *SymbolicMaxBECount =
6849 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6850 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6851 ConservativeResult =
6852 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6857 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6867 ID = Intrinsic::umax;
6870 ID = Intrinsic::smax;
6874 ID = Intrinsic::umin;
6877 ID = Intrinsic::smin;
6884 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6885 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6887 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6888 return setRange(S, SignHint,
6889 ConservativeResult.intersectWith(
X, RangeType));
6898 ConservativeResult =
6899 ConservativeResult.intersectWith(*MDRange, RangeType);
6904 auto CR = getRangeForUnknownRecurrence(U);
6905 ConservativeResult = ConservativeResult.intersectWith(CR);
6916 if (
U->getType()->isPointerTy()) {
6919 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
6920 int ptrIdxDiff = ptrSize -
BitWidth;
6921 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
6927 if (!
Known.Zero.getHiBits(NS).isZero())
6928 Known.Zero.setHighBits(NS);
6929 if (!
Known.One.getHiBits(NS).isZero())
6930 Known.One.setHighBits(NS);
6933 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
6934 ConservativeResult = ConservativeResult.intersectWith(
6935 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
6938 ConservativeResult = ConservativeResult.intersectWith(
6943 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6947 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
6948 DL, CanBeNull,
nullptr);
6964 ConservativeResult = ConservativeResult.intersectWith(
6974 return getRangeRef(AR, SignHint,
Depth + 1);
6978 ConstantRange RangeFromOps(
BitWidth,
false);
6980 for (
const auto &
Op :
Phi->operands()) {
6982 RangeFromOps = RangeFromOps.unionWith(OpRange);
6984 if (RangeFromOps.isFullSet())
6987 ConservativeResult =
6988 ConservativeResult.intersectWith(RangeFromOps, RangeType);
6994 if (
II->getIntrinsicID() == Intrinsic::vscale) {
6996 ConservativeResult = ConservativeResult.difference(Disallowed);
6999 return setRange(U, SignHint, std::move(ConservativeResult));
7005 return setRange(S, SignHint, std::move(ConservativeResult));
7013static std::pair<ConstantRange, bool>
7021 if (Step == 0 || MaxBECount == 0)
7022 return {StartRange,
true};
7028 return {ConstantRange::getFull(
BitWidth),
false};
7044 return {ConstantRange::getFull(
BitWidth),
false};
7057 APInt MovedBoundary;
7062 MovedBoundary = StartLower - std::move(
Offset);
7065 MovedBoundary = StartUpper + std::move(
Offset);
7069 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7076 if (StartRange.
contains(MovedBoundary))
7077 return {ConstantRange::getFull(
BitWidth),
false};
7080 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7082 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7090std::pair<ConstantRange, SCEV::NoWrapFlags>
7091ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7092 const APInt &MaxBECount) {
7096 "mismatched bit widths");
7105 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7107 StartSRange, MaxBECount,
7109 ConstantRange SR = SR1.unionWith(SR2);
7126ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7128 ScalarEvolution::RangeSignHint SignHint) {
7129 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7131 "This only works for non-self-wrapping AddRecs!");
7132 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7136 return ConstantRange::getFull(
BitWidth);
7144 return ConstantRange::getFull(
BitWidth);
7148 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7150 MaxItersWithoutWrap))
7151 return ConstantRange::getFull(
BitWidth);
7172 ConstantRange StartRange = getRangeRef(Start, SignHint);
7173 ConstantRange EndRange = getRangeRef(End, SignHint);
7174 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7178 return RangeBetween;
7183 return ConstantRange::getFull(
BitWidth);
7186 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7187 return RangeBetween;
7189 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7190 return RangeBetween;
7191 return ConstantRange::getFull(
BitWidth);
7196 const APInt &MaxBECount) {
7203 "mismatched bit widths");
7205 struct SelectPattern {
7206 Value *Condition =
nullptr;
7210 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7212 std::optional<unsigned> CastOp;
7226 CastOp = SCast->getSCEVType();
7227 S = SCast->getOperand();
7230 using namespace llvm::PatternMatch;
7237 Condition =
nullptr;
7269 bool isRecognized() {
return Condition !=
nullptr; }
7272 SelectPattern StartPattern(*
this,
BitWidth, Start);
7273 if (!StartPattern.isRecognized())
7274 return ConstantRange::getFull(
BitWidth);
7276 SelectPattern StepPattern(*
this,
BitWidth, Step);
7277 if (!StepPattern.isRecognized())
7278 return ConstantRange::getFull(
BitWidth);
7280 if (StartPattern.Condition != StepPattern.Condition) {
7284 return ConstantRange::getFull(
BitWidth);
7295 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7296 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7297 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7298 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7300 ConstantRange TrueRange =
7301 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7302 ConstantRange FalseRange =
7303 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7315 PDI && PDI->isDisjoint()) {
7330ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7343 SmallPtrSet<const SCEV *, 16> Visited;
7345 auto pushOp = [&](
const SCEV *S) {
7346 if (!Visited.
insert(S).second)
7349 if (Visited.
size() > 30) {
7360 while (!Worklist.
empty()) {
7362 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7363 if (!Bound || DT.dominates(Bound, DefI))
7370 return Bound ? Bound : &*F.getEntryBlock().begin();
7376 return getDefiningScopeBound(
Ops, Discard);
7379bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7381 if (
A->getParent() ==
B->getParent() &&
7386 auto *BLoop = LI.getLoopFor(
B->getParent());
7387 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7388 BLoop->getLoopPreheader() ==
A->getParent() &&
7390 A->getParent()->end()) &&
7398 SCEVPoisonCollector PC(
true);
7400 return PC.MaybePoison.
empty();
7403bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7413bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7430 for (
const Use &
Op :
I->operands()) {
7436 auto *DefI = getDefiningScopeBound(SCEVOps);
7437 return isGuaranteedToTransferExecutionTo(DefI,
I);
7440bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7442 if (isSCEVExprNeverPoison(
I))
7453 auto *ExitingBB =
L->getExitingBlock();
7457 SmallPtrSet<const Value *, 16> KnownPoison;
7466 while (!Worklist.
empty()) {
7469 for (
const Use &U :
Poison->uses()) {
7472 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7476 if (KnownPoison.
insert(PoisonUser).second)
7484ScalarEvolution::LoopProperties
7485ScalarEvolution::getLoopProperties(
const Loop *L) {
7486 using LoopProperties = ScalarEvolution::LoopProperties;
7488 auto Itr = LoopPropertiesCache.find(L);
7489 if (Itr == LoopPropertiesCache.end()) {
7492 return !
SI->isSimple();
7502 return I->mayWriteToMemory();
7505 LoopProperties LP = {
true,
7508 for (
auto *BB :
L->getBlocks())
7509 for (
auto &
I : *BB) {
7511 LP.HasNoAbnormalExits =
false;
7512 if (HasSideEffects(&
I))
7513 LP.HasNoSideEffects =
false;
7514 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7518 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7519 assert(InsertPair.second &&
"We just checked!");
7520 Itr = InsertPair.first;
7533const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7539 Stack.emplace_back(V,
false);
7540 while (!Stack.empty()) {
7541 auto E = Stack.back();
7542 Value *CurV = E.getPointer();
7550 const SCEV *CreatedSCEV =
nullptr;
7553 CreatedSCEV = createSCEV(CurV);
7558 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7562 insertValueToMap(CurV, CreatedSCEV);
7565 Stack.back().setInt(
true);
7568 Stack.emplace_back(
Op,
false);
7585 if (!DT.isReachableFromEntry(
I->getParent()))
7598 switch (BO->Opcode) {
7599 case Instruction::Add:
7600 case Instruction::Mul: {
7607 Ops.push_back(BO->
Op);
7611 Ops.push_back(BO->RHS);
7615 (BO->Opcode == Instruction::Add &&
7616 (NewBO->Opcode != Instruction::Add &&
7617 NewBO->Opcode != Instruction::Sub)) ||
7618 (BO->Opcode == Instruction::Mul &&
7619 NewBO->Opcode != Instruction::Mul)) {
7620 Ops.push_back(BO->LHS);
7625 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7628 Ops.push_back(BO->LHS);
7636 case Instruction::Sub:
7637 case Instruction::UDiv:
7638 case Instruction::URem:
7640 case Instruction::AShr:
7641 case Instruction::Shl:
7642 case Instruction::Xor:
7646 case Instruction::And:
7647 case Instruction::Or:
7651 case Instruction::LShr:
7658 Ops.push_back(BO->LHS);
7659 Ops.push_back(BO->RHS);
7663 switch (
U->getOpcode()) {
7664 case Instruction::Trunc:
7665 case Instruction::ZExt:
7666 case Instruction::SExt:
7667 case Instruction::PtrToAddr:
7668 case Instruction::PtrToInt:
7669 Ops.push_back(
U->getOperand(0));
7672 case Instruction::BitCast:
7674 Ops.push_back(
U->getOperand(0));
7679 case Instruction::SDiv:
7680 case Instruction::SRem:
7681 Ops.push_back(
U->getOperand(0));
7682 Ops.push_back(
U->getOperand(1));
7685 case Instruction::GetElementPtr:
7687 "GEP source element type must be sized");
7691 case Instruction::IntToPtr:
7694 case Instruction::PHI:
7725 Ops.push_back(CondICmp->getOperand(0));
7726 Ops.push_back(CondICmp->getOperand(1));
7746 case Instruction::Select: {
7748 auto CanSimplifyToUnknown = [
this,
U]() {
7766 if (CanSimplifyToUnknown())
7773 case Instruction::Call:
7774 case Instruction::Invoke:
7781 switch (
II->getIntrinsicID()) {
7782 case Intrinsic::abs:
7783 Ops.push_back(
II->getArgOperand(0));
7785 case Intrinsic::umax:
7786 case Intrinsic::umin:
7787 case Intrinsic::smax:
7788 case Intrinsic::smin:
7789 case Intrinsic::usub_sat:
7790 case Intrinsic::uadd_sat:
7791 Ops.push_back(
II->getArgOperand(0));
7792 Ops.push_back(
II->getArgOperand(1));
7794 case Intrinsic::start_loop_iterations:
7795 case Intrinsic::annotation:
7796 case Intrinsic::ptr_annotation:
7797 Ops.push_back(
II->getArgOperand(0));
7809const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7818 if (!DT.isReachableFromEntry(
I->getParent()))
7833 switch (BO->Opcode) {
7834 case Instruction::Add: {
7860 if (BO->Opcode == Instruction::Sub)
7868 if (BO->Opcode == Instruction::Sub)
7875 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7876 NewBO->Opcode != Instruction::Sub)) {
7886 case Instruction::Mul: {
7907 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7916 case Instruction::UDiv:
7920 case Instruction::URem:
7924 case Instruction::Sub: {
7927 Flags = getNoWrapFlagsFromUB(BO->
Op);
7932 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
7935 if (HasPtrLHS || HasPtrRHS) {
7940 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
7941 bool BothPtr) ->
const SCEV * {
7944 const SCEV *PtrSCEV =
getSCEV(PtrOp);
7954 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
7955 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
7963 case Instruction::And:
7969 if (CI->isMinusOne())
7971 const APInt &
A = CI->getValue();
7977 unsigned LZ =
A.countl_zero();
7978 unsigned TZ =
A.countr_zero();
7983 APInt EffectiveMask =
7985 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
7988 const SCEV *ShiftedLHS =
nullptr;
7992 unsigned MulZeros = OpC->getAPInt().countr_zero();
7993 unsigned GCD = std::min(MulZeros, TZ);
7998 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8020 case Instruction::Or:
8029 case Instruction::Xor:
8032 if (CI->isMinusOne())
8041 if (LBO->getOpcode() == Instruction::And &&
8042 LCI->getValue() == CI->getValue())
8043 if (
const SCEVZeroExtendExpr *Z =
8046 const SCEV *Z0 =
Z->getOperand();
8053 if (CI->getValue().isMask(Z0TySize))
8059 APInt Trunc = CI->getValue().trunc(Z0TySize);
8068 case Instruction::Shl:
8086 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8095 ConstantInt *
X = ConstantInt::get(
8101 case Instruction::AShr:
8123 const SCEV *AddTruncateExpr =
nullptr;
8124 ConstantInt *ShlAmtCI =
nullptr;
8125 const SCEV *AddConstant =
nullptr;
8127 if (L &&
L->getOpcode() == Instruction::Add) {
8135 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8142 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8150 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8155 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8160 if (AddTruncateExpr && ShlAmtCI) {
8172 const APInt &ShlAmt = ShlAmtCI->
getValue();
8176 const SCEV *CompositeExpr =
8178 if (
L->getOpcode() != Instruction::Shl)
8179 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8188 switch (
U->getOpcode()) {
8189 case Instruction::Trunc:
8192 case Instruction::ZExt:
8195 case Instruction::SExt:
8205 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8206 Type *Ty =
U->getType();
8214 case Instruction::BitCast:
8220 case Instruction::PtrToAddr: {
8227 case Instruction::PtrToInt:
8231 case Instruction::IntToPtr:
8235 case Instruction::SDiv:
8242 case Instruction::SRem:
8249 case Instruction::GetElementPtr:
8252 case Instruction::PHI:
8255 case Instruction::Select:
8256 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8259 case Instruction::Call:
8260 case Instruction::Invoke:
8265 switch (
II->getIntrinsicID()) {
8266 case Intrinsic::abs:
8270 case Intrinsic::umax:
8274 case Intrinsic::umin:
8278 case Intrinsic::smax:
8282 case Intrinsic::smin:
8286 case Intrinsic::usub_sat: {
8287 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8288 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8292 case Intrinsic::uadd_sat: {
8293 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8294 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8298 case Intrinsic::start_loop_iterations:
8299 case Intrinsic::annotation:
8300 case Intrinsic::ptr_annotation:
8304 case Intrinsic::vscale:
8324 auto *ExitCountType = ExitCount->
getType();
8325 assert(ExitCountType->isIntegerTy());
8327 1 + ExitCountType->getScalarSizeInBits());
8340 auto CanAddOneWithoutOverflow = [&]() {
8342 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8353 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8383 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8384 assert(L->isLoopExiting(ExitingBlock) &&
8385 "Exiting block must actually branch out of the loop!");
8394 const auto *MaxExitCount =
8402 L->getExitingBlocks(ExitingBlocks);
8405 if (ExitingBlocks.
empty() ||
8421 const LoopGuards &Guards) {
8425 const SCEV *TCExpr =
8433 : (
unsigned)Multiple.getZExtValue();
8437 const SCEV *ExitCount) {
8459 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8460 assert(L->isLoopExiting(ExitingBlock) &&
8461 "Exiting block must actually branch out of the loop!");
8471 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8473 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8475 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8485 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8488 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8491 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8499 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8506 return getBackedgeTakenInfo(L).getExact(L,
this);
8508 return getBackedgeTakenInfo(L).getConstantMax(
this);
8510 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8517 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8522 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8526 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8536 for (
PHINode &PN : Header->phis())
8537 if (Visited.
insert(&PN).second)
8541ScalarEvolution::BackedgeTakenInfo &
8542ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8543 auto &BTI = getBackedgeTakenInfo(L);
8544 if (BTI.hasFullInfo())
8547 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8550 return Pair.first->second;
8552 BackedgeTakenInfo
Result =
8553 computeBackedgeTakenCount(L,
true);
8555 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8558ScalarEvolution::BackedgeTakenInfo &
8559ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8565 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8566 BackedgeTakenCounts.try_emplace(L);
8568 return Pair.first->second;
8573 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8580 if (
Result.hasAnyInfo()) {
8583 auto LoopUsersIt = LoopUsers.find(L);
8584 if (LoopUsersIt != LoopUsers.end())
8586 forgetMemoizedResults(ToForget);
8589 for (PHINode &PN :
L->getHeader()->phis())
8590 ConstantEvolutionLoopExitValue.erase(&PN);
8598 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8607 BackedgeTakenCounts.clear();
8608 PredicatedBackedgeTakenCounts.clear();
8609 BECountUsers.clear();
8610 LoopPropertiesCache.clear();
8611 ConstantEvolutionLoopExitValue.clear();
8612 ValueExprMap.clear();
8613 ValuesAtScopes.clear();
8614 ValuesAtScopesUsers.clear();
8615 LoopDispositions.clear();
8616 BlockDispositions.clear();
8617 UnsignedRanges.clear();
8618 SignedRanges.clear();
8619 ExprValueMap.clear();
8621 ConstantMultipleCache.clear();
8622 PredicatedSCEVRewrites.clear();
8624 FoldCacheUser.clear();
8626void ScalarEvolution::visitAndClearUsers(
8630 while (!Worklist.
empty()) {
8637 if (It != ValueExprMap.
end()) {
8639 eraseValueFromMap(It->first);
8641 ConstantEvolutionLoopExitValue.erase(PN);
8655 while (!LoopWorklist.
empty()) {
8659 forgetBackedgeTakenCounts(CurrL,
false);
8660 forgetBackedgeTakenCounts(CurrL,
true);
8663 PredicatedSCEVRewrites.remove_if(
8664 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8666 auto LoopUsersItr = LoopUsers.find(CurrL);
8667 if (LoopUsersItr != LoopUsers.end())
8672 visitAndClearUsers(Worklist, Visited, ToForget);
8674 LoopPropertiesCache.erase(CurrL);
8677 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8679 forgetMemoizedResults(ToForget);
8696 visitAndClearUsers(Worklist, Visited, ToForget);
8698 forgetMemoizedResults(ToForget);
8706 auto InvalidateValue = [&](
Value *Val) {
8710 struct InvalidationRootCollector {
8714 InvalidationRootCollector(
Loop *L) : L(L) {}
8716 bool follow(
const SCEV *S) {
8722 if (L->contains(AddRec->
getLoop()))
8727 bool isDone()
const {
return false; }
8730 InvalidationRootCollector
C(L);
8732 forgetMemoizedResults(
C.Roots);
8755 BlockDispositions.clear();
8756 LoopDispositions.clear();
8773 while (!Worklist.
empty()) {
8775 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8776 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8777 if (!LoopDispoRemoved && !BlockDispoRemoved)
8779 auto Users = SCEVUsers.find(Curr);
8780 if (
Users != SCEVUsers.end())
8793const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8797 if (!isComplete() || ExitNotTaken.
empty())
8808 for (
const auto &ENT : ExitNotTaken) {
8809 const SCEV *BECount = ENT.ExactNotTaken;
8812 "We should only have known counts for exiting blocks that dominate "
8815 Ops.push_back(BECount);
8820 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8821 "Predicate should be always true!");
8830const ScalarEvolution::ExitNotTakenInfo *
8831ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8832 const BasicBlock *ExitingBlock,
8833 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8834 for (
const auto &ENT : ExitNotTaken)
8835 if (ENT.ExitingBlock == ExitingBlock) {
8836 if (ENT.hasAlwaysTruePredicate())
8838 else if (Predicates) {
8848const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8850 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8851 if (!getConstantMax())
8854 for (
const auto &ENT : ExitNotTaken)
8855 if (!ENT.hasAlwaysTruePredicate()) {
8863 "No point in having a non-constant max backedge taken count!");
8864 return getConstantMax();
8867const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8869 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8877 for (
const auto &ENT : ExitNotTaken) {
8878 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8881 "We should only have known counts for exiting blocks that "
8887 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8888 "Predicate should be always true!");
8891 if (ExitCounts.
empty())
8900bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8902 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8903 return !ENT.hasAlwaysTruePredicate();
8905 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8921 this->ExactNotTaken = E = ConstantMaxNotTaken;
8922 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8927 "Exact is not allowed to be less precise than Constant Max");
8930 "Exact is not allowed to be less precise than Symbolic Max");
8933 "Symbolic Max is not allowed to be less precise than Constant Max");
8936 "No point in having a non-constant max backedge taken count!");
8938 for (
const auto PredList : PredLists)
8939 for (
const auto *
P : PredList) {
8947 "Backedge count should be int");
8950 "Max backedge count should be int");
8963ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8965 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8966 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8967 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8969 ExitNotTaken.reserve(ExitCounts.
size());
8970 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8971 std::back_inserter(ExitNotTaken),
8972 [&](
const EdgeExitInfo &EEI) {
8973 BasicBlock *ExitBB = EEI.first;
8974 const ExitLimit &EL = EEI.second;
8975 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
8976 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
8981 "No point in having a non-constant max backedge taken count!");
8985ScalarEvolution::BackedgeTakenInfo
8986ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
8987 bool AllowPredicates) {
8989 L->getExitingBlocks(ExitingBlocks);
8991 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8994 bool CouldComputeBECount =
true;
8996 const SCEV *MustExitMaxBECount =
nullptr;
8997 const SCEV *MayExitMaxBECount =
nullptr;
8998 bool MustExitMaxOrZero =
false;
8999 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9010 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9011 if (ExitIfTrue == CI->
isZero())
9015 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9017 assert((AllowPredicates || EL.Predicates.empty()) &&
9018 "Predicated exit limit when predicates are not allowed!");
9023 ++NumExitCountsComputed;
9027 CouldComputeBECount =
false;
9034 "Exact is known but symbolic isn't?");
9035 ++NumExitCountsNotComputed;
9050 DT.dominates(ExitBB, Latch)) {
9051 if (!MustExitMaxBECount) {
9052 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9053 MustExitMaxOrZero = EL.MaxOrZero;
9056 EL.ConstantMaxNotTaken);
9060 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9063 EL.ConstantMaxNotTaken);
9067 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9071 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9077 for (
const auto &Pair : ExitCounts) {
9079 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9081 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9082 {
L, AllowPredicates});
9084 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9085 MaxBECount, MaxOrZero);
9088ScalarEvolution::ExitLimit
9089ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9090 bool IsOnlyExit,
bool AllowPredicates) {
9091 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9095 if (!Latch || !DT.dominates(ExitingBlock, Latch))