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 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1020 ConversionFn CreatePtrCast;
1024 ConversionFn CreatePtrCast)
1025 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
1028 Type *TargetTy, ConversionFn CreatePtrCast) {
1030 return Rewriter.visit(Scev);
1056 "Should only reach pointer-typed SCEVUnknown's.");
1061 return SE.getZero(TargetTy);
1062 return CreatePtrCast(Expr);
1067 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1071 if (DL.hasUnstableRepresentation(
Op->getType()))
1074 Type *Ty = DL.getAddressType(
Op->getType());
1085 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1087 SCEV *S =
new (SCEVAllocator)
1089 UniqueSCEVs.insert(S, Token);
1092 return static_cast<const SCEV *
>(S);
1095 "We must have succeeded in sinking the cast, "
1096 "and ending up with an integer-typed expression!");
1103 "This is not a truncating conversion!");
1105 "This is not a conversion to a SCEVable type!");
1106 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1111 ID.AddPointer(
Op.getOpaqueValue());
1114 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1137 UniqueSCEVs.insert(S, Token);
1150 unsigned numTruncs = 0;
1151 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1159 if (numTruncs < 2) {
1169 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1176 for (
const SCEV *
Op : AddRec->operands())
1191 UniqueSCEVs.insert(S, Token);
1232struct ExtendOpTraitsBase {
1233 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
SCEVUse,
Type *,
1238template <
typename ExtendOp>
struct ExtendOpTraits {
1254 static const GetExtendExprTy GetExtendExpr;
1256 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1257 ICmpInst::Predicate *Pred,
1258 ScalarEvolution *SE) {
1263const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1270 static const GetExtendExprTy GetExtendExpr;
1272 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1273 ICmpInst::Predicate *Pred,
1274 ScalarEvolution *SE) {
1279const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1291template <
typename ExtendOpTy>
1294 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1295 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1311 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1324 auto PreStartFlags =
1342 const SCEV *OperandExtendedStart =
1344 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1345 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1357 const SCEV *OverflowLimit =
1358 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1360 if (OverflowLimit &&
1368template <
typename ExtendOpTy>
1372 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1380 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1415template <
typename ExtendOpTy>
1416bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1419 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1429 APInt StartAI = StartC->
getAPInt();
1431 for (
unsigned Delta : {-2, -1, 1, 2}) {
1432 const SCEV *PreStart =
getConstant(StartAI - Delta);
1434 FoldingSetNodeID
ID;
1436 ID.AddPointer(PreStart);
1437 ID.AddPointer(Step);
1439 FoldingSetInsertToken Token;
1441 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.lookup(ID, Token));
1445 if (PreAR &&
any(PreAR->getNoWrapFlags(WrapType))) {
1448 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1449 DeltaS, &Pred,
this);
1467 const unsigned BitWidth =
C.getBitWidth();
1485 const APInt &ConstantStart,
1500 auto I = FoldCache.
insert({ID, S});
1504 auto &UserIDs = FoldCacheUser[
I.first->second];
1505 assert(
count(UserIDs, ID) == 1 &&
"unexpected duplicates in UserIDs");
1506 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1507 if (UserIDs[
I] == ID) {
1512 I.first->second = S;
1514 FoldCacheUser[S].push_back(ID);
1520 "This is not an extending conversion!");
1522 "This is not a conversion to a SCEVable type!");
1523 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1527 if (
const SCEV *S = FoldCache.lookup(ID))
1539 "This is not an extending conversion!");
1541 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1553 const SCEV *Start, *Step;
1558 if (AR->hasNoUnsignedWrap()) {
1569 ID.AddPointer(
Op.getOpaqueValue());
1572 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1577 UniqueSCEVs.insert(S, Token);
1587 const SCEV *
X = ST->getOperand();
1620 const SCEV *CastedMaxBECount =
1624 if (MaxBECount == RecastedMaxBECount) {
1633 const SCEV *WideMaxBECount =
1635 const SCEV *OperandExtendedAdd =
1641 if (ZAdd == OperandExtendedAdd) {
1652 OperandExtendedAdd =
1658 if (ZAdd == OperandExtendedAdd) {
1679 !AC.assumptions().empty()) {
1681 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1683 if (AR->hasNoUnsignedWrap()) {
1718 const APInt &
C = SC->getAPInt();
1722 const SCEV *SResidual =
1730 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1754 if (SA->hasNoUnsignedWrap()) {
1767 if (SA->hasNoSignedWrap() &&
1770 C->isNegative() && !
C->isMinSignedValue() && C2->
sge(
C->abs())) {
1789 const SCEV *SResidual =
1800 if (SM->hasNoUnsignedWrap()) {
1822 const SCEV *TruncRHS;
1859 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1863 UniqueSCEVs.insert(S, Token);
1872 "This is not an extending conversion!");
1874 "This is not a conversion to a SCEVable type!");
1875 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1879 if (
const SCEV *S = FoldCache.lookup(ID))
1891 "This is not an extending conversion!");
1893 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1910 const SCEV *Start, *Step;
1915 if (AR->hasNoSignedWrap()) {
1926 ID.AddPointer(
Op.getOpaqueValue());
1929 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1935 UniqueSCEVs.insert(S, Token);
1945 const SCEV *
X = ST->getOperand();
1956 if (SA->hasNoSignedWrap()) {
1978 const SCEV *SResidual =
2011 const SCEV *CastedMaxBECount =
2015 if (MaxBECount == RecastedMaxBECount) {
2024 const SCEV *WideMaxBECount =
2026 const SCEV *OperandExtendedAdd =
2032 if (SAdd == OperandExtendedAdd) {
2043 OperandExtendedAdd =
2049 if (SAdd == OperandExtendedAdd) {
2069 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2071 if (AR->hasNoSignedWrap()) {
2085 const APInt &
C = SC->getAPInt();
2089 const SCEV *SResidual =
2097 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2124 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
2128 UniqueSCEVs.insert(S, Token);
2144 assert(Expr->
getType() == Ty &&
"requested type must match");
2156 "This is not an extending conversion!");
2158 "This is not a conversion to a SCEVable type!");
2163 if (SC->getAPInt().isNegative())
2168 const SCEV *NewOp =
T->getOperand();
2187 for (
const SCEV *
Op : AR->operands())
2225 APInt &AccumulatedConstant,
2229 bool Interesting =
false;
2236 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2238 AccumulatedConstant += Scale *
C->getAPInt();
2243 for (; i !=
Ops.size(); ++i) {
2252 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2258 auto Pair = M.insert({
Key, NewScale});
2262 Pair.first->second += NewScale;
2270 auto Pair = M.insert({
Ops[i], Scale});
2274 Pair.first->second += Scale;
2293 case Instruction::Add:
2296 case Instruction::Sub:
2299 case Instruction::Mul:
2313 const SCEV *
A = (this->*Extension)(
2315 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2316 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2324 if (BinOp == Instruction::Mul)
2330 APInt C = RHSC->getAPInt();
2331 unsigned NumBits =
C.getBitWidth();
2332 bool IsSub = (BinOp == Instruction::Sub);
2333 bool IsNegativeConst = (
Signed &&
C.isNegative());
2335 bool OverflowDown = IsSub ^ IsNegativeConst;
2337 if (IsNegativeConst) {
2350 APInt Limit = Min + Magnitude;
2356 APInt Limit = Max - Magnitude;
2361std::optional<SCEV::NoWrapFlags>
2366 return std::nullopt;
2375 bool Deduced =
false;
2381 bool CanUseNSW =
true;
2382 const APInt *ShiftAmt;
2387 return std::nullopt;
2391 Opcode = Instruction::Mul;
2393 }
else if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
2394 Opcode != Instruction::Mul) {
2395 return std::nullopt;
2414 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;
2467 Opcode,
C, OBO::NoSignedWrap);
2475 Opcode,
C, OBO::NoUnsignedWrap);
2485 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2492 if (UDiv->getOperand(1) ==
Ops[1])
2495 if (UDiv->getOperand(1) ==
Ops[0])
2511 "only nuw or nsw allowed");
2512 assert(!
Ops.empty() &&
"Cannot get empty add!");
2513 if (
Ops.size() == 1)
return Ops[0];
2516 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2518 "SCEVAddExpr operand types don't match!");
2520 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2521 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2526 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2527 [](
const APInt &
C) {
return C.isZero(); },
2528 [](
const APInt &
C) {
return false; });
2541 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2546 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2547 Add->setNoWrapFlags(ComputeFlags(
Ops));
2555 bool FoundMatch =
false;
2556 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2557 if (
Ops[i] ==
Ops[i+1]) {
2569 --i; e -=
Count - 1;
2579 auto FindTruncSrcType = [&]() ->
Type * {
2585 return T->getOperand()->getType();
2587 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2589 return T->getOperand()->getType();
2593 if (
auto *SrcType = FindTruncSrcType()) {
2600 if (
T->getOperand()->getType() != SrcType) {
2609 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2612 if (
T->getOperand()->getType() != SrcType) {
2640 if (
Ops.size() == 2) {
2650 auto C2 =
C->getAPInt();
2653 APInt ConstAdd = C1 + C2;
2654 auto AddFlags = AddExpr->getNoWrapFlags();
2695 if (
Ops.size() == 2 &&
2706 if (Idx <
Ops.size()) {
2707 bool DeletedAdd =
false;
2718 Ops.erase(
Ops.begin()+Idx);
2721 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2744 struct APIntCompare {
2745 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2746 return LHS.ult(RHS);
2753 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2754 for (
const SCEV *NewOp : NewOps)
2755 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2758 if (AccumulatedConstant != 0)
2760 for (
auto &MulOp : MulOpLists) {
2761 if (MulOp.first == 1) {
2763 }
else if (MulOp.first != 0) {
2772 if (
Ops.size() == 1)
2781 if (M->getNumOperands() == 2)
2782 return M->getOperand(OpIdx == 0);
2784 append_range(Remaining, M->operands().drop_front(OpIdx + 1));
2793 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2797 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2805 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp) {
2806 if (MulOpSCEV ==
Ops[AddOp]) {
2817 for (
unsigned OMulOp = 0, OE = OtherMul->
getNumOperands(); OMulOp != OE;
2819 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2821 Cofactors.
push_back(StripFactor(OtherMul, OMulOp));
2830 if (!Cofactors.
empty()) {
2838 if (
Ops.size() == DeadIndices.
size() + 1)
2845 Ops.erase(
Ops.begin() + Idx);
2849 Ops.push_back(OuterMul);
2868 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2871 Ops.erase(
Ops.begin()+i);
2876 if (!LIOps.
empty()) {
2901 auto *DefI = getDefiningScopeBound(LIOps);
2903 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2915 if (
Ops.size() == 1)
return NewRec;
2918 for (
unsigned i = 0;; ++i)
2919 if (
Ops[i] == AddRec) {
2929 for (
unsigned OtherIdx = Idx+1;
2937 "AddRecExprs are not sorted in reverse dominance order?");
2944 if (OtherAddRec->getLoop() == AddRecLoop) {
2945 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2947 if (i >= AddRecOps.
size()) {
2948 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2952 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
2955 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
2970 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2978 ID.AddPointer(
Op.getOpaqueValue());
2984 S =
new (SCEVAllocator)
2986 UniqueSCEVs.insert(S, Token);
2997 FoldingSetNodeID
ID;
3000 ID.AddPointer(
Op.getOpaqueValue());
3002 FoldingSetInsertToken Token;
3004 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.lookup(ID, Token));
3008 S =
new (SCEVAllocator)
3009 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3010 UniqueSCEVs.insert(S, Token);
3012 LoopUsers[
L].push_back(S);
3021 FoldingSetNodeID
ID;
3024 ID.AddPointer(
Op.getOpaqueValue());
3025 FoldingSetInsertToken Token;
3026 SCEVMulExpr *S =
static_cast<SCEVMulExpr *
>(UniqueSCEVs.lookup(ID, Token));
3030 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3032 UniqueSCEVs.insert(S, Token);
3041 FoldingSetNodeID
ID;
3043 ID.AddPointer(
LHS.getOpaqueValue());
3044 ID.AddPointer(
RHS.getOpaqueValue());
3045 FoldingSetInsertToken Token;
3046 SCEV *S = UniqueSCEVs.lookup(ID, Token);
3048 S =
new (SCEVAllocator) SCEVUDivExpr(
ID.Intern(SCEVAllocator),
LHS,
RHS);
3049 UniqueSCEVs.insert(S, Token);
3058 if (j > 1 && k / j != i) Overflow =
true;
3074 if (n == 0 || n == k)
return 1;
3075 if (k > n)
return 0;
3081 for (
uint64_t i = 1; i <= k; ++i) {
3082 r =
umul_ov(r, n-(i-1), Overflow);
3091 struct FindConstantInAddMulChain {
3092 bool FoundConstant =
false;
3094 bool follow(
const SCEV *S) {
3099 bool isDone()
const {
3100 return FoundConstant;
3104 FindConstantInAddMulChain
F;
3106 ST.visitAll(StartExpr);
3107 return F.FoundConstant;
3115 "only nuw or nsw allowed");
3116 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3117 if (
Ops.size() == 1)
return Ops[0];
3119 Type *ETy =
Ops[0]->getType();
3121 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3123 "SCEVMulExpr operand types don't match!");
3128 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3129 [](
const APInt &
C) {
return C.isOne(); },
3130 [](
const APInt &
C) {
return C.isZero(); });
3141 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3146 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3147 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3152 if (
Ops.size() == 2) {
3160 const SCEV *Op0, *Op1;
3168 if (
Ops[0]->isAllOnesValue()) {
3173 bool AnyFolded =
false;
3174 for (
const SCEV *AddOp :
Add->operands()) {
3194 if (AddRec->hasNoSignedWrap()) {
3201 AddRec->getNoWrapFlags(FlagsMask));
3224 APInt C1V = LHSC->getAPInt();
3234 const SCEV *NewMul =
nullptr;
3238 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3253 if (Idx <
Ops.size()) {
3254 bool DeletedMul =
false;
3260 Ops.erase(
Ops.begin()+Idx);
3284 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3287 Ops.erase(
Ops.begin()+i);
3292 if (!LIOps.
empty()) {
3305 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3321 if (
Ops.size() == 1)
return NewRec;
3324 for (
unsigned i = 0;; ++i)
3325 if (
Ops[i] == AddRec) {
3346 bool OpsModified =
false;
3347 for (
unsigned OtherIdx = Idx+1;
3361 bool Overflow =
false;
3368 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3369 uint64_t Coeff1 =
Choose(x, 2*x - y, Overflow);
3372 z < ze && !Overflow; ++z) {
3373 uint64_t Coeff2 =
Choose(2*x - y, x-z, Overflow);
3375 if (LargerThan64Bits)
3376 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3378 Coeff = Coeff1*Coeff2;
3393 if (
Ops.size() == 2)
return NewAddRec;
3394 Ops[Idx] = NewAddRec;
3395 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3411 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3418 "SCEVURemExpr operand types don't match!");
3423 if (RHSC->getValue()->isOne())
3424 return getZero(LHS->getType());
3427 if (RHSC->getAPInt().isPowerOf2()) {
3428 Type *FullTy = LHS->getType();
3444 assert(!LHS->getType()->isPointerTy() &&
3445 "SCEVUDivExpr operand can't be pointer!");
3446 assert(LHS->getType() == RHS->getType() &&
3447 "SCEVUDivExpr operand types don't match!");
3458 if (RHSC->getValue()->isOne())
3463 if (!RHSC->getValue()->isZero()) {
3467 Type *Ty = LHS->getType();
3468 unsigned LZ = RHSC->getAPInt().countl_zero();
3472 if (!RHSC->getAPInt().isPowerOf2())
3480 const APInt &StepInt = Step->getAPInt();
3481 const APInt &DivInt = RHSC->getAPInt();
3482 if (!StepInt.
urem(DivInt) &&
3488 for (
const SCEV *
Op : AR->operands())
3494 const APInt *StartRem;
3507 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3511 const SCEV *NewStart =
3513 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3515 const SCEV *NewLHS =
3525 if (M->hasNoUnsignedWrap()) {
3527 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3528 const SCEV *
Op = M->getOperand(i);
3555 if (
auto *DivisorConstant =
3557 bool Overflow =
false;
3559 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3570 if (
A->hasNoUnsignedWrap()) {
3572 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3579 if (
Operands.size() ==
A->getNumOperands())
3591 const APInt &
N = RHSC->getAPInt();
3592 const APInt *NMinusM, *M;
3596 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3597 *NMinusM ==
N - *M) {
3606 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3616 return getZero(LHS->getType());
3620 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3621 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3622 if (
Mul->getOperand(i) == RHS) {
3633 const SCEV *NewLHS, *NewRHS;
3638 return getOrCreateUDivExpr(LHS, RHS);
3658 if (StepChrec->getLoop() == L) {
3677 "SCEVAddRecExpr operand types don't match!");
3678 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3682 "SCEVAddRecExpr operand is not available at loop entry!");
3700 const Loop *NestedLoop = NestedAR->getLoop();
3701 if (L->contains(NestedLoop)
3704 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3706 Operands[0] = NestedAR->getStart();
3710 bool AllInvariant =
all_of(
3722 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3733 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3743 return getOrCreateAddRecExpr(
Operands, L, Flags);
3759 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3763 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3777 bool FirstIter =
true;
3779 for (
SCEVUse IndexExpr : IndexExprs) {
3786 Offsets.push_back(FieldOffset);
3789 CurTy = STy->getTypeAtIndex(Index);
3794 "The first index of a GEP indexes a pointer");
3795 CurTy = SrcElementTy;
3806 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3807 Offsets.push_back(LocalOffset);
3812 if (Offsets.empty())
3825 "GEP should not change type mid-flight.");
3829SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3834 ID.AddPointer(
Op.getOpaqueValue());
3836 return UniqueSCEVs.lookup(ID, Token);
3846 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3847 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3848 if (
Ops.size() == 1)
return Ops[0];
3851 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3853 "Operand types don't match!");
3856 "min/max should be consistently pointerish");
3882 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3884 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3889 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3891 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3897 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3903 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3908 if (Idx <
Ops.size()) {
3909 bool DeletedAny =
false;
3910 while (
Ops[Idx]->getSCEVType() == Kind) {
3912 Ops.erase(
Ops.begin()+Idx);
3930 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3931 if (
Ops[i] ==
Ops[i + 1] ||
3932 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3935 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3938 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3941 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3947 if (
Ops.size() == 1)
return Ops[0];
3949 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
3956 ID.AddPointer(
Op.getOpaqueValue());
3958 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
3960 return ExistingSCEV;
3963 SCEV *S =
new (SCEVAllocator)
3966 UniqueSCEVs.insert(S, Token);
3974class SCEVSequentialMinMaxDeduplicatingVisitor final
3975 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
3976 std::optional<const SCEV *>> {
3977 using RetVal = std::optional<const SCEV *>;
3984 bool canRecurseInto(
SCEVTypes Kind)
const {
3987 return RootKind == Kind || NonSequentialRootKind == Kind;
3992 if (!SeenOps.
insert(S).second)
3993 return std::nullopt;
3997 if (!canRecurseInto(Kind))
4007 return std::nullopt;
4017 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4019 : SE(SE), RootKind(RootKind),
4020 NonSequentialRootKind(
4021 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4025 SmallVectorImpl<SCEVUse> &NewOps) {
4030 for (
const SCEV *
Op : OrigOps) {
4035 Ops.emplace_back(*NewOp);
4039 NewOps = std::move(
Ops);
4083struct SCEVPoisonCollector {
4084 bool LookThroughMaybePoisonBlocking;
4085 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4086 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4087 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4089 bool follow(
const SCEV *S) {
4090 if (!LookThroughMaybePoisonBlocking &&
4100 bool isDone()
const {
return false; }
4110 SCEVPoisonCollector PC1(
true);
4115 if (PC1.MaybePoison.
empty())
4121 SCEVPoisonCollector PC2(
false);
4131 SCEVPoisonCollector PC(
false);
4154 while (!Worklist.
empty()) {
4156 if (!Visited.
insert(V).second)
4160 if (Visited.
size() > 16)
4176 if (PDI->isDisjoint())
4183 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4190 if (
I->hasPoisonGeneratingAnnotations())
4201 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4202 "Not a SCEVSequentialMinMaxExpr!");
4203 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4204 if (
Ops.size() == 1)
4208 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4210 "Operand types don't match!");
4213 "min/max should be consistently pointerish");
4221 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4228 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4238 bool DeletedAny =
false;
4239 while (Idx <
Ops.size()) {
4240 if (
Ops[Idx]->getSCEVType() != Kind) {
4245 Ops.erase(
Ops.begin() + Idx);
4246 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4247 SMME->operands().end());
4255 const SCEV *SaturationPoint;
4266 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4267 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4279 Ops.erase(
Ops.begin() + i);
4284 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4285 Ops.erase(
Ops.begin() + i);
4295 ID.AddPointer(
Op.getOpaqueValue());
4297 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
4299 return ExistingSCEV;
4303 SCEV *S =
new (SCEVAllocator)
4306 UniqueSCEVs.insert(S, Token);
4354 if (
Size.isScalable())
4375 "Cannot get offset for structure containing scalable vector types");
4389 if (
SCEV *S = UniqueSCEVs.lookup(ID, Token)) {
4391 "Stale SCEVUnknown in uniquing map!");
4394 SCEV *S =
new (SCEVAllocator)
SCEVUnknown(ID.Intern(SCEVAllocator), V,
this,
4397 UniqueSCEVs.insert(S, Token);
4412 return Ty->isIntOrPtrTy();
4419 if (Ty->isPointerTy())
4430 if (Ty->isIntegerTy())
4434 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4446 bool PreciseA, PreciseB;
4447 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4448 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4449 if (!PreciseA || !PreciseB)
4452 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4453 DT.dominates(ScopeB, ScopeA);
4457 return CouldNotCompute.get();
4460bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4463 return SU && SU->getValue() ==
nullptr;
4466 return !ContainsNulls;
4471 if (
I != HasRecMap.end())
4476 HasRecMap.insert({S, FoundAddRec});
4484 if (
SI == ExprValueMap.
end())
4486 return SI->second.getArrayRef();
4492void ScalarEvolution::eraseValueFromMap(
Value *V) {
4494 if (
I != ValueExprMap.end()) {
4495 auto EVIt = ExprValueMap.find(
I->second);
4496 bool Removed = EVIt->second.remove(V);
4498 assert(Removed &&
"Value not in ExprValueMap?");
4499 ValueExprMap.erase(
I);
4503void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4507 auto It = ValueExprMap.find_as(V);
4508 if (It == ValueExprMap.end()) {
4510 ExprValueMap[S].insert(V);
4521 return createSCEVIter(V);
4528 if (
I != ValueExprMap.end()) {
4529 const SCEV *S =
I->second;
4530 assert(checkValidity(S) &&
4531 "existing SCEV has not been properly invalidated");
4544 Type *Ty = V->getType();
4560 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4573 return (
const SCEV *)
nullptr;
4579 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4583 Type *Ty = V->getType();
4589 assert(
P->getType()->isPointerTy());
4604 if (AddOp->getType()->isPointerTy()) {
4605 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4623 return getZero(LHS->getType());
4628 if (RHS->getType()->isPointerTy()) {
4629 if (!LHS->getType()->isPointerTy() ||
4639 const bool RHSIsNotMinSigned =
4670 Type *SrcTy = V->getType();
4671 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4672 "Cannot truncate or zero extend with non-integer arguments!");
4682 Type *SrcTy = V->getType();
4683 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4684 "Cannot truncate or zero extend with non-integer arguments!");
4693 Type *SrcTy = V->getType();
4694 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4695 "Cannot noop or zero extend with non-integer arguments!");
4697 "getNoopOrZeroExtend cannot truncate!");
4704 Type *SrcTy = V->getType();
4705 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4706 "Cannot noop or sign extend with non-integer arguments!");
4708 "getNoopOrSignExtend cannot truncate!");
4715 Type *SrcTy = V->getType();
4716 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4717 "Cannot noop or any extend with non-integer arguments!");
4719 "getNoopOrAnyExtend cannot truncate!");
4726 Type *SrcTy = V->getType();
4727 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4728 "Cannot truncate or noop with non-integer arguments!");
4730 "getTruncateOrNoop cannot extend!");
4738 const SCEV *PromotedLHS = LHS;
4739 const SCEV *PromotedRHS = RHS;
4759 assert(!
Ops.empty() &&
"At least one operand must be!");
4761 if (
Ops.size() == 1)
4765 Type *MaxType =
nullptr;
4771 assert(MaxType &&
"Failed to find maximum type!");
4784 if (!V->getType()->isPointerTy())
4789 V = AddRec->getStart();
4791 const SCEV *PtrOp =
nullptr;
4792 for (
const SCEV *AddOp :
Add->operands()) {
4793 if (AddOp->getType()->isPointerTy()) {
4794 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4798 assert(PtrOp &&
"Must have pointer op");
4810 for (
User *U :
I->users()) {
4812 if (Visited.
insert(UserInsn).second)
4826 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4827 bool IgnoreOtherLoops =
true) {
4830 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4832 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4837 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4839 SeenLoopVariantSCEVUnknown =
true;
4843 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4847 SeenOtherLoops =
true;
4851 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4853 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4856 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4857 : SCEVRewriteVisitor(SE),
L(
L) {}
4860 bool SeenLoopVariantSCEVUnknown =
false;
4861 bool SeenOtherLoops =
false;
4870 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4871 SCEVPostIncRewriter
Rewriter(L, SE);
4873 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4878 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4880 SeenLoopVariantSCEVUnknown =
true;
4884 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4888 SeenOtherLoops =
true;
4892 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4894 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4897 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4898 : SCEVRewriteVisitor(SE),
L(
L) {}
4901 bool SeenLoopVariantSCEVUnknown =
false;
4902 bool SeenOtherLoops =
false;
4908class SCEVBackedgeConditionFolder
4911 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4912 ScalarEvolution &SE) {
4913 bool IsPosBECond =
false;
4914 Value *BECond =
nullptr;
4915 if (BasicBlock *Latch =
L->getLoopLatch()) {
4917 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
4918 "Both outgoing branches should not target same header!");
4919 BECond = BI->getCondition();
4920 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
4925 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
4929 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4930 const SCEV *
Result = Expr;
4935 switch (
I->getOpcode()) {
4936 case Instruction::Select: {
4938 std::optional<const SCEV *> Res =
4939 compareWithBackedgeCondition(
SI->getCondition());
4947 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
4958 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
4959 bool IsPosBECond, ScalarEvolution &SE)
4960 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
4961 IsPositiveBECond(IsPosBECond) {}
4963 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
4967 Value *BackedgeCond =
nullptr;
4969 bool IsPositiveBECond;
4972std::optional<const SCEV *>
4973SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
4978 if (BackedgeCond == IC)
4981 return std::nullopt;
4986 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4987 ScalarEvolution &SE) {
4993 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5000 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5010 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5011 : SCEVRewriteVisitor(SE),
L(
L) {}
5019void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5035 const APInt &BECountAP = BECountMax->getAPInt();
5036 unsigned NoOverflowBitWidth =
5045ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5055 if (!SignedWrapViaInductionTried.insert(AR).second)
5080 AC.assumptions().empty())
5088 const SCEV *OverflowLimit =
5090 if (OverflowLimit &&
5098ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5108 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5133 AC.assumptions().empty())
5142 const SCEV *OverflowLimit =
5171 IsNSW = OBO->hasNoSignedWrap();
5172 IsNUW = OBO->hasNoUnsignedWrap();
5178 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5190 return std::nullopt;
5196 switch (
Op->getOpcode()) {
5197 case Instruction::Add:
5198 case Instruction::Sub:
5199 case Instruction::Mul:
5200 case Instruction::UDiv:
5201 case Instruction::URem:
5202 case Instruction::And:
5203 case Instruction::AShr:
5204 case Instruction::Shl:
5207 case Instruction::Or: {
5210 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5220 case Instruction::Xor:
5224 if (RHSC->getValue().isSignMask())
5225 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5227 if (V->getType()->isIntegerTy(1))
5228 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5231 case Instruction::LShr:
5240 if (SA->getValue().ult(
BitWidth)) {
5242 ConstantInt::get(SA->getContext(),
5244 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5249 case Instruction::ExtractValue: {
5251 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5259 bool Signed = WO->isSigned();
5262 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5267 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5278 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5279 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5281 return std::nullopt;
5307 if (
Op == SymbolicPHI)
5312 if (SourceBits != NewBits)
5330 if (!L || L->getHeader() != PN->
getParent())
5388std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5389ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5397 assert(L &&
"Expecting an integer loop header phi");
5402 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5403 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5404 Value *
V = PN->getIncomingValue(i);
5405 if (
L->contains(PN->getIncomingBlock(i))) {
5408 }
else if (BEValueV != V) {
5412 }
else if (!StartValueV) {
5414 }
else if (StartValueV != V) {
5415 StartValueV =
nullptr;
5419 if (!BEValueV || !StartValueV)
5420 return std::nullopt;
5422 const SCEV *BEValue =
getSCEV(BEValueV);
5429 return std::nullopt;
5433 unsigned FoundIndex =
Add->getNumOperands();
5434 Type *TruncTy =
nullptr;
5436 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5439 if (FoundIndex == e) {
5444 if (FoundIndex ==
Add->getNumOperands())
5445 return std::nullopt;
5449 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5450 if (i != FoundIndex)
5451 Ops.push_back(
Add->getOperand(i));
5457 return std::nullopt;
5510 const SCEV *StartVal =
getSCEV(StartValueV);
5511 const SCEV *PHISCEV =
5538 auto getExtendedExpr = [&](
const SCEV *Expr,
5539 bool CreateSignExtend) ->
const SCEV * {
5542 const SCEV *ExtendedExpr =
5545 return ExtendedExpr;
5553 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5554 const SCEV *ExtendedExpr) ->
bool {
5555 return Expr != ExtendedExpr &&
5559 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5560 if (PredIsKnownFalse(StartVal, StartExtended)) {
5562 return std::nullopt;
5567 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5568 if (PredIsKnownFalse(Accum, AccumExtended)) {
5570 return std::nullopt;
5573 auto AppendPredicate = [&](
const SCEV *Expr,
5574 const SCEV *ExtendedExpr) ->
void {
5575 if (Expr != ExtendedExpr &&
5583 AppendPredicate(StartVal, StartExtended);
5584 AppendPredicate(Accum, AccumExtended);
5592 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5593 std::make_pair(NewAR, Predicates);
5595 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5599std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5604 return std::nullopt;
5607 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5608 if (
I != PredicatedSCEVRewrites.end()) {
5609 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5612 if (Rewrite.first == SymbolicPHI)
5613 return std::nullopt;
5617 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5621 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5622 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5627 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5628 return std::nullopt;
5648 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5649 if (Expr1 != Expr2 &&
5650 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5651 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5668const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5670 Value *StartValueV) {
5673 assert(BEValueV && StartValueV);
5679 if (BO->Opcode != Instruction::Add)
5682 const SCEV *Accum =
nullptr;
5683 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5685 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5699 insertValueToMap(PN, PHISCEV);
5702 inferNoWrapViaConstantRanges(AR);
5709 "Accum is defined outside L, but is not invariant?");
5710 if (isAddRecNeverPoison(BEInst, L))
5717const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5725 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5731 }
else if (BEValueV != V) {
5735 }
else if (!StartValueV) {
5737 }
else if (StartValueV != V) {
5738 StartValueV =
nullptr;
5742 if (!BEValueV || !StartValueV)
5745 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5746 "PHI node already processed?");
5750 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5755 insertValueToMap(PN, SymbolicName);
5759 const SCEV *BEValue =
getSCEV(BEValueV);
5769 unsigned FoundIndex =
Add->getNumOperands();
5770 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5771 if (
Add->getOperand(i) == SymbolicName)
5772 if (FoundIndex == e) {
5777 if (FoundIndex !=
Add->getNumOperands()) {
5780 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5781 if (i != FoundIndex)
5782 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5794 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5801 if (
GEP->getOperand(0) == PN) {
5802 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
5820 const SCEV *StartVal =
getSCEV(StartValueV);
5821 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5826 forgetMemoizedResults({SymbolicName});
5827 insertValueToMap(PN, PHISCEV);
5830 inferNoWrapViaConstantRanges(AR);
5854 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5855 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5857 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5858 const SCEV *StartVal =
getSCEV(StartValueV);
5859 if (Start == StartVal) {
5863 forgetMemoizedResults({SymbolicName});
5864 insertValueToMap(PN, Shifted);
5874 eraseValueFromMap(PN);
5889 Use &LeftUse =
Merge->getOperandUse(0);
5890 Use &RightUse =
Merge->getOperandUse(1);
5926 assert(IDom &&
"At least the entry block should dominate PN");
5934const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
5939 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
5956 CommonInst = IncomingInst;
5972ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
5978 const SCEV *CommonSCEV =
getSCEV(CommonInst);
5979 bool SCEVExprsIdentical =
5981 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
5982 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
5985const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
5986 if (
const SCEV *S = createAddRecFromPHI(PN))
5996 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
5999 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6008 struct FindClosure {
6009 const SCEV *OperandToFind;
6015 bool canRecurseInto(
SCEVTypes Kind)
const {
6018 return RootKind == Kind || NonSequentialRootKind == Kind ||
6023 : OperandToFind(OperandToFind), RootKind(RootKind),
6024 NonSequentialRootKind(
6028 bool follow(
const SCEV *S) {
6029 Found = S == OperandToFind;
6031 return !isDone() && canRecurseInto(S->
getSCEVType());
6034 bool isDone()
const {
return Found; }
6037 FindClosure FC(OperandToFind, RootKind);
6042std::optional<const SCEV *>
6043ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6053 switch (ICI->getPredicate()) {
6067 bool Signed = ICI->isSigned();
6068 const SCEV *LA =
getSCEV(TrueVal);
6076 if (LA == LS &&
RA == RS)
6078 if (LA == RS &&
RA == LS)
6081 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6082 if (
Op->getType()->isPointerTy()) {
6093 LS = CoerceOperand(LS);
6094 RS = CoerceOperand(RS);
6118 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6119 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6133 X = ZExt->getOperand();
6135 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6146 return std::nullopt;
6149static std::optional<const SCEV *>
6151 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6155 "Unexpected operands of a select.");
6167 return std::nullopt;
6182static std::optional<const SCEV *>
6186 return std::nullopt;
6189 const auto *SETrue = SE->
getSCEV(TrueVal);
6190 const auto *SEFalse = SE->
getSCEV(FalseVal);
6194const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6196 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6198 V->getType() ==
TrueVal->getType() &&
6199 "Types of select hands and of the result must match.");
6202 if (!
V->getType()->isIntegerTy(1))
6205 if (std::optional<const SCEV *> S =
6218 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6222 if (std::optional<const SCEV *> S =
6223 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6229 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6235 assert(
GEP->getSourceElementType()->isSized() &&
6236 "GEP source element type must be sized");
6239 for (
Value *Index :
GEP->indices())
6244APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6247 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6250 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6252 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6255 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6273 return GetShiftedByZeros(TZ);
6283 return GetShiftedByZeros(TZ);
6287 if (
M->hasNoUnsignedWrap()) {
6290 for (
const SCEV *Operand :
M->operands().drop_front())
6298 for (
const SCEV *Operand :
M->operands())
6300 return GetShiftedByZeros(TZ);
6305 if (
N->hasNoUnsignedWrap())
6306 return GetGCDMultiple(
N);
6309 for (
const SCEV *Operand :
N->operands().drop_front())
6311 return GetShiftedByZeros(TZ);
6328 CtxI = &*F.getEntryBlock().begin();
6335 .allowEphemerals(
true))
6336 .countMinTrailingZeros();
6337 return GetShiftedByZeros(
Known);
6350 return getConstantMultipleImpl(S, CtxI);
6352 auto I = ConstantMultipleCache.find(S);
6353 if (
I != ConstantMultipleCache.end())
6356 APInt Result = getConstantMultipleImpl(S, CtxI);
6357 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6358 assert(InsertPair.second &&
"Should insert a new key");
6359 return InsertPair.first->second;
6376 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6379 if (std::optional<ConstantRange>
Range = CB->getRange())
6383 if (std::optional<ConstantRange>
Range =
A->getRange())
6386 return std::nullopt;
6393 UnsignedRanges.erase(AddRec);
6394 SignedRanges.erase(AddRec);
6395 ConstantMultipleCache.erase(AddRec);
6400getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6426 Value *Start, *Step;
6433 assert(L && L->getHeader() ==
P->getParent());
6446 case Instruction::AShr:
6447 case Instruction::LShr:
6448 case Instruction::Shl:
6463 KnownStep.getBitWidth() ==
BitWidth);
6466 auto MaxShiftAmt = KnownStep.getMaxValue();
6468 bool Overflow =
false;
6469 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6476 case Instruction::AShr: {
6484 if (KnownStart.isNonNegative())
6487 KnownStart.getMaxValue() + 1);
6488 if (KnownStart.isNegative())
6491 KnownEnd.getMaxValue() + 1);
6494 case Instruction::LShr: {
6503 KnownStart.getMaxValue() + 1);
6505 case Instruction::Shl: {
6509 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6510 return ConstantRange(KnownStart.getMinValue(),
6511 KnownEnd.getMaxValue() + 1);
6536 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6543ScalarEvolution::getRangeRefIter(
const SCEV *S,
6544 ScalarEvolution::RangeSignHint SignHint) {
6545 DenseMap<const SCEV *, ConstantRange> &Cache =
6546 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6549 SmallPtrSet<const SCEV *, 8> Seen;
6553 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6554 if (!Seen.
insert(Expr).second)
6587 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6588 const SCEV *
P = WorkList[
I];
6592 for (
const SCEV *
Op :
P->operands())
6605 if (!WorkList.
empty()) {
6610 getRangeRef(
P, SignHint);
6614 return getRangeRef(S, SignHint, 0);
6617const APInt *ScalarEvolution::getConstantAPIntOrNull(
const SCEV *S) {
6619 return &
C->getAPInt();
6627 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6628 DenseMap<const SCEV *, ConstantRange> &Cache =
6629 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6636 auto I = Cache.
find(S);
6637 if (
I != Cache.
end())
6641 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6646 return getRangeRefIter(S, SignHint);
6649 ConstantRange ConservativeResult(
BitWidth,
true);
6650 using OBO = OverflowingBinaryOperator;
6654 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6658 ConservativeResult =
6665 ConservativeResult = ConstantRange(
6681 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6688 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6695 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6700 return setRange(Cast, SignHint,
X);
6705 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6706 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6708 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6709 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6710 ConservativeResult =
6711 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6713 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6714 unsigned WrapType = OBO::AnyWrap;
6715 if (
Add->hasNoSignedWrap())
6716 WrapType |= OBO::NoSignedWrap;
6717 if (
Add->hasNoUnsignedWrap())
6718 WrapType |= OBO::NoUnsignedWrap;
6720 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6722 return setRange(
Add, SignHint,
6723 ConservativeResult.intersectWith(
X, RangeType));
6727 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6729 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6730 return setRange(
Mul, SignHint,
6731 ConservativeResult.intersectWith(
X, RangeType));
6735 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6736 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6737 return setRange(UDiv, SignHint,
6738 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6746 if (!UnsignedMinValue.
isZero())
6747 ConservativeResult = ConservativeResult.intersectWith(
6748 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6757 bool AllNonNeg =
true;
6758 bool AllNonPos =
true;
6759 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6766 ConservativeResult = ConservativeResult.intersectWith(
6771 ConservativeResult = ConservativeResult.intersectWith(
6780 const SCEV *MaxBEScev =
6794 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6796 ConservativeResult =
6797 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6800 auto RangeFromFactoring = getRangeViaFactoring(
6802 ConservativeResult =
6803 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6809 const SCEV *SymbolicMaxBECount =
6814 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6815 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6816 ConservativeResult =
6817 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6822 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6832 ID = Intrinsic::umax;
6835 ID = Intrinsic::smax;
6839 ID = Intrinsic::umin;
6842 ID = Intrinsic::smin;
6849 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6850 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6852 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6853 return setRange(S, SignHint,
6854 ConservativeResult.intersectWith(
X, RangeType));
6863 ConservativeResult =
6864 ConservativeResult.intersectWith(*MDRange, RangeType);
6869 auto CR = getRangeForUnknownRecurrence(U);
6870 ConservativeResult = ConservativeResult.intersectWith(CR);
6881 if (
U->getType()->isPointerTy()) {
6884 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
6885 int ptrIdxDiff = ptrSize -
BitWidth;
6886 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
6892 if (!
Known.Zero.getHiBits(NS).isZero())
6893 Known.Zero.setHighBits(NS);
6894 if (!
Known.One.getHiBits(NS).isZero())
6895 Known.One.setHighBits(NS);
6898 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
6899 ConservativeResult = ConservativeResult.intersectWith(
6900 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
6903 ConservativeResult = ConservativeResult.intersectWith(
6908 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6912 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
6913 DL, CanBeNull,
nullptr);
6929 ConservativeResult = ConservativeResult.intersectWith(
6939 return getRangeRef(AR, SignHint,
Depth + 1);
6943 ConstantRange RangeFromOps(
BitWidth,
false);
6945 for (
const auto &
Op :
Phi->operands()) {
6947 RangeFromOps = RangeFromOps.unionWith(OpRange);
6949 if (RangeFromOps.isFullSet())
6952 ConservativeResult =
6953 ConservativeResult.intersectWith(RangeFromOps, RangeType);
6959 if (
II->getIntrinsicID() == Intrinsic::vscale) {
6961 ConservativeResult = ConservativeResult.difference(Disallowed);
6964 return setRange(U, SignHint, std::move(ConservativeResult));
6970 return setRange(S, SignHint, std::move(ConservativeResult));
6978static std::pair<ConstantRange, bool>
6986 if (Step == 0 || MaxBECount == 0)
6987 return {StartRange,
true};
6993 return {ConstantRange::getFull(
BitWidth),
false};
7009 return {ConstantRange::getFull(
BitWidth),
false};
7022 APInt MovedBoundary;
7027 MovedBoundary = StartLower - std::move(
Offset);
7030 MovedBoundary = StartUpper + std::move(
Offset);
7034 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7041 if (StartRange.
contains(MovedBoundary))
7042 return {ConstantRange::getFull(
BitWidth),
false};
7045 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7047 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7055std::pair<ConstantRange, SCEV::NoWrapFlags>
7056ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7057 const APInt &MaxBECount) {
7061 "mismatched bit widths");
7070 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7072 StartSRange, MaxBECount,
7074 ConstantRange SR = SR1.unionWith(SR2);
7091ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7093 ScalarEvolution::RangeSignHint SignHint) {
7094 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7096 "This only works for non-self-wrapping AddRecs!");
7097 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7101 return ConstantRange::getFull(
BitWidth);
7109 return ConstantRange::getFull(
BitWidth);
7113 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7115 MaxItersWithoutWrap))
7116 return ConstantRange::getFull(
BitWidth);
7137 ConstantRange StartRange = getRangeRef(Start, SignHint);
7138 ConstantRange EndRange = getRangeRef(End, SignHint);
7139 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7143 return RangeBetween;
7148 return ConstantRange::getFull(
BitWidth);
7151 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7152 return RangeBetween;
7154 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7155 return RangeBetween;
7156 return ConstantRange::getFull(
BitWidth);
7161 const APInt &MaxBECount) {
7168 "mismatched bit widths");
7170 struct SelectPattern {
7171 Value *Condition =
nullptr;
7175 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7177 std::optional<unsigned> CastOp;
7191 CastOp = SCast->getSCEVType();
7192 S = SCast->getOperand();
7195 using namespace llvm::PatternMatch;
7202 Condition =
nullptr;
7234 bool isRecognized() {
return Condition !=
nullptr; }
7237 SelectPattern StartPattern(*
this,
BitWidth, Start);
7238 if (!StartPattern.isRecognized())
7239 return ConstantRange::getFull(
BitWidth);
7241 SelectPattern StepPattern(*
this,
BitWidth, Step);
7242 if (!StepPattern.isRecognized())
7243 return ConstantRange::getFull(
BitWidth);
7245 if (StartPattern.Condition != StepPattern.Condition) {
7249 return ConstantRange::getFull(
BitWidth);
7260 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7261 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7262 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7263 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7265 ConstantRange TrueRange =
7266 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7267 ConstantRange FalseRange =
7268 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7280 PDI && PDI->isDisjoint()) {
7295ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7308 SmallPtrSet<const SCEV *, 16> Visited;
7310 auto pushOp = [&](
const SCEV *S) {
7311 if (!Visited.
insert(S).second)
7314 if (Visited.
size() > 30) {
7325 while (!Worklist.
empty()) {
7327 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7328 if (!Bound || DT.dominates(Bound, DefI))
7335 return Bound ? Bound : &*F.getEntryBlock().begin();
7341 return getDefiningScopeBound(
Ops, Discard);
7344bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7346 if (
A->getParent() ==
B->getParent() &&
7351 auto *BLoop = LI.getLoopFor(
B->getParent());
7352 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7353 BLoop->getLoopPreheader() ==
A->getParent() &&
7355 A->getParent()->end()) &&
7363 SCEVPoisonCollector PC(
true);
7365 return PC.MaybePoison.
empty();
7368bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7378bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7395 for (
const Use &
Op :
I->operands()) {
7401 auto *DefI = getDefiningScopeBound(SCEVOps);
7402 return isGuaranteedToTransferExecutionTo(DefI,
I);
7405bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7407 if (isSCEVExprNeverPoison(
I))
7418 auto *ExitingBB =
L->getExitingBlock();
7422 SmallPtrSet<const Value *, 16> KnownPoison;
7431 while (!Worklist.
empty()) {
7434 for (
const Use &U :
Poison->uses()) {
7437 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7441 if (KnownPoison.
insert(PoisonUser).second)
7449ScalarEvolution::LoopProperties
7450ScalarEvolution::getLoopProperties(
const Loop *L) {
7451 using LoopProperties = ScalarEvolution::LoopProperties;
7453 auto Itr = LoopPropertiesCache.find(L);
7454 if (Itr == LoopPropertiesCache.end()) {
7457 return !
SI->isSimple();
7467 return I->mayWriteToMemory();
7470 LoopProperties LP = {
true,
7473 for (
auto *BB :
L->getBlocks())
7474 for (
auto &
I : *BB) {
7476 LP.HasNoAbnormalExits =
false;
7477 if (HasSideEffects(&
I))
7478 LP.HasNoSideEffects =
false;
7479 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7483 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7484 assert(InsertPair.second &&
"We just checked!");
7485 Itr = InsertPair.first;
7498const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7504 Stack.emplace_back(V,
false);
7505 while (!Stack.empty()) {
7506 auto E = Stack.back();
7507 Value *CurV = E.getPointer();
7515 const SCEV *CreatedSCEV =
nullptr;
7518 CreatedSCEV = createSCEV(CurV);
7523 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7527 insertValueToMap(CurV, CreatedSCEV);
7530 Stack.back().setInt(
true);
7533 Stack.emplace_back(
Op,
false);
7550 if (!DT.isReachableFromEntry(
I->getParent()))
7563 switch (BO->Opcode) {
7564 case Instruction::Add:
7565 case Instruction::Mul: {
7572 Ops.push_back(BO->
Op);
7576 Ops.push_back(BO->RHS);
7580 (BO->Opcode == Instruction::Add &&
7581 (NewBO->Opcode != Instruction::Add &&
7582 NewBO->Opcode != Instruction::Sub)) ||
7583 (BO->Opcode == Instruction::Mul &&
7584 NewBO->Opcode != Instruction::Mul)) {
7585 Ops.push_back(BO->LHS);
7590 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7593 Ops.push_back(BO->LHS);
7601 case Instruction::Sub:
7602 case Instruction::UDiv:
7603 case Instruction::URem:
7605 case Instruction::AShr:
7606 case Instruction::Shl:
7607 case Instruction::Xor:
7611 case Instruction::And:
7612 case Instruction::Or:
7616 case Instruction::LShr:
7623 Ops.push_back(BO->LHS);
7624 Ops.push_back(BO->RHS);
7628 switch (
U->getOpcode()) {
7629 case Instruction::Trunc:
7630 case Instruction::ZExt:
7631 case Instruction::SExt:
7632 case Instruction::PtrToAddr:
7633 case Instruction::PtrToInt:
7634 Ops.push_back(
U->getOperand(0));
7637 case Instruction::BitCast:
7639 Ops.push_back(
U->getOperand(0));
7644 case Instruction::SDiv:
7645 case Instruction::SRem:
7646 Ops.push_back(
U->getOperand(0));
7647 Ops.push_back(
U->getOperand(1));
7650 case Instruction::GetElementPtr:
7652 "GEP source element type must be sized");
7656 case Instruction::IntToPtr:
7659 case Instruction::PHI:
7690 Ops.push_back(CondICmp->getOperand(0));
7691 Ops.push_back(CondICmp->getOperand(1));
7711 case Instruction::Select: {
7713 auto CanSimplifyToUnknown = [
this,
U]() {
7731 if (CanSimplifyToUnknown())
7738 case Instruction::Call:
7739 case Instruction::Invoke:
7746 switch (
II->getIntrinsicID()) {
7747 case Intrinsic::abs:
7748 Ops.push_back(
II->getArgOperand(0));
7750 case Intrinsic::umax:
7751 case Intrinsic::umin:
7752 case Intrinsic::smax:
7753 case Intrinsic::smin:
7754 case Intrinsic::usub_sat:
7755 case Intrinsic::uadd_sat:
7756 Ops.push_back(
II->getArgOperand(0));
7757 Ops.push_back(
II->getArgOperand(1));
7759 case Intrinsic::start_loop_iterations:
7760 case Intrinsic::annotation:
7761 case Intrinsic::ptr_annotation:
7762 Ops.push_back(
II->getArgOperand(0));
7774const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7783 if (!DT.isReachableFromEntry(
I->getParent()))
7798 switch (BO->Opcode) {
7799 case Instruction::Add: {
7825 if (BO->Opcode == Instruction::Sub)
7833 if (BO->Opcode == Instruction::Sub)
7840 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7841 NewBO->Opcode != Instruction::Sub)) {
7851 case Instruction::Mul: {
7872 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7881 case Instruction::UDiv:
7885 case Instruction::URem:
7889 case Instruction::Sub: {
7892 Flags = getNoWrapFlagsFromUB(BO->
Op);
7897 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
7900 if (HasPtrLHS || HasPtrRHS) {
7905 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
7906 bool BothPtr) ->
const SCEV * {
7909 const SCEV *PtrSCEV =
getSCEV(PtrOp);
7919 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
7920 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
7928 case Instruction::And:
7934 if (CI->isMinusOne())
7936 const APInt &
A = CI->getValue();
7942 unsigned LZ =
A.countl_zero();
7943 unsigned TZ =
A.countr_zero();
7948 APInt EffectiveMask =
7950 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
7953 const SCEV *ShiftedLHS =
nullptr;
7957 unsigned MulZeros = OpC->getAPInt().countr_zero();
7958 unsigned GCD = std::min(MulZeros, TZ);
7963 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
7985 case Instruction::Or:
7994 case Instruction::Xor:
7997 if (CI->isMinusOne())
8006 if (LBO->getOpcode() == Instruction::And &&
8007 LCI->getValue() == CI->getValue())
8008 if (
const SCEVZeroExtendExpr *Z =
8011 const SCEV *Z0 =
Z->getOperand();
8018 if (CI->getValue().isMask(Z0TySize))
8024 APInt Trunc = CI->getValue().trunc(Z0TySize);
8033 case Instruction::Shl:
8051 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8060 ConstantInt *
X = ConstantInt::get(
8066 case Instruction::AShr:
8088 const SCEV *AddTruncateExpr =
nullptr;
8089 ConstantInt *ShlAmtCI =
nullptr;
8090 const SCEV *AddConstant =
nullptr;
8092 if (L &&
L->getOpcode() == Instruction::Add) {
8100 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8107 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8115 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8120 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8125 if (AddTruncateExpr && ShlAmtCI) {
8137 const APInt &ShlAmt = ShlAmtCI->
getValue();
8141 const SCEV *CompositeExpr =
8143 if (
L->getOpcode() != Instruction::Shl)
8144 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8153 switch (
U->getOpcode()) {
8154 case Instruction::Trunc:
8157 case Instruction::ZExt:
8160 case Instruction::SExt:
8170 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8171 Type *Ty =
U->getType();
8179 case Instruction::BitCast:
8185 case Instruction::PtrToAddr: {
8192 case Instruction::PtrToInt:
8196 case Instruction::IntToPtr:
8200 case Instruction::SDiv:
8207 case Instruction::SRem:
8214 case Instruction::GetElementPtr:
8217 case Instruction::PHI:
8220 case Instruction::Select:
8221 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8224 case Instruction::Call:
8225 case Instruction::Invoke:
8230 switch (
II->getIntrinsicID()) {
8231 case Intrinsic::abs:
8235 case Intrinsic::umax:
8239 case Intrinsic::umin:
8243 case Intrinsic::smax:
8247 case Intrinsic::smin:
8251 case Intrinsic::usub_sat: {
8252 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8253 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8257 case Intrinsic::uadd_sat: {
8258 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8259 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8263 case Intrinsic::start_loop_iterations:
8264 case Intrinsic::annotation:
8265 case Intrinsic::ptr_annotation:
8269 case Intrinsic::vscale:
8289 auto *ExitCountType = ExitCount->
getType();
8290 assert(ExitCountType->isIntegerTy());
8292 1 + ExitCountType->getScalarSizeInBits());
8305 auto CanAddOneWithoutOverflow = [&]() {
8307 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8318 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8348 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8349 assert(L->isLoopExiting(ExitingBlock) &&
8350 "Exiting block must actually branch out of the loop!");
8359 const auto *MaxExitCount =
8367 L->getExitingBlocks(ExitingBlocks);
8370 if (ExitingBlocks.
empty() ||
8386 const LoopGuards &Guards) {
8390 const SCEV *TCExpr =
8398 : (
unsigned)Multiple.getZExtValue();
8402 const SCEV *ExitCount) {
8424 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8425 assert(L->isLoopExiting(ExitingBlock) &&
8426 "Exiting block must actually branch out of the loop!");
8436 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8438 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8440 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8450 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8453 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8456 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8464 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8471 return getBackedgeTakenInfo(L).getExact(L,
this);
8473 return getBackedgeTakenInfo(L).getConstantMax(
this);
8475 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8482 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8487 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8491 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8501 for (
PHINode &PN : Header->phis())
8502 if (Visited.
insert(&PN).second)
8506ScalarEvolution::BackedgeTakenInfo &
8507ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8508 auto &BTI = getBackedgeTakenInfo(L);
8509 if (BTI.hasFullInfo())
8512 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8515 return Pair.first->second;
8517 BackedgeTakenInfo
Result =
8518 computeBackedgeTakenCount(L,
true);
8520 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8523ScalarEvolution::BackedgeTakenInfo &
8524ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8530 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8531 BackedgeTakenCounts.try_emplace(L);
8533 return Pair.first->second;
8538 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8545 if (
Result.hasAnyInfo()) {
8548 auto LoopUsersIt = LoopUsers.find(L);
8549 if (LoopUsersIt != LoopUsers.end())
8551 forgetMemoizedResults(ToForget);
8554 for (PHINode &PN :
L->getHeader()->phis())
8555 ConstantEvolutionLoopExitValue.erase(&PN);
8563 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8572 BackedgeTakenCounts.clear();
8573 PredicatedBackedgeTakenCounts.clear();
8574 BECountUsers.clear();
8575 LoopPropertiesCache.clear();
8576 ConstantEvolutionLoopExitValue.clear();
8577 ValueExprMap.clear();
8578 ValuesAtScopes.clear();
8579 ValuesAtScopesUsers.clear();
8580 LoopDispositions.clear();
8581 BlockDispositions.clear();
8582 UnsignedRanges.clear();
8583 SignedRanges.clear();
8584 ExprValueMap.clear();
8586 ConstantMultipleCache.clear();
8587 PredicatedSCEVRewrites.clear();
8589 FoldCacheUser.clear();
8591void ScalarEvolution::visitAndClearUsers(
8595 while (!Worklist.
empty()) {
8602 if (It != ValueExprMap.
end()) {
8604 eraseValueFromMap(It->first);
8606 ConstantEvolutionLoopExitValue.erase(PN);
8620 while (!LoopWorklist.
empty()) {
8624 forgetBackedgeTakenCounts(CurrL,
false);
8625 forgetBackedgeTakenCounts(CurrL,
true);
8628 PredicatedSCEVRewrites.remove_if(
8629 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8631 auto LoopUsersItr = LoopUsers.find(CurrL);
8632 if (LoopUsersItr != LoopUsers.end())
8637 visitAndClearUsers(Worklist, Visited, ToForget);
8639 LoopPropertiesCache.erase(CurrL);
8642 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8644 forgetMemoizedResults(ToForget);
8661 visitAndClearUsers(Worklist, Visited, ToForget);
8663 forgetMemoizedResults(ToForget);
8671 auto InvalidateValue = [&](
Value *Val) {
8675 struct InvalidationRootCollector {
8679 InvalidationRootCollector(
Loop *L) : L(L) {}
8681 bool follow(
const SCEV *S) {
8687 if (L->contains(AddRec->
getLoop()))
8692 bool isDone()
const {
return false; }
8695 InvalidationRootCollector
C(L);
8697 forgetMemoizedResults(
C.Roots);
8720 BlockDispositions.clear();
8721 LoopDispositions.clear();
8738 while (!Worklist.
empty()) {
8740 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8741 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8742 if (!LoopDispoRemoved && !BlockDispoRemoved)
8744 auto Users = SCEVUsers.find(Curr);
8745 if (
Users != SCEVUsers.end())
8758const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8762 if (!isComplete() || ExitNotTaken.
empty())
8773 for (
const auto &ENT : ExitNotTaken) {
8774 const SCEV *BECount = ENT.ExactNotTaken;
8777 "We should only have known counts for exiting blocks that dominate "
8780 Ops.push_back(BECount);
8785 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8786 "Predicate should be always true!");
8795const ScalarEvolution::ExitNotTakenInfo *
8796ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8797 const BasicBlock *ExitingBlock,
8798 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8799 for (
const auto &ENT : ExitNotTaken)
8800 if (ENT.ExitingBlock == ExitingBlock) {
8801 if (ENT.hasAlwaysTruePredicate())
8803 else if (Predicates) {
8813const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8815 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8816 if (!getConstantMax())
8819 for (
const auto &ENT : ExitNotTaken)
8820 if (!ENT.hasAlwaysTruePredicate()) {
8828 "No point in having a non-constant max backedge taken count!");
8829 return getConstantMax();
8832const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8834 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8842 for (
const auto &ENT : ExitNotTaken) {
8843 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8846 "We should only have known counts for exiting blocks that "
8852 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8853 "Predicate should be always true!");
8856 if (ExitCounts.
empty())
8865bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8867 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8868 return !ENT.hasAlwaysTruePredicate();
8870 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8886 this->ExactNotTaken = E = ConstantMaxNotTaken;
8887 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8892 "Exact is not allowed to be less precise than Constant Max");
8895 "Exact is not allowed to be less precise than Symbolic Max");
8898 "Symbolic Max is not allowed to be less precise than Constant Max");
8901 "No point in having a non-constant max backedge taken count!");
8903 for (
const auto PredList : PredLists)
8904 for (
const auto *
P : PredList) {
8912 "Backedge count should be int");
8915 "Max backedge count should be int");
8928ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8930 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8931 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8932 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8934 ExitNotTaken.reserve(ExitCounts.
size());
8935 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8936 std::back_inserter(ExitNotTaken),
8937 [&](
const EdgeExitInfo &EEI) {
8938 BasicBlock *ExitBB = EEI.first;
8939 const ExitLimit &EL = EEI.second;
8940 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
8941 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
8946 "No point in having a non-constant max backedge taken count!");
8950ScalarEvolution::BackedgeTakenInfo
8951ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
8952 bool AllowPredicates) {
8954 L->getExitingBlocks(ExitingBlocks);
8956 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8959 bool CouldComputeBECount =
true;
8961 const SCEV *MustExitMaxBECount =
nullptr;
8962 const SCEV *MayExitMaxBECount =
nullptr;
8963 bool MustExitMaxOrZero =
false;
8964 bool IsOnlyExit = ExitingBlocks.
size() == 1;
8975 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
8976 if (ExitIfTrue == CI->
isZero())
8980 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
8982 assert((AllowPredicates || EL.Predicates.empty()) &&
8983 "Predicated exit limit when predicates are not allowed!");
8988 ++NumExitCountsComputed;
8992 CouldComputeBECount =
false;
8999 "Exact is known but symbolic isn't?");
9000 ++NumExitCountsNotComputed;
9015 DT.dominates(ExitBB, Latch)) {
9016 if (!MustExitMaxBECount) {
9017 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9018 MustExitMaxOrZero = EL.MaxOrZero;
9021 EL.ConstantMaxNotTaken);
9025 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9028 EL.ConstantMaxNotTaken);
9032 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9036 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9042 for (
const auto &Pair : ExitCounts) {
9044 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9046 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9047 {
L, AllowPredicates});
9049 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9050 MaxBECount, MaxOrZero);
9053ScalarEvolution::ExitLimit
9054ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9055 bool IsOnlyExit,
bool AllowPredicates) {
9056 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9060 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9065 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9066 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9067 "It should have one successor in loop and one exit block!");
9078 if (!
L->contains(SBB)) {
9083 assert(Exit &&
"Exiting block must have at least one exit");
9084 return computeExitLimitFromSingleExitSwitch(
9085 L, SI, Exit, IsOnlyExit);
9092 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9093 bool AllowPredicates) {
9094 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9095 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9096 ControlsOnlyExit, AllowPredicates);
9099std::optional<ScalarEvolution::ExitLimit>
9100ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9101 bool ExitIfTrue,
bool ControlsOnlyExit,
9102 bool AllowPredicates) {
9104 (void)this->ExitIfTrue;
9105 (void)this->AllowPredicates;
9107 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9108 this->AllowPredicates == AllowPredicates &&
9109 "Variance in assumed invariant key components!");
9110 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9111 if (Itr == TripCountMap.end())