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"),
265#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
283 OS <<
"(ptrtoint " << *
Op->getType() <<
" " << *
Op <<
" to "
284 << *PtrToInt->
getType() <<
")";
290 OS <<
"(trunc " << *
Op->getType() <<
" " << *
Op <<
" to "
297 OS <<
"(zext " << *
Op->getType() <<
" " << *
Op <<
" to "
304 OS <<
"(sext " << *
Op->getType() <<
" " << *
Op <<
" to "
333 const char *OpStr =
nullptr;
346 OpStr =
" umin_seq ";
370 OS <<
"(" << *UDiv->
getLHS() <<
" /u " << *UDiv->
getRHS() <<
")";
377 OS <<
"***COULDNOTCOMPUTE***";
453 if (!
Mul)
return false;
457 if (!SC)
return false;
475 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
477 UniqueSCEVs.InsertNode(S, IP);
491 ConstantInt::get(ITy, V, isSigned,
true));
499 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
502 UniqueSCEVs.InsertNode(S, IP);
522 "Must be a non-bit-width-changing pointer-to-integer cast!");
534 "Cannot truncate non-integer value!");
541 "Cannot zero extend non-integer value!");
548 "Cannot sign extend non-integer value!");
553 SE->forgetMemoizedResults(
this);
556 SE->UniqueSCEVs.RemoveNode(
this);
562void SCEVUnknown::allUsesReplacedWith(
Value *New) {
564 SE->forgetMemoizedResults(
this);
567 SE->UniqueSCEVs.RemoveNode(
this);
589 if (LIsPointer != RIsPointer)
590 return (
int)LIsPointer - (int)RIsPointer;
595 return (
int)LID - (int)RID;
600 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
601 return (
int)LArgNo - (int)RArgNo;
607 if (
auto L = LGV->getLinkage() - RGV->getLinkage())
610 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
611 auto LT = GV->getLinkage();
618 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
619 return LGV->getName().compare(RGV->getName());
630 if (LParent != RParent) {
633 if (LDepth != RDepth)
634 return (
int)LDepth - (int)RDepth;
638 unsigned LNumOps = LInst->getNumOperands(),
639 RNumOps = RInst->getNumOperands();
640 if (LNumOps != RNumOps)
641 return (
int)LNumOps - (int)RNumOps;
643 for (
unsigned Idx :
seq(LNumOps)) {
645 RInst->getOperand(Idx),
Depth + 1);
659static std::optional<int>
669 return (
int)LType - (int)RType;
694 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
695 if (LBitWidth != RBitWidth)
696 return (
int)LBitWidth - (int)RBitWidth;
697 return LA.
ult(
RA) ? -1 : 1;
703 return LTy->getBitWidth() - RTy->getBitWidth();
714 if (LLoop != RLoop) {
716 assert(LHead != RHead &&
"Two loops share the same header?");
720 "No dominance between recurrences used by one SCEV?");
743 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
744 if (LNumOps != RNumOps)
745 return (
int)LNumOps - (int)RNumOps;
747 for (
unsigned i = 0; i != LNumOps; ++i) {
772 if (
Ops.size() < 2)
return;
777 return Complexity && *Complexity < 0;
779 if (
Ops.size() == 2) {
783 if (IsLessComplex(
RHS,
LHS))
790 return IsLessComplex(
LHS,
RHS);
797 for (
unsigned i = 0, e =
Ops.size(); i != e-2; ++i) {
803 for (
unsigned j = i+1; j != e &&
Ops[j]->getSCEVType() == Complexity; ++j) {
808 if (i == e-2)
return;
830template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
834 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
836 for (
unsigned Idx = 0; Idx <
Ops.size();) {
844 Ops.erase(
Ops.begin() + Idx);
851 assert(Folded &&
"Must have folded value");
855 if (Folded && IsAbsorber(Folded->
getAPInt()))
859 if (Folded && !IsIdentity(Folded->
getAPInt()))
860 Ops.insert(
Ops.begin(), Folded);
862 return Ops.size() == 1 ?
Ops[0] :
nullptr;
937 APInt OddFactorial(W, 1);
939 for (
unsigned i = 3; i <= K; ++i) {
942 OddFactorial *= (i >> TwoFactors);
946 unsigned CalculationBits = W +
T;
960 for (
unsigned i = 1; i != K; ++i) {
993 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1013 "getLosslessPtrToIntExpr() should self-recurse at most once.");
1017 if (!
Op->getType()->isPointerTy())
1028 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1058 SCEV *S =
new (SCEVAllocator)
1060 UniqueSCEVs.InsertNode(S, IP);
1065 assert(
Depth == 0 &&
"getLosslessPtrToIntExpr() should not self-recurse for "
1066 "non-SCEVUnknown's.");
1078 class SCEVPtrToIntSinkingRewriter
1086 SCEVPtrToIntSinkingRewriter
Rewriter(SE);
1087 return Rewriter.visit(Scev);
1096 return Base::visit(S);
1121 "Should only reach pointer-typed SCEVUnknown's.");
1127 const SCEV *IntOp = SCEVPtrToIntSinkingRewriter::rewrite(
Op, *
this);
1129 "We must have succeeded in sinking the cast, "
1130 "and ending up with an integer-typed expression!");
1135 assert(Ty->isIntegerTy() &&
"Target type must be an integer type!");
1147 "This is not a truncating conversion!");
1149 "This is not a conversion to a SCEVable type!");
1150 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1158 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1180 UniqueSCEVs.InsertNode(S, IP);
1192 unsigned numTruncs = 0;
1193 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1201 if (numTruncs < 2) {
1211 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1218 for (
const SCEV *
Op : AddRec->operands())
1233 UniqueSCEVs.InsertNode(S, IP);
1273struct ExtendOpTraitsBase {
1274 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
const SCEV *,
Type *,
1279template <
typename ExtendOp>
struct ExtendOpTraits {
1295 static const GetExtendExprTy GetExtendExpr;
1297 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1298 ICmpInst::Predicate *Pred,
1299 ScalarEvolution *SE) {
1304const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1311 static const GetExtendExprTy GetExtendExpr;
1313 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1314 ICmpInst::Predicate *Pred,
1315 ScalarEvolution *SE) {
1320const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1332template <
typename ExtendOpTy>
1335 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1336 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1352 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1365 auto PreStartFlags =
1383 const SCEV *OperandExtendedStart =
1385 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1386 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1398 const SCEV *OverflowLimit =
1399 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1401 if (OverflowLimit &&
1409template <
typename ExtendOpTy>
1413 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1421 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1456template <
typename ExtendOpTy>
1457bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1460 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1470 APInt StartAI = StartC->
getAPInt();
1472 for (
unsigned Delta : {-2, -1, 1, 2}) {
1473 const SCEV *PreStart =
getConstant(StartAI - Delta);
1475 FoldingSetNodeID
ID;
1477 ID.AddPointer(PreStart);
1478 ID.AddPointer(Step);
1482 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
1486 if (PreAR && PreAR->getNoWrapFlags(WrapType)) {
1489 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1490 DeltaS, &Pred,
this);
1508 const unsigned BitWidth =
C.getBitWidth();
1526 const APInt &ConstantStart,
1545 auto &UserIDs = FoldCacheUser[
I.first->second];
1546 assert(
count(UserIDs,
ID) == 1 &&
"unexpected duplicates in UserIDs");
1547 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1548 if (UserIDs[
I] ==
ID) {
1553 I.first->second = S;
1555 FoldCacheUser[S].push_back(
ID);
1561 "This is not an extending conversion!");
1563 "This is not a conversion to a SCEVable type!");
1564 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1568 if (
const SCEV *S = FoldCache.lookup(
ID))
1580 "This is not an extending conversion!");
1582 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1599 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1603 UniqueSCEVs.InsertNode(S, IP);
1612 const SCEV *
X = ST->getOperand();
1626 if (AR->isAffine()) {
1627 const SCEV *Start = AR->getStart();
1628 const SCEV *Step = AR->getStepRecurrence(*
this);
1630 const Loop *L = AR->getLoop();
1634 if (AR->hasNoUnsignedWrap()) {
1655 const SCEV *CastedMaxBECount =
1659 if (MaxBECount == RecastedMaxBECount) {
1669 const SCEV *WideMaxBECount =
1671 const SCEV *OperandExtendedAdd =
1677 if (ZAdd == OperandExtendedAdd) {
1688 OperandExtendedAdd =
1694 if (ZAdd == OperandExtendedAdd) {
1715 !AC.assumptions().empty()) {
1717 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1719 if (AR->hasNoUnsignedWrap()) {
1754 const APInt &
C = SC->getAPInt();
1758 const SCEV *SResidual =
1767 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1792 if (SA->hasNoUnsignedWrap()) {
1796 for (
const auto *
Op : SA->operands())
1813 const SCEV *SResidual =
1825 if (SM->hasNoUnsignedWrap()) {
1829 for (
const auto *
Op : SM->operands())
1847 const SCEV *TruncRHS;
1866 for (
auto *Operand :
MinMax->operands())
1877 for (
auto *Operand :
MinMax->operands())
1884 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1887 UniqueSCEVs.InsertNode(S, IP);
1895 "This is not an extending conversion!");
1897 "This is not a conversion to a SCEVable type!");
1898 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1902 if (
const SCEV *S = FoldCache.lookup(
ID))
1914 "This is not an extending conversion!");
1916 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1938 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1943 UniqueSCEVs.InsertNode(S, IP);
1952 const SCEV *
X = ST->getOperand();
1963 if (SA->hasNoSignedWrap()) {
1967 for (
const auto *
Op : SA->operands())
1985 const SCEV *SResidual =
1999 if (AR->isAffine()) {
2000 const SCEV *Start = AR->getStart();
2001 const SCEV *Step = AR->getStepRecurrence(*
this);
2003 const Loop *L = AR->getLoop();
2007 if (AR->hasNoSignedWrap()) {
2029 const SCEV *CastedMaxBECount =
2033 if (MaxBECount == RecastedMaxBECount) {
2043 const SCEV *WideMaxBECount =
2045 const SCEV *OperandExtendedAdd =
2051 if (SAdd == OperandExtendedAdd) {
2062 OperandExtendedAdd =
2068 if (SAdd == OperandExtendedAdd) {
2088 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2090 if (AR->hasNoSignedWrap()) {
2105 const APInt &
C = SC->getAPInt();
2109 const SCEV *SResidual =
2118 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2137 for (
auto *Operand :
MinMax->operands())
2146 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
2149 UniqueSCEVs.InsertNode(S, IP);
2175 "This is not an extending conversion!");
2177 "This is not a conversion to a SCEVable type!");
2182 if (SC->getAPInt().isNegative())
2187 const SCEV *NewOp =
T->getOperand();
2206 for (
const SCEV *
Op : AR->operands())
2245 APInt &AccumulatedConstant,
2248 bool Interesting =
false;
2255 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2257 AccumulatedConstant += Scale *
C->getAPInt();
2262 for (; i !=
Ops.size(); ++i) {
2272 Add->operands(), NewScale, SE);
2278 auto Pair = M.insert({
Key, NewScale});
2282 Pair.first->second += NewScale;
2290 std::pair<DenseMap<const SCEV *, APInt>::iterator,
bool> Pair =
2291 M.insert({
Ops[i], Scale});
2295 Pair.first->second += Scale;
2314 case Instruction::Add:
2317 case Instruction::Sub:
2320 case Instruction::Mul:
2334 const SCEV *
A = (this->*Extension)(
2336 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2337 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2345 if (BinOp == Instruction::Mul)
2351 APInt C = RHSC->getAPInt();
2352 unsigned NumBits =
C.getBitWidth();
2353 bool IsSub = (BinOp == Instruction::Sub);
2354 bool IsNegativeConst = (
Signed &&
C.isNegative());
2356 bool OverflowDown = IsSub ^ IsNegativeConst;
2358 if (IsNegativeConst) {
2371 APInt Limit = Min + Magnitude;
2377 APInt Limit = Max - Magnitude;
2382std::optional<SCEV::NoWrapFlags>
2387 return std::nullopt;
2396 bool Deduced =
false;
2398 if (OBO->
getOpcode() != Instruction::Add &&
2401 return std::nullopt;
2410 false, LHS, RHS, CtxI)) {
2417 true, LHS, RHS, CtxI)) {
2424 return std::nullopt;
2434 using namespace std::placeholders;
2441 assert(CanAnalyze &&
"don't call from other places!");
2448 auto IsKnownNonNegative = [&](
const SCEV *S) {
2458 if (SignOrUnsignWrap != SignOrUnsignMask &&
2465 return Instruction::Add;
2467 return Instruction::Mul;
2478 Opcode,
C, OBO::NoSignedWrap);
2486 Opcode,
C, OBO::NoUnsignedWrap);
2496 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2503 if (UDiv->getOperand(1) ==
Ops[1])
2506 if (UDiv->getOperand(1) ==
Ops[0])
2522 "only nuw or nsw allowed");
2523 assert(!
Ops.empty() &&
"Cannot get empty add!");
2524 if (
Ops.size() == 1)
return Ops[0];
2527 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2529 "SCEVAddExpr operand types don't match!");
2531 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2532 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2537 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2538 [](
const APInt &
C) {
return C.isZero(); },
2539 [](
const APInt &
C) {
return false; });
2552 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2557 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2558 Add->setNoWrapFlags(ComputeFlags(
Ops));
2566 bool FoundMatch =
false;
2567 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2568 if (
Ops[i] ==
Ops[i+1]) {
2580 --i; e -=
Count - 1;
2590 auto FindTruncSrcType = [&]() ->
Type * {
2596 return T->getOperand()->getType();
2598 const auto *LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2600 return T->getOperand()->getType();
2604 if (
auto *SrcType = FindTruncSrcType()) {
2611 if (
T->getOperand()->getType() != SrcType) {
2620 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2623 if (
T->getOperand()->getType() != SrcType) {
2651 if (
Ops.size() == 2) {
2661 auto C2 =
C->getAPInt();
2664 APInt ConstAdd = C1 + C2;
2665 auto AddFlags = AddExpr->getNoWrapFlags();
2706 if (
Ops.size() == 2 &&
2717 if (Idx <
Ops.size()) {
2718 bool DeletedAdd =
false;
2729 Ops.erase(
Ops.begin()+Idx);
2732 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2755 struct APIntCompare {
2756 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2757 return LHS.ult(RHS);
2764 std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists;
2765 for (
const SCEV *NewOp : NewOps)
2766 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2769 if (AccumulatedConstant != 0)
2771 for (
auto &MulOp : MulOpLists) {
2772 if (MulOp.first == 1) {
2774 }
else if (MulOp.first != 0) {
2783 if (
Ops.size() == 1)
2794 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2795 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2798 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp)
2799 if (MulOpSCEV ==
Ops[AddOp]) {
2801 const SCEV *InnerMul =
Mul->getOperand(MulOp == 0);
2802 if (
Mul->getNumOperands() != 2) {
2806 Mul->operands().take_front(MulOp));
2814 if (
Ops.size() == 2)
return OuterMul;
2816 Ops.erase(
Ops.begin()+AddOp);
2817 Ops.erase(
Ops.begin()+Idx-1);
2819 Ops.erase(
Ops.begin()+Idx);
2820 Ops.erase(
Ops.begin()+AddOp-1);
2822 Ops.push_back(OuterMul);
2827 for (
unsigned OtherMulIdx = Idx+1;
2834 OMulOp != e; ++OMulOp)
2835 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2837 const SCEV *InnerMul1 =
Mul->getOperand(MulOp == 0);
2838 if (
Mul->getNumOperands() != 2) {
2840 Mul->operands().take_front(MulOp));
2847 OtherMul->
operands().take_front(OMulOp));
2852 const SCEV *InnerMulSum =
2856 if (
Ops.size() == 2)
return OuterMul;
2857 Ops.erase(
Ops.begin()+Idx);
2858 Ops.erase(
Ops.begin()+OtherMulIdx-1);
2859 Ops.push_back(OuterMul);
2879 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2882 Ops.erase(
Ops.begin()+i);
2887 if (!LIOps.
empty()) {
2912 auto *DefI = getDefiningScopeBound(LIOps);
2914 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2926 if (
Ops.size() == 1)
return NewRec;
2929 for (
unsigned i = 0;; ++i)
2930 if (
Ops[i] == AddRec) {
2940 for (
unsigned OtherIdx = Idx+1;
2948 "AddRecExprs are not sorted in reverse dominance order?");
2955 if (OtherAddRec->getLoop() == AddRecLoop) {
2956 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2958 if (i >= AddRecOps.
size()) {
2959 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2963 AddRecOps[i], OtherAddRec->getOperand(i)};
2966 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
2981 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2993 static_cast<SCEVAddExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
2995 const SCEV **O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
2997 S =
new (SCEVAllocator)
2999 UniqueSCEVs.InsertNode(S, IP);
3009 FoldingSetNodeID
ID;
3011 for (
const SCEV *
Op :
Ops)
3016 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3018 const SCEV **
O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
3020 S =
new (SCEVAllocator)
3021 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3022 UniqueSCEVs.InsertNode(S, IP);
3023 LoopUsers[
L].push_back(S);
3033 FoldingSetNodeID
ID;
3035 for (
const SCEV *
Op :
Ops)
3039 static_cast<SCEVMulExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3041 const SCEV **
O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
3043 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3045 UniqueSCEVs.InsertNode(S, IP);
3054 if (j > 1 && k / j != i) Overflow =
true;
3070 if (n == 0 || n == k)
return 1;
3071 if (k > n)
return 0;
3077 for (
uint64_t i = 1; i <= k; ++i) {
3078 r =
umul_ov(r, n-(i-1), Overflow);
3087 struct FindConstantInAddMulChain {
3088 bool FoundConstant =
false;
3090 bool follow(
const SCEV *S) {
3095 bool isDone()
const {
3096 return FoundConstant;
3100 FindConstantInAddMulChain
F;
3102 ST.visitAll(StartExpr);
3103 return F.FoundConstant;
3111 "only nuw or nsw allowed");
3112 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3113 if (
Ops.size() == 1)
return Ops[0];
3115 Type *ETy =
Ops[0]->getType();
3117 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3119 "SCEVMulExpr operand types don't match!");
3124 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3125 [](
const APInt &
C) {
return C.isOne(); },
3126 [](
const APInt &
C) {
return C.isZero(); });
3137 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3142 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3143 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3148 if (
Ops.size() == 2) {
3156 const SCEV *Op0, *Op1;
3164 if (
Ops[0]->isAllOnesValue()) {
3169 bool AnyFolded =
false;
3170 for (
const SCEV *AddOp :
Add->operands()) {
3197 AddRec->getNoWrapFlags(FlagsMask));
3220 APInt C1V = LHSC->getAPInt();
3230 const SCEV *NewMul =
nullptr;
3234 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3249 if (Idx <
Ops.size()) {
3250 bool DeletedMul =
false;
3256 Ops.erase(
Ops.begin()+Idx);
3280 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3283 Ops.erase(
Ops.begin()+i);
3288 if (!LIOps.
empty()) {
3301 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3317 if (
Ops.size() == 1)
return NewRec;
3320 for (
unsigned i = 0;; ++i)
3321 if (
Ops[i] == AddRec) {
3342 bool OpsModified =
false;
3343 for (
unsigned OtherIdx = Idx+1;
3357 bool Overflow =
false;
3364 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3368 z < ze && !Overflow; ++z) {
3371 if (LargerThan64Bits)
3372 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3374 Coeff = Coeff1*Coeff2;
3389 if (
Ops.size() == 2)
return NewAddRec;
3390 Ops[Idx] = NewAddRec;
3391 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3407 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3415 "SCEVURemExpr operand types don't match!");
3420 if (RHSC->getValue()->isOne())
3421 return getZero(LHS->getType());
3424 if (RHSC->getAPInt().isPowerOf2()) {
3425 Type *FullTy = LHS->getType();
3442 assert(!LHS->getType()->isPointerTy() &&
3443 "SCEVUDivExpr operand can't be pointer!");
3444 assert(LHS->getType() == RHS->getType() &&
3445 "SCEVUDivExpr operand types don't match!");
3452 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3460 if (RHSC->getValue()->isOne())
3465 if (!RHSC->getValue()->isZero()) {
3469 Type *Ty = LHS->getType();
3470 unsigned LZ = RHSC->getAPInt().countl_zero();
3474 if (!RHSC->getAPInt().isPowerOf2())
3482 const APInt &StepInt = Step->getAPInt();
3483 const APInt &DivInt = RHSC->getAPInt();
3484 if (!StepInt.
urem(DivInt) &&
3490 for (
const SCEV *
Op : AR->operands())
3496 const APInt *StartRem;
3509 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3513 const SCEV *NewStart =
3515 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3517 const SCEV *NewLHS =
3520 if (LHS != NewLHS) {
3530 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3539 for (
const SCEV *
Op : M->operands())
3543 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3544 const SCEV *
Op = M->getOperand(i);
3556 if (
auto *DivisorConstant =
3558 bool Overflow =
false;
3560 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3571 for (
const SCEV *
Op :
A->operands())
3575 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3582 if (Operands.
size() ==
A->getNumOperands())
3589 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3599 return getZero(LHS->getType());
3603 const SCEV *NewLHS, *NewRHS;
3611 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
3614 UniqueSCEVs.InsertNode(S, IP);
3644 if (!
Mul || !
Mul->hasNoUnsignedWrap())
3651 if (LHSCst == RHSCst) {
3659 APInt Factor =
gcd(LHSCst, RHSCst);
3677 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3678 if (
Mul->getOperand(i) == RHS) {
3697 if (StepChrec->getLoop() == L) {
3711 if (Operands.
size() == 1)
return Operands[0];
3716 "SCEVAddRecExpr operand types don't match!");
3717 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3719 for (
const SCEV *
Op : Operands)
3721 "SCEVAddRecExpr operand is not available at loop entry!");
3724 if (Operands.
back()->isZero()) {
3739 const Loop *NestedLoop = NestedAR->getLoop();
3740 if (L->contains(NestedLoop)
3743 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3745 Operands[0] = NestedAR->getStart();
3749 bool AllInvariant =
all_of(
3761 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3772 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3776 Operands[0] = NestedAR;
3782 return getOrCreateAddRecExpr(Operands, L, Flags);
3798 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3802 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3816 bool FirstIter =
true;
3818 for (
const SCEV *IndexExpr : IndexExprs) {
3825 Offsets.push_back(FieldOffset);
3828 CurTy = STy->getTypeAtIndex(Index);
3833 "The first index of a GEP indexes a pointer");
3834 CurTy = SrcElementTy;
3845 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3846 Offsets.push_back(LocalOffset);
3851 if (Offsets.empty())
3864 "GEP should not change type mid-flight.");
3868SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3871 ID.AddInteger(SCEVType);
3875 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3885 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3886 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3887 if (
Ops.size() == 1)
return Ops[0];
3890 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3892 "Operand types don't match!");
3895 "min/max should be consistently pointerish");
3921 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3923 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3928 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3930 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3936 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3942 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3947 if (Idx <
Ops.size()) {
3948 bool DeletedAny =
false;
3949 while (
Ops[Idx]->getSCEVType() == Kind) {
3951 Ops.erase(
Ops.begin()+Idx);
3969 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3970 if (
Ops[i] ==
Ops[i + 1] ||
3971 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3974 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3977 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3980 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3986 if (
Ops.size() == 1)
return Ops[0];
3988 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
3993 ID.AddInteger(Kind);
3997 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3999 return ExistingSCEV;
4000 const SCEV **O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
4002 SCEV *S =
new (SCEVAllocator)
4005 UniqueSCEVs.InsertNode(S, IP);
4012class SCEVSequentialMinMaxDeduplicatingVisitor final
4013 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4014 std::optional<const SCEV *>> {
4015 using RetVal = std::optional<const SCEV *>;
4023 bool canRecurseInto(
SCEVTypes Kind)
const {
4026 return RootKind == Kind || NonSequentialRootKind == Kind;
4029 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
4031 "Only for min/max expressions.");
4034 if (!canRecurseInto(Kind))
4044 return std::nullopt;
4051 RetVal
visit(
const SCEV *S) {
4053 if (!SeenOps.
insert(S).second)
4054 return std::nullopt;
4055 return Base::visit(S);
4059 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4061 : SE(SE), RootKind(RootKind),
4062 NonSequentialRootKind(
4063 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4067 SmallVectorImpl<const SCEV *> &NewOps) {
4072 for (
const SCEV *
Op : OrigOps) {
4077 Ops.emplace_back(*NewOp);
4081 NewOps = std::move(
Ops);
4085 RetVal visitConstant(
const SCEVConstant *Constant) {
return Constant; }
4087 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4089 RetVal visitPtrToIntExpr(
const SCEVPtrToIntExpr *Expr) {
return Expr; }
4091 RetVal visitTruncateExpr(
const SCEVTruncateExpr *Expr) {
return Expr; }
4093 RetVal visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
return Expr; }
4095 RetVal visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
return Expr; }
4097 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4099 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4101 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4103 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4105 RetVal visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
4106 return visitAnyMinMaxExpr(Expr);
4109 RetVal visitUMaxExpr(
const SCEVUMaxExpr *Expr) {
4110 return visitAnyMinMaxExpr(Expr);
4113 RetVal visitSMinExpr(
const SCEVSMinExpr *Expr) {
4114 return visitAnyMinMaxExpr(Expr);
4117 RetVal visitUMinExpr(
const SCEVUMinExpr *Expr) {
4118 return visitAnyMinMaxExpr(Expr);
4121 RetVal visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *Expr) {
4122 return visitAnyMinMaxExpr(Expr);
4125 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4127 RetVal visitCouldNotCompute(
const SCEVCouldNotCompute *Expr) {
return Expr; }
4169struct SCEVPoisonCollector {
4170 bool LookThroughMaybePoisonBlocking;
4171 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4172 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4173 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4175 bool follow(
const SCEV *S) {
4176 if (!LookThroughMaybePoisonBlocking &&
4186 bool isDone()
const {
return false; }
4196 SCEVPoisonCollector PC1(
true);
4201 if (PC1.MaybePoison.empty())
4207 SCEVPoisonCollector PC2(
false);
4217 SCEVPoisonCollector PC(
false);
4240 while (!Worklist.
empty()) {
4242 if (!Visited.
insert(V).second)
4246 if (Visited.
size() > 16)
4251 if (PoisonVals.
contains(V) || ::isGuaranteedNotToBePoison(V))
4262 if (PDI->isDisjoint())
4269 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4276 if (
I->hasPoisonGeneratingAnnotations())
4287 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4288 "Not a SCEVSequentialMinMaxExpr!");
4289 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4290 if (
Ops.size() == 1)
4294 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4296 "Operand types don't match!");
4299 "min/max should be consistently pointerish");
4307 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4314 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4324 bool DeletedAny =
false;
4325 while (Idx <
Ops.size()) {
4326 if (
Ops[Idx]->getSCEVType() != Kind) {
4331 Ops.erase(
Ops.begin() + Idx);
4332 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4333 SMME->operands().end());
4341 const SCEV *SaturationPoint;
4352 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4353 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4365 Ops.erase(
Ops.begin() + i);
4370 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4371 Ops.erase(
Ops.begin() + i);
4379 ID.AddInteger(Kind);
4383 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4385 return ExistingSCEV;
4387 const SCEV **O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
4389 SCEV *S =
new (SCEVAllocator)
4392 UniqueSCEVs.InsertNode(S, IP);
4440 if (
Size.isScalable())
4461 "Cannot get offset for structure containing scalable vector types");
4475 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP)) {
4477 "Stale SCEVUnknown in uniquing map!");
4483 UniqueSCEVs.InsertNode(S, IP);
4497 return Ty->isIntOrPtrTy();
4504 if (Ty->isPointerTy())
4515 if (Ty->isIntegerTy())
4519 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4531 bool PreciseA, PreciseB;
4532 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4533 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4534 if (!PreciseA || !PreciseB)
4537 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4538 DT.dominates(ScopeB, ScopeA);
4542 return CouldNotCompute.get();
4545bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4548 return SU && SU->getValue() ==
nullptr;
4551 return !ContainsNulls;
4556 if (
I != HasRecMap.end())
4561 HasRecMap.insert({S, FoundAddRec});
4569 if (
SI == ExprValueMap.
end())
4571 return SI->second.getArrayRef();
4577void ScalarEvolution::eraseValueFromMap(
Value *V) {
4579 if (
I != ValueExprMap.end()) {
4580 auto EVIt = ExprValueMap.find(
I->second);
4581 bool Removed = EVIt->second.remove(V);
4583 assert(Removed &&
"Value not in ExprValueMap?");
4584 ValueExprMap.erase(
I);
4588void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4592 auto It = ValueExprMap.find_as(V);
4593 if (It == ValueExprMap.end()) {
4595 ExprValueMap[S].insert(V);
4606 return createSCEVIter(V);
4613 if (
I != ValueExprMap.end()) {
4614 const SCEV *S =
I->second;
4615 assert(checkValidity(S) &&
4616 "existing SCEV has not been properly invalidated");
4629 Type *Ty = V->getType();
4645 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4658 return (
const SCEV *)
nullptr;
4664 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4668 Type *Ty = V->getType();
4674 assert(
P->getType()->isPointerTy());
4687 const SCEV **PtrOp =
nullptr;
4688 for (
const SCEV *&AddOp :
Ops) {
4689 if (AddOp->getType()->isPointerTy()) {
4690 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4708 return getZero(LHS->getType());
4713 if (RHS->getType()->isPointerTy()) {
4714 if (!LHS->getType()->isPointerTy() ||
4724 const bool RHSIsNotMinSigned =
4755 Type *SrcTy = V->getType();
4756 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4757 "Cannot truncate or zero extend with non-integer arguments!");
4767 Type *SrcTy = V->getType();
4768 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4769 "Cannot truncate or zero extend with non-integer arguments!");
4779 Type *SrcTy = V->getType();
4780 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4781 "Cannot noop or zero extend with non-integer arguments!");
4783 "getNoopOrZeroExtend cannot truncate!");
4791 Type *SrcTy = V->getType();
4792 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4793 "Cannot noop or sign extend with non-integer arguments!");
4795 "getNoopOrSignExtend cannot truncate!");
4803 Type *SrcTy = V->getType();
4804 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4805 "Cannot noop or any extend with non-integer arguments!");
4807 "getNoopOrAnyExtend cannot truncate!");
4815 Type *SrcTy = V->getType();
4816 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4817 "Cannot truncate or noop with non-integer arguments!");
4819 "getTruncateOrNoop cannot extend!");
4827 const SCEV *PromotedLHS = LHS;
4828 const SCEV *PromotedRHS = RHS;
4848 assert(!
Ops.empty() &&
"At least one operand must be!");
4850 if (
Ops.size() == 1)
4854 Type *MaxType =
nullptr;
4855 for (
const auto *S :
Ops)
4860 assert(MaxType &&
"Failed to find maximum type!");
4864 for (
const auto *S :
Ops)
4873 if (!V->getType()->isPointerTy())
4878 V = AddRec->getStart();
4880 const SCEV *PtrOp =
nullptr;
4881 for (
const SCEV *AddOp :
Add->operands()) {
4882 if (AddOp->getType()->isPointerTy()) {
4883 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4887 assert(PtrOp &&
"Must have pointer op");
4899 for (
User *U :
I->users()) {
4901 if (Visited.
insert(UserInsn).second)
4915 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4916 bool IgnoreOtherLoops =
true) {
4919 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4921 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4926 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4928 SeenLoopVariantSCEVUnknown =
true;
4932 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4936 SeenOtherLoops =
true;
4940 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4942 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4945 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4946 : SCEVRewriteVisitor(SE),
L(
L) {}
4949 bool SeenLoopVariantSCEVUnknown =
false;
4950 bool SeenOtherLoops =
false;
4959 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4960 SCEVPostIncRewriter
Rewriter(L, SE);
4962 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4967 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4969 SeenLoopVariantSCEVUnknown =
true;
4973 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4977 SeenOtherLoops =
true;
4981 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4983 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4986 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4987 : SCEVRewriteVisitor(SE),
L(
L) {}
4990 bool SeenLoopVariantSCEVUnknown =
false;
4991 bool SeenOtherLoops =
false;
4997class SCEVBackedgeConditionFolder
5000 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5001 ScalarEvolution &SE) {
5002 bool IsPosBECond =
false;
5003 Value *BECond =
nullptr;
5004 if (BasicBlock *Latch =
L->getLoopLatch()) {
5008 "Both outgoing branches should not target same header!");
5015 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
5019 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5020 const SCEV *
Result = Expr;
5025 switch (
I->getOpcode()) {
5026 case Instruction::Select: {
5028 std::optional<const SCEV *> Res =
5029 compareWithBackedgeCondition(
SI->getCondition());
5037 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5048 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5049 bool IsPosBECond, ScalarEvolution &SE)
5050 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5051 IsPositiveBECond(IsPosBECond) {}
5053 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5057 Value *BackedgeCond =
nullptr;
5059 bool IsPositiveBECond;
5062std::optional<const SCEV *>
5063SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5068 if (BackedgeCond == IC)
5071 return std::nullopt;
5076 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5077 ScalarEvolution &SE) {
5083 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5090 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5100 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5101 : SCEVRewriteVisitor(SE),
L(
L) {}
5110ScalarEvolution::proveNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5114 using OBO = OverflowingBinaryOperator;
5122 const APInt &BECountAP = BECountMax->getAPInt();
5123 unsigned NoOverflowBitWidth =
5135 Instruction::Add, IncRange, OBO::NoSignedWrap);
5136 if (NSWRegion.contains(AddRecRange))
5145 Instruction::Add, IncRange, OBO::NoUnsignedWrap);
5146 if (NUWRegion.contains(AddRecRange))
5154ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5164 if (!SignedWrapViaInductionTried.insert(AR).second)
5189 AC.assumptions().empty())
5197 const SCEV *OverflowLimit =
5199 if (OverflowLimit &&
5207ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5217 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5243 AC.assumptions().empty())
5278 explicit BinaryOp(Operator *
Op)
5282 IsNSW = OBO->hasNoSignedWrap();
5283 IsNUW = OBO->hasNoUnsignedWrap();
5287 explicit BinaryOp(
unsigned Opcode,
Value *
LHS,
Value *
RHS,
bool IsNSW =
false,
5289 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5301 return std::nullopt;
5307 switch (
Op->getOpcode()) {
5308 case Instruction::Add:
5309 case Instruction::Sub:
5310 case Instruction::Mul:
5311 case Instruction::UDiv:
5312 case Instruction::URem:
5313 case Instruction::And:
5314 case Instruction::AShr:
5315 case Instruction::Shl:
5316 return BinaryOp(
Op);
5318 case Instruction::Or: {
5321 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5323 return BinaryOp(
Op);
5326 case Instruction::Xor:
5330 if (RHSC->getValue().isSignMask())
5331 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5333 if (V->getType()->isIntegerTy(1))
5334 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5335 return BinaryOp(
Op);
5337 case Instruction::LShr:
5346 if (SA->getValue().ult(
BitWidth)) {
5348 ConstantInt::get(SA->getContext(),
5350 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5353 return BinaryOp(
Op);
5355 case Instruction::ExtractValue: {
5357 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5365 bool Signed = WO->isSigned();
5368 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5373 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5384 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5385 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5387 return std::nullopt;
5413 if (
Op == SymbolicPHI)
5418 if (SourceBits != NewBits)
5436 if (!L || L->getHeader() != PN->
getParent())
5494std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5495ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5503 assert(L &&
"Expecting an integer loop header phi");
5508 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5509 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5510 Value *
V = PN->getIncomingValue(i);
5511 if (
L->contains(PN->getIncomingBlock(i))) {
5514 }
else if (BEValueV != V) {
5518 }
else if (!StartValueV) {
5520 }
else if (StartValueV != V) {
5521 StartValueV =
nullptr;
5525 if (!BEValueV || !StartValueV)
5526 return std::nullopt;
5528 const SCEV *BEValue =
getSCEV(BEValueV);
5535 return std::nullopt;
5539 unsigned FoundIndex =
Add->getNumOperands();
5540 Type *TruncTy =
nullptr;
5542 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5545 if (FoundIndex == e) {
5550 if (FoundIndex ==
Add->getNumOperands())
5551 return std::nullopt;
5555 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5556 if (i != FoundIndex)
5557 Ops.push_back(
Add->getOperand(i));
5563 return std::nullopt;
5616 const SCEV *StartVal =
getSCEV(StartValueV);
5617 const SCEV *PHISCEV =
5644 auto getExtendedExpr = [&](
const SCEV *Expr,
5645 bool CreateSignExtend) ->
const SCEV * {
5648 const SCEV *ExtendedExpr =
5651 return ExtendedExpr;
5659 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5660 const SCEV *ExtendedExpr) ->
bool {
5661 return Expr != ExtendedExpr &&
5665 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5666 if (PredIsKnownFalse(StartVal, StartExtended)) {
5668 return std::nullopt;
5673 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5674 if (PredIsKnownFalse(Accum, AccumExtended)) {
5676 return std::nullopt;
5679 auto AppendPredicate = [&](
const SCEV *Expr,
5680 const SCEV *ExtendedExpr) ->
void {
5681 if (Expr != ExtendedExpr &&
5689 AppendPredicate(StartVal, StartExtended);
5690 AppendPredicate(Accum, AccumExtended);
5698 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5699 std::make_pair(NewAR, Predicates);
5701 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5705std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5710 return std::nullopt;
5713 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5714 if (
I != PredicatedSCEVRewrites.end()) {
5715 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5718 if (Rewrite.first == SymbolicPHI)
5719 return std::nullopt;
5723 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5727 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5728 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5733 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5734 return std::nullopt;
5751 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5752 if (Expr1 != Expr2 &&
5753 !Preds->implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5754 !Preds->implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5771const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5773 Value *StartValueV) {
5776 assert(BEValueV && StartValueV);
5782 if (BO->Opcode != Instruction::Add)
5785 const SCEV *Accum =
nullptr;
5786 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5788 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5802 insertValueToMap(PN, PHISCEV);
5807 proveNoWrapViaConstantRanges(AR)));
5815 "Accum is defined outside L, but is not invariant?");
5816 if (isAddRecNeverPoison(BEInst, L))
5823const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5824 const Loop *
L = LI.getLoopFor(PN->
getParent());
5831 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5837 }
else if (BEValueV != V) {
5841 }
else if (!StartValueV) {
5843 }
else if (StartValueV != V) {
5844 StartValueV =
nullptr;
5848 if (!BEValueV || !StartValueV)
5851 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5852 "PHI node already processed?");
5856 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5861 insertValueToMap(PN, SymbolicName);
5865 const SCEV *BEValue =
getSCEV(BEValueV);
5875 unsigned FoundIndex =
Add->getNumOperands();
5876 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5877 if (
Add->getOperand(i) == SymbolicName)
5878 if (FoundIndex == e) {
5883 if (FoundIndex !=
Add->getNumOperands()) {
5886 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5887 if (i != FoundIndex)
5888 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5900 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5907 if (
GEP->getOperand(0) == PN) {
5908 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
5926 const SCEV *StartVal =
getSCEV(StartValueV);
5927 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5932 forgetMemoizedResults(SymbolicName);
5933 insertValueToMap(PN, PHISCEV);
5938 proveNoWrapViaConstantRanges(AR)));
5963 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5964 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5966 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5967 const SCEV *StartVal =
getSCEV(StartValueV);
5968 if (Start == StartVal) {
5972 forgetMemoizedResults(SymbolicName);
5973 insertValueToMap(PN, Shifted);
5983 eraseValueFromMap(PN);
6003 Use &LeftUse =
Merge->getOperandUse(0);
6004 Use &RightUse =
Merge->getOperandUse(1);
6021const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
6023 [&](
BasicBlock *BB) {
return DT.isReachableFromEntry(BB); };
6038 assert(IDom &&
"At least the entry block should dominate PN");
6047 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6063ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6064 BinaryOperator *CommonInst =
nullptr;
6075 CommonInst = IncomingInst;
6082 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6083 bool SCEVExprsIdentical =
6085 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6086 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6089const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6090 if (
const SCEV *S = createAddRecFromPHI(PN))
6100 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6103 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6112 struct FindClosure {
6113 const SCEV *OperandToFind;
6119 bool canRecurseInto(
SCEVTypes Kind)
const {
6122 return RootKind == Kind || NonSequentialRootKind == Kind ||
6127 : OperandToFind(OperandToFind), RootKind(RootKind),
6128 NonSequentialRootKind(
6132 bool follow(
const SCEV *S) {
6133 Found = S == OperandToFind;
6135 return !isDone() && canRecurseInto(S->
getSCEVType());
6138 bool isDone()
const {
return Found; }
6141 FindClosure FC(OperandToFind, RootKind);
6146std::optional<const SCEV *>
6147ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6157 switch (ICI->getPredicate()) {
6171 bool Signed = ICI->isSigned();
6172 const SCEV *LA =
getSCEV(TrueVal);
6180 if (LA == LS &&
RA == RS)
6182 if (LA == RS &&
RA == LS)
6185 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6186 if (
Op->getType()->isPointerTy()) {
6197 LS = CoerceOperand(LS);
6198 RS = CoerceOperand(RS);
6222 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6223 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6237 X = ZExt->getOperand();
6239 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6250 return std::nullopt;
6253static std::optional<const SCEV *>
6255 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6259 "Unexpected operands of a select.");
6271 return std::nullopt;
6286static std::optional<const SCEV *>
6290 return std::nullopt;
6293 const auto *SETrue = SE->
getSCEV(TrueVal);
6294 const auto *SEFalse = SE->
getSCEV(FalseVal);
6298const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6300 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6302 V->getType() ==
TrueVal->getType() &&
6303 "Types of select hands and of the result must match.");
6306 if (!
V->getType()->isIntegerTy(1))
6309 if (std::optional<const SCEV *> S =
6322 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6326 if (std::optional<const SCEV *> S =
6327 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6333 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6339 assert(
GEP->getSourceElementType()->isSized() &&
6340 "GEP source element type must be sized");
6343 for (
Value *Index :
GEP->indices())
6348APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6351 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6354 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6356 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6359 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6377 return GetShiftedByZeros(TZ);
6387 return GetShiftedByZeros(TZ);
6391 if (
M->hasNoUnsignedWrap()) {
6394 for (
const SCEV *Operand :
M->operands().drop_front())
6402 for (
const SCEV *Operand :
M->operands())
6404 return GetShiftedByZeros(TZ);
6409 if (
N->hasNoUnsignedWrap())
6410 return GetGCDMultiple(
N);
6413 for (
const SCEV *Operand :
N->operands().drop_front())
6415 return GetShiftedByZeros(TZ);
6432 CtxI = &*F.getEntryBlock().begin();
6438 .countMinTrailingZeros();
6439 return GetShiftedByZeros(Known);
6452 return getConstantMultipleImpl(S, CtxI);
6454 auto I = ConstantMultipleCache.find(S);
6455 if (
I != ConstantMultipleCache.end())
6458 APInt Result = getConstantMultipleImpl(S, CtxI);
6459 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6460 assert(InsertPair.second &&
"Should insert a new key");
6461 return InsertPair.first->second;
6478 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6481 if (std::optional<ConstantRange>
Range = CB->getRange())
6485 if (std::optional<ConstantRange>
Range =
A->getRange())
6488 return std::nullopt;
6495 UnsignedRanges.erase(AddRec);
6496 SignedRanges.erase(AddRec);
6497 ConstantMultipleCache.erase(AddRec);
6502getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6528 Value *Start, *Step;
6535 assert(L && L->getHeader() ==
P->getParent());
6548 case Instruction::AShr:
6549 case Instruction::LShr:
6550 case Instruction::Shl:
6565 KnownStep.getBitWidth() ==
BitWidth);
6568 auto MaxShiftAmt = KnownStep.getMaxValue();
6570 bool Overflow =
false;
6571 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6578 case Instruction::AShr: {
6586 if (KnownStart.isNonNegative())
6589 KnownStart.getMaxValue() + 1);
6590 if (KnownStart.isNegative())
6593 KnownEnd.getMaxValue() + 1);
6596 case Instruction::LShr: {
6605 KnownStart.getMaxValue() + 1);
6607 case Instruction::Shl: {
6611 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6612 return ConstantRange(KnownStart.getMinValue(),
6613 KnownEnd.getMaxValue() + 1);
6621ScalarEvolution::getRangeRefIter(
const SCEV *S,
6622 ScalarEvolution::RangeSignHint SignHint) {
6623 DenseMap<const SCEV *, ConstantRange> &Cache =
6624 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6627 SmallPtrSet<const SCEV *, 8> Seen;
6631 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6632 if (!Seen.
insert(Expr).second)
6665 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6666 const SCEV *
P = WorkList[
I];
6670 for (
const SCEV *
Op :
P->operands())
6676 if (!PendingPhiRangesIter.insert(
P).second)
6683 if (!WorkList.
empty()) {
6688 getRangeRef(
P, SignHint);
6692 PendingPhiRangesIter.erase(
P);
6696 return getRangeRef(S, SignHint, 0);
6703 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6704 DenseMap<const SCEV *, ConstantRange> &Cache =
6705 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6713 if (
I != Cache.
end())
6717 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6722 return getRangeRefIter(S, SignHint);
6725 ConstantRange ConservativeResult(
BitWidth,
true);
6726 using OBO = OverflowingBinaryOperator;
6730 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6734 ConservativeResult =
6741 ConservativeResult = ConstantRange(
6757 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6764 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6771 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6775 ConstantRange
X = getRangeRef(PtrToInt->
getOperand(), SignHint,
Depth + 1);
6776 return setRange(PtrToInt, SignHint,
X);
6781 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6782 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6784 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6785 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6786 ConservativeResult =
6787 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6789 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6790 unsigned WrapType = OBO::AnyWrap;
6791 if (
Add->hasNoSignedWrap())
6792 WrapType |= OBO::NoSignedWrap;
6793 if (
Add->hasNoUnsignedWrap())
6794 WrapType |= OBO::NoUnsignedWrap;
6796 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6798 return setRange(
Add, SignHint,
6799 ConservativeResult.intersectWith(
X, RangeType));
6803 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6805 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6806 return setRange(
Mul, SignHint,
6807 ConservativeResult.intersectWith(
X, RangeType));
6811 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6812 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6813 return setRange(UDiv, SignHint,
6814 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6822 if (!UnsignedMinValue.
isZero())
6823 ConservativeResult = ConservativeResult.intersectWith(
6824 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6833 bool AllNonNeg =
true;
6834 bool AllNonPos =
true;
6835 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6842 ConservativeResult = ConservativeResult.intersectWith(
6847 ConservativeResult = ConservativeResult.intersectWith(
6856 const SCEV *MaxBEScev =
6870 auto RangeFromAffine = getRangeForAffineAR(
6872 ConservativeResult =
6873 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6875 auto RangeFromFactoring = getRangeViaFactoring(
6877 ConservativeResult =
6878 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6884 const SCEV *SymbolicMaxBECount =
6889 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6890 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6891 ConservativeResult =
6892 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6897 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6907 ID = Intrinsic::umax;
6910 ID = Intrinsic::smax;
6914 ID = Intrinsic::umin;
6917 ID = Intrinsic::smin;
6924 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6925 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6927 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6928 return setRange(S, SignHint,
6929 ConservativeResult.intersectWith(
X, RangeType));
6938 ConservativeResult =
6939 ConservativeResult.intersectWith(*MDRange, RangeType);
6944 auto CR = getRangeForUnknownRecurrence(U);
6945 ConservativeResult = ConservativeResult.intersectWith(CR);
6956 if (
U->getType()->isPointerTy()) {
6959 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
6960 int ptrIdxDiff = ptrSize -
BitWidth;
6961 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
6974 ConservativeResult = ConservativeResult.intersectWith(
6978 ConservativeResult = ConservativeResult.intersectWith(
6983 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6986 bool CanBeNull, CanBeFreed;
6987 uint64_t DerefBytes =
6988 V->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed);
6998 uint64_t
Align =
U->getValue()->getPointerAlignment(DL).value();
6999 uint64_t Rem = MaxVal.
urem(Align);
7004 ConservativeResult = ConservativeResult.intersectWith(
7012 if (PendingPhiRanges.insert(Phi).second) {
7013 ConstantRange RangeFromOps(
BitWidth,
false);
7015 for (
const auto &
Op :
Phi->operands()) {
7017 RangeFromOps = RangeFromOps.unionWith(OpRange);
7019 if (RangeFromOps.isFullSet())
7022 ConservativeResult =
7023 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7024 bool Erased = PendingPhiRanges.erase(Phi);
7025 assert(Erased &&
"Failed to erase Phi properly?");
7032 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7034 ConservativeResult = ConservativeResult.difference(Disallowed);
7037 return setRange(U, SignHint, std::move(ConservativeResult));
7043 return setRange(S, SignHint, std::move(ConservativeResult));
7052 const APInt &MaxBECount,
7059 if (Step == 0 || MaxBECount == 0)
7066 return ConstantRange::getFull(
BitWidth);
7082 return ConstantRange::getFull(
BitWidth);
7094 APInt MovedBoundary = Descending ? (StartLower - std::move(
Offset))
7095 : (StartUpper + std::move(
Offset));
7100 if (StartRange.
contains(MovedBoundary))
7101 return ConstantRange::getFull(
BitWidth);
7104 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7106 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7115 const APInt &MaxBECount) {
7119 "mismatched bit widths");
7128 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7130 StartSRange, MaxBECount,
7142ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7144 ScalarEvolution::RangeSignHint SignHint) {
7145 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7147 "This only works for non-self-wrapping AddRecs!");
7148 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7152 return ConstantRange::getFull(
BitWidth);
7160 return ConstantRange::getFull(
BitWidth);
7164 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7166 MaxItersWithoutWrap))
7167 return ConstantRange::getFull(
BitWidth);
7188 ConstantRange StartRange = getRangeRef(Start, SignHint);
7189 ConstantRange EndRange = getRangeRef(End, SignHint);
7190 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7194 return RangeBetween;
7199 return ConstantRange::getFull(
BitWidth);
7202 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7203 return RangeBetween;
7205 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7206 return RangeBetween;
7207 return ConstantRange::getFull(
BitWidth);
7212 const APInt &MaxBECount) {
7219 "mismatched bit widths");
7221 struct SelectPattern {
7222 Value *Condition =
nullptr;
7226 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7228 std::optional<unsigned> CastOp;
7242 CastOp = SCast->getSCEVType();
7243 S = SCast->getOperand();
7246 using namespace llvm::PatternMatch;
7253 Condition =
nullptr;
7285 bool isRecognized() {
return Condition !=
nullptr; }
7288 SelectPattern StartPattern(*
this,
BitWidth, Start);
7289 if (!StartPattern.isRecognized())
7290 return ConstantRange::getFull(
BitWidth);
7292 SelectPattern StepPattern(*
this,
BitWidth, Step);
7293 if (!StepPattern.isRecognized())
7294 return ConstantRange::getFull(
BitWidth);
7296 if (StartPattern.Condition != StepPattern.Condition) {
7300 return ConstantRange::getFull(
BitWidth);
7311 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7312 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7313 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7314 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7316 ConstantRange TrueRange =
7317 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount);
7318 ConstantRange FalseRange =
7319 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount);
7341ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7355 SmallPtrSet<const SCEV *, 16> Visited;
7357 auto pushOp = [&](
const SCEV *S) {
7358 if (!Visited.
insert(S).second)
7361 if (Visited.
size() > 30) {
7368 for (
const auto *S :
Ops)
7372 while (!Worklist.
empty()) {
7374 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7375 if (!Bound || DT.dominates(Bound, DefI))
7382 return Bound ? Bound : &*F.getEntryBlock().begin();
7388 return getDefiningScopeBound(
Ops, Discard);
7391bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7393 if (
A->getParent() ==
B->getParent() &&
7398 auto *BLoop = LI.getLoopFor(
B->getParent());
7399 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7400 BLoop->getLoopPreheader() ==
A->getParent() &&
7402 A->getParent()->end()) &&
7409bool ScalarEvolution::isGuaranteedNotToBePoison(
const SCEV *
Op) {
7410 SCEVPoisonCollector PC(
true);
7412 return PC.MaybePoison.empty();
7415bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7421 return M && (!
isKnownNonZero(Op1) || !isGuaranteedNotToBePoison(Op1));
7425bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7442 for (
const Use &
Op :
I->operands()) {
7448 auto *DefI = getDefiningScopeBound(SCEVOps);
7449 return isGuaranteedToTransferExecutionTo(DefI,
I);
7452bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7454 if (isSCEVExprNeverPoison(
I))
7465 auto *ExitingBB =
L->getExitingBlock();
7469 SmallPtrSet<const Value *, 16> KnownPoison;
7478 while (!Worklist.
empty()) {
7481 for (
const Use &U :
Poison->uses()) {
7484 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7488 if (KnownPoison.
insert(PoisonUser).second)
7496ScalarEvolution::LoopProperties
7497ScalarEvolution::getLoopProperties(
const Loop *L) {
7498 using LoopProperties = ScalarEvolution::LoopProperties;
7500 auto Itr = LoopPropertiesCache.find(L);
7501 if (Itr == LoopPropertiesCache.end()) {
7504 return !
SI->isSimple();
7514 return I->mayWriteToMemory();
7517 LoopProperties LP = {
true,
7520 for (
auto *BB :
L->getBlocks())
7521 for (
auto &
I : *BB) {
7523 LP.HasNoAbnormalExits =
false;
7524 if (HasSideEffects(&
I))
7525 LP.HasNoSideEffects =
false;
7526 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7530 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7531 assert(InsertPair.second &&
"We just checked!");
7532 Itr = InsertPair.first;
7545const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7551 Stack.emplace_back(V,
true);
7552 Stack.emplace_back(V,
false);
7553 while (!Stack.empty()) {
7554 auto E = Stack.pop_back_val();
7555 Value *CurV = E.getPointer();
7561 const SCEV *CreatedSCEV =
nullptr;
7564 CreatedSCEV = createSCEV(CurV);
7569 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7573 insertValueToMap(CurV, CreatedSCEV);
7577 Stack.emplace_back(CurV,
true);
7579 Stack.emplace_back(
Op,
false);
7596 if (!DT.isReachableFromEntry(
I->getParent()))
7609 switch (BO->Opcode) {
7610 case Instruction::Add:
7611 case Instruction::Mul: {
7618 Ops.push_back(BO->
Op);
7622 Ops.push_back(BO->RHS);
7626 (BO->Opcode == Instruction::Add &&
7627 (NewBO->Opcode != Instruction::Add &&
7628 NewBO->Opcode != Instruction::Sub)) ||
7629 (BO->Opcode == Instruction::Mul &&
7630 NewBO->Opcode != Instruction::Mul)) {
7631 Ops.push_back(BO->LHS);
7636 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7639 Ops.push_back(BO->LHS);
7647 case Instruction::Sub:
7648 case Instruction::UDiv:
7649 case Instruction::URem:
7651 case Instruction::AShr:
7652 case Instruction::Shl:
7653 case Instruction::Xor:
7657 case Instruction::And:
7658 case Instruction::Or:
7662 case Instruction::LShr:
7669 Ops.push_back(BO->LHS);
7670 Ops.push_back(BO->RHS);
7674 switch (
U->getOpcode()) {
7675 case Instruction::Trunc:
7676 case Instruction::ZExt:
7677 case Instruction::SExt:
7678 case Instruction::PtrToInt:
7679 Ops.push_back(
U->getOperand(0));
7682 case Instruction::BitCast:
7684 Ops.push_back(
U->getOperand(0));
7689 case Instruction::SDiv:
7690 case Instruction::SRem:
7691 Ops.push_back(
U->getOperand(0));
7692 Ops.push_back(
U->getOperand(1));
7695 case Instruction::GetElementPtr:
7697 "GEP source element type must be sized");
7701 case Instruction::IntToPtr:
7704 case Instruction::PHI:
7708 case Instruction::Select: {
7710 auto CanSimplifyToUnknown = [
this,
U]() {
7728 if (CanSimplifyToUnknown())
7735 case Instruction::Call:
7736 case Instruction::Invoke:
7743 switch (
II->getIntrinsicID()) {
7744 case Intrinsic::abs:
7745 Ops.push_back(
II->getArgOperand(0));
7747 case Intrinsic::umax:
7748 case Intrinsic::umin:
7749 case Intrinsic::smax:
7750 case Intrinsic::smin:
7751 case Intrinsic::usub_sat:
7752 case Intrinsic::uadd_sat:
7753 Ops.push_back(
II->getArgOperand(0));
7754 Ops.push_back(
II->getArgOperand(1));
7756 case Intrinsic::start_loop_iterations:
7757 case Intrinsic::annotation:
7758 case Intrinsic::ptr_annotation:
7759 Ops.push_back(
II->getArgOperand(0));
7771const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7780 if (!DT.isReachableFromEntry(
I->getParent()))
7795 switch (BO->Opcode) {
7796 case Instruction::Add: {
7822 if (BO->Opcode == Instruction::Sub)
7830 if (BO->Opcode == Instruction::Sub)
7837 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7838 NewBO->Opcode != Instruction::Sub)) {
7848 case Instruction::Mul: {
7869 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7878 case Instruction::UDiv:
7882 case Instruction::URem:
7886 case Instruction::Sub: {
7889 Flags = getNoWrapFlagsFromUB(BO->
Op);
7894 case Instruction::And:
7900 if (CI->isMinusOne())
7902 const APInt &
A = CI->getValue();
7908 unsigned LZ =
A.countl_zero();
7909 unsigned TZ =
A.countr_zero();
7914 APInt EffectiveMask =
7916 if ((LZ != 0 || TZ != 0) && !((~
A & ~Known.
Zero) & EffectiveMask)) {
7919 const SCEV *ShiftedLHS =
nullptr;
7923 unsigned MulZeros = OpC->getAPInt().countr_zero();
7924 unsigned GCD = std::min(MulZeros, TZ);
7929 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
7951 case Instruction::Or:
7960 case Instruction::Xor:
7963 if (CI->isMinusOne())
7972 if (LBO->getOpcode() == Instruction::And &&
7973 LCI->getValue() == CI->getValue())
7974 if (
const SCEVZeroExtendExpr *Z =
7977 const SCEV *Z0 =
Z->getOperand();
7984 if (CI->getValue().isMask(Z0TySize))
7990 APInt Trunc = CI->getValue().trunc(Z0TySize);
7999 case Instruction::Shl:
8017 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8025 ConstantInt *
X = ConstantInt::get(
8031 case Instruction::AShr:
8053 const SCEV *AddTruncateExpr =
nullptr;
8054 ConstantInt *ShlAmtCI =
nullptr;
8055 const SCEV *AddConstant =
nullptr;
8057 if (L &&
L->getOpcode() == Instruction::Add) {
8065 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8072 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8080 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8085 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8090 if (AddTruncateExpr && ShlAmtCI) {
8102 const APInt &ShlAmt = ShlAmtCI->
getValue();
8106 const SCEV *CompositeExpr =
8108 if (
L->getOpcode() != Instruction::Shl)
8109 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8118 switch (
U->getOpcode()) {
8119 case Instruction::Trunc:
8122 case Instruction::ZExt:
8125 case Instruction::SExt:
8135 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8136 Type *Ty =
U->getType();
8144 case Instruction::BitCast:
8150 case Instruction::PtrToInt: {
8153 Type *DstIntTy =
U->getType();
8161 case Instruction::IntToPtr:
8165 case Instruction::SDiv:
8172 case Instruction::SRem:
8179 case Instruction::GetElementPtr:
8182 case Instruction::PHI:
8185 case Instruction::Select:
8186 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8189 case Instruction::Call:
8190 case Instruction::Invoke:
8195 switch (
II->getIntrinsicID()) {
8196 case Intrinsic::abs:
8200 case Intrinsic::umax:
8204 case Intrinsic::umin:
8208 case Intrinsic::smax:
8212 case Intrinsic::smin:
8216 case Intrinsic::usub_sat: {
8217 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8218 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8222 case Intrinsic::uadd_sat: {
8223 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8224 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8228 case Intrinsic::start_loop_iterations:
8229 case Intrinsic::annotation:
8230 case Intrinsic::ptr_annotation:
8234 case Intrinsic::vscale:
8254 auto *ExitCountType = ExitCount->
getType();
8255 assert(ExitCountType->isIntegerTy());
8257 1 + ExitCountType->getScalarSizeInBits());
8270 auto CanAddOneWithoutOverflow = [&]() {
8272 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8283 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8313 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8314 assert(L->isLoopExiting(ExitingBlock) &&
8315 "Exiting block must actually branch out of the loop!");
8324 const auto *MaxExitCount =
8332 L->getExitingBlocks(ExitingBlocks);
8334 std::optional<unsigned> Res;
8335 for (
auto *ExitingBB : ExitingBlocks) {
8339 Res = std::gcd(*Res, Multiple);
8341 return Res.value_or(1);
8345 const SCEV *ExitCount) {
8375 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8376 assert(L->isLoopExiting(ExitingBlock) &&
8377 "Exiting block must actually branch out of the loop!");
8387 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8389 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8391 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8401 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8404 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8407 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8415 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8422 return getBackedgeTakenInfo(L).getExact(L,
this);
8424 return getBackedgeTakenInfo(L).getConstantMax(
this);
8426 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8433 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8438 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8442 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8452 for (
PHINode &PN : Header->phis())
8453 if (Visited.
insert(&PN).second)
8457ScalarEvolution::BackedgeTakenInfo &
8458ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8459 auto &BTI = getBackedgeTakenInfo(L);
8460 if (BTI.hasFullInfo())
8463 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8466 return Pair.first->second;
8468 BackedgeTakenInfo
Result =
8469 computeBackedgeTakenCount(L,
true);
8471 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8474ScalarEvolution::BackedgeTakenInfo &
8475ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8481 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8482 BackedgeTakenCounts.try_emplace(L);
8484 return Pair.first->second;
8489 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8496 if (
Result.hasAnyInfo()) {
8499 auto LoopUsersIt = LoopUsers.find(L);
8500 if (LoopUsersIt != LoopUsers.end())
8502 forgetMemoizedResults(ToForget);
8505 for (PHINode &PN :
L->getHeader()->phis())
8506 ConstantEvolutionLoopExitValue.erase(&PN);
8514 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8523 BackedgeTakenCounts.clear();
8524 PredicatedBackedgeTakenCounts.clear();
8525 BECountUsers.clear();
8526 LoopPropertiesCache.clear();
8527 ConstantEvolutionLoopExitValue.clear();
8528 ValueExprMap.clear();
8529 ValuesAtScopes.clear();
8530 ValuesAtScopesUsers.clear();
8531 LoopDispositions.clear();
8532 BlockDispositions.clear();
8533 UnsignedRanges.clear();
8534 SignedRanges.clear();
8535 ExprValueMap.clear();
8537 ConstantMultipleCache.clear();
8538 PredicatedSCEVRewrites.clear();
8540 FoldCacheUser.clear();
8542void ScalarEvolution::visitAndClearUsers(
8546 while (!Worklist.
empty()) {
8553 if (It != ValueExprMap.
end()) {
8554 eraseValueFromMap(It->first);
8557 ConstantEvolutionLoopExitValue.erase(PN);
8571 while (!LoopWorklist.
empty()) {
8575 forgetBackedgeTakenCounts(CurrL,
false);
8576 forgetBackedgeTakenCounts(CurrL,
true);
8579 for (
auto I = PredicatedSCEVRewrites.begin();
8580 I != PredicatedSCEVRewrites.end();) {
8581 std::pair<const SCEV *, const Loop *> Entry =
I->first;
8582 if (Entry.second == CurrL)
8583 PredicatedSCEVRewrites.erase(
I++);
8588 auto LoopUsersItr = LoopUsers.find(CurrL);
8589 if (LoopUsersItr != LoopUsers.end())
8594 visitAndClearUsers(Worklist, Visited, ToForget);
8596 LoopPropertiesCache.erase(CurrL);
8599 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8601 forgetMemoizedResults(ToForget);
8618 visitAndClearUsers(Worklist, Visited, ToForget);
8620 forgetMemoizedResults(ToForget);
8632 struct InvalidationRootCollector {
8636 InvalidationRootCollector(
Loop *L) : L(L) {}
8638 bool follow(
const SCEV *S) {
8644 if (L->contains(AddRec->
getLoop()))
8649 bool isDone()
const {
return false; }
8652 InvalidationRootCollector
C(L);
8654 forgetMemoizedResults(
C.Roots);
8667 BlockDispositions.clear();
8668 LoopDispositions.clear();
8685 while (!Worklist.
empty()) {
8687 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8688 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8689 if (!LoopDispoRemoved && !BlockDispoRemoved)
8691 auto Users = SCEVUsers.find(Curr);
8692 if (
Users != SCEVUsers.end())
8705const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8709 if (!isComplete() || ExitNotTaken.
empty())
8720 for (
const auto &ENT : ExitNotTaken) {
8721 const SCEV *BECount = ENT.ExactNotTaken;
8724 "We should only have known counts for exiting blocks that dominate "
8727 Ops.push_back(BECount);
8732 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8733 "Predicate should be always true!");
8742const ScalarEvolution::ExitNotTakenInfo *
8743ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8744 const BasicBlock *ExitingBlock,
8745 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8746 for (
const auto &ENT : ExitNotTaken)
8747 if (ENT.ExitingBlock == ExitingBlock) {
8748 if (ENT.hasAlwaysTruePredicate())
8750 else if (Predicates) {
8760const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8762 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8763 if (!getConstantMax())
8766 for (
const auto &ENT : ExitNotTaken)
8767 if (!ENT.hasAlwaysTruePredicate()) {
8775 "No point in having a non-constant max backedge taken count!");
8776 return getConstantMax();
8779const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8781 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8789 for (
const auto &ENT : ExitNotTaken) {
8790 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8793 "We should only have known counts for exiting blocks that "
8799 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8800 "Predicate should be always true!");
8803 if (ExitCounts.
empty())
8812bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8814 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8815 return !ENT.hasAlwaysTruePredicate();
8817 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8833 this->ExactNotTaken = E = ConstantMaxNotTaken;
8834 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8839 "Exact is not allowed to be less precise than Constant Max");
8842 "Exact is not allowed to be less precise than Symbolic Max");
8845 "Symbolic Max is not allowed to be less precise than Constant Max");
8848 "No point in having a non-constant max backedge taken count!");
8850 for (
const auto PredList : PredLists)
8851 for (
const auto *
P : PredList) {
8859 "Backedge count should be int");
8862 "Max backedge count should be int");
8875ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8877 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8878 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8879 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8881 ExitNotTaken.reserve(ExitCounts.
size());
8882 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8883 std::back_inserter(ExitNotTaken),
8884 [&](
const EdgeExitInfo &EEI) {
8885 BasicBlock *ExitBB = EEI.first;
8886 const ExitLimit &EL = EEI.second;
8887 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
8888 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
8893 "No point in having a non-constant max backedge taken count!");
8897ScalarEvolution::BackedgeTakenInfo
8898ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
8899 bool AllowPredicates) {
8901 L->getExitingBlocks(ExitingBlocks);
8903 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8906 bool CouldComputeBECount =
true;
8908 const SCEV *MustExitMaxBECount =
nullptr;
8909 const SCEV *MayExitMaxBECount =
nullptr;
8910 bool MustExitMaxOrZero =
false;
8911 bool IsOnlyExit = ExitingBlocks.
size() == 1;
8923 if (ExitIfTrue == CI->
isZero())
8927 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
8929 assert((AllowPredicates || EL.Predicates.empty()) &&
8930 "Predicated exit limit when predicates are not allowed!");
8935 ++NumExitCountsComputed;
8939 CouldComputeBECount =
false;
8946 "Exact is known but symbolic isn't?");
8947 ++NumExitCountsNotComputed;
8962 DT.dominates(ExitBB, Latch)) {
8963 if (!MustExitMaxBECount) {
8964 MustExitMaxBECount = EL.ConstantMaxNotTaken;
8965 MustExitMaxOrZero = EL.MaxOrZero;
8968 EL.ConstantMaxNotTaken);
8972 MayExitMaxBECount = EL.ConstantMaxNotTaken;
8975 EL.ConstantMaxNotTaken);
8979 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
8983 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
8989 for (
const auto &Pair : ExitCounts) {
8991 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
8993 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
8994 {
L, AllowPredicates});
8996 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
8997 MaxBECount, MaxOrZero);
9000ScalarEvolution::ExitLimit
9001ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9002 bool IsOnlyExit,
bool AllowPredicates) {
9003 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9007 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9015 "It should have one successor in loop and one exit block!");
9026 if (!
L->contains(SBB)) {
9031 assert(Exit &&
"Exiting block must have at least one exit");
9032 return computeExitLimitFromSingleExitSwitch(
9033 L, SI, Exit, IsOnlyExit);
9040 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9041 bool AllowPredicates) {
9042 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9043 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9044 ControlsOnlyExit, AllowPredicates);
9047std::optional<ScalarEvolution::ExitLimit>
9048ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9049 bool ExitIfTrue,
bool ControlsOnlyExit,
9050 bool AllowPredicates) {
9052 (void)this->ExitIfTrue;
9053 (void)this->AllowPredicates;
9055 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9056 this->AllowPredicates == AllowPredicates &&
9057 "Variance in assumed invariant key components!");
9058 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9059 if (Itr == TripCountMap.end())
9060 return std::nullopt;
9064void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9066 bool ControlsOnlyExit,
9067 bool AllowPredicates,
9069 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9070 this->AllowPredicates == AllowPredicates &&
9071 "Variance in assumed invariant key components!");
9073 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9074 assert(InsertResult.second &&
"Expected successful insertion!");
9079ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9080 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9081 bool ControlsOnlyExit,
bool AllowPredicates) {
9083 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9087 ExitLimit EL = computeExitLimitFromCondImpl(
9088 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9089 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9093ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9094 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9095 bool ControlsOnlyExit,
bool AllowPredicates) {
9097 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9098 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates))
9099 return *LimitFromBinOp;
9105 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9106 if (EL.hasFullInfo() || !AllowPredicates)
9110 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9130 const WithOverflowInst *WO;
9145 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9146 ControlsOnlyExit, AllowPredicates);
9147 if (EL.hasAnyInfo())
9152 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9155std::optional<ScalarEvolution::ExitLimit>
9156ScalarEvolution::computeExitLimitFromCondFromBinOp(
9157 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9158 bool ControlsOnlyExit,
bool AllowPredicates) {
9167 return std::nullopt;
9172 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9173 ExitLimit EL0 = computeExitLimitFromCondCached(
9174 Cache, L, Op0, ExitIfTrue, ControlsOnlyExit && !EitherMayExit,
9176 ExitLimit EL1 = computeExitLimitFromCondCached(
9177 Cache, L, Op1, ExitIfTrue, ControlsOnlyExit && !EitherMayExit,
9181 const Constant *NeutralElement = ConstantInt::get(ExitCond->
getType(), IsAnd);
9183 return Op1 == NeutralElement ? EL0 : EL1;
9185 return Op0 == NeutralElement ? EL1 : EL0;
9190 if (EitherMayExit) {
9200 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9202 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9205 EL1.ConstantMaxNotTaken);
9207 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9209 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9212 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9216 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9217 BECount = EL0.ExactNotTaken;
9230 SymbolicMaxBECount =
9232 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9236ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9237 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9238 bool AllowPredicates) {
9250 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9252 if (EL.hasAnyInfo())
9255 auto *ExhaustiveCount =
9256 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9259 return ExhaustiveCount;
9261 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9264ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9265 const Loop *L, CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
9266 bool ControlsOnlyExit,
bool AllowPredicates) {
9291 ConstantRange CompRange =
9307 auto *InnerLHS =
LHS;
9309 InnerLHS = ZExt->getOperand();
9356 if (EL.hasAnyInfo())
9373 if (EL.hasAnyInfo())
return EL;
9405 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9407 if (EL.hasAnyInfo())
9423 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9425 if (EL.hasAnyInfo())
9436ScalarEvolution::ExitLimit
9437ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9439 BasicBlock *ExitingBlock,
9440 bool ControlsOnlyExit) {
9441 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9444 if (
Switch->getDefaultDest() == ExitingBlock)
9448 "Default case must not exit the loop!");
9454 if (EL.hasAnyInfo())
9466 "Evaluation of SCEV at constant didn't fold correctly?");
9470ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9480 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9486 auto MatchPositiveShift =
9489 using namespace PatternMatch;
9491 ConstantInt *ShiftAmt;
9493 OutOpCode = Instruction::LShr;
9495 OutOpCode = Instruction::AShr;
9497 OutOpCode = Instruction::Shl;
9512 auto MatchShiftRecurrence =
9514 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9529 if (MatchPositiveShift(
LHS, V, OpC)) {
9530 PostShiftOpCode = OpC;
9536 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9539 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9545 MatchPositiveShift(BEValue, OpLHS, OpCodeOut) &&
9552 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9557 if (!MatchShiftRecurrence(
LHS, PN, OpCode))
9569 ConstantInt *StableValue =
nullptr;
9574 case Instruction::AShr: {
9582 StableValue = ConstantInt::get(Ty, 0);
9584 StableValue = ConstantInt::get(Ty, -1,
true);
9590 case Instruction::LShr:
9591 case Instruction::Shl:
9601 "Otherwise cannot be an operand to a branch instruction");
9603 if (
Result->isZeroValue()) {
9605 const SCEV *UpperBound =
9622 if (
const Function *
F = CI->getCalledFunction())
9631 if (!L->contains(
I))
return false;
9636 return L->getHeader() ==
I->getParent();
9712 if (!
I)
return nullptr;
9725 std::vector<Constant*> Operands(
I->getNumOperands());
9727 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9731 if (!Operands[i])
return nullptr;
9736 if (!
C)
return nullptr;
9758 if (IncomingVal != CurrentVal) {
9761 IncomingVal = CurrentVal;
9773ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9776 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9785 DenseMap<Instruction *, Constant *> CurrentIterVals;
9787 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9793 for (PHINode &
PHI : Header->phis()) {
9795 CurrentIterVals[&
PHI] = StartCST;
9797 if (!CurrentIterVals.
count(PN))
9798 return RetVal =
nullptr;
9804 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9807 unsigned IterationNum = 0;
9809 for (; ; ++IterationNum) {
9810 if (IterationNum == NumIterations)
9811 return RetVal = CurrentIterVals[PN];
9815 DenseMap<Instruction *, Constant *> NextIterVals;
9820 NextIterVals[PN] = NextPHI;
9822 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9828 for (
const auto &
I : CurrentIterVals) {
9830 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9835 for (
const auto &
I : PHIsToCompute) {
9836 PHINode *
PHI =
I.first;
9839 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9842 if (NextPHI !=
I.second)
9843 StoppedEvolving =
false;
9848 if (StoppedEvolving)
9849 return RetVal = CurrentIterVals[PN];
9851 CurrentIterVals.swap(NextIterVals);
9855const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
9865 DenseMap<Instruction *, Constant *> CurrentIterVals;
9867 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9870 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
9872 for (PHINode &
PHI : Header->phis()) {
9874 CurrentIterVals[&
PHI] = StartCST;
9876 if (!CurrentIterVals.
count(PN))
9884 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
9891 if (CondVal->getValue() == uint64_t(ExitWhen)) {
9892 ++NumBruteForceTripCountsComputed;
9897 DenseMap<Instruction *, Constant *> NextIterVals;
9903 for (
const auto &
I : CurrentIterVals) {
9905 if (!
PHI ||
PHI->getParent() != Header)
continue;
9908 for (PHINode *
PHI : PHIsToCompute) {
9910 if (NextPHI)
continue;
9912 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9915 CurrentIterVals.
swap(NextIterVals);
9926 for (
auto &LS : Values)
9928 return LS.second ? LS.second : V;
9933 const SCEV *
C = computeSCEVAtScope(V, L);
9934 for (
auto &LS :
reverse(ValuesAtScopes[V]))
9935 if (LS.first == L) {
9938 ValuesAtScopesUsers[
C].push_back({L, V});
9949 switch (V->getSCEVType()) {
9982 assert(!
C->getType()->isPointerTy() &&
9983 "Can only have one pointer, and it must be last");
10010ScalarEvolution::getWithOperands(
const SCEV *S,
10011 SmallVectorImpl<const SCEV *> &NewOps) {
10045const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10046 switch (
V->getSCEVType()) {
10057 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10068 for (++i; i !=
e; ++i)
10112 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10114 if (OpAtScope !=
Ops[i]) {
10122 for (++i; i !=
e; ++i) {
10127 return getWithOperands(V, NewOps);
10142 const Loop *CurrLoop = this->LI[
I->getParent()];
10153 if (BackedgeTakenCount->
isZero()) {
10154 Value *InitValue =
nullptr;
10155 bool MultipleInitValues =
false;
10161 MultipleInitValues =
true;
10166 if (!MultipleInitValues && InitValue)
10175 unsigned InLoopPred =
10186 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10200 SmallVector<Constant *, 4> Operands;
10201 Operands.
reserve(
I->getNumOperands());
10202 bool MadeImprovement =
false;
10217 MadeImprovement |= OrigV != OpV;
10222 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10227 if (!MadeImprovement)
10248const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10250 return stripInjectiveFunctions(ZExt->getOperand());
10252 return stripInjectiveFunctions(SExt->getOperand());
10270 assert(
A != 0 &&
"A must be non-zero.");
10286 if (MinTZ < Mult2 && L->getLoopPredecessor())
10288 if (MinTZ < Mult2) {
10311 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10331static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10337 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10338 << *AddRec <<
'\n');
10341 if (!LC || !MC || !
NC) {
10342 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10343 return std::nullopt;
10349 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10357 N =
N.sext(NewWidth);
10358 M = M.sext(NewWidth);
10359 L = L.sext(NewWidth);
10376 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10377 <<
", multiplied by " <<
T <<
'\n');
10386 std::optional<APInt>
Y) {
10388 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10391 return XW.
slt(YW) ? *
X : *
Y;
10394 return std::nullopt;
10395 return X ? *
X : *
Y;
10412 return std::nullopt;
10413 unsigned W =
X->getBitWidth();
10433static std::optional<APInt>
10439 return std::nullopt;
10442 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10443 std::optional<APInt>
X =
10446 return std::nullopt;
10451 return std::nullopt;
10466static std::optional<APInt>
10470 "Starting value of addrec should be 0");
10471 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10472 <<
Range <<
", addrec " << *AddRec <<
'\n');
10476 "Addrec's initial value should be in range");
10482 return std::nullopt;
10492 auto SolveForBoundary =
10493 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10496 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10497 << Bound <<
" (before multiplying by " << M <<
")\n");
10500 std::optional<APInt> SO;
10503 "signed overflow\n");
10507 "unsigned overflow\n");
10508 std::optional<APInt> UO =
10511 auto LeavesRange = [&] (
const APInt &
X) {
10528 return {std::nullopt,
false};
10533 if (LeavesRange(*Min))
10534 return { Min,
true };
10535 std::optional<APInt> Max = Min == SO ? UO : SO;
10536 if (LeavesRange(*Max))
10537 return { Max,
true };
10540 return {std::nullopt,
true};
10547 auto SL = SolveForBoundary(
Lower);
10548 auto SU = SolveForBoundary(
Upper);
10551 if (!SL.second || !SU.second)
10552 return std::nullopt;
10595ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10597 bool ControlsOnlyExit,
10598 bool AllowPredicates) {
10609 if (
C->getValue()->isZero())
return C;
10613 const SCEVAddRecExpr *AddRec =
10616 if (!AddRec && AllowPredicates)
10622 if (!AddRec || AddRec->
getLoop() != L)
10633 return ExitLimit(R, R, R,
false, Predicates);
10691 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10717 const SCEV *
Exact =
10725 const SCEV *SymbolicMax =
10727 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10736 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10744 return ExitLimit(
E, M, S,
false, Predicates);
10747ScalarEvolution::ExitLimit
10748ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10756 if (!
C->getValue()->isZero())
10766std::pair<const BasicBlock *, const BasicBlock *>
10767ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10778 if (
const Loop *L = LI.getLoopFor(BB))
10779 return {
L->getLoopPredecessor(),
L->getHeader()};
10781 return {
nullptr, BB};
10790 if (
A ==
B)
return true;
10805 if (ComputesEqualValues(AI, BI))
10813 const SCEV *Op0, *Op1;
10832 auto TrivialCase = [&](
bool TriviallyTrue) {
10841 const SCEV *NewLHS, *NewRHS;
10865 return TrivialCase(
false);
10866 return TrivialCase(
true);
10889 const APInt &
RA = RC->getAPInt();
10891 bool SimplifiedByConstantRange =
false;
10896 return TrivialCase(
true);
10898 return TrivialCase(
false);
10907 Changed = SimplifiedByConstantRange =
true;
10911 if (!SimplifiedByConstantRange) {
10928 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
10934 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
10940 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
10946 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
10958 return TrivialCase(
true);
10960 return TrivialCase(
false);
11065 auto NonRecursive = [
this, OrNegative](
const SCEV *S) {
11067 return C->getAPInt().isPowerOf2() ||
11068 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11071 return isa<SCEVVScale>(S) && F.hasFnAttribute(Attribute::VScaleRange);
11074 if (NonRecursive(S))
11100 APInt C = Cst->getAPInt();
11101 return C.urem(M) == 0;
11109 const SCEV *SmodM =
11124 for (
auto *
A : Assumptions)
11125 if (
A->implies(
P, *
this))
11138std::pair<const SCEV *, const SCEV *>
11141 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11143 return { Start, Start };
11145 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11154 getUsedLoops(LHS, LoopsUsed);
11155 getUsedLoops(RHS, LoopsUsed);
11157 if (LoopsUsed.
empty())
11162 for (
const auto *L1 : LoopsUsed)
11163 for (
const auto *L2 : LoopsUsed)
11164 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11165 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11166 "Domination relationship is not a linear order");
11196 SplitRHS.second) &&
11208 if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
11212 return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11222 return std::nullopt;
11237 if (KnownWithoutContext)
11238 return KnownWithoutContext;
11245 return std::nullopt;
11251 const Loop *L = LHS->getLoop();
11256std::optional<ScalarEvolution::MonotonicPredicateType>
11259 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11265 auto ResultSwapped =
11268 assert(*ResultSwapped != *Result &&
11269 "monotonicity should flip as we flip the predicate");
11276std::optional<ScalarEvolution::MonotonicPredicateType>
11277ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11291 return std::nullopt;
11295 "Should be greater or less!");
11299 if (!LHS->hasNoUnsignedWrap())
11300 return std::nullopt;
11304 "Relational predicate is either signed or unsigned!");
11305 if (!
LHS->hasNoSignedWrap())
11306 return std::nullopt;
11308 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11316 return std::nullopt;
11319std::optional<ScalarEvolution::LoopInvariantPredicate>
11326 return std::nullopt;
11333 if (!ArLHS || ArLHS->
getLoop() != L)
11334 return std::nullopt;
11338 return std::nullopt;
11364 return std::nullopt;
11401 return std::nullopt;
11404std::optional<ScalarEvolution::LoopInvariantPredicate>
11409 Pred, LHS, RHS, L, CtxI, MaxIter))
11417 for (
auto *
Op :
UMin->operands())
11419 Pred, LHS, RHS, L, CtxI,
Op))
11421 return std::nullopt;
11424std::optional<ScalarEvolution::LoopInvariantPredicate>
11439 return std::nullopt;
11446 if (!AR || AR->
getLoop() != L)
11447 return std::nullopt;
11451 return std::nullopt;
11457 if (Step != One && Step != MinusOne)
11458 return std::nullopt;
11464 return std::nullopt;
11470 return std::nullopt;
11478 if (Step == MinusOne)
11482 return std::nullopt;
11488bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11494 auto CheckRange = [&](
bool IsSigned) {
11497 return RangeLHS.
icmp(Pred, RangeRHS);
11506 if (CheckRange(
true) || CheckRange(
false))
11515bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11522 auto MatchBinaryAddToConst = [
this](
const SCEV *
X,
const SCEV *
Y,
11523 APInt &OutC1, APInt &OutC2,
11525 const SCEV *XNonConstOp, *XConstOp;
11526 const SCEV *YNonConstOp, *YConstOp;
11530 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11533 XFlagsPresent = ExpectedFlags;
11538 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11541 YFlagsPresent = ExpectedFlags;
11544 if (YNonConstOp != XNonConstOp)
11552 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11555 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11615bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11637bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11638 const SCEV *
LHS,
const SCEV *
RHS) {
11643 return any_of(*BB, [&](
const Instruction &
I) {
11644 using namespace llvm::PatternMatch;
11649 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11663 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11668 "This cannot be done on broken IR!");
11671 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11680 if (LoopContinuePredicate && LoopContinuePredicate->
isConditional() &&
11681 isImpliedCond(Pred, LHS, RHS,
11683 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11688 if (WalkingBEDominatingConds)
11694 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11695 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11702 const SCEV *LoopCounter =
11710 for (
auto &AssumeVH : AC.assumptions()) {
11717 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11721 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11724 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11725 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11726 assert(DTN &&
"should reach the loop header before reaching the root!");
11729 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11737 if (!ContinuePredicate || !ContinuePredicate->
isConditional())
11751 assert(DT.dominates(DominatingEdge, Latch) &&
"should be!");
11753 if (isImpliedCond(Pred, LHS, RHS, Condition,
11767 if (!DT.isReachableFromEntry(BB))
11771 "This cannot be done on broken IR!");
11779 const bool ProvingStrictComparison =
11781 bool ProvedNonStrictComparison =
false;
11782 bool ProvedNonEquality =
false;
11785 if (!ProvedNonStrictComparison)
11786 ProvedNonStrictComparison = Fn(NonStrictPredicate);
11787 if (!ProvedNonEquality)
11789 if (ProvedNonStrictComparison && ProvedNonEquality)
11794 if (ProvingStrictComparison) {
11796 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
11798 if (SplitAndProve(ProofFn))
11803 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
11805 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
11807 if (ProvingStrictComparison) {
11809 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
11811 if (SplitAndProve(ProofFn))
11820 const Loop *ContainingLoop = LI.getLoopFor(BB);
11822 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
11826 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
11827 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
11839 for (
auto &AssumeVH : AC.assumptions()) {
11843 if (!DT.dominates(CI, BB))
11846 if (ProveViaCond(CI->getArgOperand(0),
false))
11852 F.getParent(), Intrinsic::experimental_guard);
11854 for (
const auto *GU : GuardDecl->users())
11856 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
11857 if (ProveViaCond(Guard->getArgOperand(0),
false))
11872 "LHS is not available at Loop Entry");
11874 "RHS is not available at Loop Entry");
11876 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11887 if (FoundCondValue ==
11891 if (!PendingLoopPredicates.insert(FoundCondValue).second)
11895 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
11898 const Value *Op0, *Op1;
11901 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
11905 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
11906 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
11910 if (!ICI)
return false;
11914 CmpPredicate FoundPred;
11923 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
11926bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
11927 const SCEV *
RHS, CmpPredicate FoundPred,
11928 const SCEV *FoundLHS,
const SCEV *FoundRHS,
11929 const Instruction *CtxI) {
11939 auto *WideType = FoundLHS->
getType();
11951 TruncFoundLHS, TruncFoundRHS, CtxI))
11977 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
11981bool ScalarEvolution::isImpliedCondBalancedTypes(
11982 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
11983 const SCEV *FoundLHS,
const SCEV *FoundRHS,
const Instruction *CtxI) {
11986 "Types should be balanced!");
11993 if (FoundLHS == FoundRHS)
11997 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12009 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12026 LHS, FoundLHS, FoundRHS, CtxI);
12028 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12050 assert(P1 != P2 &&
"Handled earlier!");
12054 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12058 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12061 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12062 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12063 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12068 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12079 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12080 CanonicalRHS, CanonicalFoundLHS,
12081 CanonicalFoundRHS);
12086 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12087 CanonicalRHS, CanonicalFoundLHS,
12088 CanonicalFoundRHS);
12095 const SCEVConstant *
C =
nullptr;
12096 const SCEV *
V =
nullptr;
12114 if (Min ==
C->getAPInt()) {
12119 APInt SharperMin = Min + 1;
12122 case ICmpInst::ICMP_SGE:
12123 case ICmpInst::ICMP_UGE:
12126 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12131 case ICmpInst::ICMP_SGT:
12132 case ICmpInst::ICMP_UGT:
12142 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12147 case ICmpInst::ICMP_SLE:
12148 case ICmpInst::ICMP_ULE:
12149 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12150 LHS, V, getConstant(SharperMin), CtxI))
12154 case ICmpInst::ICMP_SLT:
12155 case ICmpInst::ICMP_ULT:
12156 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12157 LHS, V, getConstant(Min), CtxI))
12171 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12175 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12178 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12185bool ScalarEvolution::splitBinaryAdd(
const SCEV *Expr,
12186 const SCEV *&L,
const SCEV *&R,
12195std::optional<APInt>
12202 APInt DiffMul(BW, 1);
12205 for (
unsigned I = 0;
I < 8; ++
I) {
12214 if (LAR->getLoop() != MAR->getLoop())
12215 return std::nullopt;
12219 if (!LAR->isAffine() || !MAR->isAffine())
12220 return std::nullopt;
12222 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12223 return std::nullopt;
12225 Less = LAR->getStart();
12226 More = MAR->getStart();
12231 auto MatchConstMul =
12232 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12237 return std::nullopt;
12239 if (
auto MatchedMore = MatchConstMul(More)) {
12240 if (
auto MatchedLess = MatchConstMul(
Less)) {
12241 if (MatchedMore->second == MatchedLess->second) {
12242 More = MatchedMore->first;
12243 Less = MatchedLess->first;
12244 DiffMul *= MatchedMore->second;
12255 Diff +=
C->getAPInt() * DiffMul;
12258 Diff -=
C->getAPInt() * DiffMul;
12261 Multiplicity[S] +=
Mul;
12263 auto Decompose = [&](
const SCEV *S,
int Mul) {
12270 Decompose(More, 1);
12271 Decompose(
Less, -1);
12275 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12276 for (
const auto &[S,
Mul] : Multiplicity) {
12281 return std::nullopt;
12283 }
else if (
Mul == -1) {
12285 return std::nullopt;
12288 return std::nullopt;
12292 if (NewMore == More || NewLess ==
Less)
12293 return std::nullopt;
12299 if (!More && !
Less)
12303 if (!More || !
Less)
12304 return std::nullopt;
12308 return std::nullopt;
12311bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12335 if (!L->contains(ContextBB) || !DT.
dominates(ContextBB, L->getLoopLatch()))
12346 if (!L->contains(ContextBB) || !DT.
dominates(ContextBB, L->getLoopLatch()))
12356bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12359 const SCEV *FoundLHS,
12360 const SCEV *FoundRHS) {
12369 if (!AddRecFoundLHS)
12376 const Loop *
L = AddRecFoundLHS->getLoop();
12377 if (L != AddRecLHS->getLoop())
12416 if (!RDiff || *LDiff != *RDiff)
12419 if (LDiff->isMinValue())
12422 APInt FoundRHSLimit;
12425 FoundRHSLimit = -(*RDiff);
12437bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12438 const SCEV *
RHS,
const SCEV *FoundLHS,
12439 const SCEV *FoundRHS,
unsigned Depth) {
12440 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12444 bool Erased = PendingMerges.erase(LPhi);
12445 assert(Erased &&
"Failed to erase LPhi!");
12449 bool Erased = PendingMerges.erase(RPhi);
12450 assert(Erased &&
"Failed to erase RPhi!");
12458 if (!PendingMerges.insert(Phi).second)
12472 if (!PendingMerges.insert(Phi).second)
12478 if (!LPhi && !RPhi)
12489 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12493 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12494 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12495 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12496 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12499 if (RPhi && RPhi->getParent() == LBB) {
12506 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12507 if (!ProvedEasily(L, R))
12518 auto *RLoop = RAR->
getLoop();
12519 auto *Predecessor = RLoop->getLoopPredecessor();
12520 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12522 if (!ProvedEasily(L1, RAR->
getStart()))
12524 auto *Latch = RLoop->getLoopLatch();
12525 assert(Latch &&
"Loop with AddRec with no latch?");
12546 if (
auto *Loop = LI.getLoopFor(LBB))
12549 if (!ProvedEasily(L,
RHS))
12556bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12559 const SCEV *FoundLHS,
12560 const SCEV *FoundRHS) {
12563 if (
RHS == FoundRHS) {
12568 if (
LHS != FoundLHS)
12575 Value *Shiftee, *ShiftValue;
12577 using namespace PatternMatch;
12578 if (
match(SUFoundRHS->getValue(),
12580 auto *ShifteeS =
getSCEV(Shiftee);
12598bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12600 const SCEV *FoundLHS,
12601 const SCEV *FoundRHS,
12602 const Instruction *CtxI) {
12603 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12605 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12607 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12608 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12610 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12614template <
typename MinMaxExprType>
12616 const SCEV *Candidate) {
12621 return is_contained(MinMaxExpr->operands(), Candidate);
12634 const SCEV *LStart, *RStart, *Step;
12684bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12686 const SCEV *FoundLHS,
12687 const SCEV *FoundRHS,
12691 "LHS and RHS have different sizes?");
12694 "FoundLHS and FoundRHS have different sizes?");
12728 auto GetOpFromSExt = [&](
const SCEV *S) {
12730 return Ext->getOperand();
12737 auto *OrigLHS =
LHS;
12738 auto *OrigFoundLHS = FoundLHS;
12739 LHS = GetOpFromSExt(
LHS);
12740 FoundLHS = GetOpFromSExt(FoundLHS);
12743 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
12746 FoundRHS,
Depth + 1);
12759 if (!LHSAddExpr->hasNoSignedWrap())
12762 auto *LL = LHSAddExpr->getOperand(0);
12763 auto *LR = LHSAddExpr->getOperand(1);
12767 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
12768 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
12773 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
12779 using namespace llvm::PatternMatch;
12798 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
12806 auto *DTy = Denominator->getType();
12807 auto *FRHSTy = FoundRHS->
getType();
12808 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
12827 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
12838 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
12840 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
12848 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
12881bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
12885 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
12888 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
12891bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
12894 const SCEV *FoundLHS,
12895 const SCEV *FoundRHS) {
12931 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
12937bool ScalarEvolution::isImpliedCondOperandsViaRanges(
12938 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
12939 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
12953 ConstantRange FoundLHSRange =
12957 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
12964 return LHSRange.
icmp(Pred, ConstRHS);
12967bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
12980 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
12988 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
12991bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
13003 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
13011 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
13023const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
13024 const SCEV *Stride,
13055 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13066 :
APIntOps::umax(MaxEnd, MinStart);
13073ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13074 const Loop *L,
bool IsSigned,
13075 bool ControlsOnlyExit,
bool AllowPredicates) {
13079 bool PredicatedIV =
false;
13084 auto canProveNUW = [&]() {
13087 if (!ControlsOnlyExit)
13108 Limit = Limit.
zext(OuterBitWidth);
13120 Type *Ty = ZExt->getType();
13131 if (!
IV && AllowPredicates) {
13136 PredicatedIV =
true;
13140 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13154 bool NoWrap = ControlsOnlyExit &&
IV->getNoWrapFlags(WrapType);
13157 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13162 if (!PositiveStride) {
13214 auto wouldZeroStrideBeUB = [&]() {
13226 if (!wouldZeroStrideBeUB()) {
13230 }
else if (!NoWrap) {
13233 if (canIVOverflowOnLT(
RHS, Stride, IsSigned))
13246 const SCEV *
Start =
IV->getStart();
13252 const SCEV *OrigStart =
Start;
13253 const SCEV *OrigRHS =
RHS;
13254 if (
Start->getType()->isPointerTy()) {
13265 const SCEV *End =
nullptr, *BECount =
nullptr,
13266 *BECountIfBackedgeTaken =
nullptr;
13269 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13270 RHSAddRec->getNoWrapFlags()) {
13283 const SCEV *RHSStart = RHSAddRec->getStart();
13284 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13296 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13305 BECountIfBackedgeTaken =
13310 if (BECount ==
nullptr) {
13315 const SCEV *MaxBECount = computeMaxBECountForLT(
13318 MaxBECount,
false , Predicates);
13325 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13352 const SCEV *Numerator =
13358 auto canProveRHSGreaterThanEqualStart = [&]() {
13377 auto *StartMinusOne =
13384 if (canProveRHSGreaterThanEqualStart()) {
13399 BECountIfBackedgeTaken =
13415 bool MayAddOverflow = [&] {
13461 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13475 if (!MayAddOverflow) {
13487 const SCEV *ConstantMaxBECount;
13488 bool MaxOrZero =
false;
13490 ConstantMaxBECount = BECount;
13491 }
else if (BECountIfBackedgeTaken &&
13496 ConstantMaxBECount = BECountIfBackedgeTaken;
13499 ConstantMaxBECount = computeMaxBECountForLT(
13507 const SCEV *SymbolicMaxBECount =
13509 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13513ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13514 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13515 bool ControlsOnlyExit,
bool AllowPredicates) {
13522 if (!
IV && AllowPredicates)
13529 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13533 bool NoWrap = ControlsOnlyExit &&
IV->getNoWrapFlags(WrapType);
13546 if (!Stride->
isOne() && !NoWrap)
13547 if (canIVOverflowOnGT(
RHS, Stride, IsSigned))
13550 const SCEV *
Start =
IV->getStart();
13551 const SCEV *End =
RHS;
13562 if (
Start->getType()->isPointerTy()) {
13597 const SCEV *ConstantMaxBECount =
13604 ConstantMaxBECount = BECount;
13605 const SCEV *SymbolicMaxBECount =
13608 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13614 if (
Range.isFullSet())
13619 if (!SC->getValue()->isZero()) {
13625 return ShiftedAddRec->getNumIterationsInRange(
13626 Range.subtract(SC->getAPInt()), SE);
13657 APInt ExitVal = (End +
A).udiv(
A);
13670 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13671 "Linear scev computation is off in a bad way!");
13702 assert(!
Last->isZero() &&
"Recurrency with zero step?");
13727 Ty = Store->getValueOperand()->getType();
13729 Ty = Load->getType();
13742 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13744 SE->ConstantEvolutionLoopExitValue.erase(PN);
13745 SE->eraseValueFromMap(getValPtr());
13749void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
13750 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13760 : CallbackVH(
V), SE(se) {}
13769 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
13771 LoopDispositions(64), BlockDispositions(64) {
13783 F.getParent(), Intrinsic::experimental_guard);
13784 HasGuards = GuardDecl && !GuardDecl->use_empty();
13788 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
13789 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
13790 ValueExprMap(
std::
move(Arg.ValueExprMap)),
13791 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
13792 PendingPhiRanges(
std::
move(Arg.PendingPhiRanges)),
13793 PendingMerges(
std::
move(Arg.PendingMerges)),
13794 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
13795 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
13796 PredicatedBackedgeTakenCounts(
13797 std::
move(Arg.PredicatedBackedgeTakenCounts)),
13798 BECountUsers(
std::
move(Arg.BECountUsers)),
13799 ConstantEvolutionLoopExitValue(
13800 std::
move(Arg.ConstantEvolutionLoopExitValue)),
13801 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
13802 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
13803 LoopDispositions(
std::
move(Arg.LoopDispositions)),
13804 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
13805 BlockDispositions(
std::
move(Arg.BlockDispositions)),
13806 SCEVUsers(
std::
move(Arg.SCEVUsers)),
13807 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
13808 SignedRanges(
std::
move(Arg.SignedRanges)),
13809 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
13810 UniquePreds(
std::
move(Arg.UniquePreds)),
13811 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
13812 LoopUsers(
std::
move(Arg.LoopUsers)),
13813 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
13814 FirstUnknown(Arg.FirstUnknown) {
13815 Arg.FirstUnknown =
nullptr;
13824 Tmp->~SCEVUnknown();
13826 FirstUnknown =
nullptr;
13828 ExprValueMap.clear();
13829 ValueExprMap.clear();
13831 BackedgeTakenCounts.clear();
13832 PredicatedBackedgeTakenCounts.clear();
13834 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
13835 assert(PendingPhiRanges.empty() &&
"getRangeRef garbage");
13836 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
13837 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
13838 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
13860 L->getHeader()->printAsOperand(OS,
false);
13864 L->getExitingBlocks(ExitingBlocks);
13865 if (ExitingBlocks.
size() != 1)
13866 OS <<
"<multiple exits> ";
13870 OS <<
"backedge-taken count is ";
13873 OS <<
"Unpredictable backedge-taken count.";
13876 if (ExitingBlocks.
size() > 1)
13877 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
13878 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
13886 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
13889 OS <<
"\n Predicates:\n";
13890 for (
const auto *
P : Predicates)
13898 L->getHeader()->printAsOperand(OS,
false);
13903 OS <<
"constant max backedge-taken count is ";
13906 OS <<
", actual taken count either this or zero.";
13908 OS <<
"Unpredictable constant max backedge-taken count. ";
13913 L->getHeader()->printAsOperand(OS,
false);
13918 OS <<
"symbolic max backedge-taken count is ";
13921 OS <<
", actual taken count either this or zero.";
13923 OS <<
"Unpredictable symbolic max backedge-taken count. ";
13927 if (ExitingBlocks.
size() > 1)
13928 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
13929 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
13939 OS <<
"\n predicated symbolic max exit count for "
13940 << ExitingBlock->
getName() <<
": ";
13942 OS <<
"\n Predicates:\n";
13943 for (
const auto *
P : Predicates)
13953 assert(!Preds.
empty() &&
"Different predicated BTC, but no predicates");
13955 L->getHeader()->printAsOperand(OS,
false);
13958 OS <<
"Predicated backedge-taken count is ";
13961 OS <<
"Unpredictable predicated backedge-taken count.";
13963 OS <<
" Predicates:\n";
13964 for (
const auto *
P : Preds)
13969 auto *PredConstantMax =
13971 if (PredConstantMax != ConstantBTC) {
13973 "different predicated constant max BTC but no predicates");
13975 L->getHeader()->printAsOperand(OS,
false);
13978 OS <<
"Predicated constant max backedge-taken count is ";
13981 OS <<
"Unpredictable predicated constant max backedge-taken count.";
13983 OS <<
" Predicates:\n";
13984 for (
const auto *
P : Preds)
13989 auto *PredSymbolicMax =
13991 if (SymbolicBTC != PredSymbolicMax) {
13993 "Different predicated symbolic max BTC, but no predicates");
13995 L->getHeader()->printAsOperand(OS,
false);
13998 OS <<
"Predicated symbolic max backedge-taken count is ";
14001 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14003 OS <<
" Predicates:\n";
14004 for (
const auto *
P : Preds)
14010 L->getHeader()->printAsOperand(OS,
false);
14034 OS <<
"Computable";
14044 OS <<
"DoesNotDominate";
14050 OS <<
"ProperlyDominates";
14067 OS <<
"Classifying expressions for: ";
14068 F.printAsOperand(OS,
false);
14083 const Loop *L = LI.getLoopFor(
I.getParent());
14098 OS <<
"\t\t" "Exits: ";
14101 OS <<
"<<Unknown>>";
14107 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14109 OS <<
"\t\t" "LoopDispositions: { ";
14115 Iter->getHeader()->printAsOperand(OS,
false);
14123 OS <<
"\t\t" "LoopDispositions: { ";
14129 InnerL->getHeader()->printAsOperand(OS,
false);
14140 OS <<
"Determining loop execution counts for: ";
14141 F.printAsOperand(OS,
false);
14149 auto &Values = LoopDispositions[S];
14150 for (
auto &V : Values) {
14151 if (V.getPointer() == L)
14156 auto &Values2 = LoopDispositions[S];
14158 if (V.getPointer() == L) {
14167ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14186 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14187 " dominate the contained loop's header?");
14214 bool HasVarying =
false;
14248 auto &Values = BlockDispositions[S];
14249 for (
auto &V : Values) {
14250 if (V.getPointer() == BB)
14255 auto &Values2 = BlockDispositions[S];
14257 if (V.getPointer() == BB) {
14266ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14295 bool Proper =
true;
14306 if (Instruction *
I =
14308 if (
I->getParent() == BB)
14310 if (DT.properlyDominates(
I->getParent(), BB))
14333void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14336 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14337 auto It = BECounts.find(L);
14338 if (It != BECounts.end()) {
14339 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14340 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14342 auto UserIt = BECountUsers.find(S);
14343 assert(UserIt != BECountUsers.end());
14348 BECounts.erase(It);
14356 while (!Worklist.
empty()) {
14358 auto Users = SCEVUsers.find(Curr);
14359 if (
Users != SCEVUsers.end())
14360 for (
const auto *User :
Users->second)
14361 if (ToForget.
insert(User).second)
14365 for (
const auto *S : ToForget)
14366 forgetMemoizedResultsImpl(S);
14368 for (
auto I = PredicatedSCEVRewrites.begin();
14369 I != PredicatedSCEVRewrites.end();) {
14370 std::pair<const SCEV *, const Loop *>
Entry =
I->first;
14371 if (ToForget.count(
Entry.first))
14372 PredicatedSCEVRewrites.erase(
I++);
14378void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14379 LoopDispositions.erase(S);
14380 BlockDispositions.erase(S);
14381 UnsignedRanges.erase(S);
14382 SignedRanges.erase(S);
14383 HasRecMap.erase(S);
14384 ConstantMultipleCache.erase(S);
14387 UnsignedWrapViaInductionTried.erase(AR);
14388 SignedWrapViaInductionTried.erase(AR);
14391 auto ExprIt = ExprValueMap.find(S);
14392 if (ExprIt != ExprValueMap.end()) {
14393 for (
Value *V : ExprIt->second) {
14394 auto ValueIt = ValueExprMap.find_as(V);
14395 if (ValueIt != ValueExprMap.end())
14396 ValueExprMap.erase(ValueIt);
14398 ExprValueMap.erase(ExprIt);
14401 auto ScopeIt = ValuesAtScopes.find(S);
14402 if (ScopeIt != ValuesAtScopes.end()) {
14403 for (
const auto &Pair : ScopeIt->second)
14406 std::make_pair(Pair.first, S));
14407 ValuesAtScopes.erase(ScopeIt);
14410 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14411 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14412 for (
const auto &Pair : ScopeUserIt->second)
14413 llvm::erase(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
14414 ValuesAtScopesUsers.erase(ScopeUserIt);
14417 auto BEUsersIt = BECountUsers.find(S);
14418 if (BEUsersIt != BECountUsers.end()) {
14420 auto Copy = BEUsersIt->second;
14421 for (
const auto &Pair : Copy)
14422 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14423 BECountUsers.erase(BEUsersIt);
14426 auto FoldUser = FoldCacheUser.find(S);
14427 if (FoldUser != FoldCacheUser.end())
14428 for (
auto &KV : FoldUser->second)
14429 FoldCache.erase(KV);
14430 FoldCacheUser.erase(S);
14434ScalarEvolution::getUsedLoops(
const SCEV *S,
14436 struct FindUsedLoops {
14437 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14438 : LoopsUsed(LoopsUsed) {}
14439 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14440 bool follow(
const SCEV *S) {
14446 bool isDone()
const {
return false; }
14449 FindUsedLoops
F(LoopsUsed);
14450 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14453void ScalarEvolution::getReachableBlocks(
14456 Worklist.
push_back(&F.getEntryBlock());
14457 while (!Worklist.
empty()) {
14459 if (!Reachable.
insert(BB).second)
14467 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14474 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14478 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14513 SCEVMapper SCM(SE2);
14515 SE2.getReachableBlocks(ReachableBlocks, F);
14517 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14535 while (!LoopStack.
empty()) {
14541 if (!ReachableBlocks.
contains(L->getHeader()))
14546 auto It = BackedgeTakenCounts.find(L);
14547 if (It == BackedgeTakenCounts.end())
14551 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14571 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14572 if (Delta && !Delta->
isZero()) {
14573 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14574 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14575 dbgs() <<
"New: " << *NewBECount <<
"\n";
14576 dbgs() <<
"Delta: " << *Delta <<
"\n";
14584 while (!Worklist.
empty()) {
14586 if (ValidLoops.
insert(L).second)
14587 Worklist.
append(L->begin(), L->end());
14589 for (
const auto &KV : ValueExprMap) {
14594 "AddRec references invalid loop");
14599 auto It = ExprValueMap.find(KV.second);
14600 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14601 dbgs() <<
"Value " << *KV.first
14602 <<
" is in ValueExprMap but not in ExprValueMap\n";
14607 if (!ReachableBlocks.
contains(
I->getParent()))
14609 const SCEV *OldSCEV = SCM.visit(KV.second);
14611 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14612 if (Delta && !Delta->
isZero()) {
14613 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14614 <<
"Old: " << *OldSCEV <<
"\n"
14615 <<
"New: " << *NewSCEV <<
"\n"
14616 <<
"Delta: " << *Delta <<
"\n";
14622 for (
const auto &KV : ExprValueMap) {
14623 for (
Value *V : KV.second) {
14624 const SCEV *S = ValueExprMap.lookup(V);
14626 dbgs() <<
"Value " << *V
14627 <<
" is in ExprValueMap but not in ValueExprMap\n";
14630 if (S != KV.first) {
14631 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14632 << *KV.first <<
"\n";
14639 for (
const auto &S : UniqueSCEVs) {
14644 auto It = SCEVUsers.find(
Op);
14645 if (It != SCEVUsers.end() && It->second.count(&S))
14647 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14648 <<
" is not being tracked!\n";
14654 for (
const auto &ValueAndVec : ValuesAtScopes) {
14656 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14657 const Loop *L = LoopAndValueAtScope.first;
14658 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
14660 auto It = ValuesAtScopesUsers.find(ValueAtScope);
14661 if (It != ValuesAtScopesUsers.end() &&
14664 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14665 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14671 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14672 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14673 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14674 const Loop *L = LoopAndValue.first;
14675 const SCEV *
Value = LoopAndValue.second;
14677 auto It = ValuesAtScopes.find(
Value);
14678 if (It != ValuesAtScopes.end() &&
14679 is_contained(It->second, std::make_pair(L, ValueAtScope)))
14681 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14682 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14688 auto VerifyBECountUsers = [&](
bool Predicated) {
14690 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14691 for (
const auto &LoopAndBEInfo : BECounts) {
14692 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14693 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14695 auto UserIt = BECountUsers.find(S);
14696 if (UserIt != BECountUsers.end() &&
14697 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14699 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14700 <<
" missing from BECountUsers\n";
14707 VerifyBECountUsers(
false);
14708 VerifyBECountUsers(
true);
14711 for (
auto &[S, Values] : LoopDispositions) {
14712 for (
auto [
Loop, CachedDisposition] : Values) {
14714 if (CachedDisposition != RecomputedDisposition) {
14715 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
14716 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
14717 << RecomputedDisposition <<
"\n";
14724 for (
auto &[S, Values] : BlockDispositions) {
14725 for (
auto [BB, CachedDisposition] : Values) {
14727 if (CachedDisposition != RecomputedDisposition) {
14728 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
14729 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
14730 <<
", actual " << RecomputedDisposition <<
"\n";
14737 for (
auto [
FoldID, Expr] : FoldCache) {
14738 auto I = FoldCacheUser.find(Expr);
14739 if (
I == FoldCacheUser.end()) {
14740 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
14745 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
14749 for (
auto [Expr, IDs] : FoldCacheUser) {
14750 for (
auto &
FoldID : IDs) {
14753 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
14758 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
14759 <<
" != " << *Expr <<
"!\n";
14770 for (
auto [S, Multiple] : ConstantMultipleCache) {
14772 if ((Multiple != 0 && RecomputedMultiple != 0 &&
14773 Multiple.
urem(RecomputedMultiple) != 0 &&
14774 RecomputedMultiple.
urem(Multiple) != 0)) {
14775 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
14776 << *S <<
" : Computed " << RecomputedMultiple
14777 <<
" but cache contains " << Multiple <<
"!\n";
14785 FunctionAnalysisManager::Invalidator &Inv) {
14817 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
14818 <<
F.getName() <<
"':\n";
14824 "Scalar Evolution Analysis",
false,
true)
14873 const SCEV *LHS,
const SCEV *RHS) {
14875 assert(LHS->getType() == RHS->getType() &&
14876 "Type mismatch between LHS and RHS");
14879 ID.AddInteger(Pred);
14880 ID.AddPointer(LHS);
14881 ID.AddPointer(RHS);
14882 void *IP =
nullptr;
14883 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
14887 UniquePreds.InsertNode(Eq, IP);
14898 ID.AddInteger(AddedFlags);
14899 void *IP =
nullptr;
14900 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
14902 auto *OF =
new (SCEVAllocator)
14904 UniquePreds.InsertNode(OF, IP);
14924 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
14925 return Rewriter.visit(S);
14931 for (
const auto *Pred : U->getPredicates())
14933 if (IPred->getLHS() == Expr &&
14935 return IPred->getRHS();
14937 if (IPred->getLHS() == Expr &&
14938 IPred->getPredicate() == ICmpInst::ICMP_EQ)
14939 return IPred->getRHS();
14942 return convertToAddRecWithPreds(Expr);
14945 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
14961 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
14978 explicit SCEVPredicateRewriter(
14979 const Loop *L, ScalarEvolution &SE,
14980 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
14981 const SCEVPredicate *Pred)
14982 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
14984 bool addOverflowAssumption(
const SCEVPredicate *
P) {
14987 return Pred && Pred->
implies(
P, SE);
14993 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
14996 return addOverflowAssumption(
A);
15005 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15009 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15011 if (!PredicatedRewrite)
15013 for (
const auto *
P : PredicatedRewrite->second){
15016 if (L != WP->getExpr()->getLoop())
15019 if (!addOverflowAssumption(
P))
15022 return PredicatedRewrite->first;
15025 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15026 const SCEVPredicate *Pred;
15035 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15042 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15062 if (!Step->
isOne())
15087 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15088 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15101 return Op->LHS == LHS &&
Op->RHS == RHS;
15108 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15110 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15135 const SCEV *Start = AR->getStart();
15136 const SCEV *OpStart =
Op->AR->getStart();
15141 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15144 const SCEV *Step = AR->getStepRecurrence(SE);
15145 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15198 if (Step->getValue()->getValue().isNonNegative())
15202 return ImpliedFlags;
15209 for (
const auto *
P : Preds)
15222 return this->implies(I, SE);
15230 for (
const auto *Pred : Preds)
15231 Pred->print(OS,
Depth);
15236 for (
const auto *Pred : Set->Preds)
15244 bool CheckImplies = Preds.
size() < 16;
15247 if (CheckImplies &&
implies(
N, SE))
15253 for (
auto *
P : Preds) {
15254 if (CheckImplies &&
N->implies(
P, SE))
15258 Preds = std::move(PrunedPreds);
15259 Preds.push_back(
N);
15266 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15271 for (
const auto *
Op :
Ops)
15276 SCEVUsers[
Op].insert(
User);
15280 const SCEV *Expr = SE.getSCEV(V);
15285 RewriteEntry &Entry = RewriteMap[Expr];
15288 if (Entry.second && Generation == Entry.first)
15289 return Entry.second;
15294 Expr = Entry.second;
15296 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15297 Entry = {Generation, NewSCEV};
15303 if (!BackedgeCount) {
15305 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15306 for (
const auto *
P : Preds)
15309 return BackedgeCount;
15313 if (!SymbolicMaxBackedgeCount) {
15315 SymbolicMaxBackedgeCount =
15316 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15317 for (
const auto *
P : Preds)
15320 return SymbolicMaxBackedgeCount;
15324 if (!SmallConstantMaxTripCount) {
15326 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15327 for (
const auto *
P : Preds)
15330 return *SmallConstantMaxTripCount;
15334 if (Preds->implies(&Pred, SE))
15339 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15340 updateGeneration();
15347void PredicatedScalarEvolution::updateGeneration() {
15349 if (++Generation == 0) {
15350 for (
auto &
II : RewriteMap) {
15351 const SCEV *Rewritten =
II.second.second;
15368 auto II = FlagsMap.insert({V, Flags});
15381 auto II = FlagsMap.find(V);
15383 if (
II != FlagsMap.end())
15392 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15397 for (
const auto *
P : NewPreds)
15400 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15406 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15409 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {
15410 for (
auto I :
Init.FlagsMap)
15411 FlagsMap.insert(
I);
15416 for (
auto *BB : L.getBlocks())
15417 for (
auto &
I : *BB) {
15418 if (!SE.isSCEVable(
I.getType()))
15421 auto *Expr = SE.getSCEV(&
I);
15422 auto II = RewriteMap.find(Expr);
15424 if (
II == RewriteMap.end())
15428 if (
II->second.second == Expr)
15433 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15441 LoopGuards Guards(SE);
15449void ScalarEvolution::LoopGuards::collectFromPHI(
15457 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15458 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15472 auto &RewriteMap =
G->second.RewriteMap;
15473 if (RewriteMap.empty())
15475 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15476 if (S == RewriteMap.end())
15482 return {C0, SM->getSCEVType()};
15485 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15486 MinMaxPattern P2) -> MinMaxPattern {
15487 auto [C1,
T1] =
P1;
15488 auto [C2, T2] = P2;
15489 if (!C1 || !C2 ||
T1 != T2)
15493 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15495 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15497 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15499 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15504 auto P = GetMinMaxConst(0);
15505 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15508 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15511 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15514 Guards.RewriteMap.insert({
LHS,
RHS});
15522 const APInt &DivisorVal,
15524 const APInt *ExprVal;
15537 const APInt &DivisorVal,
15539 const APInt *ExprVal;
15547 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15561 const SCEV *URemRHS =
nullptr;
15565 const SCEV *Multiple =
15567 DivInfo[URemLHS] = Multiple;
15569 Multiples[URemLHS] =
C->getAPInt();
15589 auto IsMinMaxSCEVWithNonNegativeConstant =
15593 if (
MinMax->getNumOperands() != 2)
15596 if (
C->getAPInt().isNegative())
15598 SCTy =
MinMax->getSCEVType();
15607 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15609 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15614 auto *DivisibleExpr =
15622void ScalarEvolution::LoopGuards::collectFromBlock(
15624 const BasicBlock *
Block,
const BasicBlock *Pred,
15632 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15643 &ExprsToRewrite]() {
15644 const SCEVConstant *C1;
15657 if (ExactRegion.isWrappedSet() || ExactRegion.isFullSet())
15659 auto [
I,
Inserted] = RewriteMap.try_emplace(LHSUnknown);
15660 const SCEV *RewrittenLHS =
Inserted ? LHSUnknown :
I->second;
15668 if (MatchRangeCheckIdiom())
15685 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15687 if (From == FromRewritten)
15689 RewriteMap[From] = To;
15695 auto GetMaybeRewritten = [&](
const SCEV *S) {
15696 return RewriteMap.lookup_or(S, S);
15699 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15701 const APInt &DividesBy =
15716 switch (Predicate) {
15745 SmallPtrSet<const SCEV *, 16> Visited;
15747 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
15751 while (!Worklist.
empty()) {
15755 if (!Visited.
insert(From).second)
15757 const SCEV *FromRewritten = GetMaybeRewritten(From);
15758 const SCEV *To =
nullptr;
15760 switch (Predicate) {
15765 EnqueueOperands(
UMax);
15771 EnqueueOperands(
SMax);
15777 EnqueueOperands(
UMin);
15783 EnqueueOperands(
SMin);
15791 const SCEV *OneAlignedUp =
15793 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
15805 const SCEVConstant *
C;
15814 Guards.NotEqual.insert({
LHS,
RHS});
15823 AddRewrite(From, FromRewritten, To);
15840 SE.F.
getParent(), Intrinsic::experimental_guard);
15842 for (
const auto *GU : GuardDecl->users())
15844 if (Guard->getFunction() ==
Block->getParent() &&
15853 unsigned NumCollectedConditions = 0;
15855 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
15857 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
15859 const BranchInst *LoopEntryPredicate =
15866 NumCollectedConditions++;
15870 if (
Depth > 0 && NumCollectedConditions == 2)
15878 if (Pair.second->hasNPredecessorsOrMore(2) &&
15880 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
15881 for (
auto &Phi : Pair.second->phis())
15892 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
15893 SmallVector<Value *, 8> Worklist;
15894 SmallPtrSet<Value *, 8> Visited;
15896 while (!Worklist.
empty()) {
15903 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
15927 DenseMap<const SCEV *, APInt> Multiples;
15929 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
15936 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
15937 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
15941 for (
const auto &[K, Divisor] : Multiples) {
15942 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
15943 Guards.RewriteMap[
K] =
15945 Guards.
rewrite(K), Divisor, SE),
15954 Guards.PreserveNUW =
true;
15955 Guards.PreserveNSW =
true;
15956 for (
const SCEV *Expr : ExprsToRewrite) {
15957 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
15958 Guards.PreserveNUW &=
15960 Guards.PreserveNSW &=
15967 if (ExprsToRewrite.size() > 1) {
15968 for (
const SCEV *Expr : ExprsToRewrite) {
15969 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
15970 Guards.RewriteMap.erase(Expr);
15971 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
15980 class SCEVLoopGuardRewriter
15991 NotEqual(Guards.NotEqual) {
15992 if (Guards.PreserveNUW)
15994 if (Guards.PreserveNSW)
16001 return Map.lookup_or(Expr, Expr);
16005 if (
const SCEV *S = Map.lookup(Expr))
16012 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16013 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16014 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16016 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16017 if (
const SCEV *S = Map.lookup(NarrowExt))
16018 return SE.getZeroExtendExpr(S, Ty);
16019 Bitwidth = Bitwidth / 2;
16027 if (
const SCEV *S = Map.lookup(Expr))
16034 if (
const SCEV *S = Map.lookup(Expr))
16040 if (
const SCEV *S = Map.lookup(Expr))
16048 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16049 const SCEV *LHS, *RHS;
16053 if (NotEqual.contains({LHS, RHS})) {
16055 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16056 return SE.getUMaxExpr(OneAlignedUp, S);
16063 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16074 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16075 return SE.getAddExpr(
16078 if (
const SCEV *S = Map.lookup(
Add))
16079 return SE.getAddExpr(Expr->
getOperand(0), S);
16091 : SE.getAddExpr(Operands,
16107 : SE.getMulExpr(Operands,
16113 if (RewriteMap.empty() && NotEqual.empty())
16116 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16117 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.
This file defines a hash set that can be used to remove duplication of nodes in a graph.
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
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
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 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
void visit(MachineFunction &MF, MachineBasicBlock &Start, std::function< void(MachineBasicBlock *)> op)
This file provides utility classes that use RAII to save and restore values.
bool SCEVMinMaxExprContains(const SCEV *Root, const SCEV *OperandToFind, SCEVTypes RootKind)
static cl::opt< unsigned > MaxAddRecSize("scalar-evolution-max-add-rec-size", cl::Hidden, cl::desc("Max coefficients in AddRec during evolving"), cl::init(8))
static cl::opt< unsigned > RangeIterThreshold("scev-range-iter-threshold", cl::Hidden, cl::desc("Threshold for switching to iteratively computing SCEV ranges"), cl::init(32))
static const Loop * isIntegerLoopHeaderPHI(const PHINode *PN, LoopInfo &LI)
static unsigned getConstantTripCount(const SCEVConstant *ExitCount)
static int CompareValueComplexity(const LoopInfo *const LI, Value *LV, Value *RV, unsigned Depth)
Compare the two values LV and RV in terms of their "complexity" where "complexity" is a partial (and ...
static const SCEV * getNextSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static void PushLoopPHIs(const Loop *L, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push PHI nodes in the header of the given loop onto the given Worklist.
static void insertFoldCacheEntry(const ScalarEvolution::FoldID &ID, const SCEV *S, DenseMap< ScalarEvolution::FoldID, const SCEV * > &FoldCache, DenseMap< const SCEV *, SmallVector< ScalarEvolution::FoldID, 2 > > &FoldCacheUser)
static cl::opt< bool > ClassifyExpressions("scalar-evolution-classify-expressions", cl::Hidden, cl::init(true), cl::desc("When printing analysis, include information on every instruction"))
static bool 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 BrPHIToSelect(DominatorTree &DT, BranchInst *BI, PHINode *Merge, Value *&C, Value *&LHS, Value *&RHS)
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 void GroupByComplexity(SmallVectorImpl< const SCEV * > &Ops, LoopInfo *LI, DominatorTree &DT)
Given a list of SCEV objects, order them by their complexity, and group objects of the same complexit...
static const SCEV * constantFoldAndGroupOps(ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT, SmallVectorImpl< const SCEV * > &Ops, FoldT Fold, IsIdentityT IsIdentity, IsAbsorberT IsAbsorber)
Performs a number of common optimizations on the passed Ops.
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 bool MatchBinarySub(const SCEV *S, const SCEV *&LHS, const SCEV *&RHS)
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 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 hasHugeExpression(ArrayRef< const SCEV * > Ops)
Returns true if Ops contains a huge SCEV (the subtree of S contains at least HugeExprThreshold nodes)...
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 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 std::optional< std::tuple< APInt, APInt, APInt, APInt, unsigned > > GetQuadraticEquation(const SCEVAddRecExpr *AddRec)
For a given quadratic addrec, generate coefficients of the corresponding quadratic equation,...
static bool isKnownPredicateExtendIdiom(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
static std::optional< BinaryOp > MatchBinaryOp(Value *V, const DataLayout &DL, AssumptionCache &AC, const DominatorTree &DT, const Instruction *CxtI)
Try to map V into a BinaryOp, and return std::nullopt on failure.
static std::optional< APInt > SolveQuadraticAddRecExact(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE)
Let c(n) be the value of the quadratic chrec {L,+,M,+,N} after n iterations.
static std::optional< APInt > TruncIfPossible(std::optional< APInt > X, unsigned BitWidth)
Helper function to truncate an optional APInt to a given BitWidth.
static cl::opt< unsigned > MaxSCEVCompareDepth("scalar-evolution-max-scev-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV complexity comparisons"), cl::init(32))
static APInt extractConstantWithoutWrapping(ScalarEvolution &SE, const SCEVConstant *ConstantTerm, const SCEVAddExpr *WholeAddExpr)
static cl::opt< unsigned > MaxConstantEvolvingDepth("scalar-evolution-max-constant-evolving-depth", cl::Hidden, cl::desc("Maximum depth of recursive constant evolving"), cl::init(32))
static ConstantRange getRangeForAffineARHelper(APInt Step, const ConstantRange &StartRange, const APInt &MaxBECount, bool Signed)
static 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 SCEV::NoWrapFlags StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, ArrayRef< const SCEV * > Ops, SCEV::NoWrapFlags Flags)
static Type * isSimpleCastedPHI(const SCEV *Op, const SCEVUnknown *SymbolicPHI, bool &Signed, ScalarEvolution &SE)
Helper function to createAddRecFromPHIWithCasts.
static Constant * EvaluateExpression(Value *V, const Loop *L, DenseMap< Instruction *, Constant * > &Vals, const DataLayout &DL, const TargetLibraryInfo *TLI)
EvaluateExpression - Given an expression that passes the getConstantEvolvingPHI predicate,...
static const SCEV * getPreviousSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static const SCEV * MatchNotExpr(const SCEV *Expr)
If Expr computes ~A, return A else return nullptr.
static cl::opt< unsigned > MaxValueCompareDepth("scalar-evolution-max-value-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive value complexity comparisons"), cl::init(2))
static const SCEV * applyDivisibilityOnMinMaxExpr(const SCEV *MinMaxExpr, APInt Divisor, ScalarEvolution &SE)
static cl::opt< bool, true > VerifySCEVOpt("verify-scev", cl::Hidden, cl::location(VerifySCEV), cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"))
static const SCEV * getSignedOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static cl::opt< unsigned > MaxArithDepth("scalar-evolution-max-arith-depth", cl::Hidden, cl::desc("Maximum depth of recursive arithmetics"), cl::init(32))
static bool HasSameValue(const SCEV *A, const SCEV *B)
SCEV structural equivalence is usually sufficient for testing whether two expressions are equal,...
static uint64_t Choose(uint64_t n, uint64_t k, bool &Overflow)
Compute the result of "n choose k", the binomial coefficient.
static std::optional< int > CompareSCEVComplexity(const LoopInfo *const LI, const SCEV *LHS, const SCEV *RHS, DominatorTree &DT, unsigned Depth=0)
static bool CollectAddOperandsWithScales(SmallDenseMap< const SCEV *, APInt, 16 > &M, SmallVectorImpl< const SCEV * > &NewOps, APInt &AccumulatedConstant, ArrayRef< const SCEV * > 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 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?
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 TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
static SymbolRef::Type getType(const Symbol *Sym)
LocallyHashedType DenseMapInfo< LocallyHashedType >::Empty
static std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
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]
Class for arbitrary precision integers.
LLVM_ABI APInt umul_ov(const APInt &RHS, bool &Overflow) const
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
uint64_t getZExtValue() const
Get zero extended value.
void setHighBits(unsigned hiBits)
Set the top hiBits bits.
LLVM_ABI APInt getHiBits(unsigned numBits) const
Compute an APInt containing numBits highbits from this APInt.
unsigned getActiveBits() const
Compute the number of active bits in the value.
LLVM_ABI APInt trunc(unsigned width) const
Truncate to new width.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
APInt abs() const
Get the absolute value.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool isSignMask() const
Check if the APInt's value is returned by getSignMask.
LLVM_ABI APInt urem(const APInt &RHS) const
Unsigned remainder operation.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
bool isNegative() const
Determine sign of this APInt.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
bool isNonPositive() const
Determine if this APInt Value is non-positive (<= 0).
unsigned countTrailingZeros() const
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
unsigned logBase2() const
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
LLVM_ABI APInt multiplicativeInverse() const
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
LLVM_ABI APInt sext(unsigned width) const
Sign extend to a new width.
APInt shl(unsigned shiftAmt) const
Left-shift function.
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
bool isSignBitSet() const
Determine if sign bit of this APInt is set.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
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()
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
size - 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_ABI bool isSingleEdge() const
Check if this is the only edge between Start and End.
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 if the block is well formed or null if the block is not well forme...
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
Conditional or Unconditional Branch instruction.
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
Value * getCondition() 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.
static LLVM_ABI Constant * getNot(Constant *C)
static LLVM_ABI Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static Constant * getGetElementPtr(Type *Ty, Constant *C, ArrayRef< Constant * > IdxList, GEPNoWrapFlags NW=GEPNoWrapFlags::none(), std::optional< ConstantRange > InRange=std::nullopt, Type *OnlyIfReducedTy=nullptr)
Getelementptr form.
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
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
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.
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID,...
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Represents flags for the getelementptr instruction/expression.
bool hasNoUnsignedSignedWrap() const
bool hasNoUnsignedWrap() const
static GEPNoWrapFlags none()
static LLVM_ABI Type * getTypeAtIndex(Type *Ty, Value *Idx)
Return the type of the element at the given index of an indexable type.
Module * getParent()
Get the module that this global value is contained inside of...
static bool isPrivateLinkage(LinkageTypes Linkage)
static bool isInternalLinkage(LinkageTypes Linkage)
This instruction compares its operands according to the predicate given to the constructor.
CmpPredicate getCmpPredicate() const
static bool isGE(Predicate P)
Return true if the predicate is SGE or UGE.
CmpPredicate getSwappedCmpPredicate() const
static LLVM_ABI bool compare(const APInt &LHS, const APInt &RHS, ICmpInst::Predicate Pred)
Return result of LHS Pred RHS comparison.
static bool isLT(Predicate P)
Return true if the predicate is SLT or ULT.
CmpPredicate getInverseCmpPredicate() const
Predicate getNonStrictCmpPredicate() const
For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.
static bool isGT(Predicate P)
Return true if the predicate is SGT or UGT.
Predicate getFlippedSignednessPredicate() const
For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->EQ.
static CmpPredicate getInverseCmpPredicate(CmpPredicate Pred)
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
static bool isLE(Predicate P)
Return true if the predicate is SLE or ULE.
LLVM_ABI bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
LLVM_ABI bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
LLVM_ABI bool isIdenticalToWhenDefined(const Instruction *I, bool IntersectAttrs=false) const LLVM_READONLY
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...
Class to represent integer types.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
An instruction for reading from memory.
Analysis pass that exposes the LoopInfo for a function.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getHeader() const
unsigned getLoopDepth() const
Return the nesting level of this loop.
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
A Module instance is used to store all the information related to an LLVM module.
unsigned getOpcode() const
Return the opcode for this Instruction or ConstantExpr.
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
bool hasNoSignedWrap() const
Test whether this operation is known to never undergo signed overflow, aka the nsw property.
bool hasNoUnsignedWrap() const
Test whether this operation is known to never undergo unsigned overflow, aka the nuw property.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
PointerIntPair - This class implements a pair of a pointer and small integer.
static PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the default address space (address sp...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
LLVM_ABI void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
LLVM_ABI const SCEVPredicate & getPredicate() const
LLVM_ABI const SCEV * getPredicatedSCEV(const SCEV *Expr)
Returns the rewritten SCEV for Expr in the context of the current SCEV predicate.
LLVM_ABI bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've proved that V doesn't wrap by means of a SCEV predicate.
LLVM_ABI void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Proves that V doesn't overflow by adding SCEV predicate.
LLVM_ABI void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
LLVM_ABI bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds.
LLVM_ABI PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
LLVM_ABI const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
LLVM_ABI unsigned getSmallConstantMaxTripCount()
Returns the upper bound of the loop trip count as a normal unsigned value, or 0 if the trip count is ...
LLVM_ABI const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSymbolicMaxBackedgeTakenCount()
Get the (predicated) symbolic max backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
constexpr bool isValid() const
This node represents an addition of some number of SCEVs.
This node represents a polynomial recurrence on the trip count of the specified loop.
friend class ScalarEvolution
const SCEV * getStart() const
LLVM_ABI const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
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
This is the base class for unary cast operator classes.
const SCEV * getOperand() const
LLVM_ABI SCEVCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, const SCEV *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, const SCEV *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
bool hasNoSelfWrap() const
size_t getNumOperands() const
bool hasNoSignedWrap() const
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
const SCEV * getOperand(unsigned i) const
const SCEV *const * Operands
ArrayRef< const SCEV * > operands() 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.
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)
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.
const SCEV * getLHS() const
const SCEV * getRHS() const
This class represents an unsigned minimum selection.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
void print(raw_ostream &OS, unsigned Depth) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Returns true if this predicate implies N.
SCEVUnionPredicate(ArrayRef< const SCEVPredicate * > Preds, ScalarEvolution &SE)
Union predicates don't get cached so create a dummy set ID for it.
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents the value of vscale, as used when defining the length of a scalable vector or r...
This class represents an assumption made on an AddRec expression.
IncrementWrapFlags
Similar to SCEV::NoWrapFlags, but with slightly different semantics for FlagNUSW.
SCEVWrapPredicate(const FoldingSetNodeIDRef ID, const SCEVAddRecExpr *AR, IncrementWrapFlags Flags)
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Returns true if this predicate implies N.
static SCEVWrapPredicate::IncrementWrapFlags setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OnFlags)
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
const SCEVAddRecExpr * getExpr() const
Implementation of the SCEVPredicate interface.
static SCEVWrapPredicate::IncrementWrapFlags clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OffFlags)
Convenient IncrementWrapFlags manipulation methods.
static SCEVWrapPredicate::IncrementWrapFlags getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE)
Returns the set of SCEVWrapPredicate no wrap flags implied by a SCEVAddRecExpr.
IncrementWrapFlags getFlags() const
Returns the set assumed no overflow flags.
This class represents a zero extension of a small integer value to a larger integer value.
This class represents an analyzed expression in the program.
LLVM_ABI ArrayRef< const SCEV * > operands() const
Return operands of this SCEV expression.
unsigned short getExpressionSize() const
LLVM_ABI bool isOne() const
Return true if the expression is a constant one.
LLVM_ABI bool isZero() const
Return true if the expression is a constant zero.
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.
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
LLVM_ABI Type * getType() const
Return the LLVM type of this SCEV expression.
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
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.
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 * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
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 const SCEV * getURemExpr(const SCEV *LHS, const SCEV *RHS)
Represents an unsigned remainder expression based on unsigned division.
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 * 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 * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
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 * getUMaxExpr(const SCEV *LHS, const SCEV *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 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.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
LLVM_ABI const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
LLVM_ABI const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
LLVM_ABI ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI)
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LLVM_ABI const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI const SCEV * getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty)
LLVM_ABI const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
LLVM_ABI const SCEV * getLosslessPtrToIntExpr(const SCEV *Op, unsigned Depth=0)
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.
APInt getUnsignedRangeMin(const SCEV *S)
Determine the min of the unsigned range for a particular SCEV.
LLVM_ABI bool SimplifyICmpOperands(CmpPredicate &Pred, const SCEV *&LHS, const SCEV *&RHS, unsigned Depth=0)
Simplify LHS and RHS in a comparison with predicate Pred.
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 const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
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 * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
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 * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
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 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)
@ 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 const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-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.
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 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 * getGEPExpr(GEPOperator *GEP, ArrayRef< const SCEV * > IndexExprs)
Returns an expression for a GEP.
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 const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
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.
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 const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
LLVM_ABI const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
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 * 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.
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask)
Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name ...
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 * 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 * getUDivExactExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
LLVM_ABI void registerUser(const SCEV *User, ArrayRef< const SCEV * > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
LLVM_ABI const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
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.
LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI bool isKnownViaInduction(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
We'd like to check the predicate on every iteration of the most dominated loop between loops used in ...
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.
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.
static LLVM_ABI IntegerType * getInt8Ty(LLVMContext &C)
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.
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 LLVMContext & getContext() const
All values hold a context through their type.
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).
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.
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.
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)
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
IntrinsicID_match m_Intrinsic()
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
bind_ty< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
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.
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
class_match< const SCEVVScale > m_SCEVVScale()
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.
class_match< const SCEVConstant > m_SCEVConstant()
cst_pred_ty< is_one > m_scev_One()
Match an integer 1.
specificloop_ty m_SpecificLoop(const Loop *L)
SCEVAffineAddRec_match< Op0_t, Op1_t, class_match< const Loop > > m_scev_AffineAddRec(const Op0_t &Op0, const Op1_t &Op1)
bind_ty< const SCEVMulExpr > m_scev_Mul(const SCEVMulExpr *&V)
SCEVUnaryExpr_match< SCEVSignExtendExpr, Op0_t > m_scev_SExt(const Op0_t &Op0)
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.
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagNUW, true > m_scev_c_NUWMul(const Op0_t &Op0, const Op1_t &Op1)
class_match< const Loop > m_Loop()
bind_ty< const SCEVAddExpr > m_scev_Add(const SCEVAddExpr *&V)
bind_ty< const SCEVUnknown > m_SCEVUnknown(const SCEVUnknown *&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.
class_match< const SCEV > m_SCEV()
@ Valid
The data is already valid.
initializer< Ty > init(const Ty &Val)
LocationClass< Ty > location(Ty &L)
@ Switch
The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...
NodeAddr< PhiNode * > Phi
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
FunctionAddr VTableAddr Value
LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt gcd(const DynamicAPInt &A, const DynamicAPInt &B)
void stable_sort(R &&Range)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
SaveAndRestore(T &) -> SaveAndRestore< T >
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)
LLVM_ABI bool canCreatePoison(const Operator *Op, bool ConsiderFlagsAndMetadata=true)
LLVM_ABI bool mustTriggerUB(const Instruction *I, const SmallPtrSetImpl< const Value * > &KnownPoison)
Return true if the given instruction must trigger undefined behavior when I is executed with any oper...
LLVM_ABI bool canConstantFoldCallTo(const CallBase *Call, const Function *F)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
InterleavedRange< Range > interleaved(const Range &R, StringRef Separator=", ", StringRef Prefix="", StringRef Suffix="")
Output range R as a sequence of interleaved elements.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
auto successors(const MachineBasicBlock *BB)
scope_exit(Callable) -> scope_exit< Callable >
constexpr from_range_t from_range
auto dyn_cast_if_present(const Y &Val)
dyn_cast_if_present<X> - Functionally identical to dyn_cast, except that a null (or none in the case ...
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
unsigned short computeExpressionSize(ArrayRef< const SCEV * > Args)
auto uninitialized_copy(R &&Src, IterTy Dst)
bool isa_and_nonnull(const Y &Val)
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO, const DominatorTree &DT)
Returns true if the arithmetic part of the WO 's result is used only along the paths control dependen...
DomTreeNodeBase< BasicBlock > DomTreeNode
LLVM_ABI bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step)
Attempt to match a simple first order recurrence cycle of the form: iv = phi Ty [Start,...
auto dyn_cast_or_null(const Y &Val)
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
iterator_range< pointee_iterator< WrappedIteratorT > > make_pointee_range(RangeT &&Range)
auto reverse(ContainerTy &&C)
LLVM_ABI bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
LLVM_ABI bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
LLVM_ABI bool isFinite(const Loop *L)
Return true if this loop can be assumed to run for a finite number of iterations.
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
LLVM_ABI bool programUndefinedIfPoison(const Instruction *Inst)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isPointerTy(const Type *T)
FunctionAddr VTableAddr Count
LLVM_ABI ConstantRange getVScaleRange(const Function *F, unsigned BitWidth)
Determine the possible constant range of vscale with the given bit width, based on the vscale_range f...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
LLVM_ABI bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)
Return true if the given value is known to be non-zero when defined.
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
LLVM_ABI bool propagatesPoison(const Use &PoisonOp)
Return true if PoisonOp's user yields poison or raises UB if its operand PoisonOp is poison.
@ UMin
Unsigned integer min implemented in terms of select(cmp()).
@ Mul
Product of integers.
@ SMax
Signed integer max implemented in terms of select(cmp()).
@ SMin
Signed integer min implemented in terms of select(cmp()).
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
DWARFExpression::Operation Op
auto max_element(R &&Range)
Provide wrappers to std::max_element which take ranges instead of having to pass begin/end explicitly...
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
ArrayRef(const T &OneElt) -> ArrayRef< T >
LLVM_ABI unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Return the number of times the sign bit of the register is replicated into the other bits.
constexpr unsigned BitWidth
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
constexpr bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
iterator_range< df_iterator< T > > depth_first(const T &G)
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be poison, but may be undef.
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
Implement std::hash so that hash_code can be used in STL containers.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
A special type used by analysis passes to provide an address that identifies that particular analysis...
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
bool isNonNegative() const
Returns true if this value is known to be non-negative.
static LLVM_ABI KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for ashr(LHS, RHS).
unsigned getBitWidth() const
Get the bit width of this value.
static LLVM_ABI KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for lshr(LHS, RHS).
KnownBits zextOrTrunc(unsigned BitWidth) const
Return known bits for a zero extension or truncation of the value we're tracking.
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
APInt getMinValue() const
Return the minimal unsigned value possible given these KnownBits.
bool isNegative() const
Returns true if this value is known to be negative.
static LLVM_ABI KnownBits shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW=false, bool NSW=false, bool ShAmtNonZero=false)
Compute known bits for shl(LHS, RHS).
An object of this class is returned by queries that could not be answered.
LLVM_ABI SCEVCouldNotCompute()
static LLVM_ABI bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This class defines a simple visitor class that may be used for various SCEV analysis purposes.
A utility class that uses RAII to save and restore the value of a variable.
Information about the number of loop iterations for which a loop exit's branch condition evaluates to...
LLVM_ABI ExitLimit(const SCEV *E)
Construct either an exact exit limit from a constant, or an unknown one from a SCEVCouldNotCompute.
const SCEV * ExactNotTaken
const SCEV * SymbolicMaxNotTaken
SmallVector< const SCEVPredicate *, 4 > Predicates
A vector of predicate guards for this ExitLimit.
const SCEV * ConstantMaxNotTaken