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())
3723 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3733 return getZero(LHS->getType());
3737 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3738 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3739 if (
Mul->getOperand(i) == RHS) {
3750 const SCEV *NewLHS, *NewRHS;
3758 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
3761 UniqueSCEVs.InsertNode(S, IP);
3798 if (StepChrec->getLoop() == L) {
3812 if (Operands.
size() == 1)
return Operands[0];
3817 "SCEVAddRecExpr operand types don't match!");
3818 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3820 for (
const SCEV *
Op : Operands)
3822 "SCEVAddRecExpr operand is not available at loop entry!");
3825 if (Operands.
back()->isZero()) {
3840 const Loop *NestedLoop = NestedAR->getLoop();
3841 if (L->contains(NestedLoop)
3844 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3846 Operands[0] = NestedAR->getStart();
3850 bool AllInvariant =
all_of(
3862 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3873 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3877 Operands[0] = NestedAR;
3883 return getOrCreateAddRecExpr(Operands, L, Flags);
3899 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3903 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3917 bool FirstIter =
true;
3919 for (
SCEVUse IndexExpr : IndexExprs) {
3926 Offsets.push_back(FieldOffset);
3929 CurTy = STy->getTypeAtIndex(Index);
3934 "The first index of a GEP indexes a pointer");
3935 CurTy = SrcElementTy;
3946 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3947 Offsets.push_back(LocalOffset);
3952 if (Offsets.empty())
3965 "GEP should not change type mid-flight.");
3969SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3972 ID.AddInteger(SCEVType);
3976 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3979SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3982 ID.AddInteger(SCEVType);
3986 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3996 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3997 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3998 if (
Ops.size() == 1)
return Ops[0];
4001 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4003 "Operand types don't match!");
4006 "min/max should be consistently pointerish");
4032 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
4034 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
4039 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
4041 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
4047 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
4053 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
4058 if (Idx <
Ops.size()) {
4059 bool DeletedAny =
false;
4060 while (
Ops[Idx]->getSCEVType() == Kind) {
4062 Ops.erase(
Ops.begin()+Idx);
4080 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
4081 if (
Ops[i] ==
Ops[i + 1] ||
4082 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
4085 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
4088 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
4091 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
4097 if (
Ops.size() == 1)
return Ops[0];
4099 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
4104 ID.AddInteger(Kind);
4108 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4110 return ExistingSCEV;
4113 SCEV *S =
new (SCEVAllocator)
4116 UniqueSCEVs.InsertNode(S, IP);
4124class SCEVSequentialMinMaxDeduplicatingVisitor final
4125 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4126 std::optional<const SCEV *>> {
4127 using RetVal = std::optional<const SCEV *>;
4135 bool canRecurseInto(
SCEVTypes Kind)
const {
4138 return RootKind == Kind || NonSequentialRootKind == Kind;
4141 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
4143 "Only for min/max expressions.");
4146 if (!canRecurseInto(Kind))
4156 return std::nullopt;
4163 RetVal
visit(
const SCEV *S) {
4165 if (!SeenOps.
insert(S).second)
4166 return std::nullopt;
4167 return Base::visit(S);
4171 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4173 : SE(SE), RootKind(RootKind),
4174 NonSequentialRootKind(
4175 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4179 SmallVectorImpl<SCEVUse> &NewOps) {
4184 for (
const SCEV *
Op : OrigOps) {
4189 Ops.emplace_back(*NewOp);
4193 NewOps = std::move(
Ops);
4197 RetVal visitConstant(
const SCEVConstant *Constant) {
return Constant; }
4199 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4201 RetVal visitPtrToAddrExpr(
const SCEVPtrToAddrExpr *Expr) {
return Expr; }
4203 RetVal visitPtrToIntExpr(
const SCEVPtrToIntExpr *Expr) {
return Expr; }
4205 RetVal visitTruncateExpr(
const SCEVTruncateExpr *Expr) {
return Expr; }
4207 RetVal visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
return Expr; }
4209 RetVal visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
return Expr; }
4211 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4213 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4215 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4217 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4219 RetVal visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
4220 return visitAnyMinMaxExpr(Expr);
4223 RetVal visitUMaxExpr(
const SCEVUMaxExpr *Expr) {
4224 return visitAnyMinMaxExpr(Expr);
4227 RetVal visitSMinExpr(
const SCEVSMinExpr *Expr) {
4228 return visitAnyMinMaxExpr(Expr);
4231 RetVal visitUMinExpr(
const SCEVUMinExpr *Expr) {
4232 return visitAnyMinMaxExpr(Expr);
4235 RetVal visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *Expr) {
4236 return visitAnyMinMaxExpr(Expr);
4239 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4241 RetVal visitCouldNotCompute(
const SCEVCouldNotCompute *Expr) {
return Expr; }
4284struct SCEVPoisonCollector {
4285 bool LookThroughMaybePoisonBlocking;
4286 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4287 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4288 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4290 bool follow(
const SCEV *S) {
4291 if (!LookThroughMaybePoisonBlocking &&
4301 bool isDone()
const {
return false; }
4311 SCEVPoisonCollector PC1(
true);
4316 if (PC1.MaybePoison.empty())
4322 SCEVPoisonCollector PC2(
false);
4332 SCEVPoisonCollector PC(
false);
4355 while (!Worklist.
empty()) {
4357 if (!Visited.
insert(V).second)
4361 if (Visited.
size() > 16)
4366 if (PoisonVals.
contains(V) || ::isGuaranteedNotToBePoison(V))
4377 if (PDI->isDisjoint())
4384 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4391 if (
I->hasPoisonGeneratingAnnotations())
4402 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4403 "Not a SCEVSequentialMinMaxExpr!");
4404 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4405 if (
Ops.size() == 1)
4409 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4411 "Operand types don't match!");
4414 "min/max should be consistently pointerish");
4422 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4429 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4439 bool DeletedAny =
false;
4440 while (Idx <
Ops.size()) {
4441 if (
Ops[Idx]->getSCEVType() != Kind) {
4446 Ops.erase(
Ops.begin() + Idx);
4447 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4448 SMME->operands().end());
4456 const SCEV *SaturationPoint;
4467 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4468 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4480 Ops.erase(
Ops.begin() + i);
4485 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4486 Ops.erase(
Ops.begin() + i);
4494 ID.AddInteger(Kind);
4498 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4500 return ExistingSCEV;
4504 SCEV *S =
new (SCEVAllocator)
4507 UniqueSCEVs.InsertNode(S, IP);
4555 if (
Size.isScalable())
4576 "Cannot get offset for structure containing scalable vector types");
4590 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP)) {
4592 "Stale SCEVUnknown in uniquing map!");
4598 UniqueSCEVs.InsertNode(S, IP);
4613 return Ty->isIntOrPtrTy();
4620 if (Ty->isPointerTy())
4631 if (Ty->isIntegerTy())
4635 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4647 bool PreciseA, PreciseB;
4648 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4649 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4650 if (!PreciseA || !PreciseB)
4653 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4654 DT.dominates(ScopeB, ScopeA);
4658 return CouldNotCompute.get();
4661bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4664 return SU && SU->getValue() ==
nullptr;
4667 return !ContainsNulls;
4672 if (
I != HasRecMap.end())
4677 HasRecMap.insert({S, FoundAddRec});
4685 if (
SI == ExprValueMap.
end())
4687 return SI->second.getArrayRef();
4693void ScalarEvolution::eraseValueFromMap(
Value *V) {
4695 if (
I != ValueExprMap.end()) {
4696 auto EVIt = ExprValueMap.find(
I->second);
4697 bool Removed = EVIt->second.remove(V);
4699 assert(Removed &&
"Value not in ExprValueMap?");
4700 ValueExprMap.erase(
I);
4704void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4708 auto It = ValueExprMap.find_as(V);
4709 if (It == ValueExprMap.end()) {
4711 ExprValueMap[S].insert(V);
4722 return createSCEVIter(V);
4729 if (
I != ValueExprMap.end()) {
4730 const SCEV *S =
I->second;
4731 assert(checkValidity(S) &&
4732 "existing SCEV has not been properly invalidated");
4745 Type *Ty = V->getType();
4761 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4774 return (
const SCEV *)
nullptr;
4780 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4784 Type *Ty = V->getType();
4790 assert(
P->getType()->isPointerTy());
4805 if (AddOp->getType()->isPointerTy()) {
4806 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4824 return getZero(LHS->getType());
4829 if (RHS->getType()->isPointerTy()) {
4830 if (!LHS->getType()->isPointerTy() ||
4840 const bool RHSIsNotMinSigned =
4871 Type *SrcTy = V->getType();
4872 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4873 "Cannot truncate or zero extend with non-integer arguments!");
4883 Type *SrcTy = V->getType();
4884 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4885 "Cannot truncate or zero extend with non-integer arguments!");
4895 Type *SrcTy = V->getType();
4896 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4897 "Cannot noop or zero extend with non-integer arguments!");
4899 "getNoopOrZeroExtend cannot truncate!");
4907 Type *SrcTy = V->getType();
4908 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4909 "Cannot noop or sign extend with non-integer arguments!");
4911 "getNoopOrSignExtend cannot truncate!");
4919 Type *SrcTy = V->getType();
4920 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4921 "Cannot noop or any extend with non-integer arguments!");
4923 "getNoopOrAnyExtend cannot truncate!");
4931 Type *SrcTy = V->getType();
4932 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4933 "Cannot truncate or noop with non-integer arguments!");
4935 "getTruncateOrNoop cannot extend!");
4943 const SCEV *PromotedLHS = LHS;
4944 const SCEV *PromotedRHS = RHS;
4964 assert(!
Ops.empty() &&
"At least one operand must be!");
4966 if (
Ops.size() == 1)
4970 Type *MaxType =
nullptr;
4976 assert(MaxType &&
"Failed to find maximum type!");
4989 if (!V->getType()->isPointerTy())
4994 V = AddRec->getStart();
4996 const SCEV *PtrOp =
nullptr;
4997 for (
const SCEV *AddOp :
Add->operands()) {
4998 if (AddOp->getType()->isPointerTy()) {
4999 assert(!PtrOp &&
"Cannot have multiple pointer ops");
5003 assert(PtrOp &&
"Must have pointer op");
5015 for (
User *U :
I->users()) {
5017 if (Visited.
insert(UserInsn).second)
5031 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
5032 bool IgnoreOtherLoops =
true) {
5035 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
5037 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
5042 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5044 SeenLoopVariantSCEVUnknown =
true;
5048 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5052 SeenOtherLoops =
true;
5056 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
5058 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
5061 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
5062 : SCEVRewriteVisitor(SE),
L(
L) {}
5065 bool SeenLoopVariantSCEVUnknown =
false;
5066 bool SeenOtherLoops =
false;
5075 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
5076 SCEVPostIncRewriter
Rewriter(L, SE);
5078 return Rewriter.hasSeenLoopVariantSCEVUnknown()
5083 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5085 SeenLoopVariantSCEVUnknown =
true;
5089 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5093 SeenOtherLoops =
true;
5097 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
5099 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
5102 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
5103 : SCEVRewriteVisitor(SE),
L(
L) {}
5106 bool SeenLoopVariantSCEVUnknown =
false;
5107 bool SeenOtherLoops =
false;
5113class SCEVBackedgeConditionFolder
5116 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5117 ScalarEvolution &SE) {
5118 bool IsPosBECond =
false;
5119 Value *BECond =
nullptr;
5120 if (BasicBlock *Latch =
L->getLoopLatch()) {
5122 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
5123 "Both outgoing branches should not target same header!");
5124 BECond = BI->getCondition();
5125 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
5130 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
5134 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5135 const SCEV *
Result = Expr;
5140 switch (
I->getOpcode()) {
5141 case Instruction::Select: {
5143 std::optional<const SCEV *> Res =
5144 compareWithBackedgeCondition(
SI->getCondition());
5152 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5163 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5164 bool IsPosBECond, ScalarEvolution &SE)
5165 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5166 IsPositiveBECond(IsPosBECond) {}
5168 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5172 Value *BackedgeCond =
nullptr;
5174 bool IsPositiveBECond;
5177std::optional<const SCEV *>
5178SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5183 if (BackedgeCond == IC)
5186 return std::nullopt;
5191 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5192 ScalarEvolution &SE) {
5198 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5205 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5215 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5216 : SCEVRewriteVisitor(SE),
L(
L) {}
5225ScalarEvolution::proveNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5229 using OBO = OverflowingBinaryOperator;
5237 const APInt &BECountAP = BECountMax->getAPInt();
5238 unsigned NoOverflowBitWidth =
5250 Instruction::Add, IncRange, OBO::NoSignedWrap);
5251 if (NSWRegion.contains(AddRecRange))
5260 Instruction::Add, IncRange, OBO::NoUnsignedWrap);
5261 if (NUWRegion.contains(AddRecRange))
5269ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5279 if (!SignedWrapViaInductionTried.insert(AR).second)
5304 AC.assumptions().empty())
5312 const SCEV *OverflowLimit =
5314 if (OverflowLimit &&
5322ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5332 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5358 AC.assumptions().empty())
5393 explicit BinaryOp(Operator *
Op)
5394 : Opcode(
Op->getOpcode()),
LHS(
Op->getOperand(0)),
RHS(
Op->getOperand(1)),
5397 IsNSW = OBO->hasNoSignedWrap();
5398 IsNUW = OBO->hasNoUnsignedWrap();
5402 explicit BinaryOp(
unsigned Opcode,
Value *
LHS,
Value *
RHS,
bool IsNSW =
false,
5404 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5416 return std::nullopt;
5422 switch (
Op->getOpcode()) {
5423 case Instruction::Add:
5424 case Instruction::Sub:
5425 case Instruction::Mul:
5426 case Instruction::UDiv:
5427 case Instruction::URem:
5428 case Instruction::And:
5429 case Instruction::AShr:
5430 case Instruction::Shl:
5431 return BinaryOp(
Op);
5433 case Instruction::Or: {
5436 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5443 return BinaryOp(
Op);
5446 case Instruction::Xor:
5450 if (RHSC->getValue().isSignMask())
5451 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5453 if (V->getType()->isIntegerTy(1))
5454 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5455 return BinaryOp(
Op);
5457 case Instruction::LShr:
5466 if (SA->getValue().ult(
BitWidth)) {
5468 ConstantInt::get(SA->getContext(),
5470 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5473 return BinaryOp(
Op);
5475 case Instruction::ExtractValue: {
5477 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5485 bool Signed = WO->isSigned();
5488 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5493 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5504 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5505 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5507 return std::nullopt;
5533 if (
Op == SymbolicPHI)
5538 if (SourceBits != NewBits)
5556 if (!L || L->getHeader() != PN->
getParent())
5614std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5615ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5623 assert(L &&
"Expecting an integer loop header phi");
5628 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5629 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5630 Value *
V = PN->getIncomingValue(i);
5631 if (
L->contains(PN->getIncomingBlock(i))) {
5634 }
else if (BEValueV != V) {
5638 }
else if (!StartValueV) {
5640 }
else if (StartValueV != V) {
5641 StartValueV =
nullptr;
5645 if (!BEValueV || !StartValueV)
5646 return std::nullopt;
5648 const SCEV *BEValue =
getSCEV(BEValueV);
5655 return std::nullopt;
5659 unsigned FoundIndex =
Add->getNumOperands();
5660 Type *TruncTy =
nullptr;
5662 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5665 if (FoundIndex == e) {
5670 if (FoundIndex ==
Add->getNumOperands())
5671 return std::nullopt;
5675 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5676 if (i != FoundIndex)
5677 Ops.push_back(
Add->getOperand(i));
5683 return std::nullopt;
5736 const SCEV *StartVal =
getSCEV(StartValueV);
5737 const SCEV *PHISCEV =
5764 auto getExtendedExpr = [&](
const SCEV *Expr,
5765 bool CreateSignExtend) ->
const SCEV * {
5768 const SCEV *ExtendedExpr =
5771 return ExtendedExpr;
5779 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5780 const SCEV *ExtendedExpr) ->
bool {
5781 return Expr != ExtendedExpr &&
5785 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5786 if (PredIsKnownFalse(StartVal, StartExtended)) {
5788 return std::nullopt;
5793 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5794 if (PredIsKnownFalse(Accum, AccumExtended)) {
5796 return std::nullopt;
5799 auto AppendPredicate = [&](
const SCEV *Expr,
5800 const SCEV *ExtendedExpr) ->
void {
5801 if (Expr != ExtendedExpr &&
5809 AppendPredicate(StartVal, StartExtended);
5810 AppendPredicate(Accum, AccumExtended);
5818 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5819 std::make_pair(NewAR, Predicates);
5821 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5825std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5830 return std::nullopt;
5833 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5834 if (
I != PredicatedSCEVRewrites.end()) {
5835 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5838 if (Rewrite.first == SymbolicPHI)
5839 return std::nullopt;
5843 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5847 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5848 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5853 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5854 return std::nullopt;
5871 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5872 if (Expr1 != Expr2 &&
5873 !Preds->implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5874 !Preds->implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5891const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5893 Value *StartValueV) {
5896 assert(BEValueV && StartValueV);
5902 if (BO->Opcode != Instruction::Add)
5905 const SCEV *Accum =
nullptr;
5906 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5908 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5922 insertValueToMap(PN, PHISCEV);
5934 "Accum is defined outside L, but is not invariant?");
5935 if (isAddRecNeverPoison(BEInst, L))
5942const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5943 const Loop *
L = LI.getLoopFor(PN->
getParent());
5950 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5956 }
else if (BEValueV != V) {
5960 }
else if (!StartValueV) {
5962 }
else if (StartValueV != V) {
5963 StartValueV =
nullptr;
5967 if (!BEValueV || !StartValueV)
5970 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5971 "PHI node already processed?");
5975 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5980 insertValueToMap(PN, SymbolicName);
5984 const SCEV *BEValue =
getSCEV(BEValueV);
5994 unsigned FoundIndex =
Add->getNumOperands();
5995 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5996 if (
Add->getOperand(i) == SymbolicName)
5997 if (FoundIndex == e) {
6002 if (FoundIndex !=
Add->getNumOperands()) {
6005 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
6006 if (i != FoundIndex)
6007 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
6019 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
6026 if (
GEP->getOperand(0) == PN) {
6027 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
6045 const SCEV *StartVal =
getSCEV(StartValueV);
6046 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
6051 forgetMemoizedResults({SymbolicName});
6052 insertValueToMap(PN, PHISCEV);
6056 const_cast<SCEVAddRecExpr *
>(AR),
6082 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
6083 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
6085 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
6086 const SCEV *StartVal =
getSCEV(StartValueV);
6087 if (Start == StartVal) {
6091 forgetMemoizedResults({SymbolicName});
6092 insertValueToMap(PN, Shifted);
6102 eraseValueFromMap(PN);
6117 Use &LeftUse =
Merge->getOperandUse(0);
6118 Use &RightUse =
Merge->getOperandUse(1);
6154 assert(IDom &&
"At least the entry block should dominate PN");
6162const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
6167 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6184 CommonInst = IncomingInst;
6200ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6206 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6207 bool SCEVExprsIdentical =
6209 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6210 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6213const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6214 if (
const SCEV *S = createAddRecFromPHI(PN))
6224 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6227 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6236 struct FindClosure {
6237 const SCEV *OperandToFind;
6243 bool canRecurseInto(
SCEVTypes Kind)
const {
6246 return RootKind == Kind || NonSequentialRootKind == Kind ||
6251 : OperandToFind(OperandToFind), RootKind(RootKind),
6252 NonSequentialRootKind(
6256 bool follow(
const SCEV *S) {
6257 Found = S == OperandToFind;
6259 return !isDone() && canRecurseInto(S->
getSCEVType());
6262 bool isDone()
const {
return Found; }
6265 FindClosure FC(OperandToFind, RootKind);
6270std::optional<const SCEV *>
6271ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6281 switch (ICI->getPredicate()) {
6295 bool Signed = ICI->isSigned();
6296 const SCEV *LA =
getSCEV(TrueVal);
6304 if (LA == LS &&
RA == RS)
6306 if (LA == RS &&
RA == LS)
6309 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6310 if (
Op->getType()->isPointerTy()) {
6321 LS = CoerceOperand(LS);
6322 RS = CoerceOperand(RS);
6346 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6347 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6361 X = ZExt->getOperand();
6363 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6374 return std::nullopt;
6377static std::optional<const SCEV *>
6379 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6383 "Unexpected operands of a select.");
6395 return std::nullopt;
6410static std::optional<const SCEV *>
6414 return std::nullopt;
6417 const auto *SETrue = SE->
getSCEV(TrueVal);
6418 const auto *SEFalse = SE->
getSCEV(FalseVal);
6422const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6424 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6426 V->getType() ==
TrueVal->getType() &&
6427 "Types of select hands and of the result must match.");
6430 if (!
V->getType()->isIntegerTy(1))
6433 if (std::optional<const SCEV *> S =
6446 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6450 if (std::optional<const SCEV *> S =
6451 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6457 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6463 assert(
GEP->getSourceElementType()->isSized() &&
6464 "GEP source element type must be sized");
6467 for (
Value *Index :
GEP->indices())
6472APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6475 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6478 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6480 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6483 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6502 return GetShiftedByZeros(TZ);
6512 return GetShiftedByZeros(TZ);
6516 if (
M->hasNoUnsignedWrap()) {
6519 for (
const SCEV *Operand :
M->operands().drop_front())
6527 for (
const SCEV *Operand :
M->operands())
6529 return GetShiftedByZeros(TZ);
6534 if (
N->hasNoUnsignedWrap())
6535 return GetGCDMultiple(
N);
6538 for (
const SCEV *Operand :
N->operands().drop_front())
6540 return GetShiftedByZeros(TZ);
6557 CtxI = &*F.getEntryBlock().begin();
6564 .allowEphemerals(
true))
6565 .countMinTrailingZeros();
6566 return GetShiftedByZeros(Known);
6579 return getConstantMultipleImpl(S, CtxI);
6581 auto I = ConstantMultipleCache.find(S);
6582 if (
I != ConstantMultipleCache.end())
6585 APInt Result = getConstantMultipleImpl(S, CtxI);
6586 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6587 assert(InsertPair.second &&
"Should insert a new key");
6588 return InsertPair.first->second;
6605 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6608 if (std::optional<ConstantRange>
Range = CB->getRange())
6612 if (std::optional<ConstantRange>
Range =
A->getRange())
6615 return std::nullopt;
6622 UnsignedRanges.erase(AddRec);
6623 SignedRanges.erase(AddRec);
6624 ConstantMultipleCache.erase(AddRec);
6629getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6655 Value *Start, *Step;
6662 assert(L && L->getHeader() ==
P->getParent());
6675 case Instruction::AShr:
6676 case Instruction::LShr:
6677 case Instruction::Shl:
6692 KnownStep.getBitWidth() ==
BitWidth);
6695 auto MaxShiftAmt = KnownStep.getMaxValue();
6697 bool Overflow =
false;
6698 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6705 case Instruction::AShr: {
6713 if (KnownStart.isNonNegative())
6716 KnownStart.getMaxValue() + 1);
6717 if (KnownStart.isNegative())
6720 KnownEnd.getMaxValue() + 1);
6723 case Instruction::LShr: {
6732 KnownStart.getMaxValue() + 1);
6734 case Instruction::Shl: {
6738 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6739 return ConstantRange(KnownStart.getMinValue(),
6740 KnownEnd.getMaxValue() + 1);
6765 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6772ScalarEvolution::getRangeRefIter(
const SCEV *S,
6773 ScalarEvolution::RangeSignHint SignHint) {
6774 DenseMap<const SCEV *, ConstantRange> &Cache =
6775 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6778 SmallPtrSet<const SCEV *, 8> Seen;
6782 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6783 if (!Seen.
insert(Expr).second)
6817 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6818 const SCEV *
P = WorkList[
I];
6822 for (
const SCEV *
Op :
P->operands())
6835 if (!WorkList.
empty()) {
6840 getRangeRef(
P, SignHint);
6844 return getRangeRef(S, SignHint, 0);
6851 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6852 DenseMap<const SCEV *, ConstantRange> &Cache =
6853 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6860 auto I = Cache.
find(S);
6861 if (
I != Cache.
end())
6865 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6870 return getRangeRefIter(S, SignHint);
6873 ConstantRange ConservativeResult(
BitWidth,
true);
6874 using OBO = OverflowingBinaryOperator;
6878 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6882 ConservativeResult =
6889 ConservativeResult = ConstantRange(
6905 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6912 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6919 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6925 return setRange(Cast, SignHint,
X);
6930 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6931 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6933 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6934 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6935 ConservativeResult =
6936 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6938 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6939 unsigned WrapType = OBO::AnyWrap;
6940 if (
Add->hasNoSignedWrap())
6941 WrapType |= OBO::NoSignedWrap;
6942 if (
Add->hasNoUnsignedWrap())
6943 WrapType |= OBO::NoUnsignedWrap;
6945 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6947 return setRange(
Add, SignHint,
6948 ConservativeResult.intersectWith(
X, RangeType));
6952 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6954 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6955 return setRange(
Mul, SignHint,
6956 ConservativeResult.intersectWith(
X, RangeType));
6960 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6961 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6962 return setRange(UDiv, SignHint,
6963 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6971 if (!UnsignedMinValue.
isZero())
6972 ConservativeResult = ConservativeResult.intersectWith(
6973 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6982 bool AllNonNeg =
true;
6983 bool AllNonPos =
true;
6984 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6991 ConservativeResult = ConservativeResult.intersectWith(
6996 ConservativeResult = ConservativeResult.intersectWith(
7005 const SCEV *MaxBEScev =
7019 auto RangeFromAffine = getRangeForAffineAR(
7021 ConservativeResult =
7022 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
7024 auto RangeFromFactoring = getRangeViaFactoring(
7026 ConservativeResult =
7027 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
7033 const SCEV *SymbolicMaxBECount =
7038 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
7039 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
7040 ConservativeResult =
7041 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
7046 return setRange(AddRec, SignHint, std::move(ConservativeResult));
7056 ID = Intrinsic::umax;
7059 ID = Intrinsic::smax;
7063 ID = Intrinsic::umin;
7066 ID = Intrinsic::smin;
7073 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
7074 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
7076 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
7077 return setRange(S, SignHint,
7078 ConservativeResult.intersectWith(
X, RangeType));
7087 ConservativeResult =
7088 ConservativeResult.intersectWith(*MDRange, RangeType);
7093 auto CR = getRangeForUnknownRecurrence(U);
7094 ConservativeResult = ConservativeResult.intersectWith(CR);
7105 if (
U->getType()->isPointerTy()) {
7108 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
7109 int ptrIdxDiff = ptrSize -
BitWidth;
7110 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
7123 ConservativeResult = ConservativeResult.intersectWith(
7127 ConservativeResult = ConservativeResult.intersectWith(
7132 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
7135 bool CanBeNull, CanBeFreed;
7136 uint64_t DerefBytes =
7137 V->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed);
7147 uint64_t
Align =
U->getValue()->getPointerAlignment(DL).value();
7148 uint64_t Rem = MaxVal.
urem(Align);
7153 ConservativeResult = ConservativeResult.intersectWith(
7163 return getRangeRef(AR, SignHint,
Depth + 1);
7167 ConstantRange RangeFromOps(
BitWidth,
false);
7169 for (
const auto &
Op :
Phi->operands()) {
7171 RangeFromOps = RangeFromOps.unionWith(OpRange);
7173 if (RangeFromOps.isFullSet())
7176 ConservativeResult =
7177 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7183 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7185 ConservativeResult = ConservativeResult.difference(Disallowed);
7188 return setRange(U, SignHint, std::move(ConservativeResult));
7194 return setRange(S, SignHint, std::move(ConservativeResult));
7203 const APInt &MaxBECount,
7210 if (Step == 0 || MaxBECount == 0)
7217 return ConstantRange::getFull(
BitWidth);
7233 return ConstantRange::getFull(
BitWidth);
7245 APInt MovedBoundary = Descending ? (StartLower - std::move(
Offset))
7246 : (StartUpper + std::move(
Offset));
7251 if (StartRange.
contains(MovedBoundary))
7252 return ConstantRange::getFull(
BitWidth);
7255 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7257 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7266 const APInt &MaxBECount) {
7270 "mismatched bit widths");
7279 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7281 StartSRange, MaxBECount,
7293ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7295 ScalarEvolution::RangeSignHint SignHint) {
7296 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7298 "This only works for non-self-wrapping AddRecs!");
7299 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7303 return ConstantRange::getFull(
BitWidth);
7311 return ConstantRange::getFull(
BitWidth);
7315 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7317 MaxItersWithoutWrap))
7318 return ConstantRange::getFull(
BitWidth);
7339 ConstantRange StartRange = getRangeRef(Start, SignHint);
7340 ConstantRange EndRange = getRangeRef(End, SignHint);
7341 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7345 return RangeBetween;
7350 return ConstantRange::getFull(
BitWidth);
7353 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7354 return RangeBetween;
7356 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7357 return RangeBetween;
7358 return ConstantRange::getFull(
BitWidth);
7363 const APInt &MaxBECount) {
7370 "mismatched bit widths");
7372 struct SelectPattern {
7373 Value *Condition =
nullptr;
7377 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7379 std::optional<unsigned> CastOp;
7393 CastOp = SCast->getSCEVType();
7394 S = SCast->getOperand();
7397 using namespace llvm::PatternMatch;
7404 Condition =
nullptr;
7436 bool isRecognized() {
return Condition !=
nullptr; }
7439 SelectPattern StartPattern(*
this,
BitWidth, Start);
7440 if (!StartPattern.isRecognized())
7441 return ConstantRange::getFull(
BitWidth);
7443 SelectPattern StepPattern(*
this,
BitWidth, Step);
7444 if (!StepPattern.isRecognized())
7445 return ConstantRange::getFull(
BitWidth);
7447 if (StartPattern.Condition != StepPattern.Condition) {
7451 return ConstantRange::getFull(
BitWidth);
7462 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7463 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7464 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7465 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7467 ConstantRange TrueRange =
7468 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount);
7469 ConstantRange FalseRange =
7470 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount);
7482 PDI && PDI->isDisjoint()) {
7497ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7510 SmallPtrSet<const SCEV *, 16> Visited;
7512 auto pushOp = [&](
const SCEV *S) {
7513 if (!Visited.
insert(S).second)
7516 if (Visited.
size() > 30) {
7527 while (!Worklist.
empty()) {
7529 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7530 if (!Bound || DT.dominates(Bound, DefI))
7537 return Bound ? Bound : &*F.getEntryBlock().begin();
7543 return getDefiningScopeBound(
Ops, Discard);
7546bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7548 if (
A->getParent() ==
B->getParent() &&
7553 auto *BLoop = LI.getLoopFor(
B->getParent());
7554 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7555 BLoop->getLoopPreheader() ==
A->getParent() &&
7557 A->getParent()->end()) &&
7564bool ScalarEvolution::isGuaranteedNotToBePoison(
const SCEV *
Op) {
7565 SCEVPoisonCollector PC(
true);
7567 return PC.MaybePoison.empty();
7570bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7576 return M && (!
isKnownNonZero(Op1) || !isGuaranteedNotToBePoison(Op1));
7580bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7597 for (
const Use &
Op :
I->operands()) {
7603 auto *DefI = getDefiningScopeBound(SCEVOps);
7604 return isGuaranteedToTransferExecutionTo(DefI,
I);
7607bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7609 if (isSCEVExprNeverPoison(
I))
7620 auto *ExitingBB =
L->getExitingBlock();
7624 SmallPtrSet<const Value *, 16> KnownPoison;
7633 while (!Worklist.
empty()) {
7636 for (
const Use &U :
Poison->uses()) {
7639 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7643 if (KnownPoison.
insert(PoisonUser).second)
7651ScalarEvolution::LoopProperties
7652ScalarEvolution::getLoopProperties(
const Loop *L) {
7653 using LoopProperties = ScalarEvolution::LoopProperties;
7655 auto Itr = LoopPropertiesCache.find(L);
7656 if (Itr == LoopPropertiesCache.end()) {
7659 return !
SI->isSimple();
7669 return I->mayWriteToMemory();
7672 LoopProperties LP = {
true,
7675 for (
auto *BB :
L->getBlocks())
7676 for (
auto &
I : *BB) {
7678 LP.HasNoAbnormalExits =
false;
7679 if (HasSideEffects(&
I))
7680 LP.HasNoSideEffects =
false;
7681 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7685 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7686 assert(InsertPair.second &&
"We just checked!");
7687 Itr = InsertPair.first;
7700const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7706 Stack.emplace_back(V,
true);
7707 Stack.emplace_back(V,
false);
7708 while (!Stack.empty()) {
7709 auto E = Stack.pop_back_val();
7710 Value *CurV = E.getPointer();
7716 const SCEV *CreatedSCEV =
nullptr;
7719 CreatedSCEV = createSCEV(CurV);
7724 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7728 insertValueToMap(CurV, CreatedSCEV);
7732 Stack.emplace_back(CurV,
true);
7734 Stack.emplace_back(
Op,
false);
7751 if (!DT.isReachableFromEntry(
I->getParent()))
7764 switch (BO->Opcode) {
7765 case Instruction::Add:
7766 case Instruction::Mul: {
7773 Ops.push_back(BO->
Op);
7777 Ops.push_back(BO->RHS);
7781 (BO->Opcode == Instruction::Add &&
7782 (NewBO->Opcode != Instruction::Add &&
7783 NewBO->Opcode != Instruction::Sub)) ||
7784 (BO->Opcode == Instruction::Mul &&
7785 NewBO->Opcode != Instruction::Mul)) {
7786 Ops.push_back(BO->LHS);
7791 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7794 Ops.push_back(BO->LHS);
7802 case Instruction::Sub:
7803 case Instruction::UDiv:
7804 case Instruction::URem:
7806 case Instruction::AShr:
7807 case Instruction::Shl:
7808 case Instruction::Xor:
7812 case Instruction::And:
7813 case Instruction::Or:
7817 case Instruction::LShr:
7824 Ops.push_back(BO->LHS);
7825 Ops.push_back(BO->RHS);
7829 switch (
U->getOpcode()) {
7830 case Instruction::Trunc:
7831 case Instruction::ZExt:
7832 case Instruction::SExt:
7833 case Instruction::PtrToAddr:
7834 case Instruction::PtrToInt:
7835 Ops.push_back(
U->getOperand(0));
7838 case Instruction::BitCast:
7840 Ops.push_back(
U->getOperand(0));
7845 case Instruction::SDiv:
7846 case Instruction::SRem:
7847 Ops.push_back(
U->getOperand(0));
7848 Ops.push_back(
U->getOperand(1));
7851 case Instruction::GetElementPtr:
7853 "GEP source element type must be sized");
7857 case Instruction::IntToPtr:
7860 case Instruction::PHI:
7891 Ops.push_back(CondICmp->getOperand(0));
7892 Ops.push_back(CondICmp->getOperand(1));
7912 case Instruction::Select: {
7914 auto CanSimplifyToUnknown = [
this,
U]() {
7932 if (CanSimplifyToUnknown())
7939 case Instruction::Call:
7940 case Instruction::Invoke:
7947 switch (
II->getIntrinsicID()) {
7948 case Intrinsic::abs:
7949 Ops.push_back(
II->getArgOperand(0));
7951 case Intrinsic::umax:
7952 case Intrinsic::umin:
7953 case Intrinsic::smax:
7954 case Intrinsic::smin:
7955 case Intrinsic::usub_sat:
7956 case Intrinsic::uadd_sat:
7957 Ops.push_back(
II->getArgOperand(0));
7958 Ops.push_back(
II->getArgOperand(1));
7960 case Intrinsic::start_loop_iterations:
7961 case Intrinsic::annotation:
7962 case Intrinsic::ptr_annotation:
7963 Ops.push_back(
II->getArgOperand(0));
7975const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7984 if (!DT.isReachableFromEntry(
I->getParent()))
7999 switch (BO->Opcode) {
8000 case Instruction::Add: {
8026 if (BO->Opcode == Instruction::Sub)
8034 if (BO->Opcode == Instruction::Sub)
8041 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
8042 NewBO->Opcode != Instruction::Sub)) {
8052 case Instruction::Mul: {
8073 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
8082 case Instruction::UDiv:
8086 case Instruction::URem:
8090 case Instruction::Sub: {
8093 Flags = getNoWrapFlagsFromUB(BO->
Op);
8098 case Instruction::And:
8104 if (CI->isMinusOne())
8106 const APInt &
A = CI->getValue();
8112 unsigned LZ =
A.countl_zero();
8113 unsigned TZ =
A.countr_zero();
8118 APInt EffectiveMask =
8120 if ((LZ != 0 || TZ != 0) && !((~
A & ~Known.
Zero) & EffectiveMask)) {
8123 const SCEV *ShiftedLHS =
nullptr;
8127 unsigned MulZeros = OpC->getAPInt().countr_zero();
8128 unsigned GCD = std::min(MulZeros, TZ);
8133 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8155 case Instruction::Or:
8164 case Instruction::Xor:
8167 if (CI->isMinusOne())
8176 if (LBO->getOpcode() == Instruction::And &&
8177 LCI->getValue() == CI->getValue())
8178 if (
const SCEVZeroExtendExpr *Z =
8181 const SCEV *Z0 =
Z->getOperand();
8188 if (CI->getValue().isMask(Z0TySize))
8194 APInt Trunc = CI->getValue().trunc(Z0TySize);
8203 case Instruction::Shl:
8221 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8230 ConstantInt *
X = ConstantInt::get(
8236 case Instruction::AShr:
8258 const SCEV *AddTruncateExpr =
nullptr;
8259 ConstantInt *ShlAmtCI =
nullptr;
8260 const SCEV *AddConstant =
nullptr;
8262 if (L &&
L->getOpcode() == Instruction::Add) {
8270 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8277 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8285 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8290 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8295 if (AddTruncateExpr && ShlAmtCI) {
8307 const APInt &ShlAmt = ShlAmtCI->
getValue();
8311 const SCEV *CompositeExpr =
8313 if (
L->getOpcode() != Instruction::Shl)
8314 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8323 switch (
U->getOpcode()) {
8324 case Instruction::Trunc:
8327 case Instruction::ZExt:
8330 case Instruction::SExt:
8340 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8341 Type *Ty =
U->getType();
8349 case Instruction::BitCast:
8355 case Instruction::PtrToAddr: {
8362 case Instruction::PtrToInt: {
8365 Type *DstIntTy =
U->getType();
8373 case Instruction::IntToPtr:
8377 case Instruction::SDiv:
8384 case Instruction::SRem:
8391 case Instruction::GetElementPtr:
8394 case Instruction::PHI:
8397 case Instruction::Select:
8398 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8401 case Instruction::Call:
8402 case Instruction::Invoke:
8407 switch (
II->getIntrinsicID()) {
8408 case Intrinsic::abs:
8412 case Intrinsic::umax:
8416 case Intrinsic::umin:
8420 case Intrinsic::smax:
8424 case Intrinsic::smin:
8428 case Intrinsic::usub_sat: {
8429 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8430 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8434 case Intrinsic::uadd_sat: {
8435 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8436 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8440 case Intrinsic::start_loop_iterations:
8441 case Intrinsic::annotation:
8442 case Intrinsic::ptr_annotation:
8446 case Intrinsic::vscale:
8466 auto *ExitCountType = ExitCount->
getType();
8467 assert(ExitCountType->isIntegerTy());
8469 1 + ExitCountType->getScalarSizeInBits());
8482 auto CanAddOneWithoutOverflow = [&]() {
8484 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8495 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8525 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8526 assert(L->isLoopExiting(ExitingBlock) &&
8527 "Exiting block must actually branch out of the loop!");
8536 const auto *MaxExitCount =
8544 L->getExitingBlocks(ExitingBlocks);
8546 std::optional<unsigned> Res;
8547 for (
auto *ExitingBB : ExitingBlocks) {
8551 Res = std::gcd(*Res, Multiple);
8553 return Res.value_or(1);
8557 const SCEV *ExitCount) {
8587 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8588 assert(L->isLoopExiting(ExitingBlock) &&
8589 "Exiting block must actually branch out of the loop!");
8599 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8601 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8603 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8613 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8616 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8619 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8627 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8634 return getBackedgeTakenInfo(L).getExact(L,
this);
8636 return getBackedgeTakenInfo(L).getConstantMax(
this);
8638 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8645 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8650 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8654 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8664 for (
PHINode &PN : Header->phis())
8665 if (Visited.
insert(&PN).second)
8669ScalarEvolution::BackedgeTakenInfo &
8670ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8671 auto &BTI = getBackedgeTakenInfo(L);
8672 if (BTI.hasFullInfo())
8675 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8678 return Pair.first->second;
8680 BackedgeTakenInfo
Result =
8681 computeBackedgeTakenCount(L,
true);
8683 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8686ScalarEvolution::BackedgeTakenInfo &
8687ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8693 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8694 BackedgeTakenCounts.try_emplace(L);
8696 return Pair.first->second;
8701 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8708 if (
Result.hasAnyInfo()) {
8711 auto LoopUsersIt = LoopUsers.find(L);
8712 if (LoopUsersIt != LoopUsers.end())
8714 forgetMemoizedResults(ToForget);
8717 for (PHINode &PN :
L->getHeader()->phis())
8718 ConstantEvolutionLoopExitValue.erase(&PN);
8726 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8735 BackedgeTakenCounts.clear();
8736 PredicatedBackedgeTakenCounts.clear();
8737 BECountUsers.clear();
8738 LoopPropertiesCache.clear();
8739 ConstantEvolutionLoopExitValue.clear();
8740 ValueExprMap.clear();
8741 ValuesAtScopes.clear();
8742 ValuesAtScopesUsers.clear();
8743 LoopDispositions.clear();
8744 BlockDispositions.clear();
8745 UnsignedRanges.clear();
8746 SignedRanges.clear();
8747 ExprValueMap.clear();
8749 ConstantMultipleCache.clear();
8750 PredicatedSCEVRewrites.clear();
8752 FoldCacheUser.clear();
8754void ScalarEvolution::visitAndClearUsers(
8758 while (!Worklist.
empty()) {
8765 if (It != ValueExprMap.
end()) {
8767 eraseValueFromMap(It->first);
8769 ConstantEvolutionLoopExitValue.erase(PN);
8783 while (!LoopWorklist.
empty()) {
8787 forgetBackedgeTakenCounts(CurrL,
false);
8788 forgetBackedgeTakenCounts(CurrL,
true);
8791 PredicatedSCEVRewrites.remove_if(
8792 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8794 auto LoopUsersItr = LoopUsers.find(CurrL);
8795 if (LoopUsersItr != LoopUsers.end())
8800 visitAndClearUsers(Worklist, Visited, ToForget);
8802 LoopPropertiesCache.erase(CurrL);
8805 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8807 forgetMemoizedResults(ToForget);
8824 visitAndClearUsers(Worklist, Visited, ToForget);
8826 forgetMemoizedResults(ToForget);
8838 struct InvalidationRootCollector {
8842 InvalidationRootCollector(
Loop *L) : L(L) {}
8844 bool follow(
const SCEV *S) {
8850 if (L->contains(AddRec->
getLoop()))
8855 bool isDone()
const {
return false; }
8858 InvalidationRootCollector
C(L);
8860 forgetMemoizedResults(
C.Roots);
8873 BlockDispositions.clear();
8874 LoopDispositions.clear();
8891 while (!Worklist.
empty()) {
8893 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8894 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8895 if (!LoopDispoRemoved && !BlockDispoRemoved)
8897 auto Users = SCEVUsers.find(Curr);
8898 if (
Users != SCEVUsers.end())
8911const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8915 if (!isComplete() || ExitNotTaken.
empty())
8926 for (
const auto &ENT : ExitNotTaken) {
8927 const SCEV *BECount = ENT.ExactNotTaken;
8930 "We should only have known counts for exiting blocks that dominate "
8933 Ops.push_back(BECount);
8938 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8939 "Predicate should be always true!");
8948const ScalarEvolution::ExitNotTakenInfo *
8949ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8950 const BasicBlock *ExitingBlock,
8951 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8952 for (
const auto &ENT : ExitNotTaken)
8953 if (ENT.ExitingBlock == ExitingBlock) {
8954 if (ENT.hasAlwaysTruePredicate())
8956 else if (Predicates) {
8966const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8968 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8969 if (!getConstantMax())
8972 for (
const auto &ENT : ExitNotTaken)
8973 if (!ENT.hasAlwaysTruePredicate()) {
8981 "No point in having a non-constant max backedge taken count!");
8982 return getConstantMax();
8985const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8987 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8995 for (
const auto &ENT : ExitNotTaken) {
8996 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8999 "We should only have known counts for exiting blocks that "
9005 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
9006 "Predicate should be always true!");
9009 if (ExitCounts.
empty())
9018bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
9020 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
9021 return !ENT.hasAlwaysTruePredicate();
9023 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
9039 this->ExactNotTaken = E = ConstantMaxNotTaken;
9040 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
9045 "Exact is not allowed to be less precise than Constant Max");
9048 "Exact is not allowed to be less precise than Symbolic Max");
9051 "Symbolic Max is not allowed to be less precise than Constant Max");
9054 "No point in having a non-constant max backedge taken count!");
9056 for (
const auto PredList : PredLists)
9057 for (
const auto *
P : PredList) {
9065 "Backedge count should be int");
9068 "Max backedge count should be int");
9081ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
9083 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
9084 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
9085 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9087 ExitNotTaken.reserve(ExitCounts.
size());
9088 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
9089 std::back_inserter(ExitNotTaken),
9090 [&](
const EdgeExitInfo &EEI) {
9091 BasicBlock *ExitBB = EEI.first;
9092 const ExitLimit &EL = EEI.second;
9093 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
9094 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
9099 "No point in having a non-constant max backedge taken count!");
9103ScalarEvolution::BackedgeTakenInfo
9104ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
9105 bool AllowPredicates) {
9107 L->getExitingBlocks(ExitingBlocks);
9109 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9112 bool CouldComputeBECount =
true;
9114 const SCEV *MustExitMaxBECount =
nullptr;
9115 const SCEV *MayExitMaxBECount =
nullptr;
9116 bool MustExitMaxOrZero =
false;
9117 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9128 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9129 if (ExitIfTrue == CI->
isZero())
9133 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9135 assert((AllowPredicates || EL.Predicates.empty()) &&
9136 "Predicated exit limit when predicates are not allowed!");
9141 ++NumExitCountsComputed;
9145 CouldComputeBECount =
false;
9152 "Exact is known but symbolic isn't?");
9153 ++NumExitCountsNotComputed;
9168 DT.dominates(ExitBB, Latch)) {
9169 if (!MustExitMaxBECount) {
9170 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9171 MustExitMaxOrZero = EL.MaxOrZero;
9174 EL.ConstantMaxNotTaken);
9178 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9181 EL.ConstantMaxNotTaken);
9185 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9189 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9195 for (
const auto &Pair : ExitCounts) {
9197 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9199 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9200 {
L, AllowPredicates});
9202 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9203 MaxBECount, MaxOrZero);
9206ScalarEvolution::ExitLimit
9207ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9208 bool IsOnlyExit,
bool AllowPredicates) {
9209 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9213 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9218 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9219 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9220 "It should have one successor in loop and one exit block!");
9231 if (!
L->contains(SBB)) {
9236 assert(Exit &&
"Exiting block must have at least one exit");
9237 return computeExitLimitFromSingleExitSwitch(
9238 L, SI, Exit, IsOnlyExit);
9245 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9246 bool AllowPredicates) {
9247 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9248 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9249 ControlsOnlyExit, AllowPredicates);
9252std::optional<ScalarEvolution::ExitLimit>
9253ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9254 bool ExitIfTrue,
bool ControlsOnlyExit,
9255 bool AllowPredicates) {
9257 (void)this->ExitIfTrue;
9258 (void)this->AllowPredicates;
9260 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9261 this->AllowPredicates == AllowPredicates &&
9262 "Variance in assumed invariant key components!");
9263 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9264 if (Itr == TripCountMap.end())
9265 return std::nullopt;
9269void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9271 bool ControlsOnlyExit,
9272 bool AllowPredicates,
9274 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9275 this->AllowPredicates == AllowPredicates &&
9276 "Variance in assumed invariant key components!");
9278 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9279 assert(InsertResult.second &&
"Expected successful insertion!");
9284ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9285 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9286 bool ControlsOnlyExit,
bool AllowPredicates) {
9288 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9292 ExitLimit EL = computeExitLimitFromCondImpl(
9293 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9294 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9298ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9299 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9300 bool ControlsOnlyExit,
bool AllowPredicates) {
9302 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9303 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9304 return *LimitFromBinOp;
9310 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9311 if (EL.hasFullInfo() || !AllowPredicates)
9315 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9335 const WithOverflowInst *WO;
9350 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9351 ControlsOnlyExit, AllowPredicates);
9352 if (EL.hasAnyInfo())
9357 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9360std::optional<ScalarEvolution::ExitLimit>
9361ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9365 bool AllowPredicates) {
9374 return std::nullopt;
9378 ExitLimit EL0 = computeExitLimitFromCondCached(
9379 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9380 ExitLimit EL1 = computeExitLimitFromCondCached(
9381 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9386 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9391 if (EitherMayExit) {
9401 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9403 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9406 EL1.ConstantMaxNotTaken);
9408 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9410 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9413 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9417 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9418 BECount = EL0.ExactNotTaken;
9431 SymbolicMaxBECount =
9433 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9437ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9438 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9439 bool AllowPredicates) {
9451 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9453 if (EL.hasAnyInfo())
9456 auto *ExhaustiveCount =
9457 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9460 return ExhaustiveCount;
9462 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9465ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9467 bool ControlsOnlyExit,
bool AllowPredicates) {
9492 ConstantRange CompRange =
9510 InnerLHS = ZExt->getOperand();
9557 if (EL.hasAnyInfo())
9574 if (EL.hasAnyInfo())
return EL;
9606 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9608 if (EL.hasAnyInfo())
9624 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9626 if (EL.hasAnyInfo())
9637ScalarEvolution::ExitLimit
9638ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9640 BasicBlock *ExitingBlock,
9641 bool ControlsOnlyExit) {
9642 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9645 if (
Switch->getDefaultDest() == ExitingBlock)
9649 "Default case must not exit the loop!");
9655 if (EL.hasAnyInfo())
9667 "Evaluation of SCEV at constant didn't fold correctly?");
9671ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9681 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9687 auto MatchPositiveShift =
9690 using namespace PatternMatch;
9692 ConstantInt *ShiftAmt;
9694 OutOpCode = Instruction::LShr;
9696 OutOpCode = Instruction::AShr;
9698 OutOpCode = Instruction::Shl;
9713 auto MatchShiftRecurrence =
9715 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9730 if (MatchPositiveShift(
LHS, V, OpC)) {
9731 PostShiftOpCode = OpC;
9737 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9740 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9746 MatchPositiveShift(BEValue, OpLHS, OpCodeOut) &&
9753 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9758 if (!MatchShiftRecurrence(
LHS, PN, OpCode))
9770 ConstantInt *StableValue =
nullptr;
9775 case Instruction::AShr: {
9783 StableValue = ConstantInt::get(Ty, 0);
9785 StableValue = ConstantInt::get(Ty, -1,
true);
9791 case Instruction::LShr:
9792 case Instruction::Shl:
9802 "Otherwise cannot be an operand to a branch instruction");
9804 if (
Result->isNullValue()) {
9806 const SCEV *UpperBound =
9823 if (
const Function *
F = CI->getCalledFunction())
9832 if (!L->contains(
I))
return false;
9837 return L->getHeader() ==
I->getParent();
9913 if (!
I)
return nullptr;
9926 std::vector<Constant*> Operands(
I->getNumOperands());
9928 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9932 if (!Operands[i])
return nullptr;
9937 if (!
C)
return nullptr;
9959 if (IncomingVal != CurrentVal) {
9962 IncomingVal = CurrentVal;
9974ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9977 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9986 DenseMap<Instruction *, Constant *> CurrentIterVals;
9988 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9994 for (PHINode &
PHI : Header->phis()) {
9996 CurrentIterVals[&
PHI] = StartCST;
9998 if (!CurrentIterVals.
count(PN))
9999 return RetVal =
nullptr;
10005 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
10008 unsigned IterationNum = 0;
10010 for (; ; ++IterationNum) {
10011 if (IterationNum == NumIterations)
10012 return RetVal = CurrentIterVals[PN];
10016 DenseMap<Instruction *, Constant *> NextIterVals;
10021 NextIterVals[PN] = NextPHI;
10023 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
10029 for (
const auto &
I : CurrentIterVals) {
10031 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
10036 for (
const auto &
I : PHIsToCompute) {
10037 PHINode *
PHI =
I.first;
10040 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10043 if (NextPHI !=
I.second)
10044 StoppedEvolving =
false;
10049 if (StoppedEvolving)
10050 return RetVal = CurrentIterVals[PN];
10052 CurrentIterVals.swap(NextIterVals);
10056const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
10066 DenseMap<Instruction *, Constant *> CurrentIterVals;
10068 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10071 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
10073 for (PHINode &
PHI : Header->phis()) {
10075 CurrentIterVals[&
PHI] = StartCST;
10077 if (!CurrentIterVals.
count(PN))
10085 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10092 if (CondVal->getValue() == uint64_t(ExitWhen)) {
10093 ++NumBruteForceTripCountsComputed;
10098 DenseMap<Instruction *, Constant *> NextIterVals;
10104 for (
const auto &
I : CurrentIterVals) {
10106 if (!
PHI ||
PHI->getParent() != Header)
continue;
10109 for (PHINode *
PHI : PHIsToCompute) {
10111 if (NextPHI)
continue;
10113 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10116 CurrentIterVals.
swap(NextIterVals);
10127 for (
auto &LS : Values)
10129 return LS.second ? LS.second : V;
10134 const SCEV *
C = computeSCEVAtScope(V, L);
10135 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10136 if (LS.first == L) {
10139 ValuesAtScopesUsers[
C].push_back({L, V});
10150 switch (V->getSCEVType()) {
10190 assert(!
C->getType()->isPointerTy() &&
10191 "Can only have one pointer, and it must be last");
10216const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10217 SmallVectorImpl<SCEVUse> &NewOps) {
10252const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10253 switch (
V->getSCEVType()) {
10264 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10275 for (++i; i !=
e; ++i)
10320 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10330 for (++i; i !=
e; ++i) {
10335 return getWithOperands(V, NewOps);
10350 const Loop *CurrLoop = this->LI[
I->getParent()];
10361 if (BackedgeTakenCount->
isZero()) {
10362 Value *InitValue =
nullptr;
10363 bool MultipleInitValues =
false;
10369 MultipleInitValues =
true;
10374 if (!MultipleInitValues && InitValue)
10383 unsigned InLoopPred =
10394 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10408 SmallVector<Constant *, 4> Operands;
10409 Operands.
reserve(
I->getNumOperands());
10410 bool MadeImprovement =
false;
10425 MadeImprovement |= OrigV != OpV;
10430 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10435 if (!MadeImprovement)
10456const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10458 return stripInjectiveFunctions(ZExt->getOperand());
10460 return stripInjectiveFunctions(SExt->getOperand());
10478 assert(
A != 0 &&
"A must be non-zero.");
10494 if (MinTZ < Mult2 && L->getLoopPredecessor())
10496 if (MinTZ < Mult2) {
10519 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10539static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10545 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10546 << *AddRec <<
'\n');
10549 if (!LC || !MC || !
NC) {
10550 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10551 return std::nullopt;
10557 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10565 N =
N.sext(NewWidth);
10566 M = M.sext(NewWidth);
10567 L = L.sext(NewWidth);
10584 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10585 <<
", multiplied by " <<
T <<
'\n');
10594 std::optional<APInt>
Y) {
10596 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10599 return XW.
slt(YW) ? *
X : *
Y;
10602 return std::nullopt;
10603 return X ? *
X : *
Y;
10620 return std::nullopt;
10621 unsigned W =
X->getBitWidth();
10641static std::optional<APInt>
10647 return std::nullopt;
10650 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10651 std::optional<APInt>
X =
10654 return std::nullopt;
10659 return std::nullopt;
10674static std::optional<APInt>
10678 "Starting value of addrec should be 0");
10679 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10680 <<
Range <<
", addrec " << *AddRec <<
'\n');
10684 "Addrec's initial value should be in range");
10690 return std::nullopt;
10700 auto SolveForBoundary =
10701 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10704 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10705 << Bound <<
" (before multiplying by " << M <<
")\n");
10708 std::optional<APInt> SO;
10711 "signed overflow\n");
10715 "unsigned overflow\n");
10716 std::optional<APInt> UO =
10719 auto LeavesRange = [&] (
const APInt &
X) {
10736 return {std::nullopt,
false};
10741 if (LeavesRange(*Min))
10742 return { Min,
true };
10743 std::optional<APInt> Max = Min == SO ? UO : SO;
10744 if (LeavesRange(*Max))
10745 return { Max,
true };
10748 return {std::nullopt,
true};
10755 auto SL = SolveForBoundary(
Lower);
10756 auto SU = SolveForBoundary(
Upper);
10759 if (!SL.second || !SU.second)
10760 return std::nullopt;
10803ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10805 bool ControlsOnlyExit,
10806 bool AllowPredicates) {
10817 if (
C->getValue()->isZero())
return C;
10821 const SCEVAddRecExpr *AddRec =
10824 if (!AddRec && AllowPredicates)
10830 if (!AddRec || AddRec->
getLoop() != L)
10841 return ExitLimit(R, R, R,
false, Predicates);
10899 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10925 const SCEV *
Exact =
10933 const SCEV *SymbolicMax =
10935 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10944 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10952 return ExitLimit(
E, M, S,
false, Predicates);
10955ScalarEvolution::ExitLimit
10956ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10964 if (!
C->getValue()->isZero())
10974std::pair<const BasicBlock *, const BasicBlock *>
10975ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10986 if (
const Loop *L = LI.getLoopFor(BB))
10987 return {
L->getLoopPredecessor(),
L->getHeader()};
10989 return {
nullptr, BB};
10998 if (
A ==
B)
return true;
11013 if (ComputesEqualValues(AI, BI))
11021 const SCEV *Op0, *Op1;
11040 auto TrivialCase = [&](
bool TriviallyTrue) {
11049 const SCEV *NewLHS, *NewRHS;
11073 return TrivialCase(
false);
11074 return TrivialCase(
true);
11097 const APInt &
RA = RC->getAPInt();
11099 bool SimplifiedByConstantRange =
false;
11104 return TrivialCase(
true);
11106 return TrivialCase(
false);
11115 Changed = SimplifiedByConstantRange =
true;
11119 if (!SimplifiedByConstantRange) {
11136 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11142 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11148 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11154 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11166 return TrivialCase(
true);
11168 return TrivialCase(
false);
11273 auto NonRecursive = [OrNegative](
const SCEV *S) {
11275 return C->getAPInt().isPowerOf2() ||
11276 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11282 if (NonRecursive(S))
11308 APInt C = Cst->getAPInt();
11309 return C.urem(M) == 0;
11317 const SCEV *SmodM =
11332 for (
auto *
A : Assumptions)
11333 if (
A->implies(
P, *
this))
11346std::pair<const SCEV *, const SCEV *>
11349 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11351 return { Start, Start };
11353 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11362 getUsedLoops(LHS, LoopsUsed);
11363 getUsedLoops(RHS, LoopsUsed);
11365 if (LoopsUsed.
empty())
11370 for (
const auto *L1 : LoopsUsed)
11371 for (
const auto *L2 : LoopsUsed)
11372 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11373 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11374 "Domination relationship is not a linear order");
11404 SplitRHS.second) &&
11416 if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
11420 return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11430 return std::nullopt;
11445 if (KnownWithoutContext)
11446 return KnownWithoutContext;
11453 return std::nullopt;
11459 const Loop *L = LHS->getLoop();
11464std::optional<ScalarEvolution::MonotonicPredicateType>
11467 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11473 auto ResultSwapped =
11476 assert(*ResultSwapped != *Result &&
11477 "monotonicity should flip as we flip the predicate");
11484std::optional<ScalarEvolution::MonotonicPredicateType>
11485ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11499 return std::nullopt;
11503 "Should be greater or less!");
11507 if (!LHS->hasNoUnsignedWrap())
11508 return std::nullopt;
11512 "Relational predicate is either signed or unsigned!");
11513 if (!
LHS->hasNoSignedWrap())
11514 return std::nullopt;
11516 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11524 return std::nullopt;
11527std::optional<ScalarEvolution::LoopInvariantPredicate>
11534 return std::nullopt;
11541 if (!ArLHS || ArLHS->
getLoop() != L)
11542 return std::nullopt;
11546 return std::nullopt;
11572 return std::nullopt;
11609 return std::nullopt;
11612std::optional<ScalarEvolution::LoopInvariantPredicate>
11617 Pred, LHS, RHS, L, CtxI, MaxIter))
11627 Pred, LHS, RHS, L, CtxI,
Op))
11629 return std::nullopt;
11632std::optional<ScalarEvolution::LoopInvariantPredicate>
11647 return std::nullopt;
11654 if (!AR || AR->
getLoop() != L)
11655 return std::nullopt;
11660 Pred = Pred.dropSameSign();
11664 return std::nullopt;
11670 if (Step != One && Step != MinusOne)
11671 return std::nullopt;
11677 return std::nullopt;
11683 return std::nullopt;
11691 if (Step == MinusOne)
11695 return std::nullopt;
11701bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11707 auto CheckRange = [&](
bool IsSigned) {
11710 return RangeLHS.
icmp(Pred, RangeRHS);
11719 if (CheckRange(
true) || CheckRange(
false))
11728bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11737 SCEVUse XNonConstOp, XConstOp;
11738 SCEVUse YNonConstOp, YConstOp;
11742 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11745 XFlagsPresent = ExpectedFlags;
11750 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11753 YFlagsPresent = ExpectedFlags;
11756 if (YNonConstOp != XNonConstOp)
11764 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11767 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11827bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11848bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11849 const SCEV *
LHS,
const SCEV *
RHS) {
11854 return any_of(*BB, [&](
const Instruction &
I) {
11855 using namespace llvm::PatternMatch;
11860 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11874 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11879 "This cannot be done on broken IR!");
11882 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11891 if (LoopContinuePredicate &&
11892 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11893 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11898 if (WalkingBEDominatingConds)
11904 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11905 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11912 const SCEV *LoopCounter =
11920 for (
auto &AssumeVH : AC.assumptions()) {
11927 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11931 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11934 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11935 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11936 assert(DTN &&
"should reach the loop header before reaching the root!");
11939 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11957 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
11970 if (!DT.isReachableFromEntry(BB))
11974 "This cannot be done on broken IR!");
11982 const bool ProvingStrictComparison =
11984 bool ProvedNonStrictComparison =
false;
11985 bool ProvedNonEquality =
false;
11988 if (!ProvedNonStrictComparison)
11989 ProvedNonStrictComparison = Fn(NonStrictPredicate);
11990 if (!ProvedNonEquality)
11992 if (ProvedNonStrictComparison && ProvedNonEquality)
11997 if (ProvingStrictComparison) {
11999 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
12001 if (SplitAndProve(ProofFn))
12006 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
12008 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
12010 if (ProvingStrictComparison) {
12012 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
12014 if (SplitAndProve(ProofFn))
12023 const Loop *ContainingLoop = LI.getLoopFor(BB);
12025 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
12029 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
12030 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
12033 if (!BlockEntryPredicate)
12042 for (
auto &AssumeVH : AC.assumptions()) {
12046 if (!DT.dominates(CI, BB))
12049 if (ProveViaCond(CI->getArgOperand(0),
false))
12055 F.getParent(), Intrinsic::experimental_guard);
12057 for (
const auto *GU : GuardDecl->users())
12059 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12060 if (ProveViaCond(Guard->getArgOperand(0),
false))
12075 "LHS is not available at Loop Entry");
12077 "RHS is not available at Loop Entry");
12079 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12090 if (FoundCondValue ==
12094 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12098 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12101 const Value *Op0, *Op1;
12104 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12108 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12109 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12113 if (!ICI)
return false;
12117 CmpPredicate FoundPred;
12126 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12129bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12130 const SCEV *
RHS, CmpPredicate FoundPred,
12131 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12132 const Instruction *CtxI) {
12142 auto *WideType = FoundLHS->
getType();
12154 TruncFoundLHS, TruncFoundRHS, CtxI))
12180 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12184bool ScalarEvolution::isImpliedCondBalancedTypes(
12189 "Types should be balanced!");
12196 if (FoundLHS == FoundRHS)
12200 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12212 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12229 LHS, FoundLHS, FoundRHS, CtxI);
12231 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12253 assert(P1 != P2 &&
"Handled earlier!");
12257 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12261 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12264 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12265 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12266 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12271 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12282 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12283 CanonicalRHS, CanonicalFoundLHS,
12284 CanonicalFoundRHS);
12289 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12290 CanonicalRHS, CanonicalFoundLHS,
12291 CanonicalFoundRHS);
12298 const SCEVConstant *
C =
nullptr;
12299 const SCEV *
V =
nullptr;
12317 if (Min ==
C->getAPInt()) {
12322 APInt SharperMin = Min + 1;
12325 case ICmpInst::ICMP_SGE:
12326 case ICmpInst::ICMP_UGE:
12329 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12334 case ICmpInst::ICMP_SGT:
12335 case ICmpInst::ICMP_UGT:
12345 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12350 case ICmpInst::ICMP_SLE:
12351 case ICmpInst::ICMP_ULE:
12352 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12353 LHS, V, getConstant(SharperMin), CtxI))
12357 case ICmpInst::ICMP_SLT:
12358 case ICmpInst::ICMP_ULT:
12359 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12360 LHS, V, getConstant(Min), CtxI))
12374 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12378 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12381 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12397std::optional<APInt>
12404 APInt DiffMul(BW, 1);
12407 for (
unsigned I = 0;
I < 8; ++
I) {
12416 if (LAR->getLoop() != MAR->getLoop())
12417 return std::nullopt;
12421 if (!LAR->isAffine() || !MAR->isAffine())
12422 return std::nullopt;
12424 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12425 return std::nullopt;
12427 Less = LAR->getStart();
12428 More = MAR->getStart();
12433 auto MatchConstMul =
12434 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12439 return std::nullopt;
12441 if (
auto MatchedMore = MatchConstMul(More)) {
12442 if (
auto MatchedLess = MatchConstMul(
Less)) {
12443 if (MatchedMore->second == MatchedLess->second) {
12444 More = MatchedMore->first;
12445 Less = MatchedLess->first;
12446 DiffMul *= MatchedMore->second;
12457 Diff +=
C->getAPInt() * DiffMul;
12460 Diff -=
C->getAPInt() * DiffMul;
12463 Multiplicity[S] +=
Mul;
12465 auto Decompose = [&](
const SCEV *S,
int Mul) {
12472 Decompose(More, 1);
12473 Decompose(
Less, -1);
12477 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12478 for (
const auto &[S,
Mul] : Multiplicity) {
12483 return std::nullopt;
12485 }
else if (
Mul == -1) {
12487 return std::nullopt;
12490 return std::nullopt;
12494 if (NewMore == More || NewLess ==
Less)
12495 return std::nullopt;
12501 if (!More && !
Less)
12505 if (!More || !
Less)
12506 return std::nullopt;
12510 return std::nullopt;
12513bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12535 const auto *Latch = L->getLoopLatch();
12538 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12547 const auto *Latch = L->getLoopLatch();
12550 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12560bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12563 const SCEV *FoundLHS,
12564 const SCEV *FoundRHS) {
12573 if (!AddRecFoundLHS)
12580 const Loop *
L = AddRecFoundLHS->getLoop();
12581 if (L != AddRecLHS->getLoop())
12620 if (!RDiff || *LDiff != *RDiff)
12623 if (LDiff->isMinValue())
12626 APInt FoundRHSLimit;
12629 FoundRHSLimit = -(*RDiff);
12641bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12642 const SCEV *
RHS,
const SCEV *FoundLHS,
12643 const SCEV *FoundRHS,
unsigned Depth) {
12644 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12648 bool Erased = PendingMerges.erase(LPhi);
12649 assert(Erased &&
"Failed to erase LPhi!");
12653 bool Erased = PendingMerges.erase(RPhi);
12654 assert(Erased &&
"Failed to erase RPhi!");
12662 if (!PendingMerges.insert(Phi).second)
12676 if (!PendingMerges.insert(Phi).second)
12682 if (!LPhi && !RPhi)
12693 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12697 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12698 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12699 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12700 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12703 if (RPhi && RPhi->getParent() == LBB) {
12710 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12711 if (!ProvedEasily(L, R))
12722 auto *RLoop = RAR->
getLoop();
12723 auto *Predecessor = RLoop->getLoopPredecessor();
12724 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12726 if (!ProvedEasily(L1, RAR->
getStart()))
12728 auto *Latch = RLoop->getLoopLatch();
12729 assert(Latch &&
"Loop with AddRec with no latch?");
12750 if (
auto *Loop = LI.getLoopFor(LBB))
12753 if (!ProvedEasily(L,
RHS))
12760bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12763 const SCEV *FoundLHS,
12764 const SCEV *FoundRHS) {
12767 if (
RHS == FoundRHS) {
12772 if (
LHS != FoundLHS)
12779 Value *Shiftee, *ShiftValue;
12781 using namespace PatternMatch;
12782 if (
match(SUFoundRHS->getValue(),
12784 auto *ShifteeS =
getSCEV(Shiftee);
12802bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12804 const SCEV *FoundLHS,
12805 const SCEV *FoundRHS,
12806 const Instruction *CtxI) {
12807 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12809 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12811 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12812 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12814 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12818template <
typename MinMaxExprType>
12820 const SCEV *Candidate) {
12825 return is_contained(MinMaxExpr->operands(), Candidate);
12838 const SCEV *LStart, *RStart, *Step;
12888bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12890 const SCEV *FoundLHS,
12891 const SCEV *FoundRHS,
12895 "LHS and RHS have different sizes?");
12898 "FoundLHS and FoundRHS have different sizes?");
12932 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
12934 return Ext->getOperand();
12941 auto *OrigLHS =
LHS;
12942 auto *OrigFoundLHS = FoundLHS;
12943 LHS = GetOpFromSExt(
LHS);
12944 FoundLHS = GetOpFromSExt(FoundLHS);
12947 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
12950 FoundRHS,
Depth + 1);
12963 if (!LHSAddExpr->hasNoSignedWrap())
12966 SCEVUse LL = LHSAddExpr->getOperand(0);
12967 SCEVUse LR = LHSAddExpr->getOperand(1);
12971 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
12972 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
12977 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
12983 using namespace llvm::PatternMatch;
13002 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13010 auto *DTy = Denominator->getType();
13011 auto *FRHSTy = FoundRHS->
getType();
13012 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13031 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13042 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13044 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13052 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13085bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13089 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13092 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13095bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13098 const SCEV *FoundLHS,
13099 const SCEV *FoundRHS) {
13135 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13141bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13142 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13143 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13157 ConstantRange FoundLHSRange =
13161 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13168 return LHSRange.
icmp(Pred, ConstRHS);
13171bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13184 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13192 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13195bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
13207 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
13215 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
13227const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
13228 const SCEV *Stride,
13259 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13270 :
APIntOps::umax(MaxEnd, MinStart);
13277ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13278 const Loop *L,
bool IsSigned,
13279 bool ControlsOnlyExit,
bool AllowPredicates) {
13283 bool PredicatedIV =
false;
13288 auto canProveNUW = [&]() {
13291 if (!ControlsOnlyExit)
13312 Limit = Limit.
zext(OuterBitWidth);
13324 Type *Ty = ZExt->getType();
13335 if (!
IV && AllowPredicates) {
13340 PredicatedIV =
true;
13344 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13358 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13361 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13366 if (!PositiveStride) {
13418 auto wouldZeroStrideBeUB = [&]() {
13430 if (!wouldZeroStrideBeUB()) {
13434 }
else if (!NoWrap) {
13437 if (canIVOverflowOnLT(
RHS, Stride, IsSigned))
13450 const SCEV *
Start =
IV->getStart();
13456 const SCEV *OrigStart =
Start;
13457 const SCEV *OrigRHS =
RHS;
13458 if (
Start->getType()->isPointerTy()) {
13469 const SCEV *End =
nullptr, *BECount =
nullptr,
13470 *BECountIfBackedgeTaken =
nullptr;
13473 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13474 any(RHSAddRec->getNoWrapFlags())) {
13487 const SCEV *RHSStart = RHSAddRec->getStart();
13488 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13500 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13509 BECountIfBackedgeTaken =
13514 if (BECount ==
nullptr) {
13519 const SCEV *MaxBECount = computeMaxBECountForLT(
13522 MaxBECount,
false , Predicates);
13529 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13556 const SCEV *Numerator =
13562 auto canProveRHSGreaterThanEqualStart = [&]() {
13581 auto *StartMinusOne =
13588 if (canProveRHSGreaterThanEqualStart()) {
13603 BECountIfBackedgeTaken =
13619 bool MayAddOverflow = [&] {
13665 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13679 if (!MayAddOverflow) {
13691 const SCEV *ConstantMaxBECount;
13692 bool MaxOrZero =
false;
13694 ConstantMaxBECount = BECount;
13695 }
else if (BECountIfBackedgeTaken &&
13700 ConstantMaxBECount = BECountIfBackedgeTaken;
13703 ConstantMaxBECount = computeMaxBECountForLT(
13711 const SCEV *SymbolicMaxBECount =
13713 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13717ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13718 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13719 bool ControlsOnlyExit,
bool AllowPredicates) {
13726 if (!
IV && AllowPredicates)
13733 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13737 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13750 if (!Stride->
isOne() && !NoWrap)
13751 if (canIVOverflowOnGT(
RHS, Stride, IsSigned))
13754 const SCEV *
Start =
IV->getStart();
13755 const SCEV *End =
RHS;
13766 if (
Start->getType()->isPointerTy()) {
13801 const SCEV *ConstantMaxBECount =
13808 ConstantMaxBECount = BECount;
13809 const SCEV *SymbolicMaxBECount =
13812 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13818 if (
Range.isFullSet())
13823 if (!SC->getValue()->isZero()) {
13829 return ShiftedAddRec->getNumIterationsInRange(
13830 Range.subtract(SC->getAPInt()), SE);
13861 APInt ExitVal = (End +
A).udiv(
A);
13874 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13875 "Linear scev computation is off in a bad way!");
13906 assert(!
Last->isZero() &&
"Recurrency with zero step?");
13931 Ty = Store->getValueOperand()->getType();
13933 Ty = Load->getType();
13946 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13948 SE->ConstantEvolutionLoopExitValue.erase(PN);
13949 SE->eraseValueFromMap(getValPtr());
13953void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
13954 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13964 : CallbackVH(
V), SE(se) {}
13973 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
13975 LoopDispositions(64), BlockDispositions(64) {
13987 F.getParent(), Intrinsic::experimental_guard);
13988 HasGuards = GuardDecl && !GuardDecl->use_empty();
13992 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
13993 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
13994 ValueExprMap(
std::
move(Arg.ValueExprMap)),
13995 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
13996 PendingMerges(
std::
move(Arg.PendingMerges)),
13997 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
13998 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
13999 PredicatedBackedgeTakenCounts(
14000 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14001 BECountUsers(
std::
move(Arg.BECountUsers)),
14002 ConstantEvolutionLoopExitValue(
14003 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14004 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14005 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14006 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14007 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14008 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14009 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14010 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14011 SignedRanges(
std::
move(Arg.SignedRanges)),
14012 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14013 UniquePreds(
std::
move(Arg.UniquePreds)),
14014 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14015 LoopUsers(
std::
move(Arg.LoopUsers)),
14016 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14017 FirstUnknown(Arg.FirstUnknown) {
14018 Arg.FirstUnknown =
nullptr;
14027 Tmp->~SCEVUnknown();
14029 FirstUnknown =
nullptr;
14031 ExprValueMap.clear();
14032 ValueExprMap.clear();
14034 BackedgeTakenCounts.clear();
14035 PredicatedBackedgeTakenCounts.clear();
14037 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14038 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14039 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14040 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14062 L->getHeader()->printAsOperand(OS,
false);
14066 L->getExitingBlocks(ExitingBlocks);
14067 if (ExitingBlocks.
size() != 1)
14068 OS <<
"<multiple exits> ";
14072 OS <<
"backedge-taken count is ";
14075 OS <<
"Unpredictable backedge-taken count.";
14078 if (ExitingBlocks.
size() > 1)
14079 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14080 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14088 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14091 OS <<
"\n Predicates:\n";
14092 for (
const auto *
P : Predicates)
14100 L->getHeader()->printAsOperand(OS,
false);
14105 OS <<
"constant max backedge-taken count is ";
14108 OS <<
", actual taken count either this or zero.";
14110 OS <<
"Unpredictable constant max backedge-taken count. ";
14115 L->getHeader()->printAsOperand(OS,
false);
14120 OS <<
"symbolic max backedge-taken count is ";
14123 OS <<
", actual taken count either this or zero.";
14125 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14129 if (ExitingBlocks.
size() > 1)
14130 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14131 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14141 OS <<
"\n predicated symbolic max exit count for "
14142 << ExitingBlock->
getName() <<
": ";
14144 OS <<
"\n Predicates:\n";
14145 for (
const auto *
P : Predicates)
14155 assert(!Preds.
empty() &&
"Different predicated BTC, but no predicates");
14157 L->getHeader()->printAsOperand(OS,
false);
14160 OS <<
"Predicated backedge-taken count is ";
14163 OS <<
"Unpredictable predicated backedge-taken count.";
14165 OS <<
" Predicates:\n";
14166 for (
const auto *
P : Preds)
14171 auto *PredConstantMax =
14173 if (PredConstantMax != ConstantBTC) {
14175 "different predicated constant max BTC but no predicates");
14177 L->getHeader()->printAsOperand(OS,
false);
14180 OS <<
"Predicated constant max backedge-taken count is ";
14183 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14185 OS <<
" Predicates:\n";
14186 for (
const auto *
P : Preds)
14191 auto *PredSymbolicMax =
14193 if (SymbolicBTC != PredSymbolicMax) {
14195 "Different predicated symbolic max BTC, but no predicates");
14197 L->getHeader()->printAsOperand(OS,
false);
14200 OS <<
"Predicated symbolic max backedge-taken count is ";
14203 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14205 OS <<
" Predicates:\n";
14206 for (
const auto *
P : Preds)
14212 L->getHeader()->printAsOperand(OS,
false);
14239 OS <<
"Computable";
14249 OS <<
"DoesNotDominate";
14255 OS <<
"ProperlyDominates";
14272 OS <<
"Classifying expressions for: ";
14273 F.printAsOperand(OS,
false);
14288 const Loop *L = LI.getLoopFor(
I.getParent());
14303 OS <<
"\t\t" "Exits: ";
14306 OS <<
"<<Unknown>>";
14312 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14314 Iter->getHeader()->printAsOperand(OS,
false);
14322 InnerL->getHeader()->printAsOperand(OS,
false);
14333 OS <<
"Determining loop execution counts for: ";
14334 F.printAsOperand(OS,
false);
14342 auto &Values = LoopDispositions[S];
14343 for (
auto &V : Values) {
14344 if (V.getPointer() == L)
14349 auto &Values2 = LoopDispositions[S];
14351 if (V.getPointer() == L) {
14360ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14378 if (L->contains(AR->
getLoop()) &&
14380 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14385 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14386 " dominate the contained loop's header?");
14414 bool HasVarying =
false;
14415 bool HasUniform =
false;
14457 auto &Values = BlockDispositions[S];
14458 for (
auto &V : Values) {
14459 if (V.getPointer() == BB)
14464 auto &Values2 = BlockDispositions[S];
14466 if (V.getPointer() == BB) {
14475ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14505 bool Proper =
true;
14516 if (Instruction *
I =
14518 if (
I->getParent() == BB)
14520 if (DT.properlyDominates(
I->getParent(), BB))
14543void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14546 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14547 auto It = BECounts.find(L);
14548 if (It != BECounts.end()) {
14549 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14550 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14552 auto UserIt = BECountUsers.find(S);
14553 assert(UserIt != BECountUsers.end());
14558 BECounts.erase(It);
14566 while (!Worklist.
empty()) {
14568 auto Users = SCEVUsers.find(Curr);
14569 if (
Users != SCEVUsers.end())
14570 for (
const auto *User :
Users->second)
14571 if (ToForget.
insert(User).second)
14575 for (
const auto *S : ToForget)
14576 forgetMemoizedResultsImpl(S);
14578 PredicatedSCEVRewrites.remove_if(
14579 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14582void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14583 LoopDispositions.erase(S);
14584 BlockDispositions.erase(S);
14585 UnsignedRanges.erase(S);
14586 SignedRanges.erase(S);
14587 HasRecMap.erase(S);
14588 ConstantMultipleCache.erase(S);
14591 UnsignedWrapViaInductionTried.erase(AR);
14592 SignedWrapViaInductionTried.erase(AR);
14595 auto ExprIt = ExprValueMap.find(S);
14596 if (ExprIt != ExprValueMap.end()) {
14597 for (
Value *V : ExprIt->second) {
14598 auto ValueIt = ValueExprMap.find_as(V);
14599 if (ValueIt != ValueExprMap.end())
14600 ValueExprMap.erase(ValueIt);
14602 ExprValueMap.erase(ExprIt);
14605 auto ScopeIt = ValuesAtScopes.find(S);
14606 if (ScopeIt != ValuesAtScopes.end()) {
14607 for (
const auto &Pair : ScopeIt->second)
14610 std::make_pair(Pair.first, S));
14611 ValuesAtScopes.erase(ScopeIt);
14614 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14615 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14616 for (
const auto &Pair : ScopeUserIt->second)
14617 llvm::erase(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
14618 ValuesAtScopesUsers.erase(ScopeUserIt);
14621 auto BEUsersIt = BECountUsers.find(S);
14622 if (BEUsersIt != BECountUsers.end()) {
14624 auto Copy = BEUsersIt->second;
14625 for (
const auto &Pair : Copy)
14626 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14627 BECountUsers.erase(BEUsersIt);
14630 auto FoldUser = FoldCacheUser.find(S);
14631 if (FoldUser != FoldCacheUser.end())
14632 for (
auto &KV : FoldUser->second)
14633 FoldCache.erase(KV);
14634 FoldCacheUser.erase(S);
14638ScalarEvolution::getUsedLoops(
const SCEV *S,
14640 struct FindUsedLoops {
14641 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14642 : LoopsUsed(LoopsUsed) {}
14643 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14644 bool follow(
const SCEV *S) {
14650 bool isDone()
const {
return false; }
14653 FindUsedLoops
F(LoopsUsed);
14654 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14657void ScalarEvolution::getReachableBlocks(
14660 Worklist.
push_back(&F.getEntryBlock());
14661 while (!Worklist.
empty()) {
14663 if (!Reachable.
insert(BB).second)
14671 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14678 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14682 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14717 SCEVMapper SCM(SE2);
14719 SE2.getReachableBlocks(ReachableBlocks, F);
14721 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14739 while (!LoopStack.
empty()) {
14745 if (!ReachableBlocks.
contains(L->getHeader()))
14750 auto It = BackedgeTakenCounts.find(L);
14751 if (It == BackedgeTakenCounts.end())
14755 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14775 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14776 if (Delta && !Delta->
isZero()) {
14777 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14778 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14779 dbgs() <<
"New: " << *NewBECount <<
"\n";
14780 dbgs() <<
"Delta: " << *Delta <<
"\n";
14788 while (!Worklist.
empty()) {
14790 if (ValidLoops.
insert(L).second)
14791 Worklist.
append(L->begin(), L->end());
14793 for (
const auto &KV : ValueExprMap) {
14798 "AddRec references invalid loop");
14803 auto It = ExprValueMap.find(KV.second);
14804 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14805 dbgs() <<
"Value " << *KV.first
14806 <<
" is in ValueExprMap but not in ExprValueMap\n";
14811 if (!ReachableBlocks.
contains(
I->getParent()))
14813 const SCEV *OldSCEV = SCM.visit(KV.second);
14815 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14816 if (Delta && !Delta->
isZero()) {
14817 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14818 <<
"Old: " << *OldSCEV <<
"\n"
14819 <<
"New: " << *NewSCEV <<
"\n"
14820 <<
"Delta: " << *Delta <<
"\n";
14826 for (
const auto &KV : ExprValueMap) {
14827 for (
Value *V : KV.second) {
14828 const SCEV *S = ValueExprMap.lookup(V);
14830 dbgs() <<
"Value " << *V
14831 <<
" is in ExprValueMap but not in ValueExprMap\n";
14834 if (S != KV.first) {
14835 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14836 << *KV.first <<
"\n";
14843 for (
const auto &S : UniqueSCEVs) {
14848 auto It = SCEVUsers.find(
Op);
14849 if (It != SCEVUsers.end() && It->second.count(&S))
14851 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14852 <<
" is not being tracked!\n";
14858 for (
const auto &ValueAndVec : ValuesAtScopes) {
14860 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14861 const Loop *L = LoopAndValueAtScope.first;
14862 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
14864 auto It = ValuesAtScopesUsers.find(ValueAtScope);
14865 if (It != ValuesAtScopesUsers.end() &&
14868 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14869 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14875 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14876 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14877 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14878 const Loop *L = LoopAndValue.first;
14879 const SCEV *
Value = LoopAndValue.second;
14881 auto It = ValuesAtScopes.find(
Value);
14882 if (It != ValuesAtScopes.end() &&
14883 is_contained(It->second, std::make_pair(L, ValueAtScope)))
14885 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14886 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14892 auto VerifyBECountUsers = [&](
bool Predicated) {
14894 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14895 for (
const auto &LoopAndBEInfo : BECounts) {
14896 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14897 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14899 auto UserIt = BECountUsers.find(S);
14900 if (UserIt != BECountUsers.end() &&
14901 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14903 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14904 <<
" missing from BECountUsers\n";
14911 VerifyBECountUsers(
false);
14912 VerifyBECountUsers(
true);
14915 for (
auto &[S, Values] : LoopDispositions) {
14916 for (
auto [
Loop, CachedDisposition] : Values) {
14918 if (CachedDisposition != RecomputedDisposition) {
14919 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
14920 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
14921 << RecomputedDisposition <<
"\n";
14928 for (
auto &[S, Values] : BlockDispositions) {
14929 for (
auto [BB, CachedDisposition] : Values) {
14931 if (CachedDisposition != RecomputedDisposition) {
14932 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
14933 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
14934 <<
", actual " << RecomputedDisposition <<
"\n";
14941 for (
auto [
FoldID, Expr] : FoldCache) {
14942 auto I = FoldCacheUser.find(Expr);
14943 if (
I == FoldCacheUser.end()) {
14944 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
14949 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
14953 for (
auto [Expr, IDs] : FoldCacheUser) {
14954 for (
auto &
FoldID : IDs) {
14957 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
14962 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
14963 <<
" != " << *Expr <<
"!\n";
14974 for (
auto [S, Multiple] : ConstantMultipleCache) {
14976 if ((Multiple != 0 && RecomputedMultiple != 0 &&
14977 Multiple.
urem(RecomputedMultiple) != 0 &&
14978 RecomputedMultiple.
urem(Multiple) != 0)) {
14979 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
14980 << *S <<
" : Computed " << RecomputedMultiple
14981 <<
" but cache contains " << Multiple <<
"!\n";
14989 FunctionAnalysisManager::Invalidator &Inv) {
15021 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15022 <<
F.getName() <<
"':\n";
15028 "Scalar Evolution Analysis",
false,
true)
15077 const SCEV *LHS,
const SCEV *RHS) {
15079 assert(LHS->getType() == RHS->getType() &&
15080 "Type mismatch between LHS and RHS");
15083 ID.AddInteger(Pred);
15084 ID.AddPointer(LHS);
15085 ID.AddPointer(RHS);
15086 void *IP =
nullptr;
15087 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
15091 UniquePreds.InsertNode(Eq, IP);
15102 ID.AddInteger(AddedFlags);
15103 void *IP =
nullptr;
15104 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
15106 auto *OF =
new (SCEVAllocator)
15108 UniquePreds.InsertNode(OF, IP);
15128 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15129 return Rewriter.visit(S);
15135 for (
const auto *Pred : U->getPredicates())
15137 if (IPred->getLHS() == Expr &&
15139 return IPred->getRHS();
15141 if (IPred->getLHS() == Expr &&
15142 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15143 return IPred->getRHS();
15146 return convertToAddRecWithPreds(Expr);
15149 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15165 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15182 explicit SCEVPredicateRewriter(
15183 const Loop *L, ScalarEvolution &SE,
15184 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15185 const SCEVPredicate *Pred)
15186 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15188 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15191 return Pred && Pred->
implies(
P, SE);
15197 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15200 return addOverflowAssumption(
A);
15209 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15213 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15215 if (!PredicatedRewrite)
15217 for (
const auto *
P : PredicatedRewrite->second){
15220 if (L != WP->getExpr()->getLoop())
15223 if (!addOverflowAssumption(
P))
15226 return PredicatedRewrite->first;
15229 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15230 const SCEVPredicate *Pred;
15239 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15246 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15266 if (!Step->
isOne())
15291 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15292 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15305 return Op->LHS == LHS &&
Op->RHS == RHS;
15312 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15314 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15339 const SCEV *Start = AR->getStart();
15340 const SCEV *OpStart =
Op->AR->getStart();
15345 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15354 const SCEV *Step = AR->getStepRecurrence(SE);
15355 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15408 if (Step->getValue()->getValue().isNonNegative())
15412 return ImpliedFlags;
15419 for (
const auto *
P : Preds)
15432 return this->implies(I, SE);
15440 for (
const auto *Pred : Preds)
15441 Pred->print(OS,
Depth);
15446 for (
const auto *Pred : Set->Preds)
15454 bool CheckImplies = Preds.
size() < 16;
15457 if (CheckImplies &&
implies(
N, SE))
15463 for (
auto *
P : Preds) {
15464 if (CheckImplies &&
N->implies(
P, SE))
15468 Preds = std::move(PrunedPreds);
15469 Preds.push_back(
N);
15476 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15481 for (
const auto *
Op :
Ops)
15486 SCEVUsers[
Op].insert(
User);
15495 SCEVUsers[
Op].insert(
User);
15499 const SCEV *Expr = SE.getSCEV(V);
15504 RewriteEntry &Entry = RewriteMap[Expr];
15507 if (Entry.second && Generation == Entry.first)
15508 return Entry.second;
15513 Expr = Entry.second;
15515 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15516 Entry = {Generation, NewSCEV};
15522 if (!BackedgeCount) {
15524 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15525 for (
const auto *
P : Preds)
15528 return BackedgeCount;
15532 if (!SymbolicMaxBackedgeCount) {
15534 SymbolicMaxBackedgeCount =
15535 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15536 for (
const auto *
P : Preds)
15539 return SymbolicMaxBackedgeCount;
15543 if (!SmallConstantMaxTripCount) {
15545 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15546 for (
const auto *
P : Preds)
15549 return *SmallConstantMaxTripCount;
15553 if (Preds->implies(&Pred, SE))
15558 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15559 updateGeneration();
15566void PredicatedScalarEvolution::updateGeneration() {
15568 if (++Generation == 0) {
15569 for (
auto &
II : RewriteMap) {
15570 const SCEV *Rewritten =
II.second.second;
15587 auto II = FlagsMap.insert({V, Flags});
15600 auto II = FlagsMap.find(V);
15602 if (
II != FlagsMap.end())
15611 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15616 for (
const auto *
P : NewPreds)
15619 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15625 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15628 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {
15629 for (
auto I :
Init.FlagsMap)
15630 FlagsMap.insert(
I);
15635 for (
auto *BB : L.getBlocks())
15636 for (
auto &
I : *BB) {
15637 if (!SE.isSCEVable(
I.getType()))
15640 auto *Expr = SE.getSCEV(&
I);
15641 auto II = RewriteMap.find(Expr);
15643 if (
II == RewriteMap.end())
15647 if (
II->second.second == Expr)
15652 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15660 LoopGuards Guards(SE);
15668void ScalarEvolution::LoopGuards::collectFromPHI(
15676 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15677 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15691 auto &RewriteMap =
G->second.RewriteMap;
15692 if (RewriteMap.empty())
15694 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15695 if (S == RewriteMap.end())
15701 return {C0,
SM->getSCEVType()};
15704 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15705 MinMaxPattern
P2) -> MinMaxPattern {
15706 auto [C1,
T1] =
P1;
15707 auto [C2, T2] =
P2;
15708 if (!C1 || !C2 ||
T1 != T2)
15712 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15714 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15716 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15718 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15723 auto P = GetMinMaxConst(0);
15724 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15727 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15730 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15733 Guards.RewriteMap.insert({
LHS,
RHS});
15741 const APInt &DivisorVal,
15743 const APInt *ExprVal;
15756 const APInt &DivisorVal,
15758 const APInt *ExprVal;
15766 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15780 const SCEV *URemRHS =
nullptr;
15784 const SCEV *Multiple =
15786 DivInfo[URemLHS] = Multiple;
15788 Multiples[URemLHS] =
C->getAPInt();
15808 auto IsMinMaxSCEVWithNonNegativeConstant =
15812 if (
MinMax->getNumOperands() != 2)
15815 if (
C->getAPInt().isNegative())
15817 SCTy =
MinMax->getSCEVType();
15826 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15828 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15833 auto *DivisibleExpr =
15841void ScalarEvolution::LoopGuards::collectFromBlock(
15843 const BasicBlock *
Block,
const BasicBlock *Pred,
15851 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15862 &ExprsToRewrite]() {
15863 const SCEVConstant *C1;
15876 if (ExactRegion.isWrappedSet() || ExactRegion.isFullSet())
15878 auto [
I,
Inserted] = RewriteMap.try_emplace(LHSUnknown);
15879 const SCEV *RewrittenLHS =
Inserted ? LHSUnknown :
I->second;
15887 if (MatchRangeCheckIdiom())
15904 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15906 if (From == FromRewritten)
15908 RewriteMap[From] = To;
15914 auto GetMaybeRewritten = [&](
const SCEV *S) {
15915 return RewriteMap.lookup_or(S, S);
15918 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15920 const APInt &DividesBy =
15935 switch (Predicate) {
15964 SmallPtrSet<const SCEV *, 16> Visited;
15966 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
15970 while (!Worklist.
empty()) {
15974 if (!Visited.
insert(From).second)
15976 const SCEV *FromRewritten = GetMaybeRewritten(From);
15977 const SCEV *To =
nullptr;
15979 switch (Predicate) {
15984 EnqueueOperands(
UMax);
15990 EnqueueOperands(
SMax);
15996 EnqueueOperands(
UMin);
16002 EnqueueOperands(
SMin);
16010 const SCEV *OneAlignedUp =
16012 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16024 const SCEVConstant *
C;
16033 Guards.NotEqual.insert({
LHS,
RHS});
16042 AddRewrite(From, FromRewritten, To);
16059 SE.F.
getParent(), Intrinsic::experimental_guard);
16061 for (
const auto *GU : GuardDecl->users())
16063 if (Guard->getFunction() ==
Block->getParent() &&
16072 unsigned NumCollectedConditions = 0;
16074 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16076 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16078 const CondBrInst *LoopEntryPredicate =
16080 if (!LoopEntryPredicate)
16085 NumCollectedConditions++;
16089 if (
Depth > 0 && NumCollectedConditions == 2)
16097 if (Pair.second->hasNPredecessorsOrMore(2) &&
16099 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16100 for (
auto &Phi : Pair.second->phis())
16111 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16112 SmallVector<Value *, 8> Worklist;
16113 SmallPtrSet<Value *, 8> Visited;
16115 while (!Worklist.
empty()) {
16122 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16146 DenseMap<const SCEV *, APInt> Multiples;
16148 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16155 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16156 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16160 for (
const auto &[K, Divisor] : Multiples) {
16161 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16162 Guards.RewriteMap[
K] =
16164 Guards.
rewrite(K), Divisor, SE),
16173 Guards.PreserveNUW =
true;
16174 Guards.PreserveNSW =
true;
16175 for (
const SCEV *Expr : ExprsToRewrite) {
16176 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16177 Guards.PreserveNUW &=
16179 Guards.PreserveNSW &=
16186 if (ExprsToRewrite.size() > 1) {
16187 for (
const SCEV *Expr : ExprsToRewrite) {
16188 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16189 Guards.RewriteMap.erase(Expr);
16190 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16199 class SCEVLoopGuardRewriter
16210 NotEqual(Guards.NotEqual) {
16211 if (Guards.PreserveNUW)
16213 if (Guards.PreserveNSW)
16220 return Map.lookup_or(Expr, Expr);
16224 if (
const SCEV *S = Map.lookup(Expr))
16231 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16232 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16233 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16235 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16236 if (
const SCEV *S = Map.lookup(NarrowExt))
16237 return SE.getZeroExtendExpr(S, Ty);
16238 Bitwidth = Bitwidth / 2;
16246 if (
const SCEV *S = Map.lookup(Expr))
16253 if (
const SCEV *S = Map.lookup(Expr))
16259 if (
const SCEV *S = Map.lookup(Expr))
16267 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16272 if (NotEqual.contains({LHS, RHS})) {
16274 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16275 return SE.getUMaxExpr(OneAlignedUp, S);
16282 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16293 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16294 return SE.getAddExpr(
16297 if (
const SCEV *S = Map.lookup(
Add))
16298 return SE.getAddExpr(Expr->
getOperand(0), S);
16310 : SE.getAddExpr(Operands,
16326 : SE.getMulExpr(Operands,
16332 if (RewriteMap.empty() && NotEqual.empty())
16335 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16336 return Rewriter.visit(Expr);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Expand Atomic instructions
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
static bool isSigned(unsigned Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
Value * getPointer(Value *Ptr)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This defines the Use class.
iv Induction Variable Users
static constexpr Value * getValue(Ty &ValueOrUse)
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
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