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.FindNodeOrInsertPos(ID, IP)))
472 new (SCEVAllocator)
SCEVConstant(ID.Intern(SCEVAllocator), V);
473 UniqueSCEVs.InsertNode(S, IP);
488 ConstantInt::get(ITy, V,
isSigned,
true));
496 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
498 SCEV *S =
new (SCEVAllocator)
SCEVVScale(ID.Intern(SCEVAllocator), Ty);
499 UniqueSCEVs.InsertNode(S, IP);
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.RemoveNode(
this);
560void SCEVUnknown::allUsesReplacedWith(
Value *New) {
562 SE->forgetMemoizedResults({
this});
565 SE->UniqueSCEVs.RemoveNode(
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.FindNodeOrInsertPos(ID, IP))
1087 SCEV *S =
new (SCEVAllocator)
1089 UniqueSCEVs.InsertNode(S, IP);
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.FindNodeOrInsertPos(ID, IP))
return S;
1136 UniqueSCEVs.InsertNode(S, IP);
1149 unsigned numTruncs = 0;
1150 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1158 if (numTruncs < 2) {
1168 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
1175 for (
const SCEV *
Op : AddRec->operands())
1190 UniqueSCEVs.InsertNode(S, IP);
1231struct ExtendOpTraitsBase {
1232 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
SCEVUse,
Type *,
1237template <
typename ExtendOp>
struct ExtendOpTraits {
1253 static const GetExtendExprTy GetExtendExpr;
1255 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1256 ICmpInst::Predicate *Pred,
1257 ScalarEvolution *SE) {
1262const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1269 static const GetExtendExprTy GetExtendExpr;
1271 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1272 ICmpInst::Predicate *Pred,
1273 ScalarEvolution *SE) {
1278const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1290template <
typename ExtendOpTy>
1293 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1294 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1310 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1323 auto PreStartFlags =
1341 const SCEV *OperandExtendedStart =
1343 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1344 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1356 const SCEV *OverflowLimit =
1357 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1359 if (OverflowLimit &&
1367template <
typename ExtendOpTy>
1371 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1379 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1414template <
typename ExtendOpTy>
1415bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1418 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1428 APInt StartAI = StartC->
getAPInt();
1430 for (
unsigned Delta : {-2, -1, 1, 2}) {
1431 const SCEV *PreStart =
getConstant(StartAI - Delta);
1433 FoldingSetNodeID
ID;
1435 ID.AddPointer(PreStart);
1436 ID.AddPointer(Step);
1440 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
1444 if (PreAR &&
any(PreAR->getNoWrapFlags(WrapType))) {
1447 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1448 DeltaS, &Pred,
this);
1466 const unsigned BitWidth =
C.getBitWidth();
1484 const APInt &ConstantStart,
1499 auto I = FoldCache.
insert({ID, S});
1503 auto &UserIDs = FoldCacheUser[
I.first->second];
1504 assert(
count(UserIDs, ID) == 1 &&
"unexpected duplicates in UserIDs");
1505 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1506 if (UserIDs[
I] == ID) {
1511 I.first->second = S;
1513 FoldCacheUser[S].push_back(ID);
1519 "This is not an extending conversion!");
1521 "This is not a conversion to a SCEVable type!");
1522 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1526 if (
const SCEV *S = FoldCache.lookup(ID))
1538 "This is not an extending conversion!");
1540 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1552 const SCEV *Start, *Step;
1557 if (AR->hasNoUnsignedWrap()) {
1568 ID.AddPointer(
Op.getOpaqueValue());
1571 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1575 UniqueSCEVs.InsertNode(S, IP);
1585 const SCEV *
X = ST->getOperand();
1618 const SCEV *CastedMaxBECount =
1622 if (MaxBECount == RecastedMaxBECount) {
1631 const SCEV *WideMaxBECount =
1633 const SCEV *OperandExtendedAdd =
1639 if (ZAdd == OperandExtendedAdd) {
1650 OperandExtendedAdd =
1656 if (ZAdd == OperandExtendedAdd) {
1677 !AC.assumptions().empty()) {
1679 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1681 if (AR->hasNoUnsignedWrap()) {
1716 const APInt &
C = SC->getAPInt();
1720 const SCEV *SResidual =
1728 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1752 if (SA->hasNoUnsignedWrap()) {
1765 if (SA->hasNoSignedWrap() &&
1768 C->isNegative() && !
C->isMinSignedValue() && C2->
sge(
C->abs())) {
1787 const SCEV *SResidual =
1798 if (SM->hasNoUnsignedWrap()) {
1820 const SCEV *TruncRHS;
1857 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1860 UniqueSCEVs.InsertNode(S, IP);
1869 "This is not an extending conversion!");
1871 "This is not a conversion to a SCEVable type!");
1872 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1876 if (
const SCEV *S = FoldCache.lookup(ID))
1888 "This is not an extending conversion!");
1890 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1907 const SCEV *Start, *Step;
1912 if (AR->hasNoSignedWrap()) {
1923 ID.AddPointer(
Op.getOpaqueValue());
1926 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1931 UniqueSCEVs.InsertNode(S, IP);
1941 const SCEV *
X = ST->getOperand();
1952 if (SA->hasNoSignedWrap()) {
1974 const SCEV *SResidual =
2007 const SCEV *CastedMaxBECount =
2011 if (MaxBECount == RecastedMaxBECount) {
2020 const SCEV *WideMaxBECount =
2022 const SCEV *OperandExtendedAdd =
2028 if (SAdd == OperandExtendedAdd) {
2039 OperandExtendedAdd =
2045 if (SAdd == OperandExtendedAdd) {
2065 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2067 if (AR->hasNoSignedWrap()) {
2081 const APInt &
C = SC->getAPInt();
2085 const SCEV *SResidual =
2093 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2120 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
2123 UniqueSCEVs.InsertNode(S, IP);
2139 assert(Expr->
getType() == Ty &&
"requested type must match");
2151 "This is not an extending conversion!");
2153 "This is not a conversion to a SCEVable type!");
2158 if (SC->getAPInt().isNegative())
2163 const SCEV *NewOp =
T->getOperand();
2182 for (
const SCEV *
Op : AR->operands())
2220 APInt &AccumulatedConstant,
2224 bool Interesting =
false;
2231 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2233 AccumulatedConstant += Scale *
C->getAPInt();
2238 for (; i !=
Ops.size(); ++i) {
2247 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2253 auto Pair = M.insert({
Key, NewScale});
2257 Pair.first->second += NewScale;
2265 auto Pair = M.insert({
Ops[i], Scale});
2269 Pair.first->second += Scale;
2288 case Instruction::Add:
2291 case Instruction::Sub:
2294 case Instruction::Mul:
2308 const SCEV *
A = (this->*Extension)(
2310 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2311 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2319 if (BinOp == Instruction::Mul)
2325 APInt C = RHSC->getAPInt();
2326 unsigned NumBits =
C.getBitWidth();
2327 bool IsSub = (BinOp == Instruction::Sub);
2328 bool IsNegativeConst = (
Signed &&
C.isNegative());
2330 bool OverflowDown = IsSub ^ IsNegativeConst;
2332 if (IsNegativeConst) {
2345 APInt Limit = Min + Magnitude;
2351 APInt Limit = Max - Magnitude;
2356std::optional<SCEV::NoWrapFlags>
2361 return std::nullopt;
2370 bool Deduced =
false;
2376 bool CanUseNSW =
true;
2377 const APInt *ShiftAmt;
2382 return std::nullopt;
2386 Opcode = Instruction::Mul;
2388 }
else if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
2389 Opcode != Instruction::Mul) {
2390 return std::nullopt;
2409 return std::nullopt;
2419 using namespace std::placeholders;
2426 assert(CanAnalyze &&
"don't call from other places!");
2433 auto IsKnownNonNegative = [&](
SCEVUse U) {
2442 if (SignOrUnsignWrap != SignOrUnsignMask &&
2449 return Instruction::Add;
2451 return Instruction::Mul;
2462 Opcode,
C, OBO::NoSignedWrap);
2470 Opcode,
C, OBO::NoUnsignedWrap);
2480 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2487 if (UDiv->getOperand(1) ==
Ops[1])
2490 if (UDiv->getOperand(1) ==
Ops[0])
2506 "only nuw or nsw allowed");
2507 assert(!
Ops.empty() &&
"Cannot get empty add!");
2508 if (
Ops.size() == 1)
return Ops[0];
2511 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2513 "SCEVAddExpr operand types don't match!");
2515 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2516 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2521 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2522 [](
const APInt &
C) {
return C.isZero(); },
2523 [](
const APInt &
C) {
return false; });
2536 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2541 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2542 Add->setNoWrapFlags(ComputeFlags(
Ops));
2550 bool FoundMatch =
false;
2551 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2552 if (
Ops[i] ==
Ops[i+1]) {
2564 --i; e -=
Count - 1;
2574 auto FindTruncSrcType = [&]() ->
Type * {
2580 return T->getOperand()->getType();
2582 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2584 return T->getOperand()->getType();
2588 if (
auto *SrcType = FindTruncSrcType()) {
2595 if (
T->getOperand()->getType() != SrcType) {
2604 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2607 if (
T->getOperand()->getType() != SrcType) {
2635 if (
Ops.size() == 2) {
2645 auto C2 =
C->getAPInt();
2648 APInt ConstAdd = C1 + C2;
2649 auto AddFlags = AddExpr->getNoWrapFlags();
2690 if (
Ops.size() == 2 &&
2701 if (Idx <
Ops.size()) {
2702 bool DeletedAdd =
false;
2713 Ops.erase(
Ops.begin()+Idx);
2716 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2739 struct APIntCompare {
2740 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2741 return LHS.ult(RHS);
2748 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2749 for (
const SCEV *NewOp : NewOps)
2750 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2753 if (AccumulatedConstant != 0)
2755 for (
auto &MulOp : MulOpLists) {
2756 if (MulOp.first == 1) {
2758 }
else if (MulOp.first != 0) {
2767 if (
Ops.size() == 1)
2776 if (M->getNumOperands() == 2)
2777 return M->getOperand(OpIdx == 0);
2779 append_range(Remaining, M->operands().drop_front(OpIdx + 1));
2788 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2792 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2800 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp) {
2801 if (MulOpSCEV ==
Ops[AddOp]) {
2812 for (
unsigned OMulOp = 0, OE = OtherMul->
getNumOperands(); OMulOp != OE;
2814 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2816 Cofactors.
push_back(StripFactor(OtherMul, OMulOp));
2825 if (!Cofactors.
empty()) {
2833 if (
Ops.size() == DeadIndices.
size() + 1)
2840 Ops.erase(
Ops.begin() + Idx);
2844 Ops.push_back(OuterMul);
2863 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2866 Ops.erase(
Ops.begin()+i);
2871 if (!LIOps.
empty()) {
2896 auto *DefI = getDefiningScopeBound(LIOps);
2898 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2910 if (
Ops.size() == 1)
return NewRec;
2913 for (
unsigned i = 0;; ++i)
2914 if (
Ops[i] == AddRec) {
2924 for (
unsigned OtherIdx = Idx+1;
2932 "AddRecExprs are not sorted in reverse dominance order?");
2939 if (OtherAddRec->getLoop() == AddRecLoop) {
2940 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2942 if (i >= AddRecOps.
size()) {
2943 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2947 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
2950 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
2965 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2973 ID.AddPointer(
Op.getOpaqueValue());
2976 static_cast<SCEVAddExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
2980 S =
new (SCEVAllocator)
2982 UniqueSCEVs.InsertNode(S, IP);
2993 FoldingSetNodeID
ID;
2996 ID.AddPointer(
Op.getOpaqueValue());
3000 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
3004 S =
new (SCEVAllocator)
3005 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3006 UniqueSCEVs.InsertNode(S, IP);
3008 LoopUsers[
L].push_back(S);
3017 FoldingSetNodeID
ID;
3020 ID.AddPointer(
Op.getOpaqueValue());
3023 static_cast<SCEVMulExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
3027 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3029 UniqueSCEVs.InsertNode(S, IP);
3038 FoldingSetNodeID
ID;
3040 ID.AddPointer(
LHS.getOpaqueValue());
3041 ID.AddPointer(
RHS.getOpaqueValue());
3043 SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
3045 S =
new (SCEVAllocator) SCEVUDivExpr(
ID.Intern(SCEVAllocator),
LHS,
RHS);
3046 UniqueSCEVs.InsertNode(S, IP);
3055 if (j > 1 && k / j != i) Overflow =
true;
3071 if (n == 0 || n == k)
return 1;
3072 if (k > n)
return 0;
3078 for (
uint64_t i = 1; i <= k; ++i) {
3079 r =
umul_ov(r, n-(i-1), Overflow);
3088 struct FindConstantInAddMulChain {
3089 bool FoundConstant =
false;
3091 bool follow(
const SCEV *S) {
3096 bool isDone()
const {
3097 return FoundConstant;
3101 FindConstantInAddMulChain
F;
3103 ST.visitAll(StartExpr);
3104 return F.FoundConstant;
3112 "only nuw or nsw allowed");
3113 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3114 if (
Ops.size() == 1)
return Ops[0];
3116 Type *ETy =
Ops[0]->getType();
3118 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3120 "SCEVMulExpr operand types don't match!");
3125 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3126 [](
const APInt &
C) {
return C.isOne(); },
3127 [](
const APInt &
C) {
return C.isZero(); });
3138 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3143 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3144 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3149 if (
Ops.size() == 2) {
3157 const SCEV *Op0, *Op1;
3165 if (
Ops[0]->isAllOnesValue()) {
3170 bool AnyFolded =
false;
3171 for (
const SCEV *AddOp :
Add->operands()) {
3191 if (AddRec->hasNoSignedWrap()) {
3198 AddRec->getNoWrapFlags(FlagsMask));
3221 APInt C1V = LHSC->getAPInt();
3231 const SCEV *NewMul =
nullptr;
3235 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3250 if (Idx <
Ops.size()) {
3251 bool DeletedMul =
false;
3257 Ops.erase(
Ops.begin()+Idx);
3281 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3284 Ops.erase(
Ops.begin()+i);
3289 if (!LIOps.
empty()) {
3302 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3318 if (
Ops.size() == 1)
return NewRec;
3321 for (
unsigned i = 0;; ++i)
3322 if (
Ops[i] == AddRec) {
3343 bool OpsModified =
false;
3344 for (
unsigned OtherIdx = Idx+1;
3358 bool Overflow =
false;
3365 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3366 uint64_t Coeff1 =
Choose(x, 2*x - y, Overflow);
3369 z < ze && !Overflow; ++z) {
3370 uint64_t Coeff2 =
Choose(2*x - y, x-z, Overflow);
3372 if (LargerThan64Bits)
3373 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3375 Coeff = Coeff1*Coeff2;
3390 if (
Ops.size() == 2)
return NewAddRec;
3391 Ops[Idx] = NewAddRec;
3392 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3408 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3415 "SCEVURemExpr operand types don't match!");
3420 if (RHSC->getValue()->isOne())
3421 return getZero(LHS->getType());
3424 if (RHSC->getAPInt().isPowerOf2()) {
3425 Type *FullTy = LHS->getType();
3441 assert(!LHS->getType()->isPointerTy() &&
3442 "SCEVUDivExpr operand can't be pointer!");
3443 assert(LHS->getType() == RHS->getType() &&
3444 "SCEVUDivExpr operand types don't match!");
3455 if (RHSC->getValue()->isOne())
3460 if (!RHSC->getValue()->isZero()) {
3464 Type *Ty = LHS->getType();
3465 unsigned LZ = RHSC->getAPInt().countl_zero();
3469 if (!RHSC->getAPInt().isPowerOf2())
3477 const APInt &StepInt = Step->getAPInt();
3478 const APInt &DivInt = RHSC->getAPInt();
3479 if (!StepInt.
urem(DivInt) &&
3485 for (
const SCEV *
Op : AR->operands())
3491 const APInt *StartRem;
3504 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3508 const SCEV *NewStart =
3510 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3512 const SCEV *NewLHS =
3522 if (M->hasNoUnsignedWrap()) {
3524 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3525 const SCEV *
Op = M->getOperand(i);
3552 if (
auto *DivisorConstant =
3554 bool Overflow =
false;
3556 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3567 if (
A->hasNoUnsignedWrap()) {
3569 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3576 if (
Operands.size() ==
A->getNumOperands())
3588 const APInt &
N = RHSC->getAPInt();
3589 const APInt *NMinusM, *M;
3593 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3594 *NMinusM ==
N - *M) {
3603 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3613 return getZero(LHS->getType());
3617 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3618 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3619 if (
Mul->getOperand(i) == RHS) {
3630 const SCEV *NewLHS, *NewRHS;
3635 return getOrCreateUDivExpr(LHS, RHS);
3655 if (StepChrec->getLoop() == L) {
3674 "SCEVAddRecExpr operand types don't match!");
3675 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3679 "SCEVAddRecExpr operand is not available at loop entry!");
3697 const Loop *NestedLoop = NestedAR->getLoop();
3698 if (L->contains(NestedLoop)
3701 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3703 Operands[0] = NestedAR->getStart();
3707 bool AllInvariant =
all_of(
3719 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3730 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3740 return getOrCreateAddRecExpr(
Operands, L, Flags);
3756 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3760 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3774 bool FirstIter =
true;
3776 for (
SCEVUse IndexExpr : IndexExprs) {
3783 Offsets.push_back(FieldOffset);
3786 CurTy = STy->getTypeAtIndex(Index);
3791 "The first index of a GEP indexes a pointer");
3792 CurTy = SrcElementTy;
3803 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3804 Offsets.push_back(LocalOffset);
3809 if (Offsets.empty())
3822 "GEP should not change type mid-flight.");
3826SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3831 ID.AddPointer(
Op.getOpaqueValue());
3833 return UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
3843 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3844 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3845 if (
Ops.size() == 1)
return Ops[0];
3848 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3850 "Operand types don't match!");
3853 "min/max should be consistently pointerish");
3879 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3881 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3886 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3888 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3894 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3900 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3905 if (Idx <
Ops.size()) {
3906 bool DeletedAny =
false;
3907 while (
Ops[Idx]->getSCEVType() == Kind) {
3909 Ops.erase(
Ops.begin()+Idx);
3927 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3928 if (
Ops[i] ==
Ops[i + 1] ||
3929 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3932 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3935 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3938 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3944 if (
Ops.size() == 1)
return Ops[0];
3946 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
3953 ID.AddPointer(
Op.getOpaqueValue());
3955 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
3957 return ExistingSCEV;
3960 SCEV *S =
new (SCEVAllocator)
3963 UniqueSCEVs.InsertNode(S, IP);
3971class SCEVSequentialMinMaxDeduplicatingVisitor final
3972 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
3973 std::optional<const SCEV *>> {
3974 using RetVal = std::optional<const SCEV *>;
3982 bool canRecurseInto(
SCEVTypes Kind)
const {
3985 return RootKind == Kind || NonSequentialRootKind == Kind;
3988 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
3990 "Only for min/max expressions.");
3993 if (!canRecurseInto(Kind))
4003 return std::nullopt;
4010 RetVal
visit(
const SCEV *S) {
4012 if (!SeenOps.
insert(S).second)
4013 return std::nullopt;
4014 return Base::visit(S);
4018 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4020 : SE(SE), RootKind(RootKind),
4021 NonSequentialRootKind(
4022 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4026 SmallVectorImpl<SCEVUse> &NewOps) {
4031 for (
const SCEV *
Op : OrigOps) {
4036 Ops.emplace_back(*NewOp);
4040 NewOps = std::move(
Ops);
4044 RetVal visitConstant(
const SCEVConstant *Constant) {
return Constant; }
4046 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4048 RetVal visitPtrToAddrExpr(
const SCEVPtrToAddrExpr *Expr) {
return Expr; }
4050 RetVal visitTruncateExpr(
const SCEVTruncateExpr *Expr) {
return Expr; }
4052 RetVal visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
return Expr; }
4054 RetVal visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
return Expr; }
4056 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4058 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4060 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4062 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4064 RetVal visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
4065 return visitAnyMinMaxExpr(Expr);
4068 RetVal visitUMaxExpr(
const SCEVUMaxExpr *Expr) {
4069 return visitAnyMinMaxExpr(Expr);
4072 RetVal visitSMinExpr(
const SCEVSMinExpr *Expr) {
4073 return visitAnyMinMaxExpr(Expr);
4076 RetVal visitUMinExpr(
const SCEVUMinExpr *Expr) {
4077 return visitAnyMinMaxExpr(Expr);
4080 RetVal visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *Expr) {
4081 return visitAnyMinMaxExpr(Expr);
4084 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4086 RetVal visitCouldNotCompute(
const SCEVCouldNotCompute *Expr) {
return Expr; }
4128struct SCEVPoisonCollector {
4129 bool LookThroughMaybePoisonBlocking;
4130 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4131 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4132 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4134 bool follow(
const SCEV *S) {
4135 if (!LookThroughMaybePoisonBlocking &&
4145 bool isDone()
const {
return false; }
4155 SCEVPoisonCollector PC1(
true);
4160 if (PC1.MaybePoison.
empty())
4166 SCEVPoisonCollector PC2(
false);
4176 SCEVPoisonCollector PC(
false);
4199 while (!Worklist.
empty()) {
4201 if (!Visited.
insert(V).second)
4205 if (Visited.
size() > 16)
4221 if (PDI->isDisjoint())
4228 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4235 if (
I->hasPoisonGeneratingAnnotations())
4246 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4247 "Not a SCEVSequentialMinMaxExpr!");
4248 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4249 if (
Ops.size() == 1)
4253 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4255 "Operand types don't match!");
4258 "min/max should be consistently pointerish");
4266 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4273 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4283 bool DeletedAny =
false;
4284 while (Idx <
Ops.size()) {
4285 if (
Ops[Idx]->getSCEVType() != Kind) {
4290 Ops.erase(
Ops.begin() + Idx);
4291 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4292 SMME->operands().end());
4300 const SCEV *SaturationPoint;
4311 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4312 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4324 Ops.erase(
Ops.begin() + i);
4329 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4330 Ops.erase(
Ops.begin() + i);
4340 ID.AddPointer(
Op.getOpaqueValue());
4342 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
4344 return ExistingSCEV;
4348 SCEV *S =
new (SCEVAllocator)
4351 UniqueSCEVs.InsertNode(S, IP);
4399 if (
Size.isScalable())
4420 "Cannot get offset for structure containing scalable vector types");
4434 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) {
4436 "Stale SCEVUnknown in uniquing map!");
4439 SCEV *S =
new (SCEVAllocator)
SCEVUnknown(ID.Intern(SCEVAllocator), V,
this,
4442 UniqueSCEVs.InsertNode(S, IP);
4457 return Ty->isIntOrPtrTy();
4464 if (Ty->isPointerTy())
4475 if (Ty->isIntegerTy())
4479 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4491 bool PreciseA, PreciseB;
4492 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4493 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4494 if (!PreciseA || !PreciseB)
4497 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4498 DT.dominates(ScopeB, ScopeA);
4502 return CouldNotCompute.get();
4505bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4508 return SU && SU->getValue() ==
nullptr;
4511 return !ContainsNulls;
4516 if (
I != HasRecMap.end())
4521 HasRecMap.insert({S, FoundAddRec});
4529 if (
SI == ExprValueMap.
end())
4531 return SI->second.getArrayRef();
4537void ScalarEvolution::eraseValueFromMap(
Value *V) {
4539 if (
I != ValueExprMap.end()) {
4540 auto EVIt = ExprValueMap.find(
I->second);
4541 bool Removed = EVIt->second.remove(V);
4543 assert(Removed &&
"Value not in ExprValueMap?");
4544 ValueExprMap.erase(
I);
4548void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4552 auto It = ValueExprMap.find_as(V);
4553 if (It == ValueExprMap.end()) {
4555 ExprValueMap[S].insert(V);
4566 return createSCEVIter(V);
4573 if (
I != ValueExprMap.end()) {
4574 const SCEV *S =
I->second;
4575 assert(checkValidity(S) &&
4576 "existing SCEV has not been properly invalidated");
4589 Type *Ty = V->getType();
4605 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4618 return (
const SCEV *)
nullptr;
4624 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4628 Type *Ty = V->getType();
4634 assert(
P->getType()->isPointerTy());
4649 if (AddOp->getType()->isPointerTy()) {
4650 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4668 return getZero(LHS->getType());
4673 if (RHS->getType()->isPointerTy()) {
4674 if (!LHS->getType()->isPointerTy() ||
4684 const bool RHSIsNotMinSigned =
4715 Type *SrcTy = V->getType();
4716 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4717 "Cannot truncate or zero extend with non-integer arguments!");
4727 Type *SrcTy = V->getType();
4728 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4729 "Cannot truncate or zero extend with non-integer arguments!");
4738 Type *SrcTy = V->getType();
4739 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4740 "Cannot noop or zero extend with non-integer arguments!");
4742 "getNoopOrZeroExtend cannot truncate!");
4749 Type *SrcTy = V->getType();
4750 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4751 "Cannot noop or sign extend with non-integer arguments!");
4753 "getNoopOrSignExtend cannot truncate!");
4760 Type *SrcTy = V->getType();
4761 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4762 "Cannot noop or any extend with non-integer arguments!");
4764 "getNoopOrAnyExtend cannot truncate!");
4771 Type *SrcTy = V->getType();
4772 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4773 "Cannot truncate or noop with non-integer arguments!");
4775 "getTruncateOrNoop cannot extend!");
4783 const SCEV *PromotedLHS = LHS;
4784 const SCEV *PromotedRHS = RHS;
4804 assert(!
Ops.empty() &&
"At least one operand must be!");
4806 if (
Ops.size() == 1)
4810 Type *MaxType =
nullptr;
4816 assert(MaxType &&
"Failed to find maximum type!");
4829 if (!V->getType()->isPointerTy())
4834 V = AddRec->getStart();
4836 const SCEV *PtrOp =
nullptr;
4837 for (
const SCEV *AddOp :
Add->operands()) {
4838 if (AddOp->getType()->isPointerTy()) {
4839 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4843 assert(PtrOp &&
"Must have pointer op");
4855 for (
User *U :
I->users()) {
4857 if (Visited.
insert(UserInsn).second)
4871 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4872 bool IgnoreOtherLoops =
true) {
4875 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4877 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4882 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4884 SeenLoopVariantSCEVUnknown =
true;
4888 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4892 SeenOtherLoops =
true;
4896 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4898 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4901 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4902 : SCEVRewriteVisitor(SE),
L(
L) {}
4905 bool SeenLoopVariantSCEVUnknown =
false;
4906 bool SeenOtherLoops =
false;
4915 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4916 SCEVPostIncRewriter
Rewriter(L, SE);
4918 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4923 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4925 SeenLoopVariantSCEVUnknown =
true;
4929 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4933 SeenOtherLoops =
true;
4937 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4939 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4942 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4943 : SCEVRewriteVisitor(SE),
L(
L) {}
4946 bool SeenLoopVariantSCEVUnknown =
false;
4947 bool SeenOtherLoops =
false;
4953class SCEVBackedgeConditionFolder
4956 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4957 ScalarEvolution &SE) {
4958 bool IsPosBECond =
false;
4959 Value *BECond =
nullptr;
4960 if (BasicBlock *Latch =
L->getLoopLatch()) {
4962 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
4963 "Both outgoing branches should not target same header!");
4964 BECond = BI->getCondition();
4965 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
4970 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
4974 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4975 const SCEV *
Result = Expr;
4980 switch (
I->getOpcode()) {
4981 case Instruction::Select: {
4983 std::optional<const SCEV *> Res =
4984 compareWithBackedgeCondition(
SI->getCondition());
4992 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5003 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5004 bool IsPosBECond, ScalarEvolution &SE)
5005 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5006 IsPositiveBECond(IsPosBECond) {}
5008 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5012 Value *BackedgeCond =
nullptr;
5014 bool IsPositiveBECond;
5017std::optional<const SCEV *>
5018SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5023 if (BackedgeCond == IC)
5026 return std::nullopt;
5031 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5032 ScalarEvolution &SE) {
5038 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5045 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5055 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5056 : SCEVRewriteVisitor(SE),
L(
L) {}
5064void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5080 const APInt &BECountAP = BECountMax->getAPInt();
5081 unsigned NoOverflowBitWidth =
5090ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5100 if (!SignedWrapViaInductionTried.insert(AR).second)
5125 AC.assumptions().empty())
5133 const SCEV *OverflowLimit =
5135 if (OverflowLimit &&
5143ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5153 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5178 AC.assumptions().empty())
5187 const SCEV *OverflowLimit =
5216 IsNSW = OBO->hasNoSignedWrap();
5217 IsNUW = OBO->hasNoUnsignedWrap();
5223 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5235 return std::nullopt;
5241 switch (
Op->getOpcode()) {
5242 case Instruction::Add:
5243 case Instruction::Sub:
5244 case Instruction::Mul:
5245 case Instruction::UDiv:
5246 case Instruction::URem:
5247 case Instruction::And:
5248 case Instruction::AShr:
5249 case Instruction::Shl:
5252 case Instruction::Or: {
5255 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5265 case Instruction::Xor:
5269 if (RHSC->getValue().isSignMask())
5270 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5272 if (V->getType()->isIntegerTy(1))
5273 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5276 case Instruction::LShr:
5285 if (SA->getValue().ult(
BitWidth)) {
5287 ConstantInt::get(SA->getContext(),
5289 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5294 case Instruction::ExtractValue: {
5296 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5304 bool Signed = WO->isSigned();
5307 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5312 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5323 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5324 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5326 return std::nullopt;
5352 if (
Op == SymbolicPHI)
5357 if (SourceBits != NewBits)
5375 if (!L || L->getHeader() != PN->
getParent())
5433std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5434ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5442 assert(L &&
"Expecting an integer loop header phi");
5447 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5448 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5449 Value *
V = PN->getIncomingValue(i);
5450 if (
L->contains(PN->getIncomingBlock(i))) {
5453 }
else if (BEValueV != V) {
5457 }
else if (!StartValueV) {
5459 }
else if (StartValueV != V) {
5460 StartValueV =
nullptr;
5464 if (!BEValueV || !StartValueV)
5465 return std::nullopt;
5467 const SCEV *BEValue =
getSCEV(BEValueV);
5474 return std::nullopt;
5478 unsigned FoundIndex =
Add->getNumOperands();
5479 Type *TruncTy =
nullptr;
5481 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5484 if (FoundIndex == e) {
5489 if (FoundIndex ==
Add->getNumOperands())
5490 return std::nullopt;
5494 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5495 if (i != FoundIndex)
5496 Ops.push_back(
Add->getOperand(i));
5502 return std::nullopt;
5555 const SCEV *StartVal =
getSCEV(StartValueV);
5556 const SCEV *PHISCEV =
5583 auto getExtendedExpr = [&](
const SCEV *Expr,
5584 bool CreateSignExtend) ->
const SCEV * {
5587 const SCEV *ExtendedExpr =
5590 return ExtendedExpr;
5598 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5599 const SCEV *ExtendedExpr) ->
bool {
5600 return Expr != ExtendedExpr &&
5604 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5605 if (PredIsKnownFalse(StartVal, StartExtended)) {
5607 return std::nullopt;
5612 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5613 if (PredIsKnownFalse(Accum, AccumExtended)) {
5615 return std::nullopt;
5618 auto AppendPredicate = [&](
const SCEV *Expr,
5619 const SCEV *ExtendedExpr) ->
void {
5620 if (Expr != ExtendedExpr &&
5628 AppendPredicate(StartVal, StartExtended);
5629 AppendPredicate(Accum, AccumExtended);
5637 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5638 std::make_pair(NewAR, Predicates);
5640 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5644std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5649 return std::nullopt;
5652 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5653 if (
I != PredicatedSCEVRewrites.end()) {
5654 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5657 if (Rewrite.first == SymbolicPHI)
5658 return std::nullopt;
5662 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5666 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5667 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5672 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5673 return std::nullopt;
5693 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5694 if (Expr1 != Expr2 &&
5695 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5696 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5713const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5715 Value *StartValueV) {
5718 assert(BEValueV && StartValueV);
5724 if (BO->Opcode != Instruction::Add)
5727 const SCEV *Accum =
nullptr;
5728 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5730 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5744 insertValueToMap(PN, PHISCEV);
5747 inferNoWrapViaConstantRanges(AR);
5754 "Accum is defined outside L, but is not invariant?");
5755 if (isAddRecNeverPoison(BEInst, L))
5762const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5770 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5776 }
else if (BEValueV != V) {
5780 }
else if (!StartValueV) {
5782 }
else if (StartValueV != V) {
5783 StartValueV =
nullptr;
5787 if (!BEValueV || !StartValueV)
5790 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5791 "PHI node already processed?");
5795 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5800 insertValueToMap(PN, SymbolicName);
5804 const SCEV *BEValue =
getSCEV(BEValueV);
5814 unsigned FoundIndex =
Add->getNumOperands();
5815 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5816 if (
Add->getOperand(i) == SymbolicName)
5817 if (FoundIndex == e) {
5822 if (FoundIndex !=
Add->getNumOperands()) {
5825 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5826 if (i != FoundIndex)
5827 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5839 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5846 if (
GEP->getOperand(0) == PN) {
5847 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
5865 const SCEV *StartVal =
getSCEV(StartValueV);
5866 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5871 forgetMemoizedResults({SymbolicName});
5872 insertValueToMap(PN, PHISCEV);
5875 inferNoWrapViaConstantRanges(AR);
5899 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5900 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5902 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5903 const SCEV *StartVal =
getSCEV(StartValueV);
5904 if (Start == StartVal) {
5908 forgetMemoizedResults({SymbolicName});
5909 insertValueToMap(PN, Shifted);
5919 eraseValueFromMap(PN);
5934 Use &LeftUse =
Merge->getOperandUse(0);
5935 Use &RightUse =
Merge->getOperandUse(1);
5971 assert(IDom &&
"At least the entry block should dominate PN");
5979const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
5984 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6001 CommonInst = IncomingInst;
6017ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6023 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6024 bool SCEVExprsIdentical =
6026 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6027 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6030const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6031 if (
const SCEV *S = createAddRecFromPHI(PN))
6041 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6044 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6053 struct FindClosure {
6054 const SCEV *OperandToFind;
6060 bool canRecurseInto(
SCEVTypes Kind)
const {
6063 return RootKind == Kind || NonSequentialRootKind == Kind ||
6068 : OperandToFind(OperandToFind), RootKind(RootKind),
6069 NonSequentialRootKind(
6073 bool follow(
const SCEV *S) {
6074 Found = S == OperandToFind;
6076 return !isDone() && canRecurseInto(S->
getSCEVType());
6079 bool isDone()
const {
return Found; }
6082 FindClosure FC(OperandToFind, RootKind);
6087std::optional<const SCEV *>
6088ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6098 switch (ICI->getPredicate()) {
6112 bool Signed = ICI->isSigned();
6113 const SCEV *LA =
getSCEV(TrueVal);
6121 if (LA == LS &&
RA == RS)
6123 if (LA == RS &&
RA == LS)
6126 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6127 if (
Op->getType()->isPointerTy()) {
6138 LS = CoerceOperand(LS);
6139 RS = CoerceOperand(RS);
6163 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6164 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6178 X = ZExt->getOperand();
6180 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6191 return std::nullopt;
6194static std::optional<const SCEV *>
6196 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6200 "Unexpected operands of a select.");
6212 return std::nullopt;
6227static std::optional<const SCEV *>
6231 return std::nullopt;
6234 const auto *SETrue = SE->
getSCEV(TrueVal);
6235 const auto *SEFalse = SE->
getSCEV(FalseVal);
6239const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6241 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6243 V->getType() ==
TrueVal->getType() &&
6244 "Types of select hands and of the result must match.");
6247 if (!
V->getType()->isIntegerTy(1))
6250 if (std::optional<const SCEV *> S =
6263 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6267 if (std::optional<const SCEV *> S =
6268 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6274 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6280 assert(
GEP->getSourceElementType()->isSized() &&
6281 "GEP source element type must be sized");
6284 for (
Value *Index :
GEP->indices())
6289APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6292 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6295 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6297 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6300 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6318 return GetShiftedByZeros(TZ);
6328 return GetShiftedByZeros(TZ);
6332 if (
M->hasNoUnsignedWrap()) {
6335 for (
const SCEV *Operand :
M->operands().drop_front())
6343 for (
const SCEV *Operand :
M->operands())
6345 return GetShiftedByZeros(TZ);
6350 if (
N->hasNoUnsignedWrap())
6351 return GetGCDMultiple(
N);
6354 for (
const SCEV *Operand :
N->operands().drop_front())
6356 return GetShiftedByZeros(TZ);
6373 CtxI = &*F.getEntryBlock().begin();
6380 .allowEphemerals(
true))
6381 .countMinTrailingZeros();
6382 return GetShiftedByZeros(
Known);
6395 return getConstantMultipleImpl(S, CtxI);
6397 auto I = ConstantMultipleCache.find(S);
6398 if (
I != ConstantMultipleCache.end())
6401 APInt Result = getConstantMultipleImpl(S, CtxI);
6402 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6403 assert(InsertPair.second &&
"Should insert a new key");
6404 return InsertPair.first->second;
6421 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6424 if (std::optional<ConstantRange>
Range = CB->getRange())
6428 if (std::optional<ConstantRange>
Range =
A->getRange())
6431 return std::nullopt;
6438 UnsignedRanges.erase(AddRec);
6439 SignedRanges.erase(AddRec);
6440 ConstantMultipleCache.erase(AddRec);
6445getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6471 Value *Start, *Step;
6478 assert(L && L->getHeader() ==
P->getParent());
6491 case Instruction::AShr:
6492 case Instruction::LShr:
6493 case Instruction::Shl:
6508 KnownStep.getBitWidth() ==
BitWidth);
6511 auto MaxShiftAmt = KnownStep.getMaxValue();
6513 bool Overflow =
false;
6514 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6521 case Instruction::AShr: {
6529 if (KnownStart.isNonNegative())
6532 KnownStart.getMaxValue() + 1);
6533 if (KnownStart.isNegative())
6536 KnownEnd.getMaxValue() + 1);
6539 case Instruction::LShr: {
6548 KnownStart.getMaxValue() + 1);
6550 case Instruction::Shl: {
6554 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6555 return ConstantRange(KnownStart.getMinValue(),
6556 KnownEnd.getMaxValue() + 1);
6581 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6588ScalarEvolution::getRangeRefIter(
const SCEV *S,
6589 ScalarEvolution::RangeSignHint SignHint) {
6590 DenseMap<const SCEV *, ConstantRange> &Cache =
6591 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6594 SmallPtrSet<const SCEV *, 8> Seen;
6598 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6599 if (!Seen.
insert(Expr).second)
6632 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6633 const SCEV *
P = WorkList[
I];
6637 for (
const SCEV *
Op :
P->operands())
6650 if (!WorkList.
empty()) {
6655 getRangeRef(
P, SignHint);
6659 return getRangeRef(S, SignHint, 0);
6662const APInt *ScalarEvolution::getConstantAPIntOrNull(
const SCEV *S) {
6664 return &
C->getAPInt();
6672 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6673 DenseMap<const SCEV *, ConstantRange> &Cache =
6674 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6681 auto I = Cache.
find(S);
6682 if (
I != Cache.
end())
6686 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6691 return getRangeRefIter(S, SignHint);
6694 ConstantRange ConservativeResult(
BitWidth,
true);
6695 using OBO = OverflowingBinaryOperator;
6699 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6703 ConservativeResult =
6710 ConservativeResult = ConstantRange(
6726 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6733 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6740 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6745 return setRange(Cast, SignHint,
X);
6750 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6751 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6753 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6754 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6755 ConservativeResult =
6756 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6758 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6759 unsigned WrapType = OBO::AnyWrap;
6760 if (
Add->hasNoSignedWrap())
6761 WrapType |= OBO::NoSignedWrap;
6762 if (
Add->hasNoUnsignedWrap())
6763 WrapType |= OBO::NoUnsignedWrap;
6765 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6767 return setRange(
Add, SignHint,
6768 ConservativeResult.intersectWith(
X, RangeType));
6772 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6774 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6775 return setRange(
Mul, SignHint,
6776 ConservativeResult.intersectWith(
X, RangeType));
6780 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6781 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6782 return setRange(UDiv, SignHint,
6783 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6791 if (!UnsignedMinValue.
isZero())
6792 ConservativeResult = ConservativeResult.intersectWith(
6793 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6802 bool AllNonNeg =
true;
6803 bool AllNonPos =
true;
6804 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6811 ConservativeResult = ConservativeResult.intersectWith(
6816 ConservativeResult = ConservativeResult.intersectWith(
6825 const SCEV *MaxBEScev =
6839 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6841 ConservativeResult =
6842 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6845 auto RangeFromFactoring = getRangeViaFactoring(
6847 ConservativeResult =
6848 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6854 const SCEV *SymbolicMaxBECount =
6859 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6860 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6861 ConservativeResult =
6862 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6867 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6877 ID = Intrinsic::umax;
6880 ID = Intrinsic::smax;
6884 ID = Intrinsic::umin;
6887 ID = Intrinsic::smin;
6894 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6895 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6897 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6898 return setRange(S, SignHint,
6899 ConservativeResult.intersectWith(
X, RangeType));
6908 ConservativeResult =
6909 ConservativeResult.intersectWith(*MDRange, RangeType);
6914 auto CR = getRangeForUnknownRecurrence(U);
6915 ConservativeResult = ConservativeResult.intersectWith(CR);
6926 if (
U->getType()->isPointerTy()) {
6929 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
6930 int ptrIdxDiff = ptrSize -
BitWidth;
6931 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
6937 if (!
Known.Zero.getHiBits(NS).isZero())
6938 Known.Zero.setHighBits(NS);
6939 if (!
Known.One.getHiBits(NS).isZero())
6940 Known.One.setHighBits(NS);
6943 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
6944 ConservativeResult = ConservativeResult.intersectWith(
6945 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
6948 ConservativeResult = ConservativeResult.intersectWith(
6953 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6957 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
6958 DL, CanBeNull,
nullptr);
6974 ConservativeResult = ConservativeResult.intersectWith(
6984 return getRangeRef(AR, SignHint,
Depth + 1);
6988 ConstantRange RangeFromOps(
BitWidth,
false);
6990 for (
const auto &
Op :
Phi->operands()) {
6992 RangeFromOps = RangeFromOps.unionWith(OpRange);
6994 if (RangeFromOps.isFullSet())
6997 ConservativeResult =
6998 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7004 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7006 ConservativeResult = ConservativeResult.difference(Disallowed);
7009 return setRange(U, SignHint, std::move(ConservativeResult));
7015 return setRange(S, SignHint, std::move(ConservativeResult));
7023static std::pair<ConstantRange, bool>
7031 if (Step == 0 || MaxBECount == 0)
7032 return {StartRange,
true};
7038 return {ConstantRange::getFull(
BitWidth),
false};
7054 return {ConstantRange::getFull(
BitWidth),
false};
7067 APInt MovedBoundary;
7072 MovedBoundary = StartLower - std::move(
Offset);
7075 MovedBoundary = StartUpper + std::move(
Offset);
7079 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7086 if (StartRange.
contains(MovedBoundary))
7087 return {ConstantRange::getFull(
BitWidth),
false};
7090 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7092 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7100std::pair<ConstantRange, SCEV::NoWrapFlags>
7101ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7102 const APInt &MaxBECount) {
7106 "mismatched bit widths");
7115 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7117 StartSRange, MaxBECount,
7119 ConstantRange SR = SR1.unionWith(SR2);
7136ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7138 ScalarEvolution::RangeSignHint SignHint) {
7139 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7141 "This only works for non-self-wrapping AddRecs!");
7142 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7146 return ConstantRange::getFull(
BitWidth);
7154 return ConstantRange::getFull(
BitWidth);
7158 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7160 MaxItersWithoutWrap))
7161 return ConstantRange::getFull(
BitWidth);
7182 ConstantRange StartRange = getRangeRef(Start, SignHint);
7183 ConstantRange EndRange = getRangeRef(End, SignHint);
7184 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7188 return RangeBetween;
7193 return ConstantRange::getFull(
BitWidth);
7196 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7197 return RangeBetween;
7199 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7200 return RangeBetween;
7201 return ConstantRange::getFull(
BitWidth);
7206 const APInt &MaxBECount) {
7213 "mismatched bit widths");
7215 struct SelectPattern {
7216 Value *Condition =
nullptr;
7220 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7222 std::optional<unsigned> CastOp;
7236 CastOp = SCast->getSCEVType();
7237 S = SCast->getOperand();
7240 using namespace llvm::PatternMatch;
7247 Condition =
nullptr;
7279 bool isRecognized() {
return Condition !=
nullptr; }
7282 SelectPattern StartPattern(*
this,
BitWidth, Start);
7283 if (!StartPattern.isRecognized())
7284 return ConstantRange::getFull(
BitWidth);
7286 SelectPattern StepPattern(*
this,
BitWidth, Step);
7287 if (!StepPattern.isRecognized())
7288 return ConstantRange::getFull(
BitWidth);
7290 if (StartPattern.Condition != StepPattern.Condition) {
7294 return ConstantRange::getFull(
BitWidth);
7305 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7306 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7307 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7308 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7310 ConstantRange TrueRange =
7311 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7312 ConstantRange FalseRange =
7313 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7325 PDI && PDI->isDisjoint()) {
7340ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7353 SmallPtrSet<const SCEV *, 16> Visited;
7355 auto pushOp = [&](
const SCEV *S) {
7356 if (!Visited.
insert(S).second)
7359 if (Visited.
size() > 30) {
7370 while (!Worklist.
empty()) {
7372 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7373 if (!Bound || DT.dominates(Bound, DefI))
7380 return Bound ? Bound : &*F.getEntryBlock().begin();
7386 return getDefiningScopeBound(
Ops, Discard);
7389bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7391 if (
A->getParent() ==
B->getParent() &&
7396 auto *BLoop = LI.getLoopFor(
B->getParent());
7397 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7398 BLoop->getLoopPreheader() ==
A->getParent() &&
7400 A->getParent()->end()) &&
7408 SCEVPoisonCollector PC(
true);
7410 return PC.MaybePoison.
empty();
7413bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7423bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7440 for (
const Use &
Op :
I->operands()) {
7446 auto *DefI = getDefiningScopeBound(SCEVOps);
7447 return isGuaranteedToTransferExecutionTo(DefI,
I);
7450bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7452 if (isSCEVExprNeverPoison(
I))
7463 auto *ExitingBB =
L->getExitingBlock();
7467 SmallPtrSet<const Value *, 16> KnownPoison;
7476 while (!Worklist.
empty()) {
7479 for (
const Use &U :
Poison->uses()) {
7482 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7486 if (KnownPoison.
insert(PoisonUser).second)
7494ScalarEvolution::LoopProperties
7495ScalarEvolution::getLoopProperties(
const Loop *L) {
7496 using LoopProperties = ScalarEvolution::LoopProperties;
7498 auto Itr = LoopPropertiesCache.find(L);
7499 if (Itr == LoopPropertiesCache.end()) {
7502 return !
SI->isSimple();
7512 return I->mayWriteToMemory();
7515 LoopProperties LP = {
true,
7518 for (
auto *BB :
L->getBlocks())
7519 for (
auto &
I : *BB) {
7521 LP.HasNoAbnormalExits =
false;
7522 if (HasSideEffects(&
I))
7523 LP.HasNoSideEffects =
false;
7524 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7528 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7529 assert(InsertPair.second &&
"We just checked!");
7530 Itr = InsertPair.first;
7543const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7549 Stack.emplace_back(V,
false);
7550 while (!Stack.empty()) {
7551 auto E = Stack.back();
7552 Value *CurV = E.getPointer();
7560 const SCEV *CreatedSCEV =
nullptr;
7563 CreatedSCEV = createSCEV(CurV);
7568 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7572 insertValueToMap(CurV, CreatedSCEV);
7575 Stack.back().setInt(
true);
7578 Stack.emplace_back(
Op,
false);
7595 if (!DT.isReachableFromEntry(
I->getParent()))
7608 switch (BO->Opcode) {
7609 case Instruction::Add:
7610 case Instruction::Mul: {
7617 Ops.push_back(BO->
Op);
7621 Ops.push_back(BO->RHS);
7625 (BO->Opcode == Instruction::Add &&
7626 (NewBO->Opcode != Instruction::Add &&
7627 NewBO->Opcode != Instruction::Sub)) ||
7628 (BO->Opcode == Instruction::Mul &&
7629 NewBO->Opcode != Instruction::Mul)) {
7630 Ops.push_back(BO->LHS);
7635 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7638 Ops.push_back(BO->LHS);
7646 case Instruction::Sub:
7647 case Instruction::UDiv:
7648 case Instruction::URem:
7650 case Instruction::AShr:
7651 case Instruction::Shl:
7652 case Instruction::Xor:
7656 case Instruction::And:
7657 case Instruction::Or:
7661 case Instruction::LShr:
7668 Ops.push_back(BO->LHS);
7669 Ops.push_back(BO->RHS);
7673 switch (
U->getOpcode()) {
7674 case Instruction::Trunc:
7675 case Instruction::ZExt:
7676 case Instruction::SExt:
7677 case Instruction::PtrToAddr:
7678 case Instruction::PtrToInt:
7679 Ops.push_back(
U->getOperand(0));
7682 case Instruction::BitCast:
7684 Ops.push_back(
U->getOperand(0));
7689 case Instruction::SDiv:
7690 case Instruction::SRem:
7691 Ops.push_back(
U->getOperand(0));
7692 Ops.push_back(
U->getOperand(1));
7695 case Instruction::GetElementPtr:
7697 "GEP source element type must be sized");
7701 case Instruction::IntToPtr:
7704 case Instruction::PHI:
7735 Ops.push_back(CondICmp->getOperand(0));
7736 Ops.push_back(CondICmp->getOperand(1));
7756 case Instruction::Select: {
7758 auto CanSimplifyToUnknown = [
this,
U]() {
7776 if (CanSimplifyToUnknown())
7783 case Instruction::Call:
7784 case Instruction::Invoke:
7791 switch (
II->getIntrinsicID()) {
7792 case Intrinsic::abs:
7793 Ops.push_back(
II->getArgOperand(0));
7795 case Intrinsic::umax:
7796 case Intrinsic::umin:
7797 case Intrinsic::smax:
7798 case Intrinsic::smin:
7799 case Intrinsic::usub_sat:
7800 case Intrinsic::uadd_sat:
7801 Ops.push_back(
II->getArgOperand(0));
7802 Ops.push_back(
II->getArgOperand(1));
7804 case Intrinsic::start_loop_iterations:
7805 case Intrinsic::annotation:
7806 case Intrinsic::ptr_annotation:
7807 Ops.push_back(
II->getArgOperand(0));
7819const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7828 if (!DT.isReachableFromEntry(
I->getParent()))
7843 switch (BO->Opcode) {
7844 case Instruction::Add: {
7870 if (BO->Opcode == Instruction::Sub)
7878 if (BO->Opcode == Instruction::Sub)
7885 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7886 NewBO->Opcode != Instruction::Sub)) {
7896 case Instruction::Mul: {
7917 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7926 case Instruction::UDiv:
7930 case Instruction::URem:
7934 case Instruction::Sub: {
7937 Flags = getNoWrapFlagsFromUB(BO->
Op);
7942 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
7945 if (HasPtrLHS || HasPtrRHS) {
7950 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
7951 bool BothPtr) ->
const SCEV * {
7954 const SCEV *PtrSCEV =
getSCEV(PtrOp);
7964 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
7965 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
7973 case Instruction::And:
7979 if (CI->isMinusOne())
7981 const APInt &
A = CI->getValue();
7987 unsigned LZ =
A.countl_zero();
7988 unsigned TZ =
A.countr_zero();
7993 APInt EffectiveMask =
7995 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
7998 const SCEV *ShiftedLHS =
nullptr;
8002 unsigned MulZeros = OpC->getAPInt().countr_zero();
8003 unsigned GCD = std::min(MulZeros, TZ);
8008 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8030 case Instruction::Or:
8039 case Instruction::Xor:
8042 if (CI->isMinusOne())
8051 if (LBO->getOpcode() == Instruction::And &&
8052 LCI->getValue() == CI->getValue())
8053 if (
const SCEVZeroExtendExpr *Z =
8056 const SCEV *Z0 =
Z->getOperand();
8063 if (CI->getValue().isMask(Z0TySize))
8069 APInt Trunc = CI->getValue().trunc(Z0TySize);
8078 case Instruction::Shl:
8096 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8105 ConstantInt *
X = ConstantInt::get(
8111 case Instruction::AShr:
8133 const SCEV *AddTruncateExpr =
nullptr;
8134 ConstantInt *ShlAmtCI =
nullptr;
8135 const SCEV *AddConstant =
nullptr;
8137 if (L &&
L->getOpcode() == Instruction::Add) {
8145 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8152 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8160 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8165 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8170 if (AddTruncateExpr && ShlAmtCI) {
8182 const APInt &ShlAmt = ShlAmtCI->
getValue();
8186 const SCEV *CompositeExpr =
8188 if (
L->getOpcode() != Instruction::Shl)
8189 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8198 switch (
U->getOpcode()) {
8199 case Instruction::Trunc:
8202 case Instruction::ZExt:
8205 case Instruction::SExt:
8215 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8216 Type *Ty =
U->getType();
8224 case Instruction::BitCast:
8230 case Instruction::PtrToAddr: {
8237 case Instruction::PtrToInt:
8241 case Instruction::IntToPtr:
8245 case Instruction::SDiv:
8252 case Instruction::SRem:
8259 case Instruction::GetElementPtr:
8262 case Instruction::PHI:
8265 case Instruction::Select:
8266 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8269 case Instruction::Call:
8270 case Instruction::Invoke:
8275 switch (
II->getIntrinsicID()) {
8276 case Intrinsic::abs:
8280 case Intrinsic::umax:
8284 case Intrinsic::umin:
8288 case Intrinsic::smax:
8292 case Intrinsic::smin:
8296 case Intrinsic::usub_sat: {
8297 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8298 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8302 case Intrinsic::uadd_sat: {
8303 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8304 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8308 case Intrinsic::start_loop_iterations:
8309 case Intrinsic::annotation:
8310 case Intrinsic::ptr_annotation:
8314 case Intrinsic::vscale:
8334 auto *ExitCountType = ExitCount->
getType();
8335 assert(ExitCountType->isIntegerTy());
8337 1 + ExitCountType->getScalarSizeInBits());
8350 auto CanAddOneWithoutOverflow = [&]() {
8352 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8363 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8393 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8394 assert(L->isLoopExiting(ExitingBlock) &&
8395 "Exiting block must actually branch out of the loop!");
8404 const auto *MaxExitCount =
8412 L->getExitingBlocks(ExitingBlocks);
8414 std::optional<unsigned> Res;
8415 for (
auto *ExitingBB : ExitingBlocks) {
8419 Res = std::gcd(*Res, Multiple);
8421 return Res.value_or(1);
8425 const SCEV *ExitCount) {
8455 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8456 assert(L->isLoopExiting(ExitingBlock) &&
8457 "Exiting block must actually branch out of the loop!");
8467 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8469 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8471 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8481 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8484 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8487 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8495 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8502 return getBackedgeTakenInfo(L).getExact(L,
this);
8504 return getBackedgeTakenInfo(L).getConstantMax(
this);
8506 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8513 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8518 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8522 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8532 for (
PHINode &PN : Header->phis())
8533 if (Visited.
insert(&PN).second)
8537ScalarEvolution::BackedgeTakenInfo &
8538ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8539 auto &BTI = getBackedgeTakenInfo(L);
8540 if (BTI.hasFullInfo())
8543 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8546 return Pair.first->second;
8548 BackedgeTakenInfo
Result =
8549 computeBackedgeTakenCount(L,
true);
8551 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8554ScalarEvolution::BackedgeTakenInfo &
8555ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8561 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8562 BackedgeTakenCounts.try_emplace(L);
8564 return Pair.first->second;
8569 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8576 if (
Result.hasAnyInfo()) {
8579 auto LoopUsersIt = LoopUsers.find(L);
8580 if (LoopUsersIt != LoopUsers.end())
8582 forgetMemoizedResults(ToForget);
8585 for (PHINode &PN :
L->getHeader()->phis())
8586 ConstantEvolutionLoopExitValue.erase(&PN);
8594 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8603 BackedgeTakenCounts.clear();
8604 PredicatedBackedgeTakenCounts.clear();
8605 BECountUsers.clear();
8606 LoopPropertiesCache.clear();
8607 ConstantEvolutionLoopExitValue.clear();
8608 ValueExprMap.clear();
8609 ValuesAtScopes.clear();
8610 ValuesAtScopesUsers.clear();
8611 LoopDispositions.clear();
8612 BlockDispositions.clear();
8613 UnsignedRanges.clear();
8614 SignedRanges.clear();
8615 ExprValueMap.clear();
8617 ConstantMultipleCache.clear();
8618 PredicatedSCEVRewrites.clear();
8620 FoldCacheUser.clear();
8622void ScalarEvolution::visitAndClearUsers(
8626 while (!Worklist.
empty()) {
8633 if (It != ValueExprMap.
end()) {
8635 eraseValueFromMap(It->first);
8637 ConstantEvolutionLoopExitValue.erase(PN);
8651 while (!LoopWorklist.
empty()) {
8655 forgetBackedgeTakenCounts(CurrL,
false);
8656 forgetBackedgeTakenCounts(CurrL,
true);
8659 PredicatedSCEVRewrites.remove_if(
8660 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8662 auto LoopUsersItr = LoopUsers.find(CurrL);
8663 if (LoopUsersItr != LoopUsers.end())
8668 visitAndClearUsers(Worklist, Visited, ToForget);
8670 LoopPropertiesCache.erase(CurrL);
8673 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8675 forgetMemoizedResults(ToForget);
8692 visitAndClearUsers(Worklist, Visited, ToForget);
8694 forgetMemoizedResults(ToForget);
8702 auto InvalidateValue = [&](
Value *Val) {
8706 struct InvalidationRootCollector {
8710 InvalidationRootCollector(
Loop *L) : L(L) {}
8712 bool follow(
const SCEV *S) {
8718 if (L->contains(AddRec->
getLoop()))
8723 bool isDone()
const {
return false; }
8726 InvalidationRootCollector
C(L);
8728 forgetMemoizedResults(
C.Roots);
8738 return isa<WithOverflowInst>(Inc);
8752 BlockDispositions.clear();
8753 LoopDispositions.clear();
8770 while (!Worklist.
empty()) {
8772 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8773 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8774 if (!LoopDispoRemoved && !BlockDispoRemoved)
8776 auto Users = SCEVUsers.find(Curr);
8777 if (
Users != SCEVUsers.end())
8790const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8794 if (!isComplete() || ExitNotTaken.
empty())
8805 for (
const auto &ENT : ExitNotTaken) {
8806 const SCEV *BECount = ENT.ExactNotTaken;
8809 "We should only have known counts for exiting blocks that dominate "
8812 Ops.push_back(BECount);
8817 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8818 "Predicate should be always true!");
8827const ScalarEvolution::ExitNotTakenInfo *
8828ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8829 const BasicBlock *ExitingBlock,
8830 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8831 for (
const auto &ENT : ExitNotTaken)
8832 if (ENT.ExitingBlock == ExitingBlock) {
8833 if (ENT.hasAlwaysTruePredicate())
8835 else if (Predicates) {
8845const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8847 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8848 if (!getConstantMax())
8851 for (
const auto &ENT : ExitNotTaken)
8852 if (!ENT.hasAlwaysTruePredicate()) {
8860 "No point in having a non-constant max backedge taken count!");
8861 return getConstantMax();
8864const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8866 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8874 for (
const auto &ENT : ExitNotTaken) {
8875 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8878 "We should only have known counts for exiting blocks that "
8884 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8885 "Predicate should be always true!");
8888 if (ExitCounts.
empty())
8897bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8899 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8900 return !ENT.hasAlwaysTruePredicate();
8902 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8918 this->ExactNotTaken = E = ConstantMaxNotTaken;
8919 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8924 "Exact is not allowed to be less precise than Constant Max");
8927 "Exact is not allowed to be less precise than Symbolic Max");
8930 "Symbolic Max is not allowed to be less precise than Constant Max");
8933 "No point in having a non-constant max backedge taken count!");
8935 for (
const auto PredList : PredLists)
8936 for (
const auto *
P : PredList) {
8944 "Backedge count should be int");
8947 "Max backedge count should be int");
8960ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8962 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8963 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8964 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8966 ExitNotTaken.reserve(ExitCounts.
size());
8967 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8968 std::back_inserter(ExitNotTaken),
8969 [&](
const EdgeExitInfo &EEI) {
8970 BasicBlock *ExitBB = EEI.first;
8971 const ExitLimit &EL = EEI.second;
8972 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
8973 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
8978 "No point in having a non-constant max backedge taken count!");
8982ScalarEvolution::BackedgeTakenInfo
8983ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
8984 bool AllowPredicates) {
8986 L->getExitingBlocks(ExitingBlocks);
8988 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8991 bool CouldComputeBECount =
true;
8993 const SCEV *MustExitMaxBECount =
nullptr;
8994 const SCEV *MayExitMaxBECount =
nullptr;
8995 bool MustExitMaxOrZero =
false;
8996 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9007 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9008 if (ExitIfTrue == CI->
isZero())
9012 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9014 assert((AllowPredicates || EL.Predicates.empty()) &&
9015 "Predicated exit limit when predicates are not allowed!");
9020 ++NumExitCountsComputed;
9024 CouldComputeBECount =
false;
9031 "Exact is known but symbolic isn't?");
9032 ++NumExitCountsNotComputed;
9047 DT.dominates(ExitBB, Latch)) {
9048 if (!MustExitMaxBECount) {
9049 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9050 MustExitMaxOrZero = EL.MaxOrZero;
9053 EL.ConstantMaxNotTaken);
9057 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9060 EL.ConstantMaxNotTaken);
9064 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9068 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9074 for (
const auto &Pair : ExitCounts) {
9076 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9078 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9079 {
L, AllowPredicates});
9081 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9082 MaxBECount, MaxOrZero);
9085ScalarEvolution::ExitLimit
9086ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9087 bool IsOnlyExit,
bool AllowPredicates) {
9088 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9092 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9097 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9098 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9099 "It should have one successor in loop and one exit block!");
9110 if (!
L->contains(SBB)) {
9115 assert(Exit &&
"Exiting block must have at least one exit");
9116 return computeExitLimitFromSingleExitSwitch(
9117 L, SI, Exit, IsOnlyExit);