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)
285 OS <<
"(ptrto" << OpS <<
" " << *
Op->getType() <<
" " << *
Op <<
" to "
292 OS <<
"(trunc " << *
Op->getType() <<
" " << *
Op <<
" to "
299 OS <<
"(zext " << *
Op->getType() <<
" " << *
Op <<
" to "
306 OS <<
"(sext " << *
Op->getType() <<
" " << *
Op <<
" to "
335 const char *OpStr =
nullptr;
348 OpStr =
" umin_seq ";
372 OS <<
"(" << *UDiv->
getLHS() <<
" /u " << *UDiv->
getRHS() <<
")";
379 OS <<
"***COULDNOTCOMPUTE***";
457 if (!
Mul)
return false;
461 if (!SC)
return false;
479 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
481 UniqueSCEVs.InsertNode(S, IP);
495 ConstantInt::get(ITy, V, isSigned,
true));
503 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
506 UniqueSCEVs.InsertNode(S, IP);
526 "Must be a non-bit-width-changing pointer-to-integer cast!");
533 "Must be a non-bit-width-changing pointer-to-integer cast!");
545 "Cannot truncate non-integer value!");
552 "Cannot zero extend non-integer value!");
559 "Cannot sign extend non-integer value!");
564 SE->forgetMemoizedResults(
this);
567 SE->UniqueSCEVs.RemoveNode(
this);
573void SCEVUnknown::allUsesReplacedWith(
Value *New) {
575 SE->forgetMemoizedResults(
this);
578 SE->UniqueSCEVs.RemoveNode(
this);
600 if (LIsPointer != RIsPointer)
601 return (
int)LIsPointer - (int)RIsPointer;
606 return (
int)LID - (int)RID;
611 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
612 return (
int)LArgNo - (int)RArgNo;
618 if (
auto L = LGV->getLinkage() - RGV->getLinkage())
621 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
622 auto LT = GV->getLinkage();
629 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
630 return LGV->getName().compare(RGV->getName());
641 if (LParent != RParent) {
644 if (LDepth != RDepth)
645 return (
int)LDepth - (int)RDepth;
649 unsigned LNumOps = LInst->getNumOperands(),
650 RNumOps = RInst->getNumOperands();
651 if (LNumOps != RNumOps)
652 return (
int)LNumOps - (int)RNumOps;
654 for (
unsigned Idx :
seq(LNumOps)) {
656 RInst->getOperand(Idx),
Depth + 1);
670static std::optional<int>
680 return (
int)LType - (int)RType;
705 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
706 if (LBitWidth != RBitWidth)
707 return (
int)LBitWidth - (int)RBitWidth;
708 return LA.
ult(
RA) ? -1 : 1;
714 return LTy->getBitWidth() - RTy->getBitWidth();
725 if (LLoop != RLoop) {
727 assert(LHead != RHead &&
"Two loops share the same header?");
731 "No dominance between recurrences used by one SCEV?");
755 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
756 if (LNumOps != RNumOps)
757 return (
int)LNumOps - (int)RNumOps;
759 for (
unsigned i = 0; i != LNumOps; ++i) {
784 if (
Ops.size() < 2)
return;
789 return Complexity && *Complexity < 0;
791 if (
Ops.size() == 2) {
795 if (IsLessComplex(
RHS,
LHS))
802 return IsLessComplex(
LHS,
RHS);
809 for (
unsigned i = 0, e =
Ops.size(); i != e-2; ++i) {
815 for (
unsigned j = i+1; j != e &&
Ops[j]->getSCEVType() == Complexity; ++j) {
820 if (i == e-2)
return;
842template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
846 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
848 for (
unsigned Idx = 0; Idx <
Ops.size();) {
856 Ops.erase(
Ops.begin() + Idx);
863 assert(Folded &&
"Must have folded value");
867 if (Folded && IsAbsorber(Folded->
getAPInt()))
871 if (Folded && !IsIdentity(Folded->
getAPInt()))
872 Ops.insert(
Ops.begin(), Folded);
874 return Ops.size() == 1 ?
Ops[0] :
nullptr;
949 APInt OddFactorial(W, 1);
951 for (
unsigned i = 3; i <= K; ++i) {
954 OddFactorial *= (i >> TwoFactors);
958 unsigned CalculationBits = W +
T;
972 for (
unsigned i = 1; i != K; ++i) {
1005 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1033 ConversionFn CreatePtrCast;
1037 ConversionFn CreatePtrCast)
1038 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
1041 Type *TargetTy, ConversionFn CreatePtrCast) {
1043 return Rewriter.visit(Scev);
1079 "Should only reach pointer-typed SCEVUnknown's.");
1084 return SE.getZero(TargetTy);
1085 return CreatePtrCast(Expr);
1090 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1109 Op, *
this, IntPtrTy, [
this, IntPtrTy](
const SCEVUnknown *U) {
1114 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1116 SCEV *S =
new (SCEVAllocator)
1118 UniqueSCEVs.InsertNode(S, IP);
1120 return static_cast<const SCEV *
>(S);
1123 "We must have succeeded in sinking the cast, "
1124 "and ending up with an integer-typed expression!");
1129 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1133 if (DL.hasUnstableRepresentation(
Op->getType()))
1136 Type *Ty = DL.getAddressType(
Op->getType());
1147 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1149 SCEV *S =
new (SCEVAllocator)
1151 UniqueSCEVs.InsertNode(S, IP);
1153 return static_cast<const SCEV *
>(S);
1156 "We must have succeeded in sinking the cast, "
1157 "and ending up with an integer-typed expression!");
1162 assert(Ty->isIntegerTy() &&
"Target type must be an integer type!");
1174 "This is not a truncating conversion!");
1176 "This is not a conversion to a SCEVable type!");
1177 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1185 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1207 UniqueSCEVs.InsertNode(S, IP);
1219 unsigned numTruncs = 0;
1220 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1228 if (numTruncs < 2) {
1238 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1245 for (
const SCEV *
Op : AddRec->operands())
1260 UniqueSCEVs.InsertNode(S, IP);
1300struct ExtendOpTraitsBase {
1301 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
const SCEV *,
Type *,
1306template <
typename ExtendOp>
struct ExtendOpTraits {
1322 static const GetExtendExprTy GetExtendExpr;
1324 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1325 ICmpInst::Predicate *Pred,
1326 ScalarEvolution *SE) {
1331const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1338 static const GetExtendExprTy GetExtendExpr;
1340 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1341 ICmpInst::Predicate *Pred,
1342 ScalarEvolution *SE) {
1347const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1359template <
typename ExtendOpTy>
1362 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1363 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1379 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1392 auto PreStartFlags =
1410 const SCEV *OperandExtendedStart =
1412 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1413 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1425 const SCEV *OverflowLimit =
1426 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1428 if (OverflowLimit &&
1436template <
typename ExtendOpTy>
1440 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1448 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1483template <
typename ExtendOpTy>
1484bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1487 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1497 APInt StartAI = StartC->
getAPInt();
1499 for (
unsigned Delta : {-2, -1, 1, 2}) {
1500 const SCEV *PreStart =
getConstant(StartAI - Delta);
1502 FoldingSetNodeID
ID;
1504 ID.AddPointer(PreStart);
1505 ID.AddPointer(Step);
1509 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
1513 if (PreAR && PreAR->getNoWrapFlags(WrapType)) {
1516 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1517 DeltaS, &Pred,
this);
1535 const unsigned BitWidth =
C.getBitWidth();
1553 const APInt &ConstantStart,
1572 auto &UserIDs = FoldCacheUser[
I.first->second];
1573 assert(
count(UserIDs,
ID) == 1 &&
"unexpected duplicates in UserIDs");
1574 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1575 if (UserIDs[
I] ==
ID) {
1580 I.first->second = S;
1582 FoldCacheUser[S].push_back(
ID);
1588 "This is not an extending conversion!");
1590 "This is not a conversion to a SCEVable type!");
1591 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1595 if (
const SCEV *S = FoldCache.lookup(
ID))
1607 "This is not an extending conversion!");
1609 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1626 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1630 UniqueSCEVs.InsertNode(S, IP);
1639 const SCEV *
X = ST->getOperand();
1653 if (AR->isAffine()) {
1654 const SCEV *Start = AR->getStart();
1655 const SCEV *Step = AR->getStepRecurrence(*
this);
1657 const Loop *L = AR->getLoop();
1661 if (AR->hasNoUnsignedWrap()) {
1682 const SCEV *CastedMaxBECount =
1686 if (MaxBECount == RecastedMaxBECount) {
1696 const SCEV *WideMaxBECount =
1698 const SCEV *OperandExtendedAdd =
1704 if (ZAdd == OperandExtendedAdd) {
1715 OperandExtendedAdd =
1721 if (ZAdd == OperandExtendedAdd) {
1742 !AC.assumptions().empty()) {
1744 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1746 if (AR->hasNoUnsignedWrap()) {
1781 const APInt &
C = SC->getAPInt();
1785 const SCEV *SResidual =
1794 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1819 if (SA->hasNoUnsignedWrap()) {
1823 for (
const auto *
Op : SA->operands())
1840 const SCEV *SResidual =
1852 if (
SM->hasNoUnsignedWrap()) {
1856 for (
const auto *
Op :
SM->operands())
1874 const SCEV *TruncRHS;
1893 for (
auto *Operand :
MinMax->operands())
1904 for (
auto *Operand :
MinMax->operands())
1911 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1914 UniqueSCEVs.InsertNode(S, IP);
1922 "This is not an extending conversion!");
1924 "This is not a conversion to a SCEVable type!");
1925 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1929 if (
const SCEV *S = FoldCache.lookup(
ID))
1941 "This is not an extending conversion!");
1943 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1965 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1970 UniqueSCEVs.InsertNode(S, IP);
1979 const SCEV *
X = ST->getOperand();
1990 if (SA->hasNoSignedWrap()) {
1994 for (
const auto *
Op : SA->operands())
2012 const SCEV *SResidual =
2026 if (AR->isAffine()) {
2027 const SCEV *Start = AR->getStart();
2028 const SCEV *Step = AR->getStepRecurrence(*
this);
2030 const Loop *L = AR->getLoop();
2034 if (AR->hasNoSignedWrap()) {
2056 const SCEV *CastedMaxBECount =
2060 if (MaxBECount == RecastedMaxBECount) {
2070 const SCEV *WideMaxBECount =
2072 const SCEV *OperandExtendedAdd =
2078 if (SAdd == OperandExtendedAdd) {
2089 OperandExtendedAdd =
2095 if (SAdd == OperandExtendedAdd) {
2115 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2117 if (AR->hasNoSignedWrap()) {
2132 const APInt &
C = SC->getAPInt();
2136 const SCEV *SResidual =
2145 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2164 for (
auto *Operand :
MinMax->operands())
2173 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
2176 UniqueSCEVs.InsertNode(S, IP);
2202 "This is not an extending conversion!");
2204 "This is not a conversion to a SCEVable type!");
2209 if (SC->getAPInt().isNegative())
2214 const SCEV *NewOp =
T->getOperand();
2233 for (
const SCEV *
Op : AR->operands())
2272 APInt &AccumulatedConstant,
2275 bool Interesting =
false;
2282 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2284 AccumulatedConstant += Scale *
C->getAPInt();
2289 for (; i !=
Ops.size(); ++i) {
2299 Add->operands(), NewScale, SE);
2305 auto Pair = M.insert({
Key, NewScale});
2309 Pair.first->second += NewScale;
2317 std::pair<DenseMap<const SCEV *, APInt>::iterator,
bool> Pair =
2318 M.insert({
Ops[i], Scale});
2322 Pair.first->second += Scale;
2341 case Instruction::Add:
2344 case Instruction::Sub:
2347 case Instruction::Mul:
2361 const SCEV *
A = (this->*Extension)(
2363 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2364 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2372 if (BinOp == Instruction::Mul)
2378 APInt C = RHSC->getAPInt();
2379 unsigned NumBits =
C.getBitWidth();
2380 bool IsSub = (BinOp == Instruction::Sub);
2381 bool IsNegativeConst = (
Signed &&
C.isNegative());
2383 bool OverflowDown = IsSub ^ IsNegativeConst;
2385 if (IsNegativeConst) {
2398 APInt Limit = Min + Magnitude;
2404 APInt Limit = Max - Magnitude;
2409std::optional<SCEV::NoWrapFlags>
2414 return std::nullopt;
2423 bool Deduced =
false;
2425 if (OBO->
getOpcode() != Instruction::Add &&
2428 return std::nullopt;
2437 false, LHS, RHS, CtxI)) {
2444 true, LHS, RHS, CtxI)) {
2451 return std::nullopt;
2461 using namespace std::placeholders;
2468 assert(CanAnalyze &&
"don't call from other places!");
2475 auto IsKnownNonNegative = [&](
const SCEV *S) {
2485 if (SignOrUnsignWrap != SignOrUnsignMask &&
2492 return Instruction::Add;
2494 return Instruction::Mul;
2505 Opcode,
C, OBO::NoSignedWrap);
2513 Opcode,
C, OBO::NoUnsignedWrap);
2523 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2530 if (UDiv->getOperand(1) ==
Ops[1])
2533 if (UDiv->getOperand(1) ==
Ops[0])
2549 "only nuw or nsw allowed");
2550 assert(!
Ops.empty() &&
"Cannot get empty add!");
2551 if (
Ops.size() == 1)
return Ops[0];
2554 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2556 "SCEVAddExpr operand types don't match!");
2558 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2559 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2564 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2565 [](
const APInt &
C) {
return C.isZero(); },
2566 [](
const APInt &
C) {
return false; });
2579 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2584 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2585 Add->setNoWrapFlags(ComputeFlags(
Ops));
2593 bool FoundMatch =
false;
2594 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2595 if (
Ops[i] ==
Ops[i+1]) {
2607 --i; e -=
Count - 1;
2617 auto FindTruncSrcType = [&]() ->
Type * {
2623 return T->getOperand()->getType();
2625 const auto *LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2627 return T->getOperand()->getType();
2631 if (
auto *SrcType = FindTruncSrcType()) {
2638 if (
T->getOperand()->getType() != SrcType) {
2647 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2650 if (
T->getOperand()->getType() != SrcType) {
2678 if (
Ops.size() == 2) {
2688 auto C2 =
C->getAPInt();
2691 APInt ConstAdd = C1 + C2;
2692 auto AddFlags = AddExpr->getNoWrapFlags();
2733 if (
Ops.size() == 2 &&
2744 if (Idx <
Ops.size()) {
2745 bool DeletedAdd =
false;
2756 Ops.erase(
Ops.begin()+Idx);
2759 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2782 struct APIntCompare {
2783 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2784 return LHS.ult(RHS);
2791 std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists;
2792 for (
const SCEV *NewOp : NewOps)
2793 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2796 if (AccumulatedConstant != 0)
2798 for (
auto &MulOp : MulOpLists) {
2799 if (MulOp.first == 1) {
2801 }
else if (MulOp.first != 0) {
2810 if (
Ops.size() == 1)
2821 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2822 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2825 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp)
2826 if (MulOpSCEV ==
Ops[AddOp]) {
2828 const SCEV *InnerMul =
Mul->getOperand(MulOp == 0);
2829 if (
Mul->getNumOperands() != 2) {
2833 Mul->operands().take_front(MulOp));
2841 if (
Ops.size() == 2)
return OuterMul;
2843 Ops.erase(
Ops.begin()+AddOp);
2844 Ops.erase(
Ops.begin()+Idx-1);
2846 Ops.erase(
Ops.begin()+Idx);
2847 Ops.erase(
Ops.begin()+AddOp-1);
2849 Ops.push_back(OuterMul);
2854 for (
unsigned OtherMulIdx = Idx+1;
2861 OMulOp != e; ++OMulOp)
2862 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2864 const SCEV *InnerMul1 =
Mul->getOperand(MulOp == 0);
2865 if (
Mul->getNumOperands() != 2) {
2867 Mul->operands().take_front(MulOp));
2874 OtherMul->
operands().take_front(OMulOp));
2879 const SCEV *InnerMulSum =
2883 if (
Ops.size() == 2)
return OuterMul;
2884 Ops.erase(
Ops.begin()+Idx);
2885 Ops.erase(
Ops.begin()+OtherMulIdx-1);
2886 Ops.push_back(OuterMul);
2906 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2909 Ops.erase(
Ops.begin()+i);
2914 if (!LIOps.
empty()) {
2939 auto *DefI = getDefiningScopeBound(LIOps);
2941 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2953 if (
Ops.size() == 1)
return NewRec;
2956 for (
unsigned i = 0;; ++i)
2957 if (
Ops[i] == AddRec) {
2967 for (
unsigned OtherIdx = Idx+1;
2975 "AddRecExprs are not sorted in reverse dominance order?");
2982 if (OtherAddRec->getLoop() == AddRecLoop) {
2983 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2985 if (i >= AddRecOps.
size()) {
2986 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2990 AddRecOps[i], OtherAddRec->getOperand(i)};
2993 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3008 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
3020 static_cast<SCEVAddExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3022 const SCEV **O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
3024 S =
new (SCEVAllocator)
3026 UniqueSCEVs.InsertNode(S, IP);
3036 FoldingSetNodeID
ID;
3038 for (
const SCEV *
Op :
Ops)
3043 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3045 const SCEV **
O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
3047 S =
new (SCEVAllocator)
3048 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3049 UniqueSCEVs.InsertNode(S, IP);
3050 LoopUsers[
L].push_back(S);
3060 FoldingSetNodeID
ID;
3062 for (
const SCEV *
Op :
Ops)
3066 static_cast<SCEVMulExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3068 const SCEV **
O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
3070 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3072 UniqueSCEVs.InsertNode(S, IP);
3081 if (j > 1 && k / j != i) Overflow =
true;
3097 if (n == 0 || n == k)
return 1;
3098 if (k > n)
return 0;
3104 for (
uint64_t i = 1; i <= k; ++i) {
3105 r =
umul_ov(r, n-(i-1), Overflow);
3114 struct FindConstantInAddMulChain {
3115 bool FoundConstant =
false;
3117 bool follow(
const SCEV *S) {
3122 bool isDone()
const {
3123 return FoundConstant;
3127 FindConstantInAddMulChain
F;
3129 ST.visitAll(StartExpr);
3130 return F.FoundConstant;
3138 "only nuw or nsw allowed");
3139 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3140 if (
Ops.size() == 1)
return Ops[0];
3142 Type *ETy =
Ops[0]->getType();
3144 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3146 "SCEVMulExpr operand types don't match!");
3151 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3152 [](
const APInt &
C) {
return C.isOne(); },
3153 [](
const APInt &
C) {
return C.isZero(); });
3164 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3169 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3170 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3175 if (
Ops.size() == 2) {
3183 const SCEV *Op0, *Op1;
3191 if (
Ops[0]->isAllOnesValue()) {
3196 bool AnyFolded =
false;
3197 for (
const SCEV *AddOp :
Add->operands()) {
3224 AddRec->getNoWrapFlags(FlagsMask));
3247 APInt C1V = LHSC->getAPInt();
3257 const SCEV *NewMul =
nullptr;
3261 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3276 if (Idx <
Ops.size()) {
3277 bool DeletedMul =
false;
3283 Ops.erase(
Ops.begin()+Idx);
3307 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3310 Ops.erase(
Ops.begin()+i);
3315 if (!LIOps.
empty()) {
3328 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3344 if (
Ops.size() == 1)
return NewRec;
3347 for (
unsigned i = 0;; ++i)
3348 if (
Ops[i] == AddRec) {
3369 bool OpsModified =
false;
3370 for (
unsigned OtherIdx = Idx+1;
3384 bool Overflow =
false;
3391 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3395 z < ze && !Overflow; ++z) {
3398 if (LargerThan64Bits)
3399 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3401 Coeff = Coeff1*Coeff2;
3416 if (
Ops.size() == 2)
return NewAddRec;
3417 Ops[Idx] = NewAddRec;
3418 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3434 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3442 "SCEVURemExpr operand types don't match!");
3447 if (RHSC->getValue()->isOne())
3448 return getZero(LHS->getType());
3451 if (RHSC->getAPInt().isPowerOf2()) {
3452 Type *FullTy = LHS->getType();
3469 assert(!LHS->getType()->isPointerTy() &&
3470 "SCEVUDivExpr operand can't be pointer!");
3471 assert(LHS->getType() == RHS->getType() &&
3472 "SCEVUDivExpr operand types don't match!");
3479 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3487 if (RHSC->getValue()->isOne())
3492 if (!RHSC->getValue()->isZero()) {
3496 Type *Ty = LHS->getType();
3497 unsigned LZ = RHSC->getAPInt().countl_zero();
3501 if (!RHSC->getAPInt().isPowerOf2())
3509 const APInt &StepInt = Step->getAPInt();
3510 const APInt &DivInt = RHSC->getAPInt();
3511 if (!StepInt.
urem(DivInt) &&
3517 for (
const SCEV *
Op : AR->operands())
3523 const APInt *StartRem;
3536 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3540 const SCEV *NewStart =
3542 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3544 const SCEV *NewLHS =
3547 if (LHS != NewLHS) {
3557 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3566 for (
const SCEV *
Op : M->operands())
3570 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3571 const SCEV *
Op = M->getOperand(i);
3583 if (
auto *DivisorConstant =
3585 bool Overflow =
false;
3587 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3598 for (
const SCEV *
Op :
A->operands())
3602 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3609 if (Operands.
size() ==
A->getNumOperands())
3616 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3626 return getZero(LHS->getType());
3630 const SCEV *NewLHS, *NewRHS;
3638 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
3641 UniqueSCEVs.InsertNode(S, IP);
3671 if (!
Mul || !
Mul->hasNoUnsignedWrap())
3678 if (LHSCst == RHSCst) {
3686 APInt Factor =
gcd(LHSCst, RHSCst);
3704 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3705 if (
Mul->getOperand(i) == RHS) {
3724 if (StepChrec->getLoop() == L) {
3738 if (Operands.
size() == 1)
return Operands[0];
3743 "SCEVAddRecExpr operand types don't match!");
3744 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3746 for (
const SCEV *
Op : Operands)
3748 "SCEVAddRecExpr operand is not available at loop entry!");
3751 if (Operands.
back()->isZero()) {
3766 const Loop *NestedLoop = NestedAR->getLoop();
3767 if (L->contains(NestedLoop)
3770 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3772 Operands[0] = NestedAR->getStart();
3776 bool AllInvariant =
all_of(
3788 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3799 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3803 Operands[0] = NestedAR;
3809 return getOrCreateAddRecExpr(Operands, L, Flags);
3825 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3829 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3843 bool FirstIter =
true;
3845 for (
const SCEV *IndexExpr : IndexExprs) {
3852 Offsets.push_back(FieldOffset);
3855 CurTy = STy->getTypeAtIndex(Index);
3860 "The first index of a GEP indexes a pointer");
3861 CurTy = SrcElementTy;
3872 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3873 Offsets.push_back(LocalOffset);
3878 if (Offsets.empty())
3891 "GEP should not change type mid-flight.");
3895SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3898 ID.AddInteger(SCEVType);
3902 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3912 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3913 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3914 if (
Ops.size() == 1)
return Ops[0];
3917 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3919 "Operand types don't match!");
3922 "min/max should be consistently pointerish");
3948 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3950 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3955 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3957 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3963 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3969 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3974 if (Idx <
Ops.size()) {
3975 bool DeletedAny =
false;
3976 while (
Ops[Idx]->getSCEVType() == Kind) {
3978 Ops.erase(
Ops.begin()+Idx);
3996 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3997 if (
Ops[i] ==
Ops[i + 1] ||
3998 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
4001 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
4004 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
4007 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
4013 if (
Ops.size() == 1)
return Ops[0];
4015 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
4020 ID.AddInteger(Kind);
4024 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4026 return ExistingSCEV;
4027 const SCEV **O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
4029 SCEV *S =
new (SCEVAllocator)
4032 UniqueSCEVs.InsertNode(S, IP);
4039class SCEVSequentialMinMaxDeduplicatingVisitor final
4040 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4041 std::optional<const SCEV *>> {
4042 using RetVal = std::optional<const SCEV *>;
4050 bool canRecurseInto(
SCEVTypes Kind)
const {
4053 return RootKind == Kind || NonSequentialRootKind == Kind;
4056 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
4058 "Only for min/max expressions.");
4061 if (!canRecurseInto(Kind))
4071 return std::nullopt;
4078 RetVal
visit(
const SCEV *S) {
4080 if (!SeenOps.
insert(S).second)
4081 return std::nullopt;
4082 return Base::visit(S);
4086 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4088 : SE(SE), RootKind(RootKind),
4089 NonSequentialRootKind(
4090 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4094 SmallVectorImpl<const SCEV *> &NewOps) {
4099 for (
const SCEV *
Op : OrigOps) {
4104 Ops.emplace_back(*NewOp);
4108 NewOps = std::move(
Ops);
4112 RetVal visitConstant(
const SCEVConstant *Constant) {
return Constant; }
4114 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4116 RetVal visitPtrToAddrExpr(
const SCEVPtrToAddrExpr *Expr) {
return Expr; }
4118 RetVal visitPtrToIntExpr(
const SCEVPtrToIntExpr *Expr) {
return Expr; }
4120 RetVal visitTruncateExpr(
const SCEVTruncateExpr *Expr) {
return Expr; }
4122 RetVal visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
return Expr; }
4124 RetVal visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
return Expr; }
4126 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4128 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4130 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4132 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4134 RetVal visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
4135 return visitAnyMinMaxExpr(Expr);
4138 RetVal visitUMaxExpr(
const SCEVUMaxExpr *Expr) {
4139 return visitAnyMinMaxExpr(Expr);
4142 RetVal visitSMinExpr(
const SCEVSMinExpr *Expr) {
4143 return visitAnyMinMaxExpr(Expr);
4146 RetVal visitUMinExpr(
const SCEVUMinExpr *Expr) {
4147 return visitAnyMinMaxExpr(Expr);
4150 RetVal visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *Expr) {
4151 return visitAnyMinMaxExpr(Expr);
4154 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4156 RetVal visitCouldNotCompute(
const SCEVCouldNotCompute *Expr) {
return Expr; }
4199struct SCEVPoisonCollector {
4200 bool LookThroughMaybePoisonBlocking;
4201 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4202 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4203 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4205 bool follow(
const SCEV *S) {
4206 if (!LookThroughMaybePoisonBlocking &&
4216 bool isDone()
const {
return false; }
4226 SCEVPoisonCollector PC1(
true);
4231 if (PC1.MaybePoison.empty())
4237 SCEVPoisonCollector PC2(
false);
4247 SCEVPoisonCollector PC(
false);
4270 while (!Worklist.
empty()) {
4272 if (!Visited.
insert(V).second)
4276 if (Visited.
size() > 16)
4281 if (PoisonVals.
contains(V) || ::isGuaranteedNotToBePoison(V))
4292 if (PDI->isDisjoint())
4299 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4306 if (
I->hasPoisonGeneratingAnnotations())
4317 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4318 "Not a SCEVSequentialMinMaxExpr!");
4319 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4320 if (
Ops.size() == 1)
4324 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4326 "Operand types don't match!");
4329 "min/max should be consistently pointerish");
4337 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4344 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4354 bool DeletedAny =
false;
4355 while (Idx <
Ops.size()) {
4356 if (
Ops[Idx]->getSCEVType() != Kind) {
4361 Ops.erase(
Ops.begin() + Idx);
4362 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4363 SMME->operands().end());
4371 const SCEV *SaturationPoint;
4382 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4383 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4395 Ops.erase(
Ops.begin() + i);
4400 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4401 Ops.erase(
Ops.begin() + i);
4409 ID.AddInteger(Kind);
4413 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4415 return ExistingSCEV;
4417 const SCEV **O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
4419 SCEV *S =
new (SCEVAllocator)
4422 UniqueSCEVs.InsertNode(S, IP);
4470 if (
Size.isScalable())
4491 "Cannot get offset for structure containing scalable vector types");
4505 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP)) {
4507 "Stale SCEVUnknown in uniquing map!");
4513 UniqueSCEVs.InsertNode(S, IP);
4527 return Ty->isIntOrPtrTy();
4534 if (Ty->isPointerTy())
4545 if (Ty->isIntegerTy())
4549 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4561 bool PreciseA, PreciseB;
4562 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4563 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4564 if (!PreciseA || !PreciseB)
4567 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4568 DT.dominates(ScopeB, ScopeA);
4572 return CouldNotCompute.get();
4575bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4578 return SU && SU->getValue() ==
nullptr;
4581 return !ContainsNulls;
4586 if (
I != HasRecMap.end())
4591 HasRecMap.insert({S, FoundAddRec});
4599 if (
SI == ExprValueMap.
end())
4601 return SI->second.getArrayRef();
4607void ScalarEvolution::eraseValueFromMap(
Value *V) {
4609 if (
I != ValueExprMap.end()) {
4610 auto EVIt = ExprValueMap.find(
I->second);
4611 bool Removed = EVIt->second.remove(V);
4613 assert(Removed &&
"Value not in ExprValueMap?");
4614 ValueExprMap.erase(
I);
4618void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4622 auto It = ValueExprMap.find_as(V);
4623 if (It == ValueExprMap.end()) {
4625 ExprValueMap[S].insert(V);
4636 return createSCEVIter(V);
4643 if (
I != ValueExprMap.end()) {
4644 const SCEV *S =
I->second;
4645 assert(checkValidity(S) &&
4646 "existing SCEV has not been properly invalidated");
4659 Type *Ty = V->getType();
4675 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4688 return (
const SCEV *)
nullptr;
4694 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4698 Type *Ty = V->getType();
4704 assert(
P->getType()->isPointerTy());
4717 const SCEV **PtrOp =
nullptr;
4718 for (
const SCEV *&AddOp :
Ops) {
4719 if (AddOp->getType()->isPointerTy()) {
4720 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4738 return getZero(LHS->getType());
4743 if (RHS->getType()->isPointerTy()) {
4744 if (!LHS->getType()->isPointerTy() ||
4754 const bool RHSIsNotMinSigned =
4785 Type *SrcTy = V->getType();
4786 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4787 "Cannot truncate or zero extend with non-integer arguments!");
4797 Type *SrcTy = V->getType();
4798 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4799 "Cannot truncate or zero extend with non-integer arguments!");
4809 Type *SrcTy = V->getType();
4810 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4811 "Cannot noop or zero extend with non-integer arguments!");
4813 "getNoopOrZeroExtend cannot truncate!");
4821 Type *SrcTy = V->getType();
4822 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4823 "Cannot noop or sign extend with non-integer arguments!");
4825 "getNoopOrSignExtend cannot truncate!");
4833 Type *SrcTy = V->getType();
4834 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4835 "Cannot noop or any extend with non-integer arguments!");
4837 "getNoopOrAnyExtend cannot truncate!");
4845 Type *SrcTy = V->getType();
4846 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4847 "Cannot truncate or noop with non-integer arguments!");
4849 "getTruncateOrNoop cannot extend!");
4857 const SCEV *PromotedLHS = LHS;
4858 const SCEV *PromotedRHS = RHS;
4878 assert(!
Ops.empty() &&
"At least one operand must be!");
4880 if (
Ops.size() == 1)
4884 Type *MaxType =
nullptr;
4885 for (
const auto *S :
Ops)
4890 assert(MaxType &&
"Failed to find maximum type!");
4894 for (
const auto *S :
Ops)
4903 if (!V->getType()->isPointerTy())
4908 V = AddRec->getStart();
4910 const SCEV *PtrOp =
nullptr;
4911 for (
const SCEV *AddOp :
Add->operands()) {
4912 if (AddOp->getType()->isPointerTy()) {
4913 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4917 assert(PtrOp &&
"Must have pointer op");
4929 for (
User *U :
I->users()) {
4931 if (Visited.
insert(UserInsn).second)
4945 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4946 bool IgnoreOtherLoops =
true) {
4949 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4951 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4956 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4958 SeenLoopVariantSCEVUnknown =
true;
4962 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4966 SeenOtherLoops =
true;
4970 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4972 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4975 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4976 : SCEVRewriteVisitor(SE),
L(
L) {}
4979 bool SeenLoopVariantSCEVUnknown =
false;
4980 bool SeenOtherLoops =
false;
4989 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4990 SCEVPostIncRewriter
Rewriter(L, SE);
4992 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4997 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4999 SeenLoopVariantSCEVUnknown =
true;
5003 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5007 SeenOtherLoops =
true;
5011 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
5013 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
5016 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
5017 : SCEVRewriteVisitor(SE),
L(
L) {}
5020 bool SeenLoopVariantSCEVUnknown =
false;
5021 bool SeenOtherLoops =
false;
5027class SCEVBackedgeConditionFolder
5030 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5031 ScalarEvolution &SE) {
5032 bool IsPosBECond =
false;
5033 Value *BECond =
nullptr;
5034 if (BasicBlock *Latch =
L->getLoopLatch()) {
5038 "Both outgoing branches should not target same header!");
5045 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
5049 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5050 const SCEV *
Result = Expr;
5055 switch (
I->getOpcode()) {
5056 case Instruction::Select: {
5058 std::optional<const SCEV *> Res =
5059 compareWithBackedgeCondition(
SI->getCondition());
5067 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5078 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5079 bool IsPosBECond, ScalarEvolution &SE)
5080 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5081 IsPositiveBECond(IsPosBECond) {}
5083 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5087 Value *BackedgeCond =
nullptr;
5089 bool IsPositiveBECond;
5092std::optional<const SCEV *>
5093SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5098 if (BackedgeCond == IC)
5101 return std::nullopt;
5106 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5107 ScalarEvolution &SE) {
5113 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5120 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5130 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5131 : SCEVRewriteVisitor(SE),
L(
L) {}
5140ScalarEvolution::proveNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5144 using OBO = OverflowingBinaryOperator;
5152 const APInt &BECountAP = BECountMax->getAPInt();
5153 unsigned NoOverflowBitWidth =
5165 Instruction::Add, IncRange, OBO::NoSignedWrap);
5166 if (NSWRegion.contains(AddRecRange))
5175 Instruction::Add, IncRange, OBO::NoUnsignedWrap);
5176 if (NUWRegion.contains(AddRecRange))
5184ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5194 if (!SignedWrapViaInductionTried.insert(AR).second)
5219 AC.assumptions().empty())
5227 const SCEV *OverflowLimit =
5229 if (OverflowLimit &&
5237ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5247 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5273 AC.assumptions().empty())
5308 explicit BinaryOp(Operator *
Op)
5312 IsNSW = OBO->hasNoSignedWrap();
5313 IsNUW = OBO->hasNoUnsignedWrap();
5317 explicit BinaryOp(
unsigned Opcode,
Value *
LHS,
Value *
RHS,
bool IsNSW =
false,
5319 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5331 return std::nullopt;
5337 switch (
Op->getOpcode()) {
5338 case Instruction::Add:
5339 case Instruction::Sub:
5340 case Instruction::Mul:
5341 case Instruction::UDiv:
5342 case Instruction::URem:
5343 case Instruction::And:
5344 case Instruction::AShr:
5345 case Instruction::Shl:
5346 return BinaryOp(
Op);
5348 case Instruction::Or: {
5351 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5353 return BinaryOp(
Op);
5356 case Instruction::Xor:
5360 if (RHSC->getValue().isSignMask())
5361 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5363 if (V->getType()->isIntegerTy(1))
5364 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5365 return BinaryOp(
Op);
5367 case Instruction::LShr:
5376 if (SA->getValue().ult(
BitWidth)) {
5378 ConstantInt::get(SA->getContext(),
5380 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5383 return BinaryOp(
Op);
5385 case Instruction::ExtractValue: {
5387 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5395 bool Signed = WO->isSigned();
5398 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5403 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5414 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5415 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5417 return std::nullopt;
5443 if (
Op == SymbolicPHI)
5448 if (SourceBits != NewBits)
5466 if (!L || L->getHeader() != PN->
getParent())
5524std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5525ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5533 assert(L &&
"Expecting an integer loop header phi");
5538 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5539 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5540 Value *
V = PN->getIncomingValue(i);
5541 if (
L->contains(PN->getIncomingBlock(i))) {
5544 }
else if (BEValueV != V) {
5548 }
else if (!StartValueV) {
5550 }
else if (StartValueV != V) {
5551 StartValueV =
nullptr;
5555 if (!BEValueV || !StartValueV)
5556 return std::nullopt;
5558 const SCEV *BEValue =
getSCEV(BEValueV);
5565 return std::nullopt;
5569 unsigned FoundIndex =
Add->getNumOperands();
5570 Type *TruncTy =
nullptr;
5572 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5575 if (FoundIndex == e) {
5580 if (FoundIndex ==
Add->getNumOperands())
5581 return std::nullopt;
5585 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5586 if (i != FoundIndex)
5587 Ops.push_back(
Add->getOperand(i));
5593 return std::nullopt;
5646 const SCEV *StartVal =
getSCEV(StartValueV);
5647 const SCEV *PHISCEV =
5674 auto getExtendedExpr = [&](
const SCEV *Expr,
5675 bool CreateSignExtend) ->
const SCEV * {
5678 const SCEV *ExtendedExpr =
5681 return ExtendedExpr;
5689 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5690 const SCEV *ExtendedExpr) ->
bool {
5691 return Expr != ExtendedExpr &&
5695 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5696 if (PredIsKnownFalse(StartVal, StartExtended)) {
5698 return std::nullopt;
5703 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5704 if (PredIsKnownFalse(Accum, AccumExtended)) {
5706 return std::nullopt;
5709 auto AppendPredicate = [&](
const SCEV *Expr,
5710 const SCEV *ExtendedExpr) ->
void {
5711 if (Expr != ExtendedExpr &&
5719 AppendPredicate(StartVal, StartExtended);
5720 AppendPredicate(Accum, AccumExtended);
5728 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5729 std::make_pair(NewAR, Predicates);
5731 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5735std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5740 return std::nullopt;
5743 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5744 if (
I != PredicatedSCEVRewrites.end()) {
5745 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5748 if (Rewrite.first == SymbolicPHI)
5749 return std::nullopt;
5753 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5757 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5758 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5763 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5764 return std::nullopt;
5781 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5782 if (Expr1 != Expr2 &&
5783 !Preds->implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5784 !Preds->implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5801const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5803 Value *StartValueV) {
5806 assert(BEValueV && StartValueV);
5812 if (BO->Opcode != Instruction::Add)
5815 const SCEV *Accum =
nullptr;
5816 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5818 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5832 insertValueToMap(PN, PHISCEV);
5837 proveNoWrapViaConstantRanges(AR)));
5845 "Accum is defined outside L, but is not invariant?");
5846 if (isAddRecNeverPoison(BEInst, L))
5853const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5854 const Loop *
L = LI.getLoopFor(PN->
getParent());
5861 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5867 }
else if (BEValueV != V) {
5871 }
else if (!StartValueV) {
5873 }
else if (StartValueV != V) {
5874 StartValueV =
nullptr;
5878 if (!BEValueV || !StartValueV)
5881 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5882 "PHI node already processed?");
5886 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5891 insertValueToMap(PN, SymbolicName);
5895 const SCEV *BEValue =
getSCEV(BEValueV);
5905 unsigned FoundIndex =
Add->getNumOperands();
5906 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5907 if (
Add->getOperand(i) == SymbolicName)
5908 if (FoundIndex == e) {
5913 if (FoundIndex !=
Add->getNumOperands()) {
5916 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5917 if (i != FoundIndex)
5918 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5930 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5937 if (
GEP->getOperand(0) == PN) {
5938 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
5956 const SCEV *StartVal =
getSCEV(StartValueV);
5957 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5962 forgetMemoizedResults(SymbolicName);
5963 insertValueToMap(PN, PHISCEV);
5968 proveNoWrapViaConstantRanges(AR)));
5993 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5994 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5996 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5997 const SCEV *StartVal =
getSCEV(StartValueV);
5998 if (Start == StartVal) {
6002 forgetMemoizedResults(SymbolicName);
6003 insertValueToMap(PN, Shifted);
6013 eraseValueFromMap(PN);
6033 Use &LeftUse =
Merge->getOperandUse(0);
6034 Use &RightUse =
Merge->getOperandUse(1);
6051const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
6053 [&](
BasicBlock *BB) {
return DT.isReachableFromEntry(BB); };
6068 assert(IDom &&
"At least the entry block should dominate PN");
6077 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6093ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6094 BinaryOperator *CommonInst =
nullptr;
6105 CommonInst = IncomingInst;
6112 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6113 bool SCEVExprsIdentical =
6115 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6116 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6119const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6120 if (
const SCEV *S = createAddRecFromPHI(PN))
6130 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6133 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6142 struct FindClosure {
6143 const SCEV *OperandToFind;
6149 bool canRecurseInto(
SCEVTypes Kind)
const {
6152 return RootKind == Kind || NonSequentialRootKind == Kind ||
6157 : OperandToFind(OperandToFind), RootKind(RootKind),
6158 NonSequentialRootKind(
6162 bool follow(
const SCEV *S) {
6163 Found = S == OperandToFind;
6165 return !isDone() && canRecurseInto(S->
getSCEVType());
6168 bool isDone()
const {
return Found; }
6171 FindClosure FC(OperandToFind, RootKind);
6176std::optional<const SCEV *>
6177ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6187 switch (ICI->getPredicate()) {
6201 bool Signed = ICI->isSigned();
6202 const SCEV *LA =
getSCEV(TrueVal);
6210 if (LA == LS &&
RA == RS)
6212 if (LA == RS &&
RA == LS)
6215 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6216 if (
Op->getType()->isPointerTy()) {
6227 LS = CoerceOperand(LS);
6228 RS = CoerceOperand(RS);
6252 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6253 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6267 X = ZExt->getOperand();
6269 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6280 return std::nullopt;
6283static std::optional<const SCEV *>
6285 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6289 "Unexpected operands of a select.");
6301 return std::nullopt;
6316static std::optional<const SCEV *>
6320 return std::nullopt;
6323 const auto *SETrue = SE->
getSCEV(TrueVal);
6324 const auto *SEFalse = SE->
getSCEV(FalseVal);
6328const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6330 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6332 V->getType() ==
TrueVal->getType() &&
6333 "Types of select hands and of the result must match.");
6336 if (!
V->getType()->isIntegerTy(1))
6339 if (std::optional<const SCEV *> S =
6352 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6356 if (std::optional<const SCEV *> S =
6357 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6363 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6369 assert(
GEP->getSourceElementType()->isSized() &&
6370 "GEP source element type must be sized");
6373 for (
Value *Index :
GEP->indices())
6378APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6381 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6384 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6386 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6389 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6408 return GetShiftedByZeros(TZ);
6418 return GetShiftedByZeros(TZ);
6422 if (
M->hasNoUnsignedWrap()) {
6425 for (
const SCEV *Operand :
M->operands().drop_front())
6433 for (
const SCEV *Operand :
M->operands())
6435 return GetShiftedByZeros(TZ);
6440 if (
N->hasNoUnsignedWrap())
6441 return GetGCDMultiple(
N);
6444 for (
const SCEV *Operand :
N->operands().drop_front())
6446 return GetShiftedByZeros(TZ);
6463 CtxI = &*F.getEntryBlock().begin();
6469 .countMinTrailingZeros();
6470 return GetShiftedByZeros(Known);
6483 return getConstantMultipleImpl(S, CtxI);
6485 auto I = ConstantMultipleCache.find(S);
6486 if (
I != ConstantMultipleCache.end())
6489 APInt Result = getConstantMultipleImpl(S, CtxI);
6490 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6491 assert(InsertPair.second &&
"Should insert a new key");
6492 return InsertPair.first->second;
6509 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6512 if (std::optional<ConstantRange>
Range = CB->getRange())
6516 if (std::optional<ConstantRange>
Range =
A->getRange())
6519 return std::nullopt;
6526 UnsignedRanges.erase(AddRec);
6527 SignedRanges.erase(AddRec);
6528 ConstantMultipleCache.erase(AddRec);
6533getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6559 Value *Start, *Step;
6566 assert(L && L->getHeader() ==
P->getParent());
6579 case Instruction::AShr:
6580 case Instruction::LShr:
6581 case Instruction::Shl:
6596 KnownStep.getBitWidth() ==
BitWidth);
6599 auto MaxShiftAmt = KnownStep.getMaxValue();
6601 bool Overflow =
false;
6602 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6609 case Instruction::AShr: {
6617 if (KnownStart.isNonNegative())
6620 KnownStart.getMaxValue() + 1);
6621 if (KnownStart.isNegative())
6624 KnownEnd.getMaxValue() + 1);
6627 case Instruction::LShr: {
6636 KnownStart.getMaxValue() + 1);
6638 case Instruction::Shl: {
6642 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6643 return ConstantRange(KnownStart.getMinValue(),
6644 KnownEnd.getMaxValue() + 1);
6652ScalarEvolution::getRangeRefIter(
const SCEV *S,
6653 ScalarEvolution::RangeSignHint SignHint) {
6654 DenseMap<const SCEV *, ConstantRange> &Cache =
6655 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6658 SmallPtrSet<const SCEV *, 8> Seen;
6662 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6663 if (!Seen.
insert(Expr).second)
6697 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6698 const SCEV *
P = WorkList[
I];
6702 for (
const SCEV *
Op :
P->operands())
6708 if (!PendingPhiRangesIter.insert(
P).second)
6715 if (!WorkList.
empty()) {
6720 getRangeRef(
P, SignHint);
6724 PendingPhiRangesIter.erase(
P);
6728 return getRangeRef(S, SignHint, 0);
6735 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6736 DenseMap<const SCEV *, ConstantRange> &Cache =
6737 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6745 if (
I != Cache.
end())
6749 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6754 return getRangeRefIter(S, SignHint);
6757 ConstantRange ConservativeResult(
BitWidth,
true);
6758 using OBO = OverflowingBinaryOperator;
6762 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6766 ConservativeResult =
6773 ConservativeResult = ConstantRange(
6789 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6796 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6803 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6809 return setRange(Cast, SignHint,
X);
6814 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6815 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6817 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6818 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6819 ConservativeResult =
6820 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6822 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6823 unsigned WrapType = OBO::AnyWrap;
6824 if (
Add->hasNoSignedWrap())
6825 WrapType |= OBO::NoSignedWrap;
6826 if (
Add->hasNoUnsignedWrap())
6827 WrapType |= OBO::NoUnsignedWrap;
6829 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6831 return setRange(
Add, SignHint,
6832 ConservativeResult.intersectWith(
X, RangeType));
6836 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6838 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6839 return setRange(
Mul, SignHint,
6840 ConservativeResult.intersectWith(
X, RangeType));
6844 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6845 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6846 return setRange(UDiv, SignHint,
6847 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6855 if (!UnsignedMinValue.
isZero())
6856 ConservativeResult = ConservativeResult.intersectWith(
6857 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6866 bool AllNonNeg =
true;
6867 bool AllNonPos =
true;
6868 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6875 ConservativeResult = ConservativeResult.intersectWith(
6880 ConservativeResult = ConservativeResult.intersectWith(
6889 const SCEV *MaxBEScev =
6903 auto RangeFromAffine = getRangeForAffineAR(
6905 ConservativeResult =
6906 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6908 auto RangeFromFactoring = getRangeViaFactoring(
6910 ConservativeResult =
6911 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6917 const SCEV *SymbolicMaxBECount =
6922 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6923 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6924 ConservativeResult =
6925 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6930 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6940 ID = Intrinsic::umax;
6943 ID = Intrinsic::smax;
6947 ID = Intrinsic::umin;
6950 ID = Intrinsic::smin;
6957 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6958 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6960 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6961 return setRange(S, SignHint,
6962 ConservativeResult.intersectWith(
X, RangeType));
6971 ConservativeResult =
6972 ConservativeResult.intersectWith(*MDRange, RangeType);
6977 auto CR = getRangeForUnknownRecurrence(U);
6978 ConservativeResult = ConservativeResult.intersectWith(CR);
6989 if (
U->getType()->isPointerTy()) {
6992 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
6993 int ptrIdxDiff = ptrSize -
BitWidth;
6994 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
7007 ConservativeResult = ConservativeResult.intersectWith(
7011 ConservativeResult = ConservativeResult.intersectWith(
7016 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
7019 bool CanBeNull, CanBeFreed;
7020 uint64_t DerefBytes =
7021 V->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed);
7031 uint64_t
Align =
U->getValue()->getPointerAlignment(DL).value();
7032 uint64_t Rem = MaxVal.
urem(Align);
7037 ConservativeResult = ConservativeResult.intersectWith(
7045 if (PendingPhiRanges.insert(Phi).second) {
7046 ConstantRange RangeFromOps(
BitWidth,
false);
7048 for (
const auto &
Op :
Phi->operands()) {
7050 RangeFromOps = RangeFromOps.unionWith(OpRange);
7052 if (RangeFromOps.isFullSet())
7055 ConservativeResult =
7056 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7057 bool Erased = PendingPhiRanges.erase(Phi);
7058 assert(Erased &&
"Failed to erase Phi properly?");
7065 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7067 ConservativeResult = ConservativeResult.difference(Disallowed);
7070 return setRange(U, SignHint, std::move(ConservativeResult));
7076 return setRange(S, SignHint, std::move(ConservativeResult));
7085 const APInt &MaxBECount,
7092 if (Step == 0 || MaxBECount == 0)
7099 return ConstantRange::getFull(
BitWidth);
7115 return ConstantRange::getFull(
BitWidth);
7127 APInt MovedBoundary = Descending ? (StartLower - std::move(
Offset))
7128 : (StartUpper + std::move(
Offset));
7133 if (StartRange.
contains(MovedBoundary))
7134 return ConstantRange::getFull(
BitWidth);
7137 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7139 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7148 const APInt &MaxBECount) {
7152 "mismatched bit widths");
7161 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7163 StartSRange, MaxBECount,
7175ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7177 ScalarEvolution::RangeSignHint SignHint) {
7178 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7180 "This only works for non-self-wrapping AddRecs!");
7181 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7185 return ConstantRange::getFull(
BitWidth);
7193 return ConstantRange::getFull(
BitWidth);
7197 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7199 MaxItersWithoutWrap))
7200 return ConstantRange::getFull(
BitWidth);
7221 ConstantRange StartRange = getRangeRef(Start, SignHint);
7222 ConstantRange EndRange = getRangeRef(End, SignHint);
7223 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7227 return RangeBetween;
7232 return ConstantRange::getFull(
BitWidth);
7235 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7236 return RangeBetween;
7238 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7239 return RangeBetween;
7240 return ConstantRange::getFull(
BitWidth);
7245 const APInt &MaxBECount) {
7252 "mismatched bit widths");
7254 struct SelectPattern {
7255 Value *Condition =
nullptr;
7259 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7261 std::optional<unsigned> CastOp;
7275 CastOp = SCast->getSCEVType();
7276 S = SCast->getOperand();
7279 using namespace llvm::PatternMatch;
7286 Condition =
nullptr;
7318 bool isRecognized() {
return Condition !=
nullptr; }
7321 SelectPattern StartPattern(*
this,
BitWidth, Start);
7322 if (!StartPattern.isRecognized())
7323 return ConstantRange::getFull(
BitWidth);
7325 SelectPattern StepPattern(*
this,
BitWidth, Step);
7326 if (!StepPattern.isRecognized())
7327 return ConstantRange::getFull(
BitWidth);
7329 if (StartPattern.Condition != StepPattern.Condition) {
7333 return ConstantRange::getFull(
BitWidth);
7344 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7345 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7346 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7347 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7349 ConstantRange TrueRange =
7350 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount);
7351 ConstantRange FalseRange =
7352 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount);
7374ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7388 SmallPtrSet<const SCEV *, 16> Visited;
7390 auto pushOp = [&](
const SCEV *S) {
7391 if (!Visited.
insert(S).second)
7394 if (Visited.
size() > 30) {
7401 for (
const auto *S :
Ops)
7405 while (!Worklist.
empty()) {
7407 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7408 if (!Bound || DT.dominates(Bound, DefI))
7415 return Bound ? Bound : &*F.getEntryBlock().begin();
7421 return getDefiningScopeBound(
Ops, Discard);
7424bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7426 if (
A->getParent() ==
B->getParent() &&
7431 auto *BLoop = LI.getLoopFor(
B->getParent());
7432 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7433 BLoop->getLoopPreheader() ==
A->getParent() &&
7435 A->getParent()->end()) &&
7442bool ScalarEvolution::isGuaranteedNotToBePoison(
const SCEV *
Op) {
7443 SCEVPoisonCollector PC(
true);
7445 return PC.MaybePoison.empty();
7448bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7454 return M && (!
isKnownNonZero(Op1) || !isGuaranteedNotToBePoison(Op1));
7458bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7475 for (
const Use &
Op :
I->operands()) {
7481 auto *DefI = getDefiningScopeBound(SCEVOps);
7482 return isGuaranteedToTransferExecutionTo(DefI,
I);
7485bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7487 if (isSCEVExprNeverPoison(
I))
7498 auto *ExitingBB =
L->getExitingBlock();
7502 SmallPtrSet<const Value *, 16> KnownPoison;
7511 while (!Worklist.
empty()) {
7514 for (
const Use &U :
Poison->uses()) {
7517 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7521 if (KnownPoison.
insert(PoisonUser).second)
7529ScalarEvolution::LoopProperties
7530ScalarEvolution::getLoopProperties(
const Loop *L) {
7531 using LoopProperties = ScalarEvolution::LoopProperties;
7533 auto Itr = LoopPropertiesCache.find(L);
7534 if (Itr == LoopPropertiesCache.end()) {
7537 return !
SI->isSimple();
7547 return I->mayWriteToMemory();
7550 LoopProperties LP = {
true,
7553 for (
auto *BB :
L->getBlocks())
7554 for (
auto &
I : *BB) {
7556 LP.HasNoAbnormalExits =
false;
7557 if (HasSideEffects(&
I))
7558 LP.HasNoSideEffects =
false;
7559 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7563 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7564 assert(InsertPair.second &&
"We just checked!");
7565 Itr = InsertPair.first;
7578const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7584 Stack.emplace_back(V,
true);
7585 Stack.emplace_back(V,
false);
7586 while (!Stack.empty()) {
7587 auto E = Stack.pop_back_val();
7588 Value *CurV = E.getPointer();
7594 const SCEV *CreatedSCEV =
nullptr;
7597 CreatedSCEV = createSCEV(CurV);
7602 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7606 insertValueToMap(CurV, CreatedSCEV);
7610 Stack.emplace_back(CurV,
true);
7612 Stack.emplace_back(
Op,
false);
7629 if (!DT.isReachableFromEntry(
I->getParent()))
7642 switch (BO->Opcode) {
7643 case Instruction::Add:
7644 case Instruction::Mul: {
7651 Ops.push_back(BO->
Op);
7655 Ops.push_back(BO->RHS);
7659 (BO->Opcode == Instruction::Add &&
7660 (NewBO->Opcode != Instruction::Add &&
7661 NewBO->Opcode != Instruction::Sub)) ||
7662 (BO->Opcode == Instruction::Mul &&
7663 NewBO->Opcode != Instruction::Mul)) {
7664 Ops.push_back(BO->LHS);
7669 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7672 Ops.push_back(BO->LHS);
7680 case Instruction::Sub:
7681 case Instruction::UDiv:
7682 case Instruction::URem:
7684 case Instruction::AShr:
7685 case Instruction::Shl:
7686 case Instruction::Xor:
7690 case Instruction::And:
7691 case Instruction::Or:
7695 case Instruction::LShr:
7702 Ops.push_back(BO->LHS);
7703 Ops.push_back(BO->RHS);
7707 switch (
U->getOpcode()) {
7708 case Instruction::Trunc:
7709 case Instruction::ZExt:
7710 case Instruction::SExt:
7711 case Instruction::PtrToAddr:
7712 case Instruction::PtrToInt:
7713 Ops.push_back(
U->getOperand(0));
7716 case Instruction::BitCast:
7718 Ops.push_back(
U->getOperand(0));
7723 case Instruction::SDiv:
7724 case Instruction::SRem:
7725 Ops.push_back(
U->getOperand(0));
7726 Ops.push_back(
U->getOperand(1));
7729 case Instruction::GetElementPtr:
7731 "GEP source element type must be sized");
7735 case Instruction::IntToPtr:
7738 case Instruction::PHI:
7742 case Instruction::Select: {
7744 auto CanSimplifyToUnknown = [
this,
U]() {
7762 if (CanSimplifyToUnknown())
7769 case Instruction::Call:
7770 case Instruction::Invoke:
7777 switch (
II->getIntrinsicID()) {
7778 case Intrinsic::abs:
7779 Ops.push_back(
II->getArgOperand(0));
7781 case Intrinsic::umax:
7782 case Intrinsic::umin:
7783 case Intrinsic::smax:
7784 case Intrinsic::smin:
7785 case Intrinsic::usub_sat:
7786 case Intrinsic::uadd_sat:
7787 Ops.push_back(
II->getArgOperand(0));
7788 Ops.push_back(
II->getArgOperand(1));
7790 case Intrinsic::start_loop_iterations:
7791 case Intrinsic::annotation:
7792 case Intrinsic::ptr_annotation:
7793 Ops.push_back(
II->getArgOperand(0));
7805const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7814 if (!DT.isReachableFromEntry(
I->getParent()))
7829 switch (BO->Opcode) {
7830 case Instruction::Add: {
7856 if (BO->Opcode == Instruction::Sub)
7864 if (BO->Opcode == Instruction::Sub)
7871 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7872 NewBO->Opcode != Instruction::Sub)) {
7882 case Instruction::Mul: {
7903 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7912 case Instruction::UDiv:
7916 case Instruction::URem:
7920 case Instruction::Sub: {
7923 Flags = getNoWrapFlagsFromUB(BO->
Op);
7928 case Instruction::And:
7934 if (CI->isMinusOne())
7936 const APInt &
A = CI->getValue();
7942 unsigned LZ =
A.countl_zero();
7943 unsigned TZ =
A.countr_zero();
7948 APInt EffectiveMask =
7950 if ((LZ != 0 || TZ != 0) && !((~
A & ~Known.
Zero) & EffectiveMask)) {
7953 const SCEV *ShiftedLHS =
nullptr;
7957 unsigned MulZeros = OpC->getAPInt().countr_zero();
7958 unsigned GCD = std::min(MulZeros, TZ);
7963 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
7985 case Instruction::Or:
7994 case Instruction::Xor:
7997 if (CI->isMinusOne())
8006 if (LBO->getOpcode() == Instruction::And &&
8007 LCI->getValue() == CI->getValue())
8008 if (
const SCEVZeroExtendExpr *Z =
8011 const SCEV *Z0 =
Z->getOperand();
8018 if (CI->getValue().isMask(Z0TySize))
8024 APInt Trunc = CI->getValue().trunc(Z0TySize);
8033 case Instruction::Shl:
8051 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8059 ConstantInt *
X = ConstantInt::get(
8065 case Instruction::AShr:
8087 const SCEV *AddTruncateExpr =
nullptr;
8088 ConstantInt *ShlAmtCI =
nullptr;
8089 const SCEV *AddConstant =
nullptr;
8091 if (L &&
L->getOpcode() == Instruction::Add) {
8099 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8106 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8114 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8119 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8124 if (AddTruncateExpr && ShlAmtCI) {
8136 const APInt &ShlAmt = ShlAmtCI->
getValue();
8140 const SCEV *CompositeExpr =
8142 if (
L->getOpcode() != Instruction::Shl)
8143 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8152 switch (
U->getOpcode()) {
8153 case Instruction::Trunc:
8156 case Instruction::ZExt:
8159 case Instruction::SExt:
8169 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8170 Type *Ty =
U->getType();
8178 case Instruction::BitCast:
8184 case Instruction::PtrToAddr: {
8191 case Instruction::PtrToInt: {
8194 Type *DstIntTy =
U->getType();
8202 case Instruction::IntToPtr:
8206 case Instruction::SDiv:
8213 case Instruction::SRem:
8220 case Instruction::GetElementPtr:
8223 case Instruction::PHI:
8226 case Instruction::Select:
8227 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8230 case Instruction::Call:
8231 case Instruction::Invoke:
8236 switch (
II->getIntrinsicID()) {
8237 case Intrinsic::abs:
8241 case Intrinsic::umax:
8245 case Intrinsic::umin:
8249 case Intrinsic::smax:
8253 case Intrinsic::smin:
8257 case Intrinsic::usub_sat: {
8258 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8259 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8263 case Intrinsic::uadd_sat: {
8264 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8265 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8269 case Intrinsic::start_loop_iterations:
8270 case Intrinsic::annotation:
8271 case Intrinsic::ptr_annotation:
8275 case Intrinsic::vscale:
8295 auto *ExitCountType = ExitCount->
getType();
8296 assert(ExitCountType->isIntegerTy());
8298 1 + ExitCountType->getScalarSizeInBits());
8311 auto CanAddOneWithoutOverflow = [&]() {
8313 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8324 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8354 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8355 assert(L->isLoopExiting(ExitingBlock) &&
8356 "Exiting block must actually branch out of the loop!");
8365 const auto *MaxExitCount =
8373 L->getExitingBlocks(ExitingBlocks);
8375 std::optional<unsigned> Res;
8376 for (
auto *ExitingBB : ExitingBlocks) {
8380 Res = std::gcd(*Res, Multiple);
8382 return Res.value_or(1);
8386 const SCEV *ExitCount) {
8416 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8417 assert(L->isLoopExiting(ExitingBlock) &&
8418 "Exiting block must actually branch out of the loop!");
8428 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8430 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8432 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8442 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8445 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8448 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8456 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8463 return getBackedgeTakenInfo(L).getExact(L,
this);
8465 return getBackedgeTakenInfo(L).getConstantMax(
this);
8467 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8474 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8479 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8483 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8493 for (
PHINode &PN : Header->phis())
8494 if (Visited.
insert(&PN).second)
8498ScalarEvolution::BackedgeTakenInfo &
8499ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8500 auto &BTI = getBackedgeTakenInfo(L);
8501 if (BTI.hasFullInfo())
8504 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8507 return Pair.first->second;
8509 BackedgeTakenInfo
Result =
8510 computeBackedgeTakenCount(L,
true);
8512 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8515ScalarEvolution::BackedgeTakenInfo &
8516ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8522 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8523 BackedgeTakenCounts.try_emplace(L);
8525 return Pair.first->second;
8530 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8537 if (
Result.hasAnyInfo()) {
8540 auto LoopUsersIt = LoopUsers.find(L);
8541 if (LoopUsersIt != LoopUsers.end())
8543 forgetMemoizedResults(ToForget);
8546 for (PHINode &PN :
L->getHeader()->phis())
8547 ConstantEvolutionLoopExitValue.erase(&PN);
8555 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8564 BackedgeTakenCounts.clear();
8565 PredicatedBackedgeTakenCounts.clear();
8566 BECountUsers.clear();
8567 LoopPropertiesCache.clear();
8568 ConstantEvolutionLoopExitValue.clear();
8569 ValueExprMap.clear();
8570 ValuesAtScopes.clear();
8571 ValuesAtScopesUsers.clear();
8572 LoopDispositions.clear();
8573 BlockDispositions.clear();
8574 UnsignedRanges.clear();
8575 SignedRanges.clear();
8576 ExprValueMap.clear();
8578 ConstantMultipleCache.clear();
8579 PredicatedSCEVRewrites.clear();
8581 FoldCacheUser.clear();
8583void ScalarEvolution::visitAndClearUsers(
8587 while (!Worklist.
empty()) {
8594 if (It != ValueExprMap.
end()) {
8595 eraseValueFromMap(It->first);
8598 ConstantEvolutionLoopExitValue.erase(PN);
8612 while (!LoopWorklist.
empty()) {
8616 forgetBackedgeTakenCounts(CurrL,
false);
8617 forgetBackedgeTakenCounts(CurrL,
true);
8620 for (
auto I = PredicatedSCEVRewrites.begin();
8621 I != PredicatedSCEVRewrites.end();) {
8622 std::pair<const SCEV *, const Loop *> Entry =
I->first;
8623 if (Entry.second == CurrL)
8624 PredicatedSCEVRewrites.erase(
I++);
8629 auto LoopUsersItr = LoopUsers.find(CurrL);
8630 if (LoopUsersItr != LoopUsers.end())
8635 visitAndClearUsers(Worklist, Visited, ToForget);
8637 LoopPropertiesCache.erase(CurrL);
8640 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8642 forgetMemoizedResults(ToForget);
8659 visitAndClearUsers(Worklist, Visited, ToForget);
8661 forgetMemoizedResults(ToForget);
8673 struct InvalidationRootCollector {
8677 InvalidationRootCollector(
Loop *L) : L(L) {}
8679 bool follow(
const SCEV *S) {
8685 if (L->contains(AddRec->
getLoop()))
8690 bool isDone()
const {
return false; }
8693 InvalidationRootCollector
C(L);
8695 forgetMemoizedResults(
C.Roots);
8708 BlockDispositions.clear();
8709 LoopDispositions.clear();
8726 while (!Worklist.
empty()) {
8728 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8729 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8730 if (!LoopDispoRemoved && !BlockDispoRemoved)
8732 auto Users = SCEVUsers.find(Curr);
8733 if (
Users != SCEVUsers.end())
8746const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8750 if (!isComplete() || ExitNotTaken.
empty())
8761 for (
const auto &ENT : ExitNotTaken) {
8762 const SCEV *BECount = ENT.ExactNotTaken;
8765 "We should only have known counts for exiting blocks that dominate "
8768 Ops.push_back(BECount);
8773 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8774 "Predicate should be always true!");
8783const ScalarEvolution::ExitNotTakenInfo *
8784ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8785 const BasicBlock *ExitingBlock,
8786 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8787 for (
const auto &ENT : ExitNotTaken)
8788 if (ENT.ExitingBlock == ExitingBlock) {
8789 if (ENT.hasAlwaysTruePredicate())
8791 else if (Predicates) {
8801const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8803 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8804 if (!getConstantMax())
8807 for (
const auto &ENT : ExitNotTaken)
8808 if (!ENT.hasAlwaysTruePredicate()) {
8816 "No point in having a non-constant max backedge taken count!");
8817 return getConstantMax();
8820const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8822 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8830 for (
const auto &ENT : ExitNotTaken) {
8831 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8834 "We should only have known counts for exiting blocks that "
8840 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8841 "Predicate should be always true!");
8844 if (ExitCounts.
empty())
8853bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8855 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8856 return !ENT.hasAlwaysTruePredicate();
8858 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8874 this->ExactNotTaken = E = ConstantMaxNotTaken;
8875 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8880 "Exact is not allowed to be less precise than Constant Max");
8883 "Exact is not allowed to be less precise than Symbolic Max");
8886 "Symbolic Max is not allowed to be less precise than Constant Max");
8889 "No point in having a non-constant max backedge taken count!");
8891 for (
const auto PredList : PredLists)
8892 for (
const auto *
P : PredList) {
8900 "Backedge count should be int");
8903 "Max backedge count should be int");
8916ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8918 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8919 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8920 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8922 ExitNotTaken.reserve(ExitCounts.
size());
8923 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8924 std::back_inserter(ExitNotTaken),
8925 [&](
const EdgeExitInfo &EEI) {
8926 BasicBlock *ExitBB = EEI.first;
8927 const ExitLimit &EL = EEI.second;
8928 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
8929 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
8934 "No point in having a non-constant max backedge taken count!");
8938ScalarEvolution::BackedgeTakenInfo
8939ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
8940 bool AllowPredicates) {
8942 L->getExitingBlocks(ExitingBlocks);
8944 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8947 bool CouldComputeBECount =
true;
8949 const SCEV *MustExitMaxBECount =
nullptr;
8950 const SCEV *MayExitMaxBECount =
nullptr;
8951 bool MustExitMaxOrZero =
false;
8952 bool IsOnlyExit = ExitingBlocks.
size() == 1;
8964 if (ExitIfTrue == CI->
isZero())
8968 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
8970 assert((AllowPredicates || EL.Predicates.empty()) &&
8971 "Predicated exit limit when predicates are not allowed!");
8976 ++NumExitCountsComputed;
8980 CouldComputeBECount =
false;
8987 "Exact is known but symbolic isn't?");
8988 ++NumExitCountsNotComputed;
9003 DT.dominates(ExitBB, Latch)) {
9004 if (!MustExitMaxBECount) {
9005 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9006 MustExitMaxOrZero = EL.MaxOrZero;
9009 EL.ConstantMaxNotTaken);
9013 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9016 EL.ConstantMaxNotTaken);
9020 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9024 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9030 for (
const auto &Pair : ExitCounts) {
9032 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9034 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9035 {
L, AllowPredicates});
9037 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9038 MaxBECount, MaxOrZero);
9041ScalarEvolution::ExitLimit
9042ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9043 bool IsOnlyExit,
bool AllowPredicates) {
9044 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9048 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9056 "It should have one successor in loop and one exit block!");
9067 if (!
L->contains(SBB)) {
9072 assert(Exit &&
"Exiting block must have at least one exit");
9073 return computeExitLimitFromSingleExitSwitch(
9074 L, SI, Exit, IsOnlyExit);
9081 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9082 bool AllowPredicates) {
9083 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9084 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9085 ControlsOnlyExit, AllowPredicates);
9088std::optional<ScalarEvolution::ExitLimit>
9089ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9090 bool ExitIfTrue,
bool ControlsOnlyExit,
9091 bool AllowPredicates) {
9093 (void)this->ExitIfTrue;
9094 (void)this->AllowPredicates;
9096 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9097 this->AllowPredicates == AllowPredicates &&
9098 "Variance in assumed invariant key components!");
9099 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9100 if (Itr == TripCountMap.end())
9101 return std::nullopt;
9105void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9107 bool ControlsOnlyExit,
9108 bool AllowPredicates,
9110 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9111 this->AllowPredicates == AllowPredicates &&
9112 "Variance in assumed invariant key components!");
9114 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9115 assert(InsertResult.second &&
"Expected successful insertion!");
9120ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9121 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9122 bool ControlsOnlyExit,
bool AllowPredicates) {
9124 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9128 ExitLimit EL = computeExitLimitFromCondImpl(
9129 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9130 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9134ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9135 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9136 bool ControlsOnlyExit,
bool AllowPredicates) {
9138 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9139 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates))
9140 return *LimitFromBinOp;
9146 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9147 if (EL.hasFullInfo() || !AllowPredicates)
9151 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9171 const WithOverflowInst *WO;
9186 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9187 ControlsOnlyExit, AllowPredicates);
9188 if (EL.hasAnyInfo())
9193 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9196std::optional<ScalarEvolution::ExitLimit>
9197ScalarEvolution::computeExitLimitFromCondFromBinOp(
9198 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9199 bool ControlsOnlyExit,
bool AllowPredicates) {
9208 return std::nullopt;
9213 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9214 ExitLimit EL0 = computeExitLimitFromCondCached(
9215 Cache, L, Op0, ExitIfTrue, ControlsOnlyExit && !EitherMayExit,
9217 ExitLimit EL1 = computeExitLimitFromCondCached(
9218 Cache, L, Op1, ExitIfTrue, ControlsOnlyExit && !EitherMayExit,
9222 const Constant *NeutralElement = ConstantInt::get(ExitCond->
getType(), IsAnd);
9224 return Op1 == NeutralElement ? EL0 : EL1;
9226 return Op0 == NeutralElement ? EL1 : EL0;
9231 if (EitherMayExit) {
9241 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9243 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9246 EL1.ConstantMaxNotTaken);
9248 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9250 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9253 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9257 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9258 BECount = EL0.ExactNotTaken;
9271 SymbolicMaxBECount =
9273 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9277ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9278 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9279 bool AllowPredicates) {
9291 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9293 if (EL.hasAnyInfo())
9296 auto *ExhaustiveCount =
9297 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9300 return ExhaustiveCount;
9302 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9305ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9306 const Loop *L, CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
9307 bool ControlsOnlyExit,
bool AllowPredicates) {
9332 ConstantRange CompRange =
9348 auto *InnerLHS =
LHS;
9350 InnerLHS = ZExt->getOperand();
9397 if (EL.hasAnyInfo())
9414 if (EL.hasAnyInfo())
return EL;
9446 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9448 if (EL.hasAnyInfo())
9464 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9466 if (EL.hasAnyInfo())
9477ScalarEvolution::ExitLimit
9478ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9480 BasicBlock *ExitingBlock,
9481 bool ControlsOnlyExit) {
9482 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9485 if (
Switch->getDefaultDest() == ExitingBlock)
9489 "Default case must not exit the loop!");
9495 if (EL.hasAnyInfo())
9507 "Evaluation of SCEV at constant didn't fold correctly?");
9511ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9521 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9527 auto MatchPositiveShift =
9530 using namespace PatternMatch;
9532 ConstantInt *ShiftAmt;
9534 OutOpCode = Instruction::LShr;
9536 OutOpCode = Instruction::AShr;
9538 OutOpCode = Instruction::Shl;
9553 auto MatchShiftRecurrence =
9555 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9570 if (MatchPositiveShift(
LHS, V, OpC)) {
9571 PostShiftOpCode = OpC;
9577 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9580 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9586 MatchPositiveShift(BEValue, OpLHS, OpCodeOut) &&
9593 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9598 if (!MatchShiftRecurrence(
LHS, PN, OpCode))
9610 ConstantInt *StableValue =
nullptr;
9615 case Instruction::AShr: {
9623 StableValue = ConstantInt::get(Ty, 0);
9625 StableValue = ConstantInt::get(Ty, -1,
true);
9631 case Instruction::LShr:
9632 case Instruction::Shl:
9642 "Otherwise cannot be an operand to a branch instruction");
9644 if (
Result->isNullValue()) {
9646 const SCEV *UpperBound =
9663 if (
const Function *
F = CI->getCalledFunction())
9672 if (!L->contains(
I))
return false;
9677 return L->getHeader() ==
I->getParent();
9753 if (!
I)
return nullptr;
9766 std::vector<Constant*> Operands(
I->getNumOperands());
9768 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9772 if (!Operands[i])
return nullptr;
9777 if (!
C)
return nullptr;
9799 if (IncomingVal != CurrentVal) {
9802 IncomingVal = CurrentVal;
9814ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9817 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9826 DenseMap<Instruction *, Constant *> CurrentIterVals;
9828 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9834 for (PHINode &
PHI : Header->phis()) {
9836 CurrentIterVals[&
PHI] = StartCST;
9838 if (!CurrentIterVals.
count(PN))
9839 return RetVal =
nullptr;
9845 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9848 unsigned IterationNum = 0;
9850 for (; ; ++IterationNum) {
9851 if (IterationNum == NumIterations)
9852 return RetVal = CurrentIterVals[PN];
9856 DenseMap<Instruction *, Constant *> NextIterVals;
9861 NextIterVals[PN] = NextPHI;
9863 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9869 for (
const auto &
I : CurrentIterVals) {
9871 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9876 for (
const auto &
I : PHIsToCompute) {
9877 PHINode *
PHI =
I.first;
9880 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9883 if (NextPHI !=
I.second)
9884 StoppedEvolving =
false;
9889 if (StoppedEvolving)
9890 return RetVal = CurrentIterVals[PN];
9892 CurrentIterVals.swap(NextIterVals);
9896const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
9906 DenseMap<Instruction *, Constant *> CurrentIterVals;
9908 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9911 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
9913 for (PHINode &
PHI : Header->phis()) {
9915 CurrentIterVals[&
PHI] = StartCST;
9917 if (!CurrentIterVals.
count(PN))
9925 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
9932 if (CondVal->getValue() == uint64_t(ExitWhen)) {
9933 ++NumBruteForceTripCountsComputed;
9938 DenseMap<Instruction *, Constant *> NextIterVals;
9944 for (
const auto &
I : CurrentIterVals) {
9946 if (!
PHI ||
PHI->getParent() != Header)
continue;
9949 for (PHINode *
PHI : PHIsToCompute) {
9951 if (NextPHI)
continue;
9953 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9956 CurrentIterVals.
swap(NextIterVals);
9967 for (
auto &LS : Values)
9969 return LS.second ? LS.second : V;
9974 const SCEV *
C = computeSCEVAtScope(V, L);
9975 for (
auto &LS :
reverse(ValuesAtScopes[V]))
9976 if (LS.first == L) {
9979 ValuesAtScopesUsers[
C].push_back({L, V});
9990 switch (V->getSCEVType()) {
10030 assert(!
C->getType()->isPointerTy() &&
10031 "Can only have one pointer, and it must be last");
10057ScalarEvolution::getWithOperands(
const SCEV *S,
10058 SmallVectorImpl<const SCEV *> &NewOps) {
10093const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10094 switch (
V->getSCEVType()) {
10105 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10116 for (++i; i !=
e; ++i)
10161 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10163 if (OpAtScope !=
Ops[i]) {
10171 for (++i; i !=
e; ++i) {
10176 return getWithOperands(V, NewOps);
10191 const Loop *CurrLoop = this->LI[
I->getParent()];
10202 if (BackedgeTakenCount->
isZero()) {
10203 Value *InitValue =
nullptr;
10204 bool MultipleInitValues =
false;
10210 MultipleInitValues =
true;
10215 if (!MultipleInitValues && InitValue)
10224 unsigned InLoopPred =
10235 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10249 SmallVector<Constant *, 4> Operands;
10250 Operands.
reserve(
I->getNumOperands());
10251 bool MadeImprovement =
false;
10266 MadeImprovement |= OrigV != OpV;
10271 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10276 if (!MadeImprovement)
10297const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10299 return stripInjectiveFunctions(ZExt->getOperand());
10301 return stripInjectiveFunctions(SExt->getOperand());
10319 assert(
A != 0 &&
"A must be non-zero.");
10335 if (MinTZ < Mult2 && L->getLoopPredecessor())
10337 if (MinTZ < Mult2) {
10360 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10380static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10386 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10387 << *AddRec <<
'\n');
10390 if (!LC || !MC || !
NC) {
10391 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10392 return std::nullopt;
10398 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10406 N =
N.sext(NewWidth);
10407 M = M.sext(NewWidth);
10408 L = L.sext(NewWidth);
10425 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10426 <<
", multiplied by " <<
T <<
'\n');
10435 std::optional<APInt>
Y) {
10437 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10440 return XW.
slt(YW) ? *
X : *
Y;
10443 return std::nullopt;
10444 return X ? *
X : *
Y;
10461 return std::nullopt;
10462 unsigned W =
X->getBitWidth();
10482static std::optional<APInt>
10488 return std::nullopt;
10491 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10492 std::optional<APInt>
X =
10495 return std::nullopt;
10500 return std::nullopt;
10515static std::optional<APInt>
10519 "Starting value of addrec should be 0");
10520 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10521 <<
Range <<
", addrec " << *AddRec <<
'\n');
10525 "Addrec's initial value should be in range");
10531 return std::nullopt;
10541 auto SolveForBoundary =
10542 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10545 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10546 << Bound <<
" (before multiplying by " << M <<
")\n");
10549 std::optional<APInt> SO;
10552 "signed overflow\n");
10556 "unsigned overflow\n");
10557 std::optional<APInt> UO =
10560 auto LeavesRange = [&] (
const APInt &
X) {
10577 return {std::nullopt,
false};
10582 if (LeavesRange(*Min))
10583 return { Min,
true };
10584 std::optional<APInt> Max = Min == SO ? UO : SO;
10585 if (LeavesRange(*Max))
10586 return { Max,
true };
10589 return {std::nullopt,
true};
10596 auto SL = SolveForBoundary(
Lower);
10597 auto SU = SolveForBoundary(
Upper);
10600 if (!SL.second || !SU.second)
10601 return std::nullopt;
10644ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10646 bool ControlsOnlyExit,
10647 bool AllowPredicates) {
10658 if (
C->getValue()->isZero())
return C;
10662 const SCEVAddRecExpr *AddRec =
10665 if (!AddRec && AllowPredicates)
10671 if (!AddRec || AddRec->
getLoop() != L)
10682 return ExitLimit(R, R, R,
false, Predicates);
10740 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10766 const SCEV *
Exact =
10774 const SCEV *SymbolicMax =
10776 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10785 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10793 return ExitLimit(
E, M, S,
false, Predicates);
10796ScalarEvolution::ExitLimit
10797ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10805 if (!
C->getValue()->isZero())
10815std::pair<const BasicBlock *, const BasicBlock *>
10816ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10827 if (
const Loop *L = LI.getLoopFor(BB))
10828 return {
L->getLoopPredecessor(),
L->getHeader()};
10830 return {
nullptr, BB};
10839 if (
A ==
B)
return true;
10854 if (ComputesEqualValues(AI, BI))
10862 const SCEV *Op0, *Op1;
10881 auto TrivialCase = [&](
bool TriviallyTrue) {
10890 const SCEV *NewLHS, *NewRHS;
10914 return TrivialCase(
false);
10915 return TrivialCase(
true);
10938 const APInt &
RA = RC->getAPInt();
10940 bool SimplifiedByConstantRange =
false;
10945 return TrivialCase(
true);
10947 return TrivialCase(
false);
10956 Changed = SimplifiedByConstantRange =
true;
10960 if (!SimplifiedByConstantRange) {
10977 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
10983 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
10989 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
10995 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11007 return TrivialCase(
true);
11009 return TrivialCase(
false);
11114 auto NonRecursive = [OrNegative](
const SCEV *S) {
11116 return C->getAPInt().isPowerOf2() ||
11117 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11123 if (NonRecursive(S))
11149 APInt C = Cst->getAPInt();
11150 return C.urem(M) == 0;
11158 const SCEV *SmodM =
11173 for (
auto *
A : Assumptions)
11174 if (
A->implies(
P, *
this))
11187std::pair<const SCEV *, const SCEV *>
11190 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11192 return { Start, Start };
11194 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11203 getUsedLoops(LHS, LoopsUsed);
11204 getUsedLoops(RHS, LoopsUsed);
11206 if (LoopsUsed.
empty())
11211 for (
const auto *L1 : LoopsUsed)
11212 for (
const auto *L2 : LoopsUsed)
11213 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11214 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11215 "Domination relationship is not a linear order");
11245 SplitRHS.second) &&
11257 if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
11261 return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11271 return std::nullopt;
11286 if (KnownWithoutContext)
11287 return KnownWithoutContext;
11294 return std::nullopt;
11300 const Loop *L = LHS->getLoop();
11305std::optional<ScalarEvolution::MonotonicPredicateType>
11308 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11314 auto ResultSwapped =
11317 assert(*ResultSwapped != *Result &&
11318 "monotonicity should flip as we flip the predicate");
11325std::optional<ScalarEvolution::MonotonicPredicateType>
11326ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11340 return std::nullopt;
11344 "Should be greater or less!");
11348 if (!LHS->hasNoUnsignedWrap())
11349 return std::nullopt;
11353 "Relational predicate is either signed or unsigned!");
11354 if (!
LHS->hasNoSignedWrap())
11355 return std::nullopt;
11357 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11365 return std::nullopt;
11368std::optional<ScalarEvolution::LoopInvariantPredicate>
11375 return std::nullopt;
11382 if (!ArLHS || ArLHS->
getLoop() != L)
11383 return std::nullopt;
11387 return std::nullopt;
11413 return std::nullopt;
11450 return std::nullopt;
11453std::optional<ScalarEvolution::LoopInvariantPredicate>
11458 Pred, LHS, RHS, L, CtxI, MaxIter))
11466 for (
auto *
Op :
UMin->operands())
11468 Pred, LHS, RHS, L, CtxI,
Op))
11470 return std::nullopt;
11473std::optional<ScalarEvolution::LoopInvariantPredicate>
11488 return std::nullopt;
11495 if (!AR || AR->
getLoop() != L)
11496 return std::nullopt;
11501 Pred = Pred.dropSameSign();
11505 return std::nullopt;
11511 if (Step != One && Step != MinusOne)
11512 return std::nullopt;
11518 return std::nullopt;
11524 return std::nullopt;
11532 if (Step == MinusOne)
11536 return std::nullopt;
11542bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11548 auto CheckRange = [&](
bool IsSigned) {
11551 return RangeLHS.
icmp(Pred, RangeRHS);
11560 if (CheckRange(
true) || CheckRange(
false))
11569bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11576 auto MatchBinaryAddToConst = [
this](
const SCEV *
X,
const SCEV *
Y,
11577 APInt &OutC1, APInt &OutC2,
11579 const SCEV *XNonConstOp, *XConstOp;
11580 const SCEV *YNonConstOp, *YConstOp;
11584 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11587 XFlagsPresent = ExpectedFlags;
11592 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11595 YFlagsPresent = ExpectedFlags;
11598 if (YNonConstOp != XNonConstOp)
11606 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11609 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11669bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11691bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11692 const SCEV *
LHS,
const SCEV *
RHS) {
11697 return any_of(*BB, [&](
const Instruction &
I) {
11698 using namespace llvm::PatternMatch;
11703 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11717 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11722 "This cannot be done on broken IR!");
11725 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11734 if (LoopContinuePredicate && LoopContinuePredicate->
isConditional() &&
11735 isImpliedCond(Pred, LHS, RHS,
11737 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11742 if (WalkingBEDominatingConds)
11748 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11749 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11756 const SCEV *LoopCounter =
11764 for (
auto &AssumeVH : AC.assumptions()) {
11771 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11775 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11778 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11779 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11780 assert(DTN &&
"should reach the loop header before reaching the root!");
11783 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11791 if (!ContinuePredicate || !ContinuePredicate->
isConditional())
11805 assert(DT.dominates(DominatingEdge, Latch) &&
"should be!");
11807 if (isImpliedCond(Pred, LHS, RHS, Condition,
11821 if (!DT.isReachableFromEntry(BB))
11825 "This cannot be done on broken IR!");
11833 const bool ProvingStrictComparison =
11835 bool ProvedNonStrictComparison =
false;
11836 bool ProvedNonEquality =
false;
11839 if (!ProvedNonStrictComparison)
11840 ProvedNonStrictComparison = Fn(NonStrictPredicate);
11841 if (!ProvedNonEquality)
11843 if (ProvedNonStrictComparison && ProvedNonEquality)
11848 if (ProvingStrictComparison) {
11850 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
11852 if (SplitAndProve(ProofFn))
11857 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
11859 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
11861 if (ProvingStrictComparison) {
11863 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
11865 if (SplitAndProve(ProofFn))
11874 const Loop *ContainingLoop = LI.getLoopFor(BB);
11876 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
11880 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
11881 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
11893 for (
auto &AssumeVH : AC.assumptions()) {
11897 if (!DT.dominates(CI, BB))
11900 if (ProveViaCond(CI->getArgOperand(0),
false))
11906 F.getParent(), Intrinsic::experimental_guard);
11908 for (
const auto *GU : GuardDecl->users())
11910 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
11911 if (ProveViaCond(Guard->getArgOperand(0),
false))
11926 "LHS is not available at Loop Entry");
11928 "RHS is not available at Loop Entry");
11930 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11941 if (FoundCondValue ==
11945 if (!PendingLoopPredicates.insert(FoundCondValue).second)
11949 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
11952 const Value *Op0, *Op1;
11955 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
11959 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
11960 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
11964 if (!ICI)
return false;
11968 CmpPredicate FoundPred;
11977 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
11980bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
11981 const SCEV *
RHS, CmpPredicate FoundPred,
11982 const SCEV *FoundLHS,
const SCEV *FoundRHS,
11983 const Instruction *CtxI) {
11993 auto *WideType = FoundLHS->
getType();
12005 TruncFoundLHS, TruncFoundRHS, CtxI))
12031 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12035bool ScalarEvolution::isImpliedCondBalancedTypes(
12036 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
12037 const SCEV *FoundLHS,
const SCEV *FoundRHS,
const Instruction *CtxI) {
12040 "Types should be balanced!");
12047 if (FoundLHS == FoundRHS)
12051 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12063 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12080 LHS, FoundLHS, FoundRHS, CtxI);
12082 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12104 assert(P1 != P2 &&
"Handled earlier!");
12108 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12112 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12115 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12116 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12117 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12122 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12133 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12134 CanonicalRHS, CanonicalFoundLHS,
12135 CanonicalFoundRHS);
12140 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12141 CanonicalRHS, CanonicalFoundLHS,
12142 CanonicalFoundRHS);
12149 const SCEVConstant *
C =
nullptr;
12150 const SCEV *
V =
nullptr;
12168 if (Min ==
C->getAPInt()) {
12173 APInt SharperMin = Min + 1;
12176 case ICmpInst::ICMP_SGE:
12177 case ICmpInst::ICMP_UGE:
12180 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12185 case ICmpInst::ICMP_SGT:
12186 case ICmpInst::ICMP_UGT:
12196 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12201 case ICmpInst::ICMP_SLE:
12202 case ICmpInst::ICMP_ULE:
12203 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12204 LHS, V, getConstant(SharperMin), CtxI))
12208 case ICmpInst::ICMP_SLT:
12209 case ICmpInst::ICMP_ULT:
12210 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12211 LHS, V, getConstant(Min), CtxI))
12225 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12229 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12232 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12239bool ScalarEvolution::splitBinaryAdd(
const SCEV *Expr,
12240 const SCEV *&L,
const SCEV *&R,
12249std::optional<APInt>
12256 APInt DiffMul(BW, 1);
12259 for (
unsigned I = 0;
I < 8; ++
I) {
12268 if (LAR->getLoop() != MAR->getLoop())
12269 return std::nullopt;
12273 if (!LAR->isAffine() || !MAR->isAffine())
12274 return std::nullopt;
12276 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12277 return std::nullopt;
12279 Less = LAR->getStart();
12280 More = MAR->getStart();
12285 auto MatchConstMul =
12286 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12291 return std::nullopt;
12293 if (
auto MatchedMore = MatchConstMul(More)) {
12294 if (
auto MatchedLess = MatchConstMul(
Less)) {
12295 if (MatchedMore->second == MatchedLess->second) {
12296 More = MatchedMore->first;
12297 Less = MatchedLess->first;
12298 DiffMul *= MatchedMore->second;
12309 Diff +=
C->getAPInt() * DiffMul;
12312 Diff -=
C->getAPInt() * DiffMul;
12315 Multiplicity[S] +=
Mul;
12317 auto Decompose = [&](
const SCEV *S,
int Mul) {
12324 Decompose(More, 1);
12325 Decompose(
Less, -1);
12329 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12330 for (
const auto &[S,
Mul] : Multiplicity) {
12335 return std::nullopt;
12337 }
else if (
Mul == -1) {
12339 return std::nullopt;
12342 return std::nullopt;
12346 if (NewMore == More || NewLess ==
Less)
12347 return std::nullopt;
12353 if (!More && !
Less)
12357 if (!More || !
Less)
12358 return std::nullopt;
12362 return std::nullopt;
12365bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12389 if (!L->contains(ContextBB) || !DT.
dominates(ContextBB, L->getLoopLatch()))
12400 if (!L->contains(ContextBB) || !DT.
dominates(ContextBB, L->getLoopLatch()))
12410bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12413 const SCEV *FoundLHS,
12414 const SCEV *FoundRHS) {
12423 if (!AddRecFoundLHS)
12430 const Loop *
L = AddRecFoundLHS->getLoop();
12431 if (L != AddRecLHS->getLoop())
12470 if (!RDiff || *LDiff != *RDiff)
12473 if (LDiff->isMinValue())
12476 APInt FoundRHSLimit;
12479 FoundRHSLimit = -(*RDiff);
12491bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12492 const SCEV *
RHS,
const SCEV *FoundLHS,
12493 const SCEV *FoundRHS,
unsigned Depth) {
12494 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12498 bool Erased = PendingMerges.erase(LPhi);
12499 assert(Erased &&
"Failed to erase LPhi!");
12503 bool Erased = PendingMerges.erase(RPhi);
12504 assert(Erased &&
"Failed to erase RPhi!");
12512 if (!PendingMerges.insert(Phi).second)
12526 if (!PendingMerges.insert(Phi).second)
12532 if (!LPhi && !RPhi)
12543 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12547 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12548 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12549 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12550 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12553 if (RPhi && RPhi->getParent() == LBB) {
12560 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12561 if (!ProvedEasily(L, R))
12572 auto *RLoop = RAR->
getLoop();
12573 auto *Predecessor = RLoop->getLoopPredecessor();
12574 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12576 if (!ProvedEasily(L1, RAR->
getStart()))
12578 auto *Latch = RLoop->getLoopLatch();
12579 assert(Latch &&
"Loop with AddRec with no latch?");
12600 if (
auto *Loop = LI.getLoopFor(LBB))
12603 if (!ProvedEasily(L,
RHS))
12610bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12613 const SCEV *FoundLHS,
12614 const SCEV *FoundRHS) {
12617 if (
RHS == FoundRHS) {
12622 if (
LHS != FoundLHS)
12629 Value *Shiftee, *ShiftValue;
12631 using namespace PatternMatch;
12632 if (
match(SUFoundRHS->getValue(),
12634 auto *ShifteeS =
getSCEV(Shiftee);
12652bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12654 const SCEV *FoundLHS,
12655 const SCEV *FoundRHS,
12656 const Instruction *CtxI) {
12657 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12659 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12661 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12662 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12664 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12668template <
typename MinMaxExprType>
12670 const SCEV *Candidate) {
12675 return is_contained(MinMaxExpr->operands(), Candidate);
12688 const SCEV *LStart, *RStart, *Step;
12738bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12740 const SCEV *FoundLHS,
12741 const SCEV *FoundRHS,
12745 "LHS and RHS have different sizes?");
12748 "FoundLHS and FoundRHS have different sizes?");
12782 auto GetOpFromSExt = [&](
const SCEV *S) {
12784 return Ext->getOperand();
12791 auto *OrigLHS =
LHS;
12792 auto *OrigFoundLHS = FoundLHS;
12793 LHS = GetOpFromSExt(
LHS);
12794 FoundLHS = GetOpFromSExt(FoundLHS);
12797 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
12800 FoundRHS,
Depth + 1);
12813 if (!LHSAddExpr->hasNoSignedWrap())
12816 auto *LL = LHSAddExpr->getOperand(0);
12817 auto *LR = LHSAddExpr->getOperand(1);
12821 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
12822 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
12827 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
12833 using namespace llvm::PatternMatch;
12852 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
12860 auto *DTy = Denominator->getType();
12861 auto *FRHSTy = FoundRHS->
getType();
12862 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
12881 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
12892 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
12894 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
12902 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
12935bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
12939 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
12942 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
12945bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
12948 const SCEV *FoundLHS,
12949 const SCEV *FoundRHS) {
12985 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
12991bool ScalarEvolution::isImpliedCondOperandsViaRanges(
12992 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
12993 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13007 ConstantRange FoundLHSRange =
13011 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13018 return LHSRange.
icmp(Pred, ConstRHS);
13021bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13034 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13042 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13045bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
13057 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
13065 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
13077const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
13078 const SCEV *Stride,
13109 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13120 :
APIntOps::umax(MaxEnd, MinStart);
13127ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13128 const Loop *L,
bool IsSigned,
13129 bool ControlsOnlyExit,
bool AllowPredicates) {
13133 bool PredicatedIV =
false;
13138 auto canProveNUW = [&]() {
13141 if (!ControlsOnlyExit)
13162 Limit = Limit.
zext(OuterBitWidth);
13174 Type *Ty = ZExt->getType();
13185 if (!
IV && AllowPredicates) {
13190 PredicatedIV =
true;
13194 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13208 bool NoWrap = ControlsOnlyExit &&
IV->getNoWrapFlags(WrapType);
13211 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13216 if (!PositiveStride) {
13268 auto wouldZeroStrideBeUB = [&]() {
13280 if (!wouldZeroStrideBeUB()) {
13284 }
else if (!NoWrap) {
13287 if (canIVOverflowOnLT(
RHS, Stride, IsSigned))
13300 const SCEV *
Start =
IV->getStart();
13306 const SCEV *OrigStart =
Start;
13307 const SCEV *OrigRHS =
RHS;
13308 if (
Start->getType()->isPointerTy()) {
13319 const SCEV *End =
nullptr, *BECount =
nullptr,
13320 *BECountIfBackedgeTaken =
nullptr;
13323 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13324 RHSAddRec->getNoWrapFlags()) {
13337 const SCEV *RHSStart = RHSAddRec->getStart();
13338 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13350 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13359 BECountIfBackedgeTaken =
13364 if (BECount ==
nullptr) {
13369 const SCEV *MaxBECount = computeMaxBECountForLT(
13372 MaxBECount,
false , Predicates);
13379 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13406 const SCEV *Numerator =
13412 auto canProveRHSGreaterThanEqualStart = [&]() {
13431 auto *StartMinusOne =
13438 if (canProveRHSGreaterThanEqualStart()) {
13453 BECountIfBackedgeTaken =
13469 bool MayAddOverflow = [&] {
13515 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13529 if (!MayAddOverflow) {
13541 const SCEV *ConstantMaxBECount;
13542 bool MaxOrZero =
false;
13544 ConstantMaxBECount = BECount;
13545 }
else if (BECountIfBackedgeTaken &&
13550 ConstantMaxBECount = BECountIfBackedgeTaken;
13553 ConstantMaxBECount = computeMaxBECountForLT(
13561 const SCEV *SymbolicMaxBECount =
13563 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13567ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13568 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13569 bool ControlsOnlyExit,
bool AllowPredicates) {
13576 if (!
IV && AllowPredicates)
13583 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13587 bool NoWrap = ControlsOnlyExit &&
IV->getNoWrapFlags(WrapType);
13600 if (!Stride->
isOne() && !NoWrap)
13601 if (canIVOverflowOnGT(
RHS, Stride, IsSigned))
13604 const SCEV *
Start =
IV->getStart();
13605 const SCEV *End =
RHS;
13616 if (
Start->getType()->isPointerTy()) {
13651 const SCEV *ConstantMaxBECount =
13658 ConstantMaxBECount = BECount;
13659 const SCEV *SymbolicMaxBECount =
13662 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13668 if (
Range.isFullSet())
13673 if (!SC->getValue()->isZero()) {
13679 return ShiftedAddRec->getNumIterationsInRange(
13680 Range.subtract(SC->getAPInt()), SE);
13711 APInt ExitVal = (End +
A).udiv(
A);
13724 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13725 "Linear scev computation is off in a bad way!");
13756 assert(!
Last->isZero() &&
"Recurrency with zero step?");
13781 Ty = Store->getValueOperand()->getType();
13783 Ty = Load->getType();
13796 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13798 SE->ConstantEvolutionLoopExitValue.erase(PN);
13799 SE->eraseValueFromMap(getValPtr());
13803void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
13804 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13814 : CallbackVH(
V), SE(se) {}
13823 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
13825 LoopDispositions(64), BlockDispositions(64) {
13837 F.getParent(), Intrinsic::experimental_guard);
13838 HasGuards = GuardDecl && !GuardDecl->use_empty();
13842 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
13843 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
13844 ValueExprMap(
std::
move(Arg.ValueExprMap)),
13845 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
13846 PendingPhiRanges(
std::
move(Arg.PendingPhiRanges)),
13847 PendingMerges(
std::
move(Arg.PendingMerges)),
13848 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
13849 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
13850 PredicatedBackedgeTakenCounts(
13851 std::
move(Arg.PredicatedBackedgeTakenCounts)),
13852 BECountUsers(
std::
move(Arg.BECountUsers)),
13853 ConstantEvolutionLoopExitValue(
13854 std::
move(Arg.ConstantEvolutionLoopExitValue)),
13855 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
13856 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
13857 LoopDispositions(
std::
move(Arg.LoopDispositions)),
13858 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
13859 BlockDispositions(
std::
move(Arg.BlockDispositions)),
13860 SCEVUsers(
std::
move(Arg.SCEVUsers)),
13861 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
13862 SignedRanges(
std::
move(Arg.SignedRanges)),
13863 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
13864 UniquePreds(
std::
move(Arg.UniquePreds)),
13865 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
13866 LoopUsers(
std::
move(Arg.LoopUsers)),
13867 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
13868 FirstUnknown(Arg.FirstUnknown) {
13869 Arg.FirstUnknown =
nullptr;
13878 Tmp->~SCEVUnknown();
13880 FirstUnknown =
nullptr;
13882 ExprValueMap.clear();
13883 ValueExprMap.clear();
13885 BackedgeTakenCounts.clear();
13886 PredicatedBackedgeTakenCounts.clear();
13888 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
13889 assert(PendingPhiRanges.empty() &&
"getRangeRef garbage");
13890 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
13891 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
13892 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
13914 L->getHeader()->printAsOperand(OS,
false);
13918 L->getExitingBlocks(ExitingBlocks);
13919 if (ExitingBlocks.
size() != 1)
13920 OS <<
"<multiple exits> ";
13924 OS <<
"backedge-taken count is ";
13927 OS <<
"Unpredictable backedge-taken count.";
13930 if (ExitingBlocks.
size() > 1)
13931 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
13932 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
13940 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
13943 OS <<
"\n Predicates:\n";
13944 for (
const auto *
P : Predicates)
13952 L->getHeader()->printAsOperand(OS,
false);
13957 OS <<
"constant max backedge-taken count is ";
13960 OS <<
", actual taken count either this or zero.";
13962 OS <<
"Unpredictable constant max backedge-taken count. ";
13967 L->getHeader()->printAsOperand(OS,
false);
13972 OS <<
"symbolic max backedge-taken count is ";
13975 OS <<
", actual taken count either this or zero.";
13977 OS <<
"Unpredictable symbolic max backedge-taken count. ";
13981 if (ExitingBlocks.
size() > 1)
13982 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
13983 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
13993 OS <<
"\n predicated symbolic max exit count for "
13994 << ExitingBlock->
getName() <<
": ";
13996 OS <<
"\n Predicates:\n";
13997 for (
const auto *
P : Predicates)
14007 assert(!Preds.
empty() &&
"Different predicated BTC, but no predicates");
14009 L->getHeader()->printAsOperand(OS,
false);
14012 OS <<
"Predicated backedge-taken count is ";
14015 OS <<
"Unpredictable predicated backedge-taken count.";
14017 OS <<
" Predicates:\n";
14018 for (
const auto *
P : Preds)
14023 auto *PredConstantMax =
14025 if (PredConstantMax != ConstantBTC) {
14027 "different predicated constant max BTC but no predicates");
14029 L->getHeader()->printAsOperand(OS,
false);
14032 OS <<
"Predicated constant max backedge-taken count is ";
14035 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14037 OS <<
" Predicates:\n";
14038 for (
const auto *
P : Preds)
14043 auto *PredSymbolicMax =
14045 if (SymbolicBTC != PredSymbolicMax) {
14047 "Different predicated symbolic max BTC, but no predicates");
14049 L->getHeader()->printAsOperand(OS,
false);
14052 OS <<
"Predicated symbolic max backedge-taken count is ";
14055 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14057 OS <<
" Predicates:\n";
14058 for (
const auto *
P : Preds)
14064 L->getHeader()->printAsOperand(OS,
false);
14088 OS <<
"Computable";
14098 OS <<
"DoesNotDominate";
14104 OS <<
"ProperlyDominates";
14121 OS <<
"Classifying expressions for: ";
14122 F.printAsOperand(OS,
false);
14137 const Loop *L = LI.getLoopFor(
I.getParent());
14152 OS <<
"\t\t" "Exits: ";
14155 OS <<
"<<Unknown>>";
14161 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14163 Iter->getHeader()->printAsOperand(OS,
false);
14171 InnerL->getHeader()->printAsOperand(OS,
false);
14182 OS <<
"Determining loop execution counts for: ";
14183 F.printAsOperand(OS,
false);
14191 auto &Values = LoopDispositions[S];
14192 for (
auto &V : Values) {
14193 if (V.getPointer() == L)
14198 auto &Values2 = LoopDispositions[S];
14200 if (V.getPointer() == L) {
14209ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14228 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14229 " dominate the contained loop's header?");
14257 bool HasVarying =
false;
14291 auto &Values = BlockDispositions[S];
14292 for (
auto &V : Values) {
14293 if (V.getPointer() == BB)
14298 auto &Values2 = BlockDispositions[S];
14300 if (V.getPointer() == BB) {
14309ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14339 bool Proper =
true;
14350 if (Instruction *
I =
14352 if (
I->getParent() == BB)
14354 if (DT.properlyDominates(
I->getParent(), BB))
14377void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14380 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14381 auto It = BECounts.find(L);
14382 if (It != BECounts.end()) {
14383 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14384 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14386 auto UserIt = BECountUsers.find(S);
14387 assert(UserIt != BECountUsers.end());
14392 BECounts.erase(It);
14400 while (!Worklist.
empty()) {
14402 auto Users = SCEVUsers.find(Curr);
14403 if (
Users != SCEVUsers.end())
14404 for (
const auto *User :
Users->second)
14405 if (ToForget.
insert(User).second)
14409 for (
const auto *S : ToForget)
14410 forgetMemoizedResultsImpl(S);
14412 for (
auto I = PredicatedSCEVRewrites.begin();
14413 I != PredicatedSCEVRewrites.end();) {
14414 std::pair<const SCEV *, const Loop *>
Entry =
I->first;
14415 if (ToForget.count(
Entry.first))
14416 PredicatedSCEVRewrites.erase(
I++);
14422void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14423 LoopDispositions.erase(S);
14424 BlockDispositions.erase(S);
14425 UnsignedRanges.erase(S);
14426 SignedRanges.erase(S);
14427 HasRecMap.erase(S);
14428 ConstantMultipleCache.erase(S);
14431 UnsignedWrapViaInductionTried.erase(AR);
14432 SignedWrapViaInductionTried.erase(AR);
14435 auto ExprIt = ExprValueMap.find(S);
14436 if (ExprIt != ExprValueMap.end()) {
14437 for (
Value *V : ExprIt->second) {
14438 auto ValueIt = ValueExprMap.find_as(V);
14439 if (ValueIt != ValueExprMap.end())
14440 ValueExprMap.erase(ValueIt);
14442 ExprValueMap.erase(ExprIt);
14445 auto ScopeIt = ValuesAtScopes.find(S);
14446 if (ScopeIt != ValuesAtScopes.end()) {
14447 for (
const auto &Pair : ScopeIt->second)
14450 std::make_pair(Pair.first, S));
14451 ValuesAtScopes.erase(ScopeIt);
14454 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14455 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14456 for (
const auto &Pair : ScopeUserIt->second)
14457 llvm::erase(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
14458 ValuesAtScopesUsers.erase(ScopeUserIt);
14461 auto BEUsersIt = BECountUsers.find(S);
14462 if (BEUsersIt != BECountUsers.end()) {
14464 auto Copy = BEUsersIt->second;
14465 for (
const auto &Pair : Copy)
14466 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14467 BECountUsers.erase(BEUsersIt);
14470 auto FoldUser = FoldCacheUser.find(S);
14471 if (FoldUser != FoldCacheUser.end())
14472 for (
auto &KV : FoldUser->second)
14473 FoldCache.erase(KV);
14474 FoldCacheUser.erase(S);
14478ScalarEvolution::getUsedLoops(
const SCEV *S,
14480 struct FindUsedLoops {
14481 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14482 : LoopsUsed(LoopsUsed) {}
14483 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14484 bool follow(
const SCEV *S) {
14490 bool isDone()
const {
return false; }
14493 FindUsedLoops
F(LoopsUsed);
14494 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14497void ScalarEvolution::getReachableBlocks(
14500 Worklist.
push_back(&F.getEntryBlock());
14501 while (!Worklist.
empty()) {
14503 if (!Reachable.
insert(BB).second)
14511 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14518 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14522 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14557 SCEVMapper SCM(SE2);
14559 SE2.getReachableBlocks(ReachableBlocks, F);
14561 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14579 while (!LoopStack.
empty()) {
14585 if (!ReachableBlocks.
contains(L->getHeader()))
14590 auto It = BackedgeTakenCounts.find(L);
14591 if (It == BackedgeTakenCounts.end())
14595 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14615 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14616 if (Delta && !Delta->
isZero()) {
14617 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14618 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14619 dbgs() <<
"New: " << *NewBECount <<
"\n";
14620 dbgs() <<
"Delta: " << *Delta <<
"\n";
14628 while (!Worklist.
empty()) {
14630 if (ValidLoops.
insert(L).second)
14631 Worklist.
append(L->begin(), L->end());
14633 for (
const auto &KV : ValueExprMap) {
14638 "AddRec references invalid loop");
14643 auto It = ExprValueMap.find(KV.second);
14644 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14645 dbgs() <<
"Value " << *KV.first
14646 <<
" is in ValueExprMap but not in ExprValueMap\n";
14651 if (!ReachableBlocks.
contains(
I->getParent()))
14653 const SCEV *OldSCEV = SCM.visit(KV.second);
14655 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14656 if (Delta && !Delta->
isZero()) {
14657 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14658 <<
"Old: " << *OldSCEV <<
"\n"
14659 <<
"New: " << *NewSCEV <<
"\n"
14660 <<
"Delta: " << *Delta <<
"\n";
14666 for (
const auto &KV : ExprValueMap) {
14667 for (
Value *V : KV.second) {
14668 const SCEV *S = ValueExprMap.lookup(V);
14670 dbgs() <<
"Value " << *V
14671 <<
" is in ExprValueMap but not in ValueExprMap\n";
14674 if (S != KV.first) {
14675 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14676 << *KV.first <<
"\n";
14683 for (
const auto &S : UniqueSCEVs) {
14688 auto It = SCEVUsers.find(
Op);
14689 if (It != SCEVUsers.end() && It->second.count(&S))
14691 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14692 <<
" is not being tracked!\n";
14698 for (
const auto &ValueAndVec : ValuesAtScopes) {
14700 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14701 const Loop *L = LoopAndValueAtScope.first;
14702 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
14704 auto It = ValuesAtScopesUsers.find(ValueAtScope);
14705 if (It != ValuesAtScopesUsers.end() &&
14708 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14709 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14715 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14716 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14717 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14718 const Loop *L = LoopAndValue.first;
14719 const SCEV *
Value = LoopAndValue.second;
14721 auto It = ValuesAtScopes.find(
Value);
14722 if (It != ValuesAtScopes.end() &&
14723 is_contained(It->second, std::make_pair(L, ValueAtScope)))
14725 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14726 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14732 auto VerifyBECountUsers = [&](
bool Predicated) {
14734 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14735 for (
const auto &LoopAndBEInfo : BECounts) {
14736 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14737 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14739 auto UserIt = BECountUsers.find(S);
14740 if (UserIt != BECountUsers.end() &&
14741 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14743 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14744 <<
" missing from BECountUsers\n";
14751 VerifyBECountUsers(
false);
14752 VerifyBECountUsers(
true);
14755 for (
auto &[S, Values] : LoopDispositions) {
14756 for (
auto [
Loop, CachedDisposition] : Values) {
14758 if (CachedDisposition != RecomputedDisposition) {
14759 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
14760 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
14761 << RecomputedDisposition <<
"\n";
14768 for (
auto &[S, Values] : BlockDispositions) {
14769 for (
auto [BB, CachedDisposition] : Values) {
14771 if (CachedDisposition != RecomputedDisposition) {
14772 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
14773 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
14774 <<
", actual " << RecomputedDisposition <<
"\n";
14781 for (
auto [
FoldID, Expr] : FoldCache) {
14782 auto I = FoldCacheUser.find(Expr);
14783 if (
I == FoldCacheUser.end()) {
14784 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
14789 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
14793 for (
auto [Expr, IDs] : FoldCacheUser) {
14794 for (
auto &
FoldID : IDs) {
14797 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
14802 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
14803 <<
" != " << *Expr <<
"!\n";
14814 for (
auto [S, Multiple] : ConstantMultipleCache) {
14816 if ((Multiple != 0 && RecomputedMultiple != 0 &&
14817 Multiple.
urem(RecomputedMultiple) != 0 &&
14818 RecomputedMultiple.
urem(Multiple) != 0)) {
14819 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
14820 << *S <<
" : Computed " << RecomputedMultiple
14821 <<
" but cache contains " << Multiple <<
"!\n";
14829 FunctionAnalysisManager::Invalidator &Inv) {
14861 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
14862 <<
F.getName() <<
"':\n";
14868 "Scalar Evolution Analysis",
false,
true)
14917 const SCEV *LHS,
const SCEV *RHS) {
14919 assert(LHS->getType() == RHS->getType() &&
14920 "Type mismatch between LHS and RHS");
14923 ID.AddInteger(Pred);
14924 ID.AddPointer(LHS);
14925 ID.AddPointer(RHS);
14926 void *IP =
nullptr;
14927 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
14931 UniquePreds.InsertNode(Eq, IP);
14942 ID.AddInteger(AddedFlags);
14943 void *IP =
nullptr;
14944 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
14946 auto *OF =
new (SCEVAllocator)
14948 UniquePreds.InsertNode(OF, IP);
14968 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
14969 return Rewriter.visit(S);
14975 for (
const auto *Pred : U->getPredicates())
14977 if (IPred->getLHS() == Expr &&
14979 return IPred->getRHS();
14981 if (IPred->getLHS() == Expr &&
14982 IPred->getPredicate() == ICmpInst::ICMP_EQ)
14983 return IPred->getRHS();
14986 return convertToAddRecWithPreds(Expr);
14989 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15005 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15022 explicit SCEVPredicateRewriter(
15023 const Loop *L, ScalarEvolution &SE,
15024 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15025 const SCEVPredicate *Pred)
15026 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15028 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15031 return Pred && Pred->
implies(
P, SE);
15037 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15040 return addOverflowAssumption(
A);
15049 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15053 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15055 if (!PredicatedRewrite)
15057 for (
const auto *
P : PredicatedRewrite->second){
15060 if (L != WP->getExpr()->getLoop())
15063 if (!addOverflowAssumption(
P))
15066 return PredicatedRewrite->first;
15069 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15070 const SCEVPredicate *Pred;
15079 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15086 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15106 if (!Step->
isOne())
15131 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15132 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15145 return Op->LHS == LHS &&
Op->RHS == RHS;
15152 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15154 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15179 const SCEV *Start = AR->getStart();
15180 const SCEV *OpStart =
Op->AR->getStart();
15185 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15188 const SCEV *Step = AR->getStepRecurrence(SE);
15189 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15242 if (Step->getValue()->getValue().isNonNegative())
15246 return ImpliedFlags;
15253 for (
const auto *
P : Preds)
15266 return this->implies(I, SE);
15274 for (
const auto *Pred : Preds)
15275 Pred->print(OS,
Depth);
15280 for (
const auto *Pred : Set->Preds)
15288 bool CheckImplies = Preds.
size() < 16;
15291 if (CheckImplies &&
implies(
N, SE))
15297 for (
auto *
P : Preds) {
15298 if (CheckImplies &&
N->implies(
P, SE))
15302 Preds = std::move(PrunedPreds);
15303 Preds.push_back(
N);
15310 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15315 for (
const auto *
Op :
Ops)
15320 SCEVUsers[
Op].insert(
User);
15324 const SCEV *Expr = SE.getSCEV(V);
15329 RewriteEntry &Entry = RewriteMap[Expr];
15332 if (Entry.second && Generation == Entry.first)
15333 return Entry.second;
15338 Expr = Entry.second;
15340 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15341 Entry = {Generation, NewSCEV};
15347 if (!BackedgeCount) {
15349 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15350 for (
const auto *
P : Preds)
15353 return BackedgeCount;
15357 if (!SymbolicMaxBackedgeCount) {
15359 SymbolicMaxBackedgeCount =
15360 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15361 for (
const auto *
P : Preds)
15364 return SymbolicMaxBackedgeCount;
15368 if (!SmallConstantMaxTripCount) {
15370 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15371 for (
const auto *
P : Preds)
15374 return *SmallConstantMaxTripCount;
15378 if (Preds->implies(&Pred, SE))
15383 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15384 updateGeneration();
15391void PredicatedScalarEvolution::updateGeneration() {
15393 if (++Generation == 0) {
15394 for (
auto &
II : RewriteMap) {
15395 const SCEV *Rewritten =
II.second.second;
15412 auto II = FlagsMap.insert({V, Flags});
15425 auto II = FlagsMap.find(V);
15427 if (
II != FlagsMap.end())
15436 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15441 for (
const auto *
P : NewPreds)
15444 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15450 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15453 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {
15454 for (
auto I :
Init.FlagsMap)
15455 FlagsMap.insert(
I);
15460 for (
auto *BB : L.getBlocks())
15461 for (
auto &
I : *BB) {
15462 if (!SE.isSCEVable(
I.getType()))
15465 auto *Expr = SE.getSCEV(&
I);
15466 auto II = RewriteMap.find(Expr);
15468 if (
II == RewriteMap.end())
15472 if (
II->second.second == Expr)
15477 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15485 LoopGuards Guards(SE);
15493void ScalarEvolution::LoopGuards::collectFromPHI(
15501 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15502 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15516 auto &RewriteMap =
G->second.RewriteMap;
15517 if (RewriteMap.empty())
15519 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15520 if (S == RewriteMap.end())
15526 return {C0,
SM->getSCEVType()};
15529 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15530 MinMaxPattern
P2) -> MinMaxPattern {
15531 auto [C1,
T1] =
P1;
15532 auto [C2, T2] =
P2;
15533 if (!C1 || !C2 ||
T1 != T2)
15537 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15539 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15541 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15543 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15548 auto P = GetMinMaxConst(0);
15549 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15552 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15555 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15558 Guards.RewriteMap.insert({
LHS,
RHS});
15566 const APInt &DivisorVal,
15568 const APInt *ExprVal;
15581 const APInt &DivisorVal,
15583 const APInt *ExprVal;
15591 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15605 const SCEV *URemRHS =
nullptr;
15609 const SCEV *Multiple =
15611 DivInfo[URemLHS] = Multiple;
15613 Multiples[URemLHS] =
C->getAPInt();
15633 auto IsMinMaxSCEVWithNonNegativeConstant =
15637 if (
MinMax->getNumOperands() != 2)
15640 if (
C->getAPInt().isNegative())
15642 SCTy =
MinMax->getSCEVType();
15651 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15653 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15658 auto *DivisibleExpr =
15666void ScalarEvolution::LoopGuards::collectFromBlock(
15668 const BasicBlock *
Block,
const BasicBlock *Pred,
15676 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15687 &ExprsToRewrite]() {
15688 const SCEVConstant *C1;
15701 if (ExactRegion.isWrappedSet() || ExactRegion.isFullSet())
15703 auto [
I,
Inserted] = RewriteMap.try_emplace(LHSUnknown);
15704 const SCEV *RewrittenLHS =
Inserted ? LHSUnknown :
I->second;
15712 if (MatchRangeCheckIdiom())
15729 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15731 if (From == FromRewritten)
15733 RewriteMap[From] = To;
15739 auto GetMaybeRewritten = [&](
const SCEV *S) {
15740 return RewriteMap.lookup_or(S, S);
15743 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15745 const APInt &DividesBy =
15760 switch (Predicate) {
15789 SmallPtrSet<const SCEV *, 16> Visited;
15791 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
15795 while (!Worklist.
empty()) {
15799 if (!Visited.
insert(From).second)
15801 const SCEV *FromRewritten = GetMaybeRewritten(From);
15802 const SCEV *To =
nullptr;
15804 switch (Predicate) {
15809 EnqueueOperands(
UMax);
15815 EnqueueOperands(
SMax);
15821 EnqueueOperands(
UMin);
15827 EnqueueOperands(
SMin);
15835 const SCEV *OneAlignedUp =
15837 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
15849 const SCEVConstant *
C;
15858 Guards.NotEqual.insert({
LHS,
RHS});
15867 AddRewrite(From, FromRewritten, To);
15884 SE.F.
getParent(), Intrinsic::experimental_guard);
15886 for (
const auto *GU : GuardDecl->users())
15888 if (Guard->getFunction() ==
Block->getParent() &&
15897 unsigned NumCollectedConditions = 0;
15899 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
15901 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
15903 const BranchInst *LoopEntryPredicate =
15910 NumCollectedConditions++;
15914 if (
Depth > 0 && NumCollectedConditions == 2)
15922 if (Pair.second->hasNPredecessorsOrMore(2) &&
15924 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
15925 for (
auto &Phi : Pair.second->phis())
15936 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
15937 SmallVector<Value *, 8> Worklist;
15938 SmallPtrSet<Value *, 8> Visited;
15940 while (!Worklist.
empty()) {
15947 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
15971 DenseMap<const SCEV *, APInt> Multiples;
15973 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
15980 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
15981 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
15985 for (
const auto &[K, Divisor] : Multiples) {
15986 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
15987 Guards.RewriteMap[
K] =
15989 Guards.
rewrite(K), Divisor, SE),
15998 Guards.PreserveNUW =
true;
15999 Guards.PreserveNSW =
true;
16000 for (
const SCEV *Expr : ExprsToRewrite) {
16001 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16002 Guards.PreserveNUW &=
16004 Guards.PreserveNSW &=
16011 if (ExprsToRewrite.size() > 1) {
16012 for (
const SCEV *Expr : ExprsToRewrite) {
16013 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16014 Guards.RewriteMap.erase(Expr);
16015 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16024 class SCEVLoopGuardRewriter
16035 NotEqual(Guards.NotEqual) {
16036 if (Guards.PreserveNUW)
16038 if (Guards.PreserveNSW)
16045 return Map.lookup_or(Expr, Expr);
16049 if (
const SCEV *S = Map.lookup(Expr))
16056 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16057 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16058 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16060 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16061 if (
const SCEV *S = Map.lookup(NarrowExt))
16062 return SE.getZeroExtendExpr(S, Ty);
16063 Bitwidth = Bitwidth / 2;
16071 if (
const SCEV *S = Map.lookup(Expr))
16078 if (
const SCEV *S = Map.lookup(Expr))
16084 if (
const SCEV *S = Map.lookup(Expr))
16092 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16093 const SCEV *LHS, *RHS;
16097 if (NotEqual.contains({LHS, RHS})) {
16099 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16100 return SE.getUMaxExpr(OneAlignedUp, S);
16107 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16118 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16119 return SE.getAddExpr(
16122 if (
const SCEV *S = Map.lookup(
Add))
16123 return SE.getAddExpr(Expr->
getOperand(0), S);
16135 : SE.getAddExpr(Operands,
16151 : SE.getMulExpr(Operands,
16157 if (RewriteMap.empty() && NotEqual.empty())
16160 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16161 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)
static constexpr unsigned SM(unsigned Version)
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
PowerPC Reduce CR logical Operation
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
const SmallVectorImpl< MachineOperand > & Cond
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
SI optimize exec mask operations pre RA
static void visit(BasicBlock &Start, std::function< bool(BasicBlock *)> op)
This file provides utility classes that use RAII to save and restore values.
bool SCEVMinMaxExprContains(const SCEV *Root, const SCEV *OperandToFind, SCEVTypes RootKind)
static cl::opt< unsigned > MaxAddRecSize("scalar-evolution-max-add-rec-size", cl::Hidden, cl::desc("Max coefficients in AddRec during evolving"), cl::init(8))
static cl::opt< unsigned > RangeIterThreshold("scev-range-iter-threshold", cl::Hidden, cl::desc("Threshold for switching to iteratively computing SCEV ranges"), cl::init(32))
static const Loop * isIntegerLoopHeaderPHI(const PHINode *PN, LoopInfo &LI)
static unsigned getConstantTripCount(const SCEVConstant *ExitCount)
static int CompareValueComplexity(const LoopInfo *const LI, Value *LV, Value *RV, unsigned Depth)
Compare the two values LV and RV in terms of their "complexity" where "complexity" is a partial (and ...
static const SCEV * getNextSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static void PushLoopPHIs(const Loop *L, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push PHI nodes in the header of the given loop onto the given Worklist.
static void insertFoldCacheEntry(const ScalarEvolution::FoldID &ID, const SCEV *S, DenseMap< ScalarEvolution::FoldID, const SCEV * > &FoldCache, DenseMap< const SCEV *, SmallVector< ScalarEvolution::FoldID, 2 > > &FoldCacheUser)
static cl::opt< bool > ClassifyExpressions("scalar-evolution-classify-expressions", cl::Hidden, cl::init(true), cl::desc("When printing analysis, include information on every instruction"))
static bool 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]
SCEVCastSinkingRewriter(ScalarEvolution &SE, Type *TargetTy, ConversionFn CreatePtrCast)
static const SCEV * rewrite(const SCEV *Scev, ScalarEvolution &SE, Type *TargetTy, ConversionFn CreatePtrCast)
const SCEV * visitUnknown(const SCEVUnknown *Expr)
const SCEV * visitMulExpr(const SCEVMulExpr *Expr)
const SCEV * visitAddExpr(const SCEVAddExpr *Expr)
const SCEV * visit(const SCEV *S)
Class for arbitrary precision integers.
LLVM_ABI APInt umul_ov(const APInt &RHS, bool &Overflow) const
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
uint64_t getZExtValue() const
Get zero extended value.
void setHighBits(unsigned hiBits)
Set the top hiBits bits.
LLVM_ABI APInt getHiBits(unsigned numBits) const
Compute an APInt containing numBits highbits from this APInt.
unsigned getActiveBits() const
Compute the number of active bits in the value.
LLVM_ABI APInt trunc(unsigned width) const
Truncate to new width.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
APInt abs() const
Get the absolute value.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool isSignMask() const
Check if the APInt's value is returned by getSignMask.
LLVM_ABI APInt urem(const APInt &RHS) const
Unsigned remainder operation.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
bool isNegative() const
Determine sign of this APInt.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
bool isNonPositive() const
Determine if this APInt Value is non-positive (<= 0).
unsigned countTrailingZeros() const
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
unsigned logBase2() const
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
LLVM_ABI APInt multiplicativeInverse() const
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
LLVM_ABI APInt sext(unsigned width) const
Sign extend to a new width.
APInt shl(unsigned shiftAmt) const
Left-shift function.
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
bool isSignBitSet() const
Determine if sign bit of this APInt is set.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
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 Constant * getPtrAdd(Constant *Ptr, Constant *Offset, GEPNoWrapFlags NW=GEPNoWrapFlags::none(), std::optional< ConstantRange > InRange=std::nullopt, Type *OnlyIfReduced=nullptr)
Create a getelementptr i8, ptr, offset constant expression.
static LLVM_ABI Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static LLVM_ABI Constant * getPtrToAddr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static LLVM_ABI Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
static LLVM_ABI Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
This is the shared class of boolean and integer constants.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
static LLVM_ABI ConstantInt * getBool(LLVMContext &Context, bool V)
This class represents a range of values.
LLVM_ABI ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
LLVM_ABI ConstantRange zextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
PreferredRangeType
If represented precisely, the result of some range operations may consist of multiple disjoint ranges...
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI ConstantRange urem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned remainder operation of...
LLVM_ABI bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
LLVM_ABI bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other?
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI ConstantRange zeroExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
LLVM_ABI bool isSignWrappedSet() const
Return true if this set wraps around the signed domain.
LLVM_ABI APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
LLVM_ABI bool isWrappedSet() const
Return true if this set wraps around the unsigned domain.
LLVM_ABI void print(raw_ostream &OS) const
Print out the bounds to a stream.
LLVM_ABI ConstantRange truncate(uint32_t BitWidth, unsigned NoWrapKind=0) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
LLVM_ABI ConstantRange signExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI bool contains(const APInt &Val) const
Return true if the specified value is in the set.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
LLVM_ABI ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
LLVM_ABI APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
static LLVM_ABI ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
LLVM_ABI unsigned getMinSignedBits() const
Compute the maximal number of bits needed to represent every value in this signed range.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
LLVM_ABI ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
LLVM_ABI ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
static LLVM_ABI ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)
Produce the range that contains X if and only if "X BinOp Other" does not wrap.
This is an important base class in LLVM.
A parsed version of the target data layout string in and methods for querying it.
LLVM_ABI const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
LLVM_ABI IntegerType * getIntPtrType(LLVMContext &C, unsigned AddressSpace=0) const
Returns an integer type with size at least as big as that of a pointer in the given address space.
LLVM_ABI unsigned getIndexTypeSizeInBits(Type *Ty) const
The size in bits of the index used in GEP calculation for this type.
LLVM_ABI IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
TypeSize getTypeSizeInBits(Type *Ty) const
Size examples:
ValueT lookup(const_arg_type_t< KeyT > Val) const
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.
A helper class to return the specified delimiter string after the first invocation of operator String...
An instruction for reading from memory.
Analysis pass that exposes the LoopInfo for a function.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getHeader() const
unsigned getLoopDepth() const
Return the nesting level of this loop.
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
A Module instance is used to store all the information related to an LLVM module.
unsigned getOpcode() const
Return the opcode for this Instruction or ConstantExpr.
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
bool hasNoSignedWrap() const
Test whether this operation is known to never undergo signed overflow, aka the nsw property.
bool hasNoUnsignedWrap() const
Test whether this operation is known to never undergo unsigned overflow, aka the nuw property.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
PointerIntPair - This class implements a pair of a pointer and small integer.
static PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the default address space (address sp...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
LLVM_ABI void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
LLVM_ABI const SCEVPredicate & getPredicate() const
LLVM_ABI const SCEV * getPredicatedSCEV(const SCEV *Expr)
Returns the rewritten SCEV for Expr in the context of the current SCEV predicate.
LLVM_ABI bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've proved that V doesn't wrap by means of a SCEV predicate.
LLVM_ABI void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Proves that V doesn't overflow by adding SCEV predicate.
LLVM_ABI void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
LLVM_ABI bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds.
LLVM_ABI PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
LLVM_ABI const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
LLVM_ABI unsigned getSmallConstantMaxTripCount()
Returns the upper bound of the loop trip count as a normal unsigned value, or 0 if the trip count is ...
LLVM_ABI const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSymbolicMaxBackedgeTakenCount()
Get the (predicated) symbolic max backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
constexpr bool isValid() const
This node represents an addition of some number of SCEVs.
This node represents a polynomial recurrence on the trip count of the specified loop.
friend class ScalarEvolution
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, without capturing the p...
This class represents a cast from a pointer to a pointer-sized integer value.
This visitor recursively visits a SCEV expression and re-writes it.
const SCEV * visitSignExtendExpr(const SCEVSignExtendExpr *Expr)
const SCEV * visit(const SCEV *S)
const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)
const SCEV * visitSMinExpr(const SCEVSMinExpr *Expr)
SCEVRewriteVisitor(ScalarEvolution &SE)
const SCEV * visitUMinExpr(const SCEVUMinExpr *Expr)
This class represents a signed minimum selection.
This node is the base class for sequential/in-order min/max selections.
static SCEVTypes getEquivalentNonSequentialSCEVType(SCEVTypes Ty)
This class represents a sign extension of a small integer value to a larger integer value.
Visit all nodes in the expression tree using worklist traversal.
This class represents a truncation of an integer value to a smaller integer value.
This class represents a binary unsigned division operation.
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 * getLosslessPtrToIntExpr(const SCEV *Op)
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 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 SCEV * getPtrToAddrExpr(const SCEV *Op)
LLVM_ABI const SCEVAddRecExpr * convertSCEVToAddRecWithPredicates(const SCEV *S, const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Preds)
Tries to convert the S expression to an AddRec expression, adding additional predicates to Preds as r...
LLVM_ABI const SCEV * 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.
StringRef - Represent a constant reference to a string, i.e.
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
TypeSize getElementOffset(unsigned Idx) const
TypeSize getSizeInBits() const
Class to represent struct types.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntOrPtrTy() const
Return true if this is an integer type or a pointer type.
bool isIntegerTy() const
True if this is an instance of IntegerType.
static LLVM_ABI IntegerType * getIntNTy(LLVMContext &C, unsigned N)
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
LLVMContext & getContext() const
All values hold a context through their type.
unsigned getValueID() const
Return an ID for the concrete type of this object.
LLVM_ABI void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
LLVM_ABI std::optional< APInt > SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, unsigned RangeWidth)
Let q(n) = An^2 + Bn + C, and BW = bit width of the value range (e.g.
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
LLVM_ABI APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
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.
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