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 *>;
3985 bool canRecurseInto(
SCEVTypes Kind)
const {
3988 return RootKind == Kind || NonSequentialRootKind == Kind;
3991 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
3993 "Only for min/max expressions.");
3996 if (!canRecurseInto(Kind))
4006 return std::nullopt;
4013 RetVal
visit(
const SCEV *S) {
4015 if (!SeenOps.
insert(S).second)
4016 return std::nullopt;
4017 return Base::visit(S);
4021 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4023 : SE(SE), RootKind(RootKind),
4024 NonSequentialRootKind(
4025 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4029 SmallVectorImpl<SCEVUse> &NewOps) {
4034 for (
const SCEV *
Op : OrigOps) {
4039 Ops.emplace_back(*NewOp);
4043 NewOps = std::move(
Ops);
4047 RetVal visitConstant(
const SCEVConstant *Constant) {
return Constant; }
4049 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4051 RetVal visitPtrToAddrExpr(
const SCEVPtrToAddrExpr *Expr) {
return Expr; }
4053 RetVal visitTruncateExpr(
const SCEVTruncateExpr *Expr) {
return Expr; }
4055 RetVal visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
return Expr; }
4057 RetVal visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
return Expr; }
4059 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4061 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4063 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4065 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4067 RetVal visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
4068 return visitAnyMinMaxExpr(Expr);
4071 RetVal visitUMaxExpr(
const SCEVUMaxExpr *Expr) {
4072 return visitAnyMinMaxExpr(Expr);
4075 RetVal visitSMinExpr(
const SCEVSMinExpr *Expr) {
4076 return visitAnyMinMaxExpr(Expr);
4079 RetVal visitUMinExpr(
const SCEVUMinExpr *Expr) {
4080 return visitAnyMinMaxExpr(Expr);
4083 RetVal visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *Expr) {
4084 return visitAnyMinMaxExpr(Expr);
4087 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4089 RetVal visitCouldNotCompute(
const SCEVCouldNotCompute *Expr) {
return Expr; }
4131struct SCEVPoisonCollector {
4132 bool LookThroughMaybePoisonBlocking;
4133 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4134 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4135 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4137 bool follow(
const SCEV *S) {
4138 if (!LookThroughMaybePoisonBlocking &&
4148 bool isDone()
const {
return false; }
4158 SCEVPoisonCollector PC1(
true);
4163 if (PC1.MaybePoison.
empty())
4169 SCEVPoisonCollector PC2(
false);
4179 SCEVPoisonCollector PC(
false);
4202 while (!Worklist.
empty()) {
4204 if (!Visited.
insert(V).second)
4208 if (Visited.
size() > 16)
4224 if (PDI->isDisjoint())
4231 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4238 if (
I->hasPoisonGeneratingAnnotations())
4249 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4250 "Not a SCEVSequentialMinMaxExpr!");
4251 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4252 if (
Ops.size() == 1)
4256 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4258 "Operand types don't match!");
4261 "min/max should be consistently pointerish");
4269 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4276 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4286 bool DeletedAny =
false;
4287 while (Idx <
Ops.size()) {
4288 if (
Ops[Idx]->getSCEVType() != Kind) {
4293 Ops.erase(
Ops.begin() + Idx);
4294 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4295 SMME->operands().end());
4303 const SCEV *SaturationPoint;
4314 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4315 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4327 Ops.erase(
Ops.begin() + i);
4332 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4333 Ops.erase(
Ops.begin() + i);
4343 ID.AddPointer(
Op.getOpaqueValue());
4345 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
4347 return ExistingSCEV;
4351 SCEV *S =
new (SCEVAllocator)
4354 UniqueSCEVs.insert(S, Token);
4402 if (
Size.isScalable())
4423 "Cannot get offset for structure containing scalable vector types");
4437 if (
SCEV *S = UniqueSCEVs.lookup(ID, Token)) {
4439 "Stale SCEVUnknown in uniquing map!");
4442 SCEV *S =
new (SCEVAllocator)
SCEVUnknown(ID.Intern(SCEVAllocator), V,
this,
4445 UniqueSCEVs.insert(S, Token);
4460 return Ty->isIntOrPtrTy();
4467 if (Ty->isPointerTy())
4478 if (Ty->isIntegerTy())
4482 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4494 bool PreciseA, PreciseB;
4495 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4496 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4497 if (!PreciseA || !PreciseB)
4500 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4501 DT.dominates(ScopeB, ScopeA);
4505 return CouldNotCompute.get();
4508bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4511 return SU && SU->getValue() ==
nullptr;
4514 return !ContainsNulls;
4519 if (
I != HasRecMap.end())
4524 HasRecMap.insert({S, FoundAddRec});
4532 if (
SI == ExprValueMap.
end())
4534 return SI->second.getArrayRef();
4540void ScalarEvolution::eraseValueFromMap(
Value *V) {
4542 if (
I != ValueExprMap.end()) {
4543 auto EVIt = ExprValueMap.find(
I->second);
4544 bool Removed = EVIt->second.remove(V);
4546 assert(Removed &&
"Value not in ExprValueMap?");
4547 ValueExprMap.erase(
I);
4551void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4555 auto It = ValueExprMap.find_as(V);
4556 if (It == ValueExprMap.end()) {
4558 ExprValueMap[S].insert(V);
4569 return createSCEVIter(V);
4576 if (
I != ValueExprMap.end()) {
4577 const SCEV *S =
I->second;
4578 assert(checkValidity(S) &&
4579 "existing SCEV has not been properly invalidated");
4592 Type *Ty = V->getType();
4608 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4621 return (
const SCEV *)
nullptr;
4627 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4631 Type *Ty = V->getType();
4637 assert(
P->getType()->isPointerTy());
4652 if (AddOp->getType()->isPointerTy()) {
4653 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4671 return getZero(LHS->getType());
4676 if (RHS->getType()->isPointerTy()) {
4677 if (!LHS->getType()->isPointerTy() ||
4687 const bool RHSIsNotMinSigned =
4718 Type *SrcTy = V->getType();
4719 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4720 "Cannot truncate or zero extend with non-integer arguments!");
4730 Type *SrcTy = V->getType();
4731 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4732 "Cannot truncate or zero extend with non-integer arguments!");
4741 Type *SrcTy = V->getType();
4742 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4743 "Cannot noop or zero extend with non-integer arguments!");
4745 "getNoopOrZeroExtend cannot truncate!");
4752 Type *SrcTy = V->getType();
4753 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4754 "Cannot noop or sign extend with non-integer arguments!");
4756 "getNoopOrSignExtend cannot truncate!");
4763 Type *SrcTy = V->getType();
4764 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4765 "Cannot noop or any extend with non-integer arguments!");
4767 "getNoopOrAnyExtend cannot truncate!");
4774 Type *SrcTy = V->getType();
4775 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4776 "Cannot truncate or noop with non-integer arguments!");
4778 "getTruncateOrNoop cannot extend!");
4786 const SCEV *PromotedLHS = LHS;
4787 const SCEV *PromotedRHS = RHS;
4807 assert(!
Ops.empty() &&
"At least one operand must be!");
4809 if (
Ops.size() == 1)
4813 Type *MaxType =
nullptr;
4819 assert(MaxType &&
"Failed to find maximum type!");
4832 if (!V->getType()->isPointerTy())
4837 V = AddRec->getStart();
4839 const SCEV *PtrOp =
nullptr;
4840 for (
const SCEV *AddOp :
Add->operands()) {
4841 if (AddOp->getType()->isPointerTy()) {
4842 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4846 assert(PtrOp &&
"Must have pointer op");
4858 for (
User *U :
I->users()) {
4860 if (Visited.
insert(UserInsn).second)
4874 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4875 bool IgnoreOtherLoops =
true) {
4878 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4880 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4885 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4887 SeenLoopVariantSCEVUnknown =
true;
4891 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4895 SeenOtherLoops =
true;
4899 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4901 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4904 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4905 : SCEVRewriteVisitor(SE),
L(
L) {}
4908 bool SeenLoopVariantSCEVUnknown =
false;
4909 bool SeenOtherLoops =
false;
4918 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4919 SCEVPostIncRewriter
Rewriter(L, SE);
4921 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4926 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4928 SeenLoopVariantSCEVUnknown =
true;
4932 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4936 SeenOtherLoops =
true;
4940 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4942 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4945 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4946 : SCEVRewriteVisitor(SE),
L(
L) {}
4949 bool SeenLoopVariantSCEVUnknown =
false;
4950 bool SeenOtherLoops =
false;
4956class SCEVBackedgeConditionFolder
4959 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4960 ScalarEvolution &SE) {
4961 bool IsPosBECond =
false;
4962 Value *BECond =
nullptr;
4963 if (BasicBlock *Latch =
L->getLoopLatch()) {
4965 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
4966 "Both outgoing branches should not target same header!");
4967 BECond = BI->getCondition();
4968 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
4973 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
4977 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4978 const SCEV *
Result = Expr;
4983 switch (
I->getOpcode()) {
4984 case Instruction::Select: {
4986 std::optional<const SCEV *> Res =
4987 compareWithBackedgeCondition(
SI->getCondition());
4995 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5006 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5007 bool IsPosBECond, ScalarEvolution &SE)
5008 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5009 IsPositiveBECond(IsPosBECond) {}
5011 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5015 Value *BackedgeCond =
nullptr;
5017 bool IsPositiveBECond;
5020std::optional<const SCEV *>
5021SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5026 if (BackedgeCond == IC)
5029 return std::nullopt;
5034 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5035 ScalarEvolution &SE) {
5041 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5048 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5058 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5059 : SCEVRewriteVisitor(SE),
L(
L) {}
5067void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5083 const APInt &BECountAP = BECountMax->getAPInt();
5084 unsigned NoOverflowBitWidth =
5093ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5103 if (!SignedWrapViaInductionTried.insert(AR).second)
5128 AC.assumptions().empty())
5136 const SCEV *OverflowLimit =
5138 if (OverflowLimit &&
5146ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5156 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5181 AC.assumptions().empty())
5190 const SCEV *OverflowLimit =
5219 IsNSW = OBO->hasNoSignedWrap();
5220 IsNUW = OBO->hasNoUnsignedWrap();
5226 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5238 return std::nullopt;
5244 switch (
Op->getOpcode()) {
5245 case Instruction::Add:
5246 case Instruction::Sub:
5247 case Instruction::Mul:
5248 case Instruction::UDiv:
5249 case Instruction::URem:
5250 case Instruction::And:
5251 case Instruction::AShr:
5252 case Instruction::Shl:
5255 case Instruction::Or: {
5258 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5268 case Instruction::Xor:
5272 if (RHSC->getValue().isSignMask())
5273 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5275 if (V->getType()->isIntegerTy(1))
5276 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5279 case Instruction::LShr:
5288 if (SA->getValue().ult(
BitWidth)) {
5290 ConstantInt::get(SA->getContext(),
5292 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5297 case Instruction::ExtractValue: {
5299 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5307 bool Signed = WO->isSigned();
5310 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5315 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5326 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5327 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5329 return std::nullopt;
5355 if (
Op == SymbolicPHI)
5360 if (SourceBits != NewBits)
5378 if (!L || L->getHeader() != PN->
getParent())
5436std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5437ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5445 assert(L &&
"Expecting an integer loop header phi");
5450 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5451 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5452 Value *
V = PN->getIncomingValue(i);
5453 if (
L->contains(PN->getIncomingBlock(i))) {
5456 }
else if (BEValueV != V) {
5460 }
else if (!StartValueV) {
5462 }
else if (StartValueV != V) {
5463 StartValueV =
nullptr;
5467 if (!BEValueV || !StartValueV)
5468 return std::nullopt;
5470 const SCEV *BEValue =
getSCEV(BEValueV);
5477 return std::nullopt;
5481 unsigned FoundIndex =
Add->getNumOperands();
5482 Type *TruncTy =
nullptr;
5484 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5487 if (FoundIndex == e) {
5492 if (FoundIndex ==
Add->getNumOperands())
5493 return std::nullopt;
5497 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5498 if (i != FoundIndex)
5499 Ops.push_back(
Add->getOperand(i));
5505 return std::nullopt;
5558 const SCEV *StartVal =
getSCEV(StartValueV);
5559 const SCEV *PHISCEV =
5586 auto getExtendedExpr = [&](
const SCEV *Expr,
5587 bool CreateSignExtend) ->
const SCEV * {
5590 const SCEV *ExtendedExpr =
5593 return ExtendedExpr;
5601 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5602 const SCEV *ExtendedExpr) ->
bool {
5603 return Expr != ExtendedExpr &&
5607 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5608 if (PredIsKnownFalse(StartVal, StartExtended)) {
5610 return std::nullopt;
5615 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5616 if (PredIsKnownFalse(Accum, AccumExtended)) {
5618 return std::nullopt;
5621 auto AppendPredicate = [&](
const SCEV *Expr,
5622 const SCEV *ExtendedExpr) ->
void {
5623 if (Expr != ExtendedExpr &&
5631 AppendPredicate(StartVal, StartExtended);
5632 AppendPredicate(Accum, AccumExtended);
5640 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5641 std::make_pair(NewAR, Predicates);
5643 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5647std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5652 return std::nullopt;
5655 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5656 if (
I != PredicatedSCEVRewrites.end()) {
5657 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5660 if (Rewrite.first == SymbolicPHI)
5661 return std::nullopt;
5665 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5669 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5670 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5675 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5676 return std::nullopt;
5696 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5697 if (Expr1 != Expr2 &&
5698 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5699 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5716const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5718 Value *StartValueV) {
5721 assert(BEValueV && StartValueV);
5727 if (BO->Opcode != Instruction::Add)
5730 const SCEV *Accum =
nullptr;
5731 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5733 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5747 insertValueToMap(PN, PHISCEV);
5750 inferNoWrapViaConstantRanges(AR);
5757 "Accum is defined outside L, but is not invariant?");
5758 if (isAddRecNeverPoison(BEInst, L))
5765const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5773 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5779 }
else if (BEValueV != V) {
5783 }
else if (!StartValueV) {
5785 }
else if (StartValueV != V) {
5786 StartValueV =
nullptr;
5790 if (!BEValueV || !StartValueV)
5793 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5794 "PHI node already processed?");
5798 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5803 insertValueToMap(PN, SymbolicName);
5807 const SCEV *BEValue =
getSCEV(BEValueV);
5817 unsigned FoundIndex =
Add->getNumOperands();
5818 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5819 if (
Add->getOperand(i) == SymbolicName)
5820 if (FoundIndex == e) {
5825 if (FoundIndex !=
Add->getNumOperands()) {
5828 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5829 if (i != FoundIndex)
5830 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5842 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5849 if (
GEP->getOperand(0) == PN) {
5850 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
5868 const SCEV *StartVal =
getSCEV(StartValueV);
5869 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5874 forgetMemoizedResults({SymbolicName});
5875 insertValueToMap(PN, PHISCEV);
5878 inferNoWrapViaConstantRanges(AR);
5902 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5903 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5905 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5906 const SCEV *StartVal =
getSCEV(StartValueV);
5907 if (Start == StartVal) {
5911 forgetMemoizedResults({SymbolicName});
5912 insertValueToMap(PN, Shifted);
5922 eraseValueFromMap(PN);
5937 Use &LeftUse =
Merge->getOperandUse(0);
5938 Use &RightUse =
Merge->getOperandUse(1);
5974 assert(IDom &&
"At least the entry block should dominate PN");
5982const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
5987 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6004 CommonInst = IncomingInst;
6020ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6026 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6027 bool SCEVExprsIdentical =
6029 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6030 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6033const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6034 if (
const SCEV *S = createAddRecFromPHI(PN))
6044 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6047 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6056 struct FindClosure {
6057 const SCEV *OperandToFind;
6063 bool canRecurseInto(
SCEVTypes Kind)
const {
6066 return RootKind == Kind || NonSequentialRootKind == Kind ||
6071 : OperandToFind(OperandToFind), RootKind(RootKind),
6072 NonSequentialRootKind(
6076 bool follow(
const SCEV *S) {
6077 Found = S == OperandToFind;
6079 return !isDone() && canRecurseInto(S->
getSCEVType());
6082 bool isDone()
const {
return Found; }
6085 FindClosure FC(OperandToFind, RootKind);
6090std::optional<const SCEV *>
6091ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6101 switch (ICI->getPredicate()) {
6115 bool Signed = ICI->isSigned();
6116 const SCEV *LA =
getSCEV(TrueVal);
6124 if (LA == LS &&
RA == RS)
6126 if (LA == RS &&
RA == LS)
6129 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6130 if (
Op->getType()->isPointerTy()) {
6141 LS = CoerceOperand(LS);
6142 RS = CoerceOperand(RS);
6166 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6167 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6181 X = ZExt->getOperand();
6183 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6194 return std::nullopt;
6197static std::optional<const SCEV *>
6199 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6203 "Unexpected operands of a select.");
6215 return std::nullopt;
6230static std::optional<const SCEV *>
6234 return std::nullopt;
6237 const auto *SETrue = SE->
getSCEV(TrueVal);
6238 const auto *SEFalse = SE->
getSCEV(FalseVal);
6242const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6244 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6246 V->getType() ==
TrueVal->getType() &&
6247 "Types of select hands and of the result must match.");
6250 if (!
V->getType()->isIntegerTy(1))
6253 if (std::optional<const SCEV *> S =
6266 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6270 if (std::optional<const SCEV *> S =
6271 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6277 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6283 assert(
GEP->getSourceElementType()->isSized() &&
6284 "GEP source element type must be sized");
6287 for (
Value *Index :
GEP->indices())
6292APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6295 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6298 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6300 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6303 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6321 return GetShiftedByZeros(TZ);
6331 return GetShiftedByZeros(TZ);
6335 if (
M->hasNoUnsignedWrap()) {
6338 for (
const SCEV *Operand :
M->operands().drop_front())
6346 for (
const SCEV *Operand :
M->operands())
6348 return GetShiftedByZeros(TZ);
6353 if (
N->hasNoUnsignedWrap())
6354 return GetGCDMultiple(
N);
6357 for (
const SCEV *Operand :
N->operands().drop_front())
6359 return GetShiftedByZeros(TZ);
6376 CtxI = &*F.getEntryBlock().begin();
6383 .allowEphemerals(
true))
6384 .countMinTrailingZeros();
6385 return GetShiftedByZeros(
Known);
6398 return getConstantMultipleImpl(S, CtxI);
6400 auto I = ConstantMultipleCache.find(S);
6401 if (
I != ConstantMultipleCache.end())
6404 APInt Result = getConstantMultipleImpl(S, CtxI);
6405 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6406 assert(InsertPair.second &&
"Should insert a new key");
6407 return InsertPair.first->second;
6424 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6427 if (std::optional<ConstantRange>
Range = CB->getRange())
6431 if (std::optional<ConstantRange>
Range =
A->getRange())
6434 return std::nullopt;
6441 UnsignedRanges.erase(AddRec);
6442 SignedRanges.erase(AddRec);
6443 ConstantMultipleCache.erase(AddRec);
6448getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6474 Value *Start, *Step;
6481 assert(L && L->getHeader() ==
P->getParent());
6494 case Instruction::AShr:
6495 case Instruction::LShr:
6496 case Instruction::Shl:
6511 KnownStep.getBitWidth() ==
BitWidth);
6514 auto MaxShiftAmt = KnownStep.getMaxValue();
6516 bool Overflow =
false;
6517 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6524 case Instruction::AShr: {
6532 if (KnownStart.isNonNegative())
6535 KnownStart.getMaxValue() + 1);
6536 if (KnownStart.isNegative())
6539 KnownEnd.getMaxValue() + 1);
6542 case Instruction::LShr: {
6551 KnownStart.getMaxValue() + 1);
6553 case Instruction::Shl: {
6557 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6558 return ConstantRange(KnownStart.getMinValue(),
6559 KnownEnd.getMaxValue() + 1);
6584 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6591ScalarEvolution::getRangeRefIter(
const SCEV *S,
6592 ScalarEvolution::RangeSignHint SignHint) {
6593 DenseMap<const SCEV *, ConstantRange> &Cache =
6594 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6597 SmallPtrSet<const SCEV *, 8> Seen;
6601 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6602 if (!Seen.
insert(Expr).second)
6635 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6636 const SCEV *
P = WorkList[
I];
6640 for (
const SCEV *
Op :
P->operands())
6653 if (!WorkList.
empty()) {
6658 getRangeRef(
P, SignHint);
6662 return getRangeRef(S, SignHint, 0);
6665const APInt *ScalarEvolution::getConstantAPIntOrNull(
const SCEV *S) {
6667 return &
C->getAPInt();
6675 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6676 DenseMap<const SCEV *, ConstantRange> &Cache =
6677 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6684 auto I = Cache.
find(S);
6685 if (
I != Cache.
end())
6689 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6694 return getRangeRefIter(S, SignHint);
6697 ConstantRange ConservativeResult(
BitWidth,
true);
6698 using OBO = OverflowingBinaryOperator;
6702 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6706 ConservativeResult =
6713 ConservativeResult = ConstantRange(
6729 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6736 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6743 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6748 return setRange(Cast, SignHint,
X);
6753 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6754 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6756 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6757 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6758 ConservativeResult =
6759 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6761 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6762 unsigned WrapType = OBO::AnyWrap;
6763 if (
Add->hasNoSignedWrap())
6764 WrapType |= OBO::NoSignedWrap;
6765 if (
Add->hasNoUnsignedWrap())
6766 WrapType |= OBO::NoUnsignedWrap;
6768 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6770 return setRange(
Add, SignHint,
6771 ConservativeResult.intersectWith(
X, RangeType));
6775 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6777 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6778 return setRange(
Mul, SignHint,
6779 ConservativeResult.intersectWith(
X, RangeType));
6783 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6784 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6785 return setRange(UDiv, SignHint,
6786 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6794 if (!UnsignedMinValue.
isZero())
6795 ConservativeResult = ConservativeResult.intersectWith(
6796 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6805 bool AllNonNeg =
true;
6806 bool AllNonPos =
true;
6807 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6814 ConservativeResult = ConservativeResult.intersectWith(
6819 ConservativeResult = ConservativeResult.intersectWith(
6828 const SCEV *MaxBEScev =
6842 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6844 ConservativeResult =
6845 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6848 auto RangeFromFactoring = getRangeViaFactoring(
6850 ConservativeResult =
6851 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6857 const SCEV *SymbolicMaxBECount =
6862 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6863 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6864 ConservativeResult =
6865 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6870 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6880 ID = Intrinsic::umax;
6883 ID = Intrinsic::smax;
6887 ID = Intrinsic::umin;
6890 ID = Intrinsic::smin;
6897 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6898 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6900 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6901 return setRange(S, SignHint,
6902 ConservativeResult.intersectWith(
X, RangeType));
6911 ConservativeResult =
6912 ConservativeResult.intersectWith(*MDRange, RangeType);
6917 auto CR = getRangeForUnknownRecurrence(U);
6918 ConservativeResult = ConservativeResult.intersectWith(CR);
6929 if (
U->getType()->isPointerTy()) {
6932 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
6933 int ptrIdxDiff = ptrSize -
BitWidth;
6934 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
6940 if (!
Known.Zero.getHiBits(NS).isZero())
6941 Known.Zero.setHighBits(NS);
6942 if (!
Known.One.getHiBits(NS).isZero())
6943 Known.One.setHighBits(NS);
6946 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
6947 ConservativeResult = ConservativeResult.intersectWith(
6948 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
6951 ConservativeResult = ConservativeResult.intersectWith(
6956 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6960 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
6961 DL, CanBeNull,
nullptr);
6977 ConservativeResult = ConservativeResult.intersectWith(
6987 return getRangeRef(AR, SignHint,
Depth + 1);
6991 ConstantRange RangeFromOps(
BitWidth,
false);
6993 for (
const auto &
Op :
Phi->operands()) {
6995 RangeFromOps = RangeFromOps.unionWith(OpRange);
6997 if (RangeFromOps.isFullSet())
7000 ConservativeResult =
7001 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7007 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7009 ConservativeResult = ConservativeResult.difference(Disallowed);
7012 return setRange(U, SignHint, std::move(ConservativeResult));
7018 return setRange(S, SignHint, std::move(ConservativeResult));
7026static std::pair<ConstantRange, bool>
7034 if (Step == 0 || MaxBECount == 0)
7035 return {StartRange,
true};
7041 return {ConstantRange::getFull(
BitWidth),
false};
7057 return {ConstantRange::getFull(
BitWidth),
false};
7070 APInt MovedBoundary;
7075 MovedBoundary = StartLower - std::move(
Offset);
7078 MovedBoundary = StartUpper + std::move(
Offset);
7082 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7089 if (StartRange.
contains(MovedBoundary))
7090 return {ConstantRange::getFull(
BitWidth),
false};
7093 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7095 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7103std::pair<ConstantRange, SCEV::NoWrapFlags>
7104ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7105 const APInt &MaxBECount) {
7109 "mismatched bit widths");
7118 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7120 StartSRange, MaxBECount,
7122 ConstantRange SR = SR1.unionWith(SR2);
7139ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7141 ScalarEvolution::RangeSignHint SignHint) {
7142 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7144 "This only works for non-self-wrapping AddRecs!");
7145 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7149 return ConstantRange::getFull(
BitWidth);
7157 return ConstantRange::getFull(
BitWidth);
7161 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7163 MaxItersWithoutWrap))
7164 return ConstantRange::getFull(
BitWidth);
7185 ConstantRange StartRange = getRangeRef(Start, SignHint);
7186 ConstantRange EndRange = getRangeRef(End, SignHint);
7187 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7191 return RangeBetween;
7196 return ConstantRange::getFull(
BitWidth);
7199 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7200 return RangeBetween;
7202 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7203 return RangeBetween;
7204 return ConstantRange::getFull(
BitWidth);
7209 const APInt &MaxBECount) {
7216 "mismatched bit widths");
7218 struct SelectPattern {
7219 Value *Condition =
nullptr;
7223 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7225 std::optional<unsigned> CastOp;
7239 CastOp = SCast->getSCEVType();
7240 S = SCast->getOperand();
7243 using namespace llvm::PatternMatch;
7250 Condition =
nullptr;
7282 bool isRecognized() {
return Condition !=
nullptr; }
7285 SelectPattern StartPattern(*
this,
BitWidth, Start);
7286 if (!StartPattern.isRecognized())
7287 return ConstantRange::getFull(
BitWidth);
7289 SelectPattern StepPattern(*
this,
BitWidth, Step);
7290 if (!StepPattern.isRecognized())
7291 return ConstantRange::getFull(
BitWidth);
7293 if (StartPattern.Condition != StepPattern.Condition) {
7297 return ConstantRange::getFull(
BitWidth);
7308 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7309 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7310 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7311 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7313 ConstantRange TrueRange =
7314 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7315 ConstantRange FalseRange =
7316 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7328 PDI && PDI->isDisjoint()) {
7343ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7356 SmallPtrSet<const SCEV *, 16> Visited;
7358 auto pushOp = [&](
const SCEV *S) {
7359 if (!Visited.
insert(S).second)
7362 if (Visited.
size() > 30) {
7373 while (!Worklist.
empty()) {
7375 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7376 if (!Bound || DT.dominates(Bound, DefI))
7383 return Bound ? Bound : &*F.getEntryBlock().begin();
7389 return getDefiningScopeBound(
Ops, Discard);
7392bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7394 if (
A->getParent() ==
B->getParent() &&
7399 auto *BLoop = LI.getLoopFor(
B->getParent());
7400 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7401 BLoop->getLoopPreheader() ==
A->getParent() &&
7403 A->getParent()->end()) &&
7411 SCEVPoisonCollector PC(
true);
7413 return PC.MaybePoison.
empty();
7416bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7426bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7443 for (
const Use &
Op :
I->operands()) {
7449 auto *DefI = getDefiningScopeBound(SCEVOps);
7450 return isGuaranteedToTransferExecutionTo(DefI,
I);
7453bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7455 if (isSCEVExprNeverPoison(
I))
7466 auto *ExitingBB =
L->getExitingBlock();
7470 SmallPtrSet<const Value *, 16> KnownPoison;
7479 while (!Worklist.
empty()) {
7482 for (
const Use &U :
Poison->uses()) {
7485 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7489 if (KnownPoison.
insert(PoisonUser).second)
7497ScalarEvolution::LoopProperties
7498ScalarEvolution::getLoopProperties(
const Loop *L) {
7499 using LoopProperties = ScalarEvolution::LoopProperties;
7501 auto Itr = LoopPropertiesCache.find(L);
7502 if (Itr == LoopPropertiesCache.end()) {
7505 return !
SI->isSimple();
7515 return I->mayWriteToMemory();
7518 LoopProperties LP = {
true,
7521 for (
auto *BB :
L->getBlocks())
7522 for (
auto &
I : *BB) {
7524 LP.HasNoAbnormalExits =
false;
7525 if (HasSideEffects(&
I))
7526 LP.HasNoSideEffects =
false;
7527 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7531 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7532 assert(InsertPair.second &&
"We just checked!");
7533 Itr = InsertPair.first;
7546const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7552 Stack.emplace_back(V,
false);
7553 while (!Stack.empty()) {
7554 auto E = Stack.back();
7555 Value *CurV = E.getPointer();
7563 const SCEV *CreatedSCEV =
nullptr;
7566 CreatedSCEV = createSCEV(CurV);
7571 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7575 insertValueToMap(CurV, CreatedSCEV);
7578 Stack.back().setInt(
true);
7581 Stack.emplace_back(
Op,
false);
7598 if (!DT.isReachableFromEntry(
I->getParent()))
7611 switch (BO->Opcode) {
7612 case Instruction::Add:
7613 case Instruction::Mul: {
7620 Ops.push_back(BO->
Op);
7624 Ops.push_back(BO->RHS);
7628 (BO->Opcode == Instruction::Add &&
7629 (NewBO->Opcode != Instruction::Add &&
7630 NewBO->Opcode != Instruction::Sub)) ||
7631 (BO->Opcode == Instruction::Mul &&
7632 NewBO->Opcode != Instruction::Mul)) {
7633 Ops.push_back(BO->LHS);
7638 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7641 Ops.push_back(BO->LHS);
7649 case Instruction::Sub:
7650 case Instruction::UDiv:
7651 case Instruction::URem:
7653 case Instruction::AShr:
7654 case Instruction::Shl:
7655 case Instruction::Xor:
7659 case Instruction::And:
7660 case Instruction::Or:
7664 case Instruction::LShr:
7671 Ops.push_back(BO->LHS);
7672 Ops.push_back(BO->RHS);
7676 switch (
U->getOpcode()) {
7677 case Instruction::Trunc:
7678 case Instruction::ZExt:
7679 case Instruction::SExt:
7680 case Instruction::PtrToAddr:
7681 case Instruction::PtrToInt:
7682 Ops.push_back(
U->getOperand(0));
7685 case Instruction::BitCast:
7687 Ops.push_back(
U->getOperand(0));
7692 case Instruction::SDiv:
7693 case Instruction::SRem:
7694 Ops.push_back(
U->getOperand(0));
7695 Ops.push_back(
U->getOperand(1));
7698 case Instruction::GetElementPtr:
7700 "GEP source element type must be sized");
7704 case Instruction::IntToPtr:
7707 case Instruction::PHI:
7738 Ops.push_back(CondICmp->getOperand(0));
7739 Ops.push_back(CondICmp->getOperand(1));
7759 case Instruction::Select: {
7761 auto CanSimplifyToUnknown = [
this,
U]() {
7779 if (CanSimplifyToUnknown())
7786 case Instruction::Call:
7787 case Instruction::Invoke:
7794 switch (
II->getIntrinsicID()) {
7795 case Intrinsic::abs:
7796 Ops.push_back(
II->getArgOperand(0));
7798 case Intrinsic::umax:
7799 case Intrinsic::umin:
7800 case Intrinsic::smax:
7801 case Intrinsic::smin:
7802 case Intrinsic::usub_sat:
7803 case Intrinsic::uadd_sat:
7804 Ops.push_back(
II->getArgOperand(0));
7805 Ops.push_back(
II->getArgOperand(1));
7807 case Intrinsic::start_loop_iterations:
7808 case Intrinsic::annotation:
7809 case Intrinsic::ptr_annotation:
7810 Ops.push_back(
II->getArgOperand(0));
7822const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7831 if (!DT.isReachableFromEntry(
I->getParent()))
7846 switch (BO->Opcode) {
7847 case Instruction::Add: {
7873 if (BO->Opcode == Instruction::Sub)
7881 if (BO->Opcode == Instruction::Sub)
7888 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7889 NewBO->Opcode != Instruction::Sub)) {
7899 case Instruction::Mul: {
7920 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7929 case Instruction::UDiv:
7933 case Instruction::URem:
7937 case Instruction::Sub: {
7940 Flags = getNoWrapFlagsFromUB(BO->
Op);
7945 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
7948 if (HasPtrLHS || HasPtrRHS) {
7953 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
7954 bool BothPtr) ->
const SCEV * {
7957 const SCEV *PtrSCEV =
getSCEV(PtrOp);
7967 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
7968 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
7976 case Instruction::And:
7982 if (CI->isMinusOne())
7984 const APInt &
A = CI->getValue();
7990 unsigned LZ =
A.countl_zero();
7991 unsigned TZ =
A.countr_zero();
7996 APInt EffectiveMask =
7998 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
8001 const SCEV *ShiftedLHS =
nullptr;
8005 unsigned MulZeros = OpC->getAPInt().countr_zero();
8006 unsigned GCD = std::min(MulZeros, TZ);
8011 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8033 case Instruction::Or:
8042 case Instruction::Xor:
8045 if (CI->isMinusOne())
8054 if (LBO->getOpcode() == Instruction::And &&
8055 LCI->getValue() == CI->getValue())
8056 if (
const SCEVZeroExtendExpr *Z =
8059 const SCEV *Z0 =
Z->getOperand();
8066 if (CI->getValue().isMask(Z0TySize))
8072 APInt Trunc = CI->getValue().trunc(Z0TySize);
8081 case Instruction::Shl:
8099 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8108 ConstantInt *
X = ConstantInt::get(
8114 case Instruction::AShr:
8136 const SCEV *AddTruncateExpr =
nullptr;
8137 ConstantInt *ShlAmtCI =
nullptr;
8138 const SCEV *AddConstant =
nullptr;
8140 if (L &&
L->getOpcode() == Instruction::Add) {
8148 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8155 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8163 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8168 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8173 if (AddTruncateExpr && ShlAmtCI) {
8185 const APInt &ShlAmt = ShlAmtCI->
getValue();
8189 const SCEV *CompositeExpr =
8191 if (
L->getOpcode() != Instruction::Shl)
8192 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8201 switch (
U->getOpcode()) {
8202 case Instruction::Trunc:
8205 case Instruction::ZExt:
8208 case Instruction::SExt:
8218 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8219 Type *Ty =
U->getType();
8227 case Instruction::BitCast:
8233 case Instruction::PtrToAddr: {
8240 case Instruction::PtrToInt:
8244 case Instruction::IntToPtr:
8248 case Instruction::SDiv:
8255 case Instruction::SRem:
8262 case Instruction::GetElementPtr:
8265 case Instruction::PHI:
8268 case Instruction::Select:
8269 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8272 case Instruction::Call:
8273 case Instruction::Invoke:
8278 switch (
II->getIntrinsicID()) {
8279 case Intrinsic::abs:
8283 case Intrinsic::umax:
8287 case Intrinsic::umin:
8291 case Intrinsic::smax:
8295 case Intrinsic::smin:
8299 case Intrinsic::usub_sat: {
8300 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8301 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8305 case Intrinsic::uadd_sat: {
8306 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8307 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8311 case Intrinsic::start_loop_iterations:
8312 case Intrinsic::annotation:
8313 case Intrinsic::ptr_annotation:
8317 case Intrinsic::vscale:
8337 auto *ExitCountType = ExitCount->
getType();
8338 assert(ExitCountType->isIntegerTy());
8340 1 + ExitCountType->getScalarSizeInBits());
8353 auto CanAddOneWithoutOverflow = [&]() {
8355 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8366 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8396 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8397 assert(L->isLoopExiting(ExitingBlock) &&
8398 "Exiting block must actually branch out of the loop!");
8407 const auto *MaxExitCount =
8415 L->getExitingBlocks(ExitingBlocks);
8417 std::optional<unsigned> Res;
8418 for (
auto *ExitingBB : ExitingBlocks) {
8422 Res = std::gcd(*Res, Multiple);
8424 return Res.value_or(1);
8428 const SCEV *ExitCount) {
8458 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8459 assert(L->isLoopExiting(ExitingBlock) &&
8460 "Exiting block must actually branch out of the loop!");
8470 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8472 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8474 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8484 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8487 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8490 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8498 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8505 return getBackedgeTakenInfo(L).getExact(L,
this);
8507 return getBackedgeTakenInfo(L).getConstantMax(
this);
8509 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8516 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8521 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8525 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8535 for (
PHINode &PN : Header->phis())
8536 if (Visited.
insert(&PN).second)
8540ScalarEvolution::BackedgeTakenInfo &
8541ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8542 auto &BTI = getBackedgeTakenInfo(L);
8543 if (BTI.hasFullInfo())
8546 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8549 return Pair.first->second;
8551 BackedgeTakenInfo
Result =
8552 computeBackedgeTakenCount(L,
true);
8554 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8557ScalarEvolution::BackedgeTakenInfo &
8558ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8564 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8565 BackedgeTakenCounts.try_emplace(L);
8567 return Pair.first->second;
8572 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8579 if (
Result.hasAnyInfo()) {
8582 auto LoopUsersIt = LoopUsers.find(L);
8583 if (LoopUsersIt != LoopUsers.end())
8585 forgetMemoizedResults(ToForget);
8588 for (PHINode &PN :
L->getHeader()->phis())
8589 ConstantEvolutionLoopExitValue.erase(&PN);
8597 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8606 BackedgeTakenCounts.clear();
8607 PredicatedBackedgeTakenCounts.clear();
8608 BECountUsers.clear();
8609 LoopPropertiesCache.clear();
8610 ConstantEvolutionLoopExitValue.clear();
8611 ValueExprMap.clear();
8612 ValuesAtScopes.clear();
8613 ValuesAtScopesUsers.clear();
8614 LoopDispositions.clear();
8615 BlockDispositions.clear();
8616 UnsignedRanges.clear();
8617 SignedRanges.clear();
8618 ExprValueMap.clear();
8620 ConstantMultipleCache.clear();
8621 PredicatedSCEVRewrites.clear();
8623 FoldCacheUser.clear();
8625void ScalarEvolution::visitAndClearUsers(
8629 while (!Worklist.
empty()) {
8636 if (It != ValueExprMap.
end()) {
8638 eraseValueFromMap(It->first);
8640 ConstantEvolutionLoopExitValue.erase(PN);
8654 while (!LoopWorklist.
empty()) {
8658 forgetBackedgeTakenCounts(CurrL,
false);
8659 forgetBackedgeTakenCounts(CurrL,
true);
8662 PredicatedSCEVRewrites.remove_if(
8663 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8665 auto LoopUsersItr = LoopUsers.find(CurrL);
8666 if (LoopUsersItr != LoopUsers.end())
8671 visitAndClearUsers(Worklist, Visited, ToForget);
8673 LoopPropertiesCache.erase(CurrL);
8676 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8678 forgetMemoizedResults(ToForget);
8695 visitAndClearUsers(Worklist, Visited, ToForget);
8697 forgetMemoizedResults(ToForget);
8705 auto InvalidateValue = [&](
Value *Val) {
8709 struct InvalidationRootCollector {
8713 InvalidationRootCollector(
Loop *L) : L(L) {}
8715 bool follow(
const SCEV *S) {
8721 if (L->contains(AddRec->
getLoop()))
8726 bool isDone()
const {
return false; }
8729 InvalidationRootCollector
C(L);
8731 forgetMemoizedResults(
C.Roots);
8741 return isa<WithOverflowInst>(Inc);
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))
9100 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9101 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9102 "It should have one successor in loop and one exit block!");
9113 if (!
L->contains(SBB)) {
9118 assert(Exit &&
"Exiting block must have at least one exit");
9119 return computeExitLimitFromSingleExitSwitch(
9120 L, SI, Exit, IsOnlyExit);