83#include "llvm/Config/llvm-config.h"
138#define DEBUG_TYPE "scalar-evolution"
141 "Number of loop exits with predictable exit counts");
143 "Number of loop exits without predictable exit counts");
145 "Number of loops with trip counts computed by force");
147#ifdef EXPENSIVE_CHECKS
155 cl::desc(
"Maximum number of iterations SCEV will "
156 "symbolically execute a constant "
162 cl::desc(
"Verify ScalarEvolution's backedge taken counts (slow)"));
165 cl::desc(
"Enable stricter verification with -verify-scev is passed"));
169 cl::desc(
"Verify IR correctness when making sensitive SCEV queries (slow)"),
174 cl::desc(
"Threshold for inlining multiplication operands into a SCEV"),
179 cl::desc(
"Threshold for inlining addition operands into a SCEV"),
183 "scalar-evolution-max-scev-compare-depth",
cl::Hidden,
184 cl::desc(
"Maximum depth of recursive SCEV complexity comparisons"),
188 "scalar-evolution-max-scev-operations-implication-depth",
cl::Hidden,
189 cl::desc(
"Maximum depth of recursive SCEV operations implication analysis"),
193 "scalar-evolution-max-value-compare-depth",
cl::Hidden,
194 cl::desc(
"Maximum depth of recursive value complexity comparisons"),
199 cl::desc(
"Maximum depth of recursive arithmetics"),
203 "scalar-evolution-max-constant-evolving-depth",
cl::Hidden,
208 cl::desc(
"Maximum depth of recursive SExt/ZExt/Trunc"),
213 cl::desc(
"Max coefficients in AddRec during evolving"),
218 cl::desc(
"Size of the expression which is considered huge"),
223 cl::desc(
"Threshold for switching to iteratively computing SCEV ranges"),
227 "scalar-evolution-max-loop-guard-collection-depth",
cl::Hidden,
228 cl::desc(
"Maximum depth for recursive loop guard collection"),
cl::init(1));
233 cl::desc(
"When printing analysis, include information on every instruction"));
236 "scalar-evolution-use-expensive-range-sharpening",
cl::Hidden,
238 cl::desc(
"Use more powerful methods of sharpening expression ranges. May "
239 "be costly in terms of compile time"));
242 "scalar-evolution-max-scc-analysis-depth",
cl::Hidden,
243 cl::desc(
"Maximum amount of nodes to process while searching SCEVUnknown "
244 "Phi strongly connected components"),
249 cl::desc(
"Handle <= and >= in finite loops"),
253 "scalar-evolution-use-context-for-no-wrap-flag-strenghening",
cl::Hidden,
254 cl::desc(
"Infer nuw/nsw flags using context where suitable"),
343#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
363 OS <<
"(ptrto" << OpS <<
" " << *
Op->getType() <<
" " << *
Op <<
" to "
370 OS <<
"(trunc " << *
Op->getType() <<
" " << *
Op <<
" to "
377 OS <<
"(zext " << *
Op->getType() <<
" " << *
Op <<
" to "
384 OS <<
"(sext " << *
Op->getType() <<
" " << *
Op <<
" to "
413 const char *OpStr =
nullptr;
426 OpStr =
" umin_seq ";
450 OS <<
"(" << *UDiv->
getLHS() <<
" /u " << *UDiv->
getRHS() <<
")";
457 OS <<
"***COULDNOTCOMPUTE***";
535 if (!
Mul)
return false;
539 if (!SC)
return false;
557 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
559 UniqueSCEVs.InsertNode(S, IP);
574 ConstantInt::get(ITy, V,
isSigned,
true));
582 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
585 UniqueSCEVs.InsertNode(S, IP);
606 "Must be a non-bit-width-changing pointer-to-integer cast!");
613 "Must be a non-bit-width-changing pointer-to-integer cast!");
625 "Cannot truncate non-integer value!");
632 "Cannot zero extend non-integer value!");
639 "Cannot sign extend non-integer value!");
644 SE->forgetMemoizedResults({
this});
647 SE->UniqueSCEVs.RemoveNode(
this);
653void SCEVUnknown::allUsesReplacedWith(
Value *New) {
655 SE->forgetMemoizedResults({
this});
658 SE->UniqueSCEVs.RemoveNode(
this);
680 if (LIsPointer != RIsPointer)
681 return (
int)LIsPointer - (int)RIsPointer;
686 return (
int)LID - (int)RID;
691 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
692 return (
int)LArgNo - (int)RArgNo;
698 if (
auto L = LGV->getLinkage() - RGV->getLinkage())
701 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
702 auto LT = GV->getLinkage();
709 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
710 return LGV->getName().compare(RGV->getName());
721 if (LParent != RParent) {
724 if (LDepth != RDepth)
725 return (
int)LDepth - (int)RDepth;
729 unsigned LNumOps = LInst->getNumOperands(),
730 RNumOps = RInst->getNumOperands();
731 if (LNumOps != RNumOps)
732 return (
int)LNumOps - (int)RNumOps;
734 for (
unsigned Idx :
seq(LNumOps)) {
736 RInst->getOperand(Idx),
Depth + 1);
750static std::optional<int>
760 return (
int)LType - (int)RType;
785 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
786 if (LBitWidth != RBitWidth)
787 return (
int)LBitWidth - (int)RBitWidth;
788 return LA.
ult(
RA) ? -1 : 1;
794 return LTy->getBitWidth() - RTy->getBitWidth();
805 if (LLoop != RLoop) {
807 assert(LHead != RHead &&
"Two loops share the same header?");
811 "No dominance between recurrences used by one SCEV?");
835 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
836 if (LNumOps != RNumOps)
837 return (
int)LNumOps - (int)RNumOps;
839 for (
unsigned i = 0; i != LNumOps; ++i) {
865 if (
Ops.size() < 2)
return;
870 return Complexity && *Complexity < 0;
872 if (
Ops.size() == 2) {
876 if (IsLessComplex(
RHS,
LHS))
889 for (
unsigned i = 0, e =
Ops.size(); i != e-2; ++i) {
895 for (
unsigned j = i+1; j != e &&
Ops[j]->getSCEVType() == Complexity; ++j) {
900 if (i == e-2)
return;
922template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
926 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
928 for (
unsigned Idx = 0; Idx <
Ops.size();) {
936 Ops.erase(
Ops.begin() + Idx);
943 assert(Folded &&
"Must have folded value");
947 if (Folded && IsAbsorber(Folded->
getAPInt()))
951 if (Folded && !IsIdentity(Folded->
getAPInt()))
952 Ops.insert(
Ops.begin(), Folded);
954 return Ops.size() == 1 ?
Ops[0] :
nullptr;
1029 APInt OddFactorial(W, 1);
1031 for (
unsigned i = 3; i <= K; ++i) {
1034 OddFactorial *= (i >> TwoFactors);
1038 unsigned CalculationBits = W +
T;
1052 for (
unsigned i = 1; i != K; ++i) {
1085 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1114 ConversionFn CreatePtrCast;
1118 ConversionFn CreatePtrCast)
1119 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
1122 Type *TargetTy, ConversionFn CreatePtrCast) {
1124 return Rewriter.visit(Scev);
1160 "Should only reach pointer-typed SCEVUnknown's.");
1165 return SE.getZero(TargetTy);
1166 return CreatePtrCast(Expr);
1171 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1195 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1197 SCEV *S =
new (SCEVAllocator)
1199 UniqueSCEVs.InsertNode(S, IP);
1202 return static_cast<const SCEV *
>(S);
1205 "We must have succeeded in sinking the cast, "
1206 "and ending up with an integer-typed expression!");
1211 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1215 if (DL.hasUnstableRepresentation(
Op->getType()))
1218 Type *Ty = DL.getAddressType(
Op->getType());
1229 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1231 SCEV *S =
new (SCEVAllocator)
1233 UniqueSCEVs.InsertNode(S, IP);
1236 return static_cast<const SCEV *
>(S);
1239 "We must have succeeded in sinking the cast, "
1240 "and ending up with an integer-typed expression!");
1245 assert(Ty->isIntegerTy() &&
"Target type must be an integer type!");
1257 "This is not a truncating conversion!");
1259 "This is not a conversion to a SCEVable type!");
1260 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1268 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1290 UniqueSCEVs.InsertNode(S, IP);
1303 unsigned numTruncs = 0;
1304 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1312 if (numTruncs < 2) {
1322 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1329 for (
const SCEV *
Op : AddRec->operands())
1344 UniqueSCEVs.InsertNode(S, IP);
1385struct ExtendOpTraitsBase {
1386 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
const SCEV *,
Type *,
1391template <
typename ExtendOp>
struct ExtendOpTraits {
1407 static const GetExtendExprTy GetExtendExpr;
1409 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1410 ICmpInst::Predicate *Pred,
1411 ScalarEvolution *SE) {
1416const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1423 static const GetExtendExprTy GetExtendExpr;
1425 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1426 ICmpInst::Predicate *Pred,
1427 ScalarEvolution *SE) {
1432const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1444template <
typename ExtendOpTy>
1447 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1448 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1464 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1477 auto PreStartFlags =
1495 const SCEV *OperandExtendedStart =
1497 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1498 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1510 const SCEV *OverflowLimit =
1511 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1513 if (OverflowLimit &&
1521template <
typename ExtendOpTy>
1525 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1533 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1568template <
typename ExtendOpTy>
1569bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1572 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1582 APInt StartAI = StartC->
getAPInt();
1584 for (
unsigned Delta : {-2, -1, 1, 2}) {
1585 const SCEV *PreStart =
getConstant(StartAI - Delta);
1587 FoldingSetNodeID
ID;
1589 ID.AddPointer(PreStart);
1590 ID.AddPointer(Step);
1594 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
1598 if (PreAR &&
any(PreAR->getNoWrapFlags(WrapType))) {
1601 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1602 DeltaS, &Pred,
this);
1620 const unsigned BitWidth =
C.getBitWidth();
1638 const APInt &ConstantStart,
1657 auto &UserIDs = FoldCacheUser[
I.first->second];
1658 assert(
count(UserIDs,
ID) == 1 &&
"unexpected duplicates in UserIDs");
1659 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1660 if (UserIDs[
I] ==
ID) {
1665 I.first->second = S;
1667 FoldCacheUser[S].push_back(
ID);
1673 "This is not an extending conversion!");
1675 "This is not a conversion to a SCEVable type!");
1676 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1680 if (
const SCEV *S = FoldCache.lookup(
ID))
1692 "This is not an extending conversion!");
1694 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1708 if (AR->isAffine() && AR->hasNoUnsignedWrap()) {
1713 return getAddRecExpr(Start, Step, AR->getLoop(), AR->getNoWrapFlags());
1723 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1727 UniqueSCEVs.InsertNode(S, IP);
1737 const SCEV *
X = ST->getOperand();
1751 if (AR->isAffine()) {
1752 const SCEV *Start = AR->getStart();
1753 const SCEV *Step = AR->getStepRecurrence(*
this);
1755 const Loop *L = AR->getLoop();
1773 const SCEV *CastedMaxBECount =
1777 if (MaxBECount == RecastedMaxBECount) {
1787 const SCEV *WideMaxBECount =
1789 const SCEV *OperandExtendedAdd =
1795 if (ZAdd == OperandExtendedAdd) {
1806 OperandExtendedAdd =
1812 if (ZAdd == OperandExtendedAdd) {
1833 !AC.assumptions().empty()) {
1835 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1837 if (AR->hasNoUnsignedWrap()) {
1872 const APInt &
C = SC->getAPInt();
1876 const SCEV *SResidual =
1884 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1909 if (SA->hasNoUnsignedWrap()) {
1922 if (SA->hasNoSignedWrap() &&
1925 C->isNegative() && !
C->isMinSignedValue() && C2->
sge(
C->abs())) {
1944 const SCEV *SResidual =
1955 if (
SM->hasNoUnsignedWrap()) {
1977 const SCEV *TruncRHS;
2014 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
2017 UniqueSCEVs.InsertNode(S, IP);
2026 "This is not an extending conversion!");
2028 "This is not a conversion to a SCEVable type!");
2029 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
2033 if (
const SCEV *S = FoldCache.lookup(
ID))
2045 "This is not an extending conversion!");
2047 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
2066 if (AR->isAffine() && AR->hasNoSignedWrap()) {
2081 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
2086 UniqueSCEVs.InsertNode(S, IP);
2096 const SCEV *
X = ST->getOperand();
2107 if (SA->hasNoSignedWrap()) {
2129 const SCEV *SResidual =
2142 if (AR->isAffine()) {
2143 const SCEV *Start = AR->getStart();
2144 const SCEV *Step = AR->getStepRecurrence(*
this);
2146 const Loop *L = AR->getLoop();
2165 const SCEV *CastedMaxBECount =
2169 if (MaxBECount == RecastedMaxBECount) {
2179 const SCEV *WideMaxBECount =
2181 const SCEV *OperandExtendedAdd =
2187 if (SAdd == OperandExtendedAdd) {
2198 OperandExtendedAdd =
2204 if (SAdd == OperandExtendedAdd) {
2224 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2226 if (AR->hasNoSignedWrap()) {
2241 const APInt &
C = SC->getAPInt();
2245 const SCEV *SResidual =
2253 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2281 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
2284 UniqueSCEVs.InsertNode(S, IP);
2311 "This is not an extending conversion!");
2313 "This is not a conversion to a SCEVable type!");
2318 if (SC->getAPInt().isNegative())
2323 const SCEV *NewOp =
T->getOperand();
2342 for (
const SCEV *
Op : AR->operands())
2380 APInt &AccumulatedConstant,
2384 bool Interesting =
false;
2391 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2393 AccumulatedConstant += Scale *
C->getAPInt();
2398 for (; i !=
Ops.size(); ++i) {
2407 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2413 auto Pair = M.insert({
Key, NewScale});
2417 Pair.first->second += NewScale;
2425 auto Pair = M.insert({
Ops[i], Scale});
2429 Pair.first->second += Scale;
2448 case Instruction::Add:
2451 case Instruction::Sub:
2454 case Instruction::Mul:
2468 const SCEV *
A = (this->*Extension)(
2470 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2471 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2479 if (BinOp == Instruction::Mul)
2485 APInt C = RHSC->getAPInt();
2486 unsigned NumBits =
C.getBitWidth();
2487 bool IsSub = (BinOp == Instruction::Sub);
2488 bool IsNegativeConst = (
Signed &&
C.isNegative());
2490 bool OverflowDown = IsSub ^ IsNegativeConst;
2492 if (IsNegativeConst) {
2505 APInt Limit = Min + Magnitude;
2511 APInt Limit = Max - Magnitude;
2516std::optional<SCEV::NoWrapFlags>
2521 return std::nullopt;
2530 bool Deduced =
false;
2536 bool CanUseNSW =
true;
2537 const APInt *ShiftAmt;
2542 return std::nullopt;
2546 Opcode = Instruction::Mul;
2548 }
else if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
2549 Opcode != Instruction::Mul) {
2550 return std::nullopt;
2569 return std::nullopt;
2579 using namespace std::placeholders;
2586 assert(CanAnalyze &&
"don't call from other places!");
2593 auto IsKnownNonNegative = [&](
SCEVUse U) {
2602 if (SignOrUnsignWrap != SignOrUnsignMask &&
2609 return Instruction::Add;
2611 return Instruction::Mul;
2622 Opcode,
C, OBO::NoSignedWrap);
2630 Opcode,
C, OBO::NoUnsignedWrap);
2640 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2647 if (UDiv->getOperand(1) ==
Ops[1])
2650 if (UDiv->getOperand(1) ==
Ops[0])
2666 "only nuw or nsw allowed");
2667 assert(!
Ops.empty() &&
"Cannot get empty add!");
2668 if (
Ops.size() == 1)
return Ops[0];
2671 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2673 "SCEVAddExpr operand types don't match!");
2675 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2676 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2681 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2682 [](
const APInt &
C) {
return C.isZero(); },
2683 [](
const APInt &
C) {
return false; });
2696 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2701 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2702 Add->setNoWrapFlags(ComputeFlags(
Ops));
2710 bool FoundMatch =
false;
2711 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2712 if (
Ops[i] ==
Ops[i+1]) {
2724 --i; e -=
Count - 1;
2734 auto FindTruncSrcType = [&]() ->
Type * {
2740 return T->getOperand()->getType();
2742 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2744 return T->getOperand()->getType();
2748 if (
auto *SrcType = FindTruncSrcType()) {
2755 if (
T->getOperand()->getType() != SrcType) {
2764 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2767 if (
T->getOperand()->getType() != SrcType) {
2795 if (
Ops.size() == 2) {
2805 auto C2 =
C->getAPInt();
2808 APInt ConstAdd = C1 + C2;
2809 auto AddFlags = AddExpr->getNoWrapFlags();
2850 if (
Ops.size() == 2 &&
2861 if (Idx <
Ops.size()) {
2862 bool DeletedAdd =
false;
2873 Ops.erase(
Ops.begin()+Idx);
2876 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2899 struct APIntCompare {
2900 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2901 return LHS.ult(RHS);
2908 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2909 for (
const SCEV *NewOp : NewOps)
2910 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2913 if (AccumulatedConstant != 0)
2915 for (
auto &MulOp : MulOpLists) {
2916 if (MulOp.first == 1) {
2918 }
else if (MulOp.first != 0) {
2927 if (
Ops.size() == 1)
2936 if (M->getNumOperands() == 2)
2937 return M->getOperand(
OpIdx == 0);
2948 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2952 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2960 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp) {
2961 if (MulOpSCEV ==
Ops[AddOp]) {
2972 for (
unsigned OMulOp = 0, OE = OtherMul->
getNumOperands(); OMulOp != OE;
2974 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2976 Cofactors.
push_back(StripFactor(OtherMul, OMulOp));
2985 if (!Cofactors.
empty()) {
2993 if (
Ops.size() == DeadIndices.
size() + 1)
3000 Ops.erase(
Ops.begin() + Idx);
3004 Ops.push_back(OuterMul);
3023 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3026 Ops.erase(
Ops.begin()+i);
3031 if (!LIOps.
empty()) {
3056 auto *DefI = getDefiningScopeBound(LIOps);
3058 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
3070 if (
Ops.size() == 1)
return NewRec;
3073 for (
unsigned i = 0;; ++i)
3074 if (
Ops[i] == AddRec) {
3084 for (
unsigned OtherIdx = Idx+1;
3092 "AddRecExprs are not sorted in reverse dominance order?");
3099 if (OtherAddRec->getLoop() == AddRecLoop) {
3100 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
3102 if (i >= AddRecOps.
size()) {
3103 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
3107 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
3110 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3125 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
3136 static_cast<SCEVAddExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3140 S =
new (SCEVAllocator)
3142 UniqueSCEVs.InsertNode(S, IP);
3153 FoldingSetNodeID
ID;
3155 for (
const SCEV *
Op :
Ops)
3160 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3164 S =
new (SCEVAllocator)
3165 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3166 UniqueSCEVs.InsertNode(S, IP);
3168 LoopUsers[
L].push_back(S);
3177 FoldingSetNodeID
ID;
3179 for (
const SCEV *
Op :
Ops)
3183 static_cast<SCEVMulExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3187 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3189 UniqueSCEVs.InsertNode(S, IP);
3199 if (j > 1 && k / j != i) Overflow =
true;
3215 if (n == 0 || n == k)
return 1;
3216 if (k > n)
return 0;
3222 for (
uint64_t i = 1; i <= k; ++i) {
3223 r =
umul_ov(r, n-(i-1), Overflow);
3232 struct FindConstantInAddMulChain {
3233 bool FoundConstant =
false;
3235 bool follow(
const SCEV *S) {
3240 bool isDone()
const {
3241 return FoundConstant;
3245 FindConstantInAddMulChain
F;
3247 ST.visitAll(StartExpr);
3248 return F.FoundConstant;
3256 "only nuw or nsw allowed");
3257 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3258 if (
Ops.size() == 1)
return Ops[0];
3260 Type *ETy =
Ops[0]->getType();
3262 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3264 "SCEVMulExpr operand types don't match!");
3269 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3270 [](
const APInt &
C) {
return C.isOne(); },
3271 [](
const APInt &
C) {
return C.isZero(); });
3282 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3287 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3288 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3293 if (
Ops.size() == 2) {
3301 const SCEV *Op0, *Op1;
3309 if (
Ops[0]->isAllOnesValue()) {
3314 bool AnyFolded =
false;
3315 for (
const SCEV *AddOp :
Add->operands()) {
3335 if (AddRec->hasNoSignedWrap()) {
3342 AddRec->getNoWrapFlags(FlagsMask));
3365 APInt C1V = LHSC->getAPInt();
3375 const SCEV *NewMul =
nullptr;
3379 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3394 if (Idx <
Ops.size()) {
3395 bool DeletedMul =
false;
3401 Ops.erase(
Ops.begin()+Idx);
3425 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3428 Ops.erase(
Ops.begin()+i);
3433 if (!LIOps.
empty()) {
3446 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3462 if (
Ops.size() == 1)
return NewRec;
3465 for (
unsigned i = 0;; ++i)
3466 if (
Ops[i] == AddRec) {
3487 bool OpsModified =
false;
3488 for (
unsigned OtherIdx = Idx+1;
3502 bool Overflow =
false;
3509 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3513 z < ze && !Overflow; ++z) {
3516 if (LargerThan64Bits)
3517 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3519 Coeff = Coeff1*Coeff2;
3534 if (
Ops.size() == 2)
return NewAddRec;
3535 Ops[Idx] = NewAddRec;
3536 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3552 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3559 "SCEVURemExpr operand types don't match!");
3564 if (RHSC->getValue()->isOne())
3565 return getZero(LHS->getType());
3568 if (RHSC->getAPInt().isPowerOf2()) {
3569 Type *FullTy = LHS->getType();
3585 assert(!LHS->getType()->isPointerTy() &&
3586 "SCEVUDivExpr operand can't be pointer!");
3587 assert(LHS->getType() == RHS->getType() &&
3588 "SCEVUDivExpr operand types don't match!");
3595 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3603 if (RHSC->getValue()->isOne())
3608 if (!RHSC->getValue()->isZero()) {
3612 Type *Ty = LHS->getType();
3613 unsigned LZ = RHSC->getAPInt().countl_zero();
3617 if (!RHSC->getAPInt().isPowerOf2())
3625 const APInt &StepInt = Step->getAPInt();
3626 const APInt &DivInt = RHSC->getAPInt();
3627 if (!StepInt.
urem(DivInt) &&
3633 for (
const SCEV *
Op : AR->operands())
3639 const APInt *StartRem;
3652 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3656 const SCEV *NewStart =
3658 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3660 const SCEV *NewLHS =
3663 if (LHS != NewLHS) {
3673 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3682 for (
const SCEV *
Op : M->operands())
3686 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3687 const SCEV *
Op = M->getOperand(i);
3714 if (
auto *DivisorConstant =
3716 bool Overflow =
false;
3718 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3729 for (
const SCEV *
Op :
A->operands())
3733 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3740 if (Operands.
size() ==
A->getNumOperands())
3752 const APInt &
N = RHSC->getAPInt();
3753 const APInt *NMinusM, *M;
3757 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3758 *NMinusM ==
N - *M) {
3767 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3777 return getZero(LHS->getType());
3781 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3782 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3783 if (
Mul->getOperand(i) == RHS) {
3794 const SCEV *NewLHS, *NewRHS;
3802 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
3805 UniqueSCEVs.InsertNode(S, IP);
3842 if (StepChrec->getLoop() == L) {
3856 if (Operands.
size() == 1)
return Operands[0];
3861 "SCEVAddRecExpr operand types don't match!");
3862 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3864 for (
const SCEV *
Op : Operands)
3866 "SCEVAddRecExpr operand is not available at loop entry!");
3869 if (Operands.
back()->isZero()) {
3884 const Loop *NestedLoop = NestedAR->getLoop();
3885 if (L->contains(NestedLoop)
3888 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3890 Operands[0] = NestedAR->getStart();
3894 bool AllInvariant =
all_of(
3906 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3917 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3921 Operands[0] = NestedAR;
3927 return getOrCreateAddRecExpr(Operands, L, Flags);
3943 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3947 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3961 bool FirstIter =
true;
3963 for (
SCEVUse IndexExpr : IndexExprs) {
3970 Offsets.push_back(FieldOffset);
3973 CurTy = STy->getTypeAtIndex(Index);
3978 "The first index of a GEP indexes a pointer");
3979 CurTy = SrcElementTy;
3990 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3991 Offsets.push_back(LocalOffset);
3996 if (Offsets.empty())
4009 "GEP should not change type mid-flight.");
4013SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
4016 ID.AddInteger(SCEVType);
4020 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4023SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
4026 ID.AddInteger(SCEVType);
4030 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4040 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
4041 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4042 if (
Ops.size() == 1)
return Ops[0];
4045 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4047 "Operand types don't match!");
4050 "min/max should be consistently pointerish");
4076 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
4078 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
4083 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
4085 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
4091 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
4097 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
4102 if (Idx <
Ops.size()) {
4103 bool DeletedAny =
false;
4104 while (
Ops[Idx]->getSCEVType() == Kind) {
4106 Ops.erase(
Ops.begin()+Idx);
4124 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
4125 if (
Ops[i] ==
Ops[i + 1] ||
4126 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
4129 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
4132 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
4135 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
4141 if (
Ops.size() == 1)
return Ops[0];
4143 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
4148 ID.AddInteger(Kind);
4152 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4154 return ExistingSCEV;
4157 SCEV *S =
new (SCEVAllocator)
4160 UniqueSCEVs.InsertNode(S, IP);
4168class SCEVSequentialMinMaxDeduplicatingVisitor final
4169 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4170 std::optional<const SCEV *>> {
4171 using RetVal = std::optional<const SCEV *>;
4179 bool canRecurseInto(
SCEVTypes Kind)
const {
4182 return RootKind == Kind || NonSequentialRootKind == Kind;
4185 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
4187 "Only for min/max expressions.");
4190 if (!canRecurseInto(Kind))
4200 return std::nullopt;
4207 RetVal
visit(
const SCEV *S) {
4209 if (!SeenOps.
insert(S).second)
4210 return std::nullopt;
4211 return Base::visit(S);
4215 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4217 : SE(SE), RootKind(RootKind),
4218 NonSequentialRootKind(
4219 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4223 SmallVectorImpl<SCEVUse> &NewOps) {
4228 for (
const SCEV *
Op : OrigOps) {
4233 Ops.emplace_back(*NewOp);
4237 NewOps = std::move(
Ops);
4241 RetVal visitConstant(
const SCEVConstant *Constant) {
return Constant; }
4243 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4245 RetVal visitPtrToAddrExpr(
const SCEVPtrToAddrExpr *Expr) {
return Expr; }
4247 RetVal visitPtrToIntExpr(
const SCEVPtrToIntExpr *Expr) {
return Expr; }
4249 RetVal visitTruncateExpr(
const SCEVTruncateExpr *Expr) {
return Expr; }
4251 RetVal visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
return Expr; }
4253 RetVal visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
return Expr; }
4255 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4257 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4259 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4261 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4263 RetVal visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
4264 return visitAnyMinMaxExpr(Expr);
4267 RetVal visitUMaxExpr(
const SCEVUMaxExpr *Expr) {
4268 return visitAnyMinMaxExpr(Expr);
4271 RetVal visitSMinExpr(
const SCEVSMinExpr *Expr) {
4272 return visitAnyMinMaxExpr(Expr);
4275 RetVal visitUMinExpr(
const SCEVUMinExpr *Expr) {
4276 return visitAnyMinMaxExpr(Expr);
4279 RetVal visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *Expr) {
4280 return visitAnyMinMaxExpr(Expr);
4283 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4285 RetVal visitCouldNotCompute(
const SCEVCouldNotCompute *Expr) {
return Expr; }
4328struct SCEVPoisonCollector {
4329 bool LookThroughMaybePoisonBlocking;
4330 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4331 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4332 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4334 bool follow(
const SCEV *S) {
4335 if (!LookThroughMaybePoisonBlocking &&
4345 bool isDone()
const {
return false; }
4355 SCEVPoisonCollector PC1(
true);
4360 if (PC1.MaybePoison.empty())
4366 SCEVPoisonCollector PC2(
false);
4376 SCEVPoisonCollector PC(
false);
4399 while (!Worklist.
empty()) {
4401 if (!Visited.
insert(V).second)
4405 if (Visited.
size() > 16)
4421 if (PDI->isDisjoint())
4428 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4435 if (
I->hasPoisonGeneratingAnnotations())
4446 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4447 "Not a SCEVSequentialMinMaxExpr!");
4448 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4449 if (
Ops.size() == 1)
4453 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4455 "Operand types don't match!");
4458 "min/max should be consistently pointerish");
4466 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4473 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4483 bool DeletedAny =
false;
4484 while (Idx <
Ops.size()) {
4485 if (
Ops[Idx]->getSCEVType() != Kind) {
4490 Ops.erase(
Ops.begin() + Idx);
4491 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4492 SMME->operands().end());
4500 const SCEV *SaturationPoint;
4511 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4512 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4524 Ops.erase(
Ops.begin() + i);
4529 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4530 Ops.erase(
Ops.begin() + i);
4538 ID.AddInteger(Kind);
4542 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4544 return ExistingSCEV;
4548 SCEV *S =
new (SCEVAllocator)
4551 UniqueSCEVs.InsertNode(S, IP);
4599 if (
Size.isScalable())
4620 "Cannot get offset for structure containing scalable vector types");
4634 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP)) {
4636 "Stale SCEVUnknown in uniquing map!");
4642 UniqueSCEVs.InsertNode(S, IP);
4657 return Ty->isIntOrPtrTy();
4664 if (Ty->isPointerTy())
4675 if (Ty->isIntegerTy())
4679 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4691 bool PreciseA, PreciseB;
4692 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4693 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4694 if (!PreciseA || !PreciseB)
4697 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4698 DT.dominates(ScopeB, ScopeA);
4702 return CouldNotCompute.get();
4705bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4708 return SU && SU->getValue() ==
nullptr;
4711 return !ContainsNulls;
4716 if (
I != HasRecMap.end())
4721 HasRecMap.insert({S, FoundAddRec});
4729 if (
SI == ExprValueMap.
end())
4731 return SI->second.getArrayRef();
4737void ScalarEvolution::eraseValueFromMap(
Value *V) {
4739 if (
I != ValueExprMap.end()) {
4740 auto EVIt = ExprValueMap.find(
I->second);
4741 bool Removed = EVIt->second.remove(V);
4743 assert(Removed &&
"Value not in ExprValueMap?");
4744 ValueExprMap.erase(
I);
4748void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4752 auto It = ValueExprMap.find_as(V);
4753 if (It == ValueExprMap.end()) {
4755 ExprValueMap[S].insert(V);
4766 return createSCEVIter(V);
4773 if (
I != ValueExprMap.end()) {
4774 const SCEV *S =
I->second;
4775 assert(checkValidity(S) &&
4776 "existing SCEV has not been properly invalidated");
4789 Type *Ty = V->getType();
4805 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4818 return (
const SCEV *)
nullptr;
4824 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4828 Type *Ty = V->getType();
4834 assert(
P->getType()->isPointerTy());
4849 if (AddOp->getType()->isPointerTy()) {
4850 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4868 return getZero(LHS->getType());
4873 if (RHS->getType()->isPointerTy()) {
4874 if (!LHS->getType()->isPointerTy() ||
4884 const bool RHSIsNotMinSigned =
4915 Type *SrcTy = V->getType();
4916 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4917 "Cannot truncate or zero extend with non-integer arguments!");
4927 Type *SrcTy = V->getType();
4928 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4929 "Cannot truncate or zero extend with non-integer arguments!");
4939 Type *SrcTy = V->getType();
4940 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4941 "Cannot noop or zero extend with non-integer arguments!");
4943 "getNoopOrZeroExtend cannot truncate!");
4951 Type *SrcTy = V->getType();
4952 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4953 "Cannot noop or sign extend with non-integer arguments!");
4955 "getNoopOrSignExtend cannot truncate!");
4963 Type *SrcTy = V->getType();
4964 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4965 "Cannot noop or any extend with non-integer arguments!");
4967 "getNoopOrAnyExtend cannot truncate!");
4975 Type *SrcTy = V->getType();
4976 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4977 "Cannot truncate or noop with non-integer arguments!");
4979 "getTruncateOrNoop cannot extend!");
4987 const SCEV *PromotedLHS = LHS;
4988 const SCEV *PromotedRHS = RHS;
5008 assert(!
Ops.empty() &&
"At least one operand must be!");
5010 if (
Ops.size() == 1)
5014 Type *MaxType =
nullptr;
5020 assert(MaxType &&
"Failed to find maximum type!");
5033 if (!V->getType()->isPointerTy())
5038 V = AddRec->getStart();
5040 const SCEV *PtrOp =
nullptr;
5041 for (
const SCEV *AddOp :
Add->operands()) {
5042 if (AddOp->getType()->isPointerTy()) {
5043 assert(!PtrOp &&
"Cannot have multiple pointer ops");
5047 assert(PtrOp &&
"Must have pointer op");
5059 for (
User *U :
I->users()) {
5061 if (Visited.
insert(UserInsn).second)
5075 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
5076 bool IgnoreOtherLoops =
true) {
5079 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
5081 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
5086 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5088 SeenLoopVariantSCEVUnknown =
true;
5092 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5096 SeenOtherLoops =
true;
5100 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
5102 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
5105 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
5106 : SCEVRewriteVisitor(SE),
L(
L) {}
5109 bool SeenLoopVariantSCEVUnknown =
false;
5110 bool SeenOtherLoops =
false;
5119 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
5120 SCEVPostIncRewriter
Rewriter(L, SE);
5122 return Rewriter.hasSeenLoopVariantSCEVUnknown()
5127 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5129 SeenLoopVariantSCEVUnknown =
true;
5133 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5137 SeenOtherLoops =
true;
5141 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
5143 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
5146 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
5147 : SCEVRewriteVisitor(SE),
L(
L) {}
5150 bool SeenLoopVariantSCEVUnknown =
false;
5151 bool SeenOtherLoops =
false;
5157class SCEVBackedgeConditionFolder
5160 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5161 ScalarEvolution &SE) {
5162 bool IsPosBECond =
false;
5163 Value *BECond =
nullptr;
5164 if (BasicBlock *Latch =
L->getLoopLatch()) {
5166 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
5167 "Both outgoing branches should not target same header!");
5168 BECond = BI->getCondition();
5169 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
5174 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
5178 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5179 const SCEV *
Result = Expr;
5184 switch (
I->getOpcode()) {
5185 case Instruction::Select: {
5187 std::optional<const SCEV *> Res =
5188 compareWithBackedgeCondition(
SI->getCondition());
5196 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5207 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5208 bool IsPosBECond, ScalarEvolution &SE)
5209 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5210 IsPositiveBECond(IsPosBECond) {}
5212 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5216 Value *BackedgeCond =
nullptr;
5218 bool IsPositiveBECond;
5221std::optional<const SCEV *>
5222SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5227 if (BackedgeCond == IC)
5230 return std::nullopt;
5235 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5236 ScalarEvolution &SE) {
5242 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5249 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5259 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5260 : SCEVRewriteVisitor(SE),
L(
L) {}
5268void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5284 const APInt &BECountAP = BECountMax->getAPInt();
5285 unsigned NoOverflowBitWidth =
5294ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5304 if (!SignedWrapViaInductionTried.insert(AR).second)
5329 AC.assumptions().empty())
5337 const SCEV *OverflowLimit =
5339 if (OverflowLimit &&
5347ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5357 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5383 AC.assumptions().empty())
5422 IsNSW = OBO->hasNoSignedWrap();
5423 IsNUW = OBO->hasNoUnsignedWrap();
5429 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5441 return std::nullopt;
5447 switch (
Op->getOpcode()) {
5448 case Instruction::Add:
5449 case Instruction::Sub:
5450 case Instruction::Mul:
5451 case Instruction::UDiv:
5452 case Instruction::URem:
5453 case Instruction::And:
5454 case Instruction::AShr:
5455 case Instruction::Shl:
5458 case Instruction::Or: {
5461 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5471 case Instruction::Xor:
5475 if (RHSC->getValue().isSignMask())
5476 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5478 if (V->getType()->isIntegerTy(1))
5479 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5482 case Instruction::LShr:
5491 if (SA->getValue().ult(
BitWidth)) {
5493 ConstantInt::get(SA->getContext(),
5495 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5500 case Instruction::ExtractValue: {
5502 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5510 bool Signed = WO->isSigned();
5513 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5518 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5529 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5530 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5532 return std::nullopt;
5558 if (
Op == SymbolicPHI)
5563 if (SourceBits != NewBits)
5581 if (!L || L->getHeader() != PN->
getParent())
5639std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5640ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5648 assert(L &&
"Expecting an integer loop header phi");
5653 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5654 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5655 Value *
V = PN->getIncomingValue(i);
5656 if (
L->contains(PN->getIncomingBlock(i))) {
5659 }
else if (BEValueV != V) {
5663 }
else if (!StartValueV) {
5665 }
else if (StartValueV != V) {
5666 StartValueV =
nullptr;
5670 if (!BEValueV || !StartValueV)
5671 return std::nullopt;
5673 const SCEV *BEValue =
getSCEV(BEValueV);
5680 return std::nullopt;
5684 unsigned FoundIndex =
Add->getNumOperands();
5685 Type *TruncTy =
nullptr;
5687 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5690 if (FoundIndex == e) {
5695 if (FoundIndex ==
Add->getNumOperands())
5696 return std::nullopt;
5700 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5701 if (i != FoundIndex)
5702 Ops.push_back(
Add->getOperand(i));
5708 return std::nullopt;
5761 const SCEV *StartVal =
getSCEV(StartValueV);
5762 const SCEV *PHISCEV =
5789 auto getExtendedExpr = [&](
const SCEV *Expr,
5790 bool CreateSignExtend) ->
const SCEV * {
5793 const SCEV *ExtendedExpr =
5796 return ExtendedExpr;
5804 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5805 const SCEV *ExtendedExpr) ->
bool {
5806 return Expr != ExtendedExpr &&
5810 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5811 if (PredIsKnownFalse(StartVal, StartExtended)) {
5813 return std::nullopt;
5818 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5819 if (PredIsKnownFalse(Accum, AccumExtended)) {
5821 return std::nullopt;
5824 auto AppendPredicate = [&](
const SCEV *Expr,
5825 const SCEV *ExtendedExpr) ->
void {
5826 if (Expr != ExtendedExpr &&
5834 AppendPredicate(StartVal, StartExtended);
5835 AppendPredicate(Accum, AccumExtended);
5843 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5844 std::make_pair(NewAR, Predicates);
5846 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5850std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5855 return std::nullopt;
5858 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5859 if (
I != PredicatedSCEVRewrites.end()) {
5860 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5863 if (Rewrite.first == SymbolicPHI)
5864 return std::nullopt;
5868 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5872 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5873 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5878 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5879 return std::nullopt;
5899 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5900 if (Expr1 != Expr2 &&
5901 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5902 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5919const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5921 Value *StartValueV) {
5924 assert(BEValueV && StartValueV);
5930 if (BO->Opcode != Instruction::Add)
5933 const SCEV *Accum =
nullptr;
5934 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5936 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5950 insertValueToMap(PN, PHISCEV);
5953 inferNoWrapViaConstantRanges(AR);
5960 "Accum is defined outside L, but is not invariant?");
5961 if (isAddRecNeverPoison(BEInst, L))
5968const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5969 const Loop *
L = LI.getLoopFor(PN->
getParent());
5976 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5982 }
else if (BEValueV != V) {
5986 }
else if (!StartValueV) {
5988 }
else if (StartValueV != V) {
5989 StartValueV =
nullptr;
5993 if (!BEValueV || !StartValueV)
5996 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5997 "PHI node already processed?");
6001 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
6006 insertValueToMap(PN, SymbolicName);
6010 const SCEV *BEValue =
getSCEV(BEValueV);
6020 unsigned FoundIndex =
Add->getNumOperands();
6021 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
6022 if (
Add->getOperand(i) == SymbolicName)
6023 if (FoundIndex == e) {
6028 if (FoundIndex !=
Add->getNumOperands()) {
6031 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
6032 if (i != FoundIndex)
6033 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
6045 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
6052 if (
GEP->getOperand(0) == PN) {
6053 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
6071 const SCEV *StartVal =
getSCEV(StartValueV);
6072 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
6077 forgetMemoizedResults({SymbolicName});
6078 insertValueToMap(PN, PHISCEV);
6081 inferNoWrapViaConstantRanges(AR);
6105 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
6106 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
6108 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
6109 const SCEV *StartVal =
getSCEV(StartValueV);
6110 if (Start == StartVal) {
6114 forgetMemoizedResults({SymbolicName});
6115 insertValueToMap(PN, Shifted);
6125 eraseValueFromMap(PN);
6140 Use &LeftUse =
Merge->getOperandUse(0);
6141 Use &RightUse =
Merge->getOperandUse(1);
6177 assert(IDom &&
"At least the entry block should dominate PN");
6185const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
6190 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6207 CommonInst = IncomingInst;
6223ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6229 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6230 bool SCEVExprsIdentical =
6232 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6233 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6236const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6237 if (
const SCEV *S = createAddRecFromPHI(PN))
6247 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6250 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6259 struct FindClosure {
6260 const SCEV *OperandToFind;
6266 bool canRecurseInto(
SCEVTypes Kind)
const {
6269 return RootKind == Kind || NonSequentialRootKind == Kind ||
6274 : OperandToFind(OperandToFind), RootKind(RootKind),
6275 NonSequentialRootKind(
6279 bool follow(
const SCEV *S) {
6280 Found = S == OperandToFind;
6282 return !isDone() && canRecurseInto(S->
getSCEVType());
6285 bool isDone()
const {
return Found; }
6288 FindClosure FC(OperandToFind, RootKind);
6293std::optional<const SCEV *>
6294ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6304 switch (ICI->getPredicate()) {
6318 bool Signed = ICI->isSigned();
6319 const SCEV *LA =
getSCEV(TrueVal);
6327 if (LA == LS &&
RA == RS)
6329 if (LA == RS &&
RA == LS)
6332 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6333 if (
Op->getType()->isPointerTy()) {
6344 LS = CoerceOperand(LS);
6345 RS = CoerceOperand(RS);
6369 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6370 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6384 X = ZExt->getOperand();
6386 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6397 return std::nullopt;
6400static std::optional<const SCEV *>
6402 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6406 "Unexpected operands of a select.");
6418 return std::nullopt;
6433static std::optional<const SCEV *>
6437 return std::nullopt;
6440 const auto *SETrue = SE->
getSCEV(TrueVal);
6441 const auto *SEFalse = SE->
getSCEV(FalseVal);
6445const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6447 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6449 V->getType() ==
TrueVal->getType() &&
6450 "Types of select hands and of the result must match.");
6453 if (!
V->getType()->isIntegerTy(1))
6456 if (std::optional<const SCEV *> S =
6469 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6473 if (std::optional<const SCEV *> S =
6474 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6480 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6486 assert(
GEP->getSourceElementType()->isSized() &&
6487 "GEP source element type must be sized");
6490 for (
Value *Index :
GEP->indices())
6495APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6498 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6501 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6503 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6506 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6525 return GetShiftedByZeros(TZ);
6535 return GetShiftedByZeros(TZ);
6539 if (
M->hasNoUnsignedWrap()) {
6542 for (
const SCEV *Operand :
M->operands().drop_front())
6550 for (
const SCEV *Operand :
M->operands())
6552 return GetShiftedByZeros(TZ);
6557 if (
N->hasNoUnsignedWrap())
6558 return GetGCDMultiple(
N);
6561 for (
const SCEV *Operand :
N->operands().drop_front())
6563 return GetShiftedByZeros(TZ);
6580 CtxI = &*F.getEntryBlock().begin();
6587 .allowEphemerals(
true))
6588 .countMinTrailingZeros();
6589 return GetShiftedByZeros(
Known);
6602 return getConstantMultipleImpl(S, CtxI);
6604 auto I = ConstantMultipleCache.find(S);
6605 if (
I != ConstantMultipleCache.end())
6608 APInt Result = getConstantMultipleImpl(S, CtxI);
6609 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6610 assert(InsertPair.second &&
"Should insert a new key");
6611 return InsertPair.first->second;
6628 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6631 if (std::optional<ConstantRange>
Range = CB->getRange())
6635 if (std::optional<ConstantRange>
Range =
A->getRange())
6638 return std::nullopt;
6645 UnsignedRanges.erase(AddRec);
6646 SignedRanges.erase(AddRec);
6647 ConstantMultipleCache.erase(AddRec);
6652getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6678 Value *Start, *Step;
6685 assert(L && L->getHeader() ==
P->getParent());
6698 case Instruction::AShr:
6699 case Instruction::LShr:
6700 case Instruction::Shl:
6715 KnownStep.getBitWidth() ==
BitWidth);
6718 auto MaxShiftAmt = KnownStep.getMaxValue();
6720 bool Overflow =
false;
6721 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6728 case Instruction::AShr: {
6736 if (KnownStart.isNonNegative())
6739 KnownStart.getMaxValue() + 1);
6740 if (KnownStart.isNegative())
6743 KnownEnd.getMaxValue() + 1);
6746 case Instruction::LShr: {
6755 KnownStart.getMaxValue() + 1);
6757 case Instruction::Shl: {
6761 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6762 return ConstantRange(KnownStart.getMinValue(),
6763 KnownEnd.getMaxValue() + 1);
6788 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6795ScalarEvolution::getRangeRefIter(
const SCEV *S,
6796 ScalarEvolution::RangeSignHint SignHint) {
6797 DenseMap<const SCEV *, ConstantRange> &Cache =
6798 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6801 SmallPtrSet<const SCEV *, 8> Seen;
6805 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6806 if (!Seen.
insert(Expr).second)
6840 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6841 const SCEV *
P = WorkList[
I];
6845 for (
const SCEV *
Op :
P->operands())
6858 if (!WorkList.
empty()) {
6863 getRangeRef(
P, SignHint);
6867 return getRangeRef(S, SignHint, 0);
6874 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6875 DenseMap<const SCEV *, ConstantRange> &Cache =
6876 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6883 auto I = Cache.
find(S);
6884 if (
I != Cache.
end())
6888 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6893 return getRangeRefIter(S, SignHint);
6896 ConstantRange ConservativeResult(
BitWidth,
true);
6897 using OBO = OverflowingBinaryOperator;
6901 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6905 ConservativeResult =
6912 ConservativeResult = ConstantRange(
6928 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6935 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6942 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6948 return setRange(Cast, SignHint,
X);
6953 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6954 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6956 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6957 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6958 ConservativeResult =
6959 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6961 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6962 unsigned WrapType = OBO::AnyWrap;
6963 if (
Add->hasNoSignedWrap())
6964 WrapType |= OBO::NoSignedWrap;
6965 if (
Add->hasNoUnsignedWrap())
6966 WrapType |= OBO::NoUnsignedWrap;
6968 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6970 return setRange(
Add, SignHint,
6971 ConservativeResult.intersectWith(
X, RangeType));
6975 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6977 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6978 return setRange(
Mul, SignHint,
6979 ConservativeResult.intersectWith(
X, RangeType));
6983 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6984 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6985 return setRange(UDiv, SignHint,
6986 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6994 if (!UnsignedMinValue.
isZero())
6995 ConservativeResult = ConservativeResult.intersectWith(
6996 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
7005 bool AllNonNeg =
true;
7006 bool AllNonPos =
true;
7007 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
7014 ConservativeResult = ConservativeResult.intersectWith(
7019 ConservativeResult = ConservativeResult.intersectWith(
7028 const SCEV *MaxBEScev =
7042 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
7044 ConservativeResult =
7045 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
7048 auto RangeFromFactoring = getRangeViaFactoring(
7050 ConservativeResult =
7051 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
7057 const SCEV *SymbolicMaxBECount =
7062 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
7063 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
7064 ConservativeResult =
7065 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
7070 return setRange(AddRec, SignHint, std::move(ConservativeResult));
7080 ID = Intrinsic::umax;
7083 ID = Intrinsic::smax;
7087 ID = Intrinsic::umin;
7090 ID = Intrinsic::smin;
7097 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
7098 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
7100 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
7101 return setRange(S, SignHint,
7102 ConservativeResult.intersectWith(
X, RangeType));
7111 ConservativeResult =
7112 ConservativeResult.intersectWith(*MDRange, RangeType);
7117 auto CR = getRangeForUnknownRecurrence(U);
7118 ConservativeResult = ConservativeResult.intersectWith(CR);
7129 if (
U->getType()->isPointerTy()) {
7132 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
7133 int ptrIdxDiff = ptrSize -
BitWidth;
7134 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
7140 if (!
Known.Zero.getHiBits(NS).isZero())
7141 Known.Zero.setHighBits(NS);
7142 if (!
Known.One.getHiBits(NS).isZero())
7143 Known.One.setHighBits(NS);
7146 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
7147 ConservativeResult = ConservativeResult.intersectWith(
7148 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
7151 ConservativeResult = ConservativeResult.intersectWith(
7156 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
7160 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
7161 DL, CanBeNull,
nullptr);
7171 uint64_t
Align =
U->getValue()->getPointerAlignment(DL).value();
7172 uint64_t Rem = MaxVal.
urem(Align);
7177 ConservativeResult = ConservativeResult.intersectWith(
7187 return getRangeRef(AR, SignHint,
Depth + 1);
7191 ConstantRange RangeFromOps(
BitWidth,
false);
7193 for (
const auto &
Op :
Phi->operands()) {
7195 RangeFromOps = RangeFromOps.unionWith(OpRange);
7197 if (RangeFromOps.isFullSet())
7200 ConservativeResult =
7201 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7207 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7209 ConservativeResult = ConservativeResult.difference(Disallowed);
7212 return setRange(U, SignHint, std::move(ConservativeResult));
7218 return setRange(S, SignHint, std::move(ConservativeResult));
7226static std::pair<ConstantRange, bool>
7234 if (Step == 0 || MaxBECount == 0)
7235 return {StartRange,
true};
7241 return {ConstantRange::getFull(
BitWidth),
false};
7257 return {ConstantRange::getFull(
BitWidth),
false};
7270 APInt MovedBoundary;
7275 MovedBoundary = StartLower - std::move(
Offset);
7278 MovedBoundary = StartUpper + std::move(
Offset);
7282 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7289 if (StartRange.
contains(MovedBoundary))
7290 return {ConstantRange::getFull(
BitWidth),
false};
7293 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7295 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7303std::pair<ConstantRange, SCEV::NoWrapFlags>
7304ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7305 const APInt &MaxBECount) {
7309 "mismatched bit widths");
7318 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7320 StartSRange, MaxBECount,
7322 ConstantRange SR = SR1.unionWith(SR2);
7339ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7341 ScalarEvolution::RangeSignHint SignHint) {
7342 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7344 "This only works for non-self-wrapping AddRecs!");
7345 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7349 return ConstantRange::getFull(
BitWidth);
7357 return ConstantRange::getFull(
BitWidth);
7361 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7363 MaxItersWithoutWrap))
7364 return ConstantRange::getFull(
BitWidth);
7385 ConstantRange StartRange = getRangeRef(Start, SignHint);
7386 ConstantRange EndRange = getRangeRef(End, SignHint);
7387 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7391 return RangeBetween;
7396 return ConstantRange::getFull(
BitWidth);
7399 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7400 return RangeBetween;
7402 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7403 return RangeBetween;
7404 return ConstantRange::getFull(
BitWidth);
7409 const APInt &MaxBECount) {
7416 "mismatched bit widths");
7418 struct SelectPattern {
7419 Value *Condition =
nullptr;
7423 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7425 std::optional<unsigned> CastOp;
7439 CastOp = SCast->getSCEVType();
7440 S = SCast->getOperand();
7443 using namespace llvm::PatternMatch;
7450 Condition =
nullptr;
7482 bool isRecognized() {
return Condition !=
nullptr; }
7485 SelectPattern StartPattern(*
this,
BitWidth, Start);
7486 if (!StartPattern.isRecognized())
7487 return ConstantRange::getFull(
BitWidth);
7489 SelectPattern StepPattern(*
this,
BitWidth, Step);
7490 if (!StepPattern.isRecognized())
7491 return ConstantRange::getFull(
BitWidth);
7493 if (StartPattern.Condition != StepPattern.Condition) {
7497 return ConstantRange::getFull(
BitWidth);
7508 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7509 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7510 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7511 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7513 ConstantRange TrueRange =
7514 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7515 ConstantRange FalseRange =
7516 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7528 PDI && PDI->isDisjoint()) {
7543ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7556 SmallPtrSet<const SCEV *, 16> Visited;
7558 auto pushOp = [&](
const SCEV *S) {
7559 if (!Visited.
insert(S).second)
7562 if (Visited.
size() > 30) {
7573 while (!Worklist.
empty()) {
7575 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7576 if (!Bound || DT.dominates(Bound, DefI))
7583 return Bound ? Bound : &*F.getEntryBlock().begin();
7589 return getDefiningScopeBound(
Ops, Discard);
7592bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7594 if (
A->getParent() ==
B->getParent() &&
7599 auto *BLoop = LI.getLoopFor(
B->getParent());
7600 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7601 BLoop->getLoopPreheader() ==
A->getParent() &&
7603 A->getParent()->end()) &&
7611 SCEVPoisonCollector PC(
true);
7613 return PC.MaybePoison.empty();
7616bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7626bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7643 for (
const Use &
Op :
I->operands()) {
7649 auto *DefI = getDefiningScopeBound(SCEVOps);
7650 return isGuaranteedToTransferExecutionTo(DefI,
I);
7653bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7655 if (isSCEVExprNeverPoison(
I))
7666 auto *ExitingBB =
L->getExitingBlock();
7670 SmallPtrSet<const Value *, 16> KnownPoison;
7679 while (!Worklist.
empty()) {
7682 for (
const Use &U :
Poison->uses()) {
7685 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7689 if (KnownPoison.
insert(PoisonUser).second)
7697ScalarEvolution::LoopProperties
7698ScalarEvolution::getLoopProperties(
const Loop *L) {
7699 using LoopProperties = ScalarEvolution::LoopProperties;
7701 auto Itr = LoopPropertiesCache.find(L);
7702 if (Itr == LoopPropertiesCache.end()) {
7705 return !
SI->isSimple();
7715 return I->mayWriteToMemory();
7718 LoopProperties LP = {
true,
7721 for (
auto *BB :
L->getBlocks())
7722 for (
auto &
I : *BB) {
7724 LP.HasNoAbnormalExits =
false;
7725 if (HasSideEffects(&
I))
7726 LP.HasNoSideEffects =
false;
7727 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7731 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7732 assert(InsertPair.second &&
"We just checked!");
7733 Itr = InsertPair.first;
7746const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7752 Stack.emplace_back(V,
false);
7753 while (!Stack.empty()) {
7754 auto E = Stack.back();
7755 Value *CurV = E.getPointer();
7763 const SCEV *CreatedSCEV =
nullptr;
7766 CreatedSCEV = createSCEV(CurV);
7771 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7775 insertValueToMap(CurV, CreatedSCEV);
7778 Stack.back().setInt(
true);
7781 Stack.emplace_back(
Op,
false);
7798 if (!DT.isReachableFromEntry(
I->getParent()))
7811 switch (BO->Opcode) {
7812 case Instruction::Add:
7813 case Instruction::Mul: {
7820 Ops.push_back(BO->
Op);
7824 Ops.push_back(BO->RHS);
7828 (BO->Opcode == Instruction::Add &&
7829 (NewBO->Opcode != Instruction::Add &&
7830 NewBO->Opcode != Instruction::Sub)) ||
7831 (BO->Opcode == Instruction::Mul &&
7832 NewBO->Opcode != Instruction::Mul)) {
7833 Ops.push_back(BO->LHS);
7838 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7841 Ops.push_back(BO->LHS);
7849 case Instruction::Sub:
7850 case Instruction::UDiv:
7851 case Instruction::URem:
7853 case Instruction::AShr:
7854 case Instruction::Shl:
7855 case Instruction::Xor:
7859 case Instruction::And:
7860 case Instruction::Or:
7864 case Instruction::LShr:
7871 Ops.push_back(BO->LHS);
7872 Ops.push_back(BO->RHS);
7876 switch (
U->getOpcode()) {
7877 case Instruction::Trunc:
7878 case Instruction::ZExt:
7879 case Instruction::SExt:
7880 case Instruction::PtrToAddr:
7881 case Instruction::PtrToInt:
7882 Ops.push_back(
U->getOperand(0));
7885 case Instruction::BitCast:
7887 Ops.push_back(
U->getOperand(0));
7892 case Instruction::SDiv:
7893 case Instruction::SRem:
7894 Ops.push_back(
U->getOperand(0));
7895 Ops.push_back(
U->getOperand(1));
7898 case Instruction::GetElementPtr:
7900 "GEP source element type must be sized");
7904 case Instruction::IntToPtr:
7907 case Instruction::PHI:
7938 Ops.push_back(CondICmp->getOperand(0));
7939 Ops.push_back(CondICmp->getOperand(1));
7959 case Instruction::Select: {
7961 auto CanSimplifyToUnknown = [
this,
U]() {
7979 if (CanSimplifyToUnknown())
7986 case Instruction::Call:
7987 case Instruction::Invoke:
7994 switch (
II->getIntrinsicID()) {
7995 case Intrinsic::abs:
7996 Ops.push_back(
II->getArgOperand(0));
7998 case Intrinsic::umax:
7999 case Intrinsic::umin:
8000 case Intrinsic::smax:
8001 case Intrinsic::smin:
8002 case Intrinsic::usub_sat:
8003 case Intrinsic::uadd_sat:
8004 Ops.push_back(
II->getArgOperand(0));
8005 Ops.push_back(
II->getArgOperand(1));
8007 case Intrinsic::start_loop_iterations:
8008 case Intrinsic::annotation:
8009 case Intrinsic::ptr_annotation:
8010 Ops.push_back(
II->getArgOperand(0));
8022const SCEV *ScalarEvolution::createSCEV(
Value *V) {
8031 if (!DT.isReachableFromEntry(
I->getParent()))
8046 switch (BO->Opcode) {
8047 case Instruction::Add: {
8073 if (BO->Opcode == Instruction::Sub)
8081 if (BO->Opcode == Instruction::Sub)
8088 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
8089 NewBO->Opcode != Instruction::Sub)) {
8099 case Instruction::Mul: {
8120 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
8129 case Instruction::UDiv:
8133 case Instruction::URem:
8137 case Instruction::Sub: {
8140 Flags = getNoWrapFlagsFromUB(BO->
Op);
8145 case Instruction::And:
8151 if (CI->isMinusOne())
8153 const APInt &
A = CI->getValue();
8159 unsigned LZ =
A.countl_zero();
8160 unsigned TZ =
A.countr_zero();
8165 APInt EffectiveMask =
8167 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
8170 const SCEV *ShiftedLHS =
nullptr;
8174 unsigned MulZeros = OpC->getAPInt().countr_zero();
8175 unsigned GCD = std::min(MulZeros, TZ);
8180 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8202 case Instruction::Or:
8211 case Instruction::Xor:
8214 if (CI->isMinusOne())
8223 if (LBO->getOpcode() == Instruction::And &&
8224 LCI->getValue() == CI->getValue())
8225 if (
const SCEVZeroExtendExpr *Z =
8228 const SCEV *Z0 =
Z->getOperand();
8235 if (CI->getValue().isMask(Z0TySize))
8241 APInt Trunc = CI->getValue().trunc(Z0TySize);
8250 case Instruction::Shl:
8268 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8277 ConstantInt *
X = ConstantInt::get(
8283 case Instruction::AShr:
8305 const SCEV *AddTruncateExpr =
nullptr;
8306 ConstantInt *ShlAmtCI =
nullptr;
8307 const SCEV *AddConstant =
nullptr;
8309 if (L &&
L->getOpcode() == Instruction::Add) {
8317 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8324 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8332 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8337 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8342 if (AddTruncateExpr && ShlAmtCI) {
8354 const APInt &ShlAmt = ShlAmtCI->
getValue();
8358 const SCEV *CompositeExpr =
8360 if (
L->getOpcode() != Instruction::Shl)
8361 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8370 switch (
U->getOpcode()) {
8371 case Instruction::Trunc:
8374 case Instruction::ZExt:
8377 case Instruction::SExt:
8387 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8388 Type *Ty =
U->getType();
8396 case Instruction::BitCast:
8402 case Instruction::PtrToAddr: {
8409 case Instruction::PtrToInt: {
8412 Type *DstIntTy =
U->getType();
8420 case Instruction::IntToPtr:
8424 case Instruction::SDiv:
8431 case Instruction::SRem:
8438 case Instruction::GetElementPtr:
8441 case Instruction::PHI:
8444 case Instruction::Select:
8445 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8448 case Instruction::Call:
8449 case Instruction::Invoke:
8454 switch (
II->getIntrinsicID()) {
8455 case Intrinsic::abs:
8459 case Intrinsic::umax:
8463 case Intrinsic::umin:
8467 case Intrinsic::smax:
8471 case Intrinsic::smin:
8475 case Intrinsic::usub_sat: {
8476 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8477 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8481 case Intrinsic::uadd_sat: {
8482 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8483 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8487 case Intrinsic::start_loop_iterations:
8488 case Intrinsic::annotation:
8489 case Intrinsic::ptr_annotation:
8493 case Intrinsic::vscale:
8513 auto *ExitCountType = ExitCount->
getType();
8514 assert(ExitCountType->isIntegerTy());
8516 1 + ExitCountType->getScalarSizeInBits());
8529 auto CanAddOneWithoutOverflow = [&]() {
8531 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8542 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8572 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8573 assert(L->isLoopExiting(ExitingBlock) &&
8574 "Exiting block must actually branch out of the loop!");
8583 const auto *MaxExitCount =
8591 L->getExitingBlocks(ExitingBlocks);
8593 std::optional<unsigned> Res;
8594 for (
auto *ExitingBB : ExitingBlocks) {
8598 Res = std::gcd(*Res, Multiple);
8600 return Res.value_or(1);
8604 const SCEV *ExitCount) {
8634 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8635 assert(L->isLoopExiting(ExitingBlock) &&
8636 "Exiting block must actually branch out of the loop!");
8646 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8648 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8650 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8660 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8663 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8666 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8674 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8681 return getBackedgeTakenInfo(L).getExact(L,
this);
8683 return getBackedgeTakenInfo(L).getConstantMax(
this);
8685 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8692 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8697 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8701 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8704ScalarEvolution::BackedgeTakenInfo &
8705ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8706 auto &BTI = getBackedgeTakenInfo(L);
8707 if (BTI.hasFullInfo())
8710 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8713 return Pair.first->second;
8715 BackedgeTakenInfo Result =
8716 computeBackedgeTakenCount(L,
true);
8718 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8721ScalarEvolution::BackedgeTakenInfo &
8722ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8728 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8729 BackedgeTakenCounts.try_emplace(L);
8731 return Pair.first->second;
8736 BackedgeTakenInfo Result = computeBackedgeTakenCount(L);
8743 if (Result.hasAnyInfo()) {
8746 auto LoopUsersIt = LoopUsers.find(L);
8747 if (LoopUsersIt != LoopUsers.end())
8749 forgetMemoizedResults(ToForget);
8752 for (
PHINode &PN : L->getHeader()->phis())
8753 ConstantEvolutionLoopExitValue.erase(&PN);
8761 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8770 BackedgeTakenCounts.clear();
8771 PredicatedBackedgeTakenCounts.clear();
8772 BECountUsers.clear();
8773 LoopPropertiesCache.clear();
8774 ConstantEvolutionLoopExitValue.clear();
8775 ValueExprMap.clear();
8776 ValuesAtScopes.clear();
8777 ValuesAtScopesUsers.clear();
8778 LoopDispositions.clear();
8779 BlockDispositions.clear();
8780 UnsignedRanges.clear();
8781 SignedRanges.clear();
8782 ExprValueMap.clear();
8784 ConstantMultipleCache.clear();
8785 PredicatedSCEVRewrites.clear();
8787 FoldCacheUser.clear();
8789void ScalarEvolution::visitAndClearUsers(
8793 while (!Worklist.
empty()) {
8800 if (It != ValueExprMap.
end()) {
8802 eraseValueFromMap(It->first);
8804 ConstantEvolutionLoopExitValue.erase(PN);
8816 while (!LoopWorklist.
empty()) {
8820 forgetBackedgeTakenCounts(CurrL,
false);
8821 forgetBackedgeTakenCounts(CurrL,
true);
8824 PredicatedSCEVRewrites.remove_if(
8825 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8827 auto LoopUsersItr = LoopUsers.find(CurrL);
8828 if (LoopUsersItr != LoopUsers.end())
8832 for (
PHINode &PN : CurrL->getHeader()->phis()) {
8833 ConstantEvolutionLoopExitValue.erase(&PN);
8834 auto VIt = ValueExprMap.find_as(
static_cast<Value *
>(&PN));
8835 if (VIt != ValueExprMap.end())
8839 LoopPropertiesCache.erase(CurrL);
8842 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8844 forgetMemoizedResults(ToForget);
8861 visitAndClearUsers(Worklist, Visited, ToForget);
8863 forgetMemoizedResults(ToForget);
8875 struct InvalidationRootCollector {
8879 InvalidationRootCollector(
Loop *L) : L(L) {}
8881 bool follow(
const SCEV *S) {
8887 if (L->contains(AddRec->
getLoop()))
8892 bool isDone()
const {
return false; }
8895 InvalidationRootCollector
C(L);
8897 forgetMemoizedResults(
C.Roots);
8910 BlockDispositions.clear();
8911 LoopDispositions.clear();
8928 while (!Worklist.
empty()) {
8930 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8931 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8932 if (!LoopDispoRemoved && !BlockDispoRemoved)
8934 auto Users = SCEVUsers.find(Curr);
8935 if (
Users != SCEVUsers.end())
8948const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8952 if (!isComplete() || ExitNotTaken.
empty())
8963 for (
const auto &ENT : ExitNotTaken) {
8964 const SCEV *BECount = ENT.ExactNotTaken;
8967 "We should only have known counts for exiting blocks that dominate "
8970 Ops.push_back(BECount);
8975 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8976 "Predicate should be always true!");
8985const ScalarEvolution::ExitNotTakenInfo *
8986ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8987 const BasicBlock *ExitingBlock,
8988 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8989 for (
const auto &ENT : ExitNotTaken)
8990 if (ENT.ExitingBlock == ExitingBlock) {
8991 if (ENT.hasAlwaysTruePredicate())
8993 else if (Predicates) {
9003const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
9005 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
9006 if (!getConstantMax())
9009 for (
const auto &ENT : ExitNotTaken)
9010 if (!ENT.hasAlwaysTruePredicate()) {
9018 "No point in having a non-constant max backedge taken count!");
9019 return getConstantMax();
9022const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
9024 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
9032 for (
const auto &ENT : ExitNotTaken) {
9033 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
9036 "We should only have known counts for exiting blocks that "
9042 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
9043 "Predicate should be always true!");
9046 if (ExitCounts.
empty())
9055bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
9057 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
9058 return !ENT.hasAlwaysTruePredicate();
9060 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
9076 this->ExactNotTaken = E = ConstantMaxNotTaken;
9077 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
9082 "Exact is not allowed to be less precise than Constant Max");
9085 "Exact is not allowed to be less precise than Symbolic Max");
9088 "Symbolic Max is not allowed to be less precise than Constant Max");
9091 "No point in having a non-constant max backedge taken count!");
9093 for (
const auto PredList : PredLists)
9094 for (
const auto *
P : PredList) {
9102 "Backedge count should be int");
9105 "Max backedge count should be int");
9118ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
9120 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
9121 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
9122 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9124 ExitNotTaken.reserve(ExitCounts.
size());
9125 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
9126 std::back_inserter(ExitNotTaken),
9127 [&](
const EdgeExitInfo &EEI) {
9128 BasicBlock *ExitBB = EEI.first;
9129 const ExitLimit &EL = EEI.second;
9130 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
9131 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
9136 "No point in having a non-constant max backedge taken count!");
9140ScalarEvolution::BackedgeTakenInfo
9141ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
9142 bool AllowPredicates) {
9144 L->getExitingBlocks(ExitingBlocks);
9146 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9149 bool CouldComputeBECount =
true;
9151 const SCEV *MustExitMaxBECount =
nullptr;
9152 const SCEV *MayExitMaxBECount =
nullptr;
9153 bool MustExitMaxOrZero =
false;
9154 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9165 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9166 if (ExitIfTrue == CI->
isZero())
9170 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9172 assert((AllowPredicates || EL.Predicates.empty()) &&
9173 "Predicated exit limit when predicates are not allowed!");
9178 ++NumExitCountsComputed;
9182 CouldComputeBECount =
false;
9189 "Exact is known but symbolic isn't?");
9190 ++NumExitCountsNotComputed;
9205 DT.dominates(ExitBB, Latch)) {
9206 if (!MustExitMaxBECount) {
9207 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9208 MustExitMaxOrZero = EL.MaxOrZero;
9211 EL.ConstantMaxNotTaken);
9215 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9218 EL.ConstantMaxNotTaken);
9222 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9226 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9232 for (
const auto &Pair : ExitCounts) {
9234 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9236 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9237 {
L, AllowPredicates});
9239 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9240 MaxBECount, MaxOrZero);
9243ScalarEvolution::ExitLimit
9244ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9245 bool IsOnlyExit,
bool AllowPredicates) {
9246 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9250 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9255 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9256 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9257 "It should have one successor in loop and one exit block!");
9268 if (!
L->contains(SBB)) {
9273 assert(Exit &&
"Exiting block must have at least one exit");
9274 return computeExitLimitFromSingleExitSwitch(
9275 L, SI, Exit, IsOnlyExit);
9282 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9283 bool AllowPredicates) {
9284 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9285 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9286 ControlsOnlyExit, AllowPredicates);
9289std::optional<ScalarEvolution::ExitLimit>
9290ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9291 bool ExitIfTrue,
bool ControlsOnlyExit,
9292 bool AllowPredicates) {
9294 (void)this->ExitIfTrue;
9295 (void)this->AllowPredicates;
9297 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9298 this->AllowPredicates == AllowPredicates &&
9299 "Variance in assumed invariant key components!");
9300 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9301 if (Itr == TripCountMap.end())
9302 return std::nullopt;
9306void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9308 bool ControlsOnlyExit,
9309 bool AllowPredicates,
9311 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9312 this->AllowPredicates == AllowPredicates &&
9313 "Variance in assumed invariant key components!");
9315 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9316 assert(InsertResult.second &&
"Expected successful insertion!");
9321ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9322 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9323 bool ControlsOnlyExit,
bool AllowPredicates) {
9325 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9329 ExitLimit EL = computeExitLimitFromCondImpl(
9330 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9331 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9335ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9336 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9337 bool ControlsOnlyExit,
bool AllowPredicates) {
9339 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9340 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9341 return *LimitFromBinOp;
9347 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9348 if (EL.hasFullInfo() || !AllowPredicates)
9352 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9372 const WithOverflowInst *WO;
9387 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9388 ControlsOnlyExit, AllowPredicates);
9389 if (EL.hasAnyInfo())
9394 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9397std::optional<ScalarEvolution::ExitLimit>
9398ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9402 bool AllowPredicates) {
9411 return std::nullopt;
9415 ExitLimit EL0 = computeExitLimitFromCondCached(
9416 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9417 ExitLimit EL1 = computeExitLimitFromCondCached(
9418 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9423 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9428 if (EitherMayExit) {
9438 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9440 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9443 EL1.ConstantMaxNotTaken);
9445 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9447 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9450 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9454 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9455 BECount = EL0.ExactNotTaken;
9468 SymbolicMaxBECount =
9470 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9474ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9475 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9476 bool AllowPredicates) {
9488 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9490 if (EL.hasAnyInfo())
9493 auto *ExhaustiveCount =
9494 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9497 return ExhaustiveCount;
9499 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9502ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9504 bool ControlsOnlyExit,
bool AllowPredicates) {
9529 ConstantRange CompRange =
9547 InnerLHS = ZExt->getOperand();
9594 if (EL.hasAnyInfo())
9611 if (EL.hasAnyInfo())
return EL;
9643 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9645 if (EL.hasAnyInfo())
9661 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9663 if (EL.hasAnyInfo())
9674ScalarEvolution::ExitLimit
9675ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9677 BasicBlock *ExitingBlock,
9678 bool ControlsOnlyExit) {
9679 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9682 if (
Switch->getDefaultDest() == ExitingBlock)
9686 "Default case must not exit the loop!");
9692 if (EL.hasAnyInfo())
9704 "Evaluation of SCEV at constant didn't fold correctly?");
9708ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9718 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9725 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9727 unsigned &OutShiftAmt) {
9728 using namespace PatternMatch;
9730 ConstantInt *ShiftAmt;
9732 OutOpCode = Instruction::LShr;
9734 OutOpCode = Instruction::AShr;
9736 OutOpCode = Instruction::Shl;
9741 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9756 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9758 unsigned &ShiftAmtOut) {
9759 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9775 if (MatchPositiveShift(
LHS, V, OpC, Amt)) {
9776 PostShiftOpCode = OpC;
9782 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9785 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9791 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9798 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9804 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9816 ConstantInt *StableValue =
nullptr;
9821 case Instruction::AShr: {
9828 if (
Known.isNonNegative())
9829 StableValue = ConstantInt::get(Ty, 0);
9830 else if (
Known.isNegative())
9831 StableValue = ConstantInt::get(Ty, -1,
true);
9837 case Instruction::LShr:
9838 case Instruction::Shl:
9848 "Otherwise cannot be an operand to a branch instruction");
9850 if (
Result->isNullValue()) {
9859 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9861 const SCEV *StartSCEV =
getSCEV(StartValue);
9865 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9866 MaxBTC = std::min(MaxBTC, RangeBTC);
9870 const SCEV *UpperBound =
9887 if (
const Function *
F = CI->getCalledFunction())
9896 if (!L->contains(
I))
return false;
9901 return L->getHeader() ==
I->getParent();
9977 if (!
I)
return nullptr;
9990 std::vector<Constant*> Operands(
I->getNumOperands());
9992 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9996 if (!Operands[i])
return nullptr;
10001 if (!
C)
return nullptr;
10023 if (IncomingVal != CurrentVal) {
10026 IncomingVal = CurrentVal;
10030 return IncomingVal;
10038ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
10041 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
10050 DenseMap<Instruction *, Constant *> CurrentIterVals;
10052 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10058 for (PHINode &
PHI : Header->phis()) {
10060 CurrentIterVals[&
PHI] = StartCST;
10062 if (!CurrentIterVals.
count(PN))
10063 return RetVal =
nullptr;
10069 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
10072 unsigned IterationNum = 0;
10074 for (; ; ++IterationNum) {
10075 if (IterationNum == NumIterations)
10076 return RetVal = CurrentIterVals[PN];
10080 DenseMap<Instruction *, Constant *> NextIterVals;
10085 NextIterVals[PN] = NextPHI;
10087 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
10093 for (
const auto &
I : CurrentIterVals) {
10095 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
10100 for (
const auto &
I : PHIsToCompute) {
10101 PHINode *
PHI =
I.first;
10104 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10107 if (NextPHI !=
I.second)
10108 StoppedEvolving =
false;
10113 if (StoppedEvolving)
10114 return RetVal = CurrentIterVals[PN];
10116 CurrentIterVals.swap(NextIterVals);
10120const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
10130 DenseMap<Instruction *, Constant *> CurrentIterVals;
10132 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10135 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
10137 for (PHINode &
PHI : Header->phis()) {
10139 CurrentIterVals[&
PHI] = StartCST;
10141 if (!CurrentIterVals.
count(PN))
10149 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10156 if (CondVal->getValue() == uint64_t(ExitWhen)) {
10157 ++NumBruteForceTripCountsComputed;
10162 DenseMap<Instruction *, Constant *> NextIterVals;
10168 for (
const auto &
I : CurrentIterVals) {
10170 if (!
PHI ||
PHI->getParent() != Header)
continue;
10173 for (PHINode *
PHI : PHIsToCompute) {
10175 if (NextPHI)
continue;
10177 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10180 CurrentIterVals.
swap(NextIterVals);
10193 return LS.second ? LS.second : V;
10195 Values.emplace_back(L,
nullptr);
10198 const SCEV *
C = computeSCEVAtScope(V, L);
10199 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10200 if (LS.first == L) {
10203 ValuesAtScopesUsers[
C].push_back({L, V});
10214 switch (V->getSCEVType()) {
10254 assert(!
C->getType()->isPointerTy() &&
10255 "Can only have one pointer, and it must be last");
10280const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10281 SmallVectorImpl<SCEVUse> &NewOps) {
10316const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10317 switch (
V->getSCEVType()) {
10328 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10339 for (++i; i !=
e; ++i)
10384 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10394 for (++i; i !=
e; ++i) {
10399 return getWithOperands(V, NewOps);
10414 const Loop *CurrLoop = this->LI[
I->getParent()];
10425 if (BackedgeTakenCount->
isZero()) {
10426 Value *InitValue =
nullptr;
10427 bool MultipleInitValues =
false;
10433 MultipleInitValues =
true;
10438 if (!MultipleInitValues && InitValue)
10447 unsigned InLoopPred =
10458 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10472 SmallVector<Constant *, 4> Operands;
10473 Operands.
reserve(
I->getNumOperands());
10474 bool MadeImprovement =
false;
10489 MadeImprovement |= OrigV != OpV;
10494 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10499 if (!MadeImprovement)
10520const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10522 return stripInjectiveFunctions(ZExt->getOperand());
10524 return stripInjectiveFunctions(SExt->getOperand());
10542 assert(
A != 0 &&
"A must be non-zero.");
10558 if (MinTZ < Mult2 && L->getLoopPredecessor())
10560 if (MinTZ < Mult2) {
10583 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10603static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10609 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10610 << *AddRec <<
'\n');
10613 if (!LC || !MC || !
NC) {
10614 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10615 return std::nullopt;
10621 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10629 N =
N.sext(NewWidth);
10630 M = M.sext(NewWidth);
10631 L = L.sext(NewWidth);
10648 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10649 <<
", multiplied by " <<
T <<
'\n');
10658 std::optional<APInt>
Y) {
10660 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10663 return XW.
slt(YW) ? *
X : *
Y;
10666 return std::nullopt;
10667 return X ? *
X : *
Y;
10684 return std::nullopt;
10685 unsigned W =
X->getBitWidth();
10705static std::optional<APInt>
10711 return std::nullopt;
10714 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10715 std::optional<APInt>
X =
10718 return std::nullopt;
10723 return std::nullopt;
10738static std::optional<APInt>
10742 "Starting value of addrec should be 0");
10743 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10744 <<
Range <<
", addrec " << *AddRec <<
'\n');
10748 "Addrec's initial value should be in range");
10754 return std::nullopt;
10764 auto SolveForBoundary =
10765 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10768 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10769 << Bound <<
" (before multiplying by " << M <<
")\n");
10772 std::optional<APInt> SO;
10775 "signed overflow\n");
10779 "unsigned overflow\n");
10780 std::optional<APInt> UO =
10783 auto LeavesRange = [&] (
const APInt &
X) {
10791 if (
Range.contains(
V1->getValue()))
10800 return {std::nullopt,
false};
10805 if (LeavesRange(*Min))
10806 return { Min,
true };
10807 std::optional<APInt> Max = Min == SO ? UO : SO;
10808 if (LeavesRange(*Max))
10809 return { Max,
true };
10812 return {std::nullopt,
true};
10819 auto SL = SolveForBoundary(
Lower);
10820 auto SU = SolveForBoundary(
Upper);
10823 if (!SL.second || !SU.second)
10824 return std::nullopt;
10867ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10869 bool ControlsOnlyExit,
10870 bool AllowPredicates) {
10881 if (
C->getValue()->isZero())
return C;
10885 const SCEVAddRecExpr *AddRec =
10888 if (!AddRec && AllowPredicates)
10894 if (!AddRec || AddRec->
getLoop() != L)
10905 return ExitLimit(R, R, R,
false, Predicates);
10963 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10989 const SCEV *
Exact =
10997 const SCEV *SymbolicMax =
10999 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
11008 AllowPredicates ? &Predicates :
nullptr, *
this, L);
11016 return ExitLimit(
E, M, S,
false, Predicates);
11019ScalarEvolution::ExitLimit
11020ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
11028 if (!
C->getValue()->isZero())
11038std::pair<const BasicBlock *, const BasicBlock *>
11039ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
11050 if (
const Loop *L = LI.getLoopFor(BB))
11051 return {
L->getLoopPredecessor(),
L->getHeader()};
11053 return {
nullptr, BB};
11062 if (
A ==
B)
return true;
11077 if (ComputesEqualValues(AI, BI))
11085 const SCEV *Op0, *Op1;
11104 auto TrivialCase = [&](
bool TriviallyTrue) {
11113 const SCEV *NewLHS, *NewRHS;
11137 return TrivialCase(
false);
11138 return TrivialCase(
true);
11157 RAdd->hasNoSignedWrap()) ||
11159 RAdd->hasNoUnsignedWrap())) {
11179 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
11180 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
11183 C->getAPInt().isStrictlyPositive()) ||
11207 const APInt &
RA = RC->getAPInt();
11209 bool SimplifiedByConstantRange =
false;
11214 return TrivialCase(
true);
11216 return TrivialCase(
false);
11225 Changed = SimplifiedByConstantRange =
true;
11229 if (!SimplifiedByConstantRange) {
11246 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11252 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11258 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11264 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11276 return TrivialCase(
true);
11278 return TrivialCase(
false);
11383 auto NonRecursive = [OrNegative](
const SCEV *S) {
11385 return C->getAPInt().isPowerOf2() ||
11386 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11392 if (NonRecursive(S))
11418 APInt C = Cst->getAPInt();
11419 return C.urem(M) == 0;
11427 const SCEV *SmodM =
11442 for (
auto *
A : Assumptions)
11443 if (
A->implies(
P, *
this))
11456std::pair<const SCEV *, const SCEV *>
11459 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11461 return { Start, Start };
11463 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11472 getUsedLoops(LHS, LoopsUsed);
11473 getUsedLoops(RHS, LoopsUsed);
11475 if (LoopsUsed.
empty())
11480 for (
const auto *L1 : LoopsUsed)
11481 for (
const auto *L2 : LoopsUsed)
11482 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11483 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11484 "Domination relationship is not a linear order");
11514 SplitRHS.second) &&
11526 if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
11530 return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11540 return std::nullopt;
11555 if (KnownWithoutContext)
11556 return KnownWithoutContext;
11563 return std::nullopt;
11569 const Loop *L = LHS->getLoop();
11574std::optional<ScalarEvolution::MonotonicPredicateType>
11577 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11583 auto ResultSwapped =
11586 assert(*ResultSwapped != *Result &&
11587 "monotonicity should flip as we flip the predicate");
11594std::optional<ScalarEvolution::MonotonicPredicateType>
11595ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11609 return std::nullopt;
11613 "Should be greater or less!");
11617 if (!LHS->hasNoUnsignedWrap())
11618 return std::nullopt;
11622 "Relational predicate is either signed or unsigned!");
11623 if (!
LHS->hasNoSignedWrap())
11624 return std::nullopt;
11626 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11634 return std::nullopt;
11637std::optional<ScalarEvolution::LoopInvariantPredicate>
11644 return std::nullopt;
11651 if (!ArLHS || ArLHS->
getLoop() != L)
11652 return std::nullopt;
11656 return std::nullopt;
11682 return std::nullopt;
11719 return std::nullopt;
11722std::optional<ScalarEvolution::LoopInvariantPredicate>
11727 Pred, LHS, RHS, L, CtxI, MaxIter))
11737 Pred, LHS, RHS, L, CtxI,
Op))
11739 return std::nullopt;
11742std::optional<ScalarEvolution::LoopInvariantPredicate>
11757 return std::nullopt;
11764 if (!AR || AR->
getLoop() != L)
11765 return std::nullopt;
11770 Pred = Pred.dropSameSign();
11774 return std::nullopt;
11780 if (Step != One && Step != MinusOne)
11781 return std::nullopt;
11787 return std::nullopt;
11793 return std::nullopt;
11801 if (Step == MinusOne)
11805 return std::nullopt;
11811bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11817 auto CheckRange = [&](
bool IsSigned) {
11820 return RangeLHS.
icmp(Pred, RangeRHS);
11829 if (CheckRange(
true) || CheckRange(
false))
11838bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11847 SCEVUse XNonConstOp, XConstOp;
11848 SCEVUse YNonConstOp, YConstOp;
11852 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11855 XFlagsPresent = ExpectedFlags;
11860 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11863 YFlagsPresent = ExpectedFlags;
11866 if (YNonConstOp != XNonConstOp)
11874 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11877 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11937bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11958bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11959 const SCEV *
LHS,
const SCEV *
RHS) {
11964 return any_of(*BB, [&](
const Instruction &
I) {
11965 using namespace llvm::PatternMatch;
11970 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11984 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11989 "This cannot be done on broken IR!");
11992 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12001 if (LoopContinuePredicate &&
12002 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
12003 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
12008 if (WalkingBEDominatingConds)
12014 const auto &BETakenInfo = getBackedgeTakenInfo(L);
12015 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
12022 const SCEV *LoopCounter =
12030 for (
auto &AssumeVH : AC.assumptions()) {
12037 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
12041 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
12044 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
12045 DTN != HeaderDTN; DTN = DTN->getIDom()) {
12046 assert(DTN &&
"should reach the loop header before reaching the root!");
12049 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
12067 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
12080 if (!DT.isReachableFromEntry(BB))
12084 "This cannot be done on broken IR!");
12092 const bool ProvingStrictComparison =
12094 bool ProvedNonStrictComparison =
false;
12095 bool ProvedNonEquality =
false;
12098 if (!ProvedNonStrictComparison)
12099 ProvedNonStrictComparison = Fn(NonStrictPredicate);
12100 if (!ProvedNonEquality)
12102 if (ProvedNonStrictComparison && ProvedNonEquality)
12107 if (ProvingStrictComparison) {
12109 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
12111 if (SplitAndProve(ProofFn))
12116 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
12118 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
12120 if (ProvingStrictComparison) {
12122 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
12124 if (SplitAndProve(ProofFn))
12133 const Loop *ContainingLoop = LI.getLoopFor(BB);
12135 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
12139 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
12140 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
12143 if (!BlockEntryPredicate)
12152 for (
auto &AssumeVH : AC.assumptions()) {
12156 if (!DT.dominates(CI, BB))
12159 if (ProveViaCond(CI->getArgOperand(0),
false))
12165 F.getParent(), Intrinsic::experimental_guard);
12167 for (
const auto *GU : GuardDecl->users())
12169 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12170 if (ProveViaCond(Guard->getArgOperand(0),
false))
12185 "LHS is not available at Loop Entry");
12187 "RHS is not available at Loop Entry");
12189 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12200 if (FoundCondValue ==
12204 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12208 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12211 const Value *Op0, *Op1;
12214 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12218 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12219 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12223 if (!ICI)
return false;
12227 CmpPredicate FoundPred;
12236 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12239bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12240 const SCEV *
RHS, CmpPredicate FoundPred,
12241 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12242 const Instruction *CtxI) {
12252 auto *WideType = FoundLHS->
getType();
12264 TruncFoundLHS, TruncFoundRHS, CtxI))
12290 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12294bool ScalarEvolution::isImpliedCondBalancedTypes(
12299 "Types should be balanced!");
12306 if (FoundLHS == FoundRHS)
12310 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12322 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12339 LHS, FoundLHS, FoundRHS, CtxI);
12341 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12363 assert(P1 != P2 &&
"Handled earlier!");
12367 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12371 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12374 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12375 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12376 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12381 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12392 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12393 CanonicalRHS, CanonicalFoundLHS,
12394 CanonicalFoundRHS);
12399 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12400 CanonicalRHS, CanonicalFoundLHS,
12401 CanonicalFoundRHS);
12408 const SCEVConstant *
C =
nullptr;
12409 const SCEV *
V =
nullptr;
12427 if (Min ==
C->getAPInt()) {
12432 APInt SharperMin = Min + 1;
12435 case ICmpInst::ICMP_SGE:
12436 case ICmpInst::ICMP_UGE:
12439 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12444 case ICmpInst::ICMP_SGT:
12445 case ICmpInst::ICMP_UGT:
12455 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12460 case ICmpInst::ICMP_SLE:
12461 case ICmpInst::ICMP_ULE:
12462 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12463 LHS, V, getConstant(SharperMin), CtxI))
12467 case ICmpInst::ICMP_SLT:
12468 case ICmpInst::ICMP_ULT:
12469 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12470 LHS, V, getConstant(Min), CtxI))
12484 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12488 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12491 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12507std::optional<APInt>
12514 APInt DiffMul(BW, 1);
12517 for (
unsigned I = 0;
I < 8; ++
I) {
12526 if (LAR->getLoop() != MAR->getLoop())
12527 return std::nullopt;
12531 if (!LAR->isAffine() || !MAR->isAffine())
12532 return std::nullopt;
12534 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12535 return std::nullopt;
12537 Less = LAR->getStart();
12538 More = MAR->getStart();
12543 auto MatchConstMul =
12544 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12549 return std::nullopt;
12551 if (
auto MatchedMore = MatchConstMul(More)) {
12552 if (
auto MatchedLess = MatchConstMul(
Less)) {
12553 if (MatchedMore->second == MatchedLess->second) {
12554 More = MatchedMore->first;
12555 Less = MatchedLess->first;
12556 DiffMul *= MatchedMore->second;
12567 Diff +=
C->getAPInt() * DiffMul;
12570 Diff -=
C->getAPInt() * DiffMul;
12573 Multiplicity[S] +=
Mul;
12575 auto Decompose = [&](
const SCEV *S,
int Mul) {
12582 Decompose(More, 1);
12583 Decompose(
Less, -1);
12587 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12588 for (
const auto &[S,
Mul] : Multiplicity) {
12593 return std::nullopt;
12595 }
else if (
Mul == -1) {
12597 return std::nullopt;
12600 return std::nullopt;
12604 if (NewMore == More || NewLess ==
Less)
12605 return std::nullopt;
12611 if (!More && !
Less)
12615 if (!More || !
Less)
12616 return std::nullopt;
12620 return std::nullopt;
12623bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12645 const auto *Latch = L->getLoopLatch();
12648 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12657 const auto *Latch = L->getLoopLatch();
12660 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12670bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12673 const SCEV *FoundLHS,
12674 const SCEV *FoundRHS) {
12683 if (!AddRecFoundLHS)
12690 const Loop *
L = AddRecFoundLHS->getLoop();
12691 if (L != AddRecLHS->getLoop())
12730 if (!RDiff || *LDiff != *RDiff)
12733 if (LDiff->isMinValue())
12736 APInt FoundRHSLimit;
12739 FoundRHSLimit = -(*RDiff);
12751bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12752 const SCEV *
RHS,
const SCEV *FoundLHS,
12753 const SCEV *FoundRHS,
unsigned Depth) {
12754 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12758 bool Erased = PendingMerges.erase(LPhi);
12759 assert(Erased &&
"Failed to erase LPhi!");
12763 bool Erased = PendingMerges.erase(RPhi);
12764 assert(Erased &&
"Failed to erase RPhi!");
12772 if (!PendingMerges.insert(Phi).second)
12786 if (!PendingMerges.insert(Phi).second)
12792 if (!LPhi && !RPhi)
12803 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12807 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12808 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12809 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12810 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12813 if (RPhi && RPhi->getParent() == LBB) {
12820 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12821 if (!ProvedEasily(L, R))
12832 auto *RLoop = RAR->
getLoop();
12833 auto *Predecessor = RLoop->getLoopPredecessor();
12834 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12836 if (!ProvedEasily(L1, RAR->
getStart()))
12838 auto *Latch = RLoop->getLoopLatch();
12839 assert(Latch &&
"Loop with AddRec with no latch?");
12860 if (
auto *Loop = LI.getLoopFor(LBB))
12863 if (!ProvedEasily(L,
RHS))
12870bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12873 const SCEV *FoundLHS,
12874 const SCEV *FoundRHS) {
12877 if (
RHS == FoundRHS) {
12882 if (
LHS != FoundLHS)
12889 Value *Shiftee, *ShiftValue;
12891 using namespace PatternMatch;
12892 if (
match(SUFoundRHS->getValue(),
12894 auto *ShifteeS =
getSCEV(Shiftee);
12912bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12913 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12914 const SCEV *FoundRHS) {
12946 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12954 return Diff == FoundDiff;
12957bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12959 const SCEV *FoundLHS,
12960 const SCEV *FoundRHS,
12961 const Instruction *CtxI) {
12962 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12964 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12966 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12967 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12969 isImpliedCondOperandsViaMatchingDiff(Pred,
LHS,
RHS, FoundLHS,
12971 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12975template <
typename MinMaxExprType>
12977 const SCEV *Candidate) {
12982 return is_contained(MinMaxExpr->operands(), Candidate);
12995 const SCEV *LStart, *RStart, *Step;
13068bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
13070 const SCEV *FoundLHS,
13071 const SCEV *FoundRHS,
13075 "LHS and RHS have different sizes?");
13078 "FoundLHS and FoundRHS have different sizes?");
13112 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
13114 return Ext->getOperand();
13121 auto *OrigLHS =
LHS;
13122 auto *OrigFoundLHS = FoundLHS;
13123 LHS = GetOpFromSExt(
LHS);
13124 FoundLHS = GetOpFromSExt(FoundLHS);
13127 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
13130 FoundRHS,
Depth + 1);
13143 if (!LHSAddExpr->hasNoSignedWrap())
13146 SCEVUse LL = LHSAddExpr->getOperand(0);
13147 SCEVUse LR = LHSAddExpr->getOperand(1);
13151 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
13152 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
13157 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
13163 using namespace llvm::PatternMatch;
13182 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13190 auto *DTy = Denominator->getType();
13191 auto *FRHSTy = FoundRHS->
getType();
13192 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13211 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13222 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13224 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13232 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13265bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13269 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13272 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13275bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13278 const SCEV *FoundLHS,
13279 const SCEV *FoundRHS) {
13315 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13321bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13322 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13323 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13337 ConstantRange FoundLHSRange =
13341 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13348 return LHSRange.
icmp(Pred, ConstRHS);
13351bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13364 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13372 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13375bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
13387 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
13395 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
13407const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
13408 const SCEV *Stride,
13439 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13450 :
APIntOps::umax(MaxEnd, MinStart);
13457ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13458 const Loop *L,
bool IsSigned,
13459 bool ControlsOnlyExit,
bool AllowPredicates) {
13463 bool PredicatedIV =
false;
13468 auto canProveNUW = [&]() {
13471 if (!ControlsOnlyExit)
13492 Limit = Limit.
zext(OuterBitWidth);
13504 Type *Ty = ZExt->getType();
13515 if (!
IV && AllowPredicates) {
13520 PredicatedIV =
true;
13524 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13538 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13541 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13546 if (!PositiveStride) {
13598 auto wouldZeroStrideBeUB = [&]() {
13610 if (!wouldZeroStrideBeUB()) {
13614 }
else if (!NoWrap) {
13617 if (canIVOverflowOnLT(
RHS, Stride, IsSigned))
13630 const SCEV *
Start =
IV->getStart();
13636 const SCEV *OrigStart =
Start;
13637 const SCEV *OrigRHS =
RHS;
13638 if (
Start->getType()->isPointerTy()) {
13649 const SCEV *End =
nullptr, *BECount =
nullptr,
13650 *BECountIfBackedgeTaken =
nullptr;
13653 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13654 any(RHSAddRec->getNoWrapFlags())) {
13667 const SCEV *RHSStart = RHSAddRec->getStart();
13668 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13680 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13689 BECountIfBackedgeTaken =
13694 if (BECount ==
nullptr) {
13699 const SCEV *MaxBECount = computeMaxBECountForLT(
13702 MaxBECount,
false , Predicates);
13709 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13736 const SCEV *Numerator =
13742 auto canProveRHSGreaterThanEqualStart = [&]() {
13761 auto *StartMinusOne =
13768 if (canProveRHSGreaterThanEqualStart()) {
13783 BECountIfBackedgeTaken =
13799 bool MayAddOverflow = [&] {
13845 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13859 if (!MayAddOverflow) {
13871 const SCEV *ConstantMaxBECount;
13872 bool MaxOrZero =
false;
13874 ConstantMaxBECount = BECount;
13875 }
else if (BECountIfBackedgeTaken &&
13880 ConstantMaxBECount = BECountIfBackedgeTaken;
13883 ConstantMaxBECount = computeMaxBECountForLT(
13891 const SCEV *SymbolicMaxBECount =
13893 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13897ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13898 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13899 bool ControlsOnlyExit,
bool AllowPredicates) {
13906 if (!
IV && AllowPredicates)
13913 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13917 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13930 if (!Stride->
isOne() && !NoWrap)
13931 if (canIVOverflowOnGT(
RHS, Stride, IsSigned))
13934 const SCEV *
Start =
IV->getStart();
13935 const SCEV *End =
RHS;
13946 if (
Start->getType()->isPointerTy()) {
13981 const SCEV *ConstantMaxBECount =
13988 ConstantMaxBECount = BECount;
13989 const SCEV *SymbolicMaxBECount =
13992 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13998 if (
Range.isFullSet())
14003 if (!SC->getValue()->isZero()) {
14009 return ShiftedAddRec->getNumIterationsInRange(
14010 Range.subtract(SC->getAPInt()), SE);
14041 APInt ExitVal = (End +
A).udiv(
A);
14054 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
14055 "Linear scev computation is off in a bad way!");
14086 assert(!
Last->isZero() &&
"Recurrency with zero step?");
14111 Ty =
Store->getValueOperand()->getType();
14113 Ty =
Load->getType();
14126 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14128 SE->ConstantEvolutionLoopExitValue.erase(PN);
14129 SE->eraseValueFromMap(getValPtr());
14133void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
14134 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14144 : CallbackVH(
V), SE(se) {}
14153 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
14155 LoopDispositions(64), BlockDispositions(64) {
14167 F.getParent(), Intrinsic::experimental_guard);
14168 HasGuards = GuardDecl && !GuardDecl->use_empty();
14172 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
14173 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14174 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14175 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14176 PendingMerges(
std::
move(Arg.PendingMerges)),
14177 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14178 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14179 PredicatedBackedgeTakenCounts(
14180 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14181 BECountUsers(
std::
move(Arg.BECountUsers)),
14182 ConstantEvolutionLoopExitValue(
14183 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14184 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14185 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14186 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14187 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14188 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14189 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14190 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14191 SignedRanges(
std::
move(Arg.SignedRanges)),
14192 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14193 UniquePreds(
std::
move(Arg.UniquePreds)),
14194 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14195 LoopUsers(
std::
move(Arg.LoopUsers)),
14196 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14197 FirstUnknown(Arg.FirstUnknown) {
14198 Arg.FirstUnknown =
nullptr;
14207 Tmp->~SCEVUnknown();
14209 FirstUnknown =
nullptr;
14211 ExprValueMap.clear();
14212 ValueExprMap.clear();
14214 BackedgeTakenCounts.clear();
14215 PredicatedBackedgeTakenCounts.clear();
14217 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14218 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14219 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14220 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14242 L->getHeader()->printAsOperand(OS,
false);
14246 L->getExitingBlocks(ExitingBlocks);
14247 if (ExitingBlocks.
size() != 1)
14248 OS <<
"<multiple exits> ";
14252 OS <<
"backedge-taken count is ";
14255 OS <<
"Unpredictable backedge-taken count.";
14258 if (ExitingBlocks.
size() > 1)
14259 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14260 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14268 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14271 OS <<
"\n Predicates:\n";
14272 for (
const auto *
P : Predicates)
14280 L->getHeader()->printAsOperand(OS,
false);
14285 OS <<
"constant max backedge-taken count is ";
14288 OS <<
", actual taken count either this or zero.";
14290 OS <<
"Unpredictable constant max backedge-taken count. ";
14295 L->getHeader()->printAsOperand(OS,
false);
14300 OS <<
"symbolic max backedge-taken count is ";
14303 OS <<
", actual taken count either this or zero.";
14305 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14309 if (ExitingBlocks.
size() > 1)
14310 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14311 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14321 OS <<
"\n predicated symbolic max exit count for "
14322 << ExitingBlock->
getName() <<
": ";
14324 OS <<
"\n Predicates:\n";
14325 for (
const auto *
P : Predicates)
14336 L->getHeader()->printAsOperand(OS,
false);
14339 OS <<
"Predicated backedge-taken count is ";
14342 OS <<
"Unpredictable predicated backedge-taken count.";
14344 OS <<
" Predicates:\n";
14345 for (
const auto *
P : Preds)
14350 auto *PredConstantMax =
14352 if (PredConstantMax != ConstantBTC) {
14354 L->getHeader()->printAsOperand(OS,
false);
14357 OS <<
"Predicated constant max backedge-taken count is ";
14360 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14362 OS <<
" Predicates:\n";
14363 for (
const auto *
P : Preds)
14368 auto *PredSymbolicMax =
14370 if (SymbolicBTC != PredSymbolicMax) {
14372 L->getHeader()->printAsOperand(OS,
false);
14375 OS <<
"Predicated symbolic max backedge-taken count is ";
14378 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14380 OS <<
" Predicates:\n";
14381 for (
const auto *
P : Preds)
14387 L->getHeader()->printAsOperand(OS,
false);
14414 OS <<
"Computable";
14424 OS <<
"DoesNotDominate";
14430 OS <<
"ProperlyDominates";
14447 OS <<
"Classifying expressions for: ";
14448 F.printAsOperand(OS,
false);
14463 const Loop *L = LI.getLoopFor(
I.getParent());
14478 OS <<
"\t\t" "Exits: ";
14481 OS <<
"<<Unknown>>";
14487 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14489 Iter->getHeader()->printAsOperand(OS,
false);
14497 InnerL->getHeader()->printAsOperand(OS,
false);
14508 OS <<
"Determining loop execution counts for: ";
14509 F.printAsOperand(OS,
false);
14517 auto &
Values = LoopDispositions[S];
14518 for (
auto &V :
Values) {
14519 if (V.getPointer() == L)
14524 auto &Values2 = LoopDispositions[S];
14526 if (V.getPointer() == L) {
14535ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14553 if (L->contains(AR->
getLoop()) &&
14555 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14560 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14561 " dominate the contained loop's header?");
14589 bool HasVarying =
false;
14590 bool HasUniform =
false;
14632 auto &
Values = BlockDispositions[S];
14633 for (
auto &V :
Values) {
14634 if (V.getPointer() == BB)
14639 auto &Values2 = BlockDispositions[S];
14641 if (V.getPointer() == BB) {
14650ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14680 bool Proper =
true;
14691 if (Instruction *
I =
14693 if (
I->getParent() == BB)
14695 if (DT.properlyDominates(
I->getParent(), BB))
14718void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14721 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14722 auto It = BECounts.find(L);
14723 if (It != BECounts.end()) {
14724 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14725 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14727 auto UserIt = BECountUsers.find(S);
14728 assert(UserIt != BECountUsers.end());
14733 BECounts.erase(It);
14741 while (!Worklist.
empty()) {
14743 auto Users = SCEVUsers.find(Curr);
14744 if (
Users != SCEVUsers.end())
14745 for (
const auto *User :
Users->second)
14746 if (ToForget.
insert(User).second)
14750 for (
const auto *S : ToForget)
14751 forgetMemoizedResultsImpl(S);
14753 PredicatedSCEVRewrites.remove_if(
14754 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14757void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14758 LoopDispositions.erase(S);
14759 BlockDispositions.erase(S);
14760 UnsignedRanges.erase(S);
14761 SignedRanges.erase(S);
14762 HasRecMap.erase(S);
14763 ConstantMultipleCache.erase(S);
14766 UnsignedWrapViaInductionTried.erase(AR);
14767 SignedWrapViaInductionTried.erase(AR);
14770 auto ExprIt = ExprValueMap.find(S);
14771 if (ExprIt != ExprValueMap.end()) {
14772 for (
Value *V : ExprIt->second) {
14773 auto ValueIt = ValueExprMap.find_as(V);
14774 if (ValueIt != ValueExprMap.end())
14775 ValueExprMap.erase(ValueIt);
14777 ExprValueMap.erase(ExprIt);
14780 auto ScopeIt = ValuesAtScopes.find(S);
14781 if (ScopeIt != ValuesAtScopes.end()) {
14782 for (
const auto &Pair : ScopeIt->second)
14785 std::make_pair(Pair.first, S));
14786 ValuesAtScopes.erase(ScopeIt);
14789 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14790 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14791 for (
const auto &Pair : ScopeUserIt->second)
14792 llvm::erase(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
14793 ValuesAtScopesUsers.erase(ScopeUserIt);
14796 auto BEUsersIt = BECountUsers.find(S);
14797 if (BEUsersIt != BECountUsers.end()) {
14799 auto Copy = BEUsersIt->second;
14800 for (
const auto &Pair : Copy)
14801 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14802 BECountUsers.erase(BEUsersIt);
14805 auto FoldUser = FoldCacheUser.find(S);
14806 if (FoldUser != FoldCacheUser.end())
14807 for (
auto &KV : FoldUser->second)
14808 FoldCache.erase(KV);
14809 FoldCacheUser.erase(S);
14813ScalarEvolution::getUsedLoops(
const SCEV *S,
14815 struct FindUsedLoops {
14816 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14817 : LoopsUsed(LoopsUsed) {}
14818 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14819 bool follow(
const SCEV *S) {
14825 bool isDone()
const {
return false; }
14828 FindUsedLoops
F(LoopsUsed);
14829 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14832void ScalarEvolution::getReachableBlocks(
14835 Worklist.
push_back(&F.getEntryBlock());
14836 while (!Worklist.
empty()) {
14838 if (!Reachable.
insert(BB).second)
14846 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14853 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14857 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14892 SCEVMapper SCM(SE2);
14894 SE2.getReachableBlocks(ReachableBlocks, F);
14896 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14914 while (!LoopStack.
empty()) {
14920 if (!ReachableBlocks.
contains(L->getHeader()))
14925 auto It = BackedgeTakenCounts.find(L);
14926 if (It == BackedgeTakenCounts.end())
14930 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14950 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14951 if (Delta && !Delta->
isZero()) {
14952 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14953 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14954 dbgs() <<
"New: " << *NewBECount <<
"\n";
14955 dbgs() <<
"Delta: " << *Delta <<
"\n";
14963 while (!Worklist.
empty()) {
14965 if (ValidLoops.
insert(L).second)
14966 Worklist.
append(L->begin(), L->end());
14968 for (
const auto &KV : ValueExprMap) {
14973 "AddRec references invalid loop");
14978 auto It = ExprValueMap.find(KV.second);
14979 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14980 dbgs() <<
"Value " << *KV.first
14981 <<
" is in ValueExprMap but not in ExprValueMap\n";
14986 if (!ReachableBlocks.
contains(
I->getParent()))
14988 const SCEV *OldSCEV = SCM.visit(KV.second);
14990 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14991 if (Delta && !Delta->
isZero()) {
14992 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14993 <<
"Old: " << *OldSCEV <<
"\n"
14994 <<
"New: " << *NewSCEV <<
"\n"
14995 <<
"Delta: " << *Delta <<
"\n";
15001 for (
const auto &KV : ExprValueMap) {
15002 for (
Value *V : KV.second) {
15003 const SCEV *S = ValueExprMap.lookup(V);
15005 dbgs() <<
"Value " << *V
15006 <<
" is in ExprValueMap but not in ValueExprMap\n";
15009 if (S != KV.first) {
15010 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
15011 << *KV.first <<
"\n";
15018 for (
const auto &S : UniqueSCEVs) {
15023 auto It = SCEVUsers.find(
Op);
15024 if (It != SCEVUsers.end() && It->second.count(&S))
15026 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
15027 <<
" is not being tracked!\n";
15033 for (
const auto &ValueAndVec : ValuesAtScopes) {
15035 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
15036 const Loop *L = LoopAndValueAtScope.first;
15037 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
15039 auto It = ValuesAtScopesUsers.find(ValueAtScope);
15040 if (It != ValuesAtScopesUsers.end() &&
15043 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
15044 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
15050 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
15051 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
15052 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
15053 const Loop *L = LoopAndValue.first;
15054 const SCEV *
Value = LoopAndValue.second;
15056 auto It = ValuesAtScopes.find(
Value);
15057 if (It != ValuesAtScopes.end() &&
15058 is_contained(It->second, std::make_pair(L, ValueAtScope)))
15060 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
15061 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
15067 auto VerifyBECountUsers = [&](
bool Predicated) {
15069 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
15070 for (
const auto &LoopAndBEInfo : BECounts) {
15071 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
15072 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
15074 auto UserIt = BECountUsers.find(S);
15075 if (UserIt != BECountUsers.end() &&
15076 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
15078 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
15079 <<
" missing from BECountUsers\n";
15086 VerifyBECountUsers(
false);
15087 VerifyBECountUsers(
true);
15090 for (
auto &[S,
Values] : LoopDispositions) {
15091 for (
auto [
Loop, CachedDisposition] :
Values) {
15093 if (CachedDisposition != RecomputedDisposition) {
15094 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
15095 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
15096 << RecomputedDisposition <<
"\n";
15103 for (
auto &[S,
Values] : BlockDispositions) {
15104 for (
auto [BB, CachedDisposition] :
Values) {
15106 if (CachedDisposition != RecomputedDisposition) {
15107 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
15108 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
15109 <<
", actual " << RecomputedDisposition <<
"\n";
15116 for (
auto [
FoldID, Expr] : FoldCache) {
15117 auto I = FoldCacheUser.find(Expr);
15118 if (
I == FoldCacheUser.end()) {
15119 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
15124 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
15128 for (
auto [Expr, IDs] : FoldCacheUser) {
15129 for (
auto &
FoldID : IDs) {
15132 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
15137 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
15138 <<
" != " << *Expr <<
"!\n";
15149 for (
auto [S, Multiple] : ConstantMultipleCache) {
15151 if ((Multiple != 0 && RecomputedMultiple != 0 &&
15152 Multiple.
urem(RecomputedMultiple) != 0 &&
15153 RecomputedMultiple.
urem(Multiple) != 0)) {
15154 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
15155 << *S <<
" : Computed " << RecomputedMultiple
15156 <<
" but cache contains " << Multiple <<
"!\n";
15164 FunctionAnalysisManager::Invalidator &Inv) {
15196 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15197 <<
F.getName() <<
"':\n";
15203 "Scalar Evolution Analysis",
false,
true)
15252 const SCEV *LHS,
const SCEV *RHS) {
15254 assert(LHS->getType() == RHS->getType() &&
15255 "Type mismatch between LHS and RHS");
15258 ID.AddInteger(Pred);
15259 ID.AddPointer(LHS);
15260 ID.AddPointer(RHS);
15261 void *IP =
nullptr;
15262 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
15266 UniquePreds.InsertNode(Eq, IP);
15277 ID.AddInteger(AddedFlags);
15278 void *IP =
nullptr;
15279 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
15281 auto *OF =
new (SCEVAllocator)
15283 UniquePreds.InsertNode(OF, IP);
15303 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15304 return Rewriter.visit(S);
15310 for (
const auto *Pred : U->getPredicates())
15312 if (IPred->getLHS() == Expr &&
15314 return IPred->getRHS();
15316 if (IPred->getLHS() == Expr &&
15317 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15318 return IPred->getRHS();
15321 return convertToAddRecWithPreds(Expr);
15324 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15340 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15357 explicit SCEVPredicateRewriter(
15358 const Loop *L, ScalarEvolution &SE,
15359 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15360 const SCEVPredicate *Pred)
15361 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15363 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15366 return Pred && Pred->
implies(
P, SE);
15372 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15375 return addOverflowAssumption(
A);
15384 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15388 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15390 if (!PredicatedRewrite)
15392 for (
const auto *
P : PredicatedRewrite->second){
15395 if (L != WP->getExpr()->getLoop())
15398 if (!addOverflowAssumption(
P))
15401 return PredicatedRewrite->first;
15404 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15405 const SCEVPredicate *Pred;
15414 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15421 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15441 if (!Step->
isOne())
15466 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15467 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15480 return Op->LHS == LHS &&
Op->RHS == RHS;
15487 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15489 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15514 const SCEV *Start = AR->getStart();
15515 const SCEV *OpStart =
Op->AR->getStart();
15520 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15529 const SCEV *Step = AR->getStepRecurrence(SE);
15530 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15583 if (Step->getValue()->getValue().isNonNegative())
15587 return ImpliedFlags;
15594 for (
const auto *
P : Preds)
15607 return this->implies(I, SE);
15619 const Loop *L = NWrap->getExpr()->getLoop();
15626 return RewrittenAR &&
15632 for (
const auto *Pred : Preds)
15633 Pred->print(OS,
Depth);
15638 for (
const auto *Pred : Set->Preds)
15646 bool CheckImplies = Preds.
size() < 16;
15649 if (CheckImplies &&
implies(
N, SE))
15655 for (
auto *
P : Preds) {
15656 if (CheckImplies &&
N->implies(
P, SE))
15660 Preds = std::move(PrunedPreds);
15661 Preds.push_back(
N);
15668 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15673 for (
const auto *
Op :
Ops)
15678 SCEVUsers[
Op].insert(
User);
15687 SCEVUsers[
Op].insert(
User);
15691 const SCEV *Expr = SE.getSCEV(V);
15696 RewriteEntry &Entry = RewriteMap[Expr];
15699 if (Entry.second && Generation == Entry.first)
15700 return Entry.second;
15705 Expr = Entry.second;
15707 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15708 Entry = {Generation, NewSCEV};
15714 if (!BackedgeCount) {
15716 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15717 for (
const auto *
P : Preds)
15720 return BackedgeCount;
15724 if (!SymbolicMaxBackedgeCount) {
15726 SymbolicMaxBackedgeCount =
15727 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15728 for (
const auto *
P : Preds)
15731 return SymbolicMaxBackedgeCount;
15735 if (!SmallConstantMaxTripCount) {
15737 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15738 for (
const auto *
P : Preds)
15741 return *SmallConstantMaxTripCount;
15745 if (Preds->implies(&Pred, SE))
15750 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15751 updateGeneration();
15764void PredicatedScalarEvolution::updateGeneration() {
15766 if (++Generation == 0) {
15767 for (
auto &
II : RewriteMap) {
15768 const SCEV *Rewritten =
II.second.second;
15790 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15796 ExtraPreds->
append(NewPreds);
15802 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15808 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15811 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15815 for (
auto *BB : L.getBlocks())
15816 for (
auto &
I : *BB) {
15817 if (!SE.isSCEVable(
I.getType()))
15820 auto *Expr = SE.getSCEV(&
I);
15821 auto II = RewriteMap.find(Expr);
15823 if (
II == RewriteMap.end())
15827 if (
II->second.second == Expr)
15832 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15840 LoopGuards Guards(SE);
15848void ScalarEvolution::LoopGuards::collectFromPHI(
15856 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15857 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15871 auto &RewriteMap =
G->second.RewriteMap;
15872 if (RewriteMap.empty())
15874 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15875 if (S == RewriteMap.end())
15881 return {C0,
SM->getSCEVType()};
15884 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15885 MinMaxPattern
P2) -> MinMaxPattern {
15886 auto [C1,
T1] =
P1;
15887 auto [C2, T2] =
P2;
15888 if (!C1 || !C2 ||
T1 != T2)
15892 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15894 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15896 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15898 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15903 auto P = GetMinMaxConst(0);
15904 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15907 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15910 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15913 Guards.RewriteMap.insert({
LHS,
RHS});
15921 const APInt &DivisorVal,
15923 const APInt *ExprVal;
15936 const APInt &DivisorVal,
15938 const APInt *ExprVal;
15946 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15960 const SCEV *URemRHS =
nullptr;
15964 const SCEV *Multiple =
15966 DivInfo[URemLHS] = Multiple;
15968 Multiples[URemLHS] =
C->getAPInt();
15988 auto IsMinMaxSCEVWithNonNegativeConstant =
15992 if (
MinMax->getNumOperands() != 2)
15995 if (
C->getAPInt().isNegative())
15997 SCTy =
MinMax->getSCEVType();
16006 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
16008 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
16013 auto *DivisibleExpr =
16021void ScalarEvolution::LoopGuards::collectFromBlock(
16023 const BasicBlock *
Block,
const BasicBlock *Pred,
16031 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
16042 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
16044 if (From == FromRewritten)
16046 RewriteMap[From] = To;
16052 auto GetMaybeRewritten = [&](
const SCEV *S) {
16053 return RewriteMap.lookup_or(S, S);
16060 const SCEV *MatchLHS,
16061 const SCEV *MatchRHS) {
16062 const SCEVConstant *C1;
16065 if (!
match(MatchLHS,
16075 if (ExactRegion.isWrappedSet() || ExactRegion.isFullSet())
16077 const SCEV *RewrittenLHS = GetMaybeRewritten(LHSUnknown);
16078 const SCEV *RegionMin = SE.
getConstant(ExactRegion.getUnsignedMin());
16079 const SCEV *RegionMax = SE.
getConstant(ExactRegion.getUnsignedMax());
16080 const SCEV *ClampedLHS =
16082 AddRewrite(LHSUnknown, RewrittenLHS, ClampedLHS);
16085 if (MatchRangeCheckIdiom(Predicate,
LHS,
RHS))
16098 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
16100 const APInt &DividesBy =
16115 switch (Predicate) {
16144 SmallPtrSet<const SCEV *, 16> Visited;
16146 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
16150 while (!Worklist.
empty()) {
16154 if (!Visited.
insert(From).second)
16156 const SCEV *FromRewritten = GetMaybeRewritten(From);
16157 const SCEV *To =
nullptr;
16159 switch (Predicate) {
16164 EnqueueOperands(
UMax);
16170 EnqueueOperands(
SMax);
16176 EnqueueOperands(
UMin);
16182 EnqueueOperands(
SMin);
16190 const SCEV *OneAlignedUp =
16192 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16204 const SCEVConstant *
C;
16213 Guards.NotEqual.insert({
LHS,
RHS});
16222 AddRewrite(From, FromRewritten, To);
16239 SE.F.
getParent(), Intrinsic::experimental_guard);
16241 for (
const auto *GU : GuardDecl->users())
16243 if (Guard->getFunction() ==
Block->getParent() &&
16252 unsigned NumCollectedConditions = 0;
16254 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16256 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16258 const CondBrInst *LoopEntryPredicate =
16260 if (!LoopEntryPredicate)
16265 NumCollectedConditions++;
16269 if (
Depth > 0 && NumCollectedConditions == 2)
16277 if (Pair.second->hasNPredecessorsOrMore(2) &&
16279 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16280 for (
auto &Phi : Pair.second->phis())
16291 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16292 SmallVector<Value *, 8> Worklist;
16293 SmallPtrSet<Value *, 8> Visited;
16295 while (!Worklist.
empty()) {
16302 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16326 DenseMap<const SCEV *, APInt> Multiples;
16328 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16335 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16336 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16340 for (
const auto &[K, Divisor] : Multiples) {
16341 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16342 Guards.RewriteMap[
K] =
16344 Guards.
rewrite(K), Divisor, SE),
16353 Guards.PreserveNUW =
true;
16354 Guards.PreserveNSW =
true;
16355 for (
const SCEV *Expr : ExprsToRewrite) {
16356 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16357 Guards.PreserveNUW &=
16359 Guards.PreserveNSW &=
16366 if (ExprsToRewrite.size() > 1) {
16367 for (
const SCEV *Expr : ExprsToRewrite) {
16368 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16369 Guards.RewriteMap.erase(Expr);
16370 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16379 class SCEVLoopGuardRewriter
16390 NotEqual(Guards.NotEqual) {
16391 if (Guards.PreserveNUW)
16393 if (Guards.PreserveNSW)
16400 return Map.lookup_or(Expr, Expr);
16404 if (
const SCEV *S = Map.lookup(Expr))
16411 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16412 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16413 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16415 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16416 if (
const SCEV *S = Map.lookup(NarrowExt))
16417 return SE.getZeroExtendExpr(S, Ty);
16418 Bitwidth = Bitwidth / 2;
16426 if (
const SCEV *S = Map.lookup(Expr))
16433 if (
const SCEV *S = Map.lookup(Expr))
16439 if (
const SCEV *S = Map.lookup(Expr))
16447 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16452 if (NotEqual.contains({LHS, RHS})) {
16454 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16455 return SE.getUMaxExpr(OneAlignedUp, S);
16462 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16473 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16474 return SE.getAddExpr(
16477 if (
const SCEV *S = Map.lookup(
Add))
16478 return SE.getAddExpr(Expr->
getOperand(0), S);
16490 : SE.getAddExpr(Operands,
16506 : SE.getMulExpr(Operands,
16512 if (RewriteMap.empty() && NotEqual.empty())
16515 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16516 return Rewriter.visit(Expr);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Expand Atomic instructions
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
static bool isSigned(unsigned Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
Value * getPointer(Value *Ptr)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This defines the Use class.
iv Induction Variable Users
static constexpr Value * getValue(Ty &ValueOrUse)
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
MachineInstr unsigned OpIdx
static constexpr unsigned SM(unsigned Version)
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
PowerPC Reduce CR logical Operation
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
const SmallVectorImpl< MachineOperand > & Cond
static DominatorTree getDomTree(Function &F)
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
SI optimize exec mask operations pre RA
static void visit(BasicBlock &Start, std::function< bool(BasicBlock *)> op)
This file provides utility classes that use RAII to save and restore values.
bool SCEVMinMaxExprContains(const SCEV *Root, const SCEV *OperandToFind, SCEVTypes RootKind)
static cl::opt< unsigned > MaxAddRecSize("scalar-evolution-max-add-rec-size", cl::Hidden, cl::desc("Max coefficients in AddRec during evolving"), cl::init(8))
static cl::opt< unsigned > RangeIterThreshold("scev-range-iter-threshold", cl::Hidden, cl::desc("Threshold for switching to iteratively computing SCEV ranges"), cl::init(32))
static const Loop * isIntegerLoopHeaderPHI(const PHINode *PN, LoopInfo &LI)
static unsigned getConstantTripCount(const SCEVConstant *ExitCount)
static int CompareValueComplexity(const LoopInfo *const LI, Value *LV, Value *RV, unsigned Depth)
Compare the two values LV and RV in terms of their "complexity" where "complexity" is a partial (and ...
static const SCEV * getNextSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static void insertFoldCacheEntry(const ScalarEvolution::FoldID &ID, const SCEV *S, DenseMap< ScalarEvolution::FoldID, const SCEV * > &FoldCache, DenseMap< const SCEV *, SmallVector< ScalarEvolution::FoldID, 2 > > &FoldCacheUser)
static cl::opt< bool > ClassifyExpressions("scalar-evolution-classify-expressions", cl::Hidden, cl::init(true), cl::desc("When printing analysis, include information on every instruction"))
static bool hasHugeExpression(ArrayRef< SCEVUse > Ops)
Returns true if Ops contains a huge SCEV (the subtree of S contains at least HugeExprThreshold nodes)...
static bool CanConstantFold(const Instruction *I)
Return true if we can constant fold an instruction of the specified type, assuming that all operands ...
static cl::opt< unsigned > AddOpsInlineThreshold("scev-addops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining addition operands into a SCEV"), cl::init(500))
static cl::opt< unsigned > MaxLoopGuardCollectionDepth("scalar-evolution-max-loop-guard-collection-depth", cl::Hidden, cl::desc("Maximum depth for recursive loop guard collection"), cl::init(1))
static cl::opt< bool > VerifyIR("scev-verify-ir", cl::Hidden, cl::desc("Verify IR correctness when making sensitive SCEV queries (slow)"), cl::init(false))
static bool RangeRefPHIAllowedOperands(DominatorTree &DT, PHINode *PHI)
static const SCEV * getPreStartForExtend(const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE, unsigned Depth)
static std::optional< APInt > MinOptional(std::optional< APInt > X, std::optional< APInt > Y)
Helper function to compare optional APInts: (a) if X and Y both exist, return min(X,...
static cl::opt< unsigned > MulOpsInlineThreshold("scev-mulops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining multiplication operands into a SCEV"), cl::init(32))
static BinaryOperator * getCommonInstForPHI(PHINode *PN)
static bool isDivisibilityGuard(const SCEV *LHS, const SCEV *RHS, ScalarEvolution &SE)
static std::optional< const SCEV * > createNodeForSelectViaUMinSeq(ScalarEvolution *SE, const SCEV *CondExpr, const SCEV *TrueExpr, const SCEV *FalseExpr)
static Constant * BuildConstantFromSCEV(const SCEV *V)
This builds up a Constant using the ConstantExpr interface.
static ConstantInt * EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C, ScalarEvolution &SE)
static const SCEV * BinomialCoefficient(const SCEV *It, unsigned K, ScalarEvolution &SE, Type *ResultTy)
Compute BC(It, K). The result has width W. Assume, K > 0.
static cl::opt< unsigned > MaxCastDepth("scalar-evolution-max-cast-depth", cl::Hidden, cl::desc("Maximum depth of recursive SExt/ZExt/Trunc"), cl::init(8))
static bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr, const SCEV *Candidate)
Is MaybeMinMaxExpr an (U|S)(Min|Max) of Candidate and some other values?
static PHINode * getConstantEvolvingPHI(Value *V, const Loop *L)
getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node in the loop that V is deri...
static const SCEV * SolveLinEquationWithOverflow(const APInt &A, const SCEV *B, SmallVectorImpl< const SCEVPredicate * > *Predicates, ScalarEvolution &SE, const Loop *L)
Finds the minimum unsigned root of the following equation:
static cl::opt< unsigned > MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, cl::desc("Maximum number of iterations SCEV will " "symbolically execute a constant " "derived loop"), cl::init(100))
static uint64_t umul_ov(uint64_t i, uint64_t j, bool &Overflow)
static void PrintSCEVWithTypeHint(raw_ostream &OS, const SCEV *S)
When printing a top-level SCEV for trip counts, it's helpful to include a type for constants which ar...
static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE, const Loop *L)
static SCEV::NoWrapFlags StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, ArrayRef< SCEVUse > Ops, SCEV::NoWrapFlags Flags)
static bool containsConstantInAddMulChain(const SCEV *StartExpr)
Determine if any of the operands in this SCEV are a constant or if any of the add or multiply express...
static const SCEV * getExtendAddRecStart(const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE, unsigned Depth)
static bool CollectAddOperandsWithScales(SmallDenseMap< SCEVUse, APInt, 16 > &M, SmallVectorImpl< SCEVUse > &NewOps, APInt &AccumulatedConstant, ArrayRef< SCEVUse > Ops, const APInt &Scale, ScalarEvolution &SE)
Process the given Ops list, which is a list of operands to be added under the given scale,...
static const SCEV * constantFoldAndGroupOps(ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT, SmallVectorImpl< SCEVUse > &Ops, FoldT Fold, IsIdentityT IsIdentity, IsAbsorberT IsAbsorber)
Performs a number of common optimizations on the passed Ops.
static cl::opt< unsigned > MaxPhiSCCAnalysisSize("scalar-evolution-max-scc-analysis-depth", cl::Hidden, cl::desc("Maximum amount of nodes to process while searching SCEVUnknown " "Phi strongly connected components"), cl::init(8))
static bool IsKnownPredicateViaAddRecStart(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
static void GroupByComplexity(SmallVectorImpl< SCEVUse > &Ops, LoopInfo *LI, DominatorTree &DT)
Given a list of SCEV objects, order them by their complexity, and group objects of the same complexit...
static bool collectDivisibilityInformation(ICmpInst::Predicate Predicate, const SCEV *LHS, const SCEV *RHS, DenseMap< const SCEV *, const SCEV * > &DivInfo, DenseMap< const SCEV *, APInt > &Multiples, ScalarEvolution &SE)
static cl::opt< unsigned > MaxSCEVOperationsImplicationDepth("scalar-evolution-max-scev-operations-implication-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV operations implication analysis"), cl::init(2))
static void PushDefUseChildren(Instruction *I, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push users of the given Instruction onto the given Worklist.
static std::optional< APInt > SolveQuadraticAddRecRange(const SCEVAddRecExpr *AddRec, const ConstantRange &Range, ScalarEvolution &SE)
Let c(n) be the value of the quadratic chrec {0,+,M,+,N} after n iterations.
static cl::opt< bool > UseContextForNoWrapFlagInference("scalar-evolution-use-context-for-no-wrap-flag-strenghening", cl::Hidden, cl::desc("Infer nuw/nsw flags using context where suitable"), cl::init(true))
static cl::opt< bool > EnableFiniteLoopControl("scalar-evolution-finite-loop", cl::Hidden, cl::desc("Handle <= and >= in finite loops"), cl::init(true))
static bool getOperandsForSelectLikePHI(DominatorTree &DT, PHINode *PN, Value *&Cond, Value *&LHS, Value *&RHS)
static std::optional< std::tuple< APInt, APInt, APInt, APInt, unsigned > > GetQuadraticEquation(const SCEVAddRecExpr *AddRec)
For a given quadratic addrec, generate coefficients of the corresponding quadratic equation,...
static bool isKnownPredicateExtendIdiom(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
static std::optional< BinaryOp > MatchBinaryOp(Value *V, const DataLayout &DL, AssumptionCache &AC, const DominatorTree &DT, const Instruction *CxtI)
Try to map V into a BinaryOp, and return std::nullopt on failure.
static std::optional< APInt > SolveQuadraticAddRecExact(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE)
Let c(n) be the value of the quadratic chrec {L,+,M,+,N} after n iterations.
static std::optional< APInt > TruncIfPossible(std::optional< APInt > X, unsigned BitWidth)
Helper function to truncate an optional APInt to a given BitWidth.
static cl::opt< unsigned > MaxSCEVCompareDepth("scalar-evolution-max-scev-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV complexity comparisons"), cl::init(32))
static APInt extractConstantWithoutWrapping(ScalarEvolution &SE, const SCEVConstant *ConstantTerm, const SCEVAddExpr *WholeAddExpr)
static cl::opt< unsigned > MaxConstantEvolvingDepth("scalar-evolution-max-constant-evolving-depth", cl::Hidden, cl::desc("Maximum depth of recursive constant evolving"), cl::init(32))
static bool MatchBinarySub(const SCEV *S, SCEVUse &LHS, SCEVUse &RHS)
static std::optional< ConstantRange > GetRangeFromMetadata(Value *V)
Helper method to assign a range to V from metadata present in the IR.
static cl::opt< unsigned > HugeExprThreshold("scalar-evolution-huge-expr-threshold", cl::Hidden, cl::desc("Size of the expression which is considered huge"), cl::init(4096))
static Type * isSimpleCastedPHI(const SCEV *Op, const SCEVUnknown *SymbolicPHI, bool &Signed, ScalarEvolution &SE)
Helper function to createAddRecFromPHIWithCasts.
static Constant * EvaluateExpression(Value *V, const Loop *L, DenseMap< Instruction *, Constant * > &Vals, const DataLayout &DL, const TargetLibraryInfo *TLI)
EvaluateExpression - Given an expression that passes the getConstantEvolvingPHI predicate,...
static const SCEV * getPreviousSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static const SCEV * MatchNotExpr(const SCEV *Expr)
If Expr computes ~A, return A else return nullptr.
static std::pair< ConstantRange, bool > getRangeForAffineARHelper(APInt Step, const ConstantRange &StartRange, const APInt &MaxBECount, bool Signed)
static cl::opt< unsigned > MaxValueCompareDepth("scalar-evolution-max-value-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive value complexity comparisons"), cl::init(2))
static const SCEV * applyDivisibilityOnMinMaxExpr(const SCEV *MinMaxExpr, APInt Divisor, ScalarEvolution &SE)
static cl::opt< bool, true > VerifySCEVOpt("verify-scev", cl::Hidden, cl::location(VerifySCEV), cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"))
static const SCEV * getSignedOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static cl::opt< unsigned > MaxArithDepth("scalar-evolution-max-arith-depth", cl::Hidden, cl::desc("Maximum depth of recursive arithmetics"), cl::init(32))
static bool HasSameValue(const SCEV *A, const SCEV *B)
SCEV structural equivalence is usually sufficient for testing whether two expressions are equal,...
static uint64_t Choose(uint64_t n, uint64_t k, bool &Overflow)
Compute the result of "n choose k", the binomial coefficient.
static std::optional< int > CompareSCEVComplexity(const LoopInfo *const LI, const SCEV *LHS, const SCEV *RHS, DominatorTree &DT, unsigned Depth=0)
static bool canConstantEvolve(Instruction *I, const Loop *L)
Determine whether this instruction can constant evolve within this loop assuming its operands can all...
static PHINode * getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L, DenseMap< Instruction *, PHINode * > &PHIMap, unsigned Depth)
getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by recursing through each instructi...
static bool scevUnconditionallyPropagatesPoisonFromOperands(SCEVTypes Kind)
static cl::opt< bool > VerifySCEVStrict("verify-scev-strict", cl::Hidden, cl::desc("Enable stricter verification with -verify-scev is passed"))
static Constant * getOtherIncomingValue(PHINode *PN, BasicBlock *BB)
static cl::opt< bool > UseExpensiveRangeSharpening("scalar-evolution-use-expensive-range-sharpening", cl::Hidden, cl::init(false), cl::desc("Use more powerful methods of sharpening expression ranges. May " "be costly in terms of compile time"))
static const SCEV * getUnsignedOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static bool IsKnownPredicateViaMinOrMax(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Is LHS Pred RHS true on the virtue of LHS or RHS being a Min or Max expression?
static bool BrPHIToSelect(DominatorTree &DT, CondBrInst *BI, PHINode *Merge, Value *&C, Value *&LHS, Value *&RHS)
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
static bool InBlock(const Value *V, const BasicBlock *BB)
Provides some synthesis utilities to produce sequences of values.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
static SymbolRef::Type getType(const Symbol *Sym)
LocallyHashedType DenseMapInfo< LocallyHashedType >::Empty
static std::optional< bool > isImpliedCondOperands(CmpInst::Predicate Pred, const Value *ALHS, const Value *ARHS, const Value *BLHS, const Value *BRHS)
Return true if "icmp Pred BLHS BRHS" is true whenever "icmp PredALHS ARHS" is true.
Virtual Register Rewriter
static const uint32_t IV[8]
SCEVCastSinkingRewriter(ScalarEvolution &SE, Type *TargetTy, ConversionFn CreatePtrCast)
static const SCEV * rewrite(const SCEV *Scev, ScalarEvolution &SE, Type *TargetTy, ConversionFn CreatePtrCast)
const SCEV * visitUnknown(const SCEVUnknown *Expr)
const SCEV * visitMulExpr(const SCEVMulExpr *Expr)
const SCEV * visitAddExpr(const SCEVAddExpr *Expr)
const SCEV * visit(const SCEV *S)
Class for arbitrary precision integers.
LLVM_ABI APInt umul_ov(const APInt &RHS, bool &Overflow) const
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
uint64_t getZExtValue() const
Get zero extended value.
unsigned getActiveBits() const
Compute the number of active bits in the value.
LLVM_ABI APInt trunc(unsigned width) const
Truncate to new width.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
APInt abs() const
Get the absolute value.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool isSignMask() const
Check if the APInt's value is returned by getSignMask.
LLVM_ABI APInt urem(const APInt &RHS) const
Unsigned remainder operation.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
bool isNegative() const
Determine sign of this APInt.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
LLVM_ABI APInt uadd_ov(const APInt &RHS, bool &Overflow) const
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
bool isNonPositive() const
Determine if this APInt Value is non-positive (<= 0).
unsigned countTrailingZeros() const
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
unsigned logBase2() const
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
LLVM_ABI APInt multiplicativeInverse() const
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
LLVM_ABI APInt sext(unsigned width) const
Sign extend to a new width.
APInt shl(unsigned shiftAmt) const
Left-shift function.
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
bool isSignBitSet() const
Determine if sign bit of this APInt is set.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
This templated class represents "all analyses that operate over <aparticular IR unit>" (e....
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
AnalysisUsage & addRequiredTransitive()
Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
Get the array size.
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
MutableArrayRef< WeakVH > assumptions()
Access the list of assumption handles currently tracked for this function.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
LLVM_ABI unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
LLVM_ABI Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
BinaryOps getOpcode() const
This class represents a function call, abstracting a target machine's calling convention.
virtual void deleted()
Callback for Value destruction.
bool isFalseWhenEqual() const
This is just a convenience.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ ICMP_UGE
unsigned greater or equal
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
@ ICMP_SGE
signed greater or equal
@ ICMP_ULE
unsigned less or equal
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
bool isTrueWhenEqual() const
This is just a convenience.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
static LLVM_ABI std::optional< CmpPredicate > getMatching(CmpPredicate A, CmpPredicate B)
Compares two CmpPredicates taking samesign into account and returns the canonicalized CmpPredicate if...
LLVM_ABI CmpInst::Predicate getPreferredSignedPredicate() const
Attempts to return a signed CmpInst::Predicate from the CmpPredicate.
CmpInst::Predicate dropSameSign() const
Drops samesign information.
Conditional Branch instruction.
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
static LLVM_ABI Constant * getNot(Constant *C)
static Constant * getPtrAdd(Constant *Ptr, Constant *Offset, GEPNoWrapFlags NW=GEPNoWrapFlags::none(), std::optional< ConstantRange > InRange=std::nullopt, Type *OnlyIfReduced=nullptr)
Create a getelementptr i8, ptr, offset constant expression.
static LLVM_ABI Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static LLVM_ABI Constant * getPtrToAddr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static LLVM_ABI Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
static LLVM_ABI Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
This is the shared class of boolean and integer constants.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
static LLVM_ABI ConstantInt * getBool(LLVMContext &Context, bool V)
This class represents a range of values.
LLVM_ABI ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
LLVM_ABI ConstantRange zextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
PreferredRangeType
If represented precisely, the result of some range operations may consist of multiple disjoint ranges...
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI ConstantRange urem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned remainder operation of...
LLVM_ABI bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
LLVM_ABI bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other?
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI ConstantRange zeroExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
LLVM_ABI bool isSignWrappedSet() const
Return true if this set wraps around the signed domain.
LLVM_ABI APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
LLVM_ABI bool isWrappedSet() const
Return true if this set wraps around the unsigned domain.
LLVM_ABI void print(raw_ostream &OS) const
Print out the bounds to a stream.
LLVM_ABI ConstantRange truncate(uint32_t BitWidth, unsigned NoWrapKind=0) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
LLVM_ABI ConstantRange signExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI bool contains(const APInt &Val) const
Return true if the specified value is in the set.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
LLVM_ABI ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
LLVM_ABI APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
static LLVM_ABI ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
LLVM_ABI unsigned getMinSignedBits() const
Compute the maximal number of bits needed to represent every value in this signed range.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
LLVM_ABI ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
LLVM_ABI ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
static LLVM_ABI ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)
Produce the range that contains X if and only if "X BinOp Other" does not wrap.
This is an important base class in LLVM.
A parsed version of the target data layout string in and methods for querying it.
LLVM_ABI const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
LLVM_ABI IntegerType * getIntPtrType(LLVMContext &C, unsigned AddressSpace=0) const
Returns an integer type with size at least as big as that of a pointer in the given address space.
LLVM_ABI unsigned getIndexTypeSizeInBits(Type *Ty) const
The size in bits of the index used in GEP calculation for this type.
LLVM_ABI IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
TypeSize getTypeSizeInBits(Type *Ty) const
Size examples:
ValueT lookup(const_arg_type_t< KeyT > Val) const
Return the entry for the specified key, or a default constructed value if no such entry exists.
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive,...
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Analysis pass which computes a DominatorTree.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
This class describes a reference to an interned FoldingSetNodeID, which can be a useful to store node...
This class is used to gather all the unique data bits of a node.
Represents flags for the getelementptr instruction/expression.
bool hasNoUnsignedSignedWrap() const
bool hasNoUnsignedWrap() const
static GEPNoWrapFlags none()
static LLVM_ABI Type * getTypeAtIndex(Type *Ty, Value *Idx)
Return the type of the element at the given index of an indexable type.
Module * getParent()
Get the module that this global value is contained inside of...
static bool isPrivateLinkage(LinkageTypes Linkage)
static bool isInternalLinkage(LinkageTypes Linkage)
This instruction compares its operands according to the predicate given to the constructor.
CmpPredicate getCmpPredicate() const
static bool isGE(Predicate P)
Return true if the predicate is SGE or UGE.
CmpPredicate getSwappedCmpPredicate() const
static LLVM_ABI bool compare(const APInt &LHS, const APInt &RHS, ICmpInst::Predicate Pred)
Return result of LHS Pred RHS comparison.
static bool isLT(Predicate P)
Return true if the predicate is SLT or ULT.
CmpPredicate getInverseCmpPredicate() const
Predicate getNonStrictCmpPredicate() const
For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.
static bool isGT(Predicate P)
Return true if the predicate is SGT or UGT.
Predicate getFlippedSignednessPredicate() const
For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->EQ.
static CmpPredicate getInverseCmpPredicate(CmpPredicate Pred)
bool isEquality() const
Return true if this predicate is either EQ or NE.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
static bool isLE(Predicate P)
Return true if the predicate is SLE or ULE.
LLVM_ABI bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
LLVM_ABI bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
LLVM_ABI bool isIdenticalToWhenDefined(const Instruction *I, bool IntersectAttrs=false) const LLVM_READONLY
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...
Class to represent integer types.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
A helper class to return the specified delimiter string after the first invocation of operator String...
An instruction for reading from memory.
Analysis pass that exposes the LoopInfo for a function.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getHeader() const
unsigned getLoopDepth() const
Return the nesting level of this loop.
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
A Module instance is used to store all the information related to an LLVM module.
unsigned getOpcode() const
Return the opcode for this Instruction or ConstantExpr.
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
bool hasNoSignedWrap() const
Test whether this operation is known to never undergo signed overflow, aka the nsw property.
bool hasNoUnsignedWrap() const
Test whether this operation is known to never undergo unsigned overflow, aka the nuw property.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
PointerIntPair - This class implements a pair of a pointer and small integer.
static PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the default address space (address sp...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
LLVM_ABI void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
LLVM_ABI const SCEVPredicate & getPredicate() const
LLVM_ABI const SCEV * getPredicatedSCEV(const SCEV *Expr)
Returns the rewritten SCEV for Expr in the context of the current SCEV predicate.
LLVM_ABI bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2, ArrayRef< const SCEVPredicate * > ExtraPreds={}) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds and ExtraPreds.
LLVM_ABI bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've statically proved that V doesn't wrap.
LLVM_ABI const SCEVAddRecExpr * getAsAddRec(Value *V, SmallVectorImpl< const SCEVPredicate * > *WrapPredsAdded=nullptr)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
LLVM_ABI void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
LLVM_ABI PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
LLVM_ABI unsigned getSmallConstantMaxTripCount()
Returns the upper bound of the loop trip count as a normal unsigned value, or 0 if the trip count is ...
LLVM_ABI void addPredicates(ArrayRef< const SCEVPredicate * > Preds)
Adds all predicates in Preds.
LLVM_ABI const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSymbolicMaxBackedgeTakenCount()
Get the (predicated) symbolic max backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
constexpr bool isValid() const
This node represents an addition of some number of SCEVs.
This node represents a polynomial recurrence on the trip count of the specified loop.
friend class ScalarEvolution
LLVM_ABI const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a recurrence without clearing any previously set flags.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
bool isQuadratic() const
Return true if this represents an expression A + B*x + C*x^2 where A, B and C are loop invariant valu...
LLVM_ABI const SCEV * getNumIterationsInRange(const ConstantRange &Range, ScalarEvolution &SE) const
Return the number of iterations of this loop that produce values in the specified constant range.
LLVM_ABI const SCEVAddRecExpr * getPostIncExpr(ScalarEvolution &SE) const
Return an expression representing the value of this expression one iteration of the loop ahead.
const Loop * getLoop() const
SCEVUse getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
This is the base class for unary cast operator classes.
SCEVUse getOperand() const
LLVM_ABI SCEVCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, SCEVUse op, Type *ty)
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a non-recurrence without clearing previously set flags.
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
SCEVComparePredicate(const FoldingSetNodeIDRef ID, const ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Implementation of the SCEVPredicate interface.
This class represents a constant integer value.
ConstantInt * getValue() const
const APInt & getAPInt() const
This is the base class for unary integral cast operator classes.
LLVM_ABI SCEVIntegralCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, SCEVUse op, Type *ty)
This node is the base class min/max selections.
static enum SCEVTypes negate(enum SCEVTypes T)
This node represents multiplication of some number of SCEVs.
This node is a base class providing common functionality for n'ary operators.
bool hasNoUnsignedWrap() const
ArrayRef< SCEVUse > operands() const
bool hasNoSelfWrap() const
size_t getNumOperands() const
bool hasNoSignedWrap() const
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
SCEVUse getOperand(unsigned i) const
This class represents an assumption made using SCEV expressions which can be checked at run-time.
SCEVPredicate(const SCEVPredicate &)=default
virtual bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const =0
Returns true if this predicate implies N.
This class represents a cast from a pointer to a pointer-sized integer value, without capturing the p...
This class represents a cast from a pointer to a pointer-sized integer value.
This visitor recursively visits a SCEV expression and re-writes it.
const SCEV * visitSignExtendExpr(const SCEVSignExtendExpr *Expr)
const SCEV * visit(const SCEV *S)
const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)
const SCEV * visitSMinExpr(const SCEVSMinExpr *Expr)
SCEVRewriteVisitor(ScalarEvolution &SE)
const SCEV * visitUMinExpr(const SCEVUMinExpr *Expr)
This class represents a signed minimum selection.
This node is the base class for sequential/in-order min/max selections.
static SCEVTypes getEquivalentNonSequentialSCEVType(SCEVTypes Ty)
This class represents a sign extension of a small integer value to a larger integer value.
Visit all nodes in the expression tree using worklist traversal.
This class represents a truncation of an integer value to a smaller integer value.
This class represents a binary unsigned division operation.
This class represents an unsigned minimum selection.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
void print(raw_ostream &OS, unsigned Depth) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Returns true if this predicate implies N.
SCEVUnionPredicate(ArrayRef< const SCEVPredicate * > Preds, ScalarEvolution &SE)
Union predicates don't get cached so create a dummy set ID for it.
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
SCEVUnionPredicate getUnionWith(const SCEVPredicate *N, ScalarEvolution &SE) const
Returns a new SCEVUnionPredicate that is the union of this predicate and the given predicate N.
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents the value of vscale, as used when defining the length of a scalable vector or r...
This class represents an assumption made on an AddRec expression.
IncrementWrapFlags
Similar to SCEV::NoWrapFlags, but with slightly different semantics for FlagNUSW.
SCEVWrapPredicate(const FoldingSetNodeIDRef ID, const SCEVAddRecExpr *AR, IncrementWrapFlags Flags)
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Returns true if this predicate implies N.
static SCEVWrapPredicate::IncrementWrapFlags setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OnFlags)
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
const SCEVAddRecExpr * getExpr() const
Implementation of the SCEVPredicate interface.
static SCEVWrapPredicate::IncrementWrapFlags clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OffFlags)
Convenient IncrementWrapFlags manipulation methods.
static SCEVWrapPredicate::IncrementWrapFlags getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE)
Returns the set of SCEVWrapPredicate no wrap flags implied by a SCEVAddRecExpr.
IncrementWrapFlags getFlags() const
Returns the set assumed no overflow flags.
This class represents a zero extension of a small integer value to a larger integer value.
This class represents an analyzed expression in the program.
unsigned short getExpressionSize() const
SCEVNoWrapFlags NoWrapFlags
LLVM_ABI bool isOne() const
Return true if the expression is a constant one.
static constexpr auto FlagNUW
LLVM_ABI void computeAndSetCanonical(ScalarEvolution &SE)
Compute and set the canonical SCEV, by constructing a SCEV with the same operands,...
LLVM_ABI bool isZero() const
Return true if the expression is a constant zero.
const SCEV * CanonicalSCEV
Pointer to the canonical version of the SCEV, i.e.
static constexpr auto FlagAnyWrap
LLVM_ABI void dump() const
This method is used for debugging.
LLVM_ABI bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
LLVM_ABI bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
static constexpr auto FlagNSW
LLVM_ABI ArrayRef< SCEVUse > operands() const
Return operands of this SCEV expression.
LLVM_ABI void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
SCEV(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, unsigned short ExpressionSize)
SCEVTypes getSCEVType() const
static constexpr auto FlagNW
LLVM_ABI Type * getType() const
Return the LLVM type of this SCEV expression.
Analysis pass that exposes the ScalarEvolution for a function.
LLVM_ABI ScalarEvolution run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
void print(raw_ostream &OS, const Module *=nullptr) const override
print - Print out the internal state of the pass.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
ScalarEvolutionWrapperPass()
static LLVM_ABI LoopGuards collect(const Loop *L, ScalarEvolution &SE)
Collect rewrite map for loop guards for loop L, together with flags indicating if NUW and NSW can be ...
LLVM_ABI const SCEV * rewrite(const SCEV *Expr) const
Try to apply the collected loop guards to Expr.
The main scalar evolution driver.
LLVM_ABI const SCEV * getUDivExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
static bool hasFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags TestFlags)
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
LLVM_ABI bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
LLVM_ABI bool isKnownOnEveryIteration(CmpPredicate Pred, const SCEVAddRecExpr *LHS, const SCEV *RHS)
Test if the condition described by Pred, LHS, RHS is known to be true on every iteration of the loop ...
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterationsImpl(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
LLVM_ABI const SCEV * getUDivCeilSCEV(const SCEV *N, const SCEV *D)
Compute ceil(N / D).
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterations(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L at given Context duri...
LLVM_ABI Type * getWiderType(Type *Ty1, Type *Ty2) const
LLVM_ABI const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)
LLVM_ABI bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
LLVM_ABI bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
LLVM_ABI const SCEV * getPredicatedConstantMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getConstantMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
LLVM_ABI bool isLoopEntryGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
LLVM_ABI bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
LLVM_ABI const SCEV * getURemExpr(SCEVUse LHS, SCEVUse RHS)
Represents an unsigned remainder expression based on unsigned division.
LLVM_ABI const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
LLVM_ABI const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
LLVM_ABI const SCEV * getSMinExpr(SCEVUse LHS, SCEVUse RHS)
LLVM_ABI void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags)
Update no-wrap flags of an AddRec.
LLVM_ABI const SCEV * getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS)
Promote the operands to the wider of the types using zero-extension, and then perform a umax operatio...
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
LLVM_ABI bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?
LLVM_ABI ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsOnlyExit, bool AllowPredicates=false)
Compute the number of times the backedge of the specified loop will execute if its exit condition wer...
LLVM_ABI const SCEV * getZeroExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &Operands)
LLVM_ABI const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
LLVM_ABI uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
LLVM_ABI const SCEV * getConstant(ConstantInt *V)
LLVM_ABI const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
LLVM_ABI const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
LLVM_ABI const SCEV * getAddRecExpr(SCEVUse Start, SCEVUse Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
LLVM_ABI const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
static LLVM_ABI bool isGuaranteedNotToBePoison(const SCEV *Op)
Returns true if Op is guaranteed to not be poison.
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
LLVM_ABI const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
LLVM_ABI ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI)
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LLVM_ABI const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI const SCEV * getLosslessPtrToIntExpr(const SCEV *Op)
LLVM_ABI const SCEV * getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty)
LLVM_ABI const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &Operands)
LLVM_ABI std::optional< bool > evaluatePredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Check whether the condition described by Pred, LHS, and RHS is true or false in the given Context.
LLVM_ABI unsigned getSmallConstantMaxTripCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Returns the upper bound of the loop trip count as a normal unsigned value.
LLVM_ABI const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
LLVM_ABI bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
LLVM_ABI void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
LLVM_ABI bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
LLVM_ABI bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
LLVM_ABI bool SimplifyICmpOperands(CmpPredicate &Pred, SCEVUse &LHS, SCEVUse &RHS, unsigned Depth=0)
Simplify LHS and RHS in a comparison with predicate Pred.
APInt getUnsignedRangeMin(const SCEV *S)
Determine the min of the unsigned range for a particular SCEV.
LLVM_ABI const SCEV * getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo)
Return an expression for offsetof on the given field with type IntTy.
LLVM_ABI LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
LLVM_ABI bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
LLVM_ABI const SCEV * getSignExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool hasOperand(const SCEV *S, const SCEV *Op) const
Test whether the given SCEV has Op as a direct or indirect operand.
LLVM_ABI const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
LLVM_ABI Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
LLVM_ABI const SCEVPredicate * getComparePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
LLVM_ABI bool haveSameSign(const SCEV *S1, const SCEV *S2)
Return true if we know that S1 and S2 must have the same sign.
LLVM_ABI const SCEV * getNotSCEV(const SCEV *V)
Return the SCEV object corresponding to ~V.
LLVM_ABI const SCEV * getElementCount(Type *Ty, ElementCount EC, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
LLVM_ABI bool instructionCouldExistWithOperands(const SCEV *A, const SCEV *B)
Return true if there exists a point in the program at which both A and B could be operands to the sam...
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
LLVM_ABI void print(raw_ostream &OS) const
LLVM_ABI const SCEV * getPredicatedExitCount(const Loop *L, const BasicBlock *ExitingBlock, SmallVectorImpl< const SCEVPredicate * > *Predicates, ExitCountKind Kind=Exact)
Same as above except this uses the predicated backedge taken info and may require predicates.
static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
LLVM_ABI void forgetTopmostLoop(const Loop *L)
LLVM_ABI void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
APInt getSignedRangeMin(const SCEV *S)
Determine the min of the signed range for a particular SCEV.
LLVM_ABI bool isLoopUniform(const SCEV *S, const Loop *L)
Returns true if the given SCEV is loop-uniform with respect to the specified loop L.
LLVM_ABI const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
LLVM_ABI const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEV * getUMaxExpr(SCEVUse LHS, SCEVUse RHS)
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags Mask)
Convenient NoWrapFlags manipulation.
@ MonotonicallyDecreasing
@ MonotonicallyIncreasing
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI=nullptr)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L, return a LoopInvaria...
LLVM_ABI const SCEV * getStoreSizeOfExpr(Type *IntTy, Type *StoreTy)
Return an expression for the store size of StoreTy that is type IntTy.
LLVM_ABI const SCEVPredicate * getWrapPredicate(const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
LLVM_ABI bool isLoopBackedgeGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether the backedge of the loop is protected by a conditional between LHS and RHS.
LLVM_ABI APInt getNonZeroConstantMultiple(const SCEV *S)
const SCEV * getMinusOne(Type *Ty)
Return a SCEV for the constant -1 of a specific type.
static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
LLVM_ABI bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
LLVM_ABI BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB)
Return the "disposition" of the given SCEV with respect to the given block.
LLVM_ABI const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
LLVM_ABI const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
Promote the operands to the wider of the types using zero-extension, and then perform a umin operatio...
LLVM_ABI bool loopIsFiniteByAssumption(const Loop *L)
Return true if this loop is finite by assumption.
LLVM_ABI const SCEV * getExistingSCEV(Value *V)
Return an existing SCEV for V if there is one, otherwise return nullptr.
LLVM_ABI APInt getConstantMultiple(const SCEV *S, const Instruction *CtxI=nullptr)
Returns the max constant multiple of S.
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
@ LoopComputable
The SCEV varies predictably with the loop.
@ LoopVariant
The SCEV is loop-variant (unknown).
@ LoopInvariant
The SCEV is loop-invariant.
@ LoopUniform
The SCEV is loop-uniform.
friend class SCEVCallbackVH
LLVM_ABI bool isKnownMultipleOf(const SCEV *S, uint64_t M, SmallVectorImpl< const SCEVPredicate * > &Assumptions)
Check that S is a multiple of M.
LLVM_ABI const SCEV * getAnyExtendExpr(const SCEV *Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
LLVM_ABI bool isKnownToBeAPowerOfTwo(const SCEV *S, bool OrZero=false, bool OrNegative=false)
Test if the given expression is known to be a power of 2.
LLVM_ABI std::optional< SCEV::NoWrapFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
LLVM_ABI void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)
Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...
LLVM_ABI bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
LLVM_ABI std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
LLVM_ABI const SCEV * getCouldNotCompute()
LLVM_ABI const SCEV * getMulExpr(SmallVectorImpl< SCEVUse > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
LLVM_ABI bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
LLVM_ABI uint32_t getMinTrailingZeros(const SCEV *S, const Instruction *CtxI=nullptr)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
@ DominatesBlock
The SCEV dominates the block.
@ ProperlyDominatesBlock
The SCEV properly dominates the block.
@ DoesNotDominateBlock
The SCEV does not dominate the block.
LLVM_ABI const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
LLVM_ABI const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI void getPoisonGeneratingValues(SmallPtrSetImpl< const Value * > &Result, const SCEV *S)
Return the set of Values that, if poison, will definitively result in S being poison as well.
LLVM_ABI void forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
LLVM_ABI const SCEV * getVScale(Type *Ty)
LLVM_ABI unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
LLVM_ABI bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
LLVM_ABI const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
LLVM_ABI void forgetAllLoops()
LLVM_ABI bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
APInt getUnsignedRangeMax(const SCEV *S)
Determine the max of the unsigned range for a particular SCEV.
LLVM_ABI const SCEV * getAddExpr(SmallVectorImpl< SCEVUse > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
ExitCountKind
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of ...
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
@ ConstantMaximum
A constant which provides an upper bound on the exact trip count.
@ Exact
An expression exactly describing the number of times the backedge has executed when a loop is exited.
LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
LLVM_ABI const SCEV * getPtrToAddrExpr(const SCEV *Op)
LLVM_ABI const SCEVAddRecExpr * convertSCEVToAddRecWithPredicates(const SCEV *S, const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Preds)
Tries to convert the S expression to an AddRec expression, adding additional predicates to Preds as r...
LLVM_ABI const SCEV * getSMaxExpr(SCEVUse LHS, SCEVUse RHS)
LLVM_ABI const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
LLVM_ABI const SCEV * getSizeOfExpr(Type *IntTy, TypeSize Size)
Return an expression for a TypeSize.
LLVM_ABI std::optional< bool > evaluatePredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Check whether the condition described by Pred, LHS, and RHS is true or false.
LLVM_ABI const SCEV * getUnknown(Value *V)
LLVM_ABI std::optional< std::pair< const SCEV *, SmallVector< const SCEVPredicate *, 3 > > > createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI)
Checks if SymbolicPHI can be rewritten as an AddRecExpr under some Predicates.
LLVM_ABI const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool isKnownViaInduction(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
We'd like to check the predicate on every iteration of the most dominated loop between loops used in ...
LLVM_ABI std::optional< APInt > computeConstantDifference(const SCEV *LHS, const SCEV *RHS)
Compute LHS - RHS and returns the result as an APInt if it is a constant, and std::nullopt if it isn'...
LLVM_ABI bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
LLVM_ABI const SCEV * getUDivExactExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
LLVM_ABI const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
LLVM_ABI std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
LLVM_ABI bool canReuseInstruction(const SCEV *S, Instruction *I, SmallVectorImpl< Instruction * > &DropPoisonGeneratingInsts)
Check whether it is poison-safe to represent the expression S using the instruction I.
LLVM_ABI bool isKnownPredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * getPredicatedSymbolicMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getSymbolicMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI ~ScalarEvolution()
LLVM_ABI const SCEV * getGEPExpr(GEPOperator *GEP, ArrayRef< SCEVUse > IndexExprs)
Returns an expression for a GEP.
LLVM_ABI const SCEV * getUMinExpr(SCEVUse LHS, SCEVUse RHS, bool Sequential=false)
LLVM_ABI void registerUser(const SCEV *User, ArrayRef< const SCEV * > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
LLVM_ABI bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the basic block is protected by a conditional between LHS and RHS.
LLVM_ABI const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool containsErasedValue(const SCEV *S) const
Return true if the SCEV expression contains a Value that has been optimised out and is now a nullptr.
const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
LLVM_ABI void verify() const
LLVMContext & getContext() const
Implements a dense probed hash-table based set with some number of buckets stored inline.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Represent a constant reference to a string, i.e.
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
TypeSize getElementOffset(unsigned Idx) const
TypeSize getSizeInBits() const
Class to represent struct types.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntOrPtrTy() const
Return true if this is an integer type or a pointer type.
bool isIntegerTy() const
True if this is an instance of IntegerType.
static LLVM_ABI IntegerType * getIntNTy(LLVMContext &C, unsigned N)
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
LLVMContext & getContext() const
All values hold a context through their type.
unsigned getValueID() const
Return an ID for the concrete type of this object.
LLVM_ABI void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
LLVM_ABI std::optional< APInt > SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, unsigned RangeWidth)
Let q(n) = An^2 + Bn + C, and BW = bit width of the value range (e.g.
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
LLVM_ABI APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
constexpr bool any(E Val)
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
int getMinValue(MCInstrInfo const &MCII, MCInst const &MCI)
Return the minimum value of an extendable operand.
@ BasicBlock
Various leaf nodes.
LLVM_ABI Function * getDeclarationIfExists(const Module *M, ID id)
Look up the Function declaration of the intrinsic id in the Module M and return it if it exists.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
auto m_BasicBlock()
Match an arbitrary basic block value and ignore it.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
auto m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
match_bind< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
brc_match< Cond_t, match_bind< BasicBlock >, match_bind< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
bind_cst_ty m_scev_APInt(const APInt *&C)
Match an SCEV constant and bind it to an APInt.
cst_pred_ty< is_all_ones > m_scev_AllOnes()
Match an integer with all bits set.
SCEVUnaryExpr_match< SCEVZeroExtendExpr, Op0_t > m_scev_ZExt(const Op0_t &Op0)
is_undef_or_poison m_scev_UndefOrPoison()
Match an SCEVUnknown wrapping undef or poison.
cst_pred_ty< is_one > m_scev_One()
Match an integer 1.
specificloop_ty m_SpecificLoop(const Loop *L)
SCEVUnaryExpr_match< SCEVSignExtendExpr, Op0_t > m_scev_SExt(const Op0_t &Op0)
match_bind< const SCEVMulExpr > m_scev_Mul(const SCEVMulExpr *&V)
cst_pred_ty< is_zero > m_scev_Zero()
Match an integer 0.
SCEVUnaryExpr_match< SCEVTruncateExpr, Op0_t > m_scev_Trunc(const Op0_t &Op0)
bool match(const SCEV *S, const Pattern &P)
SCEVBinaryExpr_match< SCEVUDivExpr, Op0_t, Op1_t > m_scev_UDiv(const Op0_t &Op0, const Op1_t &Op1)
specificscev_ty m_scev_Specific(const SCEV *S)
Match if we have a specific specified SCEV.
SCEVAffineAddRec_match< Op0_t, Op1_t, match_isa< const Loop > > m_scev_AffineAddRec(const Op0_t &Op0, const Op1_t &Op1)
match_bind< const SCEVUnknown > m_SCEVUnknown(const SCEVUnknown *&V)
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagNUW, true > m_scev_c_NUWMul(const Op0_t &Op0, const Op1_t &Op1)
match_bind< const SCEVAddExpr > m_scev_Add(const SCEVAddExpr *&V)
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagAnyWrap, true > m_scev_c_Mul(const Op0_t &Op0, const Op1_t &Op1)
SCEVBinaryExpr_match< SCEVSMaxExpr, Op0_t, Op1_t > m_scev_SMax(const Op0_t &Op0, const Op1_t &Op1)
SCEVURem_match< Op0_t, Op1_t > m_scev_URem(Op0_t LHS, Op1_t RHS, ScalarEvolution &SE)
Match the mathematical pattern A - (A / B) * B, where A and B can be arbitrary expressions.
@ Valid
The data is already valid.
initializer< Ty > init(const Ty &Val)
LocationClass< Ty > location(Ty &L)
@ Switch
The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...
NodeAddr< PhiNode * > Phi
friend class Instruction
Iterator for Instructions in a `BasicBlock.
unsigned getOpcode(const VPValue *V)
Return the instruction opcode for the recipe defining V or 0 for unsupported recipes and VPValues not...
This is an optimization pass for GlobalISel generic memory operations.
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt gcd(const DynamicAPInt &A, const DynamicAPInt &B)
void stable_sort(R &&Range)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
SaveAndRestore(T &) -> SaveAndRestore< T >
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)
LLVM_ABI bool canCreatePoison(const Operator *Op, bool ConsiderFlagsAndMetadata=true)
LLVM_ABI bool mustTriggerUB(const Instruction *I, const SmallPtrSetImpl< const Value * > &KnownPoison)
Return true if the given instruction must trigger undefined behavior when I is executed with any oper...
RelativeUniformCounterPtr Values
@ Known
Known to have no common set bits.
LLVM_ABI bool canConstantFoldCallTo(const CallBase *Call, const Function *F)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
InterleavedRange< Range > interleaved(const Range &R, StringRef Separator=", ", StringRef Prefix="", StringRef Suffix="")
Output range R as a sequence of interleaved elements.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
auto successors(const MachineBasicBlock *BB)
scope_exit(Callable) -> scope_exit< Callable >
@ BinaryOp
One of the operands is a binary op.
@ Load
The value being inserted comes from a load (InsertElement only).
@ Store
The extracted value is stored (ExtractElement only).
constexpr from_range_t from_range
auto dyn_cast_if_present(const Y &Val)
dyn_cast_if_present<X> - Functionally identical to dyn_cast, except that a null (or none in the case ...
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
auto uninitialized_copy(R &&Src, IterTy Dst)
bool isa_and_nonnull(const Y &Val)
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO, const DominatorTree &DT)
Returns true if the arithmetic part of the WO 's result is used only along the paths control dependen...
DomTreeNodeBase< BasicBlock > DomTreeNode
LLVM_ABI bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step)
Attempt to match a simple first order recurrence cycle of the form: iv = phi Ty [Start,...
auto dyn_cast_or_null(const Y &Val)
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
iterator_range< pointee_iterator< WrappedIteratorT > > make_pointee_range(RangeT &&Range)
auto reverse(ContainerTy &&C)
LLVM_ABI bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
LLVM_ABI bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
LLVM_ABI bool isFinite(const Loop *L)
Return true if this loop can be assumed to run for a finite number of iterations.
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
unsigned short computeExpressionSize(ArrayRef< SCEVUse > Args)
LLVM_ABI bool programUndefinedIfPoison(const Instruction *Inst)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isPointerTy(const Type *T)
LLVM_ABI ConstantRange getVScaleRange(const Function *F, unsigned BitWidth)
Determine the possible constant range of vscale with the given bit width, based on the vscale_range f...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
LLVM_ABI bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)
Return true if the given value is known to be non-zero when defined.
constexpr T divideCeil(U Numerator, V Denominator)
Returns the integer ceil(Numerator / Denominator).
LLVM_ABI bool propagatesPoison(const Use &PoisonOp)
Return true if PoisonOp's user yields poison or raises UB if its operand PoisonOp is poison.
@ UMin
Unsigned integer min implemented in terms of select(cmp()).
@ Mul
Product of integers.
@ SMax
Signed integer max implemented in terms of select(cmp()).
@ SMin
Signed integer min implemented in terms of select(cmp()).
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
DWARFExpression::Operation Op
auto max_element(R &&Range)
Provide wrappers to std::max_element which take ranges instead of having to pass begin/end explicitly...
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
ArrayRef(const T &OneElt) -> ArrayRef< T >
LLVM_ABI unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Return the number of times the sign bit of the register is replicated into the other bits.
constexpr unsigned BitWidth
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
constexpr auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
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)
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be poison, but may be undef.
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
SCEVUseT< const SCEV * > SCEVUse
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
Implement std::hash so that hash_code can be used in STL containers.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
A special type used by analysis passes to provide an address that identifies that particular analysis...
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
static LLVM_ABI KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for ashr(LHS, RHS).
static LLVM_ABI KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for lshr(LHS, RHS).
static LLVM_ABI KnownBits shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW=false, bool NSW=false, bool ShAmtNonZero=false)
Compute known bits for shl(LHS, RHS).
An object of this class is returned by queries that could not be answered.
LLVM_ABI SCEVCouldNotCompute()
static LLVM_ABI bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This class defines a simple visitor class that may be used for various SCEV analysis purposes.
A utility class that uses RAII to save and restore the value of a variable.
Information about the number of loop iterations for which a loop exit's branch condition evaluates to...
LLVM_ABI ExitLimit(const SCEV *E)
Construct either an exact exit limit from a constant, or an unknown one from a SCEVCouldNotCompute.
const SCEV * ExactNotTaken
const SCEV * SymbolicMaxNotTaken
SmallVector< const SCEVPredicate *, 4 > Predicates
A vector of predicate guards for this ExitLimit.
const SCEV * ConstantMaxNotTaken