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!");
1711 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1715 UniqueSCEVs.InsertNode(S, IP);
1725 const SCEV *
X = ST->getOperand();
1739 if (AR->isAffine()) {
1740 const SCEV *Start = AR->getStart();
1741 const SCEV *Step = AR->getStepRecurrence(*
this);
1743 const Loop *L = AR->getLoop();
1747 if (AR->hasNoUnsignedWrap()) {
1768 const SCEV *CastedMaxBECount =
1772 if (MaxBECount == RecastedMaxBECount) {
1782 const SCEV *WideMaxBECount =
1784 const SCEV *OperandExtendedAdd =
1790 if (ZAdd == OperandExtendedAdd) {
1801 OperandExtendedAdd =
1807 if (ZAdd == OperandExtendedAdd) {
1828 !AC.assumptions().empty()) {
1830 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1832 if (AR->hasNoUnsignedWrap()) {
1867 const APInt &
C = SC->getAPInt();
1871 const SCEV *SResidual =
1879 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1904 if (SA->hasNoUnsignedWrap()) {
1917 if (SA->hasNoSignedWrap() &&
1920 C->isNegative() && !
C->isMinSignedValue() && C2->
sge(
C->abs())) {
1939 const SCEV *SResidual =
1950 if (
SM->hasNoUnsignedWrap()) {
1972 const SCEV *TruncRHS;
2009 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
2012 UniqueSCEVs.InsertNode(S, IP);
2021 "This is not an extending conversion!");
2023 "This is not a conversion to a SCEVable type!");
2024 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
2028 if (
const SCEV *S = FoldCache.lookup(
ID))
2040 "This is not an extending conversion!");
2042 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
2064 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
2069 UniqueSCEVs.InsertNode(S, IP);
2079 const SCEV *
X = ST->getOperand();
2090 if (SA->hasNoSignedWrap()) {
2112 const SCEV *SResidual =
2125 if (AR->isAffine()) {
2126 const SCEV *Start = AR->getStart();
2127 const SCEV *Step = AR->getStepRecurrence(*
this);
2129 const Loop *L = AR->getLoop();
2133 if (AR->hasNoSignedWrap()) {
2155 const SCEV *CastedMaxBECount =
2159 if (MaxBECount == RecastedMaxBECount) {
2169 const SCEV *WideMaxBECount =
2171 const SCEV *OperandExtendedAdd =
2177 if (SAdd == OperandExtendedAdd) {
2188 OperandExtendedAdd =
2194 if (SAdd == OperandExtendedAdd) {
2214 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2216 if (AR->hasNoSignedWrap()) {
2231 const APInt &
C = SC->getAPInt();
2235 const SCEV *SResidual =
2243 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2271 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
2274 UniqueSCEVs.InsertNode(S, IP);
2301 "This is not an extending conversion!");
2303 "This is not a conversion to a SCEVable type!");
2308 if (SC->getAPInt().isNegative())
2313 const SCEV *NewOp =
T->getOperand();
2332 for (
const SCEV *
Op : AR->operands())
2370 APInt &AccumulatedConstant,
2374 bool Interesting =
false;
2381 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2383 AccumulatedConstant += Scale *
C->getAPInt();
2388 for (; i !=
Ops.size(); ++i) {
2397 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2403 auto Pair = M.insert({
Key, NewScale});
2407 Pair.first->second += NewScale;
2415 auto Pair = M.insert({
Ops[i], Scale});
2419 Pair.first->second += Scale;
2438 case Instruction::Add:
2441 case Instruction::Sub:
2444 case Instruction::Mul:
2458 const SCEV *
A = (this->*Extension)(
2460 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2461 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2469 if (BinOp == Instruction::Mul)
2475 APInt C = RHSC->getAPInt();
2476 unsigned NumBits =
C.getBitWidth();
2477 bool IsSub = (BinOp == Instruction::Sub);
2478 bool IsNegativeConst = (
Signed &&
C.isNegative());
2480 bool OverflowDown = IsSub ^ IsNegativeConst;
2482 if (IsNegativeConst) {
2495 APInt Limit = Min + Magnitude;
2501 APInt Limit = Max - Magnitude;
2506std::optional<SCEV::NoWrapFlags>
2511 return std::nullopt;
2520 bool Deduced =
false;
2522 if (OBO->
getOpcode() != Instruction::Add &&
2525 return std::nullopt;
2534 false, LHS, RHS, CtxI)) {
2541 true, LHS, RHS, CtxI)) {
2548 return std::nullopt;
2558 using namespace std::placeholders;
2565 assert(CanAnalyze &&
"don't call from other places!");
2572 auto IsKnownNonNegative = [&](
SCEVUse U) {
2581 if (SignOrUnsignWrap != SignOrUnsignMask &&
2588 return Instruction::Add;
2590 return Instruction::Mul;
2601 Opcode,
C, OBO::NoSignedWrap);
2609 Opcode,
C, OBO::NoUnsignedWrap);
2619 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2626 if (UDiv->getOperand(1) ==
Ops[1])
2629 if (UDiv->getOperand(1) ==
Ops[0])
2645 "only nuw or nsw allowed");
2646 assert(!
Ops.empty() &&
"Cannot get empty add!");
2647 if (
Ops.size() == 1)
return Ops[0];
2650 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2652 "SCEVAddExpr operand types don't match!");
2654 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2655 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2660 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2661 [](
const APInt &
C) {
return C.isZero(); },
2662 [](
const APInt &
C) {
return false; });
2675 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2680 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2681 Add->setNoWrapFlags(ComputeFlags(
Ops));
2689 bool FoundMatch =
false;
2690 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2691 if (
Ops[i] ==
Ops[i+1]) {
2703 --i; e -=
Count - 1;
2713 auto FindTruncSrcType = [&]() ->
Type * {
2719 return T->getOperand()->getType();
2721 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2723 return T->getOperand()->getType();
2727 if (
auto *SrcType = FindTruncSrcType()) {
2734 if (
T->getOperand()->getType() != SrcType) {
2743 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2746 if (
T->getOperand()->getType() != SrcType) {
2774 if (
Ops.size() == 2) {
2784 auto C2 =
C->getAPInt();
2787 APInt ConstAdd = C1 + C2;
2788 auto AddFlags = AddExpr->getNoWrapFlags();
2829 if (
Ops.size() == 2 &&
2840 if (Idx <
Ops.size()) {
2841 bool DeletedAdd =
false;
2852 Ops.erase(
Ops.begin()+Idx);
2855 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2878 struct APIntCompare {
2879 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2880 return LHS.ult(RHS);
2887 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2888 for (
const SCEV *NewOp : NewOps)
2889 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2892 if (AccumulatedConstant != 0)
2894 for (
auto &MulOp : MulOpLists) {
2895 if (MulOp.first == 1) {
2897 }
else if (MulOp.first != 0) {
2906 if (
Ops.size() == 1)
2915 if (M->getNumOperands() == 2)
2916 return M->getOperand(
OpIdx == 0);
2927 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2931 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2939 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp) {
2940 if (MulOpSCEV ==
Ops[AddOp]) {
2951 for (
unsigned OMulOp = 0, OE = OtherMul->
getNumOperands(); OMulOp != OE;
2953 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2955 Cofactors.
push_back(StripFactor(OtherMul, OMulOp));
2964 if (!Cofactors.
empty()) {
2972 if (
Ops.size() == DeadIndices.
size() + 1)
2979 Ops.erase(
Ops.begin() + Idx);
2983 Ops.push_back(OuterMul);
3002 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3005 Ops.erase(
Ops.begin()+i);
3010 if (!LIOps.
empty()) {
3035 auto *DefI = getDefiningScopeBound(LIOps);
3037 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
3049 if (
Ops.size() == 1)
return NewRec;
3052 for (
unsigned i = 0;; ++i)
3053 if (
Ops[i] == AddRec) {
3063 for (
unsigned OtherIdx = Idx+1;
3071 "AddRecExprs are not sorted in reverse dominance order?");
3078 if (OtherAddRec->getLoop() == AddRecLoop) {
3079 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
3081 if (i >= AddRecOps.
size()) {
3082 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
3086 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
3089 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3104 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
3115 static_cast<SCEVAddExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3119 S =
new (SCEVAllocator)
3121 UniqueSCEVs.InsertNode(S, IP);
3132 FoldingSetNodeID
ID;
3134 for (
const SCEV *
Op :
Ops)
3139 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3143 S =
new (SCEVAllocator)
3144 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3145 UniqueSCEVs.InsertNode(S, IP);
3147 LoopUsers[
L].push_back(S);
3156 FoldingSetNodeID
ID;
3158 for (
const SCEV *
Op :
Ops)
3162 static_cast<SCEVMulExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3166 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3168 UniqueSCEVs.InsertNode(S, IP);
3178 if (j > 1 && k / j != i) Overflow =
true;
3194 if (n == 0 || n == k)
return 1;
3195 if (k > n)
return 0;
3201 for (
uint64_t i = 1; i <= k; ++i) {
3202 r =
umul_ov(r, n-(i-1), Overflow);
3211 struct FindConstantInAddMulChain {
3212 bool FoundConstant =
false;
3214 bool follow(
const SCEV *S) {
3219 bool isDone()
const {
3220 return FoundConstant;
3224 FindConstantInAddMulChain
F;
3226 ST.visitAll(StartExpr);
3227 return F.FoundConstant;
3235 "only nuw or nsw allowed");
3236 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3237 if (
Ops.size() == 1)
return Ops[0];
3239 Type *ETy =
Ops[0]->getType();
3241 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3243 "SCEVMulExpr operand types don't match!");
3248 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3249 [](
const APInt &
C) {
return C.isOne(); },
3250 [](
const APInt &
C) {
return C.isZero(); });
3261 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3266 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3267 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3272 if (
Ops.size() == 2) {
3280 const SCEV *Op0, *Op1;
3288 if (
Ops[0]->isAllOnesValue()) {
3293 bool AnyFolded =
false;
3294 for (
const SCEV *AddOp :
Add->operands()) {
3314 if (AddRec->hasNoSignedWrap()) {
3321 AddRec->getNoWrapFlags(FlagsMask));
3344 APInt C1V = LHSC->getAPInt();
3354 const SCEV *NewMul =
nullptr;
3358 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3373 if (Idx <
Ops.size()) {
3374 bool DeletedMul =
false;
3380 Ops.erase(
Ops.begin()+Idx);
3404 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3407 Ops.erase(
Ops.begin()+i);
3412 if (!LIOps.
empty()) {
3425 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3441 if (
Ops.size() == 1)
return NewRec;
3444 for (
unsigned i = 0;; ++i)
3445 if (
Ops[i] == AddRec) {
3466 bool OpsModified =
false;
3467 for (
unsigned OtherIdx = Idx+1;
3481 bool Overflow =
false;
3488 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3492 z < ze && !Overflow; ++z) {
3495 if (LargerThan64Bits)
3496 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3498 Coeff = Coeff1*Coeff2;
3513 if (
Ops.size() == 2)
return NewAddRec;
3514 Ops[Idx] = NewAddRec;
3515 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3531 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3538 "SCEVURemExpr operand types don't match!");
3543 if (RHSC->getValue()->isOne())
3544 return getZero(LHS->getType());
3547 if (RHSC->getAPInt().isPowerOf2()) {
3548 Type *FullTy = LHS->getType();
3564 assert(!LHS->getType()->isPointerTy() &&
3565 "SCEVUDivExpr operand can't be pointer!");
3566 assert(LHS->getType() == RHS->getType() &&
3567 "SCEVUDivExpr operand types don't match!");
3574 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3582 if (RHSC->getValue()->isOne())
3587 if (!RHSC->getValue()->isZero()) {
3591 Type *Ty = LHS->getType();
3592 unsigned LZ = RHSC->getAPInt().countl_zero();
3596 if (!RHSC->getAPInt().isPowerOf2())
3604 const APInt &StepInt = Step->getAPInt();
3605 const APInt &DivInt = RHSC->getAPInt();
3606 if (!StepInt.
urem(DivInt) &&
3612 for (
const SCEV *
Op : AR->operands())
3618 const APInt *StartRem;
3631 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3635 const SCEV *NewStart =
3637 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3639 const SCEV *NewLHS =
3642 if (LHS != NewLHS) {
3652 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3661 for (
const SCEV *
Op : M->operands())
3665 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3666 const SCEV *
Op = M->getOperand(i);
3693 if (
auto *DivisorConstant =
3695 bool Overflow =
false;
3697 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3708 for (
const SCEV *
Op :
A->operands())
3712 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3719 if (Operands.
size() ==
A->getNumOperands())
3731 const APInt &
N = RHSC->getAPInt();
3732 const APInt *NMinusM, *M;
3736 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3737 *NMinusM ==
N - *M) {
3746 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3756 return getZero(LHS->getType());
3760 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3761 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3762 if (
Mul->getOperand(i) == RHS) {
3773 const SCEV *NewLHS, *NewRHS;
3781 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
3784 UniqueSCEVs.InsertNode(S, IP);
3821 if (StepChrec->getLoop() == L) {
3835 if (Operands.
size() == 1)
return Operands[0];
3840 "SCEVAddRecExpr operand types don't match!");
3841 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3843 for (
const SCEV *
Op : Operands)
3845 "SCEVAddRecExpr operand is not available at loop entry!");
3848 if (Operands.
back()->isZero()) {
3863 const Loop *NestedLoop = NestedAR->getLoop();
3864 if (L->contains(NestedLoop)
3867 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3869 Operands[0] = NestedAR->getStart();
3873 bool AllInvariant =
all_of(
3885 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3896 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3900 Operands[0] = NestedAR;
3906 return getOrCreateAddRecExpr(Operands, L, Flags);
3922 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3926 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3940 bool FirstIter =
true;
3942 for (
SCEVUse IndexExpr : IndexExprs) {
3949 Offsets.push_back(FieldOffset);
3952 CurTy = STy->getTypeAtIndex(Index);
3957 "The first index of a GEP indexes a pointer");
3958 CurTy = SrcElementTy;
3969 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3970 Offsets.push_back(LocalOffset);
3975 if (Offsets.empty())
3988 "GEP should not change type mid-flight.");
3992SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3995 ID.AddInteger(SCEVType);
3999 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4002SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
4005 ID.AddInteger(SCEVType);
4009 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4019 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
4020 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4021 if (
Ops.size() == 1)
return Ops[0];
4024 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4026 "Operand types don't match!");
4029 "min/max should be consistently pointerish");
4055 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
4057 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
4062 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
4064 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
4070 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
4076 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
4081 if (Idx <
Ops.size()) {
4082 bool DeletedAny =
false;
4083 while (
Ops[Idx]->getSCEVType() == Kind) {
4085 Ops.erase(
Ops.begin()+Idx);
4103 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
4104 if (
Ops[i] ==
Ops[i + 1] ||
4105 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
4108 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
4111 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
4114 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
4120 if (
Ops.size() == 1)
return Ops[0];
4122 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
4127 ID.AddInteger(Kind);
4131 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4133 return ExistingSCEV;
4136 SCEV *S =
new (SCEVAllocator)
4139 UniqueSCEVs.InsertNode(S, IP);
4147class SCEVSequentialMinMaxDeduplicatingVisitor final
4148 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4149 std::optional<const SCEV *>> {
4150 using RetVal = std::optional<const SCEV *>;
4158 bool canRecurseInto(
SCEVTypes Kind)
const {
4161 return RootKind == Kind || NonSequentialRootKind == Kind;
4164 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
4166 "Only for min/max expressions.");
4169 if (!canRecurseInto(Kind))
4179 return std::nullopt;
4186 RetVal
visit(
const SCEV *S) {
4188 if (!SeenOps.
insert(S).second)
4189 return std::nullopt;
4190 return Base::visit(S);
4194 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4196 : SE(SE), RootKind(RootKind),
4197 NonSequentialRootKind(
4198 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4202 SmallVectorImpl<SCEVUse> &NewOps) {
4207 for (
const SCEV *
Op : OrigOps) {
4212 Ops.emplace_back(*NewOp);
4216 NewOps = std::move(
Ops);
4220 RetVal visitConstant(
const SCEVConstant *Constant) {
return Constant; }
4222 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4224 RetVal visitPtrToAddrExpr(
const SCEVPtrToAddrExpr *Expr) {
return Expr; }
4226 RetVal visitPtrToIntExpr(
const SCEVPtrToIntExpr *Expr) {
return Expr; }
4228 RetVal visitTruncateExpr(
const SCEVTruncateExpr *Expr) {
return Expr; }
4230 RetVal visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
return Expr; }
4232 RetVal visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
return Expr; }
4234 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4236 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4238 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4240 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4242 RetVal visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
4243 return visitAnyMinMaxExpr(Expr);
4246 RetVal visitUMaxExpr(
const SCEVUMaxExpr *Expr) {
4247 return visitAnyMinMaxExpr(Expr);
4250 RetVal visitSMinExpr(
const SCEVSMinExpr *Expr) {
4251 return visitAnyMinMaxExpr(Expr);
4254 RetVal visitUMinExpr(
const SCEVUMinExpr *Expr) {
4255 return visitAnyMinMaxExpr(Expr);
4258 RetVal visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *Expr) {
4259 return visitAnyMinMaxExpr(Expr);
4262 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4264 RetVal visitCouldNotCompute(
const SCEVCouldNotCompute *Expr) {
return Expr; }
4307struct SCEVPoisonCollector {
4308 bool LookThroughMaybePoisonBlocking;
4309 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4310 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4311 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4313 bool follow(
const SCEV *S) {
4314 if (!LookThroughMaybePoisonBlocking &&
4324 bool isDone()
const {
return false; }
4334 SCEVPoisonCollector PC1(
true);
4339 if (PC1.MaybePoison.empty())
4345 SCEVPoisonCollector PC2(
false);
4355 SCEVPoisonCollector PC(
false);
4378 while (!Worklist.
empty()) {
4380 if (!Visited.
insert(V).second)
4384 if (Visited.
size() > 16)
4400 if (PDI->isDisjoint())
4407 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4414 if (
I->hasPoisonGeneratingAnnotations())
4425 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4426 "Not a SCEVSequentialMinMaxExpr!");
4427 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4428 if (
Ops.size() == 1)
4432 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4434 "Operand types don't match!");
4437 "min/max should be consistently pointerish");
4445 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4452 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4462 bool DeletedAny =
false;
4463 while (Idx <
Ops.size()) {
4464 if (
Ops[Idx]->getSCEVType() != Kind) {
4469 Ops.erase(
Ops.begin() + Idx);
4470 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4471 SMME->operands().end());
4479 const SCEV *SaturationPoint;
4490 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4491 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4503 Ops.erase(
Ops.begin() + i);
4508 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4509 Ops.erase(
Ops.begin() + i);
4517 ID.AddInteger(Kind);
4521 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4523 return ExistingSCEV;
4527 SCEV *S =
new (SCEVAllocator)
4530 UniqueSCEVs.InsertNode(S, IP);
4578 if (
Size.isScalable())
4599 "Cannot get offset for structure containing scalable vector types");
4613 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP)) {
4615 "Stale SCEVUnknown in uniquing map!");
4621 UniqueSCEVs.InsertNode(S, IP);
4636 return Ty->isIntOrPtrTy();
4643 if (Ty->isPointerTy())
4654 if (Ty->isIntegerTy())
4658 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4670 bool PreciseA, PreciseB;
4671 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4672 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4673 if (!PreciseA || !PreciseB)
4676 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4677 DT.dominates(ScopeB, ScopeA);
4681 return CouldNotCompute.get();
4684bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4687 return SU && SU->getValue() ==
nullptr;
4690 return !ContainsNulls;
4695 if (
I != HasRecMap.end())
4700 HasRecMap.insert({S, FoundAddRec});
4708 if (
SI == ExprValueMap.
end())
4710 return SI->second.getArrayRef();
4716void ScalarEvolution::eraseValueFromMap(
Value *V) {
4718 if (
I != ValueExprMap.end()) {
4719 auto EVIt = ExprValueMap.find(
I->second);
4720 bool Removed = EVIt->second.remove(V);
4722 assert(Removed &&
"Value not in ExprValueMap?");
4723 ValueExprMap.erase(
I);
4727void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4731 auto It = ValueExprMap.find_as(V);
4732 if (It == ValueExprMap.end()) {
4734 ExprValueMap[S].insert(V);
4745 return createSCEVIter(V);
4752 if (
I != ValueExprMap.end()) {
4753 const SCEV *S =
I->second;
4754 assert(checkValidity(S) &&
4755 "existing SCEV has not been properly invalidated");
4768 Type *Ty = V->getType();
4784 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4797 return (
const SCEV *)
nullptr;
4803 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4807 Type *Ty = V->getType();
4813 assert(
P->getType()->isPointerTy());
4828 if (AddOp->getType()->isPointerTy()) {
4829 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4847 return getZero(LHS->getType());
4852 if (RHS->getType()->isPointerTy()) {
4853 if (!LHS->getType()->isPointerTy() ||
4863 const bool RHSIsNotMinSigned =
4894 Type *SrcTy = V->getType();
4895 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4896 "Cannot truncate or zero extend with non-integer arguments!");
4906 Type *SrcTy = V->getType();
4907 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4908 "Cannot truncate or zero extend with non-integer arguments!");
4918 Type *SrcTy = V->getType();
4919 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4920 "Cannot noop or zero extend with non-integer arguments!");
4922 "getNoopOrZeroExtend cannot truncate!");
4930 Type *SrcTy = V->getType();
4931 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4932 "Cannot noop or sign extend with non-integer arguments!");
4934 "getNoopOrSignExtend cannot truncate!");
4942 Type *SrcTy = V->getType();
4943 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4944 "Cannot noop or any extend with non-integer arguments!");
4946 "getNoopOrAnyExtend cannot truncate!");
4954 Type *SrcTy = V->getType();
4955 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4956 "Cannot truncate or noop with non-integer arguments!");
4958 "getTruncateOrNoop cannot extend!");
4966 const SCEV *PromotedLHS = LHS;
4967 const SCEV *PromotedRHS = RHS;
4987 assert(!
Ops.empty() &&
"At least one operand must be!");
4989 if (
Ops.size() == 1)
4993 Type *MaxType =
nullptr;
4999 assert(MaxType &&
"Failed to find maximum type!");
5012 if (!V->getType()->isPointerTy())
5017 V = AddRec->getStart();
5019 const SCEV *PtrOp =
nullptr;
5020 for (
const SCEV *AddOp :
Add->operands()) {
5021 if (AddOp->getType()->isPointerTy()) {
5022 assert(!PtrOp &&
"Cannot have multiple pointer ops");
5026 assert(PtrOp &&
"Must have pointer op");
5038 for (
User *U :
I->users()) {
5040 if (Visited.
insert(UserInsn).second)
5054 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
5055 bool IgnoreOtherLoops =
true) {
5058 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
5060 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
5065 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5067 SeenLoopVariantSCEVUnknown =
true;
5071 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5075 SeenOtherLoops =
true;
5079 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
5081 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
5084 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
5085 : SCEVRewriteVisitor(SE),
L(
L) {}
5088 bool SeenLoopVariantSCEVUnknown =
false;
5089 bool SeenOtherLoops =
false;
5098 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
5099 SCEVPostIncRewriter
Rewriter(L, SE);
5101 return Rewriter.hasSeenLoopVariantSCEVUnknown()
5106 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5108 SeenLoopVariantSCEVUnknown =
true;
5112 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5116 SeenOtherLoops =
true;
5120 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
5122 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
5125 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
5126 : SCEVRewriteVisitor(SE),
L(
L) {}
5129 bool SeenLoopVariantSCEVUnknown =
false;
5130 bool SeenOtherLoops =
false;
5136class SCEVBackedgeConditionFolder
5139 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5140 ScalarEvolution &SE) {
5141 bool IsPosBECond =
false;
5142 Value *BECond =
nullptr;
5143 if (BasicBlock *Latch =
L->getLoopLatch()) {
5145 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
5146 "Both outgoing branches should not target same header!");
5147 BECond = BI->getCondition();
5148 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
5153 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
5157 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5158 const SCEV *
Result = Expr;
5163 switch (
I->getOpcode()) {
5164 case Instruction::Select: {
5166 std::optional<const SCEV *> Res =
5167 compareWithBackedgeCondition(
SI->getCondition());
5175 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5186 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5187 bool IsPosBECond, ScalarEvolution &SE)
5188 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5189 IsPositiveBECond(IsPosBECond) {}
5191 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5195 Value *BackedgeCond =
nullptr;
5197 bool IsPositiveBECond;
5200std::optional<const SCEV *>
5201SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5206 if (BackedgeCond == IC)
5209 return std::nullopt;
5214 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5215 ScalarEvolution &SE) {
5221 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5228 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5238 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5239 : SCEVRewriteVisitor(SE),
L(
L) {}
5247void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5263 const APInt &BECountAP = BECountMax->getAPInt();
5264 unsigned NoOverflowBitWidth =
5273ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5283 if (!SignedWrapViaInductionTried.insert(AR).second)
5308 AC.assumptions().empty())
5316 const SCEV *OverflowLimit =
5318 if (OverflowLimit &&
5326ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5336 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5362 AC.assumptions().empty())
5397 explicit BinaryOp(Operator *
Op)
5398 : Opcode(
Op->getOpcode()),
LHS(
Op->getOperand(0)),
RHS(
Op->getOperand(1)),
5401 IsNSW = OBO->hasNoSignedWrap();
5402 IsNUW = OBO->hasNoUnsignedWrap();
5406 explicit BinaryOp(
unsigned Opcode,
Value *
LHS,
Value *
RHS,
bool IsNSW =
false,
5408 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5420 return std::nullopt;
5426 switch (
Op->getOpcode()) {
5427 case Instruction::Add:
5428 case Instruction::Sub:
5429 case Instruction::Mul:
5430 case Instruction::UDiv:
5431 case Instruction::URem:
5432 case Instruction::And:
5433 case Instruction::AShr:
5434 case Instruction::Shl:
5435 return BinaryOp(
Op);
5437 case Instruction::Or: {
5440 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5447 return BinaryOp(
Op);
5450 case Instruction::Xor:
5454 if (RHSC->getValue().isSignMask())
5455 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5457 if (V->getType()->isIntegerTy(1))
5458 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5459 return BinaryOp(
Op);
5461 case Instruction::LShr:
5470 if (SA->getValue().ult(
BitWidth)) {
5472 ConstantInt::get(SA->getContext(),
5474 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5477 return BinaryOp(
Op);
5479 case Instruction::ExtractValue: {
5481 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5489 bool Signed = WO->isSigned();
5492 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5497 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5508 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5509 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5511 return std::nullopt;
5537 if (
Op == SymbolicPHI)
5542 if (SourceBits != NewBits)
5560 if (!L || L->getHeader() != PN->
getParent())
5618std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5619ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5627 assert(L &&
"Expecting an integer loop header phi");
5632 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5633 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5634 Value *
V = PN->getIncomingValue(i);
5635 if (
L->contains(PN->getIncomingBlock(i))) {
5638 }
else if (BEValueV != V) {
5642 }
else if (!StartValueV) {
5644 }
else if (StartValueV != V) {
5645 StartValueV =
nullptr;
5649 if (!BEValueV || !StartValueV)
5650 return std::nullopt;
5652 const SCEV *BEValue =
getSCEV(BEValueV);
5659 return std::nullopt;
5663 unsigned FoundIndex =
Add->getNumOperands();
5664 Type *TruncTy =
nullptr;
5666 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5669 if (FoundIndex == e) {
5674 if (FoundIndex ==
Add->getNumOperands())
5675 return std::nullopt;
5679 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5680 if (i != FoundIndex)
5681 Ops.push_back(
Add->getOperand(i));
5687 return std::nullopt;
5740 const SCEV *StartVal =
getSCEV(StartValueV);
5741 const SCEV *PHISCEV =
5768 auto getExtendedExpr = [&](
const SCEV *Expr,
5769 bool CreateSignExtend) ->
const SCEV * {
5772 const SCEV *ExtendedExpr =
5775 return ExtendedExpr;
5783 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5784 const SCEV *ExtendedExpr) ->
bool {
5785 return Expr != ExtendedExpr &&
5789 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5790 if (PredIsKnownFalse(StartVal, StartExtended)) {
5792 return std::nullopt;
5797 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5798 if (PredIsKnownFalse(Accum, AccumExtended)) {
5800 return std::nullopt;
5803 auto AppendPredicate = [&](
const SCEV *Expr,
5804 const SCEV *ExtendedExpr) ->
void {
5805 if (Expr != ExtendedExpr &&
5813 AppendPredicate(StartVal, StartExtended);
5814 AppendPredicate(Accum, AccumExtended);
5822 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5823 std::make_pair(NewAR, Predicates);
5825 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5829std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5834 return std::nullopt;
5837 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5838 if (
I != PredicatedSCEVRewrites.end()) {
5839 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5842 if (Rewrite.first == SymbolicPHI)
5843 return std::nullopt;
5847 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5851 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5852 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5857 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5858 return std::nullopt;
5878 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5879 if (Expr1 != Expr2 &&
5880 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5881 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5898const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5900 Value *StartValueV) {
5903 assert(BEValueV && StartValueV);
5909 if (BO->Opcode != Instruction::Add)
5912 const SCEV *Accum =
nullptr;
5913 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5915 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5929 insertValueToMap(PN, PHISCEV);
5932 inferNoWrapViaConstantRanges(AR);
5939 "Accum is defined outside L, but is not invariant?");
5940 if (isAddRecNeverPoison(BEInst, L))
5947const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5948 const Loop *
L = LI.getLoopFor(PN->
getParent());
5955 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5961 }
else if (BEValueV != V) {
5965 }
else if (!StartValueV) {
5967 }
else if (StartValueV != V) {
5968 StartValueV =
nullptr;
5972 if (!BEValueV || !StartValueV)
5975 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5976 "PHI node already processed?");
5980 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5985 insertValueToMap(PN, SymbolicName);
5989 const SCEV *BEValue =
getSCEV(BEValueV);
5999 unsigned FoundIndex =
Add->getNumOperands();
6000 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
6001 if (
Add->getOperand(i) == SymbolicName)
6002 if (FoundIndex == e) {
6007 if (FoundIndex !=
Add->getNumOperands()) {
6010 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
6011 if (i != FoundIndex)
6012 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
6024 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
6031 if (
GEP->getOperand(0) == PN) {
6032 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
6050 const SCEV *StartVal =
getSCEV(StartValueV);
6051 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
6056 forgetMemoizedResults({SymbolicName});
6057 insertValueToMap(PN, PHISCEV);
6060 inferNoWrapViaConstantRanges(AR);
6084 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
6085 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
6087 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
6088 const SCEV *StartVal =
getSCEV(StartValueV);
6089 if (Start == StartVal) {
6093 forgetMemoizedResults({SymbolicName});
6094 insertValueToMap(PN, Shifted);
6104 eraseValueFromMap(PN);
6119 Use &LeftUse =
Merge->getOperandUse(0);
6120 Use &RightUse =
Merge->getOperandUse(1);
6156 assert(IDom &&
"At least the entry block should dominate PN");
6164const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
6169 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6186 CommonInst = IncomingInst;
6202ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6208 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6209 bool SCEVExprsIdentical =
6211 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6212 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6215const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6216 if (
const SCEV *S = createAddRecFromPHI(PN))
6226 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6229 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6238 struct FindClosure {
6239 const SCEV *OperandToFind;
6245 bool canRecurseInto(
SCEVTypes Kind)
const {
6248 return RootKind == Kind || NonSequentialRootKind == Kind ||
6253 : OperandToFind(OperandToFind), RootKind(RootKind),
6254 NonSequentialRootKind(
6258 bool follow(
const SCEV *S) {
6259 Found = S == OperandToFind;
6261 return !isDone() && canRecurseInto(S->
getSCEVType());
6264 bool isDone()
const {
return Found; }
6267 FindClosure FC(OperandToFind, RootKind);
6272std::optional<const SCEV *>
6273ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6283 switch (ICI->getPredicate()) {
6297 bool Signed = ICI->isSigned();
6298 const SCEV *LA =
getSCEV(TrueVal);
6306 if (LA == LS &&
RA == RS)
6308 if (LA == RS &&
RA == LS)
6311 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6312 if (
Op->getType()->isPointerTy()) {
6323 LS = CoerceOperand(LS);
6324 RS = CoerceOperand(RS);
6348 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6349 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6363 X = ZExt->getOperand();
6365 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6376 return std::nullopt;
6379static std::optional<const SCEV *>
6381 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6385 "Unexpected operands of a select.");
6397 return std::nullopt;
6412static std::optional<const SCEV *>
6416 return std::nullopt;
6419 const auto *SETrue = SE->
getSCEV(TrueVal);
6420 const auto *SEFalse = SE->
getSCEV(FalseVal);
6424const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6426 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6428 V->getType() ==
TrueVal->getType() &&
6429 "Types of select hands and of the result must match.");
6432 if (!
V->getType()->isIntegerTy(1))
6435 if (std::optional<const SCEV *> S =
6448 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6452 if (std::optional<const SCEV *> S =
6453 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6459 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6465 assert(
GEP->getSourceElementType()->isSized() &&
6466 "GEP source element type must be sized");
6469 for (
Value *Index :
GEP->indices())
6474APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6477 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6480 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6482 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6485 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6504 return GetShiftedByZeros(TZ);
6514 return GetShiftedByZeros(TZ);
6518 if (
M->hasNoUnsignedWrap()) {
6521 for (
const SCEV *Operand :
M->operands().drop_front())
6529 for (
const SCEV *Operand :
M->operands())
6531 return GetShiftedByZeros(TZ);
6536 if (
N->hasNoUnsignedWrap())
6537 return GetGCDMultiple(
N);
6540 for (
const SCEV *Operand :
N->operands().drop_front())
6542 return GetShiftedByZeros(TZ);
6559 CtxI = &*F.getEntryBlock().begin();
6566 .allowEphemerals(
true))
6567 .countMinTrailingZeros();
6568 return GetShiftedByZeros(Known);
6581 return getConstantMultipleImpl(S, CtxI);
6583 auto I = ConstantMultipleCache.find(S);
6584 if (
I != ConstantMultipleCache.end())
6587 APInt Result = getConstantMultipleImpl(S, CtxI);
6588 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6589 assert(InsertPair.second &&
"Should insert a new key");
6590 return InsertPair.first->second;
6607 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6610 if (std::optional<ConstantRange>
Range = CB->getRange())
6614 if (std::optional<ConstantRange>
Range =
A->getRange())
6617 return std::nullopt;
6624 UnsignedRanges.erase(AddRec);
6625 SignedRanges.erase(AddRec);
6626 ConstantMultipleCache.erase(AddRec);
6631getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6657 Value *Start, *Step;
6664 assert(L && L->getHeader() ==
P->getParent());
6677 case Instruction::AShr:
6678 case Instruction::LShr:
6679 case Instruction::Shl:
6694 KnownStep.getBitWidth() ==
BitWidth);
6697 auto MaxShiftAmt = KnownStep.getMaxValue();
6699 bool Overflow =
false;
6700 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6707 case Instruction::AShr: {
6715 if (KnownStart.isNonNegative())
6718 KnownStart.getMaxValue() + 1);
6719 if (KnownStart.isNegative())
6722 KnownEnd.getMaxValue() + 1);
6725 case Instruction::LShr: {
6734 KnownStart.getMaxValue() + 1);
6736 case Instruction::Shl: {
6740 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6741 return ConstantRange(KnownStart.getMinValue(),
6742 KnownEnd.getMaxValue() + 1);
6767 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6774ScalarEvolution::getRangeRefIter(
const SCEV *S,
6775 ScalarEvolution::RangeSignHint SignHint) {
6776 DenseMap<const SCEV *, ConstantRange> &Cache =
6777 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6780 SmallPtrSet<const SCEV *, 8> Seen;
6784 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6785 if (!Seen.
insert(Expr).second)
6819 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6820 const SCEV *
P = WorkList[
I];
6824 for (
const SCEV *
Op :
P->operands())
6837 if (!WorkList.
empty()) {
6842 getRangeRef(
P, SignHint);
6846 return getRangeRef(S, SignHint, 0);
6853 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6854 DenseMap<const SCEV *, ConstantRange> &Cache =
6855 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6862 auto I = Cache.
find(S);
6863 if (
I != Cache.
end())
6867 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6872 return getRangeRefIter(S, SignHint);
6875 ConstantRange ConservativeResult(
BitWidth,
true);
6876 using OBO = OverflowingBinaryOperator;
6880 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6884 ConservativeResult =
6891 ConservativeResult = ConstantRange(
6907 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6914 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6921 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6927 return setRange(Cast, SignHint,
X);
6932 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6933 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6935 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6936 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6937 ConservativeResult =
6938 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6940 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6941 unsigned WrapType = OBO::AnyWrap;
6942 if (
Add->hasNoSignedWrap())
6943 WrapType |= OBO::NoSignedWrap;
6944 if (
Add->hasNoUnsignedWrap())
6945 WrapType |= OBO::NoUnsignedWrap;
6947 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6949 return setRange(
Add, SignHint,
6950 ConservativeResult.intersectWith(
X, RangeType));
6954 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6956 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6957 return setRange(
Mul, SignHint,
6958 ConservativeResult.intersectWith(
X, RangeType));
6962 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6963 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6964 return setRange(UDiv, SignHint,
6965 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6973 if (!UnsignedMinValue.
isZero())
6974 ConservativeResult = ConservativeResult.intersectWith(
6975 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6984 bool AllNonNeg =
true;
6985 bool AllNonPos =
true;
6986 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6993 ConservativeResult = ConservativeResult.intersectWith(
6998 ConservativeResult = ConservativeResult.intersectWith(
7007 const SCEV *MaxBEScev =
7021 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
7023 ConservativeResult =
7024 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
7027 auto RangeFromFactoring = getRangeViaFactoring(
7029 ConservativeResult =
7030 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
7036 const SCEV *SymbolicMaxBECount =
7041 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
7042 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
7043 ConservativeResult =
7044 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
7049 return setRange(AddRec, SignHint, std::move(ConservativeResult));
7059 ID = Intrinsic::umax;
7062 ID = Intrinsic::smax;
7066 ID = Intrinsic::umin;
7069 ID = Intrinsic::smin;
7076 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
7077 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
7079 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
7080 return setRange(S, SignHint,
7081 ConservativeResult.intersectWith(
X, RangeType));
7090 ConservativeResult =
7091 ConservativeResult.intersectWith(*MDRange, RangeType);
7096 auto CR = getRangeForUnknownRecurrence(U);
7097 ConservativeResult = ConservativeResult.intersectWith(CR);
7108 if (
U->getType()->isPointerTy()) {
7111 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
7112 int ptrIdxDiff = ptrSize -
BitWidth;
7113 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
7126 ConservativeResult = ConservativeResult.intersectWith(
7130 ConservativeResult = ConservativeResult.intersectWith(
7135 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
7139 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
7140 DL, CanBeNull,
nullptr);
7150 uint64_t
Align =
U->getValue()->getPointerAlignment(DL).value();
7151 uint64_t Rem = MaxVal.
urem(Align);
7156 ConservativeResult = ConservativeResult.intersectWith(
7166 return getRangeRef(AR, SignHint,
Depth + 1);
7170 ConstantRange RangeFromOps(
BitWidth,
false);
7172 for (
const auto &
Op :
Phi->operands()) {
7174 RangeFromOps = RangeFromOps.unionWith(OpRange);
7176 if (RangeFromOps.isFullSet())
7179 ConservativeResult =
7180 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7186 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7188 ConservativeResult = ConservativeResult.difference(Disallowed);
7191 return setRange(U, SignHint, std::move(ConservativeResult));
7197 return setRange(S, SignHint, std::move(ConservativeResult));
7205static std::pair<ConstantRange, bool>
7213 if (Step == 0 || MaxBECount == 0)
7214 return {StartRange,
true};
7220 return {ConstantRange::getFull(
BitWidth),
false};
7236 return {ConstantRange::getFull(
BitWidth),
false};
7249 APInt MovedBoundary;
7254 MovedBoundary = StartLower - std::move(
Offset);
7257 MovedBoundary = StartUpper + std::move(
Offset);
7261 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7268 if (StartRange.
contains(MovedBoundary))
7269 return {ConstantRange::getFull(
BitWidth),
false};
7272 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7274 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7282std::pair<ConstantRange, SCEV::NoWrapFlags>
7283ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7284 const APInt &MaxBECount) {
7288 "mismatched bit widths");
7297 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7299 StartSRange, MaxBECount,
7301 ConstantRange SR = SR1.unionWith(SR2);
7318ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7320 ScalarEvolution::RangeSignHint SignHint) {
7321 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7323 "This only works for non-self-wrapping AddRecs!");
7324 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7328 return ConstantRange::getFull(
BitWidth);
7336 return ConstantRange::getFull(
BitWidth);
7340 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7342 MaxItersWithoutWrap))
7343 return ConstantRange::getFull(
BitWidth);
7364 ConstantRange StartRange = getRangeRef(Start, SignHint);
7365 ConstantRange EndRange = getRangeRef(End, SignHint);
7366 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7370 return RangeBetween;
7375 return ConstantRange::getFull(
BitWidth);
7378 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7379 return RangeBetween;
7381 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7382 return RangeBetween;
7383 return ConstantRange::getFull(
BitWidth);
7388 const APInt &MaxBECount) {
7395 "mismatched bit widths");
7397 struct SelectPattern {
7398 Value *Condition =
nullptr;
7402 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7404 std::optional<unsigned> CastOp;
7418 CastOp = SCast->getSCEVType();
7419 S = SCast->getOperand();
7422 using namespace llvm::PatternMatch;
7429 Condition =
nullptr;
7461 bool isRecognized() {
return Condition !=
nullptr; }
7464 SelectPattern StartPattern(*
this,
BitWidth, Start);
7465 if (!StartPattern.isRecognized())
7466 return ConstantRange::getFull(
BitWidth);
7468 SelectPattern StepPattern(*
this,
BitWidth, Step);
7469 if (!StepPattern.isRecognized())
7470 return ConstantRange::getFull(
BitWidth);
7472 if (StartPattern.Condition != StepPattern.Condition) {
7476 return ConstantRange::getFull(
BitWidth);
7487 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7488 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7489 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7490 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7492 ConstantRange TrueRange =
7493 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7494 ConstantRange FalseRange =
7495 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7507 PDI && PDI->isDisjoint()) {
7522ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7535 SmallPtrSet<const SCEV *, 16> Visited;
7537 auto pushOp = [&](
const SCEV *S) {
7538 if (!Visited.
insert(S).second)
7541 if (Visited.
size() > 30) {
7552 while (!Worklist.
empty()) {
7554 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7555 if (!Bound || DT.dominates(Bound, DefI))
7562 return Bound ? Bound : &*F.getEntryBlock().begin();
7568 return getDefiningScopeBound(
Ops, Discard);
7571bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7573 if (
A->getParent() ==
B->getParent() &&
7578 auto *BLoop = LI.getLoopFor(
B->getParent());
7579 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7580 BLoop->getLoopPreheader() ==
A->getParent() &&
7582 A->getParent()->end()) &&
7590 SCEVPoisonCollector PC(
true);
7592 return PC.MaybePoison.empty();
7595bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7605bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7622 for (
const Use &
Op :
I->operands()) {
7628 auto *DefI = getDefiningScopeBound(SCEVOps);
7629 return isGuaranteedToTransferExecutionTo(DefI,
I);
7632bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7634 if (isSCEVExprNeverPoison(
I))
7645 auto *ExitingBB =
L->getExitingBlock();
7649 SmallPtrSet<const Value *, 16> KnownPoison;
7658 while (!Worklist.
empty()) {
7661 for (
const Use &U :
Poison->uses()) {
7664 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7668 if (KnownPoison.
insert(PoisonUser).second)
7676ScalarEvolution::LoopProperties
7677ScalarEvolution::getLoopProperties(
const Loop *L) {
7678 using LoopProperties = ScalarEvolution::LoopProperties;
7680 auto Itr = LoopPropertiesCache.find(L);
7681 if (Itr == LoopPropertiesCache.end()) {
7684 return !
SI->isSimple();
7694 return I->mayWriteToMemory();
7697 LoopProperties LP = {
true,
7700 for (
auto *BB :
L->getBlocks())
7701 for (
auto &
I : *BB) {
7703 LP.HasNoAbnormalExits =
false;
7704 if (HasSideEffects(&
I))
7705 LP.HasNoSideEffects =
false;
7706 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7710 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7711 assert(InsertPair.second &&
"We just checked!");
7712 Itr = InsertPair.first;
7725const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7731 Stack.emplace_back(V,
false);
7732 while (!Stack.empty()) {
7733 auto E = Stack.back();
7734 Value *CurV = E.getPointer();
7742 const SCEV *CreatedSCEV =
nullptr;
7745 CreatedSCEV = createSCEV(CurV);
7750 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7754 insertValueToMap(CurV, CreatedSCEV);
7757 Stack.back().setInt(
true);
7760 Stack.emplace_back(
Op,
false);
7777 if (!DT.isReachableFromEntry(
I->getParent()))
7790 switch (BO->Opcode) {
7791 case Instruction::Add:
7792 case Instruction::Mul: {
7799 Ops.push_back(BO->
Op);
7803 Ops.push_back(BO->RHS);
7807 (BO->Opcode == Instruction::Add &&
7808 (NewBO->Opcode != Instruction::Add &&
7809 NewBO->Opcode != Instruction::Sub)) ||
7810 (BO->Opcode == Instruction::Mul &&
7811 NewBO->Opcode != Instruction::Mul)) {
7812 Ops.push_back(BO->LHS);
7817 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7820 Ops.push_back(BO->LHS);
7828 case Instruction::Sub:
7829 case Instruction::UDiv:
7830 case Instruction::URem:
7832 case Instruction::AShr:
7833 case Instruction::Shl:
7834 case Instruction::Xor:
7838 case Instruction::And:
7839 case Instruction::Or:
7843 case Instruction::LShr:
7850 Ops.push_back(BO->LHS);
7851 Ops.push_back(BO->RHS);
7855 switch (
U->getOpcode()) {
7856 case Instruction::Trunc:
7857 case Instruction::ZExt:
7858 case Instruction::SExt:
7859 case Instruction::PtrToAddr:
7860 case Instruction::PtrToInt:
7861 Ops.push_back(
U->getOperand(0));
7864 case Instruction::BitCast:
7866 Ops.push_back(
U->getOperand(0));
7871 case Instruction::SDiv:
7872 case Instruction::SRem:
7873 Ops.push_back(
U->getOperand(0));
7874 Ops.push_back(
U->getOperand(1));
7877 case Instruction::GetElementPtr:
7879 "GEP source element type must be sized");
7883 case Instruction::IntToPtr:
7886 case Instruction::PHI:
7917 Ops.push_back(CondICmp->getOperand(0));
7918 Ops.push_back(CondICmp->getOperand(1));
7938 case Instruction::Select: {
7940 auto CanSimplifyToUnknown = [
this,
U]() {
7958 if (CanSimplifyToUnknown())
7965 case Instruction::Call:
7966 case Instruction::Invoke:
7973 switch (
II->getIntrinsicID()) {
7974 case Intrinsic::abs:
7975 Ops.push_back(
II->getArgOperand(0));
7977 case Intrinsic::umax:
7978 case Intrinsic::umin:
7979 case Intrinsic::smax:
7980 case Intrinsic::smin:
7981 case Intrinsic::usub_sat:
7982 case Intrinsic::uadd_sat:
7983 Ops.push_back(
II->getArgOperand(0));
7984 Ops.push_back(
II->getArgOperand(1));
7986 case Intrinsic::start_loop_iterations:
7987 case Intrinsic::annotation:
7988 case Intrinsic::ptr_annotation:
7989 Ops.push_back(
II->getArgOperand(0));
8001const SCEV *ScalarEvolution::createSCEV(
Value *V) {
8010 if (!DT.isReachableFromEntry(
I->getParent()))
8025 switch (BO->Opcode) {
8026 case Instruction::Add: {
8052 if (BO->Opcode == Instruction::Sub)
8060 if (BO->Opcode == Instruction::Sub)
8067 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
8068 NewBO->Opcode != Instruction::Sub)) {
8078 case Instruction::Mul: {
8099 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
8108 case Instruction::UDiv:
8112 case Instruction::URem:
8116 case Instruction::Sub: {
8119 Flags = getNoWrapFlagsFromUB(BO->
Op);
8124 case Instruction::And:
8130 if (CI->isMinusOne())
8132 const APInt &
A = CI->getValue();
8138 unsigned LZ =
A.countl_zero();
8139 unsigned TZ =
A.countr_zero();
8144 APInt EffectiveMask =
8146 if ((LZ != 0 || TZ != 0) && !((~
A & ~Known.
Zero) & EffectiveMask)) {
8149 const SCEV *ShiftedLHS =
nullptr;
8153 unsigned MulZeros = OpC->getAPInt().countr_zero();
8154 unsigned GCD = std::min(MulZeros, TZ);
8159 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8181 case Instruction::Or:
8190 case Instruction::Xor:
8193 if (CI->isMinusOne())
8202 if (LBO->getOpcode() == Instruction::And &&
8203 LCI->getValue() == CI->getValue())
8204 if (
const SCEVZeroExtendExpr *Z =
8207 const SCEV *Z0 =
Z->getOperand();
8214 if (CI->getValue().isMask(Z0TySize))
8220 APInt Trunc = CI->getValue().trunc(Z0TySize);
8229 case Instruction::Shl:
8247 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8256 ConstantInt *
X = ConstantInt::get(
8262 case Instruction::AShr:
8284 const SCEV *AddTruncateExpr =
nullptr;
8285 ConstantInt *ShlAmtCI =
nullptr;
8286 const SCEV *AddConstant =
nullptr;
8288 if (L &&
L->getOpcode() == Instruction::Add) {
8296 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8303 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8311 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8316 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8321 if (AddTruncateExpr && ShlAmtCI) {
8333 const APInt &ShlAmt = ShlAmtCI->
getValue();
8337 const SCEV *CompositeExpr =
8339 if (
L->getOpcode() != Instruction::Shl)
8340 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8349 switch (
U->getOpcode()) {
8350 case Instruction::Trunc:
8353 case Instruction::ZExt:
8356 case Instruction::SExt:
8366 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8367 Type *Ty =
U->getType();
8375 case Instruction::BitCast:
8381 case Instruction::PtrToAddr: {
8388 case Instruction::PtrToInt: {
8391 Type *DstIntTy =
U->getType();
8399 case Instruction::IntToPtr:
8403 case Instruction::SDiv:
8410 case Instruction::SRem:
8417 case Instruction::GetElementPtr:
8420 case Instruction::PHI:
8423 case Instruction::Select:
8424 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8427 case Instruction::Call:
8428 case Instruction::Invoke:
8433 switch (
II->getIntrinsicID()) {
8434 case Intrinsic::abs:
8438 case Intrinsic::umax:
8442 case Intrinsic::umin:
8446 case Intrinsic::smax:
8450 case Intrinsic::smin:
8454 case Intrinsic::usub_sat: {
8455 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8456 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8460 case Intrinsic::uadd_sat: {
8461 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8462 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8466 case Intrinsic::start_loop_iterations:
8467 case Intrinsic::annotation:
8468 case Intrinsic::ptr_annotation:
8472 case Intrinsic::vscale:
8492 auto *ExitCountType = ExitCount->
getType();
8493 assert(ExitCountType->isIntegerTy());
8495 1 + ExitCountType->getScalarSizeInBits());
8508 auto CanAddOneWithoutOverflow = [&]() {
8510 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8521 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8551 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8552 assert(L->isLoopExiting(ExitingBlock) &&
8553 "Exiting block must actually branch out of the loop!");
8562 const auto *MaxExitCount =
8570 L->getExitingBlocks(ExitingBlocks);
8572 std::optional<unsigned> Res;
8573 for (
auto *ExitingBB : ExitingBlocks) {
8577 Res = std::gcd(*Res, Multiple);
8579 return Res.value_or(1);
8583 const SCEV *ExitCount) {
8613 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8614 assert(L->isLoopExiting(ExitingBlock) &&
8615 "Exiting block must actually branch out of the loop!");
8625 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8627 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8629 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8639 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8642 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8645 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8653 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8660 return getBackedgeTakenInfo(L).getExact(L,
this);
8662 return getBackedgeTakenInfo(L).getConstantMax(
this);
8664 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8671 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8676 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8680 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8683ScalarEvolution::BackedgeTakenInfo &
8684ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8685 auto &BTI = getBackedgeTakenInfo(L);
8686 if (BTI.hasFullInfo())
8689 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8692 return Pair.first->second;
8694 BackedgeTakenInfo Result =
8695 computeBackedgeTakenCount(L,
true);
8697 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8700ScalarEvolution::BackedgeTakenInfo &
8701ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8707 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8708 BackedgeTakenCounts.try_emplace(L);
8710 return Pair.first->second;
8715 BackedgeTakenInfo Result = computeBackedgeTakenCount(L);
8722 if (Result.hasAnyInfo()) {
8725 auto LoopUsersIt = LoopUsers.find(L);
8726 if (LoopUsersIt != LoopUsers.end())
8728 forgetMemoizedResults(ToForget);
8731 for (
PHINode &PN : L->getHeader()->phis())
8732 ConstantEvolutionLoopExitValue.erase(&PN);
8740 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8749 BackedgeTakenCounts.clear();
8750 PredicatedBackedgeTakenCounts.clear();
8751 BECountUsers.clear();
8752 LoopPropertiesCache.clear();
8753 ConstantEvolutionLoopExitValue.clear();
8754 ValueExprMap.clear();
8755 ValuesAtScopes.clear();
8756 ValuesAtScopesUsers.clear();
8757 LoopDispositions.clear();
8758 BlockDispositions.clear();
8759 UnsignedRanges.clear();
8760 SignedRanges.clear();
8761 ExprValueMap.clear();
8763 ConstantMultipleCache.clear();
8764 PredicatedSCEVRewrites.clear();
8766 FoldCacheUser.clear();
8768void ScalarEvolution::visitAndClearUsers(
8772 while (!Worklist.
empty()) {
8779 if (It != ValueExprMap.
end()) {
8781 eraseValueFromMap(It->first);
8783 ConstantEvolutionLoopExitValue.erase(PN);
8795 while (!LoopWorklist.
empty()) {
8799 forgetBackedgeTakenCounts(CurrL,
false);
8800 forgetBackedgeTakenCounts(CurrL,
true);
8803 PredicatedSCEVRewrites.remove_if(
8804 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8806 auto LoopUsersItr = LoopUsers.find(CurrL);
8807 if (LoopUsersItr != LoopUsers.end())
8811 for (
PHINode &PN : CurrL->getHeader()->phis()) {
8812 ConstantEvolutionLoopExitValue.erase(&PN);
8813 auto VIt = ValueExprMap.find_as(
static_cast<Value *
>(&PN));
8814 if (VIt != ValueExprMap.end())
8818 LoopPropertiesCache.erase(CurrL);
8821 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8823 forgetMemoizedResults(ToForget);
8840 visitAndClearUsers(Worklist, Visited, ToForget);
8842 forgetMemoizedResults(ToForget);
8854 struct InvalidationRootCollector {
8858 InvalidationRootCollector(
Loop *L) : L(L) {}
8860 bool follow(
const SCEV *S) {
8866 if (L->contains(AddRec->
getLoop()))
8871 bool isDone()
const {
return false; }
8874 InvalidationRootCollector
C(L);
8876 forgetMemoizedResults(
C.Roots);
8889 BlockDispositions.clear();
8890 LoopDispositions.clear();
8907 while (!Worklist.
empty()) {
8909 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8910 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8911 if (!LoopDispoRemoved && !BlockDispoRemoved)
8913 auto Users = SCEVUsers.find(Curr);
8914 if (
Users != SCEVUsers.end())
8927const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8931 if (!isComplete() || ExitNotTaken.
empty())
8942 for (
const auto &ENT : ExitNotTaken) {
8943 const SCEV *BECount = ENT.ExactNotTaken;
8946 "We should only have known counts for exiting blocks that dominate "
8949 Ops.push_back(BECount);
8954 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8955 "Predicate should be always true!");
8964const ScalarEvolution::ExitNotTakenInfo *
8965ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8966 const BasicBlock *ExitingBlock,
8967 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8968 for (
const auto &ENT : ExitNotTaken)
8969 if (ENT.ExitingBlock == ExitingBlock) {
8970 if (ENT.hasAlwaysTruePredicate())
8972 else if (Predicates) {
8982const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8984 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8985 if (!getConstantMax())
8988 for (
const auto &ENT : ExitNotTaken)
8989 if (!ENT.hasAlwaysTruePredicate()) {
8997 "No point in having a non-constant max backedge taken count!");
8998 return getConstantMax();
9001const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
9003 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
9011 for (
const auto &ENT : ExitNotTaken) {
9012 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
9015 "We should only have known counts for exiting blocks that "
9021 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
9022 "Predicate should be always true!");
9025 if (ExitCounts.
empty())
9034bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
9036 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
9037 return !ENT.hasAlwaysTruePredicate();
9039 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
9055 this->ExactNotTaken = E = ConstantMaxNotTaken;
9056 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
9061 "Exact is not allowed to be less precise than Constant Max");
9064 "Exact is not allowed to be less precise than Symbolic Max");
9067 "Symbolic Max is not allowed to be less precise than Constant Max");
9070 "No point in having a non-constant max backedge taken count!");
9072 for (
const auto PredList : PredLists)
9073 for (
const auto *
P : PredList) {
9081 "Backedge count should be int");
9084 "Max backedge count should be int");
9097ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
9099 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
9100 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
9101 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9103 ExitNotTaken.reserve(ExitCounts.
size());
9104 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
9105 std::back_inserter(ExitNotTaken),
9106 [&](
const EdgeExitInfo &EEI) {
9107 BasicBlock *ExitBB = EEI.first;
9108 const ExitLimit &EL = EEI.second;
9109 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
9110 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
9115 "No point in having a non-constant max backedge taken count!");
9119ScalarEvolution::BackedgeTakenInfo
9120ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
9121 bool AllowPredicates) {
9123 L->getExitingBlocks(ExitingBlocks);
9125 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9128 bool CouldComputeBECount =
true;
9130 const SCEV *MustExitMaxBECount =
nullptr;
9131 const SCEV *MayExitMaxBECount =
nullptr;
9132 bool MustExitMaxOrZero =
false;
9133 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9144 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9145 if (ExitIfTrue == CI->
isZero())
9149 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9151 assert((AllowPredicates || EL.Predicates.empty()) &&
9152 "Predicated exit limit when predicates are not allowed!");
9157 ++NumExitCountsComputed;
9161 CouldComputeBECount =
false;
9168 "Exact is known but symbolic isn't?");
9169 ++NumExitCountsNotComputed;
9184 DT.dominates(ExitBB, Latch)) {
9185 if (!MustExitMaxBECount) {
9186 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9187 MustExitMaxOrZero = EL.MaxOrZero;
9190 EL.ConstantMaxNotTaken);
9194 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9197 EL.ConstantMaxNotTaken);
9201 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9205 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9211 for (
const auto &Pair : ExitCounts) {
9213 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9215 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9216 {
L, AllowPredicates});
9218 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9219 MaxBECount, MaxOrZero);
9222ScalarEvolution::ExitLimit
9223ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9224 bool IsOnlyExit,
bool AllowPredicates) {
9225 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9229 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9234 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9235 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9236 "It should have one successor in loop and one exit block!");
9247 if (!
L->contains(SBB)) {
9252 assert(Exit &&
"Exiting block must have at least one exit");
9253 return computeExitLimitFromSingleExitSwitch(
9254 L, SI, Exit, IsOnlyExit);
9261 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9262 bool AllowPredicates) {
9263 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9264 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9265 ControlsOnlyExit, AllowPredicates);
9268std::optional<ScalarEvolution::ExitLimit>
9269ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9270 bool ExitIfTrue,
bool ControlsOnlyExit,
9271 bool AllowPredicates) {
9273 (void)this->ExitIfTrue;
9274 (void)this->AllowPredicates;
9276 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9277 this->AllowPredicates == AllowPredicates &&
9278 "Variance in assumed invariant key components!");
9279 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9280 if (Itr == TripCountMap.end())
9281 return std::nullopt;
9285void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9287 bool ControlsOnlyExit,
9288 bool AllowPredicates,
9290 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9291 this->AllowPredicates == AllowPredicates &&
9292 "Variance in assumed invariant key components!");
9294 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9295 assert(InsertResult.second &&
"Expected successful insertion!");
9300ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9301 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9302 bool ControlsOnlyExit,
bool AllowPredicates) {
9304 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9308 ExitLimit EL = computeExitLimitFromCondImpl(
9309 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9310 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9314ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9315 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9316 bool ControlsOnlyExit,
bool AllowPredicates) {
9318 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9319 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9320 return *LimitFromBinOp;
9326 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9327 if (EL.hasFullInfo() || !AllowPredicates)
9331 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9351 const WithOverflowInst *WO;
9366 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9367 ControlsOnlyExit, AllowPredicates);
9368 if (EL.hasAnyInfo())
9373 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9376std::optional<ScalarEvolution::ExitLimit>
9377ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9381 bool AllowPredicates) {
9390 return std::nullopt;
9394 ExitLimit EL0 = computeExitLimitFromCondCached(
9395 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9396 ExitLimit EL1 = computeExitLimitFromCondCached(
9397 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9402 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9407 if (EitherMayExit) {
9417 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9419 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9422 EL1.ConstantMaxNotTaken);
9424 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9426 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9429 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9433 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9434 BECount = EL0.ExactNotTaken;
9447 SymbolicMaxBECount =
9449 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9453ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9454 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9455 bool AllowPredicates) {
9467 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9469 if (EL.hasAnyInfo())
9472 auto *ExhaustiveCount =
9473 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9476 return ExhaustiveCount;
9478 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9481ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9483 bool ControlsOnlyExit,
bool AllowPredicates) {
9508 ConstantRange CompRange =
9526 InnerLHS = ZExt->getOperand();
9573 if (EL.hasAnyInfo())
9590 if (EL.hasAnyInfo())
return EL;
9622 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9624 if (EL.hasAnyInfo())
9640 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9642 if (EL.hasAnyInfo())
9653ScalarEvolution::ExitLimit
9654ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9656 BasicBlock *ExitingBlock,
9657 bool ControlsOnlyExit) {
9658 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9661 if (
Switch->getDefaultDest() == ExitingBlock)
9665 "Default case must not exit the loop!");
9671 if (EL.hasAnyInfo())
9683 "Evaluation of SCEV at constant didn't fold correctly?");
9687ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9697 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9704 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9706 unsigned &OutShiftAmt) {
9707 using namespace PatternMatch;
9709 ConstantInt *ShiftAmt;
9711 OutOpCode = Instruction::LShr;
9713 OutOpCode = Instruction::AShr;
9715 OutOpCode = Instruction::Shl;
9720 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9735 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9737 unsigned &ShiftAmtOut) {
9738 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9754 if (MatchPositiveShift(
LHS, V, OpC, Amt)) {
9755 PostShiftOpCode = OpC;
9761 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9764 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9770 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9777 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9783 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9795 ConstantInt *StableValue =
nullptr;
9800 case Instruction::AShr: {
9808 StableValue = ConstantInt::get(Ty, 0);
9810 StableValue = ConstantInt::get(Ty, -1,
true);
9816 case Instruction::LShr:
9817 case Instruction::Shl:
9827 "Otherwise cannot be an operand to a branch instruction");
9829 if (
Result->isNullValue()) {
9838 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9840 const SCEV *StartSCEV =
getSCEV(StartValue);
9844 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9845 MaxBTC = std::min(MaxBTC, RangeBTC);
9849 const SCEV *UpperBound =
9866 if (
const Function *
F = CI->getCalledFunction())
9875 if (!L->contains(
I))
return false;
9880 return L->getHeader() ==
I->getParent();
9956 if (!
I)
return nullptr;
9969 std::vector<Constant*> Operands(
I->getNumOperands());
9971 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9975 if (!Operands[i])
return nullptr;
9980 if (!
C)
return nullptr;
10002 if (IncomingVal != CurrentVal) {
10005 IncomingVal = CurrentVal;
10009 return IncomingVal;
10017ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
10020 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
10029 DenseMap<Instruction *, Constant *> CurrentIterVals;
10031 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10037 for (PHINode &
PHI : Header->phis()) {
10039 CurrentIterVals[&
PHI] = StartCST;
10041 if (!CurrentIterVals.
count(PN))
10042 return RetVal =
nullptr;
10048 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
10051 unsigned IterationNum = 0;
10053 for (; ; ++IterationNum) {
10054 if (IterationNum == NumIterations)
10055 return RetVal = CurrentIterVals[PN];
10059 DenseMap<Instruction *, Constant *> NextIterVals;
10064 NextIterVals[PN] = NextPHI;
10066 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
10072 for (
const auto &
I : CurrentIterVals) {
10074 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
10079 for (
const auto &
I : PHIsToCompute) {
10080 PHINode *
PHI =
I.first;
10083 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10086 if (NextPHI !=
I.second)
10087 StoppedEvolving =
false;
10092 if (StoppedEvolving)
10093 return RetVal = CurrentIterVals[PN];
10095 CurrentIterVals.swap(NextIterVals);
10099const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
10109 DenseMap<Instruction *, Constant *> CurrentIterVals;
10111 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10114 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
10116 for (PHINode &
PHI : Header->phis()) {
10118 CurrentIterVals[&
PHI] = StartCST;
10120 if (!CurrentIterVals.
count(PN))
10128 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10135 if (CondVal->getValue() == uint64_t(ExitWhen)) {
10136 ++NumBruteForceTripCountsComputed;
10141 DenseMap<Instruction *, Constant *> NextIterVals;
10147 for (
const auto &
I : CurrentIterVals) {
10149 if (!
PHI ||
PHI->getParent() != Header)
continue;
10152 for (PHINode *
PHI : PHIsToCompute) {
10154 if (NextPHI)
continue;
10156 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10159 CurrentIterVals.
swap(NextIterVals);
10172 return LS.second ? LS.second : V;
10174 Values.emplace_back(L,
nullptr);
10177 const SCEV *
C = computeSCEVAtScope(V, L);
10178 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10179 if (LS.first == L) {
10182 ValuesAtScopesUsers[
C].push_back({L, V});
10193 switch (V->getSCEVType()) {
10233 assert(!
C->getType()->isPointerTy() &&
10234 "Can only have one pointer, and it must be last");
10259const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10260 SmallVectorImpl<SCEVUse> &NewOps) {
10295const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10296 switch (
V->getSCEVType()) {
10307 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10318 for (++i; i !=
e; ++i)
10363 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10373 for (++i; i !=
e; ++i) {
10378 return getWithOperands(V, NewOps);
10393 const Loop *CurrLoop = this->LI[
I->getParent()];
10404 if (BackedgeTakenCount->
isZero()) {
10405 Value *InitValue =
nullptr;
10406 bool MultipleInitValues =
false;
10412 MultipleInitValues =
true;
10417 if (!MultipleInitValues && InitValue)
10426 unsigned InLoopPred =
10437 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10451 SmallVector<Constant *, 4> Operands;
10452 Operands.
reserve(
I->getNumOperands());
10453 bool MadeImprovement =
false;
10468 MadeImprovement |= OrigV != OpV;
10473 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10478 if (!MadeImprovement)
10499const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10501 return stripInjectiveFunctions(ZExt->getOperand());
10503 return stripInjectiveFunctions(SExt->getOperand());
10521 assert(
A != 0 &&
"A must be non-zero.");
10537 if (MinTZ < Mult2 && L->getLoopPredecessor())
10539 if (MinTZ < Mult2) {
10562 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10582static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10588 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10589 << *AddRec <<
'\n');
10592 if (!LC || !MC || !
NC) {
10593 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10594 return std::nullopt;
10600 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10608 N =
N.sext(NewWidth);
10609 M = M.sext(NewWidth);
10610 L = L.sext(NewWidth);
10627 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10628 <<
", multiplied by " <<
T <<
'\n');
10637 std::optional<APInt>
Y) {
10639 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10642 return XW.
slt(YW) ? *
X : *
Y;
10645 return std::nullopt;
10646 return X ? *
X : *
Y;
10663 return std::nullopt;
10664 unsigned W =
X->getBitWidth();
10684static std::optional<APInt>
10690 return std::nullopt;
10693 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10694 std::optional<APInt>
X =
10697 return std::nullopt;
10702 return std::nullopt;
10717static std::optional<APInt>
10721 "Starting value of addrec should be 0");
10722 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10723 <<
Range <<
", addrec " << *AddRec <<
'\n');
10727 "Addrec's initial value should be in range");
10733 return std::nullopt;
10743 auto SolveForBoundary =
10744 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10747 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10748 << Bound <<
" (before multiplying by " << M <<
")\n");
10751 std::optional<APInt> SO;
10754 "signed overflow\n");
10758 "unsigned overflow\n");
10759 std::optional<APInt> UO =
10762 auto LeavesRange = [&] (
const APInt &
X) {
10770 if (
Range.contains(
V1->getValue()))
10779 return {std::nullopt,
false};
10784 if (LeavesRange(*Min))
10785 return { Min,
true };
10786 std::optional<APInt> Max = Min == SO ? UO : SO;
10787 if (LeavesRange(*Max))
10788 return { Max,
true };
10791 return {std::nullopt,
true};
10798 auto SL = SolveForBoundary(
Lower);
10799 auto SU = SolveForBoundary(
Upper);
10802 if (!SL.second || !SU.second)
10803 return std::nullopt;
10846ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10848 bool ControlsOnlyExit,
10849 bool AllowPredicates) {
10860 if (
C->getValue()->isZero())
return C;
10864 const SCEVAddRecExpr *AddRec =
10867 if (!AddRec && AllowPredicates)
10873 if (!AddRec || AddRec->
getLoop() != L)
10884 return ExitLimit(R, R, R,
false, Predicates);
10942 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10968 const SCEV *
Exact =
10976 const SCEV *SymbolicMax =
10978 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10987 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10995 return ExitLimit(
E, M, S,
false, Predicates);
10998ScalarEvolution::ExitLimit
10999ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
11007 if (!
C->getValue()->isZero())
11017std::pair<const BasicBlock *, const BasicBlock *>
11018ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
11029 if (
const Loop *L = LI.getLoopFor(BB))
11030 return {
L->getLoopPredecessor(),
L->getHeader()};
11032 return {
nullptr, BB};
11041 if (
A ==
B)
return true;
11056 if (ComputesEqualValues(AI, BI))
11064 const SCEV *Op0, *Op1;
11083 auto TrivialCase = [&](
bool TriviallyTrue) {
11092 const SCEV *NewLHS, *NewRHS;
11116 return TrivialCase(
false);
11117 return TrivialCase(
true);
11136 RAdd->hasNoSignedWrap()) ||
11138 RAdd->hasNoUnsignedWrap())) {
11158 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
11159 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
11162 C->getAPInt().isStrictlyPositive()) ||
11186 const APInt &
RA = RC->getAPInt();
11188 bool SimplifiedByConstantRange =
false;
11193 return TrivialCase(
true);
11195 return TrivialCase(
false);
11204 Changed = SimplifiedByConstantRange =
true;
11208 if (!SimplifiedByConstantRange) {
11225 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11231 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11237 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11243 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11255 return TrivialCase(
true);
11257 return TrivialCase(
false);
11362 auto NonRecursive = [OrNegative](
const SCEV *S) {
11364 return C->getAPInt().isPowerOf2() ||
11365 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11371 if (NonRecursive(S))
11397 APInt C = Cst->getAPInt();
11398 return C.urem(M) == 0;
11406 const SCEV *SmodM =
11421 for (
auto *
A : Assumptions)
11422 if (
A->implies(
P, *
this))
11435std::pair<const SCEV *, const SCEV *>
11438 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11440 return { Start, Start };
11442 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11451 getUsedLoops(LHS, LoopsUsed);
11452 getUsedLoops(RHS, LoopsUsed);
11454 if (LoopsUsed.
empty())
11459 for (
const auto *L1 : LoopsUsed)
11460 for (
const auto *L2 : LoopsUsed)
11461 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11462 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11463 "Domination relationship is not a linear order");
11493 SplitRHS.second) &&
11505 if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
11509 return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11519 return std::nullopt;
11534 if (KnownWithoutContext)
11535 return KnownWithoutContext;
11542 return std::nullopt;
11548 const Loop *L = LHS->getLoop();
11553std::optional<ScalarEvolution::MonotonicPredicateType>
11556 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11562 auto ResultSwapped =
11565 assert(*ResultSwapped != *Result &&
11566 "monotonicity should flip as we flip the predicate");
11573std::optional<ScalarEvolution::MonotonicPredicateType>
11574ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11588 return std::nullopt;
11592 "Should be greater or less!");
11596 if (!LHS->hasNoUnsignedWrap())
11597 return std::nullopt;
11601 "Relational predicate is either signed or unsigned!");
11602 if (!
LHS->hasNoSignedWrap())
11603 return std::nullopt;
11605 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11613 return std::nullopt;
11616std::optional<ScalarEvolution::LoopInvariantPredicate>
11623 return std::nullopt;
11630 if (!ArLHS || ArLHS->
getLoop() != L)
11631 return std::nullopt;
11635 return std::nullopt;
11661 return std::nullopt;
11698 return std::nullopt;
11701std::optional<ScalarEvolution::LoopInvariantPredicate>
11706 Pred, LHS, RHS, L, CtxI, MaxIter))
11716 Pred, LHS, RHS, L, CtxI,
Op))
11718 return std::nullopt;
11721std::optional<ScalarEvolution::LoopInvariantPredicate>
11736 return std::nullopt;
11743 if (!AR || AR->
getLoop() != L)
11744 return std::nullopt;
11749 Pred = Pred.dropSameSign();
11753 return std::nullopt;
11759 if (Step != One && Step != MinusOne)
11760 return std::nullopt;
11766 return std::nullopt;
11772 return std::nullopt;
11780 if (Step == MinusOne)
11784 return std::nullopt;
11790bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11796 auto CheckRange = [&](
bool IsSigned) {
11799 return RangeLHS.
icmp(Pred, RangeRHS);
11808 if (CheckRange(
true) || CheckRange(
false))
11817bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11826 SCEVUse XNonConstOp, XConstOp;
11827 SCEVUse YNonConstOp, YConstOp;
11831 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11834 XFlagsPresent = ExpectedFlags;
11839 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11842 YFlagsPresent = ExpectedFlags;
11845 if (YNonConstOp != XNonConstOp)
11853 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11856 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11916bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11937bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11938 const SCEV *
LHS,
const SCEV *
RHS) {
11943 return any_of(*BB, [&](
const Instruction &
I) {
11944 using namespace llvm::PatternMatch;
11949 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11963 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11968 "This cannot be done on broken IR!");
11971 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11980 if (LoopContinuePredicate &&
11981 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11982 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11987 if (WalkingBEDominatingConds)
11993 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11994 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
12001 const SCEV *LoopCounter =
12009 for (
auto &AssumeVH : AC.assumptions()) {
12016 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
12020 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
12023 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
12024 DTN != HeaderDTN; DTN = DTN->getIDom()) {
12025 assert(DTN &&
"should reach the loop header before reaching the root!");
12028 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
12046 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
12059 if (!DT.isReachableFromEntry(BB))
12063 "This cannot be done on broken IR!");
12071 const bool ProvingStrictComparison =
12073 bool ProvedNonStrictComparison =
false;
12074 bool ProvedNonEquality =
false;
12077 if (!ProvedNonStrictComparison)
12078 ProvedNonStrictComparison = Fn(NonStrictPredicate);
12079 if (!ProvedNonEquality)
12081 if (ProvedNonStrictComparison && ProvedNonEquality)
12086 if (ProvingStrictComparison) {
12088 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
12090 if (SplitAndProve(ProofFn))
12095 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
12097 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
12099 if (ProvingStrictComparison) {
12101 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
12103 if (SplitAndProve(ProofFn))
12112 const Loop *ContainingLoop = LI.getLoopFor(BB);
12114 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
12118 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
12119 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
12122 if (!BlockEntryPredicate)
12131 for (
auto &AssumeVH : AC.assumptions()) {
12135 if (!DT.dominates(CI, BB))
12138 if (ProveViaCond(CI->getArgOperand(0),
false))
12144 F.getParent(), Intrinsic::experimental_guard);
12146 for (
const auto *GU : GuardDecl->users())
12148 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12149 if (ProveViaCond(Guard->getArgOperand(0),
false))
12164 "LHS is not available at Loop Entry");
12166 "RHS is not available at Loop Entry");
12168 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12179 if (FoundCondValue ==
12183 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12187 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12190 const Value *Op0, *Op1;
12193 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12197 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12198 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12202 if (!ICI)
return false;
12206 CmpPredicate FoundPred;
12215 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12218bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12219 const SCEV *
RHS, CmpPredicate FoundPred,
12220 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12221 const Instruction *CtxI) {
12231 auto *WideType = FoundLHS->
getType();
12243 TruncFoundLHS, TruncFoundRHS, CtxI))
12269 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12273bool ScalarEvolution::isImpliedCondBalancedTypes(
12278 "Types should be balanced!");
12285 if (FoundLHS == FoundRHS)
12289 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12301 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12318 LHS, FoundLHS, FoundRHS, CtxI);
12320 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12342 assert(P1 != P2 &&
"Handled earlier!");
12346 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12350 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12353 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12354 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12355 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12360 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12371 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12372 CanonicalRHS, CanonicalFoundLHS,
12373 CanonicalFoundRHS);
12378 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12379 CanonicalRHS, CanonicalFoundLHS,
12380 CanonicalFoundRHS);
12387 const SCEVConstant *
C =
nullptr;
12388 const SCEV *
V =
nullptr;
12406 if (Min ==
C->getAPInt()) {
12411 APInt SharperMin = Min + 1;
12414 case ICmpInst::ICMP_SGE:
12415 case ICmpInst::ICMP_UGE:
12418 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12423 case ICmpInst::ICMP_SGT:
12424 case ICmpInst::ICMP_UGT:
12434 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12439 case ICmpInst::ICMP_SLE:
12440 case ICmpInst::ICMP_ULE:
12441 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12442 LHS, V, getConstant(SharperMin), CtxI))
12446 case ICmpInst::ICMP_SLT:
12447 case ICmpInst::ICMP_ULT:
12448 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12449 LHS, V, getConstant(Min), CtxI))
12463 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12467 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12470 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12486std::optional<APInt>
12493 APInt DiffMul(BW, 1);
12496 for (
unsigned I = 0;
I < 8; ++
I) {
12505 if (LAR->getLoop() != MAR->getLoop())
12506 return std::nullopt;
12510 if (!LAR->isAffine() || !MAR->isAffine())
12511 return std::nullopt;
12513 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12514 return std::nullopt;
12516 Less = LAR->getStart();
12517 More = MAR->getStart();
12522 auto MatchConstMul =
12523 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12528 return std::nullopt;
12530 if (
auto MatchedMore = MatchConstMul(More)) {
12531 if (
auto MatchedLess = MatchConstMul(
Less)) {
12532 if (MatchedMore->second == MatchedLess->second) {
12533 More = MatchedMore->first;
12534 Less = MatchedLess->first;
12535 DiffMul *= MatchedMore->second;
12546 Diff +=
C->getAPInt() * DiffMul;
12549 Diff -=
C->getAPInt() * DiffMul;
12552 Multiplicity[S] +=
Mul;
12554 auto Decompose = [&](
const SCEV *S,
int Mul) {
12561 Decompose(More, 1);
12562 Decompose(
Less, -1);
12566 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12567 for (
const auto &[S,
Mul] : Multiplicity) {
12572 return std::nullopt;
12574 }
else if (
Mul == -1) {
12576 return std::nullopt;
12579 return std::nullopt;
12583 if (NewMore == More || NewLess ==
Less)
12584 return std::nullopt;
12590 if (!More && !
Less)
12594 if (!More || !
Less)
12595 return std::nullopt;
12599 return std::nullopt;
12602bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12624 const auto *Latch = L->getLoopLatch();
12627 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12636 const auto *Latch = L->getLoopLatch();
12639 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12649bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12652 const SCEV *FoundLHS,
12653 const SCEV *FoundRHS) {
12662 if (!AddRecFoundLHS)
12669 const Loop *
L = AddRecFoundLHS->getLoop();
12670 if (L != AddRecLHS->getLoop())
12709 if (!RDiff || *LDiff != *RDiff)
12712 if (LDiff->isMinValue())
12715 APInt FoundRHSLimit;
12718 FoundRHSLimit = -(*RDiff);
12730bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12731 const SCEV *
RHS,
const SCEV *FoundLHS,
12732 const SCEV *FoundRHS,
unsigned Depth) {
12733 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12737 bool Erased = PendingMerges.erase(LPhi);
12738 assert(Erased &&
"Failed to erase LPhi!");
12742 bool Erased = PendingMerges.erase(RPhi);
12743 assert(Erased &&
"Failed to erase RPhi!");
12751 if (!PendingMerges.insert(Phi).second)
12765 if (!PendingMerges.insert(Phi).second)
12771 if (!LPhi && !RPhi)
12782 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12786 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12787 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12788 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12789 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12792 if (RPhi && RPhi->getParent() == LBB) {
12799 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12800 if (!ProvedEasily(L, R))
12811 auto *RLoop = RAR->
getLoop();
12812 auto *Predecessor = RLoop->getLoopPredecessor();
12813 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12815 if (!ProvedEasily(L1, RAR->
getStart()))
12817 auto *Latch = RLoop->getLoopLatch();
12818 assert(Latch &&
"Loop with AddRec with no latch?");
12839 if (
auto *Loop = LI.getLoopFor(LBB))
12842 if (!ProvedEasily(L,
RHS))
12849bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12852 const SCEV *FoundLHS,
12853 const SCEV *FoundRHS) {
12856 if (
RHS == FoundRHS) {
12861 if (
LHS != FoundLHS)
12868 Value *Shiftee, *ShiftValue;
12870 using namespace PatternMatch;
12871 if (
match(SUFoundRHS->getValue(),
12873 auto *ShifteeS =
getSCEV(Shiftee);
12891bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12892 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12893 const SCEV *FoundRHS) {
12925 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12933 return Diff == FoundDiff;
12936bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12938 const SCEV *FoundLHS,
12939 const SCEV *FoundRHS,
12940 const Instruction *CtxI) {
12941 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12943 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12945 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12946 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12948 isImpliedCondOperandsViaMatchingDiff(Pred,
LHS,
RHS, FoundLHS,
12950 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12954template <
typename MinMaxExprType>
12956 const SCEV *Candidate) {
12961 return is_contained(MinMaxExpr->operands(), Candidate);
12974 const SCEV *LStart, *RStart, *Step;
13024bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
13026 const SCEV *FoundLHS,
13027 const SCEV *FoundRHS,
13031 "LHS and RHS have different sizes?");
13034 "FoundLHS and FoundRHS have different sizes?");
13068 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
13070 return Ext->getOperand();
13077 auto *OrigLHS =
LHS;
13078 auto *OrigFoundLHS = FoundLHS;
13079 LHS = GetOpFromSExt(
LHS);
13080 FoundLHS = GetOpFromSExt(FoundLHS);
13083 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
13086 FoundRHS,
Depth + 1);
13099 if (!LHSAddExpr->hasNoSignedWrap())
13102 SCEVUse LL = LHSAddExpr->getOperand(0);
13103 SCEVUse LR = LHSAddExpr->getOperand(1);
13107 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
13108 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
13113 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
13119 using namespace llvm::PatternMatch;
13138 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13146 auto *DTy = Denominator->getType();
13147 auto *FRHSTy = FoundRHS->
getType();
13148 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13167 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13178 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13180 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13188 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13221bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13225 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13228 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13231bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13234 const SCEV *FoundLHS,
13235 const SCEV *FoundRHS) {
13271 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13277bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13278 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13279 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13293 ConstantRange FoundLHSRange =
13297 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13304 return LHSRange.
icmp(Pred, ConstRHS);
13307bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13320 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13328 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13331bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
13343 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
13351 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
13363const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
13364 const SCEV *Stride,
13395 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13406 :
APIntOps::umax(MaxEnd, MinStart);
13413ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13414 const Loop *L,
bool IsSigned,
13415 bool ControlsOnlyExit,
bool AllowPredicates) {
13419 bool PredicatedIV =
false;
13424 auto canProveNUW = [&]() {
13427 if (!ControlsOnlyExit)
13448 Limit = Limit.
zext(OuterBitWidth);
13460 Type *Ty = ZExt->getType();
13471 if (!
IV && AllowPredicates) {
13476 PredicatedIV =
true;
13480 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13494 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13497 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13502 if (!PositiveStride) {
13554 auto wouldZeroStrideBeUB = [&]() {
13566 if (!wouldZeroStrideBeUB()) {
13570 }
else if (!NoWrap) {
13573 if (canIVOverflowOnLT(
RHS, Stride, IsSigned))
13586 const SCEV *
Start =
IV->getStart();
13592 const SCEV *OrigStart =
Start;
13593 const SCEV *OrigRHS =
RHS;
13594 if (
Start->getType()->isPointerTy()) {
13605 const SCEV *End =
nullptr, *BECount =
nullptr,
13606 *BECountIfBackedgeTaken =
nullptr;
13609 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13610 any(RHSAddRec->getNoWrapFlags())) {
13623 const SCEV *RHSStart = RHSAddRec->getStart();
13624 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13636 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13645 BECountIfBackedgeTaken =
13650 if (BECount ==
nullptr) {
13655 const SCEV *MaxBECount = computeMaxBECountForLT(
13658 MaxBECount,
false , Predicates);
13665 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13692 const SCEV *Numerator =
13698 auto canProveRHSGreaterThanEqualStart = [&]() {
13717 auto *StartMinusOne =
13724 if (canProveRHSGreaterThanEqualStart()) {
13739 BECountIfBackedgeTaken =
13755 bool MayAddOverflow = [&] {
13801 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13815 if (!MayAddOverflow) {
13827 const SCEV *ConstantMaxBECount;
13828 bool MaxOrZero =
false;
13830 ConstantMaxBECount = BECount;
13831 }
else if (BECountIfBackedgeTaken &&
13836 ConstantMaxBECount = BECountIfBackedgeTaken;
13839 ConstantMaxBECount = computeMaxBECountForLT(
13847 const SCEV *SymbolicMaxBECount =
13849 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13853ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13854 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13855 bool ControlsOnlyExit,
bool AllowPredicates) {
13862 if (!
IV && AllowPredicates)
13869 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13873 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13886 if (!Stride->
isOne() && !NoWrap)
13887 if (canIVOverflowOnGT(
RHS, Stride, IsSigned))
13890 const SCEV *
Start =
IV->getStart();
13891 const SCEV *End =
RHS;
13902 if (
Start->getType()->isPointerTy()) {
13937 const SCEV *ConstantMaxBECount =
13944 ConstantMaxBECount = BECount;
13945 const SCEV *SymbolicMaxBECount =
13948 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13954 if (
Range.isFullSet())
13959 if (!SC->getValue()->isZero()) {
13965 return ShiftedAddRec->getNumIterationsInRange(
13966 Range.subtract(SC->getAPInt()), SE);
13997 APInt ExitVal = (End +
A).udiv(
A);
14010 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
14011 "Linear scev computation is off in a bad way!");
14042 assert(!
Last->isZero() &&
"Recurrency with zero step?");
14067 Ty = Store->getValueOperand()->getType();
14069 Ty = Load->getType();
14082 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14084 SE->ConstantEvolutionLoopExitValue.erase(PN);
14085 SE->eraseValueFromMap(getValPtr());
14089void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
14090 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14100 : CallbackVH(
V), SE(se) {}
14109 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
14111 LoopDispositions(64), BlockDispositions(64) {
14123 F.getParent(), Intrinsic::experimental_guard);
14124 HasGuards = GuardDecl && !GuardDecl->use_empty();
14128 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
14129 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14130 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14131 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14132 PendingMerges(
std::
move(Arg.PendingMerges)),
14133 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14134 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14135 PredicatedBackedgeTakenCounts(
14136 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14137 BECountUsers(
std::
move(Arg.BECountUsers)),
14138 ConstantEvolutionLoopExitValue(
14139 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14140 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14141 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14142 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14143 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14144 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14145 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14146 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14147 SignedRanges(
std::
move(Arg.SignedRanges)),
14148 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14149 UniquePreds(
std::
move(Arg.UniquePreds)),
14150 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14151 LoopUsers(
std::
move(Arg.LoopUsers)),
14152 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14153 FirstUnknown(Arg.FirstUnknown) {
14154 Arg.FirstUnknown =
nullptr;
14163 Tmp->~SCEVUnknown();
14165 FirstUnknown =
nullptr;
14167 ExprValueMap.clear();
14168 ValueExprMap.clear();
14170 BackedgeTakenCounts.clear();
14171 PredicatedBackedgeTakenCounts.clear();
14173 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14174 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14175 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14176 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14198 L->getHeader()->printAsOperand(OS,
false);
14202 L->getExitingBlocks(ExitingBlocks);
14203 if (ExitingBlocks.
size() != 1)
14204 OS <<
"<multiple exits> ";
14208 OS <<
"backedge-taken count is ";
14211 OS <<
"Unpredictable backedge-taken count.";
14214 if (ExitingBlocks.
size() > 1)
14215 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14216 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14224 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14227 OS <<
"\n Predicates:\n";
14228 for (
const auto *
P : Predicates)
14236 L->getHeader()->printAsOperand(OS,
false);
14241 OS <<
"constant max backedge-taken count is ";
14244 OS <<
", actual taken count either this or zero.";
14246 OS <<
"Unpredictable constant max backedge-taken count. ";
14251 L->getHeader()->printAsOperand(OS,
false);
14256 OS <<
"symbolic max backedge-taken count is ";
14259 OS <<
", actual taken count either this or zero.";
14261 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14265 if (ExitingBlocks.
size() > 1)
14266 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14267 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14277 OS <<
"\n predicated symbolic max exit count for "
14278 << ExitingBlock->
getName() <<
": ";
14280 OS <<
"\n Predicates:\n";
14281 for (
const auto *
P : Predicates)
14292 L->getHeader()->printAsOperand(OS,
false);
14295 OS <<
"Predicated backedge-taken count is ";
14298 OS <<
"Unpredictable predicated backedge-taken count.";
14300 OS <<
" Predicates:\n";
14301 for (
const auto *
P : Preds)
14306 auto *PredConstantMax =
14308 if (PredConstantMax != ConstantBTC) {
14310 L->getHeader()->printAsOperand(OS,
false);
14313 OS <<
"Predicated constant max backedge-taken count is ";
14316 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14318 OS <<
" Predicates:\n";
14319 for (
const auto *
P : Preds)
14324 auto *PredSymbolicMax =
14326 if (SymbolicBTC != PredSymbolicMax) {
14328 L->getHeader()->printAsOperand(OS,
false);
14331 OS <<
"Predicated symbolic max backedge-taken count is ";
14334 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14336 OS <<
" Predicates:\n";
14337 for (
const auto *
P : Preds)
14343 L->getHeader()->printAsOperand(OS,
false);
14370 OS <<
"Computable";
14380 OS <<
"DoesNotDominate";
14386 OS <<
"ProperlyDominates";
14403 OS <<
"Classifying expressions for: ";
14404 F.printAsOperand(OS,
false);
14419 const Loop *L = LI.getLoopFor(
I.getParent());
14434 OS <<
"\t\t" "Exits: ";
14437 OS <<
"<<Unknown>>";
14443 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14445 Iter->getHeader()->printAsOperand(OS,
false);
14453 InnerL->getHeader()->printAsOperand(OS,
false);
14464 OS <<
"Determining loop execution counts for: ";
14465 F.printAsOperand(OS,
false);
14473 auto &
Values = LoopDispositions[S];
14474 for (
auto &V :
Values) {
14475 if (V.getPointer() == L)
14480 auto &Values2 = LoopDispositions[S];
14482 if (V.getPointer() == L) {
14491ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14509 if (L->contains(AR->
getLoop()) &&
14511 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14516 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14517 " dominate the contained loop's header?");
14545 bool HasVarying =
false;
14546 bool HasUniform =
false;
14588 auto &
Values = BlockDispositions[S];
14589 for (
auto &V :
Values) {
14590 if (V.getPointer() == BB)
14595 auto &Values2 = BlockDispositions[S];
14597 if (V.getPointer() == BB) {
14606ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14636 bool Proper =
true;
14647 if (Instruction *
I =
14649 if (
I->getParent() == BB)
14651 if (DT.properlyDominates(
I->getParent(), BB))
14674void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14677 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14678 auto It = BECounts.find(L);
14679 if (It != BECounts.end()) {
14680 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14681 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14683 auto UserIt = BECountUsers.find(S);
14684 assert(UserIt != BECountUsers.end());
14689 BECounts.erase(It);
14697 while (!Worklist.
empty()) {
14699 auto Users = SCEVUsers.find(Curr);
14700 if (
Users != SCEVUsers.end())
14701 for (
const auto *User :
Users->second)
14702 if (ToForget.
insert(User).second)
14706 for (
const auto *S : ToForget)
14707 forgetMemoizedResultsImpl(S);
14709 PredicatedSCEVRewrites.remove_if(
14710 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14713void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14714 LoopDispositions.erase(S);
14715 BlockDispositions.erase(S);
14716 UnsignedRanges.erase(S);
14717 SignedRanges.erase(S);
14718 HasRecMap.erase(S);
14719 ConstantMultipleCache.erase(S);
14722 UnsignedWrapViaInductionTried.erase(AR);
14723 SignedWrapViaInductionTried.erase(AR);
14726 auto ExprIt = ExprValueMap.find(S);
14727 if (ExprIt != ExprValueMap.end()) {
14728 for (
Value *V : ExprIt->second) {
14729 auto ValueIt = ValueExprMap.find_as(V);
14730 if (ValueIt != ValueExprMap.end())
14731 ValueExprMap.erase(ValueIt);
14733 ExprValueMap.erase(ExprIt);
14736 auto ScopeIt = ValuesAtScopes.find(S);
14737 if (ScopeIt != ValuesAtScopes.end()) {
14738 for (
const auto &Pair : ScopeIt->second)
14741 std::make_pair(Pair.first, S));
14742 ValuesAtScopes.erase(ScopeIt);
14745 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14746 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14747 for (
const auto &Pair : ScopeUserIt->second)
14748 llvm::erase(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
14749 ValuesAtScopesUsers.erase(ScopeUserIt);
14752 auto BEUsersIt = BECountUsers.find(S);
14753 if (BEUsersIt != BECountUsers.end()) {
14755 auto Copy = BEUsersIt->second;
14756 for (
const auto &Pair : Copy)
14757 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14758 BECountUsers.erase(BEUsersIt);
14761 auto FoldUser = FoldCacheUser.find(S);
14762 if (FoldUser != FoldCacheUser.end())
14763 for (
auto &KV : FoldUser->second)
14764 FoldCache.erase(KV);
14765 FoldCacheUser.erase(S);
14769ScalarEvolution::getUsedLoops(
const SCEV *S,
14771 struct FindUsedLoops {
14772 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14773 : LoopsUsed(LoopsUsed) {}
14774 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14775 bool follow(
const SCEV *S) {
14781 bool isDone()
const {
return false; }
14784 FindUsedLoops
F(LoopsUsed);
14785 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14788void ScalarEvolution::getReachableBlocks(
14791 Worklist.
push_back(&F.getEntryBlock());
14792 while (!Worklist.
empty()) {
14794 if (!Reachable.
insert(BB).second)
14802 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14809 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14813 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14848 SCEVMapper SCM(SE2);
14850 SE2.getReachableBlocks(ReachableBlocks, F);
14852 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14870 while (!LoopStack.
empty()) {
14876 if (!ReachableBlocks.
contains(L->getHeader()))
14881 auto It = BackedgeTakenCounts.find(L);
14882 if (It == BackedgeTakenCounts.end())
14886 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14906 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14907 if (Delta && !Delta->
isZero()) {
14908 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14909 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14910 dbgs() <<
"New: " << *NewBECount <<
"\n";
14911 dbgs() <<
"Delta: " << *Delta <<
"\n";
14919 while (!Worklist.
empty()) {
14921 if (ValidLoops.
insert(L).second)
14922 Worklist.
append(L->begin(), L->end());
14924 for (
const auto &KV : ValueExprMap) {
14929 "AddRec references invalid loop");
14934 auto It = ExprValueMap.find(KV.second);
14935 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14936 dbgs() <<
"Value " << *KV.first
14937 <<
" is in ValueExprMap but not in ExprValueMap\n";
14942 if (!ReachableBlocks.
contains(
I->getParent()))
14944 const SCEV *OldSCEV = SCM.visit(KV.second);
14946 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14947 if (Delta && !Delta->
isZero()) {
14948 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14949 <<
"Old: " << *OldSCEV <<
"\n"
14950 <<
"New: " << *NewSCEV <<
"\n"
14951 <<
"Delta: " << *Delta <<
"\n";
14957 for (
const auto &KV : ExprValueMap) {
14958 for (
Value *V : KV.second) {
14959 const SCEV *S = ValueExprMap.lookup(V);
14961 dbgs() <<
"Value " << *V
14962 <<
" is in ExprValueMap but not in ValueExprMap\n";
14965 if (S != KV.first) {
14966 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14967 << *KV.first <<
"\n";
14974 for (
const auto &S : UniqueSCEVs) {
14979 auto It = SCEVUsers.find(
Op);
14980 if (It != SCEVUsers.end() && It->second.count(&S))
14982 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14983 <<
" is not being tracked!\n";
14989 for (
const auto &ValueAndVec : ValuesAtScopes) {
14991 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14992 const Loop *L = LoopAndValueAtScope.first;
14993 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
14995 auto It = ValuesAtScopesUsers.find(ValueAtScope);
14996 if (It != ValuesAtScopesUsers.end() &&
14999 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
15000 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
15006 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
15007 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
15008 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
15009 const Loop *L = LoopAndValue.first;
15010 const SCEV *
Value = LoopAndValue.second;
15012 auto It = ValuesAtScopes.find(
Value);
15013 if (It != ValuesAtScopes.end() &&
15014 is_contained(It->second, std::make_pair(L, ValueAtScope)))
15016 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
15017 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
15023 auto VerifyBECountUsers = [&](
bool Predicated) {
15025 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
15026 for (
const auto &LoopAndBEInfo : BECounts) {
15027 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
15028 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
15030 auto UserIt = BECountUsers.find(S);
15031 if (UserIt != BECountUsers.end() &&
15032 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
15034 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
15035 <<
" missing from BECountUsers\n";
15042 VerifyBECountUsers(
false);
15043 VerifyBECountUsers(
true);
15046 for (
auto &[S,
Values] : LoopDispositions) {
15047 for (
auto [
Loop, CachedDisposition] :
Values) {
15049 if (CachedDisposition != RecomputedDisposition) {
15050 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
15051 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
15052 << RecomputedDisposition <<
"\n";
15059 for (
auto &[S,
Values] : BlockDispositions) {
15060 for (
auto [BB, CachedDisposition] :
Values) {
15062 if (CachedDisposition != RecomputedDisposition) {
15063 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
15064 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
15065 <<
", actual " << RecomputedDisposition <<
"\n";
15072 for (
auto [
FoldID, Expr] : FoldCache) {
15073 auto I = FoldCacheUser.find(Expr);
15074 if (
I == FoldCacheUser.end()) {
15075 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
15080 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
15084 for (
auto [Expr, IDs] : FoldCacheUser) {
15085 for (
auto &
FoldID : IDs) {
15088 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
15093 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
15094 <<
" != " << *Expr <<
"!\n";
15105 for (
auto [S, Multiple] : ConstantMultipleCache) {
15107 if ((Multiple != 0 && RecomputedMultiple != 0 &&
15108 Multiple.
urem(RecomputedMultiple) != 0 &&
15109 RecomputedMultiple.
urem(Multiple) != 0)) {
15110 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
15111 << *S <<
" : Computed " << RecomputedMultiple
15112 <<
" but cache contains " << Multiple <<
"!\n";
15120 FunctionAnalysisManager::Invalidator &Inv) {
15152 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15153 <<
F.getName() <<
"':\n";
15159 "Scalar Evolution Analysis",
false,
true)
15208 const SCEV *LHS,
const SCEV *RHS) {
15210 assert(LHS->getType() == RHS->getType() &&
15211 "Type mismatch between LHS and RHS");
15214 ID.AddInteger(Pred);
15215 ID.AddPointer(LHS);
15216 ID.AddPointer(RHS);
15217 void *IP =
nullptr;
15218 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
15222 UniquePreds.InsertNode(Eq, IP);
15233 ID.AddInteger(AddedFlags);
15234 void *IP =
nullptr;
15235 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
15237 auto *OF =
new (SCEVAllocator)
15239 UniquePreds.InsertNode(OF, IP);
15259 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15260 return Rewriter.visit(S);
15266 for (
const auto *Pred : U->getPredicates())
15268 if (IPred->getLHS() == Expr &&
15270 return IPred->getRHS();
15272 if (IPred->getLHS() == Expr &&
15273 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15274 return IPred->getRHS();
15277 return convertToAddRecWithPreds(Expr);
15280 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15296 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15313 explicit SCEVPredicateRewriter(
15314 const Loop *L, ScalarEvolution &SE,
15315 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15316 const SCEVPredicate *Pred)
15317 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15319 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15322 return Pred && Pred->
implies(
P, SE);
15328 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15331 return addOverflowAssumption(
A);
15340 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15344 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15346 if (!PredicatedRewrite)
15348 for (
const auto *
P : PredicatedRewrite->second){
15351 if (L != WP->getExpr()->getLoop())
15354 if (!addOverflowAssumption(
P))
15357 return PredicatedRewrite->first;
15360 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15361 const SCEVPredicate *Pred;
15370 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15377 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15397 if (!Step->
isOne())
15422 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15423 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15436 return Op->LHS == LHS &&
Op->RHS == RHS;
15443 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15445 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15470 const SCEV *Start = AR->getStart();
15471 const SCEV *OpStart =
Op->AR->getStart();
15476 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15485 const SCEV *Step = AR->getStepRecurrence(SE);
15486 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15539 if (Step->getValue()->getValue().isNonNegative())
15543 return ImpliedFlags;
15550 for (
const auto *
P : Preds)
15563 return this->implies(I, SE);
15575 const Loop *L = NWrap->getExpr()->getLoop();
15582 return RewrittenAR &&
15588 for (
const auto *Pred : Preds)
15589 Pred->print(OS,
Depth);
15594 for (
const auto *Pred : Set->Preds)
15602 bool CheckImplies = Preds.
size() < 16;
15605 if (CheckImplies &&
implies(
N, SE))
15611 for (
auto *
P : Preds) {
15612 if (CheckImplies &&
N->implies(
P, SE))
15616 Preds = std::move(PrunedPreds);
15617 Preds.push_back(
N);
15624 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15629 for (
const auto *
Op :
Ops)
15634 SCEVUsers[
Op].insert(
User);
15643 SCEVUsers[
Op].insert(
User);
15647 const SCEV *Expr = SE.getSCEV(V);
15652 RewriteEntry &Entry = RewriteMap[Expr];
15655 if (Entry.second && Generation == Entry.first)
15656 return Entry.second;
15661 Expr = Entry.second;
15663 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15664 Entry = {Generation, NewSCEV};
15670 if (!BackedgeCount) {
15672 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15673 for (
const auto *
P : Preds)
15676 return BackedgeCount;
15680 if (!SymbolicMaxBackedgeCount) {
15682 SymbolicMaxBackedgeCount =
15683 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15684 for (
const auto *
P : Preds)
15687 return SymbolicMaxBackedgeCount;
15691 if (!SmallConstantMaxTripCount) {
15693 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15694 for (
const auto *
P : Preds)
15697 return *SmallConstantMaxTripCount;
15701 if (Preds->implies(&Pred, SE))
15706 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15707 updateGeneration();
15720void PredicatedScalarEvolution::updateGeneration() {
15722 if (++Generation == 0) {
15723 for (
auto &
II : RewriteMap) {
15724 const SCEV *Rewritten =
II.second.second;
15746 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15752 ExtraPreds->
append(NewPreds);
15758 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15764 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15767 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15771 for (
auto *BB : L.getBlocks())
15772 for (
auto &
I : *BB) {
15773 if (!SE.isSCEVable(
I.getType()))
15776 auto *Expr = SE.getSCEV(&
I);
15777 auto II = RewriteMap.find(Expr);
15779 if (
II == RewriteMap.end())
15783 if (
II->second.second == Expr)
15788 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15796 LoopGuards Guards(SE);
15804void ScalarEvolution::LoopGuards::collectFromPHI(
15812 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15813 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15827 auto &RewriteMap =
G->second.RewriteMap;
15828 if (RewriteMap.empty())
15830 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15831 if (S == RewriteMap.end())
15837 return {C0,
SM->getSCEVType()};
15840 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15841 MinMaxPattern
P2) -> MinMaxPattern {
15842 auto [C1,
T1] =
P1;
15843 auto [C2, T2] =
P2;
15844 if (!C1 || !C2 ||
T1 != T2)
15848 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15850 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15852 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15854 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15859 auto P = GetMinMaxConst(0);
15860 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15863 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15866 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15869 Guards.RewriteMap.insert({
LHS,
RHS});
15877 const APInt &DivisorVal,
15879 const APInt *ExprVal;
15892 const APInt &DivisorVal,
15894 const APInt *ExprVal;
15902 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15916 const SCEV *URemRHS =
nullptr;
15920 const SCEV *Multiple =
15922 DivInfo[URemLHS] = Multiple;
15924 Multiples[URemLHS] =
C->getAPInt();
15944 auto IsMinMaxSCEVWithNonNegativeConstant =
15948 if (
MinMax->getNumOperands() != 2)
15951 if (
C->getAPInt().isNegative())
15953 SCTy =
MinMax->getSCEVType();
15962 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15964 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15969 auto *DivisibleExpr =
15977void ScalarEvolution::LoopGuards::collectFromBlock(
15979 const BasicBlock *
Block,
const BasicBlock *Pred,
15987 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15998 &ExprsToRewrite]() {
15999 const SCEVConstant *C1;
16012 if (ExactRegion.isWrappedSet() || ExactRegion.isFullSet())
16014 auto [
I,
Inserted] = RewriteMap.try_emplace(LHSUnknown);
16015 const SCEV *RewrittenLHS =
Inserted ? LHSUnknown :
I->second;
16023 if (MatchRangeCheckIdiom())
16040 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
16042 if (From == FromRewritten)
16044 RewriteMap[From] = To;
16050 auto GetMaybeRewritten = [&](
const SCEV *S) {
16051 return RewriteMap.lookup_or(S, S);
16054 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
16056 const APInt &DividesBy =
16071 switch (Predicate) {
16100 SmallPtrSet<const SCEV *, 16> Visited;
16102 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
16106 while (!Worklist.
empty()) {
16110 if (!Visited.
insert(From).second)
16112 const SCEV *FromRewritten = GetMaybeRewritten(From);
16113 const SCEV *To =
nullptr;
16115 switch (Predicate) {
16120 EnqueueOperands(
UMax);
16126 EnqueueOperands(
SMax);
16132 EnqueueOperands(
UMin);
16138 EnqueueOperands(
SMin);
16146 const SCEV *OneAlignedUp =
16148 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16160 const SCEVConstant *
C;
16169 Guards.NotEqual.insert({
LHS,
RHS});
16178 AddRewrite(From, FromRewritten, To);
16195 SE.F.
getParent(), Intrinsic::experimental_guard);
16197 for (
const auto *GU : GuardDecl->users())
16199 if (Guard->getFunction() ==
Block->getParent() &&
16208 unsigned NumCollectedConditions = 0;
16210 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16212 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16214 const CondBrInst *LoopEntryPredicate =
16216 if (!LoopEntryPredicate)
16221 NumCollectedConditions++;
16225 if (
Depth > 0 && NumCollectedConditions == 2)
16233 if (Pair.second->hasNPredecessorsOrMore(2) &&
16235 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16236 for (
auto &Phi : Pair.second->phis())
16247 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16248 SmallVector<Value *, 8> Worklist;
16249 SmallPtrSet<Value *, 8> Visited;
16251 while (!Worklist.
empty()) {
16258 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16282 DenseMap<const SCEV *, APInt> Multiples;
16284 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16291 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16292 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16296 for (
const auto &[K, Divisor] : Multiples) {
16297 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16298 Guards.RewriteMap[
K] =
16300 Guards.
rewrite(K), Divisor, SE),
16309 Guards.PreserveNUW =
true;
16310 Guards.PreserveNSW =
true;
16311 for (
const SCEV *Expr : ExprsToRewrite) {
16312 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16313 Guards.PreserveNUW &=
16315 Guards.PreserveNSW &=
16322 if (ExprsToRewrite.size() > 1) {
16323 for (
const SCEV *Expr : ExprsToRewrite) {
16324 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16325 Guards.RewriteMap.erase(Expr);
16326 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16335 class SCEVLoopGuardRewriter
16346 NotEqual(Guards.NotEqual) {
16347 if (Guards.PreserveNUW)
16349 if (Guards.PreserveNSW)
16356 return Map.lookup_or(Expr, Expr);
16360 if (
const SCEV *S = Map.lookup(Expr))
16367 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16368 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16369 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16371 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16372 if (
const SCEV *S = Map.lookup(NarrowExt))
16373 return SE.getZeroExtendExpr(S, Ty);
16374 Bitwidth = Bitwidth / 2;
16382 if (
const SCEV *S = Map.lookup(Expr))
16389 if (
const SCEV *S = Map.lookup(Expr))
16395 if (
const SCEV *S = Map.lookup(Expr))
16403 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16408 if (NotEqual.contains({LHS, RHS})) {
16410 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16411 return SE.getUMaxExpr(OneAlignedUp, S);
16418 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16429 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16430 return SE.getAddExpr(
16433 if (
const SCEV *S = Map.lookup(
Add))
16434 return SE.getAddExpr(Expr->
getOperand(0), S);
16446 : SE.getAddExpr(Operands,
16462 : SE.getMulExpr(Operands,
16468 if (RewriteMap.empty() && NotEqual.empty())
16471 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16472 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.
void setHighBits(unsigned hiBits)
Set the top hiBits bits.
LLVM_ABI APInt getHiBits(unsigned numBits) const
Compute an APInt containing numBits highbits from this APInt.
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)
IntrinsicID_match m_Intrinsic()
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
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.
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
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 >
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.
bool isNonNegative() const
Returns true if this value is known to be non-negative.
static LLVM_ABI KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for ashr(LHS, RHS).
unsigned getBitWidth() const
Get the bit width of this value.
static LLVM_ABI KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for lshr(LHS, RHS).
KnownBits zextOrTrunc(unsigned BitWidth) const
Return known bits for a zero extension or truncation of the value we're tracking.
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
APInt getMinValue() const
Return the minimal unsigned value possible given these KnownBits.
bool isNegative() const
Returns true if this value is known to be negative.
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