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"));
242 "scalar-evolution-max-scc-analysis-depth",
cl::Hidden,
243 cl::desc(
"Maximum amount of nodes to process while searching SCEVUnknown "
244 "Phi strongly connected components"),
249 cl::desc(
"Handle <= and >= in finite loops"),
253 "scalar-evolution-use-context-for-no-wrap-flag-strenghening",
cl::Hidden,
254 cl::desc(
"Infer nuw/nsw flags using context where suitable"),
343#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
363 OS <<
"(ptrto" << OpS <<
" " << *
Op->getType() <<
" " << *
Op <<
" to "
370 OS <<
"(trunc " << *
Op->getType() <<
" " << *
Op <<
" to "
377 OS <<
"(zext " << *
Op->getType() <<
" " << *
Op <<
" to "
384 OS <<
"(sext " << *
Op->getType() <<
" " << *
Op <<
" to "
413 const char *OpStr =
nullptr;
426 OpStr =
" umin_seq ";
450 OS <<
"(" << *UDiv->
getLHS() <<
" /u " << *UDiv->
getRHS() <<
")";
457 OS <<
"***COULDNOTCOMPUTE***";
535 if (!
Mul)
return false;
539 if (!SC)
return false;
557 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
559 UniqueSCEVs.InsertNode(S, IP);
574 ConstantInt::get(ITy, V,
isSigned,
true));
582 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
585 UniqueSCEVs.InsertNode(S, IP);
606 "Must be a non-bit-width-changing pointer-to-integer cast!");
613 "Must be a non-bit-width-changing pointer-to-integer cast!");
625 "Cannot truncate non-integer value!");
632 "Cannot zero extend non-integer value!");
639 "Cannot sign extend non-integer value!");
644 SE->forgetMemoizedResults({
this});
647 SE->UniqueSCEVs.RemoveNode(
this);
653void SCEVUnknown::allUsesReplacedWith(
Value *New) {
655 SE->forgetMemoizedResults({
this});
658 SE->UniqueSCEVs.RemoveNode(
this);
680 if (LIsPointer != RIsPointer)
681 return (
int)LIsPointer - (int)RIsPointer;
686 return (
int)LID - (int)RID;
691 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
692 return (
int)LArgNo - (int)RArgNo;
698 if (
auto L = LGV->getLinkage() - RGV->getLinkage())
701 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
702 auto LT = GV->getLinkage();
709 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
710 return LGV->getName().compare(RGV->getName());
721 if (LParent != RParent) {
724 if (LDepth != RDepth)
725 return (
int)LDepth - (int)RDepth;
729 unsigned LNumOps = LInst->getNumOperands(),
730 RNumOps = RInst->getNumOperands();
731 if (LNumOps != RNumOps)
732 return (
int)LNumOps - (int)RNumOps;
734 for (
unsigned Idx :
seq(LNumOps)) {
736 RInst->getOperand(Idx),
Depth + 1);
750static std::optional<int>
760 return (
int)LType - (int)RType;
785 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
786 if (LBitWidth != RBitWidth)
787 return (
int)LBitWidth - (int)RBitWidth;
788 return LA.
ult(
RA) ? -1 : 1;
794 return LTy->getBitWidth() - RTy->getBitWidth();
805 if (LLoop != RLoop) {
807 assert(LHead != RHead &&
"Two loops share the same header?");
811 "No dominance between recurrences used by one SCEV?");
835 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
836 if (LNumOps != RNumOps)
837 return (
int)LNumOps - (int)RNumOps;
839 for (
unsigned i = 0; i != LNumOps; ++i) {
865 if (
Ops.size() < 2)
return;
870 return Complexity && *Complexity < 0;
872 if (
Ops.size() == 2) {
876 if (IsLessComplex(
RHS,
LHS))
889 for (
unsigned i = 0, e =
Ops.size(); i != e-2; ++i) {
895 for (
unsigned j = i+1; j != e &&
Ops[j]->getSCEVType() == Complexity; ++j) {
900 if (i == e-2)
return;
922template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
926 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
928 for (
unsigned Idx = 0; Idx <
Ops.size();) {
936 Ops.erase(
Ops.begin() + Idx);
943 assert(Folded &&
"Must have folded value");
947 if (Folded && IsAbsorber(Folded->
getAPInt()))
951 if (Folded && !IsIdentity(Folded->
getAPInt()))
952 Ops.insert(
Ops.begin(), Folded);
954 return Ops.size() == 1 ?
Ops[0] :
nullptr;
1029 APInt OddFactorial(W, 1);
1031 for (
unsigned i = 3; i <= K; ++i) {
1034 OddFactorial *= (i >> TwoFactors);
1038 unsigned CalculationBits = W +
T;
1052 for (
unsigned i = 1; i != K; ++i) {
1085 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1114 ConversionFn CreatePtrCast;
1118 ConversionFn CreatePtrCast)
1119 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
1122 Type *TargetTy, ConversionFn CreatePtrCast) {
1124 return Rewriter.visit(Scev);
1160 "Should only reach pointer-typed SCEVUnknown's.");
1165 return SE.getZero(TargetTy);
1166 return CreatePtrCast(Expr);
1171 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1195 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1197 SCEV *S =
new (SCEVAllocator)
1199 UniqueSCEVs.InsertNode(S, IP);
1202 return static_cast<const SCEV *
>(S);
1205 "We must have succeeded in sinking the cast, "
1206 "and ending up with an integer-typed expression!");
1211 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1215 if (DL.hasUnstableRepresentation(
Op->getType()))
1218 Type *Ty = DL.getAddressType(
Op->getType());
1229 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1231 SCEV *S =
new (SCEVAllocator)
1233 UniqueSCEVs.InsertNode(S, IP);
1236 return static_cast<const SCEV *
>(S);
1239 "We must have succeeded in sinking the cast, "
1240 "and ending up with an integer-typed expression!");
1245 assert(Ty->isIntegerTy() &&
"Target type must be an integer type!");
1257 "This is not a truncating conversion!");
1259 "This is not a conversion to a SCEVable type!");
1260 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1268 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1290 UniqueSCEVs.InsertNode(S, IP);
1303 unsigned numTruncs = 0;
1304 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1312 if (numTruncs < 2) {
1322 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1329 for (
const SCEV *
Op : AddRec->operands())
1344 UniqueSCEVs.InsertNode(S, IP);
1385struct ExtendOpTraitsBase {
1386 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
const SCEV *,
Type *,
1391template <
typename ExtendOp>
struct ExtendOpTraits {
1407 static const GetExtendExprTy GetExtendExpr;
1409 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1410 ICmpInst::Predicate *Pred,
1411 ScalarEvolution *SE) {
1416const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1423 static const GetExtendExprTy GetExtendExpr;
1425 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1426 ICmpInst::Predicate *Pred,
1427 ScalarEvolution *SE) {
1432const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1444template <
typename ExtendOpTy>
1447 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1448 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1464 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1477 auto PreStartFlags =
1495 const SCEV *OperandExtendedStart =
1497 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1498 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1510 const SCEV *OverflowLimit =
1511 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1513 if (OverflowLimit &&
1521template <
typename ExtendOpTy>
1525 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1533 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1568template <
typename ExtendOpTy>
1569bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1572 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1582 APInt StartAI = StartC->
getAPInt();
1584 for (
unsigned Delta : {-2, -1, 1, 2}) {
1585 const SCEV *PreStart =
getConstant(StartAI - Delta);
1587 FoldingSetNodeID
ID;
1589 ID.AddPointer(PreStart);
1590 ID.AddPointer(Step);
1594 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
1598 if (PreAR &&
any(PreAR->getNoWrapFlags(WrapType))) {
1601 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1602 DeltaS, &Pred,
this);
1620 const unsigned BitWidth =
C.getBitWidth();
1638 const APInt &ConstantStart,
1657 auto &UserIDs = FoldCacheUser[
I.first->second];
1658 assert(
count(UserIDs,
ID) == 1 &&
"unexpected duplicates in UserIDs");
1659 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1660 if (UserIDs[
I] ==
ID) {
1665 I.first->second = S;
1667 FoldCacheUser[S].push_back(
ID);
1673 "This is not an extending conversion!");
1675 "This is not a conversion to a SCEVable type!");
1676 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1680 if (
const SCEV *S = FoldCache.lookup(
ID))
1692 "This is not an extending conversion!");
1694 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1708 if (AR->isAffine() && AR->hasNoUnsignedWrap()) {
1713 return getAddRecExpr(Start, Step, AR->getLoop(), AR->getNoWrapFlags());
1723 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1727 UniqueSCEVs.InsertNode(S, IP);
1737 const SCEV *
X = ST->getOperand();
1751 if (AR->isAffine()) {
1752 const SCEV *Start = AR->getStart();
1753 const SCEV *Step = AR->getStepRecurrence(*
this);
1755 const Loop *L = AR->getLoop();
1773 const SCEV *CastedMaxBECount =
1777 if (MaxBECount == RecastedMaxBECount) {
1787 const SCEV *WideMaxBECount =
1789 const SCEV *OperandExtendedAdd =
1795 if (ZAdd == OperandExtendedAdd) {
1806 OperandExtendedAdd =
1812 if (ZAdd == OperandExtendedAdd) {
1833 !AC.assumptions().empty()) {
1835 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1837 if (AR->hasNoUnsignedWrap()) {
1872 const APInt &
C = SC->getAPInt();
1876 const SCEV *SResidual =
1884 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1909 if (SA->hasNoUnsignedWrap()) {
1922 if (SA->hasNoSignedWrap() &&
1925 C->isNegative() && !
C->isMinSignedValue() && C2->
sge(
C->abs())) {
1944 const SCEV *SResidual =
1955 if (
SM->hasNoUnsignedWrap()) {
1977 const SCEV *TruncRHS;
2014 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
2017 UniqueSCEVs.InsertNode(S, IP);
2026 "This is not an extending conversion!");
2028 "This is not a conversion to a SCEVable type!");
2029 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
2033 if (
const SCEV *S = FoldCache.lookup(
ID))
2045 "This is not an extending conversion!");
2047 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
2066 if (AR->isAffine() && AR->hasNoSignedWrap()) {
2081 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
2086 UniqueSCEVs.InsertNode(S, IP);
2096 const SCEV *
X = ST->getOperand();
2107 if (SA->hasNoSignedWrap()) {
2129 const SCEV *SResidual =
2142 if (AR->isAffine()) {
2143 const SCEV *Start = AR->getStart();
2144 const SCEV *Step = AR->getStepRecurrence(*
this);
2146 const Loop *L = AR->getLoop();
2165 const SCEV *CastedMaxBECount =
2169 if (MaxBECount == RecastedMaxBECount) {
2179 const SCEV *WideMaxBECount =
2181 const SCEV *OperandExtendedAdd =
2187 if (SAdd == OperandExtendedAdd) {
2198 OperandExtendedAdd =
2204 if (SAdd == OperandExtendedAdd) {
2224 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2226 if (AR->hasNoSignedWrap()) {
2241 const APInt &
C = SC->getAPInt();
2245 const SCEV *SResidual =
2253 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2281 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
2284 UniqueSCEVs.InsertNode(S, IP);
2311 "This is not an extending conversion!");
2313 "This is not a conversion to a SCEVable type!");
2318 if (SC->getAPInt().isNegative())
2323 const SCEV *NewOp =
T->getOperand();
2342 for (
const SCEV *
Op : AR->operands())
2380 APInt &AccumulatedConstant,
2384 bool Interesting =
false;
2391 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2393 AccumulatedConstant += Scale *
C->getAPInt();
2398 for (; i !=
Ops.size(); ++i) {
2407 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2413 auto Pair = M.insert({
Key, NewScale});
2417 Pair.first->second += NewScale;
2425 auto Pair = M.insert({
Ops[i], Scale});
2429 Pair.first->second += Scale;
2448 case Instruction::Add:
2451 case Instruction::Sub:
2454 case Instruction::Mul:
2468 const SCEV *
A = (this->*Extension)(
2470 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2471 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2479 if (BinOp == Instruction::Mul)
2485 APInt C = RHSC->getAPInt();
2486 unsigned NumBits =
C.getBitWidth();
2487 bool IsSub = (BinOp == Instruction::Sub);
2488 bool IsNegativeConst = (
Signed &&
C.isNegative());
2490 bool OverflowDown = IsSub ^ IsNegativeConst;
2492 if (IsNegativeConst) {
2505 APInt Limit = Min + Magnitude;
2511 APInt Limit = Max - Magnitude;
2516std::optional<SCEV::NoWrapFlags>
2521 return std::nullopt;
2530 bool Deduced =
false;
2532 if (OBO->
getOpcode() != Instruction::Add &&
2535 return std::nullopt;
2544 false, LHS, RHS, CtxI)) {
2551 true, LHS, RHS, CtxI)) {
2558 return std::nullopt;
2568 using namespace std::placeholders;
2575 assert(CanAnalyze &&
"don't call from other places!");
2582 auto IsKnownNonNegative = [&](
SCEVUse U) {
2591 if (SignOrUnsignWrap != SignOrUnsignMask &&
2598 return Instruction::Add;
2600 return Instruction::Mul;
2611 Opcode,
C, OBO::NoSignedWrap);
2619 Opcode,
C, OBO::NoUnsignedWrap);
2629 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2636 if (UDiv->getOperand(1) ==
Ops[1])
2639 if (UDiv->getOperand(1) ==
Ops[0])
2655 "only nuw or nsw allowed");
2656 assert(!
Ops.empty() &&
"Cannot get empty add!");
2657 if (
Ops.size() == 1)
return Ops[0];
2660 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2662 "SCEVAddExpr operand types don't match!");
2664 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2665 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2670 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2671 [](
const APInt &
C) {
return C.isZero(); },
2672 [](
const APInt &
C) {
return false; });
2685 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2690 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2691 Add->setNoWrapFlags(ComputeFlags(
Ops));
2699 bool FoundMatch =
false;
2700 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2701 if (
Ops[i] ==
Ops[i+1]) {
2713 --i; e -=
Count - 1;
2723 auto FindTruncSrcType = [&]() ->
Type * {
2729 return T->getOperand()->getType();
2731 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2733 return T->getOperand()->getType();
2737 if (
auto *SrcType = FindTruncSrcType()) {
2744 if (
T->getOperand()->getType() != SrcType) {
2753 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2756 if (
T->getOperand()->getType() != SrcType) {
2784 if (
Ops.size() == 2) {
2794 auto C2 =
C->getAPInt();
2797 APInt ConstAdd = C1 + C2;
2798 auto AddFlags = AddExpr->getNoWrapFlags();
2839 if (
Ops.size() == 2 &&
2850 if (Idx <
Ops.size()) {
2851 bool DeletedAdd =
false;
2862 Ops.erase(
Ops.begin()+Idx);
2865 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2888 struct APIntCompare {
2889 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2890 return LHS.ult(RHS);
2897 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2898 for (
const SCEV *NewOp : NewOps)
2899 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2902 if (AccumulatedConstant != 0)
2904 for (
auto &MulOp : MulOpLists) {
2905 if (MulOp.first == 1) {
2907 }
else if (MulOp.first != 0) {
2916 if (
Ops.size() == 1)
2925 if (M->getNumOperands() == 2)
2926 return M->getOperand(
OpIdx == 0);
2937 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2941 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2949 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp) {
2950 if (MulOpSCEV ==
Ops[AddOp]) {
2961 for (
unsigned OMulOp = 0, OE = OtherMul->
getNumOperands(); OMulOp != OE;
2963 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2965 Cofactors.
push_back(StripFactor(OtherMul, OMulOp));
2974 if (!Cofactors.
empty()) {
2982 if (
Ops.size() == DeadIndices.
size() + 1)
2989 Ops.erase(
Ops.begin() + Idx);
2993 Ops.push_back(OuterMul);
3012 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3015 Ops.erase(
Ops.begin()+i);
3020 if (!LIOps.
empty()) {
3045 auto *DefI = getDefiningScopeBound(LIOps);
3047 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
3059 if (
Ops.size() == 1)
return NewRec;
3062 for (
unsigned i = 0;; ++i)
3063 if (
Ops[i] == AddRec) {
3073 for (
unsigned OtherIdx = Idx+1;
3081 "AddRecExprs are not sorted in reverse dominance order?");
3088 if (OtherAddRec->getLoop() == AddRecLoop) {
3089 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
3091 if (i >= AddRecOps.
size()) {
3092 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
3096 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
3099 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3114 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
3125 static_cast<SCEVAddExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3129 S =
new (SCEVAllocator)
3131 UniqueSCEVs.InsertNode(S, IP);
3142 FoldingSetNodeID
ID;
3144 for (
const SCEV *
Op :
Ops)
3149 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3153 S =
new (SCEVAllocator)
3154 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3155 UniqueSCEVs.InsertNode(S, IP);
3157 LoopUsers[
L].push_back(S);
3166 FoldingSetNodeID
ID;
3168 for (
const SCEV *
Op :
Ops)
3172 static_cast<SCEVMulExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3176 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3178 UniqueSCEVs.InsertNode(S, IP);
3188 if (j > 1 && k / j != i) Overflow =
true;
3204 if (n == 0 || n == k)
return 1;
3205 if (k > n)
return 0;
3211 for (
uint64_t i = 1; i <= k; ++i) {
3212 r =
umul_ov(r, n-(i-1), Overflow);
3221 struct FindConstantInAddMulChain {
3222 bool FoundConstant =
false;
3224 bool follow(
const SCEV *S) {
3229 bool isDone()
const {
3230 return FoundConstant;
3234 FindConstantInAddMulChain
F;
3236 ST.visitAll(StartExpr);
3237 return F.FoundConstant;
3245 "only nuw or nsw allowed");
3246 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3247 if (
Ops.size() == 1)
return Ops[0];
3249 Type *ETy =
Ops[0]->getType();
3251 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3253 "SCEVMulExpr operand types don't match!");
3258 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3259 [](
const APInt &
C) {
return C.isOne(); },
3260 [](
const APInt &
C) {
return C.isZero(); });
3271 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3276 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3277 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3282 if (
Ops.size() == 2) {
3290 const SCEV *Op0, *Op1;
3298 if (
Ops[0]->isAllOnesValue()) {
3303 bool AnyFolded =
false;
3304 for (
const SCEV *AddOp :
Add->operands()) {
3324 if (AddRec->hasNoSignedWrap()) {
3331 AddRec->getNoWrapFlags(FlagsMask));
3354 APInt C1V = LHSC->getAPInt();
3364 const SCEV *NewMul =
nullptr;
3368 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3383 if (Idx <
Ops.size()) {
3384 bool DeletedMul =
false;
3390 Ops.erase(
Ops.begin()+Idx);
3414 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3417 Ops.erase(
Ops.begin()+i);
3422 if (!LIOps.
empty()) {
3435 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3451 if (
Ops.size() == 1)
return NewRec;
3454 for (
unsigned i = 0;; ++i)
3455 if (
Ops[i] == AddRec) {
3476 bool OpsModified =
false;
3477 for (
unsigned OtherIdx = Idx+1;
3491 bool Overflow =
false;
3498 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3502 z < ze && !Overflow; ++z) {
3505 if (LargerThan64Bits)
3506 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3508 Coeff = Coeff1*Coeff2;
3523 if (
Ops.size() == 2)
return NewAddRec;
3524 Ops[Idx] = NewAddRec;
3525 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3541 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3548 "SCEVURemExpr operand types don't match!");
3553 if (RHSC->getValue()->isOne())
3554 return getZero(LHS->getType());
3557 if (RHSC->getAPInt().isPowerOf2()) {
3558 Type *FullTy = LHS->getType();
3574 assert(!LHS->getType()->isPointerTy() &&
3575 "SCEVUDivExpr operand can't be pointer!");
3576 assert(LHS->getType() == RHS->getType() &&
3577 "SCEVUDivExpr operand types don't match!");
3584 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3592 if (RHSC->getValue()->isOne())
3597 if (!RHSC->getValue()->isZero()) {
3601 Type *Ty = LHS->getType();
3602 unsigned LZ = RHSC->getAPInt().countl_zero();
3606 if (!RHSC->getAPInt().isPowerOf2())
3614 const APInt &StepInt = Step->getAPInt();
3615 const APInt &DivInt = RHSC->getAPInt();
3616 if (!StepInt.
urem(DivInt) &&
3622 for (
const SCEV *
Op : AR->operands())
3628 const APInt *StartRem;
3641 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3645 const SCEV *NewStart =
3647 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3649 const SCEV *NewLHS =
3652 if (LHS != NewLHS) {
3662 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3671 for (
const SCEV *
Op : M->operands())
3675 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3676 const SCEV *
Op = M->getOperand(i);
3703 if (
auto *DivisorConstant =
3705 bool Overflow =
false;
3707 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3718 for (
const SCEV *
Op :
A->operands())
3722 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3729 if (Operands.
size() ==
A->getNumOperands())
3741 const APInt &
N = RHSC->getAPInt();
3742 const APInt *NMinusM, *M;
3746 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3747 *NMinusM ==
N - *M) {
3756 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3766 return getZero(LHS->getType());
3770 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3771 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3772 if (
Mul->getOperand(i) == RHS) {
3783 const SCEV *NewLHS, *NewRHS;
3791 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
3794 UniqueSCEVs.InsertNode(S, IP);
3831 if (StepChrec->getLoop() == L) {
3845 if (Operands.
size() == 1)
return Operands[0];
3850 "SCEVAddRecExpr operand types don't match!");
3851 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3853 for (
const SCEV *
Op : Operands)
3855 "SCEVAddRecExpr operand is not available at loop entry!");
3858 if (Operands.
back()->isZero()) {
3873 const Loop *NestedLoop = NestedAR->getLoop();
3874 if (L->contains(NestedLoop)
3877 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3879 Operands[0] = NestedAR->getStart();
3883 bool AllInvariant =
all_of(
3895 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3906 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3910 Operands[0] = NestedAR;
3916 return getOrCreateAddRecExpr(Operands, L, Flags);
3932 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3936 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3950 bool FirstIter =
true;
3952 for (
SCEVUse IndexExpr : IndexExprs) {
3959 Offsets.push_back(FieldOffset);
3962 CurTy = STy->getTypeAtIndex(Index);
3967 "The first index of a GEP indexes a pointer");
3968 CurTy = SrcElementTy;
3979 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3980 Offsets.push_back(LocalOffset);
3985 if (Offsets.empty())
3998 "GEP should not change type mid-flight.");
4002SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
4005 ID.AddInteger(SCEVType);
4009 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4012SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
4015 ID.AddInteger(SCEVType);
4019 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4029 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
4030 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4031 if (
Ops.size() == 1)
return Ops[0];
4034 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4036 "Operand types don't match!");
4039 "min/max should be consistently pointerish");
4065 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
4067 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
4072 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
4074 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
4080 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
4086 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
4091 if (Idx <
Ops.size()) {
4092 bool DeletedAny =
false;
4093 while (
Ops[Idx]->getSCEVType() == Kind) {
4095 Ops.erase(
Ops.begin()+Idx);
4113 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
4114 if (
Ops[i] ==
Ops[i + 1] ||
4115 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
4118 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
4121 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
4124 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
4130 if (
Ops.size() == 1)
return Ops[0];
4132 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
4137 ID.AddInteger(Kind);
4141 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4143 return ExistingSCEV;
4146 SCEV *S =
new (SCEVAllocator)
4149 UniqueSCEVs.InsertNode(S, IP);
4157class SCEVSequentialMinMaxDeduplicatingVisitor final
4158 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4159 std::optional<const SCEV *>> {
4160 using RetVal = std::optional<const SCEV *>;
4168 bool canRecurseInto(
SCEVTypes Kind)
const {
4171 return RootKind == Kind || NonSequentialRootKind == Kind;
4174 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
4176 "Only for min/max expressions.");
4179 if (!canRecurseInto(Kind))
4189 return std::nullopt;
4196 RetVal
visit(
const SCEV *S) {
4198 if (!SeenOps.
insert(S).second)
4199 return std::nullopt;
4200 return Base::visit(S);
4204 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4206 : SE(SE), RootKind(RootKind),
4207 NonSequentialRootKind(
4208 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4212 SmallVectorImpl<SCEVUse> &NewOps) {
4217 for (
const SCEV *
Op : OrigOps) {
4222 Ops.emplace_back(*NewOp);
4226 NewOps = std::move(
Ops);
4230 RetVal visitConstant(
const SCEVConstant *Constant) {
return Constant; }
4232 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4234 RetVal visitPtrToAddrExpr(
const SCEVPtrToAddrExpr *Expr) {
return Expr; }
4236 RetVal visitPtrToIntExpr(
const SCEVPtrToIntExpr *Expr) {
return Expr; }
4238 RetVal visitTruncateExpr(
const SCEVTruncateExpr *Expr) {
return Expr; }
4240 RetVal visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
return Expr; }
4242 RetVal visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
return Expr; }
4244 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4246 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4248 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4250 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4252 RetVal visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
4253 return visitAnyMinMaxExpr(Expr);
4256 RetVal visitUMaxExpr(
const SCEVUMaxExpr *Expr) {
4257 return visitAnyMinMaxExpr(Expr);
4260 RetVal visitSMinExpr(
const SCEVSMinExpr *Expr) {
4261 return visitAnyMinMaxExpr(Expr);
4264 RetVal visitUMinExpr(
const SCEVUMinExpr *Expr) {
4265 return visitAnyMinMaxExpr(Expr);
4268 RetVal visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *Expr) {
4269 return visitAnyMinMaxExpr(Expr);
4272 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4274 RetVal visitCouldNotCompute(
const SCEVCouldNotCompute *Expr) {
return Expr; }
4317struct SCEVPoisonCollector {
4318 bool LookThroughMaybePoisonBlocking;
4319 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4320 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4321 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4323 bool follow(
const SCEV *S) {
4324 if (!LookThroughMaybePoisonBlocking &&
4334 bool isDone()
const {
return false; }
4344 SCEVPoisonCollector PC1(
true);
4349 if (PC1.MaybePoison.empty())
4355 SCEVPoisonCollector PC2(
false);
4365 SCEVPoisonCollector PC(
false);
4388 while (!Worklist.
empty()) {
4390 if (!Visited.
insert(V).second)
4394 if (Visited.
size() > 16)
4410 if (PDI->isDisjoint())
4417 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4424 if (
I->hasPoisonGeneratingAnnotations())
4435 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4436 "Not a SCEVSequentialMinMaxExpr!");
4437 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4438 if (
Ops.size() == 1)
4442 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4444 "Operand types don't match!");
4447 "min/max should be consistently pointerish");
4455 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4462 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4472 bool DeletedAny =
false;
4473 while (Idx <
Ops.size()) {
4474 if (
Ops[Idx]->getSCEVType() != Kind) {
4479 Ops.erase(
Ops.begin() + Idx);
4480 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4481 SMME->operands().end());
4489 const SCEV *SaturationPoint;
4500 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4501 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4513 Ops.erase(
Ops.begin() + i);
4518 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4519 Ops.erase(
Ops.begin() + i);
4527 ID.AddInteger(Kind);
4531 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4533 return ExistingSCEV;
4537 SCEV *S =
new (SCEVAllocator)
4540 UniqueSCEVs.InsertNode(S, IP);
4588 if (
Size.isScalable())
4609 "Cannot get offset for structure containing scalable vector types");
4623 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP)) {
4625 "Stale SCEVUnknown in uniquing map!");
4631 UniqueSCEVs.InsertNode(S, IP);
4646 return Ty->isIntOrPtrTy();
4653 if (Ty->isPointerTy())
4664 if (Ty->isIntegerTy())
4668 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4680 bool PreciseA, PreciseB;
4681 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4682 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4683 if (!PreciseA || !PreciseB)
4686 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4687 DT.dominates(ScopeB, ScopeA);
4691 return CouldNotCompute.get();
4694bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4697 return SU && SU->getValue() ==
nullptr;
4700 return !ContainsNulls;
4705 if (
I != HasRecMap.end())
4710 HasRecMap.insert({S, FoundAddRec});
4718 if (
SI == ExprValueMap.
end())
4720 return SI->second.getArrayRef();
4726void ScalarEvolution::eraseValueFromMap(
Value *V) {
4728 if (
I != ValueExprMap.end()) {
4729 auto EVIt = ExprValueMap.find(
I->second);
4730 bool Removed = EVIt->second.remove(V);
4732 assert(Removed &&
"Value not in ExprValueMap?");
4733 ValueExprMap.erase(
I);
4737void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4741 auto It = ValueExprMap.find_as(V);
4742 if (It == ValueExprMap.end()) {
4744 ExprValueMap[S].insert(V);
4755 return createSCEVIter(V);
4762 if (
I != ValueExprMap.end()) {
4763 const SCEV *S =
I->second;
4764 assert(checkValidity(S) &&
4765 "existing SCEV has not been properly invalidated");
4778 Type *Ty = V->getType();
4794 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4807 return (
const SCEV *)
nullptr;
4813 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4817 Type *Ty = V->getType();
4823 assert(
P->getType()->isPointerTy());
4838 if (AddOp->getType()->isPointerTy()) {
4839 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4857 return getZero(LHS->getType());
4862 if (RHS->getType()->isPointerTy()) {
4863 if (!LHS->getType()->isPointerTy() ||
4873 const bool RHSIsNotMinSigned =
4904 Type *SrcTy = V->getType();
4905 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4906 "Cannot truncate or zero extend with non-integer arguments!");
4916 Type *SrcTy = V->getType();
4917 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4918 "Cannot truncate or zero extend with non-integer arguments!");
4928 Type *SrcTy = V->getType();
4929 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4930 "Cannot noop or zero extend with non-integer arguments!");
4932 "getNoopOrZeroExtend cannot truncate!");
4940 Type *SrcTy = V->getType();
4941 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4942 "Cannot noop or sign extend with non-integer arguments!");
4944 "getNoopOrSignExtend cannot truncate!");
4952 Type *SrcTy = V->getType();
4953 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4954 "Cannot noop or any extend with non-integer arguments!");
4956 "getNoopOrAnyExtend cannot truncate!");
4964 Type *SrcTy = V->getType();
4965 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4966 "Cannot truncate or noop with non-integer arguments!");
4968 "getTruncateOrNoop cannot extend!");
4976 const SCEV *PromotedLHS = LHS;
4977 const SCEV *PromotedRHS = RHS;
4997 assert(!
Ops.empty() &&
"At least one operand must be!");
4999 if (
Ops.size() == 1)
5003 Type *MaxType =
nullptr;
5009 assert(MaxType &&
"Failed to find maximum type!");
5022 if (!V->getType()->isPointerTy())
5027 V = AddRec->getStart();
5029 const SCEV *PtrOp =
nullptr;
5030 for (
const SCEV *AddOp :
Add->operands()) {
5031 if (AddOp->getType()->isPointerTy()) {
5032 assert(!PtrOp &&
"Cannot have multiple pointer ops");
5036 assert(PtrOp &&
"Must have pointer op");
5048 for (
User *U :
I->users()) {
5050 if (Visited.
insert(UserInsn).second)
5064 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
5065 bool IgnoreOtherLoops =
true) {
5068 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
5070 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
5075 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5077 SeenLoopVariantSCEVUnknown =
true;
5081 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5085 SeenOtherLoops =
true;
5089 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
5091 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
5094 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
5095 : SCEVRewriteVisitor(SE),
L(
L) {}
5098 bool SeenLoopVariantSCEVUnknown =
false;
5099 bool SeenOtherLoops =
false;
5108 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
5109 SCEVPostIncRewriter
Rewriter(L, SE);
5111 return Rewriter.hasSeenLoopVariantSCEVUnknown()
5116 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5118 SeenLoopVariantSCEVUnknown =
true;
5122 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5126 SeenOtherLoops =
true;
5130 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
5132 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
5135 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
5136 : SCEVRewriteVisitor(SE),
L(
L) {}
5139 bool SeenLoopVariantSCEVUnknown =
false;
5140 bool SeenOtherLoops =
false;
5146class SCEVBackedgeConditionFolder
5149 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5150 ScalarEvolution &SE) {
5151 bool IsPosBECond =
false;
5152 Value *BECond =
nullptr;
5153 if (BasicBlock *Latch =
L->getLoopLatch()) {
5155 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
5156 "Both outgoing branches should not target same header!");
5157 BECond = BI->getCondition();
5158 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
5163 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
5167 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5168 const SCEV *
Result = Expr;
5173 switch (
I->getOpcode()) {
5174 case Instruction::Select: {
5176 std::optional<const SCEV *> Res =
5177 compareWithBackedgeCondition(
SI->getCondition());
5185 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5196 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5197 bool IsPosBECond, ScalarEvolution &SE)
5198 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5199 IsPositiveBECond(IsPosBECond) {}
5201 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5205 Value *BackedgeCond =
nullptr;
5207 bool IsPositiveBECond;
5210std::optional<const SCEV *>
5211SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5216 if (BackedgeCond == IC)
5219 return std::nullopt;
5224 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5225 ScalarEvolution &SE) {
5231 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5238 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5248 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5249 : SCEVRewriteVisitor(SE),
L(
L) {}
5257void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5273 const APInt &BECountAP = BECountMax->getAPInt();
5274 unsigned NoOverflowBitWidth =
5283ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5293 if (!SignedWrapViaInductionTried.insert(AR).second)
5318 AC.assumptions().empty())
5326 const SCEV *OverflowLimit =
5328 if (OverflowLimit &&
5336ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5346 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5372 AC.assumptions().empty())
5408 : Opcode(
Op->getOpcode()),
LHS(
Op->getOperand(0)),
RHS(
Op->getOperand(1)),
5411 IsNSW = OBO->hasNoSignedWrap();
5412 IsNUW = OBO->hasNoUnsignedWrap();
5418 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5430 return std::nullopt;
5436 switch (
Op->getOpcode()) {
5437 case Instruction::Add:
5438 case Instruction::Sub:
5439 case Instruction::Mul:
5440 case Instruction::UDiv:
5441 case Instruction::URem:
5442 case Instruction::And:
5443 case Instruction::AShr:
5444 case Instruction::Shl:
5447 case Instruction::Or: {
5450 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5460 case Instruction::Xor:
5464 if (RHSC->getValue().isSignMask())
5465 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5467 if (V->getType()->isIntegerTy(1))
5468 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5471 case Instruction::LShr:
5480 if (SA->getValue().ult(
BitWidth)) {
5482 ConstantInt::get(SA->getContext(),
5484 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5489 case Instruction::ExtractValue: {
5491 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5499 bool Signed = WO->isSigned();
5502 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5507 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5518 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5519 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5521 return std::nullopt;
5547 if (
Op == SymbolicPHI)
5552 if (SourceBits != NewBits)
5570 if (!L || L->getHeader() != PN->
getParent())
5628std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5629ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5637 assert(L &&
"Expecting an integer loop header phi");
5642 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5643 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5644 Value *
V = PN->getIncomingValue(i);
5645 if (
L->contains(PN->getIncomingBlock(i))) {
5648 }
else if (BEValueV != V) {
5652 }
else if (!StartValueV) {
5654 }
else if (StartValueV != V) {
5655 StartValueV =
nullptr;
5659 if (!BEValueV || !StartValueV)
5660 return std::nullopt;
5662 const SCEV *BEValue =
getSCEV(BEValueV);
5669 return std::nullopt;
5673 unsigned FoundIndex =
Add->getNumOperands();
5674 Type *TruncTy =
nullptr;
5676 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5679 if (FoundIndex == e) {
5684 if (FoundIndex ==
Add->getNumOperands())
5685 return std::nullopt;
5689 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5690 if (i != FoundIndex)
5691 Ops.push_back(
Add->getOperand(i));
5697 return std::nullopt;
5750 const SCEV *StartVal =
getSCEV(StartValueV);
5751 const SCEV *PHISCEV =
5778 auto getExtendedExpr = [&](
const SCEV *Expr,
5779 bool CreateSignExtend) ->
const SCEV * {
5782 const SCEV *ExtendedExpr =
5785 return ExtendedExpr;
5793 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5794 const SCEV *ExtendedExpr) ->
bool {
5795 return Expr != ExtendedExpr &&
5799 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5800 if (PredIsKnownFalse(StartVal, StartExtended)) {
5802 return std::nullopt;
5807 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5808 if (PredIsKnownFalse(Accum, AccumExtended)) {
5810 return std::nullopt;
5813 auto AppendPredicate = [&](
const SCEV *Expr,
5814 const SCEV *ExtendedExpr) ->
void {
5815 if (Expr != ExtendedExpr &&
5823 AppendPredicate(StartVal, StartExtended);
5824 AppendPredicate(Accum, AccumExtended);
5832 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5833 std::make_pair(NewAR, Predicates);
5835 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5839std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5844 return std::nullopt;
5847 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5848 if (
I != PredicatedSCEVRewrites.end()) {
5849 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5852 if (Rewrite.first == SymbolicPHI)
5853 return std::nullopt;
5857 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5861 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5862 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5867 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5868 return std::nullopt;
5888 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5889 if (Expr1 != Expr2 &&
5890 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5891 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5908const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5910 Value *StartValueV) {
5913 assert(BEValueV && StartValueV);
5919 if (BO->Opcode != Instruction::Add)
5922 const SCEV *Accum =
nullptr;
5923 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5925 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5939 insertValueToMap(PN, PHISCEV);
5942 inferNoWrapViaConstantRanges(AR);
5949 "Accum is defined outside L, but is not invariant?");
5950 if (isAddRecNeverPoison(BEInst, L))
5957const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5958 const Loop *
L = LI.getLoopFor(PN->
getParent());
5965 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5971 }
else if (BEValueV != V) {
5975 }
else if (!StartValueV) {
5977 }
else if (StartValueV != V) {
5978 StartValueV =
nullptr;
5982 if (!BEValueV || !StartValueV)
5985 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5986 "PHI node already processed?");
5990 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5995 insertValueToMap(PN, SymbolicName);
5999 const SCEV *BEValue =
getSCEV(BEValueV);
6009 unsigned FoundIndex =
Add->getNumOperands();
6010 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
6011 if (
Add->getOperand(i) == SymbolicName)
6012 if (FoundIndex == e) {
6017 if (FoundIndex !=
Add->getNumOperands()) {
6020 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
6021 if (i != FoundIndex)
6022 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
6034 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
6041 if (
GEP->getOperand(0) == PN) {
6042 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
6060 const SCEV *StartVal =
getSCEV(StartValueV);
6061 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
6066 forgetMemoizedResults({SymbolicName});
6067 insertValueToMap(PN, PHISCEV);
6070 inferNoWrapViaConstantRanges(AR);
6094 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
6095 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
6097 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
6098 const SCEV *StartVal =
getSCEV(StartValueV);
6099 if (Start == StartVal) {
6103 forgetMemoizedResults({SymbolicName});
6104 insertValueToMap(PN, Shifted);
6114 eraseValueFromMap(PN);
6129 Use &LeftUse =
Merge->getOperandUse(0);
6130 Use &RightUse =
Merge->getOperandUse(1);
6166 assert(IDom &&
"At least the entry block should dominate PN");
6174const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
6179 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6196 CommonInst = IncomingInst;
6212ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6218 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6219 bool SCEVExprsIdentical =
6221 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6222 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6225const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6226 if (
const SCEV *S = createAddRecFromPHI(PN))
6236 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6239 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6248 struct FindClosure {
6249 const SCEV *OperandToFind;
6255 bool canRecurseInto(
SCEVTypes Kind)
const {
6258 return RootKind == Kind || NonSequentialRootKind == Kind ||
6263 : OperandToFind(OperandToFind), RootKind(RootKind),
6264 NonSequentialRootKind(
6268 bool follow(
const SCEV *S) {
6269 Found = S == OperandToFind;
6271 return !isDone() && canRecurseInto(S->
getSCEVType());
6274 bool isDone()
const {
return Found; }
6277 FindClosure FC(OperandToFind, RootKind);
6282std::optional<const SCEV *>
6283ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6293 switch (ICI->getPredicate()) {
6307 bool Signed = ICI->isSigned();
6308 const SCEV *LA =
getSCEV(TrueVal);
6316 if (LA == LS &&
RA == RS)
6318 if (LA == RS &&
RA == LS)
6321 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6322 if (
Op->getType()->isPointerTy()) {
6333 LS = CoerceOperand(LS);
6334 RS = CoerceOperand(RS);
6358 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6359 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6373 X = ZExt->getOperand();
6375 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6386 return std::nullopt;
6389static std::optional<const SCEV *>
6391 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6395 "Unexpected operands of a select.");
6407 return std::nullopt;
6422static std::optional<const SCEV *>
6426 return std::nullopt;
6429 const auto *SETrue = SE->
getSCEV(TrueVal);
6430 const auto *SEFalse = SE->
getSCEV(FalseVal);
6434const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6436 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6438 V->getType() ==
TrueVal->getType() &&
6439 "Types of select hands and of the result must match.");
6442 if (!
V->getType()->isIntegerTy(1))
6445 if (std::optional<const SCEV *> S =
6458 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6462 if (std::optional<const SCEV *> S =
6463 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6469 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6475 assert(
GEP->getSourceElementType()->isSized() &&
6476 "GEP source element type must be sized");
6479 for (
Value *Index :
GEP->indices())
6484APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6487 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6490 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6492 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6495 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6514 return GetShiftedByZeros(TZ);
6524 return GetShiftedByZeros(TZ);
6528 if (
M->hasNoUnsignedWrap()) {
6531 for (
const SCEV *Operand :
M->operands().drop_front())
6539 for (
const SCEV *Operand :
M->operands())
6541 return GetShiftedByZeros(TZ);
6546 if (
N->hasNoUnsignedWrap())
6547 return GetGCDMultiple(
N);
6550 for (
const SCEV *Operand :
N->operands().drop_front())
6552 return GetShiftedByZeros(TZ);
6569 CtxI = &*F.getEntryBlock().begin();
6576 .allowEphemerals(
true))
6577 .countMinTrailingZeros();
6578 return GetShiftedByZeros(
Known);
6591 return getConstantMultipleImpl(S, CtxI);
6593 auto I = ConstantMultipleCache.find(S);
6594 if (
I != ConstantMultipleCache.end())
6597 APInt Result = getConstantMultipleImpl(S, CtxI);
6598 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6599 assert(InsertPair.second &&
"Should insert a new key");
6600 return InsertPair.first->second;
6617 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6620 if (std::optional<ConstantRange>
Range = CB->getRange())
6624 if (std::optional<ConstantRange>
Range =
A->getRange())
6627 return std::nullopt;
6634 UnsignedRanges.erase(AddRec);
6635 SignedRanges.erase(AddRec);
6636 ConstantMultipleCache.erase(AddRec);
6641getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6667 Value *Start, *Step;
6674 assert(L && L->getHeader() ==
P->getParent());
6687 case Instruction::AShr:
6688 case Instruction::LShr:
6689 case Instruction::Shl:
6704 KnownStep.getBitWidth() ==
BitWidth);
6707 auto MaxShiftAmt = KnownStep.getMaxValue();
6709 bool Overflow =
false;
6710 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6717 case Instruction::AShr: {
6725 if (KnownStart.isNonNegative())
6728 KnownStart.getMaxValue() + 1);
6729 if (KnownStart.isNegative())
6732 KnownEnd.getMaxValue() + 1);
6735 case Instruction::LShr: {
6744 KnownStart.getMaxValue() + 1);
6746 case Instruction::Shl: {
6750 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6751 return ConstantRange(KnownStart.getMinValue(),
6752 KnownEnd.getMaxValue() + 1);
6777 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6784ScalarEvolution::getRangeRefIter(
const SCEV *S,
6785 ScalarEvolution::RangeSignHint SignHint) {
6786 DenseMap<const SCEV *, ConstantRange> &Cache =
6787 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6790 SmallPtrSet<const SCEV *, 8> Seen;
6794 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6795 if (!Seen.
insert(Expr).second)
6829 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6830 const SCEV *
P = WorkList[
I];
6834 for (
const SCEV *
Op :
P->operands())
6847 if (!WorkList.
empty()) {
6852 getRangeRef(
P, SignHint);
6856 return getRangeRef(S, SignHint, 0);
6863 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6864 DenseMap<const SCEV *, ConstantRange> &Cache =
6865 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6872 auto I = Cache.
find(S);
6873 if (
I != Cache.
end())
6877 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6882 return getRangeRefIter(S, SignHint);
6885 ConstantRange ConservativeResult(
BitWidth,
true);
6886 using OBO = OverflowingBinaryOperator;
6890 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6894 ConservativeResult =
6901 ConservativeResult = ConstantRange(
6917 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6924 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6931 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6937 return setRange(Cast, SignHint,
X);
6942 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6943 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6945 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6946 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6947 ConservativeResult =
6948 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6950 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6951 unsigned WrapType = OBO::AnyWrap;
6952 if (
Add->hasNoSignedWrap())
6953 WrapType |= OBO::NoSignedWrap;
6954 if (
Add->hasNoUnsignedWrap())
6955 WrapType |= OBO::NoUnsignedWrap;
6957 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6959 return setRange(
Add, SignHint,
6960 ConservativeResult.intersectWith(
X, RangeType));
6964 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6966 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6967 return setRange(
Mul, SignHint,
6968 ConservativeResult.intersectWith(
X, RangeType));
6972 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6973 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6974 return setRange(UDiv, SignHint,
6975 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6983 if (!UnsignedMinValue.
isZero())
6984 ConservativeResult = ConservativeResult.intersectWith(
6985 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6994 bool AllNonNeg =
true;
6995 bool AllNonPos =
true;
6996 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
7003 ConservativeResult = ConservativeResult.intersectWith(
7008 ConservativeResult = ConservativeResult.intersectWith(
7017 const SCEV *MaxBEScev =
7031 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
7033 ConservativeResult =
7034 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
7037 auto RangeFromFactoring = getRangeViaFactoring(
7039 ConservativeResult =
7040 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
7046 const SCEV *SymbolicMaxBECount =
7051 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
7052 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
7053 ConservativeResult =
7054 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
7059 return setRange(AddRec, SignHint, std::move(ConservativeResult));
7069 ID = Intrinsic::umax;
7072 ID = Intrinsic::smax;
7076 ID = Intrinsic::umin;
7079 ID = Intrinsic::smin;
7086 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
7087 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
7089 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
7090 return setRange(S, SignHint,
7091 ConservativeResult.intersectWith(
X, RangeType));
7100 ConservativeResult =
7101 ConservativeResult.intersectWith(*MDRange, RangeType);
7106 auto CR = getRangeForUnknownRecurrence(U);
7107 ConservativeResult = ConservativeResult.intersectWith(CR);
7118 if (
U->getType()->isPointerTy()) {
7121 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
7122 int ptrIdxDiff = ptrSize -
BitWidth;
7123 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
7129 if (!
Known.Zero.getHiBits(NS).isZero())
7130 Known.Zero.setHighBits(NS);
7131 if (!
Known.One.getHiBits(NS).isZero())
7132 Known.One.setHighBits(NS);
7135 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
7136 ConservativeResult = ConservativeResult.intersectWith(
7137 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
7140 ConservativeResult = ConservativeResult.intersectWith(
7145 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
7149 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
7150 DL, CanBeNull,
nullptr);
7160 uint64_t
Align =
U->getValue()->getPointerAlignment(DL).value();
7161 uint64_t Rem = MaxVal.
urem(Align);
7166 ConservativeResult = ConservativeResult.intersectWith(
7176 return getRangeRef(AR, SignHint,
Depth + 1);
7180 ConstantRange RangeFromOps(
BitWidth,
false);
7182 for (
const auto &
Op :
Phi->operands()) {
7184 RangeFromOps = RangeFromOps.unionWith(OpRange);
7186 if (RangeFromOps.isFullSet())
7189 ConservativeResult =
7190 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7196 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7198 ConservativeResult = ConservativeResult.difference(Disallowed);
7201 return setRange(U, SignHint, std::move(ConservativeResult));
7207 return setRange(S, SignHint, std::move(ConservativeResult));
7215static std::pair<ConstantRange, bool>
7223 if (Step == 0 || MaxBECount == 0)
7224 return {StartRange,
true};
7230 return {ConstantRange::getFull(
BitWidth),
false};
7246 return {ConstantRange::getFull(
BitWidth),
false};
7259 APInt MovedBoundary;
7264 MovedBoundary = StartLower - std::move(
Offset);
7267 MovedBoundary = StartUpper + std::move(
Offset);
7271 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7278 if (StartRange.
contains(MovedBoundary))
7279 return {ConstantRange::getFull(
BitWidth),
false};
7282 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7284 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7292std::pair<ConstantRange, SCEV::NoWrapFlags>
7293ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7294 const APInt &MaxBECount) {
7298 "mismatched bit widths");
7307 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7309 StartSRange, MaxBECount,
7311 ConstantRange SR = SR1.unionWith(SR2);
7328ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7330 ScalarEvolution::RangeSignHint SignHint) {
7331 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7333 "This only works for non-self-wrapping AddRecs!");
7334 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7338 return ConstantRange::getFull(
BitWidth);
7346 return ConstantRange::getFull(
BitWidth);
7350 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7352 MaxItersWithoutWrap))
7353 return ConstantRange::getFull(
BitWidth);
7374 ConstantRange StartRange = getRangeRef(Start, SignHint);
7375 ConstantRange EndRange = getRangeRef(End, SignHint);
7376 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7380 return RangeBetween;
7385 return ConstantRange::getFull(
BitWidth);
7388 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7389 return RangeBetween;
7391 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7392 return RangeBetween;
7393 return ConstantRange::getFull(
BitWidth);
7398 const APInt &MaxBECount) {
7405 "mismatched bit widths");
7407 struct SelectPattern {
7408 Value *Condition =
nullptr;
7412 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7414 std::optional<unsigned> CastOp;
7428 CastOp = SCast->getSCEVType();
7429 S = SCast->getOperand();
7432 using namespace llvm::PatternMatch;
7439 Condition =
nullptr;
7471 bool isRecognized() {
return Condition !=
nullptr; }
7474 SelectPattern StartPattern(*
this,
BitWidth, Start);
7475 if (!StartPattern.isRecognized())
7476 return ConstantRange::getFull(
BitWidth);
7478 SelectPattern StepPattern(*
this,
BitWidth, Step);
7479 if (!StepPattern.isRecognized())
7480 return ConstantRange::getFull(
BitWidth);
7482 if (StartPattern.Condition != StepPattern.Condition) {
7486 return ConstantRange::getFull(
BitWidth);
7497 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7498 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7499 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7500 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7502 ConstantRange TrueRange =
7503 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7504 ConstantRange FalseRange =
7505 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7517 PDI && PDI->isDisjoint()) {
7532ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7545 SmallPtrSet<const SCEV *, 16> Visited;
7547 auto pushOp = [&](
const SCEV *S) {
7548 if (!Visited.
insert(S).second)
7551 if (Visited.
size() > 30) {
7562 while (!Worklist.
empty()) {
7564 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7565 if (!Bound || DT.dominates(Bound, DefI))
7572 return Bound ? Bound : &*F.getEntryBlock().begin();
7578 return getDefiningScopeBound(
Ops, Discard);
7581bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7583 if (
A->getParent() ==
B->getParent() &&
7588 auto *BLoop = LI.getLoopFor(
B->getParent());
7589 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7590 BLoop->getLoopPreheader() ==
A->getParent() &&
7592 A->getParent()->end()) &&
7600 SCEVPoisonCollector PC(
true);
7602 return PC.MaybePoison.empty();
7605bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7615bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7632 for (
const Use &
Op :
I->operands()) {
7638 auto *DefI = getDefiningScopeBound(SCEVOps);
7639 return isGuaranteedToTransferExecutionTo(DefI,
I);
7642bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7644 if (isSCEVExprNeverPoison(
I))
7655 auto *ExitingBB =
L->getExitingBlock();
7659 SmallPtrSet<const Value *, 16> KnownPoison;
7668 while (!Worklist.
empty()) {
7671 for (
const Use &U :
Poison->uses()) {
7674 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7678 if (KnownPoison.
insert(PoisonUser).second)
7686ScalarEvolution::LoopProperties
7687ScalarEvolution::getLoopProperties(
const Loop *L) {
7688 using LoopProperties = ScalarEvolution::LoopProperties;
7690 auto Itr = LoopPropertiesCache.find(L);
7691 if (Itr == LoopPropertiesCache.end()) {
7694 return !
SI->isSimple();
7704 return I->mayWriteToMemory();
7707 LoopProperties LP = {
true,
7710 for (
auto *BB :
L->getBlocks())
7711 for (
auto &
I : *BB) {
7713 LP.HasNoAbnormalExits =
false;
7714 if (HasSideEffects(&
I))
7715 LP.HasNoSideEffects =
false;
7716 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7720 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7721 assert(InsertPair.second &&
"We just checked!");
7722 Itr = InsertPair.first;
7735const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7741 Stack.emplace_back(V,
false);
7742 while (!Stack.empty()) {
7743 auto E = Stack.back();
7744 Value *CurV = E.getPointer();
7752 const SCEV *CreatedSCEV =
nullptr;
7755 CreatedSCEV = createSCEV(CurV);
7760 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7764 insertValueToMap(CurV, CreatedSCEV);
7767 Stack.back().setInt(
true);
7770 Stack.emplace_back(
Op,
false);
7787 if (!DT.isReachableFromEntry(
I->getParent()))
7800 switch (BO->Opcode) {
7801 case Instruction::Add:
7802 case Instruction::Mul: {
7809 Ops.push_back(BO->
Op);
7813 Ops.push_back(BO->RHS);
7817 (BO->Opcode == Instruction::Add &&
7818 (NewBO->Opcode != Instruction::Add &&
7819 NewBO->Opcode != Instruction::Sub)) ||
7820 (BO->Opcode == Instruction::Mul &&
7821 NewBO->Opcode != Instruction::Mul)) {
7822 Ops.push_back(BO->LHS);
7827 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7830 Ops.push_back(BO->LHS);
7838 case Instruction::Sub:
7839 case Instruction::UDiv:
7840 case Instruction::URem:
7842 case Instruction::AShr:
7843 case Instruction::Shl:
7844 case Instruction::Xor:
7848 case Instruction::And:
7849 case Instruction::Or:
7853 case Instruction::LShr:
7860 Ops.push_back(BO->LHS);
7861 Ops.push_back(BO->RHS);
7865 switch (
U->getOpcode()) {
7866 case Instruction::Trunc:
7867 case Instruction::ZExt:
7868 case Instruction::SExt:
7869 case Instruction::PtrToAddr:
7870 case Instruction::PtrToInt:
7871 Ops.push_back(
U->getOperand(0));
7874 case Instruction::BitCast:
7876 Ops.push_back(
U->getOperand(0));
7881 case Instruction::SDiv:
7882 case Instruction::SRem:
7883 Ops.push_back(
U->getOperand(0));
7884 Ops.push_back(
U->getOperand(1));
7887 case Instruction::GetElementPtr:
7889 "GEP source element type must be sized");
7893 case Instruction::IntToPtr:
7896 case Instruction::PHI:
7927 Ops.push_back(CondICmp->getOperand(0));
7928 Ops.push_back(CondICmp->getOperand(1));
7948 case Instruction::Select: {
7950 auto CanSimplifyToUnknown = [
this,
U]() {
7968 if (CanSimplifyToUnknown())
7975 case Instruction::Call:
7976 case Instruction::Invoke:
7983 switch (
II->getIntrinsicID()) {
7984 case Intrinsic::abs:
7985 Ops.push_back(
II->getArgOperand(0));
7987 case Intrinsic::umax:
7988 case Intrinsic::umin:
7989 case Intrinsic::smax:
7990 case Intrinsic::smin:
7991 case Intrinsic::usub_sat:
7992 case Intrinsic::uadd_sat:
7993 Ops.push_back(
II->getArgOperand(0));
7994 Ops.push_back(
II->getArgOperand(1));
7996 case Intrinsic::start_loop_iterations:
7997 case Intrinsic::annotation:
7998 case Intrinsic::ptr_annotation:
7999 Ops.push_back(
II->getArgOperand(0));
8011const SCEV *ScalarEvolution::createSCEV(
Value *V) {
8020 if (!DT.isReachableFromEntry(
I->getParent()))
8035 switch (BO->Opcode) {
8036 case Instruction::Add: {
8062 if (BO->Opcode == Instruction::Sub)
8070 if (BO->Opcode == Instruction::Sub)
8077 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
8078 NewBO->Opcode != Instruction::Sub)) {
8088 case Instruction::Mul: {
8109 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
8118 case Instruction::UDiv:
8122 case Instruction::URem:
8126 case Instruction::Sub: {
8129 Flags = getNoWrapFlagsFromUB(BO->
Op);
8134 case Instruction::And:
8140 if (CI->isMinusOne())
8142 const APInt &
A = CI->getValue();
8148 unsigned LZ =
A.countl_zero();
8149 unsigned TZ =
A.countr_zero();
8154 APInt EffectiveMask =
8156 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
8159 const SCEV *ShiftedLHS =
nullptr;
8163 unsigned MulZeros = OpC->getAPInt().countr_zero();
8164 unsigned GCD = std::min(MulZeros, TZ);
8169 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8191 case Instruction::Or:
8200 case Instruction::Xor:
8203 if (CI->isMinusOne())
8212 if (LBO->getOpcode() == Instruction::And &&
8213 LCI->getValue() == CI->getValue())
8214 if (
const SCEVZeroExtendExpr *Z =
8217 const SCEV *Z0 =
Z->getOperand();
8224 if (CI->getValue().isMask(Z0TySize))
8230 APInt Trunc = CI->getValue().trunc(Z0TySize);
8239 case Instruction::Shl:
8257 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8266 ConstantInt *
X = ConstantInt::get(
8272 case Instruction::AShr:
8294 const SCEV *AddTruncateExpr =
nullptr;
8295 ConstantInt *ShlAmtCI =
nullptr;
8296 const SCEV *AddConstant =
nullptr;
8298 if (L &&
L->getOpcode() == Instruction::Add) {
8306 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8313 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8321 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8326 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8331 if (AddTruncateExpr && ShlAmtCI) {
8343 const APInt &ShlAmt = ShlAmtCI->
getValue();
8347 const SCEV *CompositeExpr =
8349 if (
L->getOpcode() != Instruction::Shl)
8350 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8359 switch (
U->getOpcode()) {
8360 case Instruction::Trunc:
8363 case Instruction::ZExt:
8366 case Instruction::SExt:
8376 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8377 Type *Ty =
U->getType();
8385 case Instruction::BitCast:
8391 case Instruction::PtrToAddr: {
8398 case Instruction::PtrToInt: {
8401 Type *DstIntTy =
U->getType();
8409 case Instruction::IntToPtr:
8413 case Instruction::SDiv:
8420 case Instruction::SRem:
8427 case Instruction::GetElementPtr:
8430 case Instruction::PHI:
8433 case Instruction::Select:
8434 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8437 case Instruction::Call:
8438 case Instruction::Invoke:
8443 switch (
II->getIntrinsicID()) {
8444 case Intrinsic::abs:
8448 case Intrinsic::umax:
8452 case Intrinsic::umin:
8456 case Intrinsic::smax:
8460 case Intrinsic::smin:
8464 case Intrinsic::usub_sat: {
8465 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8466 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8470 case Intrinsic::uadd_sat: {
8471 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8472 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8476 case Intrinsic::start_loop_iterations:
8477 case Intrinsic::annotation:
8478 case Intrinsic::ptr_annotation:
8482 case Intrinsic::vscale:
8502 auto *ExitCountType = ExitCount->
getType();
8503 assert(ExitCountType->isIntegerTy());
8505 1 + ExitCountType->getScalarSizeInBits());
8518 auto CanAddOneWithoutOverflow = [&]() {
8520 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8531 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8561 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8562 assert(L->isLoopExiting(ExitingBlock) &&
8563 "Exiting block must actually branch out of the loop!");
8572 const auto *MaxExitCount =
8580 L->getExitingBlocks(ExitingBlocks);
8582 std::optional<unsigned> Res;
8583 for (
auto *ExitingBB : ExitingBlocks) {
8587 Res = std::gcd(*Res, Multiple);
8589 return Res.value_or(1);
8593 const SCEV *ExitCount) {
8623 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8624 assert(L->isLoopExiting(ExitingBlock) &&
8625 "Exiting block must actually branch out of the loop!");
8635 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8637 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8639 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8649 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8652 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8655 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8663 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8670 return getBackedgeTakenInfo(L).getExact(L,
this);
8672 return getBackedgeTakenInfo(L).getConstantMax(
this);
8674 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8681 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8686 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8690 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8693ScalarEvolution::BackedgeTakenInfo &
8694ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8695 auto &BTI = getBackedgeTakenInfo(L);
8696 if (BTI.hasFullInfo())
8699 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8702 return Pair.first->second;
8704 BackedgeTakenInfo Result =
8705 computeBackedgeTakenCount(L,
true);
8707 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8710ScalarEvolution::BackedgeTakenInfo &
8711ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8717 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8718 BackedgeTakenCounts.try_emplace(L);
8720 return Pair.first->second;
8725 BackedgeTakenInfo Result = computeBackedgeTakenCount(L);
8732 if (Result.hasAnyInfo()) {
8735 auto LoopUsersIt = LoopUsers.find(L);
8736 if (LoopUsersIt != LoopUsers.end())
8738 forgetMemoizedResults(ToForget);
8741 for (
PHINode &PN : L->getHeader()->phis())
8742 ConstantEvolutionLoopExitValue.erase(&PN);
8750 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8759 BackedgeTakenCounts.clear();
8760 PredicatedBackedgeTakenCounts.clear();
8761 BECountUsers.clear();
8762 LoopPropertiesCache.clear();
8763 ConstantEvolutionLoopExitValue.clear();
8764 ValueExprMap.clear();
8765 ValuesAtScopes.clear();
8766 ValuesAtScopesUsers.clear();
8767 LoopDispositions.clear();
8768 BlockDispositions.clear();
8769 UnsignedRanges.clear();
8770 SignedRanges.clear();
8771 ExprValueMap.clear();
8773 ConstantMultipleCache.clear();
8774 PredicatedSCEVRewrites.clear();
8776 FoldCacheUser.clear();
8778void ScalarEvolution::visitAndClearUsers(
8782 while (!Worklist.
empty()) {
8789 if (It != ValueExprMap.
end()) {
8791 eraseValueFromMap(It->first);
8793 ConstantEvolutionLoopExitValue.erase(PN);
8805 while (!LoopWorklist.
empty()) {
8809 forgetBackedgeTakenCounts(CurrL,
false);
8810 forgetBackedgeTakenCounts(CurrL,
true);
8813 PredicatedSCEVRewrites.remove_if(
8814 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8816 auto LoopUsersItr = LoopUsers.find(CurrL);
8817 if (LoopUsersItr != LoopUsers.end())
8821 for (
PHINode &PN : CurrL->getHeader()->phis()) {
8822 ConstantEvolutionLoopExitValue.erase(&PN);
8823 auto VIt = ValueExprMap.find_as(
static_cast<Value *
>(&PN));
8824 if (VIt != ValueExprMap.end())
8828 LoopPropertiesCache.erase(CurrL);
8831 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8833 forgetMemoizedResults(ToForget);
8850 visitAndClearUsers(Worklist, Visited, ToForget);
8852 forgetMemoizedResults(ToForget);
8864 struct InvalidationRootCollector {
8868 InvalidationRootCollector(
Loop *L) : L(L) {}
8870 bool follow(
const SCEV *S) {
8876 if (L->contains(AddRec->
getLoop()))
8881 bool isDone()
const {
return false; }
8884 InvalidationRootCollector
C(L);
8886 forgetMemoizedResults(
C.Roots);
8899 BlockDispositions.clear();
8900 LoopDispositions.clear();
8917 while (!Worklist.
empty()) {
8919 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8920 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8921 if (!LoopDispoRemoved && !BlockDispoRemoved)
8923 auto Users = SCEVUsers.find(Curr);
8924 if (
Users != SCEVUsers.end())
8937const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8941 if (!isComplete() || ExitNotTaken.
empty())
8952 for (
const auto &ENT : ExitNotTaken) {
8953 const SCEV *BECount = ENT.ExactNotTaken;
8956 "We should only have known counts for exiting blocks that dominate "
8959 Ops.push_back(BECount);
8964 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8965 "Predicate should be always true!");
8974const ScalarEvolution::ExitNotTakenInfo *
8975ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8976 const BasicBlock *ExitingBlock,
8977 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8978 for (
const auto &ENT : ExitNotTaken)
8979 if (ENT.ExitingBlock == ExitingBlock) {
8980 if (ENT.hasAlwaysTruePredicate())
8982 else if (Predicates) {
8992const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8994 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8995 if (!getConstantMax())
8998 for (
const auto &ENT : ExitNotTaken)
8999 if (!ENT.hasAlwaysTruePredicate()) {
9007 "No point in having a non-constant max backedge taken count!");
9008 return getConstantMax();
9011const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
9013 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
9021 for (
const auto &ENT : ExitNotTaken) {
9022 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
9025 "We should only have known counts for exiting blocks that "
9031 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
9032 "Predicate should be always true!");
9035 if (ExitCounts.
empty())
9044bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
9046 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
9047 return !ENT.hasAlwaysTruePredicate();
9049 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
9065 this->ExactNotTaken = E = ConstantMaxNotTaken;
9066 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
9071 "Exact is not allowed to be less precise than Constant Max");
9074 "Exact is not allowed to be less precise than Symbolic Max");
9077 "Symbolic Max is not allowed to be less precise than Constant Max");
9080 "No point in having a non-constant max backedge taken count!");
9082 for (
const auto PredList : PredLists)
9083 for (
const auto *
P : PredList) {
9091 "Backedge count should be int");
9094 "Max backedge count should be int");
9107ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
9109 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
9110 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
9111 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9113 ExitNotTaken.reserve(ExitCounts.
size());
9114 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
9115 std::back_inserter(ExitNotTaken),
9116 [&](
const EdgeExitInfo &EEI) {
9117 BasicBlock *ExitBB = EEI.first;
9118 const ExitLimit &EL = EEI.second;
9119 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
9120 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
9125 "No point in having a non-constant max backedge taken count!");
9129ScalarEvolution::BackedgeTakenInfo
9130ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
9131 bool AllowPredicates) {
9133 L->getExitingBlocks(ExitingBlocks);
9135 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9138 bool CouldComputeBECount =
true;
9140 const SCEV *MustExitMaxBECount =
nullptr;
9141 const SCEV *MayExitMaxBECount =
nullptr;
9142 bool MustExitMaxOrZero =
false;
9143 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9154 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9155 if (ExitIfTrue == CI->
isZero())
9159 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9161 assert((AllowPredicates || EL.Predicates.empty()) &&
9162 "Predicated exit limit when predicates are not allowed!");
9167 ++NumExitCountsComputed;
9171 CouldComputeBECount =
false;
9178 "Exact is known but symbolic isn't?");
9179 ++NumExitCountsNotComputed;
9194 DT.dominates(ExitBB, Latch)) {
9195 if (!MustExitMaxBECount) {
9196 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9197 MustExitMaxOrZero = EL.MaxOrZero;
9200 EL.ConstantMaxNotTaken);
9204 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9207 EL.ConstantMaxNotTaken);
9211 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9215 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9221 for (
const auto &Pair : ExitCounts) {
9223 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9225 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9226 {
L, AllowPredicates});
9228 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9229 MaxBECount, MaxOrZero);
9232ScalarEvolution::ExitLimit
9233ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9234 bool IsOnlyExit,
bool AllowPredicates) {
9235 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9239 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9244 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9245 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9246 "It should have one successor in loop and one exit block!");
9257 if (!
L->contains(SBB)) {
9262 assert(Exit &&
"Exiting block must have at least one exit");
9263 return computeExitLimitFromSingleExitSwitch(
9264 L, SI, Exit, IsOnlyExit);
9271 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9272 bool AllowPredicates) {
9273 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9274 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9275 ControlsOnlyExit, AllowPredicates);
9278std::optional<ScalarEvolution::ExitLimit>
9279ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9280 bool ExitIfTrue,
bool ControlsOnlyExit,
9281 bool AllowPredicates) {
9283 (void)this->ExitIfTrue;
9284 (void)this->AllowPredicates;
9286 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9287 this->AllowPredicates == AllowPredicates &&
9288 "Variance in assumed invariant key components!");
9289 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9290 if (Itr == TripCountMap.end())
9291 return std::nullopt;
9295void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9297 bool ControlsOnlyExit,
9298 bool AllowPredicates,
9300 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9301 this->AllowPredicates == AllowPredicates &&
9302 "Variance in assumed invariant key components!");
9304 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9305 assert(InsertResult.second &&
"Expected successful insertion!");
9310ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9311 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9312 bool ControlsOnlyExit,
bool AllowPredicates) {
9314 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9318 ExitLimit EL = computeExitLimitFromCondImpl(
9319 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9320 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9324ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9325 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9326 bool ControlsOnlyExit,
bool AllowPredicates) {
9328 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9329 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9330 return *LimitFromBinOp;
9336 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9337 if (EL.hasFullInfo() || !AllowPredicates)
9341 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9361 const WithOverflowInst *WO;
9376 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9377 ControlsOnlyExit, AllowPredicates);
9378 if (EL.hasAnyInfo())
9383 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9386std::optional<ScalarEvolution::ExitLimit>
9387ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9391 bool AllowPredicates) {
9400 return std::nullopt;
9404 ExitLimit EL0 = computeExitLimitFromCondCached(
9405 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9406 ExitLimit EL1 = computeExitLimitFromCondCached(
9407 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9412 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9417 if (EitherMayExit) {
9427 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9429 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9432 EL1.ConstantMaxNotTaken);
9434 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9436 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9439 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9443 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9444 BECount = EL0.ExactNotTaken;
9457 SymbolicMaxBECount =
9459 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9463ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9464 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9465 bool AllowPredicates) {
9477 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9479 if (EL.hasAnyInfo())
9482 auto *ExhaustiveCount =
9483 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9486 return ExhaustiveCount;
9488 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9491ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9493 bool ControlsOnlyExit,
bool AllowPredicates) {
9518 ConstantRange CompRange =
9536 InnerLHS = ZExt->getOperand();
9583 if (EL.hasAnyInfo())
9600 if (EL.hasAnyInfo())
return EL;
9632 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9634 if (EL.hasAnyInfo())
9650 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9652 if (EL.hasAnyInfo())
9663ScalarEvolution::ExitLimit
9664ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9666 BasicBlock *ExitingBlock,
9667 bool ControlsOnlyExit) {
9668 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9671 if (
Switch->getDefaultDest() == ExitingBlock)
9675 "Default case must not exit the loop!");
9681 if (EL.hasAnyInfo())
9693 "Evaluation of SCEV at constant didn't fold correctly?");
9697ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9707 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9714 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9716 unsigned &OutShiftAmt) {
9717 using namespace PatternMatch;
9719 ConstantInt *ShiftAmt;
9721 OutOpCode = Instruction::LShr;
9723 OutOpCode = Instruction::AShr;
9725 OutOpCode = Instruction::Shl;
9730 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9745 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9747 unsigned &ShiftAmtOut) {
9748 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9764 if (MatchPositiveShift(
LHS, V, OpC, Amt)) {
9765 PostShiftOpCode = OpC;
9771 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9774 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9780 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9787 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9793 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9805 ConstantInt *StableValue =
nullptr;
9810 case Instruction::AShr: {
9817 if (
Known.isNonNegative())
9818 StableValue = ConstantInt::get(Ty, 0);
9819 else if (
Known.isNegative())
9820 StableValue = ConstantInt::get(Ty, -1,
true);
9826 case Instruction::LShr:
9827 case Instruction::Shl:
9837 "Otherwise cannot be an operand to a branch instruction");
9839 if (
Result->isNullValue()) {
9848 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9850 const SCEV *StartSCEV =
getSCEV(StartValue);
9854 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9855 MaxBTC = std::min(MaxBTC, RangeBTC);
9859 const SCEV *UpperBound =
9876 if (
const Function *
F = CI->getCalledFunction())
9885 if (!L->contains(
I))
return false;
9890 return L->getHeader() ==
I->getParent();
9966 if (!
I)
return nullptr;
9979 std::vector<Constant*> Operands(
I->getNumOperands());
9981 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9985 if (!Operands[i])
return nullptr;
9990 if (!
C)
return nullptr;
10012 if (IncomingVal != CurrentVal) {
10015 IncomingVal = CurrentVal;
10019 return IncomingVal;
10027ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
10030 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
10039 DenseMap<Instruction *, Constant *> CurrentIterVals;
10041 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10047 for (PHINode &
PHI : Header->phis()) {
10049 CurrentIterVals[&
PHI] = StartCST;
10051 if (!CurrentIterVals.
count(PN))
10052 return RetVal =
nullptr;
10058 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
10061 unsigned IterationNum = 0;
10063 for (; ; ++IterationNum) {
10064 if (IterationNum == NumIterations)
10065 return RetVal = CurrentIterVals[PN];
10069 DenseMap<Instruction *, Constant *> NextIterVals;
10074 NextIterVals[PN] = NextPHI;
10076 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
10082 for (
const auto &
I : CurrentIterVals) {
10084 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
10089 for (
const auto &
I : PHIsToCompute) {
10090 PHINode *
PHI =
I.first;
10093 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10096 if (NextPHI !=
I.second)
10097 StoppedEvolving =
false;
10102 if (StoppedEvolving)
10103 return RetVal = CurrentIterVals[PN];
10105 CurrentIterVals.swap(NextIterVals);
10109const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
10119 DenseMap<Instruction *, Constant *> CurrentIterVals;
10121 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10124 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
10126 for (PHINode &
PHI : Header->phis()) {
10128 CurrentIterVals[&
PHI] = StartCST;
10130 if (!CurrentIterVals.
count(PN))
10138 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10145 if (CondVal->getValue() == uint64_t(ExitWhen)) {
10146 ++NumBruteForceTripCountsComputed;
10151 DenseMap<Instruction *, Constant *> NextIterVals;
10157 for (
const auto &
I : CurrentIterVals) {
10159 if (!
PHI ||
PHI->getParent() != Header)
continue;
10162 for (PHINode *
PHI : PHIsToCompute) {
10164 if (NextPHI)
continue;
10166 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10169 CurrentIterVals.
swap(NextIterVals);
10182 return LS.second ? LS.second : V;
10184 Values.emplace_back(L,
nullptr);
10187 const SCEV *
C = computeSCEVAtScope(V, L);
10188 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10189 if (LS.first == L) {
10192 ValuesAtScopesUsers[
C].push_back({L, V});
10203 switch (V->getSCEVType()) {
10243 assert(!
C->getType()->isPointerTy() &&
10244 "Can only have one pointer, and it must be last");
10269const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10270 SmallVectorImpl<SCEVUse> &NewOps) {
10305const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10306 switch (
V->getSCEVType()) {
10317 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10328 for (++i; i !=
e; ++i)
10373 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10383 for (++i; i !=
e; ++i) {
10388 return getWithOperands(V, NewOps);
10403 const Loop *CurrLoop = this->LI[
I->getParent()];
10414 if (BackedgeTakenCount->
isZero()) {
10415 Value *InitValue =
nullptr;
10416 bool MultipleInitValues =
false;
10422 MultipleInitValues =
true;
10427 if (!MultipleInitValues && InitValue)
10436 unsigned InLoopPred =
10447 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10461 SmallVector<Constant *, 4> Operands;
10462 Operands.
reserve(
I->getNumOperands());
10463 bool MadeImprovement =
false;
10478 MadeImprovement |= OrigV != OpV;
10483 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10488 if (!MadeImprovement)
10509const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10511 return stripInjectiveFunctions(ZExt->getOperand());
10513 return stripInjectiveFunctions(SExt->getOperand());
10531 assert(
A != 0 &&
"A must be non-zero.");
10547 if (MinTZ < Mult2 && L->getLoopPredecessor())
10549 if (MinTZ < Mult2) {
10572 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10592static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10598 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10599 << *AddRec <<
'\n');
10602 if (!LC || !MC || !
NC) {
10603 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10604 return std::nullopt;
10610 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10618 N =
N.sext(NewWidth);
10619 M = M.sext(NewWidth);
10620 L = L.sext(NewWidth);
10637 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10638 <<
", multiplied by " <<
T <<
'\n');
10647 std::optional<APInt>
Y) {
10649 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10652 return XW.
slt(YW) ? *
X : *
Y;
10655 return std::nullopt;
10656 return X ? *
X : *
Y;
10673 return std::nullopt;
10674 unsigned W =
X->getBitWidth();
10694static std::optional<APInt>
10700 return std::nullopt;
10703 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10704 std::optional<APInt>
X =
10707 return std::nullopt;
10712 return std::nullopt;
10727static std::optional<APInt>
10731 "Starting value of addrec should be 0");
10732 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10733 <<
Range <<
", addrec " << *AddRec <<
'\n');
10737 "Addrec's initial value should be in range");
10743 return std::nullopt;
10753 auto SolveForBoundary =
10754 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10757 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10758 << Bound <<
" (before multiplying by " << M <<
")\n");
10761 std::optional<APInt> SO;
10764 "signed overflow\n");
10768 "unsigned overflow\n");
10769 std::optional<APInt> UO =
10772 auto LeavesRange = [&] (
const APInt &
X) {
10780 if (
Range.contains(
V1->getValue()))
10789 return {std::nullopt,
false};
10794 if (LeavesRange(*Min))
10795 return { Min,
true };
10796 std::optional<APInt> Max = Min == SO ? UO : SO;
10797 if (LeavesRange(*Max))
10798 return { Max,
true };
10801 return {std::nullopt,
true};
10808 auto SL = SolveForBoundary(
Lower);
10809 auto SU = SolveForBoundary(
Upper);
10812 if (!SL.second || !SU.second)
10813 return std::nullopt;
10856ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10858 bool ControlsOnlyExit,
10859 bool AllowPredicates) {
10870 if (
C->getValue()->isZero())
return C;
10874 const SCEVAddRecExpr *AddRec =
10877 if (!AddRec && AllowPredicates)
10883 if (!AddRec || AddRec->
getLoop() != L)
10894 return ExitLimit(R, R, R,
false, Predicates);
10952 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10978 const SCEV *
Exact =
10986 const SCEV *SymbolicMax =
10988 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10997 AllowPredicates ? &Predicates :
nullptr, *
this, L);
11005 return ExitLimit(
E, M, S,
false, Predicates);
11008ScalarEvolution::ExitLimit
11009ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
11017 if (!
C->getValue()->isZero())
11027std::pair<const BasicBlock *, const BasicBlock *>
11028ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
11039 if (
const Loop *L = LI.getLoopFor(BB))
11040 return {
L->getLoopPredecessor(),
L->getHeader()};
11042 return {
nullptr, BB};
11051 if (
A ==
B)
return true;
11066 if (ComputesEqualValues(AI, BI))
11074 const SCEV *Op0, *Op1;
11093 auto TrivialCase = [&](
bool TriviallyTrue) {
11102 const SCEV *NewLHS, *NewRHS;
11126 return TrivialCase(
false);
11127 return TrivialCase(
true);
11146 RAdd->hasNoSignedWrap()) ||
11148 RAdd->hasNoUnsignedWrap())) {
11168 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
11169 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
11172 C->getAPInt().isStrictlyPositive()) ||
11196 const APInt &
RA = RC->getAPInt();
11198 bool SimplifiedByConstantRange =
false;
11203 return TrivialCase(
true);
11205 return TrivialCase(
false);
11214 Changed = SimplifiedByConstantRange =
true;
11218 if (!SimplifiedByConstantRange) {
11235 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11241 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11247 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11253 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11265 return TrivialCase(
true);
11267 return TrivialCase(
false);
11372 auto NonRecursive = [OrNegative](
const SCEV *S) {
11374 return C->getAPInt().isPowerOf2() ||
11375 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11381 if (NonRecursive(S))
11407 APInt C = Cst->getAPInt();
11408 return C.urem(M) == 0;
11416 const SCEV *SmodM =
11431 for (
auto *
A : Assumptions)
11432 if (
A->implies(
P, *
this))
11445std::pair<const SCEV *, const SCEV *>
11448 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11450 return { Start, Start };
11452 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11461 getUsedLoops(LHS, LoopsUsed);
11462 getUsedLoops(RHS, LoopsUsed);
11464 if (LoopsUsed.
empty())
11469 for (
const auto *L1 : LoopsUsed)
11470 for (
const auto *L2 : LoopsUsed)
11471 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11472 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11473 "Domination relationship is not a linear order");
11503 SplitRHS.second) &&
11515 if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
11519 return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11529 return std::nullopt;
11544 if (KnownWithoutContext)
11545 return KnownWithoutContext;
11552 return std::nullopt;
11558 const Loop *L = LHS->getLoop();
11563std::optional<ScalarEvolution::MonotonicPredicateType>
11566 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11572 auto ResultSwapped =
11575 assert(*ResultSwapped != *Result &&
11576 "monotonicity should flip as we flip the predicate");
11583std::optional<ScalarEvolution::MonotonicPredicateType>
11584ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11598 return std::nullopt;
11602 "Should be greater or less!");
11606 if (!LHS->hasNoUnsignedWrap())
11607 return std::nullopt;
11611 "Relational predicate is either signed or unsigned!");
11612 if (!
LHS->hasNoSignedWrap())
11613 return std::nullopt;
11615 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11623 return std::nullopt;
11626std::optional<ScalarEvolution::LoopInvariantPredicate>
11633 return std::nullopt;
11640 if (!ArLHS || ArLHS->
getLoop() != L)
11641 return std::nullopt;
11645 return std::nullopt;
11671 return std::nullopt;
11708 return std::nullopt;
11711std::optional<ScalarEvolution::LoopInvariantPredicate>
11716 Pred, LHS, RHS, L, CtxI, MaxIter))
11726 Pred, LHS, RHS, L, CtxI,
Op))
11728 return std::nullopt;
11731std::optional<ScalarEvolution::LoopInvariantPredicate>
11746 return std::nullopt;
11753 if (!AR || AR->
getLoop() != L)
11754 return std::nullopt;
11759 Pred = Pred.dropSameSign();
11763 return std::nullopt;
11769 if (Step != One && Step != MinusOne)
11770 return std::nullopt;
11776 return std::nullopt;
11782 return std::nullopt;
11790 if (Step == MinusOne)
11794 return std::nullopt;
11800bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11806 auto CheckRange = [&](
bool IsSigned) {
11809 return RangeLHS.
icmp(Pred, RangeRHS);
11818 if (CheckRange(
true) || CheckRange(
false))
11827bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11836 SCEVUse XNonConstOp, XConstOp;
11837 SCEVUse YNonConstOp, YConstOp;
11841 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11844 XFlagsPresent = ExpectedFlags;
11849 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11852 YFlagsPresent = ExpectedFlags;
11855 if (YNonConstOp != XNonConstOp)
11863 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11866 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11926bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11947bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11948 const SCEV *
LHS,
const SCEV *
RHS) {
11953 return any_of(*BB, [&](
const Instruction &
I) {
11954 using namespace llvm::PatternMatch;
11959 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11973 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11978 "This cannot be done on broken IR!");
11981 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11990 if (LoopContinuePredicate &&
11991 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11992 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11997 if (WalkingBEDominatingConds)
12003 const auto &BETakenInfo = getBackedgeTakenInfo(L);
12004 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
12011 const SCEV *LoopCounter =
12019 for (
auto &AssumeVH : AC.assumptions()) {
12026 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
12030 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
12033 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
12034 DTN != HeaderDTN; DTN = DTN->getIDom()) {
12035 assert(DTN &&
"should reach the loop header before reaching the root!");
12038 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
12056 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
12069 if (!DT.isReachableFromEntry(BB))
12073 "This cannot be done on broken IR!");
12081 const bool ProvingStrictComparison =
12083 bool ProvedNonStrictComparison =
false;
12084 bool ProvedNonEquality =
false;
12087 if (!ProvedNonStrictComparison)
12088 ProvedNonStrictComparison = Fn(NonStrictPredicate);
12089 if (!ProvedNonEquality)
12091 if (ProvedNonStrictComparison && ProvedNonEquality)
12096 if (ProvingStrictComparison) {
12098 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
12100 if (SplitAndProve(ProofFn))
12105 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
12107 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
12109 if (ProvingStrictComparison) {
12111 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
12113 if (SplitAndProve(ProofFn))
12122 const Loop *ContainingLoop = LI.getLoopFor(BB);
12124 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
12128 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
12129 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
12132 if (!BlockEntryPredicate)
12141 for (
auto &AssumeVH : AC.assumptions()) {
12145 if (!DT.dominates(CI, BB))
12148 if (ProveViaCond(CI->getArgOperand(0),
false))
12154 F.getParent(), Intrinsic::experimental_guard);
12156 for (
const auto *GU : GuardDecl->users())
12158 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12159 if (ProveViaCond(Guard->getArgOperand(0),
false))
12174 "LHS is not available at Loop Entry");
12176 "RHS is not available at Loop Entry");
12178 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12189 if (FoundCondValue ==
12193 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12197 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12200 const Value *Op0, *Op1;
12203 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12207 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12208 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12212 if (!ICI)
return false;
12216 CmpPredicate FoundPred;
12225 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12228bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12229 const SCEV *
RHS, CmpPredicate FoundPred,
12230 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12231 const Instruction *CtxI) {
12241 auto *WideType = FoundLHS->
getType();
12253 TruncFoundLHS, TruncFoundRHS, CtxI))
12279 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12283bool ScalarEvolution::isImpliedCondBalancedTypes(
12288 "Types should be balanced!");
12295 if (FoundLHS == FoundRHS)
12299 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12311 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12328 LHS, FoundLHS, FoundRHS, CtxI);
12330 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12352 assert(P1 != P2 &&
"Handled earlier!");
12356 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12360 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12363 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12364 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12365 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12370 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12381 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12382 CanonicalRHS, CanonicalFoundLHS,
12383 CanonicalFoundRHS);
12388 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12389 CanonicalRHS, CanonicalFoundLHS,
12390 CanonicalFoundRHS);
12397 const SCEVConstant *
C =
nullptr;
12398 const SCEV *
V =
nullptr;
12416 if (Min ==
C->getAPInt()) {
12421 APInt SharperMin = Min + 1;
12424 case ICmpInst::ICMP_SGE:
12425 case ICmpInst::ICMP_UGE:
12428 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12433 case ICmpInst::ICMP_SGT:
12434 case ICmpInst::ICMP_UGT:
12444 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12449 case ICmpInst::ICMP_SLE:
12450 case ICmpInst::ICMP_ULE:
12451 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12452 LHS, V, getConstant(SharperMin), CtxI))
12456 case ICmpInst::ICMP_SLT:
12457 case ICmpInst::ICMP_ULT:
12458 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12459 LHS, V, getConstant(Min), CtxI))
12473 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12477 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12480 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12496std::optional<APInt>
12503 APInt DiffMul(BW, 1);
12506 for (
unsigned I = 0;
I < 8; ++
I) {
12515 if (LAR->getLoop() != MAR->getLoop())
12516 return std::nullopt;
12520 if (!LAR->isAffine() || !MAR->isAffine())
12521 return std::nullopt;
12523 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12524 return std::nullopt;
12526 Less = LAR->getStart();
12527 More = MAR->getStart();
12532 auto MatchConstMul =
12533 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12538 return std::nullopt;
12540 if (
auto MatchedMore = MatchConstMul(More)) {
12541 if (
auto MatchedLess = MatchConstMul(
Less)) {
12542 if (MatchedMore->second == MatchedLess->second) {
12543 More = MatchedMore->first;
12544 Less = MatchedLess->first;
12545 DiffMul *= MatchedMore->second;
12556 Diff +=
C->getAPInt() * DiffMul;
12559 Diff -=
C->getAPInt() * DiffMul;
12562 Multiplicity[S] +=
Mul;
12564 auto Decompose = [&](
const SCEV *S,
int Mul) {
12571 Decompose(More, 1);
12572 Decompose(
Less, -1);
12576 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12577 for (
const auto &[S,
Mul] : Multiplicity) {
12582 return std::nullopt;
12584 }
else if (
Mul == -1) {
12586 return std::nullopt;
12589 return std::nullopt;
12593 if (NewMore == More || NewLess ==
Less)
12594 return std::nullopt;
12600 if (!More && !
Less)
12604 if (!More || !
Less)
12605 return std::nullopt;
12609 return std::nullopt;
12612bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12634 const auto *Latch = L->getLoopLatch();
12637 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12646 const auto *Latch = L->getLoopLatch();
12649 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12659bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12662 const SCEV *FoundLHS,
12663 const SCEV *FoundRHS) {
12672 if (!AddRecFoundLHS)
12679 const Loop *
L = AddRecFoundLHS->getLoop();
12680 if (L != AddRecLHS->getLoop())
12719 if (!RDiff || *LDiff != *RDiff)
12722 if (LDiff->isMinValue())
12725 APInt FoundRHSLimit;
12728 FoundRHSLimit = -(*RDiff);
12740bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12741 const SCEV *
RHS,
const SCEV *FoundLHS,
12742 const SCEV *FoundRHS,
unsigned Depth) {
12743 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12747 bool Erased = PendingMerges.erase(LPhi);
12748 assert(Erased &&
"Failed to erase LPhi!");
12752 bool Erased = PendingMerges.erase(RPhi);
12753 assert(Erased &&
"Failed to erase RPhi!");
12761 if (!PendingMerges.insert(Phi).second)
12775 if (!PendingMerges.insert(Phi).second)
12781 if (!LPhi && !RPhi)
12792 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12796 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12797 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12798 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12799 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12802 if (RPhi && RPhi->getParent() == LBB) {
12809 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12810 if (!ProvedEasily(L, R))
12821 auto *RLoop = RAR->
getLoop();
12822 auto *Predecessor = RLoop->getLoopPredecessor();
12823 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12825 if (!ProvedEasily(L1, RAR->
getStart()))
12827 auto *Latch = RLoop->getLoopLatch();
12828 assert(Latch &&
"Loop with AddRec with no latch?");
12849 if (
auto *Loop = LI.getLoopFor(LBB))
12852 if (!ProvedEasily(L,
RHS))
12859bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12862 const SCEV *FoundLHS,
12863 const SCEV *FoundRHS) {
12866 if (
RHS == FoundRHS) {
12871 if (
LHS != FoundLHS)
12878 Value *Shiftee, *ShiftValue;
12880 using namespace PatternMatch;
12881 if (
match(SUFoundRHS->getValue(),
12883 auto *ShifteeS =
getSCEV(Shiftee);
12901bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12902 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12903 const SCEV *FoundRHS) {
12935 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12943 return Diff == FoundDiff;
12946bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12948 const SCEV *FoundLHS,
12949 const SCEV *FoundRHS,
12950 const Instruction *CtxI) {
12951 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12953 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12955 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12956 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12958 isImpliedCondOperandsViaMatchingDiff(Pred,
LHS,
RHS, FoundLHS,
12960 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12964template <
typename MinMaxExprType>
12966 const SCEV *Candidate) {
12971 return is_contained(MinMaxExpr->operands(), Candidate);
12984 const SCEV *LStart, *RStart, *Step;
13057bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
13059 const SCEV *FoundLHS,
13060 const SCEV *FoundRHS,
13064 "LHS and RHS have different sizes?");
13067 "FoundLHS and FoundRHS have different sizes?");
13101 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
13103 return Ext->getOperand();
13110 auto *OrigLHS =
LHS;
13111 auto *OrigFoundLHS = FoundLHS;
13112 LHS = GetOpFromSExt(
LHS);
13113 FoundLHS = GetOpFromSExt(FoundLHS);
13116 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
13119 FoundRHS,
Depth + 1);
13132 if (!LHSAddExpr->hasNoSignedWrap())
13135 SCEVUse LL = LHSAddExpr->getOperand(0);
13136 SCEVUse LR = LHSAddExpr->getOperand(1);
13140 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
13141 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
13146 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
13152 using namespace llvm::PatternMatch;
13171 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13179 auto *DTy = Denominator->getType();
13180 auto *FRHSTy = FoundRHS->
getType();
13181 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13200 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13211 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13213 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13221 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13254bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13258 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13261 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13264bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13267 const SCEV *FoundLHS,
13268 const SCEV *FoundRHS) {
13304 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13310bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13311 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13312 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13326 ConstantRange FoundLHSRange =
13330 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13337 return LHSRange.
icmp(Pred, ConstRHS);
13340bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13353 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13361 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13364bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
13376 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
13384 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
13396const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
13397 const SCEV *Stride,
13428 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13439 :
APIntOps::umax(MaxEnd, MinStart);
13446ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13447 const Loop *L,
bool IsSigned,
13448 bool ControlsOnlyExit,
bool AllowPredicates) {
13452 bool PredicatedIV =
false;
13457 auto canProveNUW = [&]() {
13460 if (!ControlsOnlyExit)
13481 Limit = Limit.
zext(OuterBitWidth);
13493 Type *Ty = ZExt->getType();
13504 if (!
IV && AllowPredicates) {
13509 PredicatedIV =
true;
13513 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13527 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13530 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13535 if (!PositiveStride) {
13587 auto wouldZeroStrideBeUB = [&]() {
13599 if (!wouldZeroStrideBeUB()) {
13603 }
else if (!NoWrap) {
13606 if (canIVOverflowOnLT(
RHS, Stride, IsSigned))
13619 const SCEV *
Start =
IV->getStart();
13625 const SCEV *OrigStart =
Start;
13626 const SCEV *OrigRHS =
RHS;
13627 if (
Start->getType()->isPointerTy()) {
13638 const SCEV *End =
nullptr, *BECount =
nullptr,
13639 *BECountIfBackedgeTaken =
nullptr;
13642 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13643 any(RHSAddRec->getNoWrapFlags())) {
13656 const SCEV *RHSStart = RHSAddRec->getStart();
13657 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13669 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13678 BECountIfBackedgeTaken =
13683 if (BECount ==
nullptr) {
13688 const SCEV *MaxBECount = computeMaxBECountForLT(
13691 MaxBECount,
false , Predicates);
13698 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13725 const SCEV *Numerator =
13731 auto canProveRHSGreaterThanEqualStart = [&]() {
13750 auto *StartMinusOne =
13757 if (canProveRHSGreaterThanEqualStart()) {
13772 BECountIfBackedgeTaken =
13788 bool MayAddOverflow = [&] {
13834 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13848 if (!MayAddOverflow) {
13860 const SCEV *ConstantMaxBECount;
13861 bool MaxOrZero =
false;
13863 ConstantMaxBECount = BECount;
13864 }
else if (BECountIfBackedgeTaken &&
13869 ConstantMaxBECount = BECountIfBackedgeTaken;
13872 ConstantMaxBECount = computeMaxBECountForLT(
13880 const SCEV *SymbolicMaxBECount =
13882 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13886ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13887 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13888 bool ControlsOnlyExit,
bool AllowPredicates) {
13895 if (!
IV && AllowPredicates)
13902 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13906 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13919 if (!Stride->
isOne() && !NoWrap)
13920 if (canIVOverflowOnGT(
RHS, Stride, IsSigned))
13923 const SCEV *
Start =
IV->getStart();
13924 const SCEV *End =
RHS;
13935 if (
Start->getType()->isPointerTy()) {
13970 const SCEV *ConstantMaxBECount =
13977 ConstantMaxBECount = BECount;
13978 const SCEV *SymbolicMaxBECount =
13981 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13987 if (
Range.isFullSet())
13992 if (!SC->getValue()->isZero()) {
13998 return ShiftedAddRec->getNumIterationsInRange(
13999 Range.subtract(SC->getAPInt()), SE);
14030 APInt ExitVal = (End +
A).udiv(
A);
14043 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
14044 "Linear scev computation is off in a bad way!");
14075 assert(!
Last->isZero() &&
"Recurrency with zero step?");
14100 Ty =
Store->getValueOperand()->getType();
14102 Ty =
Load->getType();
14115 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14117 SE->ConstantEvolutionLoopExitValue.erase(PN);
14118 SE->eraseValueFromMap(getValPtr());
14122void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
14123 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14133 : CallbackVH(
V), SE(se) {}
14142 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
14144 LoopDispositions(64), BlockDispositions(64) {
14156 F.getParent(), Intrinsic::experimental_guard);
14157 HasGuards = GuardDecl && !GuardDecl->use_empty();
14161 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
14162 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14163 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14164 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14165 PendingMerges(
std::
move(Arg.PendingMerges)),
14166 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14167 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14168 PredicatedBackedgeTakenCounts(
14169 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14170 BECountUsers(
std::
move(Arg.BECountUsers)),
14171 ConstantEvolutionLoopExitValue(
14172 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14173 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14174 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14175 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14176 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14177 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14178 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14179 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14180 SignedRanges(
std::
move(Arg.SignedRanges)),
14181 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14182 UniquePreds(
std::
move(Arg.UniquePreds)),
14183 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14184 LoopUsers(
std::
move(Arg.LoopUsers)),
14185 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14186 FirstUnknown(Arg.FirstUnknown) {
14187 Arg.FirstUnknown =
nullptr;
14196 Tmp->~SCEVUnknown();
14198 FirstUnknown =
nullptr;
14200 ExprValueMap.clear();
14201 ValueExprMap.clear();
14203 BackedgeTakenCounts.clear();
14204 PredicatedBackedgeTakenCounts.clear();
14206 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14207 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14208 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14209 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14231 L->getHeader()->printAsOperand(OS,
false);
14235 L->getExitingBlocks(ExitingBlocks);
14236 if (ExitingBlocks.
size() != 1)
14237 OS <<
"<multiple exits> ";
14241 OS <<
"backedge-taken count is ";
14244 OS <<
"Unpredictable backedge-taken count.";
14247 if (ExitingBlocks.
size() > 1)
14248 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14249 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14257 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14260 OS <<
"\n Predicates:\n";
14261 for (
const auto *
P : Predicates)
14269 L->getHeader()->printAsOperand(OS,
false);
14274 OS <<
"constant max backedge-taken count is ";
14277 OS <<
", actual taken count either this or zero.";
14279 OS <<
"Unpredictable constant max backedge-taken count. ";
14284 L->getHeader()->printAsOperand(OS,
false);
14289 OS <<
"symbolic max backedge-taken count is ";
14292 OS <<
", actual taken count either this or zero.";
14294 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14298 if (ExitingBlocks.
size() > 1)
14299 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14300 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14310 OS <<
"\n predicated symbolic max exit count for "
14311 << ExitingBlock->
getName() <<
": ";
14313 OS <<
"\n Predicates:\n";
14314 for (
const auto *
P : Predicates)
14325 L->getHeader()->printAsOperand(OS,
false);
14328 OS <<
"Predicated backedge-taken count is ";
14331 OS <<
"Unpredictable predicated backedge-taken count.";
14333 OS <<
" Predicates:\n";
14334 for (
const auto *
P : Preds)
14339 auto *PredConstantMax =
14341 if (PredConstantMax != ConstantBTC) {
14343 L->getHeader()->printAsOperand(OS,
false);
14346 OS <<
"Predicated constant max backedge-taken count is ";
14349 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14351 OS <<
" Predicates:\n";
14352 for (
const auto *
P : Preds)
14357 auto *PredSymbolicMax =
14359 if (SymbolicBTC != PredSymbolicMax) {
14361 L->getHeader()->printAsOperand(OS,
false);
14364 OS <<
"Predicated symbolic max backedge-taken count is ";
14367 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14369 OS <<
" Predicates:\n";
14370 for (
const auto *
P : Preds)
14376 L->getHeader()->printAsOperand(OS,
false);
14403 OS <<
"Computable";
14413 OS <<
"DoesNotDominate";
14419 OS <<
"ProperlyDominates";
14436 OS <<
"Classifying expressions for: ";
14437 F.printAsOperand(OS,
false);
14452 const Loop *L = LI.getLoopFor(
I.getParent());
14467 OS <<
"\t\t" "Exits: ";
14470 OS <<
"<<Unknown>>";
14476 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14478 Iter->getHeader()->printAsOperand(OS,
false);
14486 InnerL->getHeader()->printAsOperand(OS,
false);
14497 OS <<
"Determining loop execution counts for: ";
14498 F.printAsOperand(OS,
false);
14506 auto &
Values = LoopDispositions[S];
14507 for (
auto &V :
Values) {
14508 if (V.getPointer() == L)
14513 auto &Values2 = LoopDispositions[S];
14515 if (V.getPointer() == L) {
14524ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14542 if (L->contains(AR->
getLoop()) &&
14544 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14549 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14550 " dominate the contained loop's header?");
14578 bool HasVarying =
false;
14579 bool HasUniform =
false;
14621 auto &
Values = BlockDispositions[S];
14622 for (
auto &V :
Values) {
14623 if (V.getPointer() == BB)
14628 auto &Values2 = BlockDispositions[S];
14630 if (V.getPointer() == BB) {
14639ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14669 bool Proper =
true;
14680 if (Instruction *
I =
14682 if (
I->getParent() == BB)
14684 if (DT.properlyDominates(
I->getParent(), BB))
14707void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14710 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14711 auto It = BECounts.find(L);
14712 if (It != BECounts.end()) {
14713 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14714 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14716 auto UserIt = BECountUsers.find(S);
14717 assert(UserIt != BECountUsers.end());
14722 BECounts.erase(It);
14730 while (!Worklist.
empty()) {
14732 auto Users = SCEVUsers.find(Curr);
14733 if (
Users != SCEVUsers.end())
14734 for (
const auto *User :
Users->second)
14735 if (ToForget.
insert(User).second)
14739 for (
const auto *S : ToForget)
14740 forgetMemoizedResultsImpl(S);
14742 PredicatedSCEVRewrites.remove_if(
14743 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14746void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14747 LoopDispositions.erase(S);
14748 BlockDispositions.erase(S);
14749 UnsignedRanges.erase(S);
14750 SignedRanges.erase(S);
14751 HasRecMap.erase(S);
14752 ConstantMultipleCache.erase(S);
14755 UnsignedWrapViaInductionTried.erase(AR);
14756 SignedWrapViaInductionTried.erase(AR);
14759 auto ExprIt = ExprValueMap.find(S);
14760 if (ExprIt != ExprValueMap.end()) {
14761 for (
Value *V : ExprIt->second) {
14762 auto ValueIt = ValueExprMap.find_as(V);
14763 if (ValueIt != ValueExprMap.end())
14764 ValueExprMap.erase(ValueIt);
14766 ExprValueMap.erase(ExprIt);
14769 auto ScopeIt = ValuesAtScopes.find(S);
14770 if (ScopeIt != ValuesAtScopes.end()) {
14771 for (
const auto &Pair : ScopeIt->second)
14774 std::make_pair(Pair.first, S));
14775 ValuesAtScopes.erase(ScopeIt);
14778 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14779 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14780 for (
const auto &Pair : ScopeUserIt->second)
14781 llvm::erase(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
14782 ValuesAtScopesUsers.erase(ScopeUserIt);
14785 auto BEUsersIt = BECountUsers.find(S);
14786 if (BEUsersIt != BECountUsers.end()) {
14788 auto Copy = BEUsersIt->second;
14789 for (
const auto &Pair : Copy)
14790 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14791 BECountUsers.erase(BEUsersIt);
14794 auto FoldUser = FoldCacheUser.find(S);
14795 if (FoldUser != FoldCacheUser.end())
14796 for (
auto &KV : FoldUser->second)
14797 FoldCache.erase(KV);
14798 FoldCacheUser.erase(S);
14802ScalarEvolution::getUsedLoops(
const SCEV *S,
14804 struct FindUsedLoops {
14805 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14806 : LoopsUsed(LoopsUsed) {}
14807 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14808 bool follow(
const SCEV *S) {
14814 bool isDone()
const {
return false; }
14817 FindUsedLoops
F(LoopsUsed);
14818 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14821void ScalarEvolution::getReachableBlocks(
14824 Worklist.
push_back(&F.getEntryBlock());
14825 while (!Worklist.
empty()) {
14827 if (!Reachable.
insert(BB).second)
14835 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14842 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14846 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14881 SCEVMapper SCM(SE2);
14883 SE2.getReachableBlocks(ReachableBlocks, F);
14885 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14903 while (!LoopStack.
empty()) {
14909 if (!ReachableBlocks.
contains(L->getHeader()))
14914 auto It = BackedgeTakenCounts.find(L);
14915 if (It == BackedgeTakenCounts.end())
14919 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14939 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14940 if (Delta && !Delta->
isZero()) {
14941 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14942 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14943 dbgs() <<
"New: " << *NewBECount <<
"\n";
14944 dbgs() <<
"Delta: " << *Delta <<
"\n";
14952 while (!Worklist.
empty()) {
14954 if (ValidLoops.
insert(L).second)
14955 Worklist.
append(L->begin(), L->end());
14957 for (
const auto &KV : ValueExprMap) {
14962 "AddRec references invalid loop");
14967 auto It = ExprValueMap.find(KV.second);
14968 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14969 dbgs() <<
"Value " << *KV.first
14970 <<
" is in ValueExprMap but not in ExprValueMap\n";
14975 if (!ReachableBlocks.
contains(
I->getParent()))
14977 const SCEV *OldSCEV = SCM.visit(KV.second);
14979 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14980 if (Delta && !Delta->
isZero()) {
14981 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14982 <<
"Old: " << *OldSCEV <<
"\n"
14983 <<
"New: " << *NewSCEV <<
"\n"
14984 <<
"Delta: " << *Delta <<
"\n";
14990 for (
const auto &KV : ExprValueMap) {
14991 for (
Value *V : KV.second) {
14992 const SCEV *S = ValueExprMap.lookup(V);
14994 dbgs() <<
"Value " << *V
14995 <<
" is in ExprValueMap but not in ValueExprMap\n";
14998 if (S != KV.first) {
14999 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
15000 << *KV.first <<
"\n";
15007 for (
const auto &S : UniqueSCEVs) {
15012 auto It = SCEVUsers.find(
Op);
15013 if (It != SCEVUsers.end() && It->second.count(&S))
15015 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
15016 <<
" is not being tracked!\n";
15022 for (
const auto &ValueAndVec : ValuesAtScopes) {
15024 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
15025 const Loop *L = LoopAndValueAtScope.first;
15026 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
15028 auto It = ValuesAtScopesUsers.find(ValueAtScope);
15029 if (It != ValuesAtScopesUsers.end() &&
15032 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
15033 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
15039 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
15040 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
15041 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
15042 const Loop *L = LoopAndValue.first;
15043 const SCEV *
Value = LoopAndValue.second;
15045 auto It = ValuesAtScopes.find(
Value);
15046 if (It != ValuesAtScopes.end() &&
15047 is_contained(It->second, std::make_pair(L, ValueAtScope)))
15049 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
15050 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
15056 auto VerifyBECountUsers = [&](
bool Predicated) {
15058 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
15059 for (
const auto &LoopAndBEInfo : BECounts) {
15060 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
15061 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
15063 auto UserIt = BECountUsers.find(S);
15064 if (UserIt != BECountUsers.end() &&
15065 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
15067 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
15068 <<
" missing from BECountUsers\n";
15075 VerifyBECountUsers(
false);
15076 VerifyBECountUsers(
true);
15079 for (
auto &[S,
Values] : LoopDispositions) {
15080 for (
auto [
Loop, CachedDisposition] :
Values) {
15082 if (CachedDisposition != RecomputedDisposition) {
15083 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
15084 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
15085 << RecomputedDisposition <<
"\n";
15092 for (
auto &[S,
Values] : BlockDispositions) {
15093 for (
auto [BB, CachedDisposition] :
Values) {
15095 if (CachedDisposition != RecomputedDisposition) {
15096 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
15097 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
15098 <<
", actual " << RecomputedDisposition <<
"\n";
15105 for (
auto [
FoldID, Expr] : FoldCache) {
15106 auto I = FoldCacheUser.find(Expr);
15107 if (
I == FoldCacheUser.end()) {
15108 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
15113 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
15117 for (
auto [Expr, IDs] : FoldCacheUser) {
15118 for (
auto &
FoldID : IDs) {
15121 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
15126 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
15127 <<
" != " << *Expr <<
"!\n";
15138 for (
auto [S, Multiple] : ConstantMultipleCache) {
15140 if ((Multiple != 0 && RecomputedMultiple != 0 &&
15141 Multiple.
urem(RecomputedMultiple) != 0 &&
15142 RecomputedMultiple.
urem(Multiple) != 0)) {
15143 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
15144 << *S <<
" : Computed " << RecomputedMultiple
15145 <<
" but cache contains " << Multiple <<
"!\n";
15153 FunctionAnalysisManager::Invalidator &Inv) {
15185 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15186 <<
F.getName() <<
"':\n";
15192 "Scalar Evolution Analysis",
false,
true)
15241 const SCEV *LHS,
const SCEV *RHS) {
15243 assert(LHS->getType() == RHS->getType() &&
15244 "Type mismatch between LHS and RHS");
15247 ID.AddInteger(Pred);
15248 ID.AddPointer(LHS);
15249 ID.AddPointer(RHS);
15250 void *IP =
nullptr;
15251 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
15255 UniquePreds.InsertNode(Eq, IP);
15266 ID.AddInteger(AddedFlags);
15267 void *IP =
nullptr;
15268 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
15270 auto *OF =
new (SCEVAllocator)
15272 UniquePreds.InsertNode(OF, IP);
15292 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15293 return Rewriter.visit(S);
15299 for (
const auto *Pred : U->getPredicates())
15301 if (IPred->getLHS() == Expr &&
15303 return IPred->getRHS();
15305 if (IPred->getLHS() == Expr &&
15306 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15307 return IPred->getRHS();
15310 return convertToAddRecWithPreds(Expr);
15313 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15329 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15346 explicit SCEVPredicateRewriter(
15347 const Loop *L, ScalarEvolution &SE,
15348 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15349 const SCEVPredicate *Pred)
15350 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15352 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15355 return Pred && Pred->
implies(
P, SE);
15361 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15364 return addOverflowAssumption(
A);
15373 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15377 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15379 if (!PredicatedRewrite)
15381 for (
const auto *
P : PredicatedRewrite->second){
15384 if (L != WP->getExpr()->getLoop())
15387 if (!addOverflowAssumption(
P))
15390 return PredicatedRewrite->first;
15393 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15394 const SCEVPredicate *Pred;
15403 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15410 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15430 if (!Step->
isOne())
15455 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15456 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15469 return Op->LHS == LHS &&
Op->RHS == RHS;
15476 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15478 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15503 const SCEV *Start = AR->getStart();
15504 const SCEV *OpStart =
Op->AR->getStart();
15509 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15518 const SCEV *Step = AR->getStepRecurrence(SE);
15519 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15572 if (Step->getValue()->getValue().isNonNegative())
15576 return ImpliedFlags;
15583 for (
const auto *
P : Preds)
15596 return this->implies(I, SE);
15608 const Loop *L = NWrap->getExpr()->getLoop();
15615 return RewrittenAR &&
15621 for (
const auto *Pred : Preds)
15622 Pred->print(OS,
Depth);
15627 for (
const auto *Pred : Set->Preds)
15635 bool CheckImplies = Preds.
size() < 16;
15638 if (CheckImplies &&
implies(
N, SE))
15644 for (
auto *
P : Preds) {
15645 if (CheckImplies &&
N->implies(
P, SE))
15649 Preds = std::move(PrunedPreds);
15650 Preds.push_back(
N);
15657 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15662 for (
const auto *
Op :
Ops)
15667 SCEVUsers[
Op].insert(
User);
15676 SCEVUsers[
Op].insert(
User);
15680 const SCEV *Expr = SE.getSCEV(V);
15685 RewriteEntry &Entry = RewriteMap[Expr];
15688 if (Entry.second && Generation == Entry.first)
15689 return Entry.second;
15694 Expr = Entry.second;
15696 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15697 Entry = {Generation, NewSCEV};
15703 if (!BackedgeCount) {
15705 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15706 for (
const auto *
P : Preds)
15709 return BackedgeCount;
15713 if (!SymbolicMaxBackedgeCount) {
15715 SymbolicMaxBackedgeCount =
15716 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15717 for (
const auto *
P : Preds)
15720 return SymbolicMaxBackedgeCount;
15724 if (!SmallConstantMaxTripCount) {
15726 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15727 for (
const auto *
P : Preds)
15730 return *SmallConstantMaxTripCount;
15734 if (Preds->implies(&Pred, SE))
15739 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15740 updateGeneration();
15753void PredicatedScalarEvolution::updateGeneration() {
15755 if (++Generation == 0) {
15756 for (
auto &
II : RewriteMap) {
15757 const SCEV *Rewritten =
II.second.second;
15779 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15785 ExtraPreds->
append(NewPreds);
15791 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15797 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15800 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15804 for (
auto *BB : L.getBlocks())
15805 for (
auto &
I : *BB) {
15806 if (!SE.isSCEVable(
I.getType()))
15809 auto *Expr = SE.getSCEV(&
I);
15810 auto II = RewriteMap.find(Expr);
15812 if (
II == RewriteMap.end())
15816 if (
II->second.second == Expr)
15821 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15829 LoopGuards Guards(SE);
15837void ScalarEvolution::LoopGuards::collectFromPHI(
15845 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15846 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15860 auto &RewriteMap =
G->second.RewriteMap;
15861 if (RewriteMap.empty())
15863 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15864 if (S == RewriteMap.end())
15870 return {C0,
SM->getSCEVType()};
15873 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15874 MinMaxPattern
P2) -> MinMaxPattern {
15875 auto [C1,
T1] =
P1;
15876 auto [C2, T2] =
P2;
15877 if (!C1 || !C2 ||
T1 != T2)
15881 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15883 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15885 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15887 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15892 auto P = GetMinMaxConst(0);
15893 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15896 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15899 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15902 Guards.RewriteMap.insert({
LHS,
RHS});
15910 const APInt &DivisorVal,
15912 const APInt *ExprVal;
15925 const APInt &DivisorVal,
15927 const APInt *ExprVal;
15935 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15949 const SCEV *URemRHS =
nullptr;
15953 const SCEV *Multiple =
15955 DivInfo[URemLHS] = Multiple;
15957 Multiples[URemLHS] =
C->getAPInt();
15977 auto IsMinMaxSCEVWithNonNegativeConstant =
15981 if (
MinMax->getNumOperands() != 2)
15984 if (
C->getAPInt().isNegative())
15986 SCTy =
MinMax->getSCEVType();
15995 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15997 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
16002 auto *DivisibleExpr =
16010void ScalarEvolution::LoopGuards::collectFromBlock(
16012 const BasicBlock *
Block,
const BasicBlock *Pred,
16020 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
16031 &ExprsToRewrite]() {
16032 const SCEVConstant *C1;
16045 if (ExactRegion.isWrappedSet() || ExactRegion.isFullSet())
16047 auto [
I,
Inserted] = RewriteMap.try_emplace(LHSUnknown);
16048 const SCEV *RewrittenLHS =
Inserted ? LHSUnknown :
I->second;
16056 if (MatchRangeCheckIdiom())
16073 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
16075 if (From == FromRewritten)
16077 RewriteMap[From] = To;
16083 auto GetMaybeRewritten = [&](
const SCEV *S) {
16084 return RewriteMap.lookup_or(S, S);
16087 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
16089 const APInt &DividesBy =
16104 switch (Predicate) {
16133 SmallPtrSet<const SCEV *, 16> Visited;
16135 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
16139 while (!Worklist.
empty()) {
16143 if (!Visited.
insert(From).second)
16145 const SCEV *FromRewritten = GetMaybeRewritten(From);
16146 const SCEV *To =
nullptr;
16148 switch (Predicate) {
16153 EnqueueOperands(
UMax);
16159 EnqueueOperands(
SMax);
16165 EnqueueOperands(
UMin);
16171 EnqueueOperands(
SMin);
16179 const SCEV *OneAlignedUp =
16181 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16193 const SCEVConstant *
C;
16202 Guards.NotEqual.insert({
LHS,
RHS});
16211 AddRewrite(From, FromRewritten, To);
16228 SE.F.
getParent(), Intrinsic::experimental_guard);
16230 for (
const auto *GU : GuardDecl->users())
16232 if (Guard->getFunction() ==
Block->getParent() &&
16241 unsigned NumCollectedConditions = 0;
16243 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16245 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16247 const CondBrInst *LoopEntryPredicate =
16249 if (!LoopEntryPredicate)
16254 NumCollectedConditions++;
16258 if (
Depth > 0 && NumCollectedConditions == 2)
16266 if (Pair.second->hasNPredecessorsOrMore(2) &&
16268 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16269 for (
auto &Phi : Pair.second->phis())
16280 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16281 SmallVector<Value *, 8> Worklist;
16282 SmallPtrSet<Value *, 8> Visited;
16284 while (!Worklist.
empty()) {
16291 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16315 DenseMap<const SCEV *, APInt> Multiples;
16317 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16324 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16325 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16329 for (
const auto &[K, Divisor] : Multiples) {
16330 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16331 Guards.RewriteMap[
K] =
16333 Guards.
rewrite(K), Divisor, SE),
16342 Guards.PreserveNUW =
true;
16343 Guards.PreserveNSW =
true;
16344 for (
const SCEV *Expr : ExprsToRewrite) {
16345 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16346 Guards.PreserveNUW &=
16348 Guards.PreserveNSW &=
16355 if (ExprsToRewrite.size() > 1) {
16356 for (
const SCEV *Expr : ExprsToRewrite) {
16357 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16358 Guards.RewriteMap.erase(Expr);
16359 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16368 class SCEVLoopGuardRewriter
16379 NotEqual(Guards.NotEqual) {
16380 if (Guards.PreserveNUW)
16382 if (Guards.PreserveNSW)
16389 return Map.lookup_or(Expr, Expr);
16393 if (
const SCEV *S = Map.lookup(Expr))
16400 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16401 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16402 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16404 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16405 if (
const SCEV *S = Map.lookup(NarrowExt))
16406 return SE.getZeroExtendExpr(S, Ty);
16407 Bitwidth = Bitwidth / 2;
16415 if (
const SCEV *S = Map.lookup(Expr))
16422 if (
const SCEV *S = Map.lookup(Expr))
16428 if (
const SCEV *S = Map.lookup(Expr))
16436 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16441 if (NotEqual.contains({LHS, RHS})) {
16443 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16444 return SE.getUMaxExpr(OneAlignedUp, S);
16451 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16462 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16463 return SE.getAddExpr(
16466 if (
const SCEV *S = Map.lookup(
Add))
16467 return SE.getAddExpr(Expr->
getOperand(0), S);
16479 : SE.getAddExpr(Operands,
16495 : SE.getMulExpr(Operands,
16501 if (RewriteMap.empty() && NotEqual.empty())
16504 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16505 return Rewriter.visit(Expr);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Expand Atomic instructions
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
static bool isSigned(unsigned Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
Value * getPointer(Value *Ptr)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This defines the Use class.
iv Induction Variable Users
static constexpr Value * getValue(Ty &ValueOrUse)
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
MachineInstr unsigned OpIdx
static constexpr unsigned SM(unsigned Version)
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
PowerPC Reduce CR logical Operation
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
const SmallVectorImpl< MachineOperand > & Cond
static DominatorTree getDomTree(Function &F)
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
SI optimize exec mask operations pre RA
static void visit(BasicBlock &Start, std::function< bool(BasicBlock *)> op)
This file provides utility classes that use RAII to save and restore values.
bool SCEVMinMaxExprContains(const SCEV *Root, const SCEV *OperandToFind, SCEVTypes RootKind)
static cl::opt< unsigned > MaxAddRecSize("scalar-evolution-max-add-rec-size", cl::Hidden, cl::desc("Max coefficients in AddRec during evolving"), cl::init(8))
static cl::opt< unsigned > RangeIterThreshold("scev-range-iter-threshold", cl::Hidden, cl::desc("Threshold for switching to iteratively computing SCEV ranges"), cl::init(32))
static const Loop * isIntegerLoopHeaderPHI(const PHINode *PN, LoopInfo &LI)
static unsigned getConstantTripCount(const SCEVConstant *ExitCount)
static int CompareValueComplexity(const LoopInfo *const LI, Value *LV, Value *RV, unsigned Depth)
Compare the two values LV and RV in terms of their "complexity" where "complexity" is a partial (and ...
static const SCEV * getNextSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static void insertFoldCacheEntry(const ScalarEvolution::FoldID &ID, const SCEV *S, DenseMap< ScalarEvolution::FoldID, const SCEV * > &FoldCache, DenseMap< const SCEV *, SmallVector< ScalarEvolution::FoldID, 2 > > &FoldCacheUser)
static cl::opt< bool > ClassifyExpressions("scalar-evolution-classify-expressions", cl::Hidden, cl::init(true), cl::desc("When printing analysis, include information on every instruction"))
static bool hasHugeExpression(ArrayRef< SCEVUse > Ops)
Returns true if Ops contains a huge SCEV (the subtree of S contains at least HugeExprThreshold nodes)...
static bool CanConstantFold(const Instruction *I)
Return true if we can constant fold an instruction of the specified type, assuming that all operands ...
static cl::opt< unsigned > AddOpsInlineThreshold("scev-addops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining addition operands into a SCEV"), cl::init(500))
static cl::opt< unsigned > MaxLoopGuardCollectionDepth("scalar-evolution-max-loop-guard-collection-depth", cl::Hidden, cl::desc("Maximum depth for recursive loop guard collection"), cl::init(1))
static cl::opt< bool > VerifyIR("scev-verify-ir", cl::Hidden, cl::desc("Verify IR correctness when making sensitive SCEV queries (slow)"), cl::init(false))
static bool RangeRefPHIAllowedOperands(DominatorTree &DT, PHINode *PHI)
static const SCEV * getPreStartForExtend(const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE, unsigned Depth)
static std::optional< APInt > MinOptional(std::optional< APInt > X, std::optional< APInt > Y)
Helper function to compare optional APInts: (a) if X and Y both exist, return min(X,...
static cl::opt< unsigned > MulOpsInlineThreshold("scev-mulops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining multiplication operands into a SCEV"), cl::init(32))
static BinaryOperator * getCommonInstForPHI(PHINode *PN)
static bool isDivisibilityGuard(const SCEV *LHS, const SCEV *RHS, ScalarEvolution &SE)
static std::optional< const SCEV * > createNodeForSelectViaUMinSeq(ScalarEvolution *SE, const SCEV *CondExpr, const SCEV *TrueExpr, const SCEV *FalseExpr)
static Constant * BuildConstantFromSCEV(const SCEV *V)
This builds up a Constant using the ConstantExpr interface.
static ConstantInt * EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C, ScalarEvolution &SE)
static const SCEV * BinomialCoefficient(const SCEV *It, unsigned K, ScalarEvolution &SE, Type *ResultTy)
Compute BC(It, K). The result has width W. Assume, K > 0.
static cl::opt< unsigned > MaxCastDepth("scalar-evolution-max-cast-depth", cl::Hidden, cl::desc("Maximum depth of recursive SExt/ZExt/Trunc"), cl::init(8))
static bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr, const SCEV *Candidate)
Is MaybeMinMaxExpr an (U|S)(Min|Max) of Candidate and some other values?
static PHINode * getConstantEvolvingPHI(Value *V, const Loop *L)
getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node in the loop that V is deri...
static const SCEV * SolveLinEquationWithOverflow(const APInt &A, const SCEV *B, SmallVectorImpl< const SCEVPredicate * > *Predicates, ScalarEvolution &SE, const Loop *L)
Finds the minimum unsigned root of the following equation:
static cl::opt< unsigned > MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, cl::desc("Maximum number of iterations SCEV will " "symbolically execute a constant " "derived loop"), cl::init(100))
static uint64_t umul_ov(uint64_t i, uint64_t j, bool &Overflow)
static void PrintSCEVWithTypeHint(raw_ostream &OS, const SCEV *S)
When printing a top-level SCEV for trip counts, it's helpful to include a type for constants which ar...
static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE, const Loop *L)
static SCEV::NoWrapFlags StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, ArrayRef< SCEVUse > Ops, SCEV::NoWrapFlags Flags)
static bool containsConstantInAddMulChain(const SCEV *StartExpr)
Determine if any of the operands in this SCEV are a constant or if any of the add or multiply express...
static const SCEV * getExtendAddRecStart(const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE, unsigned Depth)
static bool CollectAddOperandsWithScales(SmallDenseMap< SCEVUse, APInt, 16 > &M, SmallVectorImpl< SCEVUse > &NewOps, APInt &AccumulatedConstant, ArrayRef< SCEVUse > Ops, const APInt &Scale, ScalarEvolution &SE)
Process the given Ops list, which is a list of operands to be added under the given scale,...
static const SCEV * constantFoldAndGroupOps(ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT, SmallVectorImpl< SCEVUse > &Ops, FoldT Fold, IsIdentityT IsIdentity, IsAbsorberT IsAbsorber)
Performs a number of common optimizations on the passed Ops.
static cl::opt< unsigned > MaxPhiSCCAnalysisSize("scalar-evolution-max-scc-analysis-depth", cl::Hidden, cl::desc("Maximum amount of nodes to process while searching SCEVUnknown " "Phi strongly connected components"), cl::init(8))
static bool IsKnownPredicateViaAddRecStart(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
static void GroupByComplexity(SmallVectorImpl< SCEVUse > &Ops, LoopInfo *LI, DominatorTree &DT)
Given a list of SCEV objects, order them by their complexity, and group objects of the same complexit...
static bool collectDivisibilityInformation(ICmpInst::Predicate Predicate, const SCEV *LHS, const SCEV *RHS, DenseMap< const SCEV *, const SCEV * > &DivInfo, DenseMap< const SCEV *, APInt > &Multiples, ScalarEvolution &SE)
static cl::opt< unsigned > MaxSCEVOperationsImplicationDepth("scalar-evolution-max-scev-operations-implication-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV operations implication analysis"), cl::init(2))
static void PushDefUseChildren(Instruction *I, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push users of the given Instruction onto the given Worklist.
static std::optional< APInt > SolveQuadraticAddRecRange(const SCEVAddRecExpr *AddRec, const ConstantRange &Range, ScalarEvolution &SE)
Let c(n) be the value of the quadratic chrec {0,+,M,+,N} after n iterations.
static cl::opt< bool > UseContextForNoWrapFlagInference("scalar-evolution-use-context-for-no-wrap-flag-strenghening", cl::Hidden, cl::desc("Infer nuw/nsw flags using context where suitable"), cl::init(true))
static cl::opt< bool > EnableFiniteLoopControl("scalar-evolution-finite-loop", cl::Hidden, cl::desc("Handle <= and >= in finite loops"), cl::init(true))
static bool getOperandsForSelectLikePHI(DominatorTree &DT, PHINode *PN, Value *&Cond, Value *&LHS, Value *&RHS)
static std::optional< std::tuple< APInt, APInt, APInt, APInt, unsigned > > GetQuadraticEquation(const SCEVAddRecExpr *AddRec)
For a given quadratic addrec, generate coefficients of the corresponding quadratic equation,...
static bool isKnownPredicateExtendIdiom(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
static std::optional< BinaryOp > MatchBinaryOp(Value *V, const DataLayout &DL, AssumptionCache &AC, const DominatorTree &DT, const Instruction *CxtI)
Try to map V into a BinaryOp, and return std::nullopt on failure.
static std::optional< APInt > SolveQuadraticAddRecExact(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE)
Let c(n) be the value of the quadratic chrec {L,+,M,+,N} after n iterations.
static std::optional< APInt > TruncIfPossible(std::optional< APInt > X, unsigned BitWidth)
Helper function to truncate an optional APInt to a given BitWidth.
static cl::opt< unsigned > MaxSCEVCompareDepth("scalar-evolution-max-scev-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV complexity comparisons"), cl::init(32))
static APInt extractConstantWithoutWrapping(ScalarEvolution &SE, const SCEVConstant *ConstantTerm, const SCEVAddExpr *WholeAddExpr)
static cl::opt< unsigned > MaxConstantEvolvingDepth("scalar-evolution-max-constant-evolving-depth", cl::Hidden, cl::desc("Maximum depth of recursive constant evolving"), cl::init(32))
static bool MatchBinarySub(const SCEV *S, SCEVUse &LHS, SCEVUse &RHS)
static std::optional< ConstantRange > GetRangeFromMetadata(Value *V)
Helper method to assign a range to V from metadata present in the IR.
static cl::opt< unsigned > HugeExprThreshold("scalar-evolution-huge-expr-threshold", cl::Hidden, cl::desc("Size of the expression which is considered huge"), cl::init(4096))
static Type * isSimpleCastedPHI(const SCEV *Op, const SCEVUnknown *SymbolicPHI, bool &Signed, ScalarEvolution &SE)
Helper function to createAddRecFromPHIWithCasts.
static Constant * EvaluateExpression(Value *V, const Loop *L, DenseMap< Instruction *, Constant * > &Vals, const DataLayout &DL, const TargetLibraryInfo *TLI)
EvaluateExpression - Given an expression that passes the getConstantEvolvingPHI predicate,...
static const SCEV * getPreviousSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static const SCEV * MatchNotExpr(const SCEV *Expr)
If Expr computes ~A, return A else return nullptr.
static std::pair< ConstantRange, bool > getRangeForAffineARHelper(APInt Step, const ConstantRange &StartRange, const APInt &MaxBECount, bool Signed)
static cl::opt< unsigned > MaxValueCompareDepth("scalar-evolution-max-value-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive value complexity comparisons"), cl::init(2))
static const SCEV * applyDivisibilityOnMinMaxExpr(const SCEV *MinMaxExpr, APInt Divisor, ScalarEvolution &SE)
static cl::opt< bool, true > VerifySCEVOpt("verify-scev", cl::Hidden, cl::location(VerifySCEV), cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"))
static const SCEV * getSignedOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static cl::opt< unsigned > MaxArithDepth("scalar-evolution-max-arith-depth", cl::Hidden, cl::desc("Maximum depth of recursive arithmetics"), cl::init(32))
static bool HasSameValue(const SCEV *A, const SCEV *B)
SCEV structural equivalence is usually sufficient for testing whether two expressions are equal,...
static uint64_t Choose(uint64_t n, uint64_t k, bool &Overflow)
Compute the result of "n choose k", the binomial coefficient.
static std::optional< int > CompareSCEVComplexity(const LoopInfo *const LI, const SCEV *LHS, const SCEV *RHS, DominatorTree &DT, unsigned Depth=0)
static bool canConstantEvolve(Instruction *I, const Loop *L)
Determine whether this instruction can constant evolve within this loop assuming its operands can all...
static PHINode * getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L, DenseMap< Instruction *, PHINode * > &PHIMap, unsigned Depth)
getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by recursing through each instructi...
static bool scevUnconditionallyPropagatesPoisonFromOperands(SCEVTypes Kind)
static cl::opt< bool > VerifySCEVStrict("verify-scev-strict", cl::Hidden, cl::desc("Enable stricter verification with -verify-scev is passed"))
static Constant * getOtherIncomingValue(PHINode *PN, BasicBlock *BB)
static cl::opt< bool > UseExpensiveRangeSharpening("scalar-evolution-use-expensive-range-sharpening", cl::Hidden, cl::init(false), cl::desc("Use more powerful methods of sharpening expression ranges. May " "be costly in terms of compile time"))
static const SCEV * getUnsignedOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static bool IsKnownPredicateViaMinOrMax(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Is LHS Pred RHS true on the virtue of LHS or RHS being a Min or Max expression?
static bool BrPHIToSelect(DominatorTree &DT, CondBrInst *BI, PHINode *Merge, Value *&C, Value *&LHS, Value *&RHS)
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
static bool InBlock(const Value *V, const BasicBlock *BB)
Provides some synthesis utilities to produce sequences of values.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
static SymbolRef::Type getType(const Symbol *Sym)
LocallyHashedType DenseMapInfo< LocallyHashedType >::Empty
static std::optional< bool > isImpliedCondOperands(CmpInst::Predicate Pred, const Value *ALHS, const Value *ARHS, const Value *BLHS, const Value *BRHS)
Return true if "icmp Pred BLHS BRHS" is true whenever "icmp PredALHS ARHS" is true.
Virtual Register Rewriter
static const uint32_t IV[8]
SCEVCastSinkingRewriter(ScalarEvolution &SE, Type *TargetTy, ConversionFn CreatePtrCast)
static const SCEV * rewrite(const SCEV *Scev, ScalarEvolution &SE, Type *TargetTy, ConversionFn CreatePtrCast)
const SCEV * visitUnknown(const SCEVUnknown *Expr)
const SCEV * visitMulExpr(const SCEVMulExpr *Expr)
const SCEV * visitAddExpr(const SCEVAddExpr *Expr)
const SCEV * visit(const SCEV *S)
Class for arbitrary precision integers.
LLVM_ABI APInt umul_ov(const APInt &RHS, bool &Overflow) const
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
uint64_t getZExtValue() const
Get zero extended value.
unsigned getActiveBits() const
Compute the number of active bits in the value.
LLVM_ABI APInt trunc(unsigned width) const
Truncate to new width.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
APInt abs() const
Get the absolute value.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool isSignMask() const
Check if the APInt's value is returned by getSignMask.
LLVM_ABI APInt urem(const APInt &RHS) const
Unsigned remainder operation.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
bool isNegative() const
Determine sign of this APInt.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
LLVM_ABI APInt uadd_ov(const APInt &RHS, bool &Overflow) const
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
bool isNonPositive() const
Determine if this APInt Value is non-positive (<= 0).
unsigned countTrailingZeros() const
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
unsigned logBase2() const
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
LLVM_ABI APInt multiplicativeInverse() const
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
LLVM_ABI APInt sext(unsigned width) const
Sign extend to a new width.
APInt shl(unsigned shiftAmt) const
Left-shift function.
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
bool isSignBitSet() const
Determine if sign bit of this APInt is set.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
This templated class represents "all analyses that operate over <aparticular IR unit>" (e....
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
AnalysisUsage & addRequiredTransitive()
Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
Get the array size.
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
MutableArrayRef< WeakVH > assumptions()
Access the list of assumption handles currently tracked for this function.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
LLVM_ABI unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
LLVM_ABI Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
BinaryOps getOpcode() const
This class represents a function call, abstracting a target machine's calling convention.
virtual void deleted()
Callback for Value destruction.
bool isFalseWhenEqual() const
This is just a convenience.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ ICMP_UGE
unsigned greater or equal
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
@ ICMP_SGE
signed greater or equal
@ ICMP_ULE
unsigned less or equal
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
bool isTrueWhenEqual() const
This is just a convenience.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
static LLVM_ABI std::optional< CmpPredicate > getMatching(CmpPredicate A, CmpPredicate B)
Compares two CmpPredicates taking samesign into account and returns the canonicalized CmpPredicate if...
LLVM_ABI CmpInst::Predicate getPreferredSignedPredicate() const
Attempts to return a signed CmpInst::Predicate from the CmpPredicate.
CmpInst::Predicate dropSameSign() const
Drops samesign information.
Conditional Branch instruction.
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
static LLVM_ABI Constant * getNot(Constant *C)
static Constant * getPtrAdd(Constant *Ptr, Constant *Offset, GEPNoWrapFlags NW=GEPNoWrapFlags::none(), std::optional< ConstantRange > InRange=std::nullopt, Type *OnlyIfReduced=nullptr)
Create a getelementptr i8, ptr, offset constant expression.
static LLVM_ABI Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static LLVM_ABI Constant * getPtrToAddr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static LLVM_ABI Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
static LLVM_ABI Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
This is the shared class of boolean and integer constants.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
static LLVM_ABI ConstantInt * getBool(LLVMContext &Context, bool V)
This class represents a range of values.
LLVM_ABI ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
LLVM_ABI ConstantRange zextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
PreferredRangeType
If represented precisely, the result of some range operations may consist of multiple disjoint ranges...
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI ConstantRange urem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned remainder operation of...
LLVM_ABI bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
LLVM_ABI bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other?
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI ConstantRange zeroExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
LLVM_ABI bool isSignWrappedSet() const
Return true if this set wraps around the signed domain.
LLVM_ABI APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
LLVM_ABI bool isWrappedSet() const
Return true if this set wraps around the unsigned domain.
LLVM_ABI void print(raw_ostream &OS) const
Print out the bounds to a stream.
LLVM_ABI ConstantRange truncate(uint32_t BitWidth, unsigned NoWrapKind=0) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
LLVM_ABI ConstantRange signExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI bool contains(const APInt &Val) const
Return true if the specified value is in the set.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
LLVM_ABI ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
LLVM_ABI APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
static LLVM_ABI ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
LLVM_ABI unsigned getMinSignedBits() const
Compute the maximal number of bits needed to represent every value in this signed range.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
LLVM_ABI ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
LLVM_ABI ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
static LLVM_ABI ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)
Produce the range that contains X if and only if "X BinOp Other" does not wrap.
This is an important base class in LLVM.
A parsed version of the target data layout string in and methods for querying it.
LLVM_ABI const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
LLVM_ABI IntegerType * getIntPtrType(LLVMContext &C, unsigned AddressSpace=0) const
Returns an integer type with size at least as big as that of a pointer in the given address space.
LLVM_ABI unsigned getIndexTypeSizeInBits(Type *Ty) const
The size in bits of the index used in GEP calculation for this type.
LLVM_ABI IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
TypeSize getTypeSizeInBits(Type *Ty) const
Size examples:
ValueT lookup(const_arg_type_t< KeyT > Val) const
Return the entry for the specified key, or a default constructed value if no such entry exists.
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive,...
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Analysis pass which computes a DominatorTree.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
This class describes a reference to an interned FoldingSetNodeID, which can be a useful to store node...
This class is used to gather all the unique data bits of a node.
Represents flags for the getelementptr instruction/expression.
bool hasNoUnsignedSignedWrap() const
bool hasNoUnsignedWrap() const
static GEPNoWrapFlags none()
static LLVM_ABI Type * getTypeAtIndex(Type *Ty, Value *Idx)
Return the type of the element at the given index of an indexable type.
Module * getParent()
Get the module that this global value is contained inside of...
static bool isPrivateLinkage(LinkageTypes Linkage)
static bool isInternalLinkage(LinkageTypes Linkage)
This instruction compares its operands according to the predicate given to the constructor.
CmpPredicate getCmpPredicate() const
static bool isGE(Predicate P)
Return true if the predicate is SGE or UGE.
CmpPredicate getSwappedCmpPredicate() const
static LLVM_ABI bool compare(const APInt &LHS, const APInt &RHS, ICmpInst::Predicate Pred)
Return result of LHS Pred RHS comparison.
static bool isLT(Predicate P)
Return true if the predicate is SLT or ULT.
CmpPredicate getInverseCmpPredicate() const
Predicate getNonStrictCmpPredicate() const
For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.
static bool isGT(Predicate P)
Return true if the predicate is SGT or UGT.
Predicate getFlippedSignednessPredicate() const
For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->EQ.
static CmpPredicate getInverseCmpPredicate(CmpPredicate Pred)
bool isEquality() const
Return true if this predicate is either EQ or NE.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
static bool isLE(Predicate P)
Return true if the predicate is SLE or ULE.
LLVM_ABI bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
LLVM_ABI bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
LLVM_ABI bool isIdenticalToWhenDefined(const Instruction *I, bool IntersectAttrs=false) const LLVM_READONLY
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...
Class to represent integer types.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
A helper class to return the specified delimiter string after the first invocation of operator String...
An instruction for reading from memory.
Analysis pass that exposes the LoopInfo for a function.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getHeader() const
unsigned getLoopDepth() const
Return the nesting level of this loop.
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
A Module instance is used to store all the information related to an LLVM module.
unsigned getOpcode() const
Return the opcode for this Instruction or ConstantExpr.
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
bool hasNoSignedWrap() const
Test whether this operation is known to never undergo signed overflow, aka the nsw property.
bool hasNoUnsignedWrap() const
Test whether this operation is known to never undergo unsigned overflow, aka the nuw property.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
PointerIntPair - This class implements a pair of a pointer and small integer.
static PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the default address space (address sp...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
LLVM_ABI void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
LLVM_ABI const SCEVPredicate & getPredicate() const
LLVM_ABI const SCEV * getPredicatedSCEV(const SCEV *Expr)
Returns the rewritten SCEV for Expr in the context of the current SCEV predicate.
LLVM_ABI bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2, ArrayRef< const SCEVPredicate * > ExtraPreds={}) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds and ExtraPreds.
LLVM_ABI bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've statically proved that V doesn't wrap.
LLVM_ABI const SCEVAddRecExpr * getAsAddRec(Value *V, SmallVectorImpl< const SCEVPredicate * > *WrapPredsAdded=nullptr)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
LLVM_ABI void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
LLVM_ABI PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
LLVM_ABI unsigned getSmallConstantMaxTripCount()
Returns the upper bound of the loop trip count as a normal unsigned value, or 0 if the trip count is ...
LLVM_ABI void addPredicates(ArrayRef< const SCEVPredicate * > Preds)
Adds all predicates in Preds.
LLVM_ABI const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSymbolicMaxBackedgeTakenCount()
Get the (predicated) symbolic max backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
constexpr bool isValid() const
This node represents an addition of some number of SCEVs.
This node represents a polynomial recurrence on the trip count of the specified loop.
friend class ScalarEvolution
LLVM_ABI const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a recurrence without clearing any previously set flags.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
bool isQuadratic() const
Return true if this represents an expression A + B*x + C*x^2 where A, B and C are loop invariant valu...
LLVM_ABI const SCEV * getNumIterationsInRange(const ConstantRange &Range, ScalarEvolution &SE) const
Return the number of iterations of this loop that produce values in the specified constant range.
LLVM_ABI const SCEVAddRecExpr * getPostIncExpr(ScalarEvolution &SE) const
Return an expression representing the value of this expression one iteration of the loop ahead.
const Loop * getLoop() const
SCEVUse getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
This is the base class for unary cast operator classes.
SCEVUse getOperand() const
LLVM_ABI SCEVCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, SCEVUse op, Type *ty)
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a non-recurrence without clearing previously set flags.
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
SCEVComparePredicate(const FoldingSetNodeIDRef ID, const ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Implementation of the SCEVPredicate interface.
This class represents a constant integer value.
ConstantInt * getValue() const
const APInt & getAPInt() const
This is the base class for unary integral cast operator classes.
LLVM_ABI SCEVIntegralCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, SCEVUse op, Type *ty)
This node is the base class min/max selections.
static enum SCEVTypes negate(enum SCEVTypes T)
This node represents multiplication of some number of SCEVs.
This node is a base class providing common functionality for n'ary operators.
bool hasNoUnsignedWrap() const
ArrayRef< SCEVUse > operands() const
bool hasNoSelfWrap() const
size_t getNumOperands() const
bool hasNoSignedWrap() const
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
SCEVUse getOperand(unsigned i) const
This class represents an assumption made using SCEV expressions which can be checked at run-time.
SCEVPredicate(const SCEVPredicate &)=default
virtual bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const =0
Returns true if this predicate implies N.
This class represents a cast from a pointer to a pointer-sized integer value, without capturing the p...
This class represents a cast from a pointer to a pointer-sized integer value.
This visitor recursively visits a SCEV expression and re-writes it.
const SCEV * visitSignExtendExpr(const SCEVSignExtendExpr *Expr)
const SCEV * visit(const SCEV *S)
const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)
const SCEV * visitSMinExpr(const SCEVSMinExpr *Expr)
SCEVRewriteVisitor(ScalarEvolution &SE)
const SCEV * visitUMinExpr(const SCEVUMinExpr *Expr)
This class represents a signed minimum selection.
This node is the base class for sequential/in-order min/max selections.
static SCEVTypes getEquivalentNonSequentialSCEVType(SCEVTypes Ty)
This class represents a sign extension of a small integer value to a larger integer value.
Visit all nodes in the expression tree using worklist traversal.
This class represents a truncation of an integer value to a smaller integer value.
This class represents a binary unsigned division operation.
This class represents an unsigned minimum selection.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
void print(raw_ostream &OS, unsigned Depth) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Returns true if this predicate implies N.
SCEVUnionPredicate(ArrayRef< const SCEVPredicate * > Preds, ScalarEvolution &SE)
Union predicates don't get cached so create a dummy set ID for it.
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
SCEVUnionPredicate getUnionWith(const SCEVPredicate *N, ScalarEvolution &SE) const
Returns a new SCEVUnionPredicate that is the union of this predicate and the given predicate N.
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents the value of vscale, as used when defining the length of a scalable vector or r...
This class represents an assumption made on an AddRec expression.
IncrementWrapFlags
Similar to SCEV::NoWrapFlags, but with slightly different semantics for FlagNUSW.
SCEVWrapPredicate(const FoldingSetNodeIDRef ID, const SCEVAddRecExpr *AR, IncrementWrapFlags Flags)
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Returns true if this predicate implies N.
static SCEVWrapPredicate::IncrementWrapFlags setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OnFlags)
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
const SCEVAddRecExpr * getExpr() const
Implementation of the SCEVPredicate interface.
static SCEVWrapPredicate::IncrementWrapFlags clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OffFlags)
Convenient IncrementWrapFlags manipulation methods.
static SCEVWrapPredicate::IncrementWrapFlags getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE)
Returns the set of SCEVWrapPredicate no wrap flags implied by a SCEVAddRecExpr.
IncrementWrapFlags getFlags() const
Returns the set assumed no overflow flags.
This class represents a zero extension of a small integer value to a larger integer value.
This class represents an analyzed expression in the program.
unsigned short getExpressionSize() const
SCEVNoWrapFlags NoWrapFlags
LLVM_ABI bool isOne() const
Return true if the expression is a constant one.
static constexpr auto FlagNUW
LLVM_ABI void computeAndSetCanonical(ScalarEvolution &SE)
Compute and set the canonical SCEV, by constructing a SCEV with the same operands,...
LLVM_ABI bool isZero() const
Return true if the expression is a constant zero.
const SCEV * CanonicalSCEV
Pointer to the canonical version of the SCEV, i.e.
static constexpr auto FlagAnyWrap
LLVM_ABI void dump() const
This method is used for debugging.
LLVM_ABI bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
LLVM_ABI bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
static constexpr auto FlagNSW
LLVM_ABI ArrayRef< SCEVUse > operands() const
Return operands of this SCEV expression.
LLVM_ABI void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
SCEV(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, unsigned short ExpressionSize)
SCEVTypes getSCEVType() const
static constexpr auto FlagNW
LLVM_ABI Type * getType() const
Return the LLVM type of this SCEV expression.
Analysis pass that exposes the ScalarEvolution for a function.
LLVM_ABI ScalarEvolution run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
void print(raw_ostream &OS, const Module *=nullptr) const override
print - Print out the internal state of the pass.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
ScalarEvolutionWrapperPass()
static LLVM_ABI LoopGuards collect(const Loop *L, ScalarEvolution &SE)
Collect rewrite map for loop guards for loop L, together with flags indicating if NUW and NSW can be ...
LLVM_ABI const SCEV * rewrite(const SCEV *Expr) const
Try to apply the collected loop guards to Expr.
The main scalar evolution driver.
LLVM_ABI const SCEV * getUDivExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
static bool hasFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags TestFlags)
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
LLVM_ABI bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
LLVM_ABI bool isKnownOnEveryIteration(CmpPredicate Pred, const SCEVAddRecExpr *LHS, const SCEV *RHS)
Test if the condition described by Pred, LHS, RHS is known to be true on every iteration of the loop ...
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterationsImpl(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
LLVM_ABI const SCEV * getUDivCeilSCEV(const SCEV *N, const SCEV *D)
Compute ceil(N / D).
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterations(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L at given Context duri...
LLVM_ABI Type * getWiderType(Type *Ty1, Type *Ty2) const
LLVM_ABI const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)
LLVM_ABI bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
LLVM_ABI bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
LLVM_ABI const SCEV * getPredicatedConstantMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getConstantMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
LLVM_ABI bool isLoopEntryGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
LLVM_ABI bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
LLVM_ABI const SCEV * getURemExpr(SCEVUse LHS, SCEVUse RHS)
Represents an unsigned remainder expression based on unsigned division.
LLVM_ABI const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
LLVM_ABI const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
LLVM_ABI const SCEV * getSMinExpr(SCEVUse LHS, SCEVUse RHS)
LLVM_ABI void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags)
Update no-wrap flags of an AddRec.
LLVM_ABI const SCEV * getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS)
Promote the operands to the wider of the types using zero-extension, and then perform a umax operatio...
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
LLVM_ABI bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?
LLVM_ABI ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsOnlyExit, bool AllowPredicates=false)
Compute the number of times the backedge of the specified loop will execute if its exit condition wer...
LLVM_ABI const SCEV * getZeroExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &Operands)
LLVM_ABI const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
LLVM_ABI uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
LLVM_ABI const SCEV * getConstant(ConstantInt *V)
LLVM_ABI const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
LLVM_ABI const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
LLVM_ABI const SCEV * getAddRecExpr(SCEVUse Start, SCEVUse Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
LLVM_ABI const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
static LLVM_ABI bool isGuaranteedNotToBePoison(const SCEV *Op)
Returns true if Op is guaranteed to not be poison.
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
LLVM_ABI const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
LLVM_ABI ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI)
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LLVM_ABI const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI const SCEV * getLosslessPtrToIntExpr(const SCEV *Op)
LLVM_ABI const SCEV * getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty)
LLVM_ABI const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &Operands)
LLVM_ABI std::optional< bool > evaluatePredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Check whether the condition described by Pred, LHS, and RHS is true or false in the given Context.
LLVM_ABI unsigned getSmallConstantMaxTripCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Returns the upper bound of the loop trip count as a normal unsigned value.
LLVM_ABI const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
LLVM_ABI bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
LLVM_ABI void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
LLVM_ABI bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
LLVM_ABI bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
LLVM_ABI bool SimplifyICmpOperands(CmpPredicate &Pred, SCEVUse &LHS, SCEVUse &RHS, unsigned Depth=0)
Simplify LHS and RHS in a comparison with predicate Pred.
APInt getUnsignedRangeMin(const SCEV *S)
Determine the min of the unsigned range for a particular SCEV.
LLVM_ABI const SCEV * getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo)
Return an expression for offsetof on the given field with type IntTy.
LLVM_ABI LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
LLVM_ABI bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
LLVM_ABI const SCEV * getSignExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool hasOperand(const SCEV *S, const SCEV *Op) const
Test whether the given SCEV has Op as a direct or indirect operand.
LLVM_ABI const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
LLVM_ABI Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
LLVM_ABI const SCEVPredicate * getComparePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
LLVM_ABI bool haveSameSign(const SCEV *S1, const SCEV *S2)
Return true if we know that S1 and S2 must have the same sign.
LLVM_ABI const SCEV * getNotSCEV(const SCEV *V)
Return the SCEV object corresponding to ~V.
LLVM_ABI const SCEV * getElementCount(Type *Ty, ElementCount EC, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
LLVM_ABI bool instructionCouldExistWithOperands(const SCEV *A, const SCEV *B)
Return true if there exists a point in the program at which both A and B could be operands to the sam...
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
LLVM_ABI void print(raw_ostream &OS) const
LLVM_ABI const SCEV * getPredicatedExitCount(const Loop *L, const BasicBlock *ExitingBlock, SmallVectorImpl< const SCEVPredicate * > *Predicates, ExitCountKind Kind=Exact)
Same as above except this uses the predicated backedge taken info and may require predicates.
static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
LLVM_ABI void forgetTopmostLoop(const Loop *L)
LLVM_ABI void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
APInt getSignedRangeMin(const SCEV *S)
Determine the min of the signed range for a particular SCEV.
LLVM_ABI bool isLoopUniform(const SCEV *S, const Loop *L)
Returns true if the given SCEV is loop-uniform with respect to the specified loop L.
LLVM_ABI const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
LLVM_ABI const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEV * getUMaxExpr(SCEVUse LHS, SCEVUse RHS)
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags Mask)
Convenient NoWrapFlags manipulation.
@ MonotonicallyDecreasing
@ MonotonicallyIncreasing
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI=nullptr)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L, return a LoopInvaria...
LLVM_ABI const SCEV * getStoreSizeOfExpr(Type *IntTy, Type *StoreTy)
Return an expression for the store size of StoreTy that is type IntTy.
LLVM_ABI const SCEVPredicate * getWrapPredicate(const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
LLVM_ABI bool isLoopBackedgeGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether the backedge of the loop is protected by a conditional between LHS and RHS.
LLVM_ABI APInt getNonZeroConstantMultiple(const SCEV *S)
const SCEV * getMinusOne(Type *Ty)
Return a SCEV for the constant -1 of a specific type.
static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
LLVM_ABI bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
LLVM_ABI BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB)
Return the "disposition" of the given SCEV with respect to the given block.
LLVM_ABI const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
LLVM_ABI const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
Promote the operands to the wider of the types using zero-extension, and then perform a umin operatio...
LLVM_ABI bool loopIsFiniteByAssumption(const Loop *L)
Return true if this loop is finite by assumption.
LLVM_ABI const SCEV * getExistingSCEV(Value *V)
Return an existing SCEV for V if there is one, otherwise return nullptr.
LLVM_ABI APInt getConstantMultiple(const SCEV *S, const Instruction *CtxI=nullptr)
Returns the max constant multiple of S.
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
@ LoopComputable
The SCEV varies predictably with the loop.
@ LoopVariant
The SCEV is loop-variant (unknown).
@ LoopInvariant
The SCEV is loop-invariant.
@ LoopUniform
The SCEV is loop-uniform.
friend class SCEVCallbackVH
LLVM_ABI bool isKnownMultipleOf(const SCEV *S, uint64_t M, SmallVectorImpl< const SCEVPredicate * > &Assumptions)
Check that S is a multiple of M.
LLVM_ABI const SCEV * getAnyExtendExpr(const SCEV *Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
LLVM_ABI bool isKnownToBeAPowerOfTwo(const SCEV *S, bool OrZero=false, bool OrNegative=false)
Test if the given expression is known to be a power of 2.
LLVM_ABI std::optional< SCEV::NoWrapFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
LLVM_ABI void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)
Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...
LLVM_ABI bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
LLVM_ABI std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
LLVM_ABI const SCEV * getCouldNotCompute()
LLVM_ABI const SCEV * getMulExpr(SmallVectorImpl< SCEVUse > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
LLVM_ABI bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
LLVM_ABI uint32_t getMinTrailingZeros(const SCEV *S, const Instruction *CtxI=nullptr)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
@ DominatesBlock
The SCEV dominates the block.
@ ProperlyDominatesBlock
The SCEV properly dominates the block.
@ DoesNotDominateBlock
The SCEV does not dominate the block.
LLVM_ABI const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
LLVM_ABI const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI void getPoisonGeneratingValues(SmallPtrSetImpl< const Value * > &Result, const SCEV *S)
Return the set of Values that, if poison, will definitively result in S being poison as well.
LLVM_ABI void forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
LLVM_ABI const SCEV * getVScale(Type *Ty)
LLVM_ABI unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
LLVM_ABI bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
LLVM_ABI const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
LLVM_ABI void forgetAllLoops()
LLVM_ABI bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
APInt getUnsignedRangeMax(const SCEV *S)
Determine the max of the unsigned range for a particular SCEV.
LLVM_ABI const SCEV * getAddExpr(SmallVectorImpl< SCEVUse > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
ExitCountKind
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of ...
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
@ ConstantMaximum
A constant which provides an upper bound on the exact trip count.
@ Exact
An expression exactly describing the number of times the backedge has executed when a loop is exited.
LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
LLVM_ABI const SCEV * getPtrToAddrExpr(const SCEV *Op)
LLVM_ABI const SCEVAddRecExpr * convertSCEVToAddRecWithPredicates(const SCEV *S, const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Preds)
Tries to convert the S expression to an AddRec expression, adding additional predicates to Preds as r...
LLVM_ABI const SCEV * getSMaxExpr(SCEVUse LHS, SCEVUse RHS)
LLVM_ABI const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
LLVM_ABI const SCEV * getSizeOfExpr(Type *IntTy, TypeSize Size)
Return an expression for a TypeSize.
LLVM_ABI std::optional< bool > evaluatePredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Check whether the condition described by Pred, LHS, and RHS is true or false.
LLVM_ABI const SCEV * getUnknown(Value *V)
LLVM_ABI std::optional< std::pair< const SCEV *, SmallVector< const SCEVPredicate *, 3 > > > createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI)
Checks if SymbolicPHI can be rewritten as an AddRecExpr under some Predicates.
LLVM_ABI const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool isKnownViaInduction(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
We'd like to check the predicate on every iteration of the most dominated loop between loops used in ...
LLVM_ABI std::optional< APInt > computeConstantDifference(const SCEV *LHS, const SCEV *RHS)
Compute LHS - RHS and returns the result as an APInt if it is a constant, and std::nullopt if it isn'...
LLVM_ABI bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
LLVM_ABI const SCEV * getUDivExactExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
LLVM_ABI const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
LLVM_ABI std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
LLVM_ABI bool canReuseInstruction(const SCEV *S, Instruction *I, SmallVectorImpl< Instruction * > &DropPoisonGeneratingInsts)
Check whether it is poison-safe to represent the expression S using the instruction I.
LLVM_ABI bool isKnownPredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * getPredicatedSymbolicMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getSymbolicMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI ~ScalarEvolution()
LLVM_ABI const SCEV * getGEPExpr(GEPOperator *GEP, ArrayRef< SCEVUse > IndexExprs)
Returns an expression for a GEP.
LLVM_ABI const SCEV * getUMinExpr(SCEVUse LHS, SCEVUse RHS, bool Sequential=false)
LLVM_ABI void registerUser(const SCEV *User, ArrayRef< const SCEV * > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
LLVM_ABI bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the basic block is protected by a conditional between LHS and RHS.
LLVM_ABI const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool containsErasedValue(const SCEV *S) const
Return true if the SCEV expression contains a Value that has been optimised out and is now a nullptr.
const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
LLVM_ABI void verify() const
LLVMContext & getContext() const
Implements a dense probed hash-table based set with some number of buckets stored inline.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Represent a constant reference to a string, i.e.
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
TypeSize getElementOffset(unsigned Idx) const
TypeSize getSizeInBits() const
Class to represent struct types.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntOrPtrTy() const
Return true if this is an integer type or a pointer type.
bool isIntegerTy() const
True if this is an instance of IntegerType.
static LLVM_ABI IntegerType * getIntNTy(LLVMContext &C, unsigned N)
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
LLVMContext & getContext() const
All values hold a context through their type.
unsigned getValueID() const
Return an ID for the concrete type of this object.
LLVM_ABI void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
LLVM_ABI std::optional< APInt > SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, unsigned RangeWidth)
Let q(n) = An^2 + Bn + C, and BW = bit width of the value range (e.g.
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
LLVM_ABI APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
constexpr bool any(E Val)
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
int getMinValue(MCInstrInfo const &MCII, MCInst const &MCI)
Return the minimum value of an extendable operand.
@ BasicBlock
Various leaf nodes.
LLVM_ABI Function * getDeclarationIfExists(const Module *M, ID id)
Look up the Function declaration of the intrinsic id in the Module M and return it if it exists.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
auto m_BasicBlock()
Match an arbitrary basic block value and ignore it.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
auto m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
match_bind< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
brc_match< Cond_t, match_bind< BasicBlock >, match_bind< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
bind_cst_ty m_scev_APInt(const APInt *&C)
Match an SCEV constant and bind it to an APInt.
cst_pred_ty< is_all_ones > m_scev_AllOnes()
Match an integer with all bits set.
SCEVUnaryExpr_match< SCEVZeroExtendExpr, Op0_t > m_scev_ZExt(const Op0_t &Op0)
is_undef_or_poison m_scev_UndefOrPoison()
Match an SCEVUnknown wrapping undef or poison.
cst_pred_ty< is_one > m_scev_One()
Match an integer 1.
specificloop_ty m_SpecificLoop(const Loop *L)
SCEVUnaryExpr_match< SCEVSignExtendExpr, Op0_t > m_scev_SExt(const Op0_t &Op0)
match_bind< const SCEVMulExpr > m_scev_Mul(const SCEVMulExpr *&V)
cst_pred_ty< is_zero > m_scev_Zero()
Match an integer 0.
SCEVUnaryExpr_match< SCEVTruncateExpr, Op0_t > m_scev_Trunc(const Op0_t &Op0)
bool match(const SCEV *S, const Pattern &P)
SCEVBinaryExpr_match< SCEVUDivExpr, Op0_t, Op1_t > m_scev_UDiv(const Op0_t &Op0, const Op1_t &Op1)
specificscev_ty m_scev_Specific(const SCEV *S)
Match if we have a specific specified SCEV.
SCEVAffineAddRec_match< Op0_t, Op1_t, match_isa< const Loop > > m_scev_AffineAddRec(const Op0_t &Op0, const Op1_t &Op1)
match_bind< const SCEVUnknown > m_SCEVUnknown(const SCEVUnknown *&V)
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagNUW, true > m_scev_c_NUWMul(const Op0_t &Op0, const Op1_t &Op1)
match_bind< const SCEVAddExpr > m_scev_Add(const SCEVAddExpr *&V)
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagAnyWrap, true > m_scev_c_Mul(const Op0_t &Op0, const Op1_t &Op1)
SCEVBinaryExpr_match< SCEVSMaxExpr, Op0_t, Op1_t > m_scev_SMax(const Op0_t &Op0, const Op1_t &Op1)
SCEVURem_match< Op0_t, Op1_t > m_scev_URem(Op0_t LHS, Op1_t RHS, ScalarEvolution &SE)
Match the mathematical pattern A - (A / B) * B, where A and B can be arbitrary expressions.
@ Valid
The data is already valid.
initializer< Ty > init(const Ty &Val)
LocationClass< Ty > location(Ty &L)
@ Switch
The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...
NodeAddr< PhiNode * > Phi
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt gcd(const DynamicAPInt &A, const DynamicAPInt &B)
void stable_sort(R &&Range)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
SaveAndRestore(T &) -> SaveAndRestore< T >
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)
LLVM_ABI bool canCreatePoison(const Operator *Op, bool ConsiderFlagsAndMetadata=true)
LLVM_ABI bool mustTriggerUB(const Instruction *I, const SmallPtrSetImpl< const Value * > &KnownPoison)
Return true if the given instruction must trigger undefined behavior when I is executed with any oper...
RelativeUniformCounterPtr Values
@ Known
Known to have no common set bits.
LLVM_ABI bool canConstantFoldCallTo(const CallBase *Call, const Function *F)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
InterleavedRange< Range > interleaved(const Range &R, StringRef Separator=", ", StringRef Prefix="", StringRef Suffix="")
Output range R as a sequence of interleaved elements.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
auto successors(const MachineBasicBlock *BB)
scope_exit(Callable) -> scope_exit< Callable >
@ BinaryOp
One of the operands is a binary op.
@ Load
The value being inserted comes from a load (InsertElement only).
@ Store
The extracted value is stored (ExtractElement only).
constexpr from_range_t from_range
auto dyn_cast_if_present(const Y &Val)
dyn_cast_if_present<X> - Functionally identical to dyn_cast, except that a null (or none in the case ...
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
auto uninitialized_copy(R &&Src, IterTy Dst)
bool isa_and_nonnull(const Y &Val)
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO, const DominatorTree &DT)
Returns true if the arithmetic part of the WO 's result is used only along the paths control dependen...
DomTreeNodeBase< BasicBlock > DomTreeNode
LLVM_ABI bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step)
Attempt to match a simple first order recurrence cycle of the form: iv = phi Ty [Start,...
auto dyn_cast_or_null(const Y &Val)
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
iterator_range< pointee_iterator< WrappedIteratorT > > make_pointee_range(RangeT &&Range)
auto reverse(ContainerTy &&C)
LLVM_ABI bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
LLVM_ABI bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
LLVM_ABI bool isFinite(const Loop *L)
Return true if this loop can be assumed to run for a finite number of iterations.
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
unsigned short computeExpressionSize(ArrayRef< SCEVUse > Args)
LLVM_ABI bool programUndefinedIfPoison(const Instruction *Inst)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isPointerTy(const Type *T)
LLVM_ABI ConstantRange getVScaleRange(const Function *F, unsigned BitWidth)
Determine the possible constant range of vscale with the given bit width, based on the vscale_range f...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
LLVM_ABI bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)
Return true if the given value is known to be non-zero when defined.
constexpr T divideCeil(U Numerator, V Denominator)
Returns the integer ceil(Numerator / Denominator).
LLVM_ABI bool propagatesPoison(const Use &PoisonOp)
Return true if PoisonOp's user yields poison or raises UB if its operand PoisonOp is poison.
@ UMin
Unsigned integer min implemented in terms of select(cmp()).
@ Mul
Product of integers.
@ SMax
Signed integer max implemented in terms of select(cmp()).
@ SMin
Signed integer min implemented in terms of select(cmp()).
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
DWARFExpression::Operation Op
auto max_element(R &&Range)
Provide wrappers to std::max_element which take ranges instead of having to pass begin/end explicitly...
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
ArrayRef(const T &OneElt) -> ArrayRef< T >
LLVM_ABI unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Return the number of times the sign bit of the register is replicated into the other bits.
constexpr unsigned BitWidth
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
constexpr bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
iterator_range< df_iterator< T > > depth_first(const T &G)
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be poison, but may be undef.
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
SCEVUseT< const SCEV * > SCEVUse
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
Implement std::hash so that hash_code can be used in STL containers.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
A special type used by analysis passes to provide an address that identifies that particular analysis...
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
static LLVM_ABI KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for ashr(LHS, RHS).
static LLVM_ABI KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for lshr(LHS, RHS).
static LLVM_ABI KnownBits shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW=false, bool NSW=false, bool ShAmtNonZero=false)
Compute known bits for shl(LHS, RHS).
An object of this class is returned by queries that could not be answered.
LLVM_ABI SCEVCouldNotCompute()
static LLVM_ABI bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This class defines a simple visitor class that may be used for various SCEV analysis purposes.
A utility class that uses RAII to save and restore the value of a variable.
Information about the number of loop iterations for which a loop exit's branch condition evaluates to...
LLVM_ABI ExitLimit(const SCEV *E)
Construct either an exact exit limit from a constant, or an unknown one from a SCEVCouldNotCompute.
const SCEV * ExactNotTaken
const SCEV * SymbolicMaxNotTaken
SmallVector< const SCEVPredicate *, 4 > Predicates
A vector of predicate guards for this ExitLimit.
const SCEV * ConstantMaxNotTaken