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");
1190 Op, *
this, IntPtrTy, [
this, IntPtrTy](
const SCEVUnknown *U) {
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)
2917 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2918 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2921 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp)
2922 if (MulOpSCEV ==
Ops[AddOp]) {
2924 const SCEV *InnerMul =
Mul->getOperand(MulOp == 0);
2925 if (
Mul->getNumOperands() != 2) {
2932 const SCEV *AddOne =
2936 if (
Ops.size() == 2)
return OuterMul;
2938 Ops.erase(
Ops.begin()+AddOp);
2939 Ops.erase(
Ops.begin()+Idx-1);
2941 Ops.erase(
Ops.begin()+Idx);
2942 Ops.erase(
Ops.begin()+AddOp-1);
2944 Ops.push_back(OuterMul);
2949 for (
unsigned OtherMulIdx = Idx+1;
2956 OMulOp != e; ++OMulOp)
2957 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2959 const SCEV *InnerMul1 =
Mul->getOperand(MulOp == 0);
2960 if (
Mul->getNumOperands() != 2) {
2968 OtherMul->
operands().take_front(OMulOp));
2972 const SCEV *InnerMulSum =
2976 if (
Ops.size() == 2)
return OuterMul;
2977 Ops.erase(
Ops.begin()+Idx);
2978 Ops.erase(
Ops.begin()+OtherMulIdx-1);
2979 Ops.push_back(OuterMul);
2999 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3002 Ops.erase(
Ops.begin()+i);
3007 if (!LIOps.
empty()) {
3032 auto *DefI = getDefiningScopeBound(LIOps);
3034 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
3046 if (
Ops.size() == 1)
return NewRec;
3049 for (
unsigned i = 0;; ++i)
3050 if (
Ops[i] == AddRec) {
3060 for (
unsigned OtherIdx = Idx+1;
3068 "AddRecExprs are not sorted in reverse dominance order?");
3075 if (OtherAddRec->getLoop() == AddRecLoop) {
3076 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
3078 if (i >= AddRecOps.
size()) {
3079 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
3083 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
3086 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3101 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
3112 static_cast<SCEVAddExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3116 S =
new (SCEVAllocator)
3118 UniqueSCEVs.InsertNode(S, IP);
3129 FoldingSetNodeID
ID;
3131 for (
const SCEV *
Op :
Ops)
3136 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3140 S =
new (SCEVAllocator)
3141 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3142 UniqueSCEVs.InsertNode(S, IP);
3144 LoopUsers[
L].push_back(S);
3153 FoldingSetNodeID
ID;
3155 for (
const SCEV *
Op :
Ops)
3159 static_cast<SCEVMulExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3163 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3165 UniqueSCEVs.InsertNode(S, IP);
3175 if (j > 1 && k / j != i) Overflow =
true;
3191 if (n == 0 || n == k)
return 1;
3192 if (k > n)
return 0;
3198 for (
uint64_t i = 1; i <= k; ++i) {
3199 r =
umul_ov(r, n-(i-1), Overflow);
3208 struct FindConstantInAddMulChain {
3209 bool FoundConstant =
false;
3211 bool follow(
const SCEV *S) {
3216 bool isDone()
const {
3217 return FoundConstant;
3221 FindConstantInAddMulChain
F;
3223 ST.visitAll(StartExpr);
3224 return F.FoundConstant;
3232 "only nuw or nsw allowed");
3233 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3234 if (
Ops.size() == 1)
return Ops[0];
3236 Type *ETy =
Ops[0]->getType();
3238 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3240 "SCEVMulExpr operand types don't match!");
3245 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3246 [](
const APInt &
C) {
return C.isOne(); },
3247 [](
const APInt &
C) {
return C.isZero(); });
3258 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3263 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3264 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3269 if (
Ops.size() == 2) {
3277 const SCEV *Op0, *Op1;
3285 if (
Ops[0]->isAllOnesValue()) {
3290 bool AnyFolded =
false;
3291 for (
const SCEV *AddOp :
Add->operands()) {
3311 if (AddRec->hasNoSignedWrap()) {
3318 AddRec->getNoWrapFlags(FlagsMask));
3341 APInt C1V = LHSC->getAPInt();
3351 const SCEV *NewMul =
nullptr;
3355 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3370 if (Idx <
Ops.size()) {
3371 bool DeletedMul =
false;
3377 Ops.erase(
Ops.begin()+Idx);
3401 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3404 Ops.erase(
Ops.begin()+i);
3409 if (!LIOps.
empty()) {
3422 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3438 if (
Ops.size() == 1)
return NewRec;
3441 for (
unsigned i = 0;; ++i)
3442 if (
Ops[i] == AddRec) {
3463 bool OpsModified =
false;
3464 for (
unsigned OtherIdx = Idx+1;
3478 bool Overflow =
false;
3485 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3489 z < ze && !Overflow; ++z) {
3492 if (LargerThan64Bits)
3493 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3495 Coeff = Coeff1*Coeff2;
3510 if (
Ops.size() == 2)
return NewAddRec;
3511 Ops[Idx] = NewAddRec;
3512 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3528 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3535 "SCEVURemExpr operand types don't match!");
3540 if (RHSC->getValue()->isOne())
3541 return getZero(LHS->getType());
3544 if (RHSC->getAPInt().isPowerOf2()) {
3545 Type *FullTy = LHS->getType();
3561 assert(!LHS->getType()->isPointerTy() &&
3562 "SCEVUDivExpr operand can't be pointer!");
3563 assert(LHS->getType() == RHS->getType() &&
3564 "SCEVUDivExpr operand types don't match!");
3571 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3579 if (RHSC->getValue()->isOne())
3584 if (!RHSC->getValue()->isZero()) {
3588 Type *Ty = LHS->getType();
3589 unsigned LZ = RHSC->getAPInt().countl_zero();
3593 if (!RHSC->getAPInt().isPowerOf2())
3601 const APInt &StepInt = Step->getAPInt();
3602 const APInt &DivInt = RHSC->getAPInt();
3603 if (!StepInt.
urem(DivInt) &&
3609 for (
const SCEV *
Op : AR->operands())
3615 const APInt *StartRem;
3628 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3632 const SCEV *NewStart =
3634 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3636 const SCEV *NewLHS =
3639 if (LHS != NewLHS) {
3649 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3658 for (
const SCEV *
Op : M->operands())
3662 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3663 const SCEV *
Op = M->getOperand(i);
3690 if (
auto *DivisorConstant =
3692 bool Overflow =
false;
3694 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3705 for (
const SCEV *
Op :
A->operands())
3709 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3716 if (Operands.
size() ==
A->getNumOperands())
3728 const APInt &
N = RHSC->getAPInt();
3729 const APInt *NMinusM, *M;
3733 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3734 *NMinusM ==
N - *M) {
3743 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3753 return getZero(LHS->getType());
3757 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3758 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3759 if (
Mul->getOperand(i) == RHS) {
3770 const SCEV *NewLHS, *NewRHS;
3778 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
3781 UniqueSCEVs.InsertNode(S, IP);
3818 if (StepChrec->getLoop() == L) {
3832 if (Operands.
size() == 1)
return Operands[0];
3837 "SCEVAddRecExpr operand types don't match!");
3838 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3840 for (
const SCEV *
Op : Operands)
3842 "SCEVAddRecExpr operand is not available at loop entry!");
3845 if (Operands.
back()->isZero()) {
3860 const Loop *NestedLoop = NestedAR->getLoop();
3861 if (L->contains(NestedLoop)
3864 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3866 Operands[0] = NestedAR->getStart();
3870 bool AllInvariant =
all_of(
3882 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3893 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3897 Operands[0] = NestedAR;
3903 return getOrCreateAddRecExpr(Operands, L, Flags);
3919 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3923 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3937 bool FirstIter =
true;
3939 for (
SCEVUse IndexExpr : IndexExprs) {
3946 Offsets.push_back(FieldOffset);
3949 CurTy = STy->getTypeAtIndex(Index);
3954 "The first index of a GEP indexes a pointer");
3955 CurTy = SrcElementTy;
3966 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3967 Offsets.push_back(LocalOffset);
3972 if (Offsets.empty())
3985 "GEP should not change type mid-flight.");
3989SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3992 ID.AddInteger(SCEVType);
3996 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3999SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
4002 ID.AddInteger(SCEVType);
4006 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4016 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
4017 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4018 if (
Ops.size() == 1)
return Ops[0];
4021 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4023 "Operand types don't match!");
4026 "min/max should be consistently pointerish");
4052 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
4054 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
4059 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
4061 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
4067 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
4073 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
4078 if (Idx <
Ops.size()) {
4079 bool DeletedAny =
false;
4080 while (
Ops[Idx]->getSCEVType() == Kind) {
4082 Ops.erase(
Ops.begin()+Idx);
4100 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
4101 if (
Ops[i] ==
Ops[i + 1] ||
4102 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
4105 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
4108 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
4111 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
4117 if (
Ops.size() == 1)
return Ops[0];
4119 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
4124 ID.AddInteger(Kind);
4128 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4130 return ExistingSCEV;
4133 SCEV *S =
new (SCEVAllocator)
4136 UniqueSCEVs.InsertNode(S, IP);
4144class SCEVSequentialMinMaxDeduplicatingVisitor final
4145 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4146 std::optional<const SCEV *>> {
4147 using RetVal = std::optional<const SCEV *>;
4155 bool canRecurseInto(
SCEVTypes Kind)
const {
4158 return RootKind == Kind || NonSequentialRootKind == Kind;
4161 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
4163 "Only for min/max expressions.");
4166 if (!canRecurseInto(Kind))
4176 return std::nullopt;
4183 RetVal
visit(
const SCEV *S) {
4185 if (!SeenOps.
insert(S).second)
4186 return std::nullopt;
4187 return Base::visit(S);
4191 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4193 : SE(SE), RootKind(RootKind),
4194 NonSequentialRootKind(
4195 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4199 SmallVectorImpl<SCEVUse> &NewOps) {
4204 for (
const SCEV *
Op : OrigOps) {
4209 Ops.emplace_back(*NewOp);
4213 NewOps = std::move(
Ops);
4217 RetVal visitConstant(
const SCEVConstant *Constant) {
return Constant; }
4219 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4221 RetVal visitPtrToAddrExpr(
const SCEVPtrToAddrExpr *Expr) {
return Expr; }
4223 RetVal visitPtrToIntExpr(
const SCEVPtrToIntExpr *Expr) {
return Expr; }
4225 RetVal visitTruncateExpr(
const SCEVTruncateExpr *Expr) {
return Expr; }
4227 RetVal visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
return Expr; }
4229 RetVal visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
return Expr; }
4231 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4233 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4235 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4237 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4239 RetVal visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
4240 return visitAnyMinMaxExpr(Expr);
4243 RetVal visitUMaxExpr(
const SCEVUMaxExpr *Expr) {
4244 return visitAnyMinMaxExpr(Expr);
4247 RetVal visitSMinExpr(
const SCEVSMinExpr *Expr) {
4248 return visitAnyMinMaxExpr(Expr);
4251 RetVal visitUMinExpr(
const SCEVUMinExpr *Expr) {
4252 return visitAnyMinMaxExpr(Expr);
4255 RetVal visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *Expr) {
4256 return visitAnyMinMaxExpr(Expr);
4259 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4261 RetVal visitCouldNotCompute(
const SCEVCouldNotCompute *Expr) {
return Expr; }
4304struct SCEVPoisonCollector {
4305 bool LookThroughMaybePoisonBlocking;
4306 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4307 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4308 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4310 bool follow(
const SCEV *S) {
4311 if (!LookThroughMaybePoisonBlocking &&
4321 bool isDone()
const {
return false; }
4331 SCEVPoisonCollector PC1(
true);
4336 if (PC1.MaybePoison.empty())
4342 SCEVPoisonCollector PC2(
false);
4352 SCEVPoisonCollector PC(
false);
4375 while (!Worklist.
empty()) {
4377 if (!Visited.
insert(V).second)
4381 if (Visited.
size() > 16)
4386 if (PoisonVals.
contains(V) || ::isGuaranteedNotToBePoison(V))
4397 if (PDI->isDisjoint())
4404 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4411 if (
I->hasPoisonGeneratingAnnotations())
4422 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4423 "Not a SCEVSequentialMinMaxExpr!");
4424 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4425 if (
Ops.size() == 1)
4429 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4431 "Operand types don't match!");
4434 "min/max should be consistently pointerish");
4442 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4449 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4459 bool DeletedAny =
false;
4460 while (Idx <
Ops.size()) {
4461 if (
Ops[Idx]->getSCEVType() != Kind) {
4466 Ops.erase(
Ops.begin() + Idx);
4467 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4468 SMME->operands().end());
4476 const SCEV *SaturationPoint;
4487 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4488 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4500 Ops.erase(
Ops.begin() + i);
4505 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4506 Ops.erase(
Ops.begin() + i);
4514 ID.AddInteger(Kind);
4518 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4520 return ExistingSCEV;
4524 SCEV *S =
new (SCEVAllocator)
4527 UniqueSCEVs.InsertNode(S, IP);
4575 if (
Size.isScalable())
4596 "Cannot get offset for structure containing scalable vector types");
4610 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP)) {
4612 "Stale SCEVUnknown in uniquing map!");
4618 UniqueSCEVs.InsertNode(S, IP);
4633 return Ty->isIntOrPtrTy();
4640 if (Ty->isPointerTy())
4651 if (Ty->isIntegerTy())
4655 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4667 bool PreciseA, PreciseB;
4668 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4669 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4670 if (!PreciseA || !PreciseB)
4673 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4674 DT.dominates(ScopeB, ScopeA);
4678 return CouldNotCompute.get();
4681bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4684 return SU && SU->getValue() ==
nullptr;
4687 return !ContainsNulls;
4692 if (
I != HasRecMap.end())
4697 HasRecMap.insert({S, FoundAddRec});
4705 if (
SI == ExprValueMap.
end())
4707 return SI->second.getArrayRef();
4713void ScalarEvolution::eraseValueFromMap(
Value *V) {
4715 if (
I != ValueExprMap.end()) {
4716 auto EVIt = ExprValueMap.find(
I->second);
4717 bool Removed = EVIt->second.remove(V);
4719 assert(Removed &&
"Value not in ExprValueMap?");
4720 ValueExprMap.erase(
I);
4724void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4728 auto It = ValueExprMap.find_as(V);
4729 if (It == ValueExprMap.end()) {
4731 ExprValueMap[S].insert(V);
4742 return createSCEVIter(V);
4749 if (
I != ValueExprMap.end()) {
4750 const SCEV *S =
I->second;
4751 assert(checkValidity(S) &&
4752 "existing SCEV has not been properly invalidated");
4765 Type *Ty = V->getType();
4781 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4794 return (
const SCEV *)
nullptr;
4800 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4804 Type *Ty = V->getType();
4810 assert(
P->getType()->isPointerTy());
4825 if (AddOp->getType()->isPointerTy()) {
4826 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4844 return getZero(LHS->getType());
4849 if (RHS->getType()->isPointerTy()) {
4850 if (!LHS->getType()->isPointerTy() ||
4860 const bool RHSIsNotMinSigned =
4891 Type *SrcTy = V->getType();
4892 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4893 "Cannot truncate or zero extend with non-integer arguments!");
4903 Type *SrcTy = V->getType();
4904 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4905 "Cannot truncate or zero extend with non-integer arguments!");
4915 Type *SrcTy = V->getType();
4916 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4917 "Cannot noop or zero extend with non-integer arguments!");
4919 "getNoopOrZeroExtend cannot truncate!");
4927 Type *SrcTy = V->getType();
4928 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4929 "Cannot noop or sign extend with non-integer arguments!");
4931 "getNoopOrSignExtend cannot truncate!");
4939 Type *SrcTy = V->getType();
4940 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4941 "Cannot noop or any extend with non-integer arguments!");
4943 "getNoopOrAnyExtend cannot truncate!");
4951 Type *SrcTy = V->getType();
4952 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4953 "Cannot truncate or noop with non-integer arguments!");
4955 "getTruncateOrNoop cannot extend!");
4963 const SCEV *PromotedLHS = LHS;
4964 const SCEV *PromotedRHS = RHS;
4984 assert(!
Ops.empty() &&
"At least one operand must be!");
4986 if (
Ops.size() == 1)
4990 Type *MaxType =
nullptr;
4996 assert(MaxType &&
"Failed to find maximum type!");
5009 if (!V->getType()->isPointerTy())
5014 V = AddRec->getStart();
5016 const SCEV *PtrOp =
nullptr;
5017 for (
const SCEV *AddOp :
Add->operands()) {
5018 if (AddOp->getType()->isPointerTy()) {
5019 assert(!PtrOp &&
"Cannot have multiple pointer ops");
5023 assert(PtrOp &&
"Must have pointer op");
5035 for (
User *U :
I->users()) {
5037 if (Visited.
insert(UserInsn).second)
5051 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
5052 bool IgnoreOtherLoops =
true) {
5055 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
5057 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
5062 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5064 SeenLoopVariantSCEVUnknown =
true;
5068 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5072 SeenOtherLoops =
true;
5076 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
5078 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
5081 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
5082 : SCEVRewriteVisitor(SE),
L(
L) {}
5085 bool SeenLoopVariantSCEVUnknown =
false;
5086 bool SeenOtherLoops =
false;
5095 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
5096 SCEVPostIncRewriter
Rewriter(L, SE);
5098 return Rewriter.hasSeenLoopVariantSCEVUnknown()
5103 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5105 SeenLoopVariantSCEVUnknown =
true;
5109 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5113 SeenOtherLoops =
true;
5117 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
5119 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
5122 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
5123 : SCEVRewriteVisitor(SE),
L(
L) {}
5126 bool SeenLoopVariantSCEVUnknown =
false;
5127 bool SeenOtherLoops =
false;
5133class SCEVBackedgeConditionFolder
5136 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5137 ScalarEvolution &SE) {
5138 bool IsPosBECond =
false;
5139 Value *BECond =
nullptr;
5140 if (BasicBlock *Latch =
L->getLoopLatch()) {
5142 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
5143 "Both outgoing branches should not target same header!");
5144 BECond = BI->getCondition();
5145 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
5150 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
5154 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5155 const SCEV *
Result = Expr;
5160 switch (
I->getOpcode()) {
5161 case Instruction::Select: {
5163 std::optional<const SCEV *> Res =
5164 compareWithBackedgeCondition(
SI->getCondition());
5172 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5183 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5184 bool IsPosBECond, ScalarEvolution &SE)
5185 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5186 IsPositiveBECond(IsPosBECond) {}
5188 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5192 Value *BackedgeCond =
nullptr;
5194 bool IsPositiveBECond;
5197std::optional<const SCEV *>
5198SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5203 if (BackedgeCond == IC)
5206 return std::nullopt;
5211 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5212 ScalarEvolution &SE) {
5218 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5225 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5235 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5236 : SCEVRewriteVisitor(SE),
L(
L) {}
5245ScalarEvolution::proveNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5249 using OBO = OverflowingBinaryOperator;
5257 const APInt &BECountAP = BECountMax->getAPInt();
5258 unsigned NoOverflowBitWidth =
5270 Instruction::Add, IncRange, OBO::NoSignedWrap);
5271 if (NSWRegion.contains(AddRecRange))
5280 Instruction::Add, IncRange, OBO::NoUnsignedWrap);
5281 if (NUWRegion.contains(AddRecRange))
5289ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5299 if (!SignedWrapViaInductionTried.insert(AR).second)
5324 AC.assumptions().empty())
5332 const SCEV *OverflowLimit =
5334 if (OverflowLimit &&
5342ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5352 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5378 AC.assumptions().empty())
5413 explicit BinaryOp(Operator *
Op)
5417 IsNSW = OBO->hasNoSignedWrap();
5418 IsNUW = OBO->hasNoUnsignedWrap();
5422 explicit BinaryOp(
unsigned Opcode,
Value *
LHS,
Value *
RHS,
bool IsNSW =
false,
5424 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5436 return std::nullopt;
5442 switch (
Op->getOpcode()) {
5443 case Instruction::Add:
5444 case Instruction::Sub:
5445 case Instruction::Mul:
5446 case Instruction::UDiv:
5447 case Instruction::URem:
5448 case Instruction::And:
5449 case Instruction::AShr:
5450 case Instruction::Shl:
5451 return BinaryOp(
Op);
5453 case Instruction::Or: {
5456 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5463 return BinaryOp(
Op);
5466 case Instruction::Xor:
5470 if (RHSC->getValue().isSignMask())
5471 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5473 if (V->getType()->isIntegerTy(1))
5474 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5475 return BinaryOp(
Op);
5477 case Instruction::LShr:
5486 if (SA->getValue().ult(
BitWidth)) {
5488 ConstantInt::get(SA->getContext(),
5490 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5493 return BinaryOp(
Op);
5495 case Instruction::ExtractValue: {
5497 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5505 bool Signed = WO->isSigned();
5508 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5513 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5524 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5525 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5527 return std::nullopt;
5553 if (
Op == SymbolicPHI)
5558 if (SourceBits != NewBits)
5576 if (!L || L->getHeader() != PN->
getParent())
5634std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5635ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5643 assert(L &&
"Expecting an integer loop header phi");
5648 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5649 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5650 Value *
V = PN->getIncomingValue(i);
5651 if (
L->contains(PN->getIncomingBlock(i))) {
5654 }
else if (BEValueV != V) {
5658 }
else if (!StartValueV) {
5660 }
else if (StartValueV != V) {
5661 StartValueV =
nullptr;
5665 if (!BEValueV || !StartValueV)
5666 return std::nullopt;
5668 const SCEV *BEValue =
getSCEV(BEValueV);
5675 return std::nullopt;
5679 unsigned FoundIndex =
Add->getNumOperands();
5680 Type *TruncTy =
nullptr;
5682 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5685 if (FoundIndex == e) {
5690 if (FoundIndex ==
Add->getNumOperands())
5691 return std::nullopt;
5695 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5696 if (i != FoundIndex)
5697 Ops.push_back(
Add->getOperand(i));
5703 return std::nullopt;
5756 const SCEV *StartVal =
getSCEV(StartValueV);
5757 const SCEV *PHISCEV =
5784 auto getExtendedExpr = [&](
const SCEV *Expr,
5785 bool CreateSignExtend) ->
const SCEV * {
5788 const SCEV *ExtendedExpr =
5791 return ExtendedExpr;
5799 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5800 const SCEV *ExtendedExpr) ->
bool {
5801 return Expr != ExtendedExpr &&
5805 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5806 if (PredIsKnownFalse(StartVal, StartExtended)) {
5808 return std::nullopt;
5813 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5814 if (PredIsKnownFalse(Accum, AccumExtended)) {
5816 return std::nullopt;
5819 auto AppendPredicate = [&](
const SCEV *Expr,
5820 const SCEV *ExtendedExpr) ->
void {
5821 if (Expr != ExtendedExpr &&
5829 AppendPredicate(StartVal, StartExtended);
5830 AppendPredicate(Accum, AccumExtended);
5838 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5839 std::make_pair(NewAR, Predicates);
5841 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5845std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5850 return std::nullopt;
5853 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5854 if (
I != PredicatedSCEVRewrites.end()) {
5855 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5858 if (Rewrite.first == SymbolicPHI)
5859 return std::nullopt;
5863 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5867 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5868 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5873 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5874 return std::nullopt;
5891 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5892 if (Expr1 != Expr2 &&
5893 !Preds->implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5894 !Preds->implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5911const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5913 Value *StartValueV) {
5916 assert(BEValueV && StartValueV);
5922 if (BO->Opcode != Instruction::Add)
5925 const SCEV *Accum =
nullptr;
5926 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5928 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5942 insertValueToMap(PN, PHISCEV);
5954 "Accum is defined outside L, but is not invariant?");
5955 if (isAddRecNeverPoison(BEInst, L))
5962const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5963 const Loop *
L = LI.getLoopFor(PN->
getParent());
5970 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5976 }
else if (BEValueV != V) {
5980 }
else if (!StartValueV) {
5982 }
else if (StartValueV != V) {
5983 StartValueV =
nullptr;
5987 if (!BEValueV || !StartValueV)
5990 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5991 "PHI node already processed?");
5995 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
6000 insertValueToMap(PN, SymbolicName);
6004 const SCEV *BEValue =
getSCEV(BEValueV);
6014 unsigned FoundIndex =
Add->getNumOperands();
6015 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
6016 if (
Add->getOperand(i) == SymbolicName)
6017 if (FoundIndex == e) {
6022 if (FoundIndex !=
Add->getNumOperands()) {
6025 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
6026 if (i != FoundIndex)
6027 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
6039 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
6046 if (
GEP->getOperand(0) == PN) {
6047 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
6065 const SCEV *StartVal =
getSCEV(StartValueV);
6066 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
6071 forgetMemoizedResults({SymbolicName});
6072 insertValueToMap(PN, PHISCEV);
6076 const_cast<SCEVAddRecExpr *
>(AR),
6102 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
6103 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
6105 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
6106 const SCEV *StartVal =
getSCEV(StartValueV);
6107 if (Start == StartVal) {
6111 forgetMemoizedResults({SymbolicName});
6112 insertValueToMap(PN, Shifted);
6122 eraseValueFromMap(PN);
6137 Use &LeftUse =
Merge->getOperandUse(0);
6138 Use &RightUse =
Merge->getOperandUse(1);
6174 assert(IDom &&
"At least the entry block should dominate PN");
6182const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
6187 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6204 CommonInst = IncomingInst;
6220ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6226 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6227 bool SCEVExprsIdentical =
6229 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6230 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6233const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6234 if (
const SCEV *S = createAddRecFromPHI(PN))
6244 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6247 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6256 struct FindClosure {
6257 const SCEV *OperandToFind;
6263 bool canRecurseInto(
SCEVTypes Kind)
const {
6266 return RootKind == Kind || NonSequentialRootKind == Kind ||
6271 : OperandToFind(OperandToFind), RootKind(RootKind),
6272 NonSequentialRootKind(
6276 bool follow(
const SCEV *S) {
6277 Found = S == OperandToFind;
6279 return !isDone() && canRecurseInto(S->
getSCEVType());
6282 bool isDone()
const {
return Found; }
6285 FindClosure FC(OperandToFind, RootKind);
6290std::optional<const SCEV *>
6291ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6301 switch (ICI->getPredicate()) {
6315 bool Signed = ICI->isSigned();
6316 const SCEV *LA =
getSCEV(TrueVal);
6324 if (LA == LS &&
RA == RS)
6326 if (LA == RS &&
RA == LS)
6329 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6330 if (
Op->getType()->isPointerTy()) {
6341 LS = CoerceOperand(LS);
6342 RS = CoerceOperand(RS);
6366 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6367 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6381 X = ZExt->getOperand();
6383 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6394 return std::nullopt;
6397static std::optional<const SCEV *>
6399 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6403 "Unexpected operands of a select.");
6415 return std::nullopt;
6430static std::optional<const SCEV *>
6434 return std::nullopt;
6437 const auto *SETrue = SE->
getSCEV(TrueVal);
6438 const auto *SEFalse = SE->
getSCEV(FalseVal);
6442const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6444 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6446 V->getType() ==
TrueVal->getType() &&
6447 "Types of select hands and of the result must match.");
6450 if (!
V->getType()->isIntegerTy(1))
6453 if (std::optional<const SCEV *> S =
6466 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6470 if (std::optional<const SCEV *> S =
6471 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6477 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6483 assert(
GEP->getSourceElementType()->isSized() &&
6484 "GEP source element type must be sized");
6487 for (
Value *Index :
GEP->indices())
6492APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6495 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6498 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6500 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6503 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6522 return GetShiftedByZeros(TZ);
6532 return GetShiftedByZeros(TZ);
6536 if (
M->hasNoUnsignedWrap()) {
6539 for (
const SCEV *Operand :
M->operands().drop_front())
6547 for (
const SCEV *Operand :
M->operands())
6549 return GetShiftedByZeros(TZ);
6554 if (
N->hasNoUnsignedWrap())
6555 return GetGCDMultiple(
N);
6558 for (
const SCEV *Operand :
N->operands().drop_front())
6560 return GetShiftedByZeros(TZ);
6577 CtxI = &*F.getEntryBlock().begin();
6584 .allowEphemerals(
true))
6585 .countMinTrailingZeros();
6586 return GetShiftedByZeros(Known);
6599 return getConstantMultipleImpl(S, CtxI);
6601 auto I = ConstantMultipleCache.find(S);
6602 if (
I != ConstantMultipleCache.end())
6605 APInt Result = getConstantMultipleImpl(S, CtxI);
6606 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6607 assert(InsertPair.second &&
"Should insert a new key");
6608 return InsertPair.first->second;
6625 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6628 if (std::optional<ConstantRange>
Range = CB->getRange())
6632 if (std::optional<ConstantRange>
Range =
A->getRange())
6635 return std::nullopt;
6642 UnsignedRanges.erase(AddRec);
6643 SignedRanges.erase(AddRec);
6644 ConstantMultipleCache.erase(AddRec);
6649getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6675 Value *Start, *Step;
6682 assert(L && L->getHeader() ==
P->getParent());
6695 case Instruction::AShr:
6696 case Instruction::LShr:
6697 case Instruction::Shl:
6712 KnownStep.getBitWidth() ==
BitWidth);
6715 auto MaxShiftAmt = KnownStep.getMaxValue();
6717 bool Overflow =
false;
6718 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6725 case Instruction::AShr: {
6733 if (KnownStart.isNonNegative())
6736 KnownStart.getMaxValue() + 1);
6737 if (KnownStart.isNegative())
6740 KnownEnd.getMaxValue() + 1);
6743 case Instruction::LShr: {
6752 KnownStart.getMaxValue() + 1);
6754 case Instruction::Shl: {
6758 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6759 return ConstantRange(KnownStart.getMinValue(),
6760 KnownEnd.getMaxValue() + 1);
6785 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6792ScalarEvolution::getRangeRefIter(
const SCEV *S,
6793 ScalarEvolution::RangeSignHint SignHint) {
6794 DenseMap<const SCEV *, ConstantRange> &Cache =
6795 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6798 SmallPtrSet<const SCEV *, 8> Seen;
6802 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6803 if (!Seen.
insert(Expr).second)
6837 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6838 const SCEV *
P = WorkList[
I];
6842 for (
const SCEV *
Op :
P->operands())
6855 if (!WorkList.
empty()) {
6860 getRangeRef(
P, SignHint);
6864 return getRangeRef(S, SignHint, 0);
6871 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6872 DenseMap<const SCEV *, ConstantRange> &Cache =
6873 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6880 auto I = Cache.
find(S);
6881 if (
I != Cache.
end())
6885 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6890 return getRangeRefIter(S, SignHint);
6893 ConstantRange ConservativeResult(
BitWidth,
true);
6894 using OBO = OverflowingBinaryOperator;
6898 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6902 ConservativeResult =
6909 ConservativeResult = ConstantRange(
6925 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6932 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6939 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6945 return setRange(Cast, SignHint,
X);
6950 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6951 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6953 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6954 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6955 ConservativeResult =
6956 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6958 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6959 unsigned WrapType = OBO::AnyWrap;
6960 if (
Add->hasNoSignedWrap())
6961 WrapType |= OBO::NoSignedWrap;
6962 if (
Add->hasNoUnsignedWrap())
6963 WrapType |= OBO::NoUnsignedWrap;
6965 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6967 return setRange(
Add, SignHint,
6968 ConservativeResult.intersectWith(
X, RangeType));
6972 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6974 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6975 return setRange(
Mul, SignHint,
6976 ConservativeResult.intersectWith(
X, RangeType));
6980 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6981 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6982 return setRange(UDiv, SignHint,
6983 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6991 if (!UnsignedMinValue.
isZero())
6992 ConservativeResult = ConservativeResult.intersectWith(
6993 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
7002 bool AllNonNeg =
true;
7003 bool AllNonPos =
true;
7004 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
7011 ConservativeResult = ConservativeResult.intersectWith(
7016 ConservativeResult = ConservativeResult.intersectWith(
7025 const SCEV *MaxBEScev =
7039 auto RangeFromAffine = getRangeForAffineAR(
7041 ConservativeResult =
7042 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
7044 auto RangeFromFactoring = getRangeViaFactoring(
7046 ConservativeResult =
7047 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
7053 const SCEV *SymbolicMaxBECount =
7058 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
7059 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
7060 ConservativeResult =
7061 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
7066 return setRange(AddRec, SignHint, std::move(ConservativeResult));
7076 ID = Intrinsic::umax;
7079 ID = Intrinsic::smax;
7083 ID = Intrinsic::umin;
7086 ID = Intrinsic::smin;
7093 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
7094 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
7096 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
7097 return setRange(S, SignHint,
7098 ConservativeResult.intersectWith(
X, RangeType));
7107 ConservativeResult =
7108 ConservativeResult.intersectWith(*MDRange, RangeType);
7113 auto CR = getRangeForUnknownRecurrence(U);
7114 ConservativeResult = ConservativeResult.intersectWith(CR);
7125 if (
U->getType()->isPointerTy()) {
7128 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
7129 int ptrIdxDiff = ptrSize -
BitWidth;
7130 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
7143 ConservativeResult = ConservativeResult.intersectWith(
7147 ConservativeResult = ConservativeResult.intersectWith(
7152 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
7155 bool CanBeNull, CanBeFreed;
7156 uint64_t DerefBytes =
7157 V->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed);
7167 uint64_t
Align =
U->getValue()->getPointerAlignment(DL).value();
7168 uint64_t Rem = MaxVal.
urem(Align);
7173 ConservativeResult = ConservativeResult.intersectWith(
7183 return getRangeRef(AR, SignHint,
Depth + 1);
7187 ConstantRange RangeFromOps(
BitWidth,
false);
7189 for (
const auto &
Op :
Phi->operands()) {
7191 RangeFromOps = RangeFromOps.unionWith(OpRange);
7193 if (RangeFromOps.isFullSet())
7196 ConservativeResult =
7197 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7203 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7205 ConservativeResult = ConservativeResult.difference(Disallowed);
7208 return setRange(U, SignHint, std::move(ConservativeResult));
7214 return setRange(S, SignHint, std::move(ConservativeResult));
7223 const APInt &MaxBECount,
7230 if (Step == 0 || MaxBECount == 0)
7237 return ConstantRange::getFull(
BitWidth);
7253 return ConstantRange::getFull(
BitWidth);
7265 APInt MovedBoundary = Descending ? (StartLower - std::move(
Offset))
7266 : (StartUpper + std::move(
Offset));
7271 if (StartRange.
contains(MovedBoundary))
7272 return ConstantRange::getFull(
BitWidth);
7275 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7277 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7286 const APInt &MaxBECount) {
7290 "mismatched bit widths");
7299 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7301 StartSRange, MaxBECount,
7313ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7315 ScalarEvolution::RangeSignHint SignHint) {
7316 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7318 "This only works for non-self-wrapping AddRecs!");
7319 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7323 return ConstantRange::getFull(
BitWidth);
7331 return ConstantRange::getFull(
BitWidth);
7335 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7337 MaxItersWithoutWrap))
7338 return ConstantRange::getFull(
BitWidth);
7359 ConstantRange StartRange = getRangeRef(Start, SignHint);
7360 ConstantRange EndRange = getRangeRef(End, SignHint);
7361 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7365 return RangeBetween;
7370 return ConstantRange::getFull(
BitWidth);
7373 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7374 return RangeBetween;
7376 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7377 return RangeBetween;
7378 return ConstantRange::getFull(
BitWidth);
7383 const APInt &MaxBECount) {
7390 "mismatched bit widths");
7392 struct SelectPattern {
7393 Value *Condition =
nullptr;
7397 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7399 std::optional<unsigned> CastOp;
7413 CastOp = SCast->getSCEVType();
7414 S = SCast->getOperand();
7417 using namespace llvm::PatternMatch;
7424 Condition =
nullptr;
7456 bool isRecognized() {
return Condition !=
nullptr; }
7459 SelectPattern StartPattern(*
this,
BitWidth, Start);
7460 if (!StartPattern.isRecognized())
7461 return ConstantRange::getFull(
BitWidth);
7463 SelectPattern StepPattern(*
this,
BitWidth, Step);
7464 if (!StepPattern.isRecognized())
7465 return ConstantRange::getFull(
BitWidth);
7467 if (StartPattern.Condition != StepPattern.Condition) {
7471 return ConstantRange::getFull(
BitWidth);
7482 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7483 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7484 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7485 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7487 ConstantRange TrueRange =
7488 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount);
7489 ConstantRange FalseRange =
7490 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount);
7502 PDI && PDI->isDisjoint()) {
7517ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7530 SmallPtrSet<const SCEV *, 16> Visited;
7532 auto pushOp = [&](
const SCEV *S) {
7533 if (!Visited.
insert(S).second)
7536 if (Visited.
size() > 30) {
7547 while (!Worklist.
empty()) {
7549 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7550 if (!Bound || DT.dominates(Bound, DefI))
7557 return Bound ? Bound : &*F.getEntryBlock().begin();
7563 return getDefiningScopeBound(
Ops, Discard);
7566bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7568 if (
A->getParent() ==
B->getParent() &&
7573 auto *BLoop = LI.getLoopFor(
B->getParent());
7574 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7575 BLoop->getLoopPreheader() ==
A->getParent() &&
7577 A->getParent()->end()) &&
7584bool ScalarEvolution::isGuaranteedNotToBePoison(
const SCEV *
Op) {
7585 SCEVPoisonCollector PC(
true);
7587 return PC.MaybePoison.empty();
7590bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7596 return M && (!
isKnownNonZero(Op1) || !isGuaranteedNotToBePoison(Op1));
7600bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7617 for (
const Use &
Op :
I->operands()) {
7623 auto *DefI = getDefiningScopeBound(SCEVOps);
7624 return isGuaranteedToTransferExecutionTo(DefI,
I);
7627bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7629 if (isSCEVExprNeverPoison(
I))
7640 auto *ExitingBB =
L->getExitingBlock();
7644 SmallPtrSet<const Value *, 16> KnownPoison;
7653 while (!Worklist.
empty()) {
7656 for (
const Use &U :
Poison->uses()) {
7659 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7663 if (KnownPoison.
insert(PoisonUser).second)
7671ScalarEvolution::LoopProperties
7672ScalarEvolution::getLoopProperties(
const Loop *L) {
7673 using LoopProperties = ScalarEvolution::LoopProperties;
7675 auto Itr = LoopPropertiesCache.find(L);
7676 if (Itr == LoopPropertiesCache.end()) {
7679 return !
SI->isSimple();
7689 return I->mayWriteToMemory();
7692 LoopProperties LP = {
true,
7695 for (
auto *BB :
L->getBlocks())
7696 for (
auto &
I : *BB) {
7698 LP.HasNoAbnormalExits =
false;
7699 if (HasSideEffects(&
I))
7700 LP.HasNoSideEffects =
false;
7701 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7705 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7706 assert(InsertPair.second &&
"We just checked!");
7707 Itr = InsertPair.first;
7720const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7726 Stack.emplace_back(V,
true);
7727 Stack.emplace_back(V,
false);
7728 while (!Stack.empty()) {
7729 auto E = Stack.pop_back_val();
7730 Value *CurV = E.getPointer();
7736 const SCEV *CreatedSCEV =
nullptr;
7739 CreatedSCEV = createSCEV(CurV);
7744 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7748 insertValueToMap(CurV, CreatedSCEV);
7752 Stack.emplace_back(CurV,
true);
7754 Stack.emplace_back(
Op,
false);
7771 if (!DT.isReachableFromEntry(
I->getParent()))
7784 switch (BO->Opcode) {
7785 case Instruction::Add:
7786 case Instruction::Mul: {
7793 Ops.push_back(BO->
Op);
7797 Ops.push_back(BO->RHS);
7801 (BO->Opcode == Instruction::Add &&
7802 (NewBO->Opcode != Instruction::Add &&
7803 NewBO->Opcode != Instruction::Sub)) ||
7804 (BO->Opcode == Instruction::Mul &&
7805 NewBO->Opcode != Instruction::Mul)) {
7806 Ops.push_back(BO->LHS);
7811 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7814 Ops.push_back(BO->LHS);
7822 case Instruction::Sub:
7823 case Instruction::UDiv:
7824 case Instruction::URem:
7826 case Instruction::AShr:
7827 case Instruction::Shl:
7828 case Instruction::Xor:
7832 case Instruction::And:
7833 case Instruction::Or:
7837 case Instruction::LShr:
7844 Ops.push_back(BO->LHS);
7845 Ops.push_back(BO->RHS);
7849 switch (
U->getOpcode()) {
7850 case Instruction::Trunc:
7851 case Instruction::ZExt:
7852 case Instruction::SExt:
7853 case Instruction::PtrToAddr:
7854 case Instruction::PtrToInt:
7855 Ops.push_back(
U->getOperand(0));
7858 case Instruction::BitCast:
7860 Ops.push_back(
U->getOperand(0));
7865 case Instruction::SDiv:
7866 case Instruction::SRem:
7867 Ops.push_back(
U->getOperand(0));
7868 Ops.push_back(
U->getOperand(1));
7871 case Instruction::GetElementPtr:
7873 "GEP source element type must be sized");
7877 case Instruction::IntToPtr:
7880 case Instruction::PHI:
7911 Ops.push_back(CondICmp->getOperand(0));
7912 Ops.push_back(CondICmp->getOperand(1));
7932 case Instruction::Select: {
7934 auto CanSimplifyToUnknown = [
this,
U]() {
7952 if (CanSimplifyToUnknown())
7959 case Instruction::Call:
7960 case Instruction::Invoke:
7967 switch (
II->getIntrinsicID()) {
7968 case Intrinsic::abs:
7969 Ops.push_back(
II->getArgOperand(0));
7971 case Intrinsic::umax:
7972 case Intrinsic::umin:
7973 case Intrinsic::smax:
7974 case Intrinsic::smin:
7975 case Intrinsic::usub_sat:
7976 case Intrinsic::uadd_sat:
7977 Ops.push_back(
II->getArgOperand(0));
7978 Ops.push_back(
II->getArgOperand(1));
7980 case Intrinsic::start_loop_iterations:
7981 case Intrinsic::annotation:
7982 case Intrinsic::ptr_annotation:
7983 Ops.push_back(
II->getArgOperand(0));
7995const SCEV *ScalarEvolution::createSCEV(
Value *V) {
8004 if (!DT.isReachableFromEntry(
I->getParent()))
8019 switch (BO->Opcode) {
8020 case Instruction::Add: {
8046 if (BO->Opcode == Instruction::Sub)
8054 if (BO->Opcode == Instruction::Sub)
8061 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
8062 NewBO->Opcode != Instruction::Sub)) {
8072 case Instruction::Mul: {
8093 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
8102 case Instruction::UDiv:
8106 case Instruction::URem:
8110 case Instruction::Sub: {
8113 Flags = getNoWrapFlagsFromUB(BO->
Op);
8118 case Instruction::And:
8124 if (CI->isMinusOne())
8126 const APInt &
A = CI->getValue();
8132 unsigned LZ =
A.countl_zero();
8133 unsigned TZ =
A.countr_zero();
8138 APInt EffectiveMask =
8140 if ((LZ != 0 || TZ != 0) && !((~
A & ~Known.
Zero) & EffectiveMask)) {
8143 const SCEV *ShiftedLHS =
nullptr;
8147 unsigned MulZeros = OpC->getAPInt().countr_zero();
8148 unsigned GCD = std::min(MulZeros, TZ);
8153 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8175 case Instruction::Or:
8184 case Instruction::Xor:
8187 if (CI->isMinusOne())
8196 if (LBO->getOpcode() == Instruction::And &&
8197 LCI->getValue() == CI->getValue())
8198 if (
const SCEVZeroExtendExpr *Z =
8201 const SCEV *Z0 =
Z->getOperand();
8208 if (CI->getValue().isMask(Z0TySize))
8214 APInt Trunc = CI->getValue().trunc(Z0TySize);
8223 case Instruction::Shl:
8241 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8250 ConstantInt *
X = ConstantInt::get(
8256 case Instruction::AShr:
8278 const SCEV *AddTruncateExpr =
nullptr;
8279 ConstantInt *ShlAmtCI =
nullptr;
8280 const SCEV *AddConstant =
nullptr;
8282 if (L &&
L->getOpcode() == Instruction::Add) {
8290 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8297 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8305 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8310 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8315 if (AddTruncateExpr && ShlAmtCI) {
8327 const APInt &ShlAmt = ShlAmtCI->
getValue();
8331 const SCEV *CompositeExpr =
8333 if (
L->getOpcode() != Instruction::Shl)
8334 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8343 switch (
U->getOpcode()) {
8344 case Instruction::Trunc:
8347 case Instruction::ZExt:
8350 case Instruction::SExt:
8360 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8361 Type *Ty =
U->getType();
8369 case Instruction::BitCast:
8375 case Instruction::PtrToAddr: {
8382 case Instruction::PtrToInt: {
8385 Type *DstIntTy =
U->getType();
8393 case Instruction::IntToPtr:
8397 case Instruction::SDiv:
8404 case Instruction::SRem:
8411 case Instruction::GetElementPtr:
8414 case Instruction::PHI:
8417 case Instruction::Select:
8418 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8421 case Instruction::Call:
8422 case Instruction::Invoke:
8427 switch (
II->getIntrinsicID()) {
8428 case Intrinsic::abs:
8432 case Intrinsic::umax:
8436 case Intrinsic::umin:
8440 case Intrinsic::smax:
8444 case Intrinsic::smin:
8448 case Intrinsic::usub_sat: {
8449 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8450 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8454 case Intrinsic::uadd_sat: {
8455 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8456 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8460 case Intrinsic::start_loop_iterations:
8461 case Intrinsic::annotation:
8462 case Intrinsic::ptr_annotation:
8466 case Intrinsic::vscale:
8486 auto *ExitCountType = ExitCount->
getType();
8487 assert(ExitCountType->isIntegerTy());
8489 1 + ExitCountType->getScalarSizeInBits());
8502 auto CanAddOneWithoutOverflow = [&]() {
8504 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8515 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8545 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8546 assert(L->isLoopExiting(ExitingBlock) &&
8547 "Exiting block must actually branch out of the loop!");
8556 const auto *MaxExitCount =
8564 L->getExitingBlocks(ExitingBlocks);
8566 std::optional<unsigned> Res;
8567 for (
auto *ExitingBB : ExitingBlocks) {
8571 Res = std::gcd(*Res, Multiple);
8573 return Res.value_or(1);
8577 const SCEV *ExitCount) {
8607 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8608 assert(L->isLoopExiting(ExitingBlock) &&
8609 "Exiting block must actually branch out of the loop!");
8619 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8621 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8623 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8633 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8636 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8639 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8647 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8654 return getBackedgeTakenInfo(L).getExact(L,
this);
8656 return getBackedgeTakenInfo(L).getConstantMax(
this);
8658 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8665 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8670 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8674 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8684 for (
PHINode &PN : Header->phis())
8685 if (Visited.
insert(&PN).second)
8689ScalarEvolution::BackedgeTakenInfo &
8690ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8691 auto &BTI = getBackedgeTakenInfo(L);
8692 if (BTI.hasFullInfo())
8695 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8698 return Pair.first->second;
8700 BackedgeTakenInfo
Result =
8701 computeBackedgeTakenCount(L,
true);
8703 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8706ScalarEvolution::BackedgeTakenInfo &
8707ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8713 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8714 BackedgeTakenCounts.try_emplace(L);
8716 return Pair.first->second;
8721 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8728 if (
Result.hasAnyInfo()) {
8731 auto LoopUsersIt = LoopUsers.find(L);
8732 if (LoopUsersIt != LoopUsers.end())
8734 forgetMemoizedResults(ToForget);
8737 for (PHINode &PN :
L->getHeader()->phis())
8738 ConstantEvolutionLoopExitValue.erase(&PN);
8746 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8755 BackedgeTakenCounts.clear();
8756 PredicatedBackedgeTakenCounts.clear();
8757 BECountUsers.clear();
8758 LoopPropertiesCache.clear();
8759 ConstantEvolutionLoopExitValue.clear();
8760 ValueExprMap.clear();
8761 ValuesAtScopes.clear();
8762 ValuesAtScopesUsers.clear();
8763 LoopDispositions.clear();
8764 BlockDispositions.clear();
8765 UnsignedRanges.clear();
8766 SignedRanges.clear();
8767 ExprValueMap.clear();
8769 ConstantMultipleCache.clear();
8770 PredicatedSCEVRewrites.clear();
8772 FoldCacheUser.clear();
8774void ScalarEvolution::visitAndClearUsers(
8778 while (!Worklist.
empty()) {
8785 if (It != ValueExprMap.
end()) {
8787 eraseValueFromMap(It->first);
8789 ConstantEvolutionLoopExitValue.erase(PN);
8803 while (!LoopWorklist.
empty()) {
8807 forgetBackedgeTakenCounts(CurrL,
false);
8808 forgetBackedgeTakenCounts(CurrL,
true);
8811 PredicatedSCEVRewrites.remove_if(
8812 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8814 auto LoopUsersItr = LoopUsers.find(CurrL);
8815 if (LoopUsersItr != LoopUsers.end())
8820 visitAndClearUsers(Worklist, Visited, ToForget);
8822 LoopPropertiesCache.erase(CurrL);
8825 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8827 forgetMemoizedResults(ToForget);
8844 visitAndClearUsers(Worklist, Visited, ToForget);
8846 forgetMemoizedResults(ToForget);
8858 struct InvalidationRootCollector {
8862 InvalidationRootCollector(
Loop *L) : L(L) {}
8864 bool follow(
const SCEV *S) {
8870 if (L->contains(AddRec->
getLoop()))
8875 bool isDone()
const {
return false; }
8878 InvalidationRootCollector
C(L);
8880 forgetMemoizedResults(
C.Roots);
8893 BlockDispositions.clear();
8894 LoopDispositions.clear();
8911 while (!Worklist.
empty()) {
8913 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8914 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8915 if (!LoopDispoRemoved && !BlockDispoRemoved)
8917 auto Users = SCEVUsers.find(Curr);
8918 if (
Users != SCEVUsers.end())
8931const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8935 if (!isComplete() || ExitNotTaken.
empty())
8946 for (
const auto &ENT : ExitNotTaken) {
8947 const SCEV *BECount = ENT.ExactNotTaken;
8950 "We should only have known counts for exiting blocks that dominate "
8953 Ops.push_back(BECount);
8958 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8959 "Predicate should be always true!");
8968const ScalarEvolution::ExitNotTakenInfo *
8969ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8970 const BasicBlock *ExitingBlock,
8971 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8972 for (
const auto &ENT : ExitNotTaken)
8973 if (ENT.ExitingBlock == ExitingBlock) {
8974 if (ENT.hasAlwaysTruePredicate())
8976 else if (Predicates) {
8986const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8988 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8989 if (!getConstantMax())
8992 for (
const auto &ENT : ExitNotTaken)
8993 if (!ENT.hasAlwaysTruePredicate()) {
9001 "No point in having a non-constant max backedge taken count!");
9002 return getConstantMax();
9005const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
9007 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
9015 for (
const auto &ENT : ExitNotTaken) {
9016 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
9019 "We should only have known counts for exiting blocks that "
9025 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
9026 "Predicate should be always true!");
9029 if (ExitCounts.
empty())
9038bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
9040 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
9041 return !ENT.hasAlwaysTruePredicate();
9043 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
9059 this->ExactNotTaken = E = ConstantMaxNotTaken;
9060 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
9065 "Exact is not allowed to be less precise than Constant Max");
9068 "Exact is not allowed to be less precise than Symbolic Max");
9071 "Symbolic Max is not allowed to be less precise than Constant Max");
9074 "No point in having a non-constant max backedge taken count!");
9076 for (
const auto PredList : PredLists)
9077 for (
const auto *
P : PredList) {
9085 "Backedge count should be int");
9088 "Max backedge count should be int");
9101ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
9103 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
9104 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
9105 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9107 ExitNotTaken.reserve(ExitCounts.
size());
9108 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
9109 std::back_inserter(ExitNotTaken),
9110 [&](
const EdgeExitInfo &EEI) {
9111 BasicBlock *ExitBB = EEI.first;
9112 const ExitLimit &EL = EEI.second;
9113 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
9114 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
9119 "No point in having a non-constant max backedge taken count!");
9123ScalarEvolution::BackedgeTakenInfo
9124ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
9125 bool AllowPredicates) {
9127 L->getExitingBlocks(ExitingBlocks);
9129 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9132 bool CouldComputeBECount =
true;
9134 const SCEV *MustExitMaxBECount =
nullptr;
9135 const SCEV *MayExitMaxBECount =
nullptr;
9136 bool MustExitMaxOrZero =
false;
9137 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9148 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9149 if (ExitIfTrue == CI->
isZero())
9153 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9155 assert((AllowPredicates || EL.Predicates.empty()) &&
9156 "Predicated exit limit when predicates are not allowed!");
9161 ++NumExitCountsComputed;
9165 CouldComputeBECount =
false;
9172 "Exact is known but symbolic isn't?");
9173 ++NumExitCountsNotComputed;
9188 DT.dominates(ExitBB, Latch)) {
9189 if (!MustExitMaxBECount) {
9190 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9191 MustExitMaxOrZero = EL.MaxOrZero;
9194 EL.ConstantMaxNotTaken);
9198 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9201 EL.ConstantMaxNotTaken);
9205 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9209 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9215 for (
const auto &Pair : ExitCounts) {
9217 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9219 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9220 {
L, AllowPredicates});
9222 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9223 MaxBECount, MaxOrZero);
9226ScalarEvolution::ExitLimit
9227ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9228 bool IsOnlyExit,
bool AllowPredicates) {
9229 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9233 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9238 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9239 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9240 "It should have one successor in loop and one exit block!");
9251 if (!
L->contains(SBB)) {
9256 assert(Exit &&
"Exiting block must have at least one exit");
9257 return computeExitLimitFromSingleExitSwitch(
9258 L, SI, Exit, IsOnlyExit);
9265 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9266 bool AllowPredicates) {
9267 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9268 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9269 ControlsOnlyExit, AllowPredicates);
9272std::optional<ScalarEvolution::ExitLimit>
9273ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9274 bool ExitIfTrue,
bool ControlsOnlyExit,
9275 bool AllowPredicates) {
9277 (void)this->ExitIfTrue;
9278 (void)this->AllowPredicates;
9280 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9281 this->AllowPredicates == AllowPredicates &&
9282 "Variance in assumed invariant key components!");
9283 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9284 if (Itr == TripCountMap.end())
9285 return std::nullopt;
9289void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9291 bool ControlsOnlyExit,
9292 bool AllowPredicates,
9294 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9295 this->AllowPredicates == AllowPredicates &&
9296 "Variance in assumed invariant key components!");
9298 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9299 assert(InsertResult.second &&
"Expected successful insertion!");
9304ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9305 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9306 bool ControlsOnlyExit,
bool AllowPredicates) {
9308 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9312 ExitLimit EL = computeExitLimitFromCondImpl(
9313 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9314 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9318ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9319 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9320 bool ControlsOnlyExit,
bool AllowPredicates) {
9322 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9323 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9324 return *LimitFromBinOp;
9330 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9331 if (EL.hasFullInfo() || !AllowPredicates)
9335 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9355 const WithOverflowInst *WO;
9370 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9371 ControlsOnlyExit, AllowPredicates);
9372 if (EL.hasAnyInfo())
9377 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9380std::optional<ScalarEvolution::ExitLimit>
9381ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9385 bool AllowPredicates) {
9394 return std::nullopt;
9398 ExitLimit EL0 = computeExitLimitFromCondCached(
9399 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9400 ExitLimit EL1 = computeExitLimitFromCondCached(
9401 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9406 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9411 if (EitherMayExit) {
9421 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9423 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9426 EL1.ConstantMaxNotTaken);
9428 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9430 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9433 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9437 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9438 BECount = EL0.ExactNotTaken;
9451 SymbolicMaxBECount =
9453 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9457ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9458 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9459 bool AllowPredicates) {
9471 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9473 if (EL.hasAnyInfo())
9476 auto *ExhaustiveCount =
9477 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9480 return ExhaustiveCount;
9482 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9485ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9487 bool ControlsOnlyExit,
bool AllowPredicates) {
9512 ConstantRange CompRange =
9530 InnerLHS = ZExt->getOperand();
9577 if (EL.hasAnyInfo())
9594 if (EL.hasAnyInfo())
return EL;
9626 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9628 if (EL.hasAnyInfo())
9644 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9646 if (EL.hasAnyInfo())
9657ScalarEvolution::ExitLimit
9658ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9660 BasicBlock *ExitingBlock,
9661 bool ControlsOnlyExit) {
9662 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9665 if (
Switch->getDefaultDest() == ExitingBlock)
9669 "Default case must not exit the loop!");
9675 if (EL.hasAnyInfo())
9687 "Evaluation of SCEV at constant didn't fold correctly?");
9691ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9701 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9707 auto MatchPositiveShift =
9710 using namespace PatternMatch;
9712 ConstantInt *ShiftAmt;
9714 OutOpCode = Instruction::LShr;
9716 OutOpCode = Instruction::AShr;
9718 OutOpCode = Instruction::Shl;
9733 auto MatchShiftRecurrence =
9735 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9750 if (MatchPositiveShift(
LHS, V, OpC)) {
9751 PostShiftOpCode = OpC;
9757 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9760 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9766 MatchPositiveShift(BEValue, OpLHS, OpCodeOut) &&
9773 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9778 if (!MatchShiftRecurrence(
LHS, PN, OpCode))
9790 ConstantInt *StableValue =
nullptr;
9795 case Instruction::AShr: {
9803 StableValue = ConstantInt::get(Ty, 0);
9805 StableValue = ConstantInt::get(Ty, -1,
true);
9811 case Instruction::LShr:
9812 case Instruction::Shl:
9822 "Otherwise cannot be an operand to a branch instruction");
9824 if (
Result->isNullValue()) {
9826 const SCEV *UpperBound =
9843 if (
const Function *
F = CI->getCalledFunction())
9852 if (!L->contains(
I))
return false;
9857 return L->getHeader() ==
I->getParent();
9933 if (!
I)
return nullptr;
9946 std::vector<Constant*> Operands(
I->getNumOperands());
9948 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9952 if (!Operands[i])
return nullptr;
9957 if (!
C)
return nullptr;
9979 if (IncomingVal != CurrentVal) {
9982 IncomingVal = CurrentVal;
9994ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9997 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
10006 DenseMap<Instruction *, Constant *> CurrentIterVals;
10008 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10014 for (PHINode &
PHI : Header->phis()) {
10016 CurrentIterVals[&
PHI] = StartCST;
10018 if (!CurrentIterVals.
count(PN))
10019 return RetVal =
nullptr;
10025 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
10028 unsigned IterationNum = 0;
10030 for (; ; ++IterationNum) {
10031 if (IterationNum == NumIterations)
10032 return RetVal = CurrentIterVals[PN];
10036 DenseMap<Instruction *, Constant *> NextIterVals;
10041 NextIterVals[PN] = NextPHI;
10043 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
10049 for (
const auto &
I : CurrentIterVals) {
10051 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
10056 for (
const auto &
I : PHIsToCompute) {
10057 PHINode *
PHI =
I.first;
10060 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10063 if (NextPHI !=
I.second)
10064 StoppedEvolving =
false;
10069 if (StoppedEvolving)
10070 return RetVal = CurrentIterVals[PN];
10072 CurrentIterVals.swap(NextIterVals);
10076const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
10086 DenseMap<Instruction *, Constant *> CurrentIterVals;
10088 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10091 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
10093 for (PHINode &
PHI : Header->phis()) {
10095 CurrentIterVals[&
PHI] = StartCST;
10097 if (!CurrentIterVals.
count(PN))
10105 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10112 if (CondVal->getValue() == uint64_t(ExitWhen)) {
10113 ++NumBruteForceTripCountsComputed;
10118 DenseMap<Instruction *, Constant *> NextIterVals;
10124 for (
const auto &
I : CurrentIterVals) {
10126 if (!
PHI ||
PHI->getParent() != Header)
continue;
10129 for (PHINode *
PHI : PHIsToCompute) {
10131 if (NextPHI)
continue;
10133 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10136 CurrentIterVals.
swap(NextIterVals);
10147 for (
auto &LS : Values)
10149 return LS.second ? LS.second : V;
10154 const SCEV *
C = computeSCEVAtScope(V, L);
10155 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10156 if (LS.first == L) {
10159 ValuesAtScopesUsers[
C].push_back({L, V});
10170 switch (V->getSCEVType()) {
10210 assert(!
C->getType()->isPointerTy() &&
10211 "Can only have one pointer, and it must be last");
10236const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10237 SmallVectorImpl<SCEVUse> &NewOps) {
10272const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10273 switch (
V->getSCEVType()) {
10284 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10295 for (++i; i !=
e; ++i)
10340 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10350 for (++i; i !=
e; ++i) {
10355 return getWithOperands(V, NewOps);
10370 const Loop *CurrLoop = this->LI[
I->getParent()];
10381 if (BackedgeTakenCount->
isZero()) {
10382 Value *InitValue =
nullptr;
10383 bool MultipleInitValues =
false;
10389 MultipleInitValues =
true;
10394 if (!MultipleInitValues && InitValue)
10403 unsigned InLoopPred =
10414 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10428 SmallVector<Constant *, 4> Operands;
10429 Operands.
reserve(
I->getNumOperands());
10430 bool MadeImprovement =
false;
10445 MadeImprovement |= OrigV != OpV;
10450 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10455 if (!MadeImprovement)
10476const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10478 return stripInjectiveFunctions(ZExt->getOperand());
10480 return stripInjectiveFunctions(SExt->getOperand());
10498 assert(
A != 0 &&
"A must be non-zero.");
10514 if (MinTZ < Mult2 && L->getLoopPredecessor())
10516 if (MinTZ < Mult2) {
10539 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10559static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10565 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10566 << *AddRec <<
'\n');
10569 if (!LC || !MC || !
NC) {
10570 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10571 return std::nullopt;
10577 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10585 N =
N.sext(NewWidth);
10586 M = M.sext(NewWidth);
10587 L = L.sext(NewWidth);
10604 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10605 <<
", multiplied by " <<
T <<
'\n');
10614 std::optional<APInt>
Y) {
10616 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10619 return XW.
slt(YW) ? *
X : *
Y;
10622 return std::nullopt;
10623 return X ? *
X : *
Y;
10640 return std::nullopt;
10641 unsigned W =
X->getBitWidth();
10661static std::optional<APInt>
10667 return std::nullopt;
10670 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10671 std::optional<APInt>
X =
10674 return std::nullopt;
10679 return std::nullopt;
10694static std::optional<APInt>
10698 "Starting value of addrec should be 0");
10699 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10700 <<
Range <<
", addrec " << *AddRec <<
'\n');
10704 "Addrec's initial value should be in range");
10710 return std::nullopt;
10720 auto SolveForBoundary =
10721 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10724 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10725 << Bound <<
" (before multiplying by " << M <<
")\n");
10728 std::optional<APInt> SO;
10731 "signed overflow\n");
10735 "unsigned overflow\n");
10736 std::optional<APInt> UO =
10739 auto LeavesRange = [&] (
const APInt &
X) {
10756 return {std::nullopt,
false};
10761 if (LeavesRange(*Min))
10762 return { Min,
true };
10763 std::optional<APInt> Max = Min == SO ? UO : SO;
10764 if (LeavesRange(*Max))
10765 return { Max,
true };
10768 return {std::nullopt,
true};
10775 auto SL = SolveForBoundary(
Lower);
10776 auto SU = SolveForBoundary(
Upper);
10779 if (!SL.second || !SU.second)
10780 return std::nullopt;
10823ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10825 bool ControlsOnlyExit,
10826 bool AllowPredicates) {
10837 if (
C->getValue()->isZero())
return C;
10841 const SCEVAddRecExpr *AddRec =
10844 if (!AddRec && AllowPredicates)
10850 if (!AddRec || AddRec->
getLoop() != L)
10861 return ExitLimit(R, R, R,
false, Predicates);
10919 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10945 const SCEV *
Exact =
10953 const SCEV *SymbolicMax =
10955 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10964 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10972 return ExitLimit(
E, M, S,
false, Predicates);
10975ScalarEvolution::ExitLimit
10976ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10984 if (!
C->getValue()->isZero())
10994std::pair<const BasicBlock *, const BasicBlock *>
10995ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
11006 if (
const Loop *L = LI.getLoopFor(BB))
11007 return {
L->getLoopPredecessor(),
L->getHeader()};
11009 return {
nullptr, BB};
11018 if (
A ==
B)
return true;
11033 if (ComputesEqualValues(AI, BI))
11041 const SCEV *Op0, *Op1;
11060 auto TrivialCase = [&](
bool TriviallyTrue) {
11069 const SCEV *NewLHS, *NewRHS;
11093 return TrivialCase(
false);
11094 return TrivialCase(
true);
11117 const APInt &
RA = RC->getAPInt();
11119 bool SimplifiedByConstantRange =
false;
11124 return TrivialCase(
true);
11126 return TrivialCase(
false);
11135 Changed = SimplifiedByConstantRange =
true;
11139 if (!SimplifiedByConstantRange) {
11156 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11162 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11168 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11174 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11186 return TrivialCase(
true);
11188 return TrivialCase(
false);
11293 auto NonRecursive = [OrNegative](
const SCEV *S) {
11295 return C->getAPInt().isPowerOf2() ||
11296 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11302 if (NonRecursive(S))
11328 APInt C = Cst->getAPInt();
11329 return C.urem(M) == 0;
11337 const SCEV *SmodM =
11352 for (
auto *
A : Assumptions)
11353 if (
A->implies(
P, *
this))
11366std::pair<const SCEV *, const SCEV *>
11369 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11371 return { Start, Start };
11373 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11382 getUsedLoops(LHS, LoopsUsed);
11383 getUsedLoops(RHS, LoopsUsed);
11385 if (LoopsUsed.
empty())
11390 for (
const auto *L1 : LoopsUsed)
11391 for (
const auto *L2 : LoopsUsed)
11392 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11393 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11394 "Domination relationship is not a linear order");
11424 SplitRHS.second) &&
11436 if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
11440 return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11450 return std::nullopt;
11465 if (KnownWithoutContext)
11466 return KnownWithoutContext;
11473 return std::nullopt;
11479 const Loop *L = LHS->getLoop();
11484std::optional<ScalarEvolution::MonotonicPredicateType>
11487 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11493 auto ResultSwapped =
11496 assert(*ResultSwapped != *Result &&
11497 "monotonicity should flip as we flip the predicate");
11504std::optional<ScalarEvolution::MonotonicPredicateType>
11505ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11519 return std::nullopt;
11523 "Should be greater or less!");
11527 if (!LHS->hasNoUnsignedWrap())
11528 return std::nullopt;
11532 "Relational predicate is either signed or unsigned!");
11533 if (!
LHS->hasNoSignedWrap())
11534 return std::nullopt;
11536 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11544 return std::nullopt;
11547std::optional<ScalarEvolution::LoopInvariantPredicate>
11554 return std::nullopt;
11561 if (!ArLHS || ArLHS->
getLoop() != L)
11562 return std::nullopt;
11566 return std::nullopt;
11592 return std::nullopt;
11629 return std::nullopt;
11632std::optional<ScalarEvolution::LoopInvariantPredicate>
11637 Pred, LHS, RHS, L, CtxI, MaxIter))
11647 Pred, LHS, RHS, L, CtxI,
Op))
11649 return std::nullopt;
11652std::optional<ScalarEvolution::LoopInvariantPredicate>
11667 return std::nullopt;
11674 if (!AR || AR->
getLoop() != L)
11675 return std::nullopt;
11680 Pred = Pred.dropSameSign();
11684 return std::nullopt;
11690 if (Step != One && Step != MinusOne)
11691 return std::nullopt;
11697 return std::nullopt;
11703 return std::nullopt;
11711 if (Step == MinusOne)
11715 return std::nullopt;
11721bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11727 auto CheckRange = [&](
bool IsSigned) {
11730 return RangeLHS.
icmp(Pred, RangeRHS);
11739 if (CheckRange(
true) || CheckRange(
false))
11748bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11757 SCEVUse XNonConstOp, XConstOp;
11758 SCEVUse YNonConstOp, YConstOp;
11762 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11765 XFlagsPresent = ExpectedFlags;
11770 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11773 YFlagsPresent = ExpectedFlags;
11776 if (YNonConstOp != XNonConstOp)
11784 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11787 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11847bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11868bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11869 const SCEV *
LHS,
const SCEV *
RHS) {
11874 return any_of(*BB, [&](
const Instruction &
I) {
11875 using namespace llvm::PatternMatch;
11880 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11894 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11899 "This cannot be done on broken IR!");
11902 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11911 if (LoopContinuePredicate &&
11912 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11913 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11918 if (WalkingBEDominatingConds)
11924 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11925 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11932 const SCEV *LoopCounter =
11940 for (
auto &AssumeVH : AC.assumptions()) {
11947 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11951 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11954 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11955 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11956 assert(DTN &&
"should reach the loop header before reaching the root!");
11959 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11977 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
11990 if (!DT.isReachableFromEntry(BB))
11994 "This cannot be done on broken IR!");
12002 const bool ProvingStrictComparison =
12004 bool ProvedNonStrictComparison =
false;
12005 bool ProvedNonEquality =
false;
12008 if (!ProvedNonStrictComparison)
12009 ProvedNonStrictComparison = Fn(NonStrictPredicate);
12010 if (!ProvedNonEquality)
12012 if (ProvedNonStrictComparison && ProvedNonEquality)
12017 if (ProvingStrictComparison) {
12019 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
12021 if (SplitAndProve(ProofFn))
12026 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
12028 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
12030 if (ProvingStrictComparison) {
12032 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
12034 if (SplitAndProve(ProofFn))
12043 const Loop *ContainingLoop = LI.getLoopFor(BB);
12045 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
12049 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
12050 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
12053 if (!BlockEntryPredicate)
12062 for (
auto &AssumeVH : AC.assumptions()) {
12066 if (!DT.dominates(CI, BB))
12069 if (ProveViaCond(CI->getArgOperand(0),
false))
12075 F.getParent(), Intrinsic::experimental_guard);
12077 for (
const auto *GU : GuardDecl->users())
12079 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12080 if (ProveViaCond(Guard->getArgOperand(0),
false))
12095 "LHS is not available at Loop Entry");
12097 "RHS is not available at Loop Entry");
12099 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12110 if (FoundCondValue ==
12114 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12118 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12121 const Value *Op0, *Op1;
12124 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12128 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12129 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12133 if (!ICI)
return false;
12137 CmpPredicate FoundPred;
12146 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12149bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12150 const SCEV *
RHS, CmpPredicate FoundPred,
12151 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12152 const Instruction *CtxI) {
12162 auto *WideType = FoundLHS->
getType();
12174 TruncFoundLHS, TruncFoundRHS, CtxI))
12200 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12204bool ScalarEvolution::isImpliedCondBalancedTypes(
12209 "Types should be balanced!");
12216 if (FoundLHS == FoundRHS)
12220 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12232 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12249 LHS, FoundLHS, FoundRHS, CtxI);
12251 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12273 assert(P1 != P2 &&
"Handled earlier!");
12277 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12281 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12284 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12285 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12286 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12291 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12302 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12303 CanonicalRHS, CanonicalFoundLHS,
12304 CanonicalFoundRHS);
12309 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12310 CanonicalRHS, CanonicalFoundLHS,
12311 CanonicalFoundRHS);
12318 const SCEVConstant *
C =
nullptr;
12319 const SCEV *
V =
nullptr;
12337 if (Min ==
C->getAPInt()) {
12342 APInt SharperMin = Min + 1;
12345 case ICmpInst::ICMP_SGE:
12346 case ICmpInst::ICMP_UGE:
12349 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12354 case ICmpInst::ICMP_SGT:
12355 case ICmpInst::ICMP_UGT:
12365 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12370 case ICmpInst::ICMP_SLE:
12371 case ICmpInst::ICMP_ULE:
12372 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12373 LHS, V, getConstant(SharperMin), CtxI))
12377 case ICmpInst::ICMP_SLT:
12378 case ICmpInst::ICMP_ULT:
12379 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12380 LHS, V, getConstant(Min), CtxI))
12394 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12398 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12401 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12417std::optional<APInt>
12424 APInt DiffMul(BW, 1);
12427 for (
unsigned I = 0;
I < 8; ++
I) {
12436 if (LAR->getLoop() != MAR->getLoop())
12437 return std::nullopt;
12441 if (!LAR->isAffine() || !MAR->isAffine())
12442 return std::nullopt;
12444 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12445 return std::nullopt;
12447 Less = LAR->getStart();
12448 More = MAR->getStart();
12453 auto MatchConstMul =
12454 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12459 return std::nullopt;
12461 if (
auto MatchedMore = MatchConstMul(More)) {
12462 if (
auto MatchedLess = MatchConstMul(
Less)) {
12463 if (MatchedMore->second == MatchedLess->second) {
12464 More = MatchedMore->first;
12465 Less = MatchedLess->first;
12466 DiffMul *= MatchedMore->second;
12477 Diff +=
C->getAPInt() * DiffMul;
12480 Diff -=
C->getAPInt() * DiffMul;
12483 Multiplicity[S] +=
Mul;
12485 auto Decompose = [&](
const SCEV *S,
int Mul) {
12492 Decompose(More, 1);
12493 Decompose(
Less, -1);
12497 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12498 for (
const auto &[S,
Mul] : Multiplicity) {
12503 return std::nullopt;
12505 }
else if (
Mul == -1) {
12507 return std::nullopt;
12510 return std::nullopt;
12514 if (NewMore == More || NewLess ==
Less)
12515 return std::nullopt;
12521 if (!More && !
Less)
12525 if (!More || !
Less)
12526 return std::nullopt;
12530 return std::nullopt;
12533bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12555 const auto *Latch = L->getLoopLatch();
12558 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12567 const auto *Latch = L->getLoopLatch();
12570 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12580bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12583 const SCEV *FoundLHS,
12584 const SCEV *FoundRHS) {
12593 if (!AddRecFoundLHS)
12600 const Loop *
L = AddRecFoundLHS->getLoop();
12601 if (L != AddRecLHS->getLoop())
12640 if (!RDiff || *LDiff != *RDiff)
12643 if (LDiff->isMinValue())
12646 APInt FoundRHSLimit;
12649 FoundRHSLimit = -(*RDiff);
12661bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12662 const SCEV *
RHS,
const SCEV *FoundLHS,
12663 const SCEV *FoundRHS,
unsigned Depth) {
12664 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12668 bool Erased = PendingMerges.erase(LPhi);
12669 assert(Erased &&
"Failed to erase LPhi!");
12673 bool Erased = PendingMerges.erase(RPhi);
12674 assert(Erased &&
"Failed to erase RPhi!");
12682 if (!PendingMerges.insert(Phi).second)
12696 if (!PendingMerges.insert(Phi).second)
12702 if (!LPhi && !RPhi)
12713 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12717 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12718 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12719 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12720 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12723 if (RPhi && RPhi->getParent() == LBB) {
12730 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12731 if (!ProvedEasily(L, R))
12742 auto *RLoop = RAR->
getLoop();
12743 auto *Predecessor = RLoop->getLoopPredecessor();
12744 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12746 if (!ProvedEasily(L1, RAR->
getStart()))
12748 auto *Latch = RLoop->getLoopLatch();
12749 assert(Latch &&
"Loop with AddRec with no latch?");
12770 if (
auto *Loop = LI.getLoopFor(LBB))
12773 if (!ProvedEasily(L,
RHS))
12780bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12783 const SCEV *FoundLHS,
12784 const SCEV *FoundRHS) {
12787 if (
RHS == FoundRHS) {
12792 if (
LHS != FoundLHS)
12799 Value *Shiftee, *ShiftValue;
12801 using namespace PatternMatch;
12802 if (
match(SUFoundRHS->getValue(),
12804 auto *ShifteeS =
getSCEV(Shiftee);
12822bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12824 const SCEV *FoundLHS,
12825 const SCEV *FoundRHS,
12826 const Instruction *CtxI) {
12827 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12829 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12831 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12832 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12834 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12838template <
typename MinMaxExprType>
12840 const SCEV *Candidate) {
12845 return is_contained(MinMaxExpr->operands(), Candidate);
12858 const SCEV *LStart, *RStart, *Step;
12908bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12910 const SCEV *FoundLHS,
12911 const SCEV *FoundRHS,
12915 "LHS and RHS have different sizes?");
12918 "FoundLHS and FoundRHS have different sizes?");
12952 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
12954 return Ext->getOperand();
12961 auto *OrigLHS =
LHS;
12962 auto *OrigFoundLHS = FoundLHS;
12963 LHS = GetOpFromSExt(
LHS);
12964 FoundLHS = GetOpFromSExt(FoundLHS);
12967 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
12970 FoundRHS,
Depth + 1);
12983 if (!LHSAddExpr->hasNoSignedWrap())
12986 SCEVUse LL = LHSAddExpr->getOperand(0);
12987 SCEVUse LR = LHSAddExpr->getOperand(1);
12991 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
12992 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
12997 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
13003 using namespace llvm::PatternMatch;
13022 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13030 auto *DTy = Denominator->getType();
13031 auto *FRHSTy = FoundRHS->
getType();
13032 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13051 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13062 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13064 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13072 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13105bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13109 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13112 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13115bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13118 const SCEV *FoundLHS,
13119 const SCEV *FoundRHS) {
13155 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13161bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13162 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13163 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13177 ConstantRange FoundLHSRange =
13181 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13188 return LHSRange.
icmp(Pred, ConstRHS);
13191bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13204 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13212 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13215bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
13227 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
13235 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
13247const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
13248 const SCEV *Stride,
13279 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13290 :
APIntOps::umax(MaxEnd, MinStart);
13297ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13298 const Loop *L,
bool IsSigned,
13299 bool ControlsOnlyExit,
bool AllowPredicates) {
13303 bool PredicatedIV =
false;
13308 auto canProveNUW = [&]() {
13311 if (!ControlsOnlyExit)
13332 Limit = Limit.
zext(OuterBitWidth);
13344 Type *Ty = ZExt->getType();
13355 if (!
IV && AllowPredicates) {
13360 PredicatedIV =
true;
13364 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13378 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13381 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13386 if (!PositiveStride) {
13438 auto wouldZeroStrideBeUB = [&]() {
13450 if (!wouldZeroStrideBeUB()) {
13454 }
else if (!NoWrap) {
13457 if (canIVOverflowOnLT(
RHS, Stride, IsSigned))
13470 const SCEV *
Start =
IV->getStart();
13476 const SCEV *OrigStart =
Start;
13477 const SCEV *OrigRHS =
RHS;
13478 if (
Start->getType()->isPointerTy()) {
13489 const SCEV *End =
nullptr, *BECount =
nullptr,
13490 *BECountIfBackedgeTaken =
nullptr;
13493 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13494 any(RHSAddRec->getNoWrapFlags())) {
13507 const SCEV *RHSStart = RHSAddRec->getStart();
13508 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13520 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13529 BECountIfBackedgeTaken =
13534 if (BECount ==
nullptr) {
13539 const SCEV *MaxBECount = computeMaxBECountForLT(
13542 MaxBECount,
false , Predicates);
13549 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13576 const SCEV *Numerator =
13582 auto canProveRHSGreaterThanEqualStart = [&]() {
13601 auto *StartMinusOne =
13608 if (canProveRHSGreaterThanEqualStart()) {
13623 BECountIfBackedgeTaken =
13639 bool MayAddOverflow = [&] {
13685 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13699 if (!MayAddOverflow) {
13711 const SCEV *ConstantMaxBECount;
13712 bool MaxOrZero =
false;
13714 ConstantMaxBECount = BECount;
13715 }
else if (BECountIfBackedgeTaken &&
13720 ConstantMaxBECount = BECountIfBackedgeTaken;
13723 ConstantMaxBECount = computeMaxBECountForLT(
13731 const SCEV *SymbolicMaxBECount =
13733 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13737ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13738 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13739 bool ControlsOnlyExit,
bool AllowPredicates) {
13746 if (!
IV && AllowPredicates)
13753 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13757 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13770 if (!Stride->
isOne() && !NoWrap)
13771 if (canIVOverflowOnGT(
RHS, Stride, IsSigned))
13774 const SCEV *
Start =
IV->getStart();
13775 const SCEV *End =
RHS;
13786 if (
Start->getType()->isPointerTy()) {
13821 const SCEV *ConstantMaxBECount =
13828 ConstantMaxBECount = BECount;
13829 const SCEV *SymbolicMaxBECount =
13832 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13838 if (
Range.isFullSet())
13843 if (!SC->getValue()->isZero()) {
13849 return ShiftedAddRec->getNumIterationsInRange(
13850 Range.subtract(SC->getAPInt()), SE);
13881 APInt ExitVal = (End +
A).udiv(
A);
13894 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13895 "Linear scev computation is off in a bad way!");
13926 assert(!
Last->isZero() &&
"Recurrency with zero step?");
13951 Ty = Store->getValueOperand()->getType();
13953 Ty = Load->getType();
13966 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13968 SE->ConstantEvolutionLoopExitValue.erase(PN);
13969 SE->eraseValueFromMap(getValPtr());
13973void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
13974 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13984 : CallbackVH(
V), SE(se) {}
13993 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
13995 LoopDispositions(64), BlockDispositions(64) {
14007 F.getParent(), Intrinsic::experimental_guard);
14008 HasGuards = GuardDecl && !GuardDecl->use_empty();
14012 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
14013 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14014 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14015 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14016 PendingMerges(
std::
move(Arg.PendingMerges)),
14017 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14018 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14019 PredicatedBackedgeTakenCounts(
14020 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14021 BECountUsers(
std::
move(Arg.BECountUsers)),
14022 ConstantEvolutionLoopExitValue(
14023 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14024 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14025 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14026 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14027 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14028 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14029 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14030 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14031 SignedRanges(
std::
move(Arg.SignedRanges)),
14032 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14033 UniquePreds(
std::
move(Arg.UniquePreds)),
14034 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14035 LoopUsers(
std::
move(Arg.LoopUsers)),
14036 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14037 FirstUnknown(Arg.FirstUnknown) {
14038 Arg.FirstUnknown =
nullptr;
14047 Tmp->~SCEVUnknown();
14049 FirstUnknown =
nullptr;
14051 ExprValueMap.clear();
14052 ValueExprMap.clear();
14054 BackedgeTakenCounts.clear();
14055 PredicatedBackedgeTakenCounts.clear();
14057 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14058 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14059 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14060 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14082 L->getHeader()->printAsOperand(OS,
false);
14086 L->getExitingBlocks(ExitingBlocks);
14087 if (ExitingBlocks.
size() != 1)
14088 OS <<
"<multiple exits> ";
14092 OS <<
"backedge-taken count is ";
14095 OS <<
"Unpredictable backedge-taken count.";
14098 if (ExitingBlocks.
size() > 1)
14099 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14100 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14108 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14111 OS <<
"\n Predicates:\n";
14112 for (
const auto *
P : Predicates)
14120 L->getHeader()->printAsOperand(OS,
false);
14125 OS <<
"constant max backedge-taken count is ";
14128 OS <<
", actual taken count either this or zero.";
14130 OS <<
"Unpredictable constant max backedge-taken count. ";
14135 L->getHeader()->printAsOperand(OS,
false);
14140 OS <<
"symbolic max backedge-taken count is ";
14143 OS <<
", actual taken count either this or zero.";
14145 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14149 if (ExitingBlocks.
size() > 1)
14150 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14151 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14161 OS <<
"\n predicated symbolic max exit count for "
14162 << ExitingBlock->
getName() <<
": ";
14164 OS <<
"\n Predicates:\n";
14165 for (
const auto *
P : Predicates)
14175 assert(!Preds.
empty() &&
"Different predicated BTC, but no predicates");
14177 L->getHeader()->printAsOperand(OS,
false);
14180 OS <<
"Predicated backedge-taken count is ";
14183 OS <<
"Unpredictable predicated backedge-taken count.";
14185 OS <<
" Predicates:\n";
14186 for (
const auto *
P : Preds)
14191 auto *PredConstantMax =
14193 if (PredConstantMax != ConstantBTC) {
14195 "different predicated constant max BTC but no predicates");
14197 L->getHeader()->printAsOperand(OS,
false);
14200 OS <<
"Predicated constant max backedge-taken count is ";
14203 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14205 OS <<
" Predicates:\n";
14206 for (
const auto *
P : Preds)
14211 auto *PredSymbolicMax =
14213 if (SymbolicBTC != PredSymbolicMax) {
14215 "Different predicated symbolic max BTC, but no predicates");
14217 L->getHeader()->printAsOperand(OS,
false);
14220 OS <<
"Predicated symbolic max backedge-taken count is ";
14223 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14225 OS <<
" Predicates:\n";
14226 for (
const auto *
P : Preds)
14232 L->getHeader()->printAsOperand(OS,
false);
14259 OS <<
"Computable";
14269 OS <<
"DoesNotDominate";
14275 OS <<
"ProperlyDominates";
14292 OS <<
"Classifying expressions for: ";
14293 F.printAsOperand(OS,
false);
14308 const Loop *L = LI.getLoopFor(
I.getParent());
14323 OS <<
"\t\t" "Exits: ";
14326 OS <<
"<<Unknown>>";
14332 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14334 Iter->getHeader()->printAsOperand(OS,
false);
14342 InnerL->getHeader()->printAsOperand(OS,
false);
14353 OS <<
"Determining loop execution counts for: ";
14354 F.printAsOperand(OS,
false);
14362 auto &Values = LoopDispositions[S];
14363 for (
auto &V : Values) {
14364 if (V.getPointer() == L)
14369 auto &Values2 = LoopDispositions[S];
14371 if (V.getPointer() == L) {
14380ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14398 if (L->contains(AR->
getLoop()) &&
14400 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14405 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14406 " dominate the contained loop's header?");
14434 bool HasVarying =
false;
14435 bool HasUniform =
false;
14477 auto &Values = BlockDispositions[S];
14478 for (
auto &V : Values) {
14479 if (V.getPointer() == BB)
14484 auto &Values2 = BlockDispositions[S];
14486 if (V.getPointer() == BB) {
14495ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14525 bool Proper =
true;
14536 if (Instruction *
I =
14538 if (
I->getParent() == BB)
14540 if (DT.properlyDominates(
I->getParent(), BB))
14563void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14566 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14567 auto It = BECounts.find(L);
14568 if (It != BECounts.end()) {
14569 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14570 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14572 auto UserIt = BECountUsers.find(S);
14573 assert(UserIt != BECountUsers.end());
14578 BECounts.erase(It);
14586 while (!Worklist.
empty()) {
14588 auto Users = SCEVUsers.find(Curr);
14589 if (
Users != SCEVUsers.end())
14590 for (
const auto *User :
Users->second)
14591 if (ToForget.
insert(User).second)
14595 for (
const auto *S : ToForget)
14596 forgetMemoizedResultsImpl(S);
14598 PredicatedSCEVRewrites.remove_if(
14599 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14602void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14603 LoopDispositions.erase(S);
14604 BlockDispositions.erase(S);
14605 UnsignedRanges.erase(S);
14606 SignedRanges.erase(S);
14607 HasRecMap.erase(S);
14608 ConstantMultipleCache.erase(S);
14611 UnsignedWrapViaInductionTried.erase(AR);
14612 SignedWrapViaInductionTried.erase(AR);
14615 auto ExprIt = ExprValueMap.find(S);
14616 if (ExprIt != ExprValueMap.end()) {
14617 for (
Value *V : ExprIt->second) {
14618 auto ValueIt = ValueExprMap.find_as(V);
14619 if (ValueIt != ValueExprMap.end())
14620 ValueExprMap.erase(ValueIt);
14622 ExprValueMap.erase(ExprIt);
14625 auto ScopeIt = ValuesAtScopes.find(S);
14626 if (ScopeIt != ValuesAtScopes.end()) {
14627 for (
const auto &Pair : ScopeIt->second)
14630 std::make_pair(Pair.first, S));
14631 ValuesAtScopes.erase(ScopeIt);
14634 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14635 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14636 for (
const auto &Pair : ScopeUserIt->second)
14637 llvm::erase(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
14638 ValuesAtScopesUsers.erase(ScopeUserIt);
14641 auto BEUsersIt = BECountUsers.find(S);
14642 if (BEUsersIt != BECountUsers.end()) {
14644 auto Copy = BEUsersIt->second;
14645 for (
const auto &Pair : Copy)
14646 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14647 BECountUsers.erase(BEUsersIt);
14650 auto FoldUser = FoldCacheUser.find(S);
14651 if (FoldUser != FoldCacheUser.end())
14652 for (
auto &KV : FoldUser->second)
14653 FoldCache.erase(KV);
14654 FoldCacheUser.erase(S);
14658ScalarEvolution::getUsedLoops(
const SCEV *S,
14660 struct FindUsedLoops {
14661 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14662 : LoopsUsed(LoopsUsed) {}
14663 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14664 bool follow(
const SCEV *S) {
14670 bool isDone()
const {
return false; }
14673 FindUsedLoops
F(LoopsUsed);
14674 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14677void ScalarEvolution::getReachableBlocks(
14680 Worklist.
push_back(&F.getEntryBlock());
14681 while (!Worklist.
empty()) {
14683 if (!Reachable.
insert(BB).second)
14691 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14698 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14702 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14737 SCEVMapper SCM(SE2);
14739 SE2.getReachableBlocks(ReachableBlocks, F);
14741 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14759 while (!LoopStack.
empty()) {
14765 if (!ReachableBlocks.
contains(L->getHeader()))
14770 auto It = BackedgeTakenCounts.find(L);
14771 if (It == BackedgeTakenCounts.end())
14775 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14795 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14796 if (Delta && !Delta->
isZero()) {
14797 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14798 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14799 dbgs() <<
"New: " << *NewBECount <<
"\n";
14800 dbgs() <<
"Delta: " << *Delta <<
"\n";
14808 while (!Worklist.
empty()) {
14810 if (ValidLoops.
insert(L).second)
14811 Worklist.
append(L->begin(), L->end());
14813 for (
const auto &KV : ValueExprMap) {
14818 "AddRec references invalid loop");
14823 auto It = ExprValueMap.find(KV.second);
14824 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14825 dbgs() <<
"Value " << *KV.first
14826 <<
" is in ValueExprMap but not in ExprValueMap\n";
14831 if (!ReachableBlocks.
contains(
I->getParent()))
14833 const SCEV *OldSCEV = SCM.visit(KV.second);
14835 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14836 if (Delta && !Delta->
isZero()) {
14837 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14838 <<
"Old: " << *OldSCEV <<
"\n"
14839 <<
"New: " << *NewSCEV <<
"\n"
14840 <<
"Delta: " << *Delta <<
"\n";
14846 for (
const auto &KV : ExprValueMap) {
14847 for (
Value *V : KV.second) {
14848 const SCEV *S = ValueExprMap.lookup(V);
14850 dbgs() <<
"Value " << *V
14851 <<
" is in ExprValueMap but not in ValueExprMap\n";
14854 if (S != KV.first) {
14855 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14856 << *KV.first <<
"\n";
14863 for (
const auto &S : UniqueSCEVs) {
14868 auto It = SCEVUsers.find(
Op);
14869 if (It != SCEVUsers.end() && It->second.count(&S))
14871 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14872 <<
" is not being tracked!\n";
14878 for (
const auto &ValueAndVec : ValuesAtScopes) {
14880 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14881 const Loop *L = LoopAndValueAtScope.first;
14882 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
14884 auto It = ValuesAtScopesUsers.find(ValueAtScope);
14885 if (It != ValuesAtScopesUsers.end() &&
14888 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14889 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14895 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14896 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14897 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14898 const Loop *L = LoopAndValue.first;
14899 const SCEV *
Value = LoopAndValue.second;
14901 auto It = ValuesAtScopes.find(
Value);
14902 if (It != ValuesAtScopes.end() &&
14903 is_contained(It->second, std::make_pair(L, ValueAtScope)))
14905 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14906 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14912 auto VerifyBECountUsers = [&](
bool Predicated) {
14914 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14915 for (
const auto &LoopAndBEInfo : BECounts) {
14916 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14917 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14919 auto UserIt = BECountUsers.find(S);
14920 if (UserIt != BECountUsers.end() &&
14921 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14923 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14924 <<
" missing from BECountUsers\n";
14931 VerifyBECountUsers(
false);
14932 VerifyBECountUsers(
true);
14935 for (
auto &[S, Values] : LoopDispositions) {
14936 for (
auto [
Loop, CachedDisposition] : Values) {
14938 if (CachedDisposition != RecomputedDisposition) {
14939 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
14940 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
14941 << RecomputedDisposition <<
"\n";
14948 for (
auto &[S, Values] : BlockDispositions) {
14949 for (
auto [BB, CachedDisposition] : Values) {
14951 if (CachedDisposition != RecomputedDisposition) {
14952 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
14953 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
14954 <<
", actual " << RecomputedDisposition <<
"\n";
14961 for (
auto [
FoldID, Expr] : FoldCache) {
14962 auto I = FoldCacheUser.find(Expr);
14963 if (
I == FoldCacheUser.end()) {
14964 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
14969 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
14973 for (
auto [Expr, IDs] : FoldCacheUser) {
14974 for (
auto &
FoldID : IDs) {
14977 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
14982 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
14983 <<
" != " << *Expr <<
"!\n";
14994 for (
auto [S, Multiple] : ConstantMultipleCache) {
14996 if ((Multiple != 0 && RecomputedMultiple != 0 &&
14997 Multiple.
urem(RecomputedMultiple) != 0 &&
14998 RecomputedMultiple.
urem(Multiple) != 0)) {
14999 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
15000 << *S <<
" : Computed " << RecomputedMultiple
15001 <<
" but cache contains " << Multiple <<
"!\n";
15009 FunctionAnalysisManager::Invalidator &Inv) {
15041 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15042 <<
F.getName() <<
"':\n";
15048 "Scalar Evolution Analysis",
false,
true)
15097 const SCEV *LHS,
const SCEV *RHS) {
15099 assert(LHS->getType() == RHS->getType() &&
15100 "Type mismatch between LHS and RHS");
15103 ID.AddInteger(Pred);
15104 ID.AddPointer(LHS);
15105 ID.AddPointer(RHS);
15106 void *IP =
nullptr;
15107 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
15111 UniquePreds.InsertNode(Eq, IP);
15122 ID.AddInteger(AddedFlags);
15123 void *IP =
nullptr;
15124 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
15126 auto *OF =
new (SCEVAllocator)
15128 UniquePreds.InsertNode(OF, IP);
15148 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15149 return Rewriter.visit(S);
15155 for (
const auto *Pred : U->getPredicates())
15157 if (IPred->getLHS() == Expr &&
15159 return IPred->getRHS();
15161 if (IPred->getLHS() == Expr &&
15162 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15163 return IPred->getRHS();
15166 return convertToAddRecWithPreds(Expr);
15169 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15185 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15202 explicit SCEVPredicateRewriter(
15203 const Loop *L, ScalarEvolution &SE,
15204 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15205 const SCEVPredicate *Pred)
15206 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15208 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15211 return Pred && Pred->
implies(
P, SE);
15217 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15220 return addOverflowAssumption(
A);
15229 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15233 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15235 if (!PredicatedRewrite)
15237 for (
const auto *
P : PredicatedRewrite->second){
15240 if (L != WP->getExpr()->getLoop())
15243 if (!addOverflowAssumption(
P))
15246 return PredicatedRewrite->first;
15249 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15250 const SCEVPredicate *Pred;
15259 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15266 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15286 if (!Step->
isOne())
15311 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15312 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15325 return Op->LHS == LHS &&
Op->RHS == RHS;
15332 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15334 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15359 const SCEV *Start = AR->getStart();
15360 const SCEV *OpStart =
Op->AR->getStart();
15365 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15374 const SCEV *Step = AR->getStepRecurrence(SE);
15375 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15428 if (Step->getValue()->getValue().isNonNegative())
15432 return ImpliedFlags;
15439 for (
const auto *
P : Preds)
15452 return this->implies(I, SE);
15460 for (
const auto *Pred : Preds)
15461 Pred->print(OS,
Depth);
15466 for (
const auto *Pred : Set->Preds)
15474 bool CheckImplies = Preds.
size() < 16;
15477 if (CheckImplies &&
implies(
N, SE))
15483 for (
auto *
P : Preds) {
15484 if (CheckImplies &&
N->implies(
P, SE))
15488 Preds = std::move(PrunedPreds);
15489 Preds.push_back(
N);
15496 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15501 for (
const auto *
Op :
Ops)
15506 SCEVUsers[
Op].insert(
User);
15515 SCEVUsers[
Op].insert(
User);
15519 const SCEV *Expr = SE.getSCEV(V);
15524 RewriteEntry &Entry = RewriteMap[Expr];
15527 if (Entry.second && Generation == Entry.first)
15528 return Entry.second;
15533 Expr = Entry.second;
15535 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15536 Entry = {Generation, NewSCEV};
15542 if (!BackedgeCount) {
15544 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15545 for (
const auto *
P : Preds)
15548 return BackedgeCount;
15552 if (!SymbolicMaxBackedgeCount) {
15554 SymbolicMaxBackedgeCount =
15555 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15556 for (
const auto *
P : Preds)
15559 return SymbolicMaxBackedgeCount;
15563 if (!SmallConstantMaxTripCount) {
15565 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15566 for (
const auto *
P : Preds)
15569 return *SmallConstantMaxTripCount;
15573 if (Preds->implies(&Pred, SE))
15578 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15579 updateGeneration();
15586void PredicatedScalarEvolution::updateGeneration() {
15588 if (++Generation == 0) {
15589 for (
auto &
II : RewriteMap) {
15590 const SCEV *Rewritten =
II.second.second;
15607 auto II = FlagsMap.insert({V, Flags});
15620 auto II = FlagsMap.find(V);
15622 if (
II != FlagsMap.end())
15631 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15636 for (
const auto *
P : NewPreds)
15639 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15645 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15648 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {
15649 for (
auto I :
Init.FlagsMap)
15650 FlagsMap.insert(
I);
15655 for (
auto *BB : L.getBlocks())
15656 for (
auto &
I : *BB) {
15657 if (!SE.isSCEVable(
I.getType()))
15660 auto *Expr = SE.getSCEV(&
I);
15661 auto II = RewriteMap.find(Expr);
15663 if (
II == RewriteMap.end())
15667 if (
II->second.second == Expr)
15672 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15680 LoopGuards Guards(SE);
15688void ScalarEvolution::LoopGuards::collectFromPHI(
15696 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15697 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15711 auto &RewriteMap =
G->second.RewriteMap;
15712 if (RewriteMap.empty())
15714 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15715 if (S == RewriteMap.end())
15721 return {C0,
SM->getSCEVType()};
15724 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15725 MinMaxPattern
P2) -> MinMaxPattern {
15726 auto [C1,
T1] =
P1;
15727 auto [C2, T2] =
P2;
15728 if (!C1 || !C2 ||
T1 != T2)
15732 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15734 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15736 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15738 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15743 auto P = GetMinMaxConst(0);
15744 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15747 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15750 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15753 Guards.RewriteMap.insert({
LHS,
RHS});
15761 const APInt &DivisorVal,
15763 const APInt *ExprVal;
15776 const APInt &DivisorVal,
15778 const APInt *ExprVal;
15786 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15800 const SCEV *URemRHS =
nullptr;
15804 const SCEV *Multiple =
15806 DivInfo[URemLHS] = Multiple;
15808 Multiples[URemLHS] =
C->getAPInt();
15828 auto IsMinMaxSCEVWithNonNegativeConstant =
15832 if (
MinMax->getNumOperands() != 2)
15835 if (
C->getAPInt().isNegative())
15837 SCTy =
MinMax->getSCEVType();
15846 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15848 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15853 auto *DivisibleExpr =
15861void ScalarEvolution::LoopGuards::collectFromBlock(
15863 const BasicBlock *
Block,
const BasicBlock *Pred,
15871 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15882 &ExprsToRewrite]() {
15883 const SCEVConstant *C1;
15896 if (ExactRegion.isWrappedSet() || ExactRegion.isFullSet())
15898 auto [
I,
Inserted] = RewriteMap.try_emplace(LHSUnknown);
15899 const SCEV *RewrittenLHS =
Inserted ? LHSUnknown :
I->second;
15907 if (MatchRangeCheckIdiom())
15924 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15926 if (From == FromRewritten)
15928 RewriteMap[From] = To;
15934 auto GetMaybeRewritten = [&](
const SCEV *S) {
15935 return RewriteMap.lookup_or(S, S);
15938 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15940 const APInt &DividesBy =
15955 switch (Predicate) {
15984 SmallPtrSet<const SCEV *, 16> Visited;
15986 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
15990 while (!Worklist.
empty()) {
15994 if (!Visited.
insert(From).second)
15996 const SCEV *FromRewritten = GetMaybeRewritten(From);
15997 const SCEV *To =
nullptr;
15999 switch (Predicate) {
16004 EnqueueOperands(
UMax);
16010 EnqueueOperands(
SMax);
16016 EnqueueOperands(
UMin);
16022 EnqueueOperands(
SMin);
16030 const SCEV *OneAlignedUp =
16032 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16044 const SCEVConstant *
C;
16053 Guards.NotEqual.insert({
LHS,
RHS});
16062 AddRewrite(From, FromRewritten, To);
16079 SE.F.
getParent(), Intrinsic::experimental_guard);
16081 for (
const auto *GU : GuardDecl->users())
16083 if (Guard->getFunction() ==
Block->getParent() &&
16092 unsigned NumCollectedConditions = 0;
16094 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16096 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16098 const CondBrInst *LoopEntryPredicate =
16100 if (!LoopEntryPredicate)
16105 NumCollectedConditions++;
16109 if (
Depth > 0 && NumCollectedConditions == 2)
16117 if (Pair.second->hasNPredecessorsOrMore(2) &&
16119 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16120 for (
auto &Phi : Pair.second->phis())
16131 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16132 SmallVector<Value *, 8> Worklist;
16133 SmallPtrSet<Value *, 8> Visited;
16135 while (!Worklist.
empty()) {
16142 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16166 DenseMap<const SCEV *, APInt> Multiples;
16168 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16175 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16176 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16180 for (
const auto &[K, Divisor] : Multiples) {
16181 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16182 Guards.RewriteMap[
K] =
16184 Guards.
rewrite(K), Divisor, SE),
16193 Guards.PreserveNUW =
true;
16194 Guards.PreserveNSW =
true;
16195 for (
const SCEV *Expr : ExprsToRewrite) {
16196 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16197 Guards.PreserveNUW &=
16199 Guards.PreserveNSW &=
16206 if (ExprsToRewrite.size() > 1) {
16207 for (
const SCEV *Expr : ExprsToRewrite) {
16208 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16209 Guards.RewriteMap.erase(Expr);
16210 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16219 class SCEVLoopGuardRewriter
16230 NotEqual(Guards.NotEqual) {
16231 if (Guards.PreserveNUW)
16233 if (Guards.PreserveNSW)
16240 return Map.lookup_or(Expr, Expr);
16244 if (
const SCEV *S = Map.lookup(Expr))
16251 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16252 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16253 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16255 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16256 if (
const SCEV *S = Map.lookup(NarrowExt))
16257 return SE.getZeroExtendExpr(S, Ty);
16258 Bitwidth = Bitwidth / 2;
16266 if (
const SCEV *S = Map.lookup(Expr))
16273 if (
const SCEV *S = Map.lookup(Expr))
16279 if (
const SCEV *S = Map.lookup(Expr))
16287 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16292 if (NotEqual.contains({LHS, RHS})) {
16294 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16295 return SE.getUMaxExpr(OneAlignedUp, S);
16302 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16313 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16314 return SE.getAddExpr(
16317 if (
const SCEV *S = Map.lookup(
Add))
16318 return SE.getAddExpr(Expr->
getOperand(0), S);
16330 : SE.getAddExpr(Operands,
16346 : SE.getMulExpr(Operands,
16352 if (RewriteMap.empty() && NotEqual.empty())
16355 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16356 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)
static Value * getOpcode(Value &V, Type &Ty, InstrumentationConfig &IConf, InstrumentorIRBuilderTy &IIRB)
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
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 PushLoopPHIs(const Loop *L, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push PHI nodes in the header of the given loop onto the given Worklist.
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 ConstantRange getRangeForAffineARHelper(APInt Step, const ConstantRange &StartRange, const APInt &MaxBECount, bool Signed)
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 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.
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
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)
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 hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've proved that V doesn't wrap by means of a SCEV predicate.
LLVM_ABI void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Proves that V doesn't overflow by adding SCEV predicate.
LLVM_ABI void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
LLVM_ABI bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds.
LLVM_ABI PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
LLVM_ABI const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
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 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.
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.
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.
FunctionAddr VTableAddr Value
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...
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.
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)
FunctionAddr VTableAddr Count
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.
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()).
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