83#include "llvm/Config/llvm-config.h"
138#define DEBUG_TYPE "scalar-evolution"
141 "Number of loop exits with predictable exit counts");
143 "Number of loop exits without predictable exit counts");
145 "Number of loops with trip counts computed by force");
147#ifdef EXPENSIVE_CHECKS
155 cl::desc(
"Maximum number of iterations SCEV will "
156 "symbolically execute a constant "
162 cl::desc(
"Verify ScalarEvolution's backedge taken counts (slow)"));
165 cl::desc(
"Enable stricter verification with -verify-scev is passed"));
169 cl::desc(
"Verify IR correctness when making sensitive SCEV queries (slow)"),
174 cl::desc(
"Threshold for inlining multiplication operands into a SCEV"),
179 cl::desc(
"Threshold for inlining addition operands into a SCEV"),
183 "scalar-evolution-max-scev-compare-depth",
cl::Hidden,
184 cl::desc(
"Maximum depth of recursive SCEV complexity comparisons"),
188 "scalar-evolution-max-scev-operations-implication-depth",
cl::Hidden,
189 cl::desc(
"Maximum depth of recursive SCEV operations implication analysis"),
193 "scalar-evolution-max-value-compare-depth",
cl::Hidden,
194 cl::desc(
"Maximum depth of recursive value complexity comparisons"),
199 cl::desc(
"Maximum depth of recursive arithmetics"),
203 "scalar-evolution-max-constant-evolving-depth",
cl::Hidden,
208 cl::desc(
"Maximum depth of recursive SExt/ZExt/Trunc"),
213 cl::desc(
"Max coefficients in AddRec during evolving"),
218 cl::desc(
"Size of the expression which is considered huge"),
223 cl::desc(
"Threshold for switching to iteratively computing SCEV ranges"),
227 "scalar-evolution-max-loop-guard-collection-depth",
cl::Hidden,
228 cl::desc(
"Maximum depth for recursive loop guard collection"),
cl::init(1));
233 cl::desc(
"When printing analysis, include information on every instruction"));
236 "scalar-evolution-use-expensive-range-sharpening",
cl::Hidden,
238 cl::desc(
"Use more powerful methods of sharpening expression ranges. May "
239 "be costly in terms of compile time"));
242 "scalar-evolution-max-scc-analysis-depth",
cl::Hidden,
243 cl::desc(
"Maximum amount of nodes to process while searching SCEVUnknown "
244 "Phi strongly connected components"),
249 cl::desc(
"Handle <= and >= in finite loops"),
253 "scalar-evolution-use-context-for-no-wrap-flag-strenghening",
cl::Hidden,
254 cl::desc(
"Infer nuw/nsw flags using context where suitable"),
265#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
283 OS <<
"(ptrtoint " << *
Op->getType() <<
" " << *
Op <<
" to "
284 << *PtrToInt->
getType() <<
")";
290 OS <<
"(trunc " << *
Op->getType() <<
" " << *
Op <<
" to "
297 OS <<
"(zext " << *
Op->getType() <<
" " << *
Op <<
" to "
304 OS <<
"(sext " << *
Op->getType() <<
" " << *
Op <<
" to "
333 const char *OpStr =
nullptr;
346 OpStr =
" umin_seq ";
370 OS <<
"(" << *UDiv->
getLHS() <<
" /u " << *UDiv->
getRHS() <<
")";
377 OS <<
"***COULDNOTCOMPUTE***";
453 if (!
Mul)
return false;
457 if (!SC)
return false;
475 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
477 UniqueSCEVs.InsertNode(S, IP);
496 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
499 UniqueSCEVs.InsertNode(S, IP);
519 "Must be a non-bit-width-changing pointer-to-integer cast!");
531 "Cannot truncate non-integer value!");
538 "Cannot zero extend non-integer value!");
545 "Cannot sign extend non-integer value!");
550 SE->forgetMemoizedResults(
this);
553 SE->UniqueSCEVs.RemoveNode(
this);
559void SCEVUnknown::allUsesReplacedWith(
Value *New) {
561 SE->forgetMemoizedResults(
this);
564 SE->UniqueSCEVs.RemoveNode(
this);
586 if (LIsPointer != RIsPointer)
587 return (
int)LIsPointer - (int)RIsPointer;
592 return (
int)LID - (int)RID;
597 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
598 return (
int)LArgNo - (int)RArgNo;
604 if (
auto L = LGV->getLinkage() - RGV->getLinkage())
607 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
608 auto LT = GV->getLinkage();
615 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
616 return LGV->getName().compare(RGV->getName());
627 if (LParent != RParent) {
630 if (LDepth != RDepth)
631 return (
int)LDepth - (int)RDepth;
635 unsigned LNumOps = LInst->getNumOperands(),
636 RNumOps = RInst->getNumOperands();
637 if (LNumOps != RNumOps)
638 return (
int)LNumOps - (int)RNumOps;
640 for (
unsigned Idx :
seq(LNumOps)) {
642 RInst->getOperand(Idx),
Depth + 1);
656static std::optional<int>
666 return (
int)LType - (int)RType;
691 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
692 if (LBitWidth != RBitWidth)
693 return (
int)LBitWidth - (int)RBitWidth;
694 return LA.
ult(
RA) ? -1 : 1;
700 return LTy->getBitWidth() - RTy->getBitWidth();
711 if (LLoop != RLoop) {
713 assert(LHead != RHead &&
"Two loops share the same header?");
717 "No dominance between recurrences used by one SCEV?");
740 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
741 if (LNumOps != RNumOps)
742 return (
int)LNumOps - (int)RNumOps;
744 for (
unsigned i = 0; i != LNumOps; ++i) {
769 if (
Ops.size() < 2)
return;
774 return Complexity && *Complexity < 0;
776 if (
Ops.size() == 2) {
780 if (IsLessComplex(
RHS,
LHS))
787 return IsLessComplex(
LHS,
RHS);
794 for (
unsigned i = 0, e =
Ops.size(); i != e-2; ++i) {
800 for (
unsigned j = i+1; j != e &&
Ops[j]->getSCEVType() == Complexity; ++j) {
805 if (i == e-2)
return;
827template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
831 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
833 for (
unsigned Idx = 0; Idx <
Ops.size();) {
841 Ops.erase(
Ops.begin() + Idx);
848 assert(Folded &&
"Must have folded value");
852 if (Folded && IsAbsorber(Folded->
getAPInt()))
856 if (Folded && !IsIdentity(Folded->
getAPInt()))
857 Ops.insert(
Ops.begin(), Folded);
859 return Ops.size() == 1 ?
Ops[0] :
nullptr;
934 APInt OddFactorial(W, 1);
936 for (
unsigned i = 3; i <= K; ++i) {
939 OddFactorial *= (i >> TwoFactors);
943 unsigned CalculationBits = W +
T;
957 for (
unsigned i = 1; i != K; ++i) {
990 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1010 "getLosslessPtrToIntExpr() should self-recurse at most once.");
1014 if (!
Op->getType()->isPointerTy())
1025 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1055 SCEV *S =
new (SCEVAllocator)
1057 UniqueSCEVs.InsertNode(S, IP);
1062 assert(
Depth == 0 &&
"getLosslessPtrToIntExpr() should not self-recurse for "
1063 "non-SCEVUnknown's.");
1075 class SCEVPtrToIntSinkingRewriter
1083 SCEVPtrToIntSinkingRewriter
Rewriter(SE);
1084 return Rewriter.visit(Scev);
1093 return Base::visit(S);
1118 "Should only reach pointer-typed SCEVUnknown's.");
1124 const SCEV *IntOp = SCEVPtrToIntSinkingRewriter::rewrite(
Op, *
this);
1126 "We must have succeeded in sinking the cast, "
1127 "and ending up with an integer-typed expression!");
1132 assert(Ty->isIntegerTy() &&
"Target type must be an integer type!");
1144 "This is not a truncating conversion!");
1146 "This is not a conversion to a SCEVable type!");
1147 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1155 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1177 UniqueSCEVs.InsertNode(S, IP);
1189 unsigned numTruncs = 0;
1190 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1198 if (numTruncs < 2) {
1208 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1215 for (
const SCEV *
Op : AddRec->operands())
1230 UniqueSCEVs.InsertNode(S, IP);
1270struct ExtendOpTraitsBase {
1271 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
const SCEV *,
Type *,
1276template <
typename ExtendOp>
struct ExtendOpTraits {
1292 static const GetExtendExprTy GetExtendExpr;
1294 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1295 ICmpInst::Predicate *Pred,
1296 ScalarEvolution *SE) {
1301const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1308 static const GetExtendExprTy GetExtendExpr;
1310 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1311 ICmpInst::Predicate *Pred,
1312 ScalarEvolution *SE) {
1317const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1329template <
typename ExtendOpTy>
1332 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1333 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1349 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1362 auto PreStartFlags =
1380 const SCEV *OperandExtendedStart =
1382 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1383 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1395 const SCEV *OverflowLimit =
1396 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1398 if (OverflowLimit &&
1406template <
typename ExtendOpTy>
1410 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1418 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1453template <
typename ExtendOpTy>
1454bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1457 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1467 APInt StartAI = StartC->
getAPInt();
1469 for (
unsigned Delta : {-2, -1, 1, 2}) {
1470 const SCEV *PreStart =
getConstant(StartAI - Delta);
1472 FoldingSetNodeID
ID;
1474 ID.AddPointer(PreStart);
1475 ID.AddPointer(Step);
1479 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
1483 if (PreAR && PreAR->getNoWrapFlags(WrapType)) {
1486 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1487 DeltaS, &Pred,
this);
1505 const unsigned BitWidth =
C.getBitWidth();
1523 const APInt &ConstantStart,
1542 auto &UserIDs = FoldCacheUser[
I.first->second];
1543 assert(
count(UserIDs,
ID) == 1 &&
"unexpected duplicates in UserIDs");
1544 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1545 if (UserIDs[
I] ==
ID) {
1550 I.first->second = S;
1552 FoldCacheUser[S].push_back(
ID);
1558 "This is not an extending conversion!");
1560 "This is not a conversion to a SCEVable type!");
1561 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1565 if (
const SCEV *S = FoldCache.lookup(
ID))
1577 "This is not an extending conversion!");
1579 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1596 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1600 UniqueSCEVs.InsertNode(S, IP);
1609 const SCEV *
X = ST->getOperand();
1623 if (AR->isAffine()) {
1624 const SCEV *Start = AR->getStart();
1625 const SCEV *Step = AR->getStepRecurrence(*
this);
1627 const Loop *L = AR->getLoop();
1631 if (AR->hasNoUnsignedWrap()) {
1652 const SCEV *CastedMaxBECount =
1656 if (MaxBECount == RecastedMaxBECount) {
1666 const SCEV *WideMaxBECount =
1668 const SCEV *OperandExtendedAdd =
1674 if (ZAdd == OperandExtendedAdd) {
1685 OperandExtendedAdd =
1691 if (ZAdd == OperandExtendedAdd) {
1712 !AC.assumptions().empty()) {
1714 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1716 if (AR->hasNoUnsignedWrap()) {
1751 const APInt &
C = SC->getAPInt();
1755 const SCEV *SResidual =
1764 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1789 if (SA->hasNoUnsignedWrap()) {
1793 for (
const auto *
Op : SA->operands())
1810 const SCEV *SResidual =
1822 if (SM->hasNoUnsignedWrap()) {
1826 for (
const auto *
Op : SM->operands())
1844 const SCEV *TruncRHS;
1863 for (
auto *Operand :
MinMax->operands())
1874 for (
auto *Operand :
MinMax->operands())
1881 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1884 UniqueSCEVs.InsertNode(S, IP);
1892 "This is not an extending conversion!");
1894 "This is not a conversion to a SCEVable type!");
1895 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1899 if (
const SCEV *S = FoldCache.lookup(
ID))
1911 "This is not an extending conversion!");
1913 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1935 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1940 UniqueSCEVs.InsertNode(S, IP);
1949 const SCEV *
X = ST->getOperand();
1960 if (SA->hasNoSignedWrap()) {
1964 for (
const auto *
Op : SA->operands())
1982 const SCEV *SResidual =
1996 if (AR->isAffine()) {
1997 const SCEV *Start = AR->getStart();
1998 const SCEV *Step = AR->getStepRecurrence(*
this);
2000 const Loop *L = AR->getLoop();
2004 if (AR->hasNoSignedWrap()) {
2026 const SCEV *CastedMaxBECount =
2030 if (MaxBECount == RecastedMaxBECount) {
2040 const SCEV *WideMaxBECount =
2042 const SCEV *OperandExtendedAdd =
2048 if (SAdd == OperandExtendedAdd) {
2059 OperandExtendedAdd =
2065 if (SAdd == OperandExtendedAdd) {
2085 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2087 if (AR->hasNoSignedWrap()) {
2102 const APInt &
C = SC->getAPInt();
2106 const SCEV *SResidual =
2115 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2134 for (
auto *Operand :
MinMax->operands())
2143 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
2146 UniqueSCEVs.InsertNode(S, IP);
2172 "This is not an extending conversion!");
2174 "This is not a conversion to a SCEVable type!");
2179 if (SC->getAPInt().isNegative())
2184 const SCEV *NewOp =
T->getOperand();
2203 for (
const SCEV *
Op : AR->operands())
2242 APInt &AccumulatedConstant,
2245 bool Interesting =
false;
2252 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2254 AccumulatedConstant += Scale *
C->getAPInt();
2259 for (; i !=
Ops.size(); ++i) {
2269 Add->operands(), NewScale, SE);
2275 auto Pair = M.insert({
Key, NewScale});
2279 Pair.first->second += NewScale;
2287 std::pair<DenseMap<const SCEV *, APInt>::iterator,
bool> Pair =
2288 M.insert({
Ops[i], Scale});
2292 Pair.first->second += Scale;
2311 case Instruction::Add:
2314 case Instruction::Sub:
2317 case Instruction::Mul:
2331 const SCEV *
A = (this->*Extension)(
2333 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2334 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2342 if (BinOp == Instruction::Mul)
2348 APInt C = RHSC->getAPInt();
2349 unsigned NumBits =
C.getBitWidth();
2350 bool IsSub = (BinOp == Instruction::Sub);
2351 bool IsNegativeConst = (
Signed &&
C.isNegative());
2353 bool OverflowDown = IsSub ^ IsNegativeConst;
2355 if (IsNegativeConst) {
2368 APInt Limit = Min + Magnitude;
2374 APInt Limit = Max - Magnitude;
2379std::optional<SCEV::NoWrapFlags>
2384 return std::nullopt;
2393 bool Deduced =
false;
2395 if (OBO->
getOpcode() != Instruction::Add &&
2398 return std::nullopt;
2407 false, LHS, RHS, CtxI)) {
2414 true, LHS, RHS, CtxI)) {
2421 return std::nullopt;
2431 using namespace std::placeholders;
2438 assert(CanAnalyze &&
"don't call from other places!");
2445 auto IsKnownNonNegative = [&](
const SCEV *S) {
2455 if (SignOrUnsignWrap != SignOrUnsignMask &&
2462 return Instruction::Add;
2464 return Instruction::Mul;
2475 Opcode,
C, OBO::NoSignedWrap);
2483 Opcode,
C, OBO::NoUnsignedWrap);
2493 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2500 if (UDiv->getOperand(1) ==
Ops[1])
2503 if (UDiv->getOperand(1) ==
Ops[0])
2519 "only nuw or nsw allowed");
2520 assert(!
Ops.empty() &&
"Cannot get empty add!");
2521 if (
Ops.size() == 1)
return Ops[0];
2524 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2526 "SCEVAddExpr operand types don't match!");
2528 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2529 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2534 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2535 [](
const APInt &
C) {
return C.isZero(); },
2536 [](
const APInt &
C) {
return false; });
2549 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2554 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2555 Add->setNoWrapFlags(ComputeFlags(
Ops));
2563 bool FoundMatch =
false;
2564 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2565 if (
Ops[i] ==
Ops[i+1]) {
2577 --i; e -=
Count - 1;
2587 auto FindTruncSrcType = [&]() ->
Type * {
2593 return T->getOperand()->getType();
2595 const auto *LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2597 return T->getOperand()->getType();
2601 if (
auto *SrcType = FindTruncSrcType()) {
2608 if (
T->getOperand()->getType() != SrcType) {
2617 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2620 if (
T->getOperand()->getType() != SrcType) {
2648 if (
Ops.size() == 2) {
2658 auto C2 =
C->getAPInt();
2661 APInt ConstAdd = C1 + C2;
2662 auto AddFlags = AddExpr->getNoWrapFlags();
2703 if (
Ops.size() == 2 &&
2714 if (Idx <
Ops.size()) {
2715 bool DeletedAdd =
false;
2726 Ops.erase(
Ops.begin()+Idx);
2729 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2752 struct APIntCompare {
2753 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2754 return LHS.ult(RHS);
2761 std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists;
2762 for (
const SCEV *NewOp : NewOps)
2763 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2766 if (AccumulatedConstant != 0)
2768 for (
auto &MulOp : MulOpLists) {
2769 if (MulOp.first == 1) {
2771 }
else if (MulOp.first != 0) {
2780 if (
Ops.size() == 1)
2791 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2792 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2795 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp)
2796 if (MulOpSCEV ==
Ops[AddOp]) {
2798 const SCEV *InnerMul =
Mul->getOperand(MulOp == 0);
2799 if (
Mul->getNumOperands() != 2) {
2803 Mul->operands().take_front(MulOp));
2811 if (
Ops.size() == 2)
return OuterMul;
2813 Ops.erase(
Ops.begin()+AddOp);
2814 Ops.erase(
Ops.begin()+Idx-1);
2816 Ops.erase(
Ops.begin()+Idx);
2817 Ops.erase(
Ops.begin()+AddOp-1);
2819 Ops.push_back(OuterMul);
2824 for (
unsigned OtherMulIdx = Idx+1;
2831 OMulOp != e; ++OMulOp)
2832 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2834 const SCEV *InnerMul1 =
Mul->getOperand(MulOp == 0);
2835 if (
Mul->getNumOperands() != 2) {
2837 Mul->operands().take_front(MulOp));
2844 OtherMul->
operands().take_front(OMulOp));
2849 const SCEV *InnerMulSum =
2853 if (
Ops.size() == 2)
return OuterMul;
2854 Ops.erase(
Ops.begin()+Idx);
2855 Ops.erase(
Ops.begin()+OtherMulIdx-1);
2856 Ops.push_back(OuterMul);
2876 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2879 Ops.erase(
Ops.begin()+i);
2884 if (!LIOps.
empty()) {
2909 auto *DefI = getDefiningScopeBound(LIOps);
2911 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2923 if (
Ops.size() == 1)
return NewRec;
2926 for (
unsigned i = 0;; ++i)
2927 if (
Ops[i] == AddRec) {
2937 for (
unsigned OtherIdx = Idx+1;
2945 "AddRecExprs are not sorted in reverse dominance order?");
2952 if (OtherAddRec->getLoop() == AddRecLoop) {
2953 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2955 if (i >= AddRecOps.
size()) {
2956 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2960 AddRecOps[i], OtherAddRec->getOperand(i)};
2963 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
2978 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2990 static_cast<SCEVAddExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
2994 S =
new (SCEVAllocator)
2996 UniqueSCEVs.InsertNode(S, IP);
3006 FoldingSetNodeID
ID;
3008 for (
const SCEV *
Op :
Ops)
3013 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3015 const SCEV **
O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
3017 S =
new (SCEVAllocator)
3018 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3019 UniqueSCEVs.InsertNode(S, IP);
3020 LoopUsers[
L].push_back(S);
3030 FoldingSetNodeID
ID;
3032 for (
const SCEV *
Op :
Ops)
3036 static_cast<SCEVMulExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3038 const SCEV **
O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
3040 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3042 UniqueSCEVs.InsertNode(S, IP);
3051 if (j > 1 && k / j != i) Overflow =
true;
3067 if (n == 0 || n == k)
return 1;
3068 if (k > n)
return 0;
3074 for (
uint64_t i = 1; i <= k; ++i) {
3075 r =
umul_ov(r, n-(i-1), Overflow);
3084 struct FindConstantInAddMulChain {
3085 bool FoundConstant =
false;
3087 bool follow(
const SCEV *S) {
3092 bool isDone()
const {
3093 return FoundConstant;
3097 FindConstantInAddMulChain
F;
3099 ST.visitAll(StartExpr);
3100 return F.FoundConstant;
3108 "only nuw or nsw allowed");
3109 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3110 if (
Ops.size() == 1)
return Ops[0];
3112 Type *ETy =
Ops[0]->getType();
3114 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3116 "SCEVMulExpr operand types don't match!");
3121 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3122 [](
const APInt &
C) {
return C.isOne(); },
3123 [](
const APInt &
C) {
return C.isZero(); });
3134 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3139 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3140 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3145 if (
Ops.size() == 2) {
3153 const SCEV *Op0, *Op1;
3161 if (
Ops[0]->isAllOnesValue()) {
3166 bool AnyFolded =
false;
3167 for (
const SCEV *AddOp :
Add->operands()) {
3194 AddRec->getNoWrapFlags(FlagsMask));
3217 APInt C1V = LHSC->getAPInt();
3227 const SCEV *NewMul =
nullptr;
3231 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3246 if (Idx <
Ops.size()) {
3247 bool DeletedMul =
false;
3253 Ops.erase(
Ops.begin()+Idx);
3277 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3280 Ops.erase(
Ops.begin()+i);
3285 if (!LIOps.
empty()) {
3298 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3314 if (
Ops.size() == 1)
return NewRec;
3317 for (
unsigned i = 0;; ++i)
3318 if (
Ops[i] == AddRec) {
3339 bool OpsModified =
false;
3340 for (
unsigned OtherIdx = Idx+1;
3354 bool Overflow =
false;
3361 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3365 z < ze && !Overflow; ++z) {
3368 if (LargerThan64Bits)
3369 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3371 Coeff = Coeff1*Coeff2;
3386 if (
Ops.size() == 2)
return NewAddRec;
3387 Ops[Idx] = NewAddRec;
3388 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3404 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3412 "SCEVURemExpr operand types don't match!");
3417 if (RHSC->getValue()->isOne())
3418 return getZero(LHS->getType());
3421 if (RHSC->getAPInt().isPowerOf2()) {
3422 Type *FullTy = LHS->getType();
3439 assert(!LHS->getType()->isPointerTy() &&
3440 "SCEVUDivExpr operand can't be pointer!");
3441 assert(LHS->getType() == RHS->getType() &&
3442 "SCEVUDivExpr operand types don't match!");
3449 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3457 if (RHSC->getValue()->isOne())
3462 if (!RHSC->getValue()->isZero()) {
3466 Type *Ty = LHS->getType();
3467 unsigned LZ = RHSC->getAPInt().countl_zero();
3471 if (!RHSC->getAPInt().isPowerOf2())
3479 const APInt &StepInt = Step->getAPInt();
3480 const APInt &DivInt = RHSC->getAPInt();
3481 if (!StepInt.
urem(DivInt) &&
3487 for (
const SCEV *
Op : AR->operands())
3495 if (StartC && !DivInt.
urem(StepInt) &&
3501 const APInt &StartRem = StartInt.
urem(StepInt);
3502 if (StartRem != 0) {
3503 const SCEV *NewLHS =
3506 if (LHS != NewLHS) {
3516 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3525 for (
const SCEV *
Op : M->operands())
3529 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3530 const SCEV *
Op = M->getOperand(i);
3542 if (
auto *DivisorConstant =
3544 bool Overflow =
false;
3546 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3557 for (
const SCEV *
Op :
A->operands())
3561 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3568 if (Operands.
size() ==
A->getNumOperands())
3575 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3585 return getZero(LHS->getType());
3589 const SCEV *NewLHS, *NewRHS;
3597 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
3600 UniqueSCEVs.InsertNode(S, IP);
3630 if (!
Mul || !
Mul->hasNoUnsignedWrap())
3637 if (LHSCst == RHSCst) {
3645 APInt Factor =
gcd(LHSCst, RHSCst);
3663 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3664 if (
Mul->getOperand(i) == RHS) {
3683 if (StepChrec->getLoop() == L) {
3697 if (Operands.
size() == 1)
return Operands[0];
3702 "SCEVAddRecExpr operand types don't match!");
3703 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3705 for (
const SCEV *
Op : Operands)
3707 "SCEVAddRecExpr operand is not available at loop entry!");
3710 if (Operands.
back()->isZero()) {
3725 const Loop *NestedLoop = NestedAR->getLoop();
3726 if (L->contains(NestedLoop)
3729 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3731 Operands[0] = NestedAR->getStart();
3735 bool AllInvariant =
all_of(
3747 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3758 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3762 Operands[0] = NestedAR;
3768 return getOrCreateAddRecExpr(Operands, L, Flags);
3784 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3788 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3802 bool FirstIter =
true;
3804 for (
const SCEV *IndexExpr : IndexExprs) {
3811 Offsets.push_back(FieldOffset);
3814 CurTy = STy->getTypeAtIndex(Index);
3819 "The first index of a GEP indexes a pointer");
3820 CurTy = SrcElementTy;
3831 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3832 Offsets.push_back(LocalOffset);
3837 if (Offsets.empty())
3850 "GEP should not change type mid-flight.");
3854SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3857 ID.AddInteger(SCEVType);
3861 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3871 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3872 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3873 if (
Ops.size() == 1)
return Ops[0];
3876 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3878 "Operand types don't match!");
3881 "min/max should be consistently pointerish");
3907 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3909 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3914 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3916 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3922 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3928 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3933 if (Idx <
Ops.size()) {
3934 bool DeletedAny =
false;
3935 while (
Ops[Idx]->getSCEVType() == Kind) {
3937 Ops.erase(
Ops.begin()+Idx);
3955 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3956 if (
Ops[i] ==
Ops[i + 1] ||
3957 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3960 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3963 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3966 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3972 if (
Ops.size() == 1)
return Ops[0];
3974 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
3979 ID.AddInteger(Kind);
3983 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3985 return ExistingSCEV;
3986 const SCEV **O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
3988 SCEV *S =
new (SCEVAllocator)
3991 UniqueSCEVs.InsertNode(S, IP);
3998class SCEVSequentialMinMaxDeduplicatingVisitor final
3999 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4000 std::optional<const SCEV *>> {
4001 using RetVal = std::optional<const SCEV *>;
4009 bool canRecurseInto(
SCEVTypes Kind)
const {
4012 return RootKind == Kind || NonSequentialRootKind == Kind;
4015 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
4017 "Only for min/max expressions.");
4020 if (!canRecurseInto(Kind))
4030 return std::nullopt;
4037 RetVal
visit(
const SCEV *S) {
4039 if (!SeenOps.
insert(S).second)
4040 return std::nullopt;
4041 return Base::visit(S);
4045 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4047 : SE(SE), RootKind(RootKind),
4048 NonSequentialRootKind(
4049 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4053 SmallVectorImpl<const SCEV *> &NewOps) {
4058 for (
const SCEV *
Op : OrigOps) {
4063 Ops.emplace_back(*NewOp);
4067 NewOps = std::move(
Ops);
4071 RetVal visitConstant(
const SCEVConstant *Constant) {
return Constant; }
4073 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4075 RetVal visitPtrToIntExpr(
const SCEVPtrToIntExpr *Expr) {
return Expr; }
4077 RetVal visitTruncateExpr(
const SCEVTruncateExpr *Expr) {
return Expr; }
4079 RetVal visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
return Expr; }
4081 RetVal visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
return Expr; }
4083 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4085 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4087 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4089 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4091 RetVal visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
4092 return visitAnyMinMaxExpr(Expr);
4095 RetVal visitUMaxExpr(
const SCEVUMaxExpr *Expr) {
4096 return visitAnyMinMaxExpr(Expr);
4099 RetVal visitSMinExpr(
const SCEVSMinExpr *Expr) {
4100 return visitAnyMinMaxExpr(Expr);
4103 RetVal visitUMinExpr(
const SCEVUMinExpr *Expr) {
4104 return visitAnyMinMaxExpr(Expr);
4107 RetVal visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *Expr) {
4108 return visitAnyMinMaxExpr(Expr);
4111 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4113 RetVal visitCouldNotCompute(
const SCEVCouldNotCompute *Expr) {
return Expr; }
4155struct SCEVPoisonCollector {
4156 bool LookThroughMaybePoisonBlocking;
4157 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4158 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4159 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4161 bool follow(
const SCEV *S) {
4162 if (!LookThroughMaybePoisonBlocking &&
4172 bool isDone()
const {
return false; }
4182 SCEVPoisonCollector PC1(
true);
4187 if (PC1.MaybePoison.empty())
4193 SCEVPoisonCollector PC2(
false);
4203 SCEVPoisonCollector PC(
false);
4226 while (!Worklist.
empty()) {
4228 if (!Visited.
insert(V).second)
4232 if (Visited.
size() > 16)
4237 if (PoisonVals.
contains(V) || ::isGuaranteedNotToBePoison(V))
4248 if (PDI->isDisjoint())
4255 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4262 if (
I->hasPoisonGeneratingAnnotations())
4273 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4274 "Not a SCEVSequentialMinMaxExpr!");
4275 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4276 if (
Ops.size() == 1)
4280 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4282 "Operand types don't match!");
4285 "min/max should be consistently pointerish");
4293 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4300 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4310 bool DeletedAny =
false;
4311 while (Idx <
Ops.size()) {
4312 if (
Ops[Idx]->getSCEVType() != Kind) {
4317 Ops.erase(
Ops.begin() + Idx);
4318 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4319 SMME->operands().end());
4327 const SCEV *SaturationPoint;
4338 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4339 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4351 Ops.erase(
Ops.begin() + i);
4356 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4357 Ops.erase(
Ops.begin() + i);
4365 ID.AddInteger(Kind);
4369 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4371 return ExistingSCEV;
4373 const SCEV **O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
4375 SCEV *S =
new (SCEVAllocator)
4378 UniqueSCEVs.InsertNode(S, IP);
4426 if (
Size.isScalable())
4447 "Cannot get offset for structure containing scalable vector types");
4461 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP)) {
4463 "Stale SCEVUnknown in uniquing map!");
4469 UniqueSCEVs.InsertNode(S, IP);
4483 return Ty->isIntOrPtrTy();
4490 if (Ty->isPointerTy())
4501 if (Ty->isIntegerTy())
4505 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4517 bool PreciseA, PreciseB;
4518 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4519 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4520 if (!PreciseA || !PreciseB)
4523 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4524 DT.dominates(ScopeB, ScopeA);
4528 return CouldNotCompute.get();
4531bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4534 return SU && SU->getValue() ==
nullptr;
4537 return !ContainsNulls;
4542 if (
I != HasRecMap.end())
4547 HasRecMap.insert({S, FoundAddRec});
4555 if (
SI == ExprValueMap.
end())
4557 return SI->second.getArrayRef();
4563void ScalarEvolution::eraseValueFromMap(
Value *V) {
4565 if (
I != ValueExprMap.end()) {
4566 auto EVIt = ExprValueMap.find(
I->second);
4567 bool Removed = EVIt->second.remove(V);
4569 assert(Removed &&
"Value not in ExprValueMap?");
4570 ValueExprMap.erase(
I);
4574void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4578 auto It = ValueExprMap.find_as(V);
4579 if (It == ValueExprMap.end()) {
4581 ExprValueMap[S].insert(V);
4592 return createSCEVIter(V);
4599 if (
I != ValueExprMap.end()) {
4600 const SCEV *S =
I->second;
4601 assert(checkValidity(S) &&
4602 "existing SCEV has not been properly invalidated");
4615 Type *Ty = V->getType();
4631 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4644 return (
const SCEV *)
nullptr;
4650 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4654 Type *Ty = V->getType();
4660 assert(
P->getType()->isPointerTy());
4673 const SCEV **PtrOp =
nullptr;
4674 for (
const SCEV *&AddOp :
Ops) {
4675 if (AddOp->getType()->isPointerTy()) {
4676 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4694 return getZero(LHS->getType());
4699 if (RHS->getType()->isPointerTy()) {
4700 if (!LHS->getType()->isPointerTy() ||
4710 const bool RHSIsNotMinSigned =
4741 Type *SrcTy = V->getType();
4742 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4743 "Cannot truncate or zero extend with non-integer arguments!");
4753 Type *SrcTy = V->getType();
4754 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4755 "Cannot truncate or zero extend with non-integer arguments!");
4765 Type *SrcTy = V->getType();
4766 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4767 "Cannot noop or zero extend with non-integer arguments!");
4769 "getNoopOrZeroExtend cannot truncate!");
4777 Type *SrcTy = V->getType();
4778 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4779 "Cannot noop or sign extend with non-integer arguments!");
4781 "getNoopOrSignExtend cannot truncate!");
4789 Type *SrcTy = V->getType();
4790 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4791 "Cannot noop or any extend with non-integer arguments!");
4793 "getNoopOrAnyExtend cannot truncate!");
4801 Type *SrcTy = V->getType();
4802 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4803 "Cannot truncate or noop with non-integer arguments!");
4805 "getTruncateOrNoop cannot extend!");
4813 const SCEV *PromotedLHS = LHS;
4814 const SCEV *PromotedRHS = RHS;
4834 assert(!
Ops.empty() &&
"At least one operand must be!");
4836 if (
Ops.size() == 1)
4840 Type *MaxType =
nullptr;
4841 for (
const auto *S :
Ops)
4846 assert(MaxType &&
"Failed to find maximum type!");
4850 for (
const auto *S :
Ops)
4859 if (!V->getType()->isPointerTy())
4864 V = AddRec->getStart();
4866 const SCEV *PtrOp =
nullptr;
4867 for (
const SCEV *AddOp :
Add->operands()) {
4868 if (AddOp->getType()->isPointerTy()) {
4869 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4873 assert(PtrOp &&
"Must have pointer op");
4885 for (
User *U :
I->users()) {
4887 if (Visited.
insert(UserInsn).second)
4901 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4902 bool IgnoreOtherLoops =
true) {
4905 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4907 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4912 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4914 SeenLoopVariantSCEVUnknown =
true;
4918 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4922 SeenOtherLoops =
true;
4926 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4928 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4931 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4932 : SCEVRewriteVisitor(SE),
L(
L) {}
4935 bool SeenLoopVariantSCEVUnknown =
false;
4936 bool SeenOtherLoops =
false;
4945 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4946 SCEVPostIncRewriter
Rewriter(L, SE);
4948 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4953 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4955 SeenLoopVariantSCEVUnknown =
true;
4959 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4963 SeenOtherLoops =
true;
4967 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4969 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4972 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4973 : SCEVRewriteVisitor(SE),
L(
L) {}
4976 bool SeenLoopVariantSCEVUnknown =
false;
4977 bool SeenOtherLoops =
false;
4983class SCEVBackedgeConditionFolder
4986 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4987 ScalarEvolution &SE) {
4988 bool IsPosBECond =
false;
4989 Value *BECond =
nullptr;
4990 if (BasicBlock *Latch =
L->getLoopLatch()) {
4994 "Both outgoing branches should not target same header!");
5001 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
5005 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5006 const SCEV *
Result = Expr;
5011 switch (
I->getOpcode()) {
5012 case Instruction::Select: {
5014 std::optional<const SCEV *> Res =
5015 compareWithBackedgeCondition(
SI->getCondition());
5023 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5034 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5035 bool IsPosBECond, ScalarEvolution &SE)
5036 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5037 IsPositiveBECond(IsPosBECond) {}
5039 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5043 Value *BackedgeCond =
nullptr;
5045 bool IsPositiveBECond;
5048std::optional<const SCEV *>
5049SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5054 if (BackedgeCond == IC)
5057 return std::nullopt;
5062 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5063 ScalarEvolution &SE) {
5069 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5076 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5083 bool isValid() {
return Valid; }
5086 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5087 : SCEVRewriteVisitor(SE),
L(
L) {}
5096ScalarEvolution::proveNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5100 using OBO = OverflowingBinaryOperator;
5108 const APInt &BECountAP = BECountMax->getAPInt();
5109 unsigned NoOverflowBitWidth =
5121 Instruction::Add, IncRange, OBO::NoSignedWrap);
5122 if (NSWRegion.contains(AddRecRange))
5131 Instruction::Add, IncRange, OBO::NoUnsignedWrap);
5132 if (NUWRegion.contains(AddRecRange))
5140ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5150 if (!SignedWrapViaInductionTried.insert(AR).second)
5175 AC.assumptions().empty())
5183 const SCEV *OverflowLimit =
5185 if (OverflowLimit &&
5193ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5203 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5229 AC.assumptions().empty())
5264 explicit BinaryOp(Operator *
Op)
5268 IsNSW = OBO->hasNoSignedWrap();
5269 IsNUW = OBO->hasNoUnsignedWrap();
5273 explicit BinaryOp(
unsigned Opcode,
Value *
LHS,
Value *
RHS,
bool IsNSW =
false,
5275 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5287 return std::nullopt;
5293 switch (
Op->getOpcode()) {
5294 case Instruction::Add:
5295 case Instruction::Sub:
5296 case Instruction::Mul:
5297 case Instruction::UDiv:
5298 case Instruction::URem:
5299 case Instruction::And:
5300 case Instruction::AShr:
5301 case Instruction::Shl:
5302 return BinaryOp(
Op);
5304 case Instruction::Or: {
5307 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5309 return BinaryOp(
Op);
5312 case Instruction::Xor:
5316 if (RHSC->getValue().isSignMask())
5317 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5319 if (V->getType()->isIntegerTy(1))
5320 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5321 return BinaryOp(
Op);
5323 case Instruction::LShr:
5332 if (SA->getValue().ult(
BitWidth)) {
5334 ConstantInt::get(SA->getContext(),
5336 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5339 return BinaryOp(
Op);
5341 case Instruction::ExtractValue: {
5343 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5351 bool Signed = WO->isSigned();
5354 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5359 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5370 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5371 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5373 return std::nullopt;
5399 if (
Op == SymbolicPHI)
5404 if (SourceBits != NewBits)
5422 if (!L || L->getHeader() != PN->
getParent())
5480std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5481ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5489 assert(L &&
"Expecting an integer loop header phi");
5494 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5495 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5496 Value *
V = PN->getIncomingValue(i);
5497 if (
L->contains(PN->getIncomingBlock(i))) {
5500 }
else if (BEValueV != V) {
5504 }
else if (!StartValueV) {
5506 }
else if (StartValueV != V) {
5507 StartValueV =
nullptr;
5511 if (!BEValueV || !StartValueV)
5512 return std::nullopt;
5514 const SCEV *BEValue =
getSCEV(BEValueV);
5521 return std::nullopt;
5525 unsigned FoundIndex =
Add->getNumOperands();
5526 Type *TruncTy =
nullptr;
5528 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5531 if (FoundIndex == e) {
5536 if (FoundIndex ==
Add->getNumOperands())
5537 return std::nullopt;
5541 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5542 if (i != FoundIndex)
5543 Ops.push_back(
Add->getOperand(i));
5549 return std::nullopt;
5602 const SCEV *StartVal =
getSCEV(StartValueV);
5603 const SCEV *PHISCEV =
5630 auto getExtendedExpr = [&](
const SCEV *Expr,
5631 bool CreateSignExtend) ->
const SCEV * {
5634 const SCEV *ExtendedExpr =
5637 return ExtendedExpr;
5645 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5646 const SCEV *ExtendedExpr) ->
bool {
5647 return Expr != ExtendedExpr &&
5651 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5652 if (PredIsKnownFalse(StartVal, StartExtended)) {
5654 return std::nullopt;
5659 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5660 if (PredIsKnownFalse(Accum, AccumExtended)) {
5662 return std::nullopt;
5665 auto AppendPredicate = [&](
const SCEV *Expr,
5666 const SCEV *ExtendedExpr) ->
void {
5667 if (Expr != ExtendedExpr &&
5675 AppendPredicate(StartVal, StartExtended);
5676 AppendPredicate(Accum, AccumExtended);
5684 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5685 std::make_pair(NewAR, Predicates);
5687 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5691std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5696 return std::nullopt;
5699 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5700 if (
I != PredicatedSCEVRewrites.end()) {
5701 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5704 if (Rewrite.first == SymbolicPHI)
5705 return std::nullopt;
5709 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5713 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5714 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5719 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5720 return std::nullopt;
5737 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5738 if (Expr1 != Expr2 &&
5739 !Preds->implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5740 !Preds->implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5757const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5759 Value *StartValueV) {
5762 assert(BEValueV && StartValueV);
5768 if (BO->Opcode != Instruction::Add)
5771 const SCEV *Accum =
nullptr;
5772 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5774 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5788 insertValueToMap(PN, PHISCEV);
5793 proveNoWrapViaConstantRanges(AR)));
5801 "Accum is defined outside L, but is not invariant?");
5802 if (isAddRecNeverPoison(BEInst, L))
5809const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5810 const Loop *
L = LI.getLoopFor(PN->
getParent());
5817 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5823 }
else if (BEValueV != V) {
5827 }
else if (!StartValueV) {
5829 }
else if (StartValueV != V) {
5830 StartValueV =
nullptr;
5834 if (!BEValueV || !StartValueV)
5837 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5838 "PHI node already processed?");
5842 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5847 insertValueToMap(PN, SymbolicName);
5851 const SCEV *BEValue =
getSCEV(BEValueV);
5861 unsigned FoundIndex =
Add->getNumOperands();
5862 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5863 if (
Add->getOperand(i) == SymbolicName)
5864 if (FoundIndex == e) {
5869 if (FoundIndex !=
Add->getNumOperands()) {
5872 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5873 if (i != FoundIndex)
5874 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5886 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5893 if (
GEP->getOperand(0) == PN) {
5894 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
5912 const SCEV *StartVal =
getSCEV(StartValueV);
5913 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5918 forgetMemoizedResults(SymbolicName);
5919 insertValueToMap(PN, PHISCEV);
5924 proveNoWrapViaConstantRanges(AR)));
5949 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5950 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5952 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5953 const SCEV *StartVal =
getSCEV(StartValueV);
5954 if (Start == StartVal) {
5958 forgetMemoizedResults(SymbolicName);
5959 insertValueToMap(PN, Shifted);
5969 eraseValueFromMap(PN);
5989 Use &LeftUse =
Merge->getOperandUse(0);
5990 Use &RightUse =
Merge->getOperandUse(1);
6007const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
6009 [&](
BasicBlock *BB) {
return DT.isReachableFromEntry(BB); };
6024 assert(IDom &&
"At least the entry block should dominate PN");
6033 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6049ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6050 BinaryOperator *CommonInst =
nullptr;
6061 CommonInst = IncomingInst;
6068 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6069 bool SCEVExprsIdentical =
6071 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6072 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6075const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6076 if (
const SCEV *S = createAddRecFromPHI(PN))
6086 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6089 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6098 struct FindClosure {
6099 const SCEV *OperandToFind;
6105 bool canRecurseInto(
SCEVTypes Kind)
const {
6108 return RootKind == Kind || NonSequentialRootKind == Kind ||
6113 : OperandToFind(OperandToFind), RootKind(RootKind),
6114 NonSequentialRootKind(
6118 bool follow(
const SCEV *S) {
6119 Found = S == OperandToFind;
6121 return !isDone() && canRecurseInto(S->
getSCEVType());
6124 bool isDone()
const {
return Found; }
6127 FindClosure FC(OperandToFind, RootKind);
6132std::optional<const SCEV *>
6133ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6143 switch (ICI->getPredicate()) {
6157 bool Signed = ICI->isSigned();
6158 const SCEV *LA =
getSCEV(TrueVal);
6166 if (LA == LS &&
RA == RS)
6168 if (LA == RS &&
RA == LS)
6171 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6172 if (
Op->getType()->isPointerTy()) {
6183 LS = CoerceOperand(LS);
6184 RS = CoerceOperand(RS);
6208 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6209 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6223 X = ZExt->getOperand();
6225 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6236 return std::nullopt;
6239static std::optional<const SCEV *>
6241 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6245 "Unexpected operands of a select.");
6257 return std::nullopt;
6272static std::optional<const SCEV *>
6276 return std::nullopt;
6279 const auto *SETrue = SE->
getSCEV(TrueVal);
6280 const auto *SEFalse = SE->
getSCEV(FalseVal);
6284const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6286 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6288 V->getType() ==
TrueVal->getType() &&
6289 "Types of select hands and of the result must match.");
6292 if (!
V->getType()->isIntegerTy(1))
6295 if (std::optional<const SCEV *> S =
6308 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6312 if (std::optional<const SCEV *> S =
6313 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6319 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6325 assert(
GEP->getSourceElementType()->isSized() &&
6326 "GEP source element type must be sized");
6329 for (
Value *Index :
GEP->indices())
6334APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6337 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6340 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6342 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6345 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6363 return GetShiftedByZeros(TZ);
6373 return GetShiftedByZeros(TZ);
6377 if (
M->hasNoUnsignedWrap()) {
6380 for (
const SCEV *Operand :
M->operands().drop_front())
6388 for (
const SCEV *Operand :
M->operands())
6390 return GetShiftedByZeros(TZ);
6395 if (
N->hasNoUnsignedWrap())
6396 return GetGCDMultiple(
N);
6399 for (
const SCEV *Operand :
N->operands().drop_front())
6401 return GetShiftedByZeros(TZ);
6418 CtxI = &*F.getEntryBlock().begin();
6424 .countMinTrailingZeros();
6425 return GetShiftedByZeros(Known);
6438 return getConstantMultipleImpl(S, CtxI);
6440 auto I = ConstantMultipleCache.find(S);
6441 if (
I != ConstantMultipleCache.end())
6444 APInt Result = getConstantMultipleImpl(S, CtxI);
6445 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6446 assert(InsertPair.second &&
"Should insert a new key");
6447 return InsertPair.first->second;
6464 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6467 if (std::optional<ConstantRange>
Range = CB->getRange())
6471 if (std::optional<ConstantRange>
Range =
A->getRange())
6474 return std::nullopt;
6481 UnsignedRanges.erase(AddRec);
6482 SignedRanges.erase(AddRec);
6483 ConstantMultipleCache.erase(AddRec);
6488getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6514 Value *Start, *Step;
6521 assert(L && L->getHeader() ==
P->getParent());
6534 case Instruction::AShr:
6535 case Instruction::LShr:
6536 case Instruction::Shl:
6551 KnownStep.getBitWidth() ==
BitWidth);
6554 auto MaxShiftAmt = KnownStep.getMaxValue();
6556 bool Overflow =
false;
6557 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6564 case Instruction::AShr: {
6572 if (KnownStart.isNonNegative())
6575 KnownStart.getMaxValue() + 1);
6576 if (KnownStart.isNegative())
6579 KnownEnd.getMaxValue() + 1);
6582 case Instruction::LShr: {
6591 KnownStart.getMaxValue() + 1);
6593 case Instruction::Shl: {
6597 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6598 return ConstantRange(KnownStart.getMinValue(),
6599 KnownEnd.getMaxValue() + 1);
6607ScalarEvolution::getRangeRefIter(
const SCEV *S,
6608 ScalarEvolution::RangeSignHint SignHint) {
6609 DenseMap<const SCEV *, ConstantRange> &Cache =
6610 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6613 SmallPtrSet<const SCEV *, 8> Seen;
6617 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6618 if (!Seen.
insert(Expr).second)
6651 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6652 const SCEV *
P = WorkList[
I];
6656 for (
const SCEV *
Op :
P->operands())
6662 if (!PendingPhiRangesIter.insert(
P).second)
6669 if (!WorkList.
empty()) {
6674 getRangeRef(
P, SignHint);
6678 PendingPhiRangesIter.erase(
P);
6682 return getRangeRef(S, SignHint, 0);
6689 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6690 DenseMap<const SCEV *, ConstantRange> &Cache =
6691 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6699 if (
I != Cache.
end())
6703 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6708 return getRangeRefIter(S, SignHint);
6711 ConstantRange ConservativeResult(
BitWidth,
true);
6712 using OBO = OverflowingBinaryOperator;
6716 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6720 ConservativeResult =
6727 ConservativeResult = ConstantRange(
6743 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6750 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6757 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6761 ConstantRange
X = getRangeRef(PtrToInt->
getOperand(), SignHint,
Depth + 1);
6762 return setRange(PtrToInt, SignHint,
X);
6766 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6767 unsigned WrapType = OBO::AnyWrap;
6768 if (
Add->hasNoSignedWrap())
6769 WrapType |= OBO::NoSignedWrap;
6770 if (
Add->hasNoUnsignedWrap())
6771 WrapType |= OBO::NoUnsignedWrap;
6773 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6775 return setRange(
Add, SignHint,
6776 ConservativeResult.intersectWith(
X, RangeType));
6780 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6782 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6783 return setRange(
Mul, SignHint,
6784 ConservativeResult.intersectWith(
X, RangeType));
6788 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6789 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6790 return setRange(UDiv, SignHint,
6791 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6799 if (!UnsignedMinValue.
isZero())
6800 ConservativeResult = ConservativeResult.intersectWith(
6801 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6810 bool AllNonNeg =
true;
6811 bool AllNonPos =
true;
6812 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6819 ConservativeResult = ConservativeResult.intersectWith(
6824 ConservativeResult = ConservativeResult.intersectWith(
6833 const SCEV *MaxBEScev =
6847 auto RangeFromAffine = getRangeForAffineAR(
6849 ConservativeResult =
6850 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6852 auto RangeFromFactoring = getRangeViaFactoring(
6854 ConservativeResult =
6855 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6861 const SCEV *SymbolicMaxBECount =
6866 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6867 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6868 ConservativeResult =
6869 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6874 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6884 ID = Intrinsic::umax;
6887 ID = Intrinsic::smax;
6891 ID = Intrinsic::umin;
6894 ID = Intrinsic::smin;
6901 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6902 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6904 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6905 return setRange(S, SignHint,
6906 ConservativeResult.intersectWith(
X, RangeType));
6915 ConservativeResult =
6916 ConservativeResult.intersectWith(*MDRange, RangeType);
6921 auto CR = getRangeForUnknownRecurrence(U);
6922 ConservativeResult = ConservativeResult.intersectWith(CR);
6933 if (
U->getType()->isPointerTy()) {
6936 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
6937 int ptrIdxDiff = ptrSize -
BitWidth;
6938 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
6951 ConservativeResult = ConservativeResult.intersectWith(
6955 ConservativeResult = ConservativeResult.intersectWith(
6960 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6963 bool CanBeNull, CanBeFreed;
6964 uint64_t DerefBytes =
6965 V->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed);
6975 uint64_t
Align =
U->getValue()->getPointerAlignment(DL).value();
6976 uint64_t Rem = MaxVal.
urem(Align);
6981 ConservativeResult = ConservativeResult.intersectWith(
6989 if (PendingPhiRanges.insert(Phi).second) {
6990 ConstantRange RangeFromOps(
BitWidth,
false);
6992 for (
const auto &
Op :
Phi->operands()) {
6994 RangeFromOps = RangeFromOps.unionWith(OpRange);
6996 if (RangeFromOps.isFullSet())
6999 ConservativeResult =
7000 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7001 bool Erased = PendingPhiRanges.erase(Phi);
7002 assert(Erased &&
"Failed to erase Phi properly?");
7009 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7011 ConservativeResult = ConservativeResult.difference(Disallowed);
7014 return setRange(U, SignHint, std::move(ConservativeResult));
7020 return setRange(S, SignHint, std::move(ConservativeResult));
7029 const APInt &MaxBECount,
7036 if (Step == 0 || MaxBECount == 0)
7043 return ConstantRange::getFull(
BitWidth);
7059 return ConstantRange::getFull(
BitWidth);
7071 APInt MovedBoundary = Descending ? (StartLower - std::move(
Offset))
7072 : (StartUpper + std::move(
Offset));
7077 if (StartRange.
contains(MovedBoundary))
7078 return ConstantRange::getFull(
BitWidth);
7081 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7083 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7092 const APInt &MaxBECount) {
7096 "mismatched bit widths");
7105 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7107 StartSRange, MaxBECount,
7119ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7121 ScalarEvolution::RangeSignHint SignHint) {
7122 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7124 "This only works for non-self-wrapping AddRecs!");
7125 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7129 return ConstantRange::getFull(
BitWidth);
7137 return ConstantRange::getFull(
BitWidth);
7141 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7143 MaxItersWithoutWrap))
7144 return ConstantRange::getFull(
BitWidth);
7165 ConstantRange StartRange = getRangeRef(Start, SignHint);
7166 ConstantRange EndRange = getRangeRef(End, SignHint);
7167 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7171 return RangeBetween;
7176 return ConstantRange::getFull(
BitWidth);
7179 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7180 return RangeBetween;
7182 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7183 return RangeBetween;
7184 return ConstantRange::getFull(
BitWidth);
7189 const APInt &MaxBECount) {
7196 "mismatched bit widths");
7198 struct SelectPattern {
7199 Value *Condition =
nullptr;
7203 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7205 std::optional<unsigned> CastOp;
7219 CastOp = SCast->getSCEVType();
7220 S = SCast->getOperand();
7223 using namespace llvm::PatternMatch;
7230 Condition =
nullptr;
7262 bool isRecognized() {
return Condition !=
nullptr; }
7265 SelectPattern StartPattern(*
this,
BitWidth, Start);
7266 if (!StartPattern.isRecognized())
7267 return ConstantRange::getFull(
BitWidth);
7269 SelectPattern StepPattern(*
this,
BitWidth, Step);
7270 if (!StepPattern.isRecognized())
7271 return ConstantRange::getFull(
BitWidth);
7273 if (StartPattern.Condition != StepPattern.Condition) {
7277 return ConstantRange::getFull(
BitWidth);
7288 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7289 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7290 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7291 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7293 ConstantRange TrueRange =
7294 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount);
7295 ConstantRange FalseRange =
7296 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount);
7318ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7332 SmallPtrSet<const SCEV *, 16> Visited;
7334 auto pushOp = [&](
const SCEV *S) {
7335 if (!Visited.
insert(S).second)
7338 if (Visited.
size() > 30) {
7345 for (
const auto *S :
Ops)
7349 while (!Worklist.
empty()) {
7351 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7352 if (!Bound || DT.dominates(Bound, DefI))
7359 return Bound ? Bound : &*F.getEntryBlock().begin();
7365 return getDefiningScopeBound(
Ops, Discard);
7368bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7370 if (
A->getParent() ==
B->getParent() &&
7375 auto *BLoop = LI.getLoopFor(
B->getParent());
7376 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7377 BLoop->getLoopPreheader() ==
A->getParent() &&
7379 A->getParent()->end()) &&
7386bool ScalarEvolution::isGuaranteedNotToBePoison(
const SCEV *
Op) {
7387 SCEVPoisonCollector PC(
true);
7389 return PC.MaybePoison.empty();
7392bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7398 return M && (!
isKnownNonZero(Op1) || !isGuaranteedNotToBePoison(Op1));
7402bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7419 for (
const Use &
Op :
I->operands()) {
7425 auto *DefI = getDefiningScopeBound(SCEVOps);
7426 return isGuaranteedToTransferExecutionTo(DefI,
I);
7429bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7431 if (isSCEVExprNeverPoison(
I))
7442 auto *ExitingBB =
L->getExitingBlock();
7446 SmallPtrSet<const Value *, 16> KnownPoison;
7455 while (!Worklist.
empty()) {
7458 for (
const Use &U :
Poison->uses()) {
7461 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7465 if (KnownPoison.
insert(PoisonUser).second)
7473ScalarEvolution::LoopProperties
7474ScalarEvolution::getLoopProperties(
const Loop *L) {
7475 using LoopProperties = ScalarEvolution::LoopProperties;
7477 auto Itr = LoopPropertiesCache.find(L);
7478 if (Itr == LoopPropertiesCache.end()) {
7481 return !
SI->isSimple();
7491 return I->mayWriteToMemory();
7494 LoopProperties LP = {
true,
7497 for (
auto *BB :
L->getBlocks())
7498 for (
auto &
I : *BB) {
7500 LP.HasNoAbnormalExits =
false;
7501 if (HasSideEffects(&
I))
7502 LP.HasNoSideEffects =
false;
7503 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7507 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7508 assert(InsertPair.second &&
"We just checked!");
7509 Itr = InsertPair.first;
7522const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7528 Stack.emplace_back(V,
true);
7529 Stack.emplace_back(V,
false);
7530 while (!Stack.empty()) {
7531 auto E = Stack.pop_back_val();
7532 Value *CurV = E.getPointer();
7538 const SCEV *CreatedSCEV =
nullptr;
7541 CreatedSCEV = createSCEV(CurV);
7546 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7550 insertValueToMap(CurV, CreatedSCEV);
7554 Stack.emplace_back(CurV,
true);
7556 Stack.emplace_back(
Op,
false);
7573 if (!DT.isReachableFromEntry(
I->getParent()))
7586 switch (BO->Opcode) {
7587 case Instruction::Add:
7588 case Instruction::Mul: {
7595 Ops.push_back(BO->
Op);
7599 Ops.push_back(BO->RHS);
7603 (BO->Opcode == Instruction::Add &&
7604 (NewBO->Opcode != Instruction::Add &&
7605 NewBO->Opcode != Instruction::Sub)) ||
7606 (BO->Opcode == Instruction::Mul &&
7607 NewBO->Opcode != Instruction::Mul)) {
7608 Ops.push_back(BO->LHS);
7613 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7616 Ops.push_back(BO->LHS);
7624 case Instruction::Sub:
7625 case Instruction::UDiv:
7626 case Instruction::URem:
7628 case Instruction::AShr:
7629 case Instruction::Shl:
7630 case Instruction::Xor:
7634 case Instruction::And:
7635 case Instruction::Or:
7639 case Instruction::LShr:
7646 Ops.push_back(BO->LHS);
7647 Ops.push_back(BO->RHS);
7651 switch (
U->getOpcode()) {
7652 case Instruction::Trunc:
7653 case Instruction::ZExt:
7654 case Instruction::SExt:
7655 case Instruction::PtrToInt:
7656 Ops.push_back(
U->getOperand(0));
7659 case Instruction::BitCast:
7661 Ops.push_back(
U->getOperand(0));
7666 case Instruction::SDiv:
7667 case Instruction::SRem:
7668 Ops.push_back(
U->getOperand(0));
7669 Ops.push_back(
U->getOperand(1));
7672 case Instruction::GetElementPtr:
7674 "GEP source element type must be sized");
7678 case Instruction::IntToPtr:
7681 case Instruction::PHI:
7685 case Instruction::Select: {
7687 auto CanSimplifyToUnknown = [
this,
U]() {
7705 if (CanSimplifyToUnknown())
7712 case Instruction::Call:
7713 case Instruction::Invoke:
7720 switch (
II->getIntrinsicID()) {
7721 case Intrinsic::abs:
7722 Ops.push_back(
II->getArgOperand(0));
7724 case Intrinsic::umax:
7725 case Intrinsic::umin:
7726 case Intrinsic::smax:
7727 case Intrinsic::smin:
7728 case Intrinsic::usub_sat:
7729 case Intrinsic::uadd_sat:
7730 Ops.push_back(
II->getArgOperand(0));
7731 Ops.push_back(
II->getArgOperand(1));
7733 case Intrinsic::start_loop_iterations:
7734 case Intrinsic::annotation:
7735 case Intrinsic::ptr_annotation:
7736 Ops.push_back(
II->getArgOperand(0));
7748const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7757 if (!DT.isReachableFromEntry(
I->getParent()))
7772 switch (BO->Opcode) {
7773 case Instruction::Add: {
7799 if (BO->Opcode == Instruction::Sub)
7807 if (BO->Opcode == Instruction::Sub)
7814 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7815 NewBO->Opcode != Instruction::Sub)) {
7825 case Instruction::Mul: {
7846 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7855 case Instruction::UDiv:
7859 case Instruction::URem:
7863 case Instruction::Sub: {
7866 Flags = getNoWrapFlagsFromUB(BO->
Op);
7871 case Instruction::And:
7877 if (CI->isMinusOne())
7879 const APInt &
A = CI->getValue();
7885 unsigned LZ =
A.countl_zero();
7886 unsigned TZ =
A.countr_zero();
7891 APInt EffectiveMask =
7893 if ((LZ != 0 || TZ != 0) && !((~
A & ~Known.
Zero) & EffectiveMask)) {
7896 const SCEV *ShiftedLHS =
nullptr;
7900 unsigned MulZeros = OpC->getAPInt().countr_zero();
7901 unsigned GCD = std::min(MulZeros, TZ);
7906 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
7928 case Instruction::Or:
7937 case Instruction::Xor:
7940 if (CI->isMinusOne())
7949 if (LBO->getOpcode() == Instruction::And &&
7950 LCI->getValue() == CI->getValue())
7951 if (
const SCEVZeroExtendExpr *Z =
7954 const SCEV *Z0 =
Z->getOperand();
7961 if (CI->getValue().isMask(Z0TySize))
7967 APInt Trunc = CI->getValue().trunc(Z0TySize);
7976 case Instruction::Shl:
7994 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8002 ConstantInt *
X = ConstantInt::get(
8008 case Instruction::AShr:
8030 const SCEV *AddTruncateExpr =
nullptr;
8031 ConstantInt *ShlAmtCI =
nullptr;
8032 const SCEV *AddConstant =
nullptr;
8034 if (L &&
L->getOpcode() == Instruction::Add) {
8042 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8049 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8057 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8062 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8067 if (AddTruncateExpr && ShlAmtCI) {
8079 const APInt &ShlAmt = ShlAmtCI->
getValue();
8083 const SCEV *CompositeExpr =
8085 if (
L->getOpcode() != Instruction::Shl)
8086 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8095 switch (
U->getOpcode()) {
8096 case Instruction::Trunc:
8099 case Instruction::ZExt:
8102 case Instruction::SExt:
8112 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8113 Type *Ty =
U->getType();
8121 case Instruction::BitCast:
8127 case Instruction::PtrToInt: {
8130 Type *DstIntTy =
U->getType();
8138 case Instruction::IntToPtr:
8142 case Instruction::SDiv:
8149 case Instruction::SRem:
8156 case Instruction::GetElementPtr:
8159 case Instruction::PHI:
8162 case Instruction::Select:
8163 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8166 case Instruction::Call:
8167 case Instruction::Invoke:
8172 switch (
II->getIntrinsicID()) {
8173 case Intrinsic::abs:
8177 case Intrinsic::umax:
8181 case Intrinsic::umin:
8185 case Intrinsic::smax:
8189 case Intrinsic::smin:
8193 case Intrinsic::usub_sat: {
8194 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8195 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8199 case Intrinsic::uadd_sat: {
8200 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8201 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8205 case Intrinsic::start_loop_iterations:
8206 case Intrinsic::annotation:
8207 case Intrinsic::ptr_annotation:
8211 case Intrinsic::vscale:
8231 auto *ExitCountType = ExitCount->
getType();
8232 assert(ExitCountType->isIntegerTy());
8234 1 + ExitCountType->getScalarSizeInBits());
8247 auto CanAddOneWithoutOverflow = [&]() {
8249 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8260 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8290 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8291 assert(L->isLoopExiting(ExitingBlock) &&
8292 "Exiting block must actually branch out of the loop!");
8301 const auto *MaxExitCount =
8309 L->getExitingBlocks(ExitingBlocks);
8311 std::optional<unsigned> Res;
8312 for (
auto *ExitingBB : ExitingBlocks) {
8316 Res = std::gcd(*Res, Multiple);
8318 return Res.value_or(1);
8322 const SCEV *ExitCount) {
8352 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8353 assert(L->isLoopExiting(ExitingBlock) &&
8354 "Exiting block must actually branch out of the loop!");
8364 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8366 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8368 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8378 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8381 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8384 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8392 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8399 return getBackedgeTakenInfo(L).getExact(L,
this);
8401 return getBackedgeTakenInfo(L).getConstantMax(
this);
8403 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8410 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8415 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8419 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8429 for (
PHINode &PN : Header->phis())
8430 if (Visited.
insert(&PN).second)
8434ScalarEvolution::BackedgeTakenInfo &
8435ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8436 auto &BTI = getBackedgeTakenInfo(L);
8437 if (BTI.hasFullInfo())
8440 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8443 return Pair.first->second;
8445 BackedgeTakenInfo
Result =
8446 computeBackedgeTakenCount(L,
true);
8448 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8451ScalarEvolution::BackedgeTakenInfo &
8452ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8458 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8459 BackedgeTakenCounts.try_emplace(L);
8461 return Pair.first->second;
8466 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8473 if (
Result.hasAnyInfo()) {
8476 auto LoopUsersIt = LoopUsers.find(L);
8477 if (LoopUsersIt != LoopUsers.end())
8479 forgetMemoizedResults(ToForget);
8482 for (PHINode &PN :
L->getHeader()->phis())
8483 ConstantEvolutionLoopExitValue.erase(&PN);
8491 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8500 BackedgeTakenCounts.clear();
8501 PredicatedBackedgeTakenCounts.clear();
8502 BECountUsers.clear();
8503 LoopPropertiesCache.clear();
8504 ConstantEvolutionLoopExitValue.clear();
8505 ValueExprMap.clear();
8506 ValuesAtScopes.clear();
8507 ValuesAtScopesUsers.clear();
8508 LoopDispositions.clear();
8509 BlockDispositions.clear();
8510 UnsignedRanges.clear();
8511 SignedRanges.clear();
8512 ExprValueMap.clear();
8514 ConstantMultipleCache.clear();
8515 PredicatedSCEVRewrites.clear();
8517 FoldCacheUser.clear();
8519void ScalarEvolution::visitAndClearUsers(
8523 while (!Worklist.
empty()) {
8530 if (It != ValueExprMap.
end()) {
8531 eraseValueFromMap(It->first);
8534 ConstantEvolutionLoopExitValue.erase(PN);
8548 while (!LoopWorklist.
empty()) {
8552 forgetBackedgeTakenCounts(CurrL,
false);
8553 forgetBackedgeTakenCounts(CurrL,
true);
8556 for (
auto I = PredicatedSCEVRewrites.begin();
8557 I != PredicatedSCEVRewrites.end();) {
8558 std::pair<const SCEV *, const Loop *> Entry =
I->first;
8559 if (Entry.second == CurrL)
8560 PredicatedSCEVRewrites.erase(
I++);
8565 auto LoopUsersItr = LoopUsers.find(CurrL);
8566 if (LoopUsersItr != LoopUsers.end())
8571 visitAndClearUsers(Worklist, Visited, ToForget);
8573 LoopPropertiesCache.erase(CurrL);
8576 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8578 forgetMemoizedResults(ToForget);
8595 visitAndClearUsers(Worklist, Visited, ToForget);
8597 forgetMemoizedResults(ToForget);
8609 struct InvalidationRootCollector {
8613 InvalidationRootCollector(
Loop *L) : L(L) {}
8615 bool follow(
const SCEV *S) {
8621 if (L->contains(AddRec->
getLoop()))
8626 bool isDone()
const {
return false; }
8629 InvalidationRootCollector
C(L);
8631 forgetMemoizedResults(
C.Roots);
8644 BlockDispositions.clear();
8645 LoopDispositions.clear();
8662 while (!Worklist.
empty()) {
8664 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8665 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8666 if (!LoopDispoRemoved && !BlockDispoRemoved)
8668 auto Users = SCEVUsers.find(Curr);
8669 if (
Users != SCEVUsers.end())
8682const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8686 if (!isComplete() || ExitNotTaken.
empty())
8697 for (
const auto &ENT : ExitNotTaken) {
8698 const SCEV *BECount = ENT.ExactNotTaken;
8701 "We should only have known counts for exiting blocks that dominate "
8704 Ops.push_back(BECount);
8709 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8710 "Predicate should be always true!");
8719const ScalarEvolution::ExitNotTakenInfo *
8720ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8721 const BasicBlock *ExitingBlock,
8722 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8723 for (
const auto &ENT : ExitNotTaken)
8724 if (ENT.ExitingBlock == ExitingBlock) {
8725 if (ENT.hasAlwaysTruePredicate())
8727 else if (Predicates) {
8737const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8739 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8740 if (!getConstantMax())
8743 for (
const auto &ENT : ExitNotTaken)
8744 if (!ENT.hasAlwaysTruePredicate()) {
8752 "No point in having a non-constant max backedge taken count!");
8753 return getConstantMax();
8756const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8758 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8766 for (
const auto &ENT : ExitNotTaken) {
8767 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8770 "We should only have known counts for exiting blocks that "
8776 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8777 "Predicate should be always true!");
8780 if (ExitCounts.
empty())
8789bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8791 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8792 return !ENT.hasAlwaysTruePredicate();
8794 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8810 this->ExactNotTaken = E = ConstantMaxNotTaken;
8811 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8816 "Exact is not allowed to be less precise than Constant Max");
8819 "Exact is not allowed to be less precise than Symbolic Max");
8822 "Symbolic Max is not allowed to be less precise than Constant Max");
8825 "No point in having a non-constant max backedge taken count!");
8827 for (
const auto PredList : PredLists)
8828 for (
const auto *
P : PredList) {
8836 "Backedge count should be int");
8839 "Max backedge count should be int");
8852ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8854 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8855 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8856 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8858 ExitNotTaken.reserve(ExitCounts.
size());
8859 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8860 std::back_inserter(ExitNotTaken),
8861 [&](
const EdgeExitInfo &EEI) {
8862 BasicBlock *ExitBB = EEI.first;
8863 const ExitLimit &EL = EEI.second;
8864 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
8865 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
8870 "No point in having a non-constant max backedge taken count!");
8874ScalarEvolution::BackedgeTakenInfo
8875ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
8876 bool AllowPredicates) {
8878 L->getExitingBlocks(ExitingBlocks);
8880 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8883 bool CouldComputeBECount =
true;
8885 const SCEV *MustExitMaxBECount =
nullptr;
8886 const SCEV *MayExitMaxBECount =
nullptr;
8887 bool MustExitMaxOrZero =
false;
8888 bool IsOnlyExit = ExitingBlocks.
size() == 1;
8900 if (ExitIfTrue == CI->
isZero())
8904 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
8906 assert((AllowPredicates || EL.Predicates.empty()) &&
8907 "Predicated exit limit when predicates are not allowed!");
8912 ++NumExitCountsComputed;
8916 CouldComputeBECount =
false;
8923 "Exact is known but symbolic isn't?");
8924 ++NumExitCountsNotComputed;
8939 DT.dominates(ExitBB, Latch)) {
8940 if (!MustExitMaxBECount) {
8941 MustExitMaxBECount = EL.ConstantMaxNotTaken;
8942 MustExitMaxOrZero = EL.MaxOrZero;
8945 EL.ConstantMaxNotTaken);
8949 MayExitMaxBECount = EL.ConstantMaxNotTaken;
8952 EL.ConstantMaxNotTaken);
8956 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
8960 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
8966 for (
const auto &Pair : ExitCounts) {
8968 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
8970 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
8971 {
L, AllowPredicates});
8973 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
8974 MaxBECount, MaxOrZero);
8977ScalarEvolution::ExitLimit
8978ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
8979 bool IsOnlyExit,
bool AllowPredicates) {
8980 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
8984 if (!Latch || !DT.dominates(ExitingBlock, Latch))
8992 "It should have one successor in loop and one exit block!");
9003 if (!
L->contains(SBB)) {
9008 assert(Exit &&
"Exiting block must have at least one exit");
9009 return computeExitLimitFromSingleExitSwitch(
9010 L, SI, Exit, IsOnlyExit);
9017 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9018 bool AllowPredicates) {
9019 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9020 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9021 ControlsOnlyExit, AllowPredicates);
9024std::optional<ScalarEvolution::ExitLimit>
9025ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9026 bool ExitIfTrue,
bool ControlsOnlyExit,
9027 bool AllowPredicates) {
9029 (void)this->ExitIfTrue;
9030 (void)this->AllowPredicates;
9032 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9033 this->AllowPredicates == AllowPredicates &&
9034 "Variance in assumed invariant key components!");
9035 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9036 if (Itr == TripCountMap.end())
9037 return std::nullopt;
9041void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9043 bool ControlsOnlyExit,
9044 bool AllowPredicates,
9046 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9047 this->AllowPredicates == AllowPredicates &&
9048 "Variance in assumed invariant key components!");
9050 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9051 assert(InsertResult.second &&
"Expected successful insertion!");
9056ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9057 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9058 bool ControlsOnlyExit,
bool AllowPredicates) {
9060 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9064 ExitLimit EL = computeExitLimitFromCondImpl(
9065 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9066 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9070ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9071 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9072 bool ControlsOnlyExit,
bool AllowPredicates) {
9074 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9075 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates))
9076 return *LimitFromBinOp;
9082 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9083 if (EL.hasFullInfo() || !AllowPredicates)
9087 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9107 const WithOverflowInst *WO;
9122 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9123 ControlsOnlyExit, AllowPredicates);
9124 if (EL.hasAnyInfo())
9129 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9132std::optional<ScalarEvolution::ExitLimit>
9133ScalarEvolution::computeExitLimitFromCondFromBinOp(
9134 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9135 bool ControlsOnlyExit,
bool AllowPredicates) {
9144 return std::nullopt;
9149 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9150 ExitLimit EL0 = computeExitLimitFromCondCached(
9151 Cache, L, Op0, ExitIfTrue, ControlsOnlyExit && !EitherMayExit,
9153 ExitLimit EL1 = computeExitLimitFromCondCached(
9154 Cache, L, Op1, ExitIfTrue, ControlsOnlyExit && !EitherMayExit,
9158 const Constant *NeutralElement = ConstantInt::get(ExitCond->
getType(), IsAnd);
9160 return Op1 == NeutralElement ? EL0 : EL1;
9162 return Op0 == NeutralElement ? EL1 : EL0;
9167 if (EitherMayExit) {
9177 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9179 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9182 EL1.ConstantMaxNotTaken);
9184 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9186 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9189 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9193 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9194 BECount = EL0.ExactNotTaken;
9207 SymbolicMaxBECount =
9209 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9213ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9214 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9215 bool AllowPredicates) {
9227 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9229 if (EL.hasAnyInfo())
9232 auto *ExhaustiveCount =
9233 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9236 return ExhaustiveCount;
9238 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9241ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9242 const Loop *L, CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
9243 bool ControlsOnlyExit,
bool AllowPredicates) {
9268 ConstantRange CompRange =
9284 auto *InnerLHS =
LHS;
9286 InnerLHS = ZExt->getOperand();
9333 if (EL.hasAnyInfo())
9350 if (EL.hasAnyInfo())
return EL;
9382 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9384 if (EL.hasAnyInfo())
9400 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9402 if (EL.hasAnyInfo())
9413ScalarEvolution::ExitLimit
9414ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9416 BasicBlock *ExitingBlock,
9417 bool ControlsOnlyExit) {
9418 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9421 if (
Switch->getDefaultDest() == ExitingBlock)
9425 "Default case must not exit the loop!");
9431 if (EL.hasAnyInfo())
9443 "Evaluation of SCEV at constant didn't fold correctly?");
9447ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9457 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9463 auto MatchPositiveShift =
9466 using namespace PatternMatch;
9468 ConstantInt *ShiftAmt;
9470 OutOpCode = Instruction::LShr;
9472 OutOpCode = Instruction::AShr;
9474 OutOpCode = Instruction::Shl;
9489 auto MatchShiftRecurrence =
9491 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9506 if (MatchPositiveShift(
LHS, V, OpC)) {
9507 PostShiftOpCode = OpC;
9513 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9516 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9522 MatchPositiveShift(BEValue, OpLHS, OpCodeOut) &&
9529 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9534 if (!MatchShiftRecurrence(
LHS, PN, OpCode))
9546 ConstantInt *StableValue =
nullptr;
9551 case Instruction::AShr: {
9559 StableValue = ConstantInt::get(Ty, 0);
9561 StableValue = ConstantInt::get(Ty, -1,
true);
9567 case Instruction::LShr:
9568 case Instruction::Shl:
9578 "Otherwise cannot be an operand to a branch instruction");
9580 if (
Result->isZeroValue()) {
9582 const SCEV *UpperBound =
9599 if (
const Function *
F = CI->getCalledFunction())
9608 if (!L->contains(
I))
return false;
9613 return L->getHeader() ==
I->getParent();
9689 if (!
I)
return nullptr;
9702 std::vector<Constant*> Operands(
I->getNumOperands());
9704 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9708 if (!Operands[i])
return nullptr;
9713 if (!
C)
return nullptr;
9735 if (IncomingVal != CurrentVal) {
9738 IncomingVal = CurrentVal;
9750ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9753 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9762 DenseMap<Instruction *, Constant *> CurrentIterVals;
9764 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9770 for (PHINode &
PHI : Header->phis()) {
9772 CurrentIterVals[&
PHI] = StartCST;
9774 if (!CurrentIterVals.
count(PN))
9775 return RetVal =
nullptr;
9781 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9784 unsigned IterationNum = 0;
9786 for (; ; ++IterationNum) {
9787 if (IterationNum == NumIterations)
9788 return RetVal = CurrentIterVals[PN];
9792 DenseMap<Instruction *, Constant *> NextIterVals;
9797 NextIterVals[PN] = NextPHI;
9799 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9805 for (
const auto &
I : CurrentIterVals) {
9807 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9812 for (
const auto &
I : PHIsToCompute) {
9813 PHINode *
PHI =
I.first;
9816 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9819 if (NextPHI !=
I.second)
9820 StoppedEvolving =
false;
9825 if (StoppedEvolving)
9826 return RetVal = CurrentIterVals[PN];
9828 CurrentIterVals.swap(NextIterVals);
9832const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
9842 DenseMap<Instruction *, Constant *> CurrentIterVals;
9844 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9847 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
9849 for (PHINode &
PHI : Header->phis()) {
9851 CurrentIterVals[&
PHI] = StartCST;
9853 if (!CurrentIterVals.
count(PN))
9861 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
9868 if (CondVal->getValue() == uint64_t(ExitWhen)) {
9869 ++NumBruteForceTripCountsComputed;
9874 DenseMap<Instruction *, Constant *> NextIterVals;
9880 for (
const auto &
I : CurrentIterVals) {
9882 if (!
PHI ||
PHI->getParent() != Header)
continue;
9885 for (PHINode *
PHI : PHIsToCompute) {
9887 if (NextPHI)
continue;
9889 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9892 CurrentIterVals.
swap(NextIterVals);
9903 for (
auto &LS : Values)
9905 return LS.second ? LS.second : V;
9910 const SCEV *
C = computeSCEVAtScope(V, L);
9911 for (
auto &LS :
reverse(ValuesAtScopes[V]))
9912 if (LS.first == L) {
9915 ValuesAtScopesUsers[
C].push_back({L, V});
9926 switch (V->getSCEVType()) {
9959 assert(!
C->getType()->isPointerTy() &&
9960 "Can only have one pointer, and it must be last");
9987ScalarEvolution::getWithOperands(
const SCEV *S,
9988 SmallVectorImpl<const SCEV *> &NewOps) {
10022const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10023 switch (
V->getSCEVType()) {
10034 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10045 for (++i; i !=
e; ++i)
10089 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10091 if (OpAtScope !=
Ops[i]) {
10099 for (++i; i !=
e; ++i) {
10104 return getWithOperands(V, NewOps);
10119 const Loop *CurrLoop = this->LI[
I->getParent()];
10130 if (BackedgeTakenCount->
isZero()) {
10131 Value *InitValue =
nullptr;
10132 bool MultipleInitValues =
false;
10138 MultipleInitValues =
true;
10143 if (!MultipleInitValues && InitValue)
10152 unsigned InLoopPred =
10163 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10178 Operands.
reserve(
I->getNumOperands());
10179 bool MadeImprovement =
false;
10194 MadeImprovement |= OrigV != OpV;
10199 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10204 if (!MadeImprovement)
10225const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10227 return stripInjectiveFunctions(ZExt->getOperand());
10229 return stripInjectiveFunctions(SExt->getOperand());
10247 assert(
A != 0 &&
"A must be non-zero.");
10263 if (MinTZ < Mult2 && L->getLoopPredecessor())
10265 if (MinTZ < Mult2) {
10288 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10308static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10314 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10315 << *AddRec <<
'\n');
10318 if (!LC || !MC || !
NC) {
10319 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10320 return std::nullopt;
10326 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10334 N =
N.sext(NewWidth);
10335 M = M.sext(NewWidth);
10336 L = L.sext(NewWidth);
10353 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10354 <<
", multiplied by " <<
T <<
'\n');
10363 std::optional<APInt>
Y) {
10365 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10368 return XW.
slt(YW) ? *
X : *
Y;
10371 return std::nullopt;
10372 return X ? *
X : *
Y;
10389 return std::nullopt;
10390 unsigned W =
X->getBitWidth();
10410static std::optional<APInt>
10416 return std::nullopt;
10419 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10420 std::optional<APInt>
X =
10423 return std::nullopt;
10428 return std::nullopt;
10443static std::optional<APInt>
10447 "Starting value of addrec should be 0");
10448 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10449 <<
Range <<
", addrec " << *AddRec <<
'\n');
10453 "Addrec's initial value should be in range");
10459 return std::nullopt;
10469 auto SolveForBoundary =
10470 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10473 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10474 << Bound <<
" (before multiplying by " << M <<
")\n");
10477 std::optional<APInt> SO;
10480 "signed overflow\n");
10484 "unsigned overflow\n");
10485 std::optional<APInt> UO =
10488 auto LeavesRange = [&] (
const APInt &
X) {
10505 return {std::nullopt,
false};
10510 if (LeavesRange(*Min))
10511 return { Min,
true };
10512 std::optional<APInt> Max = Min == SO ? UO : SO;
10513 if (LeavesRange(*Max))
10514 return { Max,
true };
10517 return {std::nullopt,
true};
10524 auto SL = SolveForBoundary(
Lower);
10525 auto SU = SolveForBoundary(
Upper);
10528 if (!SL.second || !SU.second)
10529 return std::nullopt;
10572ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10574 bool ControlsOnlyExit,
10575 bool AllowPredicates) {
10586 if (
C->getValue()->isZero())
return C;
10590 const SCEVAddRecExpr *AddRec =
10593 if (!AddRec && AllowPredicates)
10599 if (!AddRec || AddRec->
getLoop() != L)
10610 return ExitLimit(R, R, R,
false, Predicates);
10668 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10694 const SCEV *
Exact =
10702 const SCEV *SymbolicMax =
10704 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10713 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10721 return ExitLimit(
E, M, S,
false, Predicates);
10724ScalarEvolution::ExitLimit
10725ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10733 if (!
C->getValue()->isZero())
10743std::pair<const BasicBlock *, const BasicBlock *>
10744ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10755 if (
const Loop *L = LI.getLoopFor(BB))
10756 return {
L->getLoopPredecessor(),
L->getHeader()};
10758 return {
nullptr, BB};
10767 if (
A ==
B)
return true;
10782 if (ComputesEqualValues(AI, BI))
10790 const SCEV *Op0, *Op1;
10809 auto TrivialCase = [&](
bool TriviallyTrue) {
10818 const SCEV *NewLHS, *NewRHS;
10842 return TrivialCase(
false);
10843 return TrivialCase(
true);
10866 const APInt &
RA = RC->getAPInt();
10868 bool SimplifiedByConstantRange =
false;
10873 return TrivialCase(
true);
10875 return TrivialCase(
false);
10884 Changed = SimplifiedByConstantRange =
true;
10888 if (!SimplifiedByConstantRange) {
10905 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
10911 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
10917 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
10923 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
10935 return TrivialCase(
true);
10937 return TrivialCase(
false);
11042 auto NonRecursive = [
this, OrNegative](
const SCEV *S) {
11044 return C->getAPInt().isPowerOf2() ||
11045 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11048 return isa<SCEVVScale>(S) && F.hasFnAttribute(Attribute::VScaleRange);
11051 if (NonRecursive(S))
11077 APInt C = Cst->getAPInt();
11078 return C.urem(M) == 0;
11086 const SCEV *SmodM =
11101 for (
auto *
A : Assumptions)
11102 if (
A->implies(
P, *
this))
11110std::pair<const SCEV *, const SCEV *>
11113 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11115 return { Start, Start };
11117 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11126 getUsedLoops(LHS, LoopsUsed);
11127 getUsedLoops(RHS, LoopsUsed);
11129 if (LoopsUsed.
empty())
11134 for (
const auto *L1 : LoopsUsed)
11135 for (
const auto *L2 : LoopsUsed)
11136 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11137 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11138 "Domination relationship is not a linear order");
11168 SplitRHS.second) &&
11180 if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
11184 return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11194 return std::nullopt;
11209 if (KnownWithoutContext)
11210 return KnownWithoutContext;
11217 return std::nullopt;
11223 const Loop *L = LHS->getLoop();
11228std::optional<ScalarEvolution::MonotonicPredicateType>
11231 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11237 auto ResultSwapped =
11240 assert(*ResultSwapped != *Result &&
11241 "monotonicity should flip as we flip the predicate");
11248std::optional<ScalarEvolution::MonotonicPredicateType>
11249ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11263 return std::nullopt;
11267 "Should be greater or less!");
11271 if (!LHS->hasNoUnsignedWrap())
11272 return std::nullopt;
11276 "Relational predicate is either signed or unsigned!");
11277 if (!
LHS->hasNoSignedWrap())
11278 return std::nullopt;
11280 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11288 return std::nullopt;
11291std::optional<ScalarEvolution::LoopInvariantPredicate>
11298 return std::nullopt;
11305 if (!ArLHS || ArLHS->
getLoop() != L)
11306 return std::nullopt;
11310 return std::nullopt;
11336 return std::nullopt;
11373 return std::nullopt;
11376std::optional<ScalarEvolution::LoopInvariantPredicate>
11381 Pred, LHS, RHS, L, CtxI, MaxIter))
11389 for (
auto *
Op :
UMin->operands())
11391 Pred, LHS, RHS, L, CtxI,
Op))
11393 return std::nullopt;
11396std::optional<ScalarEvolution::LoopInvariantPredicate>
11411 return std::nullopt;
11418 if (!AR || AR->
getLoop() != L)
11419 return std::nullopt;
11423 return std::nullopt;
11429 if (Step != One && Step != MinusOne)
11430 return std::nullopt;
11436 return std::nullopt;
11442 return std::nullopt;
11450 if (Step == MinusOne)
11454 return std::nullopt;
11460bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11466 auto CheckRange = [&](
bool IsSigned) {
11469 return RangeLHS.
icmp(Pred, RangeRHS);
11478 if (CheckRange(
true) || CheckRange(
false))
11487bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11494 auto MatchBinaryAddToConst = [
this](
const SCEV *
X,
const SCEV *
Y,
11495 APInt &OutC1, APInt &OutC2,
11497 const SCEV *XNonConstOp, *XConstOp;
11498 const SCEV *YNonConstOp, *YConstOp;
11502 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11505 XFlagsPresent = ExpectedFlags;
11510 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11513 YFlagsPresent = ExpectedFlags;
11516 if (YNonConstOp != XNonConstOp)
11524 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11527 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11587bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11609bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11610 const SCEV *
LHS,
const SCEV *
RHS) {
11615 return any_of(*BB, [&](
const Instruction &
I) {
11616 using namespace llvm::PatternMatch;
11621 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11635 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11640 "This cannot be done on broken IR!");
11643 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11652 if (LoopContinuePredicate && LoopContinuePredicate->
isConditional() &&
11653 isImpliedCond(Pred, LHS, RHS,
11655 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11660 if (WalkingBEDominatingConds)
11666 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11667 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11674 const SCEV *LoopCounter =
11682 for (
auto &AssumeVH : AC.assumptions()) {
11689 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11693 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11696 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11697 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11698 assert(DTN &&
"should reach the loop header before reaching the root!");
11701 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11709 if (!ContinuePredicate || !ContinuePredicate->
isConditional())
11723 assert(DT.dominates(DominatingEdge, Latch) &&
"should be!");
11725 if (isImpliedCond(Pred, LHS, RHS, Condition,
11739 if (!DT.isReachableFromEntry(BB))
11743 "This cannot be done on broken IR!");
11751 const bool ProvingStrictComparison =
11753 bool ProvedNonStrictComparison =
false;
11754 bool ProvedNonEquality =
false;
11757 if (!ProvedNonStrictComparison)
11758 ProvedNonStrictComparison = Fn(NonStrictPredicate);
11759 if (!ProvedNonEquality)
11761 if (ProvedNonStrictComparison && ProvedNonEquality)
11766 if (ProvingStrictComparison) {
11768 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
11770 if (SplitAndProve(ProofFn))
11775 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
11777 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
11779 if (ProvingStrictComparison) {
11781 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
11783 if (SplitAndProve(ProofFn))
11792 const Loop *ContainingLoop = LI.getLoopFor(BB);
11794 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
11798 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
11799 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
11811 for (
auto &AssumeVH : AC.assumptions()) {
11815 if (!DT.dominates(CI, BB))
11818 if (ProveViaCond(CI->getArgOperand(0),
false))
11824 F.getParent(), Intrinsic::experimental_guard);
11826 for (
const auto *GU : GuardDecl->users())
11828 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
11829 if (ProveViaCond(Guard->getArgOperand(0),
false))
11844 "LHS is not available at Loop Entry");
11846 "RHS is not available at Loop Entry");
11848 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11859 if (FoundCondValue ==
11863 if (!PendingLoopPredicates.insert(FoundCondValue).second)
11867 make_scope_exit([&]() { PendingLoopPredicates.erase(FoundCondValue); });
11870 const Value *Op0, *Op1;
11873 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
11877 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
11878 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
11882 if (!ICI)
return false;
11886 CmpPredicate FoundPred;
11895 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
11898bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
11899 const SCEV *
RHS, CmpPredicate FoundPred,
11900 const SCEV *FoundLHS,
const SCEV *FoundRHS,
11901 const Instruction *CtxI) {
11911 auto *WideType = FoundLHS->
getType();
11923 TruncFoundLHS, TruncFoundRHS, CtxI))
11949 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
11953bool ScalarEvolution::isImpliedCondBalancedTypes(
11954 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
11955 const SCEV *FoundLHS,
const SCEV *FoundRHS,
const Instruction *CtxI) {
11958 "Types should be balanced!");
11965 if (FoundLHS == FoundRHS)
11969 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
11981 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
11998 LHS, FoundLHS, FoundRHS, CtxI);
12000 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12022 assert(P1 != P2 &&
"Handled earlier!");
12026 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12031 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12034 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12035 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12036 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12041 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12052 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12053 CanonicalRHS, CanonicalFoundLHS,
12054 CanonicalFoundRHS);
12059 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12060 CanonicalRHS, CanonicalFoundLHS,
12061 CanonicalFoundRHS);
12068 const SCEVConstant *
C =
nullptr;
12069 const SCEV *
V =
nullptr;
12087 if (Min ==
C->getAPInt()) {
12092 APInt SharperMin = Min + 1;
12095 case ICmpInst::ICMP_SGE:
12096 case ICmpInst::ICMP_UGE:
12099 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12104 case ICmpInst::ICMP_SGT:
12105 case ICmpInst::ICMP_UGT:
12115 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12120 case ICmpInst::ICMP_SLE:
12121 case ICmpInst::ICMP_ULE:
12122 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12123 LHS, V, getConstant(SharperMin), CtxI))
12127 case ICmpInst::ICMP_SLT:
12128 case ICmpInst::ICMP_ULT:
12129 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12130 LHS, V, getConstant(Min), CtxI))
12144 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12148 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12151 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12158bool ScalarEvolution::splitBinaryAdd(
const SCEV *Expr,
12159 const SCEV *&L,
const SCEV *&R,
12168std::optional<APInt>
12175 APInt DiffMul(BW, 1);
12178 for (
unsigned I = 0;
I < 8; ++
I) {
12187 if (LAR->getLoop() != MAR->getLoop())
12188 return std::nullopt;
12192 if (!LAR->isAffine() || !MAR->isAffine())
12193 return std::nullopt;
12195 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12196 return std::nullopt;
12198 Less = LAR->getStart();
12199 More = MAR->getStart();
12204 auto MatchConstMul =
12205 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12210 return std::nullopt;
12212 if (
auto MatchedMore = MatchConstMul(More)) {
12213 if (
auto MatchedLess = MatchConstMul(
Less)) {
12214 if (MatchedMore->second == MatchedLess->second) {
12215 More = MatchedMore->first;
12216 Less = MatchedLess->first;
12217 DiffMul *= MatchedMore->second;
12228 Diff +=
C->getAPInt() * DiffMul;
12231 Diff -=
C->getAPInt() * DiffMul;
12234 Multiplicity[S] +=
Mul;
12236 auto Decompose = [&](
const SCEV *S,
int Mul) {
12243 Decompose(More, 1);
12244 Decompose(
Less, -1);
12248 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12249 for (
const auto &[S,
Mul] : Multiplicity) {
12254 return std::nullopt;
12256 }
else if (
Mul == -1) {
12258 return std::nullopt;
12261 return std::nullopt;
12265 if (NewMore == More || NewLess ==
Less)
12266 return std::nullopt;
12272 if (!More && !
Less)
12276 if (!More || !
Less)
12277 return std::nullopt;
12281 return std::nullopt;
12284bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12308 if (!L->contains(ContextBB) || !DT.
dominates(ContextBB, L->getLoopLatch()))
12319 if (!L->contains(ContextBB) || !DT.
dominates(ContextBB, L->getLoopLatch()))
12329bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12332 const SCEV *FoundLHS,
12333 const SCEV *FoundRHS) {
12342 if (!AddRecFoundLHS)
12349 const Loop *
L = AddRecFoundLHS->getLoop();
12350 if (L != AddRecLHS->getLoop())
12389 if (!RDiff || *LDiff != *RDiff)
12392 if (LDiff->isMinValue())
12395 APInt FoundRHSLimit;
12398 FoundRHSLimit = -(*RDiff);
12410bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12411 const SCEV *
RHS,
const SCEV *FoundLHS,
12412 const SCEV *FoundRHS,
unsigned Depth) {
12413 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12417 bool Erased = PendingMerges.erase(LPhi);
12418 assert(Erased &&
"Failed to erase LPhi!");
12422 bool Erased = PendingMerges.erase(RPhi);
12423 assert(Erased &&
"Failed to erase RPhi!");
12431 if (!PendingMerges.insert(Phi).second)
12445 if (!PendingMerges.insert(Phi).second)
12451 if (!LPhi && !RPhi)
12462 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12466 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12467 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12468 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12469 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12472 if (RPhi && RPhi->getParent() == LBB) {
12479 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12480 if (!ProvedEasily(L, R))
12491 auto *RLoop = RAR->
getLoop();
12492 auto *Predecessor = RLoop->getLoopPredecessor();
12493 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12495 if (!ProvedEasily(L1, RAR->
getStart()))
12497 auto *Latch = RLoop->getLoopLatch();
12498 assert(Latch &&
"Loop with AddRec with no latch?");
12519 if (
auto *Loop = LI.getLoopFor(LBB))
12522 if (!ProvedEasily(L,
RHS))
12529bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12532 const SCEV *FoundLHS,
12533 const SCEV *FoundRHS) {
12536 if (
RHS == FoundRHS) {
12541 if (
LHS != FoundLHS)
12548 Value *Shiftee, *ShiftValue;
12550 using namespace PatternMatch;
12551 if (
match(SUFoundRHS->getValue(),
12553 auto *ShifteeS =
getSCEV(Shiftee);
12571bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12573 const SCEV *FoundLHS,
12574 const SCEV *FoundRHS,
12575 const Instruction *CtxI) {
12576 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12578 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12580 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12581 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12583 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12587template <
typename MinMaxExprType>
12589 const SCEV *Candidate) {
12594 return is_contained(MinMaxExpr->operands(), Candidate);
12607 const SCEV *LStart, *RStart, *Step;
12657bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12659 const SCEV *FoundLHS,
12660 const SCEV *FoundRHS,
12664 "LHS and RHS have different sizes?");
12667 "FoundLHS and FoundRHS have different sizes?");
12701 auto GetOpFromSExt = [&](
const SCEV *S) {
12703 return Ext->getOperand();
12710 auto *OrigLHS =
LHS;
12711 auto *OrigFoundLHS = FoundLHS;
12712 LHS = GetOpFromSExt(
LHS);
12713 FoundLHS = GetOpFromSExt(FoundLHS);
12716 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
12719 FoundRHS,
Depth + 1);
12732 if (!LHSAddExpr->hasNoSignedWrap())
12735 auto *LL = LHSAddExpr->getOperand(0);
12736 auto *LR = LHSAddExpr->getOperand(1);
12740 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
12741 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
12746 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
12752 using namespace llvm::PatternMatch;
12771 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
12779 auto *DTy = Denominator->getType();
12780 auto *FRHSTy = FoundRHS->
getType();
12781 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
12800 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
12811 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
12813 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
12821 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
12854bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
12858 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
12861 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
12864bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
12867 const SCEV *FoundLHS,
12868 const SCEV *FoundRHS) {
12904 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
12910bool ScalarEvolution::isImpliedCondOperandsViaRanges(
12911 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
12912 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
12926 ConstantRange FoundLHSRange =
12930 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
12937 return LHSRange.
icmp(Pred, ConstRHS);
12940bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
12953 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
12961 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
12964bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
12976 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
12984 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
12996const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
12997 const SCEV *Stride,
13028 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13039 :
APIntOps::umax(MaxEnd, MinStart);
13046ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13047 const Loop *L,
bool IsSigned,
13048 bool ControlsOnlyExit,
bool AllowPredicates) {
13052 bool PredicatedIV =
false;
13057 auto canProveNUW = [&]() {
13060 if (!ControlsOnlyExit)
13081 Limit = Limit.
zext(OuterBitWidth);
13093 Type *Ty = ZExt->getType();
13104 if (!
IV && AllowPredicates) {
13109 PredicatedIV =
true;
13113 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13127 bool NoWrap = ControlsOnlyExit &&
IV->getNoWrapFlags(WrapType);
13130 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13135 if (!PositiveStride) {
13187 auto wouldZeroStrideBeUB = [&]() {
13199 if (!wouldZeroStrideBeUB()) {
13203 }
else if (!NoWrap) {
13206 if (canIVOverflowOnLT(
RHS, Stride, IsSigned))
13219 const SCEV *
Start =
IV->getStart();
13225 const SCEV *OrigStart =
Start;
13226 const SCEV *OrigRHS =
RHS;
13227 if (
Start->getType()->isPointerTy()) {
13238 const SCEV *End =
nullptr, *BECount =
nullptr,
13239 *BECountIfBackedgeTaken =
nullptr;
13242 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13243 RHSAddRec->getNoWrapFlags()) {
13256 const SCEV *RHSStart = RHSAddRec->getStart();
13257 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13269 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13278 BECountIfBackedgeTaken =
13283 if (BECount ==
nullptr) {
13288 const SCEV *MaxBECount = computeMaxBECountForLT(
13291 MaxBECount,
false , Predicates);
13298 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13325 const SCEV *Numerator =
13331 auto canProveRHSGreaterThanEqualStart = [&]() {
13350 auto *StartMinusOne =
13357 if (canProveRHSGreaterThanEqualStart()) {
13372 BECountIfBackedgeTaken =
13388 bool MayAddOverflow = [&] {
13434 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13448 if (!MayAddOverflow) {
13460 const SCEV *ConstantMaxBECount;
13461 bool MaxOrZero =
false;
13463 ConstantMaxBECount = BECount;
13464 }
else if (BECountIfBackedgeTaken &&
13469 ConstantMaxBECount = BECountIfBackedgeTaken;
13472 ConstantMaxBECount = computeMaxBECountForLT(
13480 const SCEV *SymbolicMaxBECount =
13482 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13486ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13487 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13488 bool ControlsOnlyExit,
bool AllowPredicates) {
13495 if (!
IV && AllowPredicates)
13502 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13506 bool NoWrap = ControlsOnlyExit &&
IV->getNoWrapFlags(WrapType);
13519 if (!Stride->
isOne() && !NoWrap)
13520 if (canIVOverflowOnGT(
RHS, Stride, IsSigned))
13523 const SCEV *
Start =
IV->getStart();
13524 const SCEV *End =
RHS;
13535 if (
Start->getType()->isPointerTy()) {
13570 const SCEV *ConstantMaxBECount =
13577 ConstantMaxBECount = BECount;
13578 const SCEV *SymbolicMaxBECount =
13581 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13587 if (
Range.isFullSet())
13592 if (!SC->getValue()->isZero()) {
13598 return ShiftedAddRec->getNumIterationsInRange(
13599 Range.subtract(SC->getAPInt()), SE);
13630 APInt ExitVal = (End +
A).udiv(
A);
13643 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13644 "Linear scev computation is off in a bad way!");
13675 assert(!
Last->isZero() &&
"Recurrency with zero step?");
13703 Ty = Store->getValueOperand()->getType();
13705 Ty = Load->getType();
13718 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13720 SE->ConstantEvolutionLoopExitValue.erase(PN);
13721 SE->eraseValueFromMap(getValPtr());
13725void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
13726 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13736 : CallbackVH(
V), SE(se) {}
13745 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
13747 LoopDispositions(64), BlockDispositions(64) {
13759 F.getParent(), Intrinsic::experimental_guard);
13760 HasGuards = GuardDecl && !GuardDecl->use_empty();
13764 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
13765 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
13766 ValueExprMap(
std::
move(Arg.ValueExprMap)),
13767 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
13768 PendingPhiRanges(
std::
move(Arg.PendingPhiRanges)),
13769 PendingMerges(
std::
move(Arg.PendingMerges)),
13770 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
13771 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
13772 PredicatedBackedgeTakenCounts(
13773 std::
move(Arg.PredicatedBackedgeTakenCounts)),
13774 BECountUsers(
std::
move(Arg.BECountUsers)),
13775 ConstantEvolutionLoopExitValue(
13776 std::
move(Arg.ConstantEvolutionLoopExitValue)),
13777 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
13778 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
13779 LoopDispositions(
std::
move(Arg.LoopDispositions)),
13780 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
13781 BlockDispositions(
std::
move(Arg.BlockDispositions)),
13782 SCEVUsers(
std::
move(Arg.SCEVUsers)),
13783 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
13784 SignedRanges(
std::
move(Arg.SignedRanges)),
13785 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
13786 UniquePreds(
std::
move(Arg.UniquePreds)),
13787 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
13788 LoopUsers(
std::
move(Arg.LoopUsers)),
13789 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
13790 FirstUnknown(Arg.FirstUnknown) {
13791 Arg.FirstUnknown =
nullptr;
13800 Tmp->~SCEVUnknown();
13802 FirstUnknown =
nullptr;
13804 ExprValueMap.clear();
13805 ValueExprMap.clear();
13807 BackedgeTakenCounts.clear();
13808 PredicatedBackedgeTakenCounts.clear();
13810 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
13811 assert(PendingPhiRanges.empty() &&
"getRangeRef garbage");
13812 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
13813 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
13814 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
13836 L->getHeader()->printAsOperand(OS,
false);
13840 L->getExitingBlocks(ExitingBlocks);
13841 if (ExitingBlocks.
size() != 1)
13842 OS <<
"<multiple exits> ";
13846 OS <<
"backedge-taken count is ";
13849 OS <<
"Unpredictable backedge-taken count.";
13852 if (ExitingBlocks.
size() > 1)
13853 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
13854 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
13862 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
13865 OS <<
"\n Predicates:\n";
13866 for (
const auto *
P : Predicates)
13874 L->getHeader()->printAsOperand(OS,
false);
13879 OS <<
"constant max backedge-taken count is ";
13882 OS <<
", actual taken count either this or zero.";
13884 OS <<
"Unpredictable constant max backedge-taken count. ";
13889 L->getHeader()->printAsOperand(OS,
false);
13894 OS <<
"symbolic max backedge-taken count is ";
13897 OS <<
", actual taken count either this or zero.";
13899 OS <<
"Unpredictable symbolic max backedge-taken count. ";
13903 if (ExitingBlocks.
size() > 1)
13904 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
13905 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
13915 OS <<
"\n predicated symbolic max exit count for "
13916 << ExitingBlock->
getName() <<
": ";
13918 OS <<
"\n Predicates:\n";
13919 for (
const auto *
P : Predicates)
13929 assert(!Preds.
empty() &&
"Different predicated BTC, but no predicates");
13931 L->getHeader()->printAsOperand(OS,
false);
13934 OS <<
"Predicated backedge-taken count is ";
13937 OS <<
"Unpredictable predicated backedge-taken count.";
13939 OS <<
" Predicates:\n";
13940 for (
const auto *
P : Preds)
13945 auto *PredConstantMax =
13947 if (PredConstantMax != ConstantBTC) {
13949 "different predicated constant max BTC but no predicates");
13951 L->getHeader()->printAsOperand(OS,
false);
13954 OS <<
"Predicated constant max backedge-taken count is ";
13957 OS <<
"Unpredictable predicated constant max backedge-taken count.";
13959 OS <<
" Predicates:\n";
13960 for (
const auto *
P : Preds)
13965 auto *PredSymbolicMax =
13967 if (SymbolicBTC != PredSymbolicMax) {
13969 "Different predicated symbolic max BTC, but no predicates");
13971 L->getHeader()->printAsOperand(OS,
false);
13974 OS <<
"Predicated symbolic max backedge-taken count is ";
13977 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
13979 OS <<
" Predicates:\n";
13980 for (
const auto *
P : Preds)
13986 L->getHeader()->printAsOperand(OS,
false);
14002 OS <<
"Computable";
14011 OS <<
"DoesNotDominate";
14017 OS <<
"ProperlyDominates";
14034 OS <<
"Classifying expressions for: ";
14035 F.printAsOperand(OS,
false);
14050 const Loop *L = LI.getLoopFor(
I.getParent());
14065 OS <<
"\t\t" "Exits: ";
14068 OS <<
"<<Unknown>>";
14074 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14076 OS <<
"\t\t" "LoopDispositions: { ";
14082 Iter->getHeader()->printAsOperand(OS,
false);
14090 OS <<
"\t\t" "LoopDispositions: { ";
14096 InnerL->getHeader()->printAsOperand(OS,
false);
14107 OS <<
"Determining loop execution counts for: ";
14108 F.printAsOperand(OS,
false);
14116 auto &Values = LoopDispositions[S];
14117 for (
auto &V : Values) {
14118 if (V.getPointer() == L)
14123 auto &Values2 = LoopDispositions[S];
14125 if (V.getPointer() == L) {
14134ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14153 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14154 " dominate the contained loop's header?");
14181 bool HasVarying =
false;
14215 auto &Values = BlockDispositions[S];
14216 for (
auto &V : Values) {
14217 if (V.getPointer() == BB)
14222 auto &Values2 = BlockDispositions[S];
14224 if (V.getPointer() == BB) {
14233ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14262 bool Proper =
true;
14273 if (Instruction *
I =
14275 if (
I->getParent() == BB)
14277 if (DT.properlyDominates(
I->getParent(), BB))
14300void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14303 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14304 auto It = BECounts.find(L);
14305 if (It != BECounts.end()) {
14306 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14307 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14309 auto UserIt = BECountUsers.find(S);
14310 assert(UserIt != BECountUsers.end());
14315 BECounts.erase(It);
14323 while (!Worklist.
empty()) {
14325 auto Users = SCEVUsers.find(Curr);
14326 if (
Users != SCEVUsers.end())
14327 for (
const auto *User :
Users->second)
14328 if (ToForget.
insert(User).second)
14332 for (
const auto *S : ToForget)
14333 forgetMemoizedResultsImpl(S);
14335 for (
auto I = PredicatedSCEVRewrites.begin();
14336 I != PredicatedSCEVRewrites.end();) {
14337 std::pair<const SCEV *, const Loop *>
Entry =
I->first;
14338 if (ToForget.count(
Entry.first))
14339 PredicatedSCEVRewrites.erase(
I++);
14345void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14346 LoopDispositions.erase(S);
14347 BlockDispositions.erase(S);
14348 UnsignedRanges.erase(S);
14349 SignedRanges.erase(S);
14350 HasRecMap.erase(S);
14351 ConstantMultipleCache.erase(S);
14354 UnsignedWrapViaInductionTried.erase(AR);
14355 SignedWrapViaInductionTried.erase(AR);
14358 auto ExprIt = ExprValueMap.find(S);
14359 if (ExprIt != ExprValueMap.end()) {
14360 for (
Value *V : ExprIt->second) {
14361 auto ValueIt = ValueExprMap.find_as(V);
14362 if (ValueIt != ValueExprMap.end())
14363 ValueExprMap.erase(ValueIt);
14365 ExprValueMap.erase(ExprIt);
14368 auto ScopeIt = ValuesAtScopes.find(S);
14369 if (ScopeIt != ValuesAtScopes.end()) {
14370 for (
const auto &Pair : ScopeIt->second)
14373 std::make_pair(Pair.first, S));
14374 ValuesAtScopes.erase(ScopeIt);
14377 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14378 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14379 for (
const auto &Pair : ScopeUserIt->second)
14380 llvm::erase(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
14381 ValuesAtScopesUsers.erase(ScopeUserIt);
14384 auto BEUsersIt = BECountUsers.find(S);
14385 if (BEUsersIt != BECountUsers.end()) {
14387 auto Copy = BEUsersIt->second;
14388 for (
const auto &Pair : Copy)
14389 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14390 BECountUsers.erase(BEUsersIt);
14393 auto FoldUser = FoldCacheUser.find(S);
14394 if (FoldUser != FoldCacheUser.end())
14395 for (
auto &KV : FoldUser->second)
14396 FoldCache.erase(KV);
14397 FoldCacheUser.erase(S);
14401ScalarEvolution::getUsedLoops(
const SCEV *S,
14403 struct FindUsedLoops {
14404 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14405 : LoopsUsed(LoopsUsed) {}
14406 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14407 bool follow(
const SCEV *S) {
14413 bool isDone()
const {
return false; }
14416 FindUsedLoops
F(LoopsUsed);
14417 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14420void ScalarEvolution::getReachableBlocks(
14423 Worklist.
push_back(&F.getEntryBlock());
14424 while (!Worklist.
empty()) {
14426 if (!Reachable.
insert(BB).second)
14434 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14441 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14445 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14480 SCEVMapper SCM(SE2);
14482 SE2.getReachableBlocks(ReachableBlocks, F);
14484 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14502 while (!LoopStack.
empty()) {
14508 if (!ReachableBlocks.
contains(L->getHeader()))
14513 auto It = BackedgeTakenCounts.find(L);
14514 if (It == BackedgeTakenCounts.end())
14518 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14538 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14539 if (Delta && !Delta->
isZero()) {
14540 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14541 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14542 dbgs() <<
"New: " << *NewBECount <<
"\n";
14543 dbgs() <<
"Delta: " << *Delta <<
"\n";
14551 while (!Worklist.
empty()) {
14553 if (ValidLoops.
insert(L).second)
14554 Worklist.
append(L->begin(), L->end());
14556 for (
const auto &KV : ValueExprMap) {
14561 "AddRec references invalid loop");
14566 auto It = ExprValueMap.find(KV.second);
14567 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14568 dbgs() <<
"Value " << *KV.first
14569 <<
" is in ValueExprMap but not in ExprValueMap\n";
14574 if (!ReachableBlocks.
contains(
I->getParent()))
14576 const SCEV *OldSCEV = SCM.visit(KV.second);
14578 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14579 if (Delta && !Delta->
isZero()) {
14580 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14581 <<
"Old: " << *OldSCEV <<
"\n"
14582 <<
"New: " << *NewSCEV <<
"\n"
14583 <<
"Delta: " << *Delta <<
"\n";
14589 for (
const auto &KV : ExprValueMap) {
14590 for (
Value *V : KV.second) {
14591 const SCEV *S = ValueExprMap.lookup(V);
14593 dbgs() <<
"Value " << *V
14594 <<
" is in ExprValueMap but not in ValueExprMap\n";
14597 if (S != KV.first) {
14598 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14599 << *KV.first <<
"\n";
14606 for (
const auto &S : UniqueSCEVs) {
14611 auto It = SCEVUsers.find(
Op);
14612 if (It != SCEVUsers.end() && It->second.count(&S))
14614 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14615 <<
" is not being tracked!\n";
14621 for (
const auto &ValueAndVec : ValuesAtScopes) {
14623 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14624 const Loop *L = LoopAndValueAtScope.first;
14625 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
14627 auto It = ValuesAtScopesUsers.find(ValueAtScope);
14628 if (It != ValuesAtScopesUsers.end() &&
14631 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14632 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14638 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14639 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14640 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14641 const Loop *L = LoopAndValue.first;
14642 const SCEV *
Value = LoopAndValue.second;
14644 auto It = ValuesAtScopes.find(
Value);
14645 if (It != ValuesAtScopes.end() &&
14646 is_contained(It->second, std::make_pair(L, ValueAtScope)))
14648 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14649 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14655 auto VerifyBECountUsers = [&](
bool Predicated) {
14657 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14658 for (
const auto &LoopAndBEInfo : BECounts) {
14659 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14660 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14662 auto UserIt = BECountUsers.find(S);
14663 if (UserIt != BECountUsers.end() &&
14664 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14666 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14667 <<
" missing from BECountUsers\n";
14674 VerifyBECountUsers(
false);
14675 VerifyBECountUsers(
true);
14678 for (
auto &[S, Values] : LoopDispositions) {
14679 for (
auto [
Loop, CachedDisposition] : Values) {
14681 if (CachedDisposition != RecomputedDisposition) {
14682 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
14683 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
14684 << RecomputedDisposition <<
"\n";
14691 for (
auto &[S, Values] : BlockDispositions) {
14692 for (
auto [BB, CachedDisposition] : Values) {
14694 if (CachedDisposition != RecomputedDisposition) {
14695 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
14696 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
14697 <<
", actual " << RecomputedDisposition <<
"\n";
14704 for (
auto [
FoldID, Expr] : FoldCache) {
14705 auto I = FoldCacheUser.find(Expr);
14706 if (
I == FoldCacheUser.end()) {
14707 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
14712 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
14716 for (
auto [Expr, IDs] : FoldCacheUser) {
14717 for (
auto &
FoldID : IDs) {
14720 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
14725 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
14726 <<
" != " << *Expr <<
"!\n";
14737 for (
auto [S, Multiple] : ConstantMultipleCache) {
14739 if ((Multiple != 0 && RecomputedMultiple != 0 &&
14740 Multiple.
urem(RecomputedMultiple) != 0 &&
14741 RecomputedMultiple.
urem(Multiple) != 0)) {
14742 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
14743 << *S <<
" : Computed " << RecomputedMultiple
14744 <<
" but cache contains " << Multiple <<
"!\n";
14752 FunctionAnalysisManager::Invalidator &Inv) {
14784 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
14785 <<
F.getName() <<
"':\n";
14791 "Scalar Evolution Analysis",
false,
true)
14840 const SCEV *LHS,
const SCEV *RHS) {
14842 assert(LHS->getType() == RHS->getType() &&
14843 "Type mismatch between LHS and RHS");
14846 ID.AddInteger(Pred);
14847 ID.AddPointer(LHS);
14848 ID.AddPointer(RHS);
14849 void *IP =
nullptr;
14850 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
14854 UniquePreds.InsertNode(Eq, IP);
14865 ID.AddInteger(AddedFlags);
14866 void *IP =
nullptr;
14867 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
14869 auto *OF =
new (SCEVAllocator)
14871 UniquePreds.InsertNode(OF, IP);
14891 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
14892 return Rewriter.visit(S);
14898 for (
const auto *Pred : U->getPredicates())
14900 if (IPred->getLHS() == Expr &&
14902 return IPred->getRHS();
14904 if (IPred->getLHS() == Expr &&
14905 IPred->getPredicate() == ICmpInst::ICMP_EQ)
14906 return IPred->getRHS();
14909 return convertToAddRecWithPreds(Expr);
14912 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
14928 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
14945 explicit SCEVPredicateRewriter(
14946 const Loop *L, ScalarEvolution &SE,
14947 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
14948 const SCEVPredicate *Pred)
14949 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
14951 bool addOverflowAssumption(
const SCEVPredicate *
P) {
14954 return Pred && Pred->
implies(
P, SE);
14960 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
14963 return addOverflowAssumption(
A);
14972 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
14976 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
14978 if (!PredicatedRewrite)
14980 for (
const auto *
P : PredicatedRewrite->second){
14983 if (L != WP->getExpr()->getLoop())
14986 if (!addOverflowAssumption(
P))
14989 return PredicatedRewrite->first;
14992 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
14993 const SCEVPredicate *Pred;
15002 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15009 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15029 if (!Step->
isOne())
15054 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15055 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15068 return Op->LHS == LHS &&
Op->RHS == RHS;
15075 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15077 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15102 const SCEV *Start = AR->getStart();
15103 const SCEV *OpStart =
Op->AR->getStart();
15108 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15111 const SCEV *Step = AR->getStepRecurrence(SE);
15112 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15165 if (Step->getValue()->getValue().isNonNegative())
15169 return ImpliedFlags;
15176 for (
const auto *
P : Preds)
15189 return this->implies(I, SE);
15197 for (
const auto *Pred : Preds)
15198 Pred->print(OS,
Depth);
15203 for (
const auto *Pred : Set->Preds)
15211 bool CheckImplies = Preds.
size() < 16;
15214 if (CheckImplies &&
implies(
N, SE))
15220 for (
auto *
P : Preds) {
15221 if (CheckImplies &&
N->implies(
P, SE))
15225 Preds = std::move(PrunedPreds);
15226 Preds.push_back(
N);
15233 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15238 for (
const auto *
Op :
Ops)
15243 SCEVUsers[
Op].insert(
User);
15247 const SCEV *Expr = SE.getSCEV(V);
15248 RewriteEntry &Entry = RewriteMap[Expr];
15251 if (Entry.second && Generation == Entry.first)
15252 return Entry.second;
15257 Expr = Entry.second;
15259 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15260 Entry = {Generation, NewSCEV};
15266 if (!BackedgeCount) {
15268 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15269 for (
const auto *
P : Preds)
15272 return BackedgeCount;
15276 if (!SymbolicMaxBackedgeCount) {
15278 SymbolicMaxBackedgeCount =
15279 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15280 for (
const auto *
P : Preds)
15283 return SymbolicMaxBackedgeCount;
15287 if (!SmallConstantMaxTripCount) {
15289 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15290 for (
const auto *
P : Preds)
15293 return *SmallConstantMaxTripCount;
15297 if (Preds->implies(&Pred, SE))
15302 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15303 updateGeneration();
15310void PredicatedScalarEvolution::updateGeneration() {
15312 if (++Generation == 0) {
15313 for (
auto &
II : RewriteMap) {
15314 const SCEV *Rewritten =
II.second.second;
15331 auto II = FlagsMap.insert({V, Flags});
15344 auto II = FlagsMap.find(V);
15346 if (
II != FlagsMap.end())
15355 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15360 for (
const auto *
P : NewPreds)
15363 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15369 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15372 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {
15373 for (
auto I :
Init.FlagsMap)
15374 FlagsMap.insert(
I);
15379 for (
auto *BB : L.getBlocks())
15380 for (
auto &
I : *BB) {
15381 if (!SE.isSCEVable(
I.getType()))
15384 auto *Expr = SE.getSCEV(&
I);
15385 auto II = RewriteMap.find(Expr);
15387 if (
II == RewriteMap.end())
15391 if (
II->second.second == Expr)
15396 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15404 LoopGuards Guards(SE);
15412void ScalarEvolution::LoopGuards::collectFromPHI(
15420 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15421 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15435 auto &RewriteMap =
G->second.RewriteMap;
15436 if (RewriteMap.empty())
15438 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15439 if (S == RewriteMap.end())
15445 return {C0, SM->getSCEVType()};
15448 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15449 MinMaxPattern P2) -> MinMaxPattern {
15450 auto [C1,
T1] =
P1;
15451 auto [C2, T2] = P2;
15452 if (!C1 || !C2 ||
T1 != T2)
15456 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15458 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15460 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15462 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15467 auto P = GetMinMaxConst(0);
15468 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15471 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15474 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15477 Guards.RewriteMap.insert({
LHS,
RHS});
15485 const APInt &DivisorVal,
15487 const APInt *ExprVal;
15500 const APInt &DivisorVal,
15502 const APInt *ExprVal;
15510 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15513void ScalarEvolution::LoopGuards::collectFromBlock(
15515 const BasicBlock *
Block,
const BasicBlock *Pred,
15523 DenseMap<const SCEV *, const SCEV *>
15540 &ExprsToRewrite]() {
15541 const SCEVConstant *C1;
15554 if (ExactRegion.isWrappedSet() || ExactRegion.isFullSet())
15556 auto [
I,
Inserted] = RewriteMap.try_emplace(LHSUnknown);
15557 const SCEV *RewrittenLHS =
Inserted ? LHSUnknown :
I->second;
15565 if (MatchRangeCheckIdiom())
15571 auto IsMinMaxSCEVWithNonNegativeConstant =
15572 [&](
const SCEV *Expr,
SCEVTypes &SCTy,
const SCEV *&
LHS,
15573 const SCEV *&
RHS) {
15583 std::function<
const SCEV *(
const SCEV *,
const SCEV *)>
15584 ApplyDivisibiltyOnMinMaxExpr = [&](
const SCEV *MinMaxExpr,
15585 const SCEV *Divisor) {
15589 const APInt &DivisorVal = ConstDivisor->getAPInt();
15591 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15593 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15599 "Expected non-negative operand!");
15600 auto *DivisibleExpr =
15605 ApplyDivisibiltyOnMinMaxExpr(MinMaxRHS, Divisor), DivisibleExpr};
15615 const SCEV *URemRHS =
nullptr;
15618 auto I = RewriteMap.find(URemLHS);
15619 const SCEV *RewrittenLHS =
I != RewriteMap.end() ?
I->second : URemLHS;
15620 RewrittenLHS = ApplyDivisibiltyOnMinMaxExpr(RewrittenLHS, URemRHS);
15621 const auto *Multiple =
15623 RewriteMap[URemLHS] = Multiple;
15643 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15645 if (From == FromRewritten)
15647 RewriteMap[From] = To;
15653 auto GetMaybeRewritten = [&](
const SCEV *S) {
15654 return RewriteMap.lookup_or(S, S);
15657 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15672 switch (Predicate) {
15701 SmallPtrSet<const SCEV *, 16> Visited;
15703 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
15707 while (!Worklist.
empty()) {
15711 if (!Visited.
insert(From).second)
15713 const SCEV *FromRewritten = GetMaybeRewritten(From);
15714 const SCEV *To =
nullptr;
15716 switch (Predicate) {
15721 EnqueueOperands(
UMax);
15727 EnqueueOperands(
SMax);
15733 EnqueueOperands(
UMin);
15739 EnqueueOperands(
SMin);
15747 const SCEV *OneAlignedUp =
15749 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
15761 const SCEVConstant *
C;
15770 Guards.NotEqual.insert({
LHS,
RHS});
15779 AddRewrite(From, FromRewritten, To);
15796 SE.F.
getParent(), Intrinsic::experimental_guard);
15798 for (
const auto *GU : GuardDecl->users())
15800 if (Guard->getFunction() ==
Block->getParent() &&
15809 unsigned NumCollectedConditions = 0;
15811 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
15813 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
15815 const BranchInst *LoopEntryPredicate =
15822 NumCollectedConditions++;
15826 if (
Depth > 0 && NumCollectedConditions == 2)
15834 if (Pair.second->hasNPredecessorsOrMore(2) &&
15836 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
15837 for (
auto &Phi : Pair.second->phis())
15845 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
15846 SmallVector<Value *, 8> Worklist;
15847 SmallPtrSet<Value *, 8> Visited;
15849 while (!Worklist.
empty()) {
15856 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
15859 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap);
15875 Guards.PreserveNUW =
true;
15876 Guards.PreserveNSW =
true;
15877 for (
const SCEV *Expr : ExprsToRewrite) {
15878 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
15879 Guards.PreserveNUW &=
15881 Guards.PreserveNSW &=
15888 if (ExprsToRewrite.size() > 1) {
15889 for (
const SCEV *Expr : ExprsToRewrite) {
15890 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
15891 Guards.RewriteMap.erase(Expr);
15892 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
15901 class SCEVLoopGuardRewriter
15912 NotEqual(Guards.NotEqual) {
15913 if (Guards.PreserveNUW)
15915 if (Guards.PreserveNSW)
15922 return Map.lookup_or(Expr, Expr);
15926 if (
const SCEV *S = Map.lookup(Expr))
15933 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
15934 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
15935 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
15937 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
15938 if (
const SCEV *S = Map.lookup(NarrowExt))
15939 return SE.getZeroExtendExpr(S, Ty);
15940 Bitwidth = Bitwidth / 2;
15948 if (
const SCEV *S = Map.lookup(Expr))
15955 if (
const SCEV *S = Map.lookup(Expr))
15961 if (
const SCEV *S = Map.lookup(Expr))
15969 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
15970 const SCEV *LHS, *RHS;
15974 if (NotEqual.contains({LHS, RHS})) {
15976 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
15977 return SE.getUMaxExpr(OneAlignedUp, S);
15984 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
15995 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
15996 return SE.getAddExpr(
15999 if (
const SCEV *S = Map.lookup(
Add))
16000 return SE.getAddExpr(Expr->
getOperand(0), S);
16012 : SE.getAddExpr(Operands,
16028 : SE.getMulExpr(Operands,
16034 if (RewriteMap.empty() && NotEqual.empty())
16037 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16038 return Rewriter.visit(Expr);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Expand Atomic instructions
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
static bool isSigned(unsigned int Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This defines the Use class.
iv Induction Variable Users
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
PowerPC Reduce CR logical Operation
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
const SmallVectorImpl< MachineOperand > & Cond
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
SI optimize exec mask operations pre RA
void visit(MachineFunction &MF, MachineBasicBlock &Start, std::function< void(MachineBasicBlock *)> op)
This file provides utility classes that use RAII to save and restore values.
bool SCEVMinMaxExprContains(const SCEV *Root, const SCEV *OperandToFind, SCEVTypes RootKind)
static cl::opt< unsigned > MaxAddRecSize("scalar-evolution-max-add-rec-size", cl::Hidden, cl::desc("Max coefficients in AddRec during evolving"), cl::init(8))
static cl::opt< unsigned > RangeIterThreshold("scev-range-iter-threshold", cl::Hidden, cl::desc("Threshold for switching to iteratively computing SCEV ranges"), cl::init(32))
static const Loop * isIntegerLoopHeaderPHI(const PHINode *PN, LoopInfo &LI)
static unsigned getConstantTripCount(const SCEVConstant *ExitCount)
static int CompareValueComplexity(const LoopInfo *const LI, Value *LV, Value *RV, unsigned Depth)
Compare the two values LV and RV in terms of their "complexity" where "complexity" is a partial (and ...
static const SCEV * getNextSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static void PushLoopPHIs(const Loop *L, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push PHI nodes in the header of the given loop onto the given Worklist.
static void insertFoldCacheEntry(const ScalarEvolution::FoldID &ID, const SCEV *S, DenseMap< ScalarEvolution::FoldID, const SCEV * > &FoldCache, DenseMap< const SCEV *, SmallVector< ScalarEvolution::FoldID, 2 > > &FoldCacheUser)
static cl::opt< bool > ClassifyExpressions("scalar-evolution-classify-expressions", cl::Hidden, cl::init(true), cl::desc("When printing analysis, include information on every instruction"))
static bool CanConstantFold(const Instruction *I)
Return true if we can constant fold an instruction of the specified type, assuming that all operands ...
static cl::opt< unsigned > AddOpsInlineThreshold("scev-addops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining addition operands into a SCEV"), cl::init(500))
static cl::opt< unsigned > MaxLoopGuardCollectionDepth("scalar-evolution-max-loop-guard-collection-depth", cl::Hidden, cl::desc("Maximum depth for recursive loop guard collection"), cl::init(1))
static cl::opt< bool > VerifyIR("scev-verify-ir", cl::Hidden, cl::desc("Verify IR correctness when making sensitive SCEV queries (slow)"), cl::init(false))
static bool BrPHIToSelect(DominatorTree &DT, BranchInst *BI, PHINode *Merge, Value *&C, Value *&LHS, Value *&RHS)
static const SCEV * getPreStartForExtend(const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE, unsigned Depth)
static std::optional< APInt > MinOptional(std::optional< APInt > X, std::optional< APInt > Y)
Helper function to compare optional APInts: (a) if X and Y both exist, return min(X,...
static cl::opt< unsigned > MulOpsInlineThreshold("scev-mulops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining multiplication operands into a SCEV"), cl::init(32))
static void GroupByComplexity(SmallVectorImpl< const SCEV * > &Ops, LoopInfo *LI, DominatorTree &DT)
Given a list of SCEV objects, order them by their complexity, and group objects of the same complexit...
static const SCEV * constantFoldAndGroupOps(ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT, SmallVectorImpl< const SCEV * > &Ops, FoldT Fold, IsIdentityT IsIdentity, IsAbsorberT IsAbsorber)
Performs a number of common optimizations on the passed Ops.
static 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 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 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 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 SCEV::NoWrapFlags StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, const ArrayRef< const SCEV * > Ops, SCEV::NoWrapFlags Flags)
static cl::opt< unsigned > MaxArithDepth("scalar-evolution-max-arith-depth", cl::Hidden, cl::desc("Maximum depth of recursive arithmetics"), cl::init(32))
static bool HasSameValue(const SCEV *A, const SCEV *B)
SCEV structural equivalence is usually sufficient for testing whether two expressions are equal,...
static uint64_t Choose(uint64_t n, uint64_t k, bool &Overflow)
Compute the result of "n choose k", the binomial coefficient.
static std::optional< int > CompareSCEVComplexity(const LoopInfo *const LI, const SCEV *LHS, const SCEV *RHS, DominatorTree &DT, unsigned Depth=0)
static bool CollectAddOperandsWithScales(SmallDenseMap< const SCEV *, APInt, 16 > &M, SmallVectorImpl< const SCEV * > &NewOps, APInt &AccumulatedConstant, ArrayRef< const SCEV * > Ops, const APInt &Scale, ScalarEvolution &SE)
Process the given Ops list, which is a list of operands to be added under the given scale,...
static bool canConstantEvolve(Instruction *I, const Loop *L)
Determine whether this instruction can constant evolve within this loop assuming its operands can all...
static PHINode * getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L, DenseMap< Instruction *, PHINode * > &PHIMap, unsigned Depth)
getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by recursing through each instructi...
static bool scevUnconditionallyPropagatesPoisonFromOperands(SCEVTypes Kind)
static cl::opt< bool > VerifySCEVStrict("verify-scev-strict", cl::Hidden, cl::desc("Enable stricter verification with -verify-scev is passed"))
static Constant * getOtherIncomingValue(PHINode *PN, BasicBlock *BB)
static cl::opt< bool > UseExpensiveRangeSharpening("scalar-evolution-use-expensive-range-sharpening", cl::Hidden, cl::init(false), cl::desc("Use more powerful methods of sharpening expression ranges. May " "be costly in terms of compile time"))
static const SCEV * getUnsignedOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static bool IsKnownPredicateViaMinOrMax(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Is LHS Pred RHS true on the virtue of LHS or RHS being a Min or Max expression?
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
static bool InBlock(const Value *V, const BasicBlock *BB)
Provides some synthesis utilities to produce sequences of values.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
static SymbolRef::Type getType(const Symbol *Sym)
LocallyHashedType DenseMapInfo< LocallyHashedType >::Empty
static std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
static std::optional< bool > isImpliedCondOperands(CmpInst::Predicate Pred, const Value *ALHS, const Value *ARHS, const Value *BLHS, const Value *BRHS)
Return true if "icmp Pred BLHS BRHS" is true whenever "icmp PredALHS ARHS" is true.
Virtual Register Rewriter
static const uint32_t IV[8]
Class for arbitrary precision integers.
LLVM_ABI APInt umul_ov(const APInt &RHS, bool &Overflow) const
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
uint64_t getZExtValue() const
Get zero extended value.
void setHighBits(unsigned hiBits)
Set the top hiBits bits.
LLVM_ABI APInt getHiBits(unsigned numBits) const
Compute an APInt containing numBits highbits from this APInt.
unsigned getActiveBits() const
Compute the number of active bits in the value.
LLVM_ABI APInt trunc(unsigned width) const
Truncate to new width.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
APInt abs() const
Get the absolute value.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool isSignMask() const
Check if the APInt's value is returned by getSignMask.
LLVM_ABI APInt urem(const APInt &RHS) const
Unsigned remainder operation.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
bool isNegative() const
Determine sign of this APInt.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
bool isNonPositive() const
Determine if this APInt Value is non-positive (<= 0).
unsigned countTrailingZeros() const
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
unsigned logBase2() const
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
LLVM_ABI APInt multiplicativeInverse() const
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
LLVM_ABI APInt sext(unsigned width) const
Sign extend to a new width.
APInt shl(unsigned shiftAmt) const
Left-shift function.
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
bool isSignBitSet() const
Determine if sign bit of this APInt is set.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
This templated class represents "all analyses that operate over <aparticular IR unit>" (e....
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
AnalysisUsage & addRequiredTransitive()
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
size - Get the array size.
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
MutableArrayRef< WeakVH > assumptions()
Access the list of assumption handles currently tracked for this function.
LLVM_ABI bool isSingleEdge() const
Check if this is the only edge between Start and End.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
LLVM_ABI unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
LLVM_ABI Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
BinaryOps getOpcode() const
Conditional or Unconditional Branch instruction.
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
Value * getCondition() const
LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
This class represents a function call, abstracting a target machine's calling convention.
virtual void deleted()
Callback for Value destruction.
bool isFalseWhenEqual() const
This is just a convenience.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ ICMP_UGE
unsigned greater or equal
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
@ ICMP_SGE
signed greater or equal
@ ICMP_ULE
unsigned less or equal
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
bool isTrueWhenEqual() const
This is just a convenience.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
static LLVM_ABI std::optional< CmpPredicate > getMatching(CmpPredicate A, CmpPredicate B)
Compares two CmpPredicates taking samesign into account and returns the canonicalized CmpPredicate if...
LLVM_ABI CmpInst::Predicate getPreferredSignedPredicate() const
Attempts to return a signed CmpInst::Predicate from the CmpPredicate.
CmpInst::Predicate dropSameSign() const
Drops samesign information.
static LLVM_ABI Constant * getNot(Constant *C)
static LLVM_ABI Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static Constant * getGetElementPtr(Type *Ty, Constant *C, ArrayRef< Constant * > IdxList, GEPNoWrapFlags NW=GEPNoWrapFlags::none(), std::optional< ConstantRange > InRange=std::nullopt, Type *OnlyIfReducedTy=nullptr)
Getelementptr form.
static LLVM_ABI Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
static LLVM_ABI Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
This is the shared class of boolean and integer constants.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
static LLVM_ABI ConstantInt * getBool(LLVMContext &Context, bool V)
This class represents a range of values.
LLVM_ABI ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
LLVM_ABI ConstantRange zextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
PreferredRangeType
If represented precisely, the result of some range operations may consist of multiple disjoint ranges...
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
LLVM_ABI bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other?
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI ConstantRange zeroExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
LLVM_ABI bool isSignWrappedSet() const
Return true if this set wraps around the signed domain.
LLVM_ABI APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
LLVM_ABI bool isWrappedSet() const
Return true if this set wraps around the unsigned domain.
LLVM_ABI void print(raw_ostream &OS) const
Print out the bounds to a stream.
LLVM_ABI ConstantRange truncate(uint32_t BitWidth, unsigned NoWrapKind=0) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
LLVM_ABI ConstantRange signExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI bool contains(const APInt &Val) const
Return true if the specified value is in the set.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
LLVM_ABI ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
LLVM_ABI APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
static LLVM_ABI ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
LLVM_ABI unsigned getMinSignedBits() const
Compute the maximal number of bits needed to represent every value in this signed range.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
LLVM_ABI ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
LLVM_ABI ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
static LLVM_ABI ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)
Produce the range that contains X if and only if "X BinOp Other" does not wrap.
This is an important base class in LLVM.
A parsed version of the target data layout string in and methods for querying it.
LLVM_ABI const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
LLVM_ABI IntegerType * getIntPtrType(LLVMContext &C, unsigned AddressSpace=0) const
Returns an integer type with size at least as big as that of a pointer in the given address space.
LLVM_ABI unsigned getIndexTypeSizeInBits(Type *Ty) const
The size in bits of the index used in GEP calculation for this type.
LLVM_ABI IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
TypeSize getTypeSizeInBits(Type *Ty) const
Size examples:
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive,...
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Analysis pass which computes a DominatorTree.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID,...
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Represents flags for the getelementptr instruction/expression.
bool hasNoUnsignedSignedWrap() const
bool hasNoUnsignedWrap() const
static GEPNoWrapFlags none()
static LLVM_ABI Type * getTypeAtIndex(Type *Ty, Value *Idx)
Return the type of the element at the given index of an indexable type.
Module * getParent()
Get the module that this global value is contained inside of...
static bool isPrivateLinkage(LinkageTypes Linkage)
static bool isInternalLinkage(LinkageTypes Linkage)
This instruction compares its operands according to the predicate given to the constructor.
CmpPredicate getCmpPredicate() const
static bool isGE(Predicate P)
Return true if the predicate is SGE or UGE.
CmpPredicate getSwappedCmpPredicate() const
static LLVM_ABI bool compare(const APInt &LHS, const APInt &RHS, ICmpInst::Predicate Pred)
Return result of LHS Pred RHS comparison.
static bool isLT(Predicate P)
Return true if the predicate is SLT or ULT.
CmpPredicate getInverseCmpPredicate() const
Predicate getNonStrictCmpPredicate() const
For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.
static bool isGT(Predicate P)
Return true if the predicate is SGT or UGT.
Predicate getFlippedSignednessPredicate() const
For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->EQ.
static CmpPredicate getInverseCmpPredicate(CmpPredicate Pred)
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
static bool isLE(Predicate P)
Return true if the predicate is SLE or ULE.
LLVM_ABI bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
LLVM_ABI bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
LLVM_ABI bool isIdenticalToWhenDefined(const Instruction *I, bool IntersectAttrs=false) const LLVM_READONLY
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...
Class to represent integer types.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
An instruction for reading from memory.
Analysis pass that exposes the LoopInfo for a function.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getHeader() const
unsigned getLoopDepth() const
Return the nesting level of this loop.
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
A Module instance is used to store all the information related to an LLVM module.
unsigned getOpcode() const
Return the opcode for this Instruction or ConstantExpr.
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
bool hasNoSignedWrap() const
Test whether this operation is known to never undergo signed overflow, aka the nsw property.
bool hasNoUnsignedWrap() const
Test whether this operation is known to never undergo unsigned overflow, aka the nuw property.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
PointerIntPair - This class implements a pair of a pointer and small integer.
static PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the default address space (address sp...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
LLVM_ABI void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
LLVM_ABI const SCEVPredicate & getPredicate() const
LLVM_ABI bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've proved that V doesn't wrap by means of a SCEV predicate.
LLVM_ABI void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Proves that V doesn't overflow by adding SCEV predicate.
LLVM_ABI void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
LLVM_ABI bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds.
LLVM_ABI PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
LLVM_ABI const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
LLVM_ABI unsigned getSmallConstantMaxTripCount()
Returns the upper bound of the loop trip count as a normal unsigned value, or 0 if the trip count is ...
LLVM_ABI const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSymbolicMaxBackedgeTakenCount()
Get the (predicated) symbolic max backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
constexpr bool isValid() const
This node represents an addition of some number of SCEVs.
This node represents a polynomial recurrence on the trip count of the specified loop.
friend class ScalarEvolution
const SCEV * getStart() const
LLVM_ABI const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a recurrence without clearing any previously set flags.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
bool isQuadratic() const
Return true if this represents an expression A + B*x + C*x^2 where A, B and C are loop invariant valu...
LLVM_ABI const SCEV * getNumIterationsInRange(const ConstantRange &Range, ScalarEvolution &SE) const
Return the number of iterations of this loop that produce values in the specified constant range.
LLVM_ABI const SCEVAddRecExpr * getPostIncExpr(ScalarEvolution &SE) const
Return an expression representing the value of this expression one iteration of the loop ahead.
const Loop * getLoop() const
This is the base class for unary cast operator classes.
const SCEV * getOperand() const
LLVM_ABI SCEVCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, const SCEV *op, Type *ty)
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a non-recurrence without clearing previously set flags.
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
SCEVComparePredicate(const FoldingSetNodeIDRef ID, const ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Implementation of the SCEVPredicate interface.
This class represents a constant integer value.
ConstantInt * getValue() const
const APInt & getAPInt() const
This is the base class for unary integral cast operator classes.
LLVM_ABI SCEVIntegralCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, const SCEV *op, Type *ty)
This node is the base class min/max selections.
static enum SCEVTypes negate(enum SCEVTypes T)
This node represents multiplication of some number of SCEVs.
This node is a base class providing common functionality for n'ary operators.
bool hasNoUnsignedWrap() const
bool hasNoSelfWrap() const
size_t getNumOperands() const
bool hasNoSignedWrap() const
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
const SCEV * getOperand(unsigned i) const
const SCEV *const * Operands
ArrayRef< const SCEV * > operands() const
This class represents an assumption made using SCEV expressions which can be checked at run-time.
SCEVPredicate(const SCEVPredicate &)=default
virtual bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const =0
Returns true if this predicate implies N.
This class represents a cast from a pointer to a pointer-sized integer value.
This visitor recursively visits a SCEV expression and re-writes it.
const SCEV * visitSignExtendExpr(const SCEVSignExtendExpr *Expr)
const SCEV * visit(const SCEV *S)
const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)
const SCEV * visitSMinExpr(const SCEVSMinExpr *Expr)
const SCEV * visitUMinExpr(const SCEVUMinExpr *Expr)
This class represents a signed minimum selection.
This node is the base class for sequential/in-order min/max selections.
static SCEVTypes getEquivalentNonSequentialSCEVType(SCEVTypes Ty)
This class represents a sign extension of a small integer value to a larger integer value.
Visit all nodes in the expression tree using worklist traversal.
This class represents a truncation of an integer value to a smaller integer value.
This class represents a binary unsigned division operation.
const SCEV * getLHS() const
const SCEV * getRHS() const
This class represents an unsigned minimum selection.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
void print(raw_ostream &OS, unsigned Depth) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Returns true if this predicate implies N.
SCEVUnionPredicate(ArrayRef< const SCEVPredicate * > Preds, ScalarEvolution &SE)
Union predicates don't get cached so create a dummy set ID for it.
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents the value of vscale, as used when defining the length of a scalable vector or r...
This class represents an assumption made on an AddRec expression.
IncrementWrapFlags
Similar to SCEV::NoWrapFlags, but with slightly different semantics for FlagNUSW.
SCEVWrapPredicate(const FoldingSetNodeIDRef ID, const SCEVAddRecExpr *AR, IncrementWrapFlags Flags)
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Returns true if this predicate implies N.
static SCEVWrapPredicate::IncrementWrapFlags setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OnFlags)
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
const SCEVAddRecExpr * getExpr() const
Implementation of the SCEVPredicate interface.
static SCEVWrapPredicate::IncrementWrapFlags clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OffFlags)
Convenient IncrementWrapFlags manipulation methods.
static SCEVWrapPredicate::IncrementWrapFlags getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE)
Returns the set of SCEVWrapPredicate no wrap flags implied by a SCEVAddRecExpr.
IncrementWrapFlags getFlags() const
Returns the set assumed no overflow flags.
This class represents a zero extension of a small integer value to a larger integer value.
This class represents an analyzed expression in the program.
LLVM_ABI ArrayRef< const SCEV * > operands() const
Return operands of this SCEV expression.
unsigned short getExpressionSize() const
LLVM_ABI bool isOne() const
Return true if the expression is a constant one.
LLVM_ABI bool isZero() const
Return true if the expression is a constant zero.
LLVM_ABI void dump() const
This method is used for debugging.
LLVM_ABI bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
LLVM_ABI bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
LLVM_ABI void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
SCEV(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, unsigned short ExpressionSize)
SCEVTypes getSCEVType() const
LLVM_ABI Type * getType() const
Return the LLVM type of this SCEV expression.
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
Analysis pass that exposes the ScalarEvolution for a function.
LLVM_ABI ScalarEvolution run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
void print(raw_ostream &OS, const Module *=nullptr) const override
print - Print out the internal state of the pass.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
ScalarEvolutionWrapperPass()
static LLVM_ABI LoopGuards collect(const Loop *L, ScalarEvolution &SE)
Collect rewrite map for loop guards for loop L, together with flags indicating if NUW and NSW can be ...
LLVM_ABI const SCEV * rewrite(const SCEV *Expr) const
Try to apply the collected loop guards to Expr.
The main scalar evolution driver.
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
static bool hasFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags TestFlags)
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
LLVM_ABI bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
LLVM_ABI bool isKnownOnEveryIteration(CmpPredicate Pred, const SCEVAddRecExpr *LHS, const SCEV *RHS)
Test if the condition described by Pred, LHS, RHS is known to be true on every iteration of the loop ...
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterationsImpl(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
LLVM_ABI const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI const SCEV * getUDivCeilSCEV(const SCEV *N, const SCEV *D)
Compute ceil(N / D).
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterations(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L at given Context duri...
LLVM_ABI Type * getWiderType(Type *Ty1, Type *Ty2) const
LLVM_ABI const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)
LLVM_ABI bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
LLVM_ABI const SCEV * getURemExpr(const SCEV *LHS, const SCEV *RHS)
Represents an unsigned remainder expression based on unsigned division.
LLVM_ABI bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
LLVM_ABI const SCEV * getPredicatedConstantMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getConstantMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
LLVM_ABI bool isLoopEntryGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
LLVM_ABI bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
LLVM_ABI const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
LLVM_ABI const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
LLVM_ABI const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags)
Update no-wrap flags of an AddRec.
LLVM_ABI const SCEV * getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS)
Promote the operands to the wider of the types using zero-extension, and then perform a umax operatio...
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
LLVM_ABI bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?
LLVM_ABI ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsOnlyExit, bool AllowPredicates=false)
Compute the number of times the backedge of the specified loop will execute if its exit condition wer...
LLVM_ABI const SCEV * getZeroExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
LLVM_ABI uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
LLVM_ABI const SCEV * getConstant(ConstantInt *V)
LLVM_ABI const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
LLVM_ABI const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
LLVM_ABI const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
LLVM_ABI ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI)
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LLVM_ABI const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI const SCEV * getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty)
LLVM_ABI const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
LLVM_ABI const SCEV * getLosslessPtrToIntExpr(const SCEV *Op, unsigned Depth=0)
LLVM_ABI std::optional< bool > evaluatePredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Check whether the condition described by Pred, LHS, and RHS is true or false in the given Context.
LLVM_ABI unsigned getSmallConstantMaxTripCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Returns the upper bound of the loop trip count as a normal unsigned value.
LLVM_ABI const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
LLVM_ABI bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
LLVM_ABI void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
LLVM_ABI bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
LLVM_ABI bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
APInt getUnsignedRangeMin(const SCEV *S)
Determine the min of the unsigned range for a particular SCEV.
LLVM_ABI bool SimplifyICmpOperands(CmpPredicate &Pred, const SCEV *&LHS, const SCEV *&RHS, unsigned Depth=0)
Simplify LHS and RHS in a comparison with predicate Pred.
LLVM_ABI const SCEV * getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo)
Return an expression for offsetof on the given field with type IntTy.
LLVM_ABI LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
LLVM_ABI bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
LLVM_ABI const SCEV * getSignExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
LLVM_ABI bool hasOperand(const SCEV *S, const SCEV *Op) const
Test whether the given SCEV has Op as a direct or indirect operand.
LLVM_ABI const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
LLVM_ABI const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
LLVM_ABI Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
LLVM_ABI const SCEVPredicate * getComparePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
LLVM_ABI const SCEV * getNotSCEV(const SCEV *V)
Return the SCEV object corresponding to ~V.
LLVM_ABI const SCEV * getElementCount(Type *Ty, ElementCount EC, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
LLVM_ABI bool instructionCouldExistWithOperands(const SCEV *A, const SCEV *B)
Return true if there exists a point in the program at which both A and B could be operands to the sam...
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
LLVM_ABI void print(raw_ostream &OS) const
LLVM_ABI const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
LLVM_ABI const SCEV * getPredicatedExitCount(const Loop *L, const BasicBlock *ExitingBlock, SmallVectorImpl< const SCEVPredicate * > *Predicates, ExitCountKind Kind=Exact)
Same as above except this uses the predicated backedge taken info and may require predicates.
static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
LLVM_ABI void forgetTopmostLoop(const Loop *L)
LLVM_ABI void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
APInt getSignedRangeMin(const SCEV *S)
Determine the min of the signed range for a particular SCEV.
LLVM_ABI const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
LLVM_ABI const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
@ MonotonicallyDecreasing
@ MonotonicallyIncreasing
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI=nullptr)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L, return a LoopInvaria...
LLVM_ABI const SCEV * getStoreSizeOfExpr(Type *IntTy, Type *StoreTy)
Return an expression for the store size of StoreTy that is type IntTy.
LLVM_ABI const SCEVPredicate * getWrapPredicate(const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
LLVM_ABI bool isLoopBackedgeGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether the backedge of the loop is protected by a conditional between LHS and RHS.
LLVM_ABI const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
LLVM_ABI APInt getNonZeroConstantMultiple(const SCEV *S)
const SCEV * getMinusOne(Type *Ty)
Return a SCEV for the constant -1 of a specific type.
static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
LLVM_ABI bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
LLVM_ABI BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB)
Return the "disposition" of the given SCEV with respect to the given block.
LLVM_ABI const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
LLVM_ABI const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
Promote the operands to the wider of the types using zero-extension, and then perform a umin operatio...
LLVM_ABI bool loopIsFiniteByAssumption(const Loop *L)
Return true if this loop is finite by assumption.
LLVM_ABI const SCEV * getExistingSCEV(Value *V)
Return an existing SCEV for V if there is one, otherwise return nullptr.
LLVM_ABI APInt getConstantMultiple(const SCEV *S, const Instruction *CtxI=nullptr)
Returns the max constant multiple of S.
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
@ LoopComputable
The SCEV varies predictably with the loop.
@ LoopVariant
The SCEV is loop-variant (unknown).
@ LoopInvariant
The SCEV is loop-invariant.
friend class SCEVCallbackVH
LLVM_ABI bool isKnownMultipleOf(const SCEV *S, uint64_t M, SmallVectorImpl< const SCEVPredicate * > &Assumptions)
Check that S is a multiple of M.
LLVM_ABI const SCEV * getAnyExtendExpr(const SCEV *Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
LLVM_ABI bool isKnownToBeAPowerOfTwo(const SCEV *S, bool OrZero=false, bool OrNegative=false)
Test if the given expression is known to be a power of 2.
LLVM_ABI std::optional< SCEV::NoWrapFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
LLVM_ABI void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)
Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...
LLVM_ABI bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
LLVM_ABI std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
LLVM_ABI const SCEV * getCouldNotCompute()
LLVM_ABI bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
LLVM_ABI uint32_t getMinTrailingZeros(const SCEV *S, const Instruction *CtxI=nullptr)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
@ DominatesBlock
The SCEV dominates the block.
@ ProperlyDominatesBlock
The SCEV properly dominates the block.
@ DoesNotDominateBlock
The SCEV does not dominate the block.
LLVM_ABI const SCEV * getGEPExpr(GEPOperator *GEP, ArrayRef< const SCEV * > IndexExprs)
Returns an expression for a GEP.
LLVM_ABI const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
LLVM_ABI const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI void getPoisonGeneratingValues(SmallPtrSetImpl< const Value * > &Result, const SCEV *S)
Return the set of Values that, if poison, will definitively result in S being poison as well.
LLVM_ABI void forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
LLVM_ABI const SCEV * getVScale(Type *Ty)
LLVM_ABI unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
LLVM_ABI bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
LLVM_ABI const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
LLVM_ABI const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
LLVM_ABI void forgetAllLoops()
LLVM_ABI bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
APInt getUnsignedRangeMax(const SCEV *S)
Determine the max of the unsigned range for a particular SCEV.
ExitCountKind
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of ...
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
@ ConstantMaximum
A constant which provides an upper bound on the exact trip count.
@ Exact
An expression exactly describing the number of times the backedge has executed when a loop is exited.
LLVM_ABI const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
LLVM_ABI const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
LLVM_ABI const SCEVAddRecExpr * convertSCEVToAddRecWithPredicates(const SCEV *S, const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Preds)
Tries to convert the S expression to an AddRec expression, adding additional predicates to Preds as r...
LLVM_ABI const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
LLVM_ABI const SCEV * getSizeOfExpr(Type *IntTy, TypeSize Size)
Return an expression for a TypeSize.
LLVM_ABI std::optional< bool > evaluatePredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Check whether the condition described by Pred, LHS, and RHS is true or false.
LLVM_ABI const SCEV * getUnknown(Value *V)
LLVM_ABI std::optional< std::pair< const SCEV *, SmallVector< const SCEVPredicate *, 3 > > > createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI)
Checks if SymbolicPHI can be rewritten as an AddRecExpr under some Predicates.
LLVM_ABI const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask)
Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name ...
LLVM_ABI std::optional< APInt > computeConstantDifference(const SCEV *LHS, const SCEV *RHS)
Compute LHS - RHS and returns the result as an APInt if it is a constant, and std::nullopt if it isn'...
LLVM_ABI bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
LLVM_ABI const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
LLVM_ABI std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
LLVM_ABI bool canReuseInstruction(const SCEV *S, Instruction *I, SmallVectorImpl< Instruction * > &DropPoisonGeneratingInsts)
Check whether it is poison-safe to represent the expression S using the instruction I.
LLVM_ABI bool isKnownPredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * getPredicatedSymbolicMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getSymbolicMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI ~ScalarEvolution()
LLVM_ABI const SCEV * getUDivExactExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
LLVM_ABI void registerUser(const SCEV *User, ArrayRef< const SCEV * > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
LLVM_ABI const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
LLVM_ABI bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the basic block is protected by a conditional between LHS and RHS.
LLVM_ABI const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool containsErasedValue(const SCEV *S) const
Return true if the SCEV expression contains a Value that has been optimised out and is now a nullptr.
LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI bool isKnownViaInduction(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
We'd like to check the predicate on every iteration of the most dominated loop between loops used in ...
const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
LLVM_ABI void verify() const
LLVMContext & getContext() const
Implements a dense probed hash-table based set with some number of buckets stored inline.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
TypeSize getElementOffset(unsigned Idx) const
TypeSize getSizeInBits() const
Class to represent struct types.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)
bool isPointerTy() const
True if this is an instance of PointerType.
static LLVM_ABI IntegerType * getInt8Ty(LLVMContext &C)
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntOrPtrTy() const
Return true if this is an integer type or a pointer type.
bool isIntegerTy() const
True if this is an instance of IntegerType.
static LLVM_ABI IntegerType * getIntNTy(LLVMContext &C, unsigned N)
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
unsigned getValueID() const
Return an ID for the concrete type of this object.
LLVM_ABI void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
LLVM_ABI LLVMContext & getContext() const
All values hold a context through their type.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
const ParentTy * getParent() const
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
LLVM_ABI std::optional< APInt > SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, unsigned RangeWidth)
Let q(n) = An^2 + Bn + C, and BW = bit width of the value range (e.g.
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
LLVM_ABI APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
int getMinValue(MCInstrInfo const &MCII, MCInst const &MCI)
Return the minimum value of an extendable operand.
@ BasicBlock
Various leaf nodes.
LLVM_ABI Function * getDeclarationIfExists(const Module *M, ID id)
Look up the Function declaration of the intrinsic id in the Module M and return it if it exists.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
IntrinsicID_match m_Intrinsic()
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
bind_ty< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
class_match< const SCEVVScale > m_SCEVVScale()
bind_cst_ty m_scev_APInt(const APInt *&C)
Match an SCEV constant and bind it to an APInt.
cst_pred_ty< is_all_ones > m_scev_AllOnes()
Match an integer with all bits set.
SCEVUnaryExpr_match< SCEVZeroExtendExpr, Op0_t > m_scev_ZExt(const Op0_t &Op0)
SCEVBinaryExpr_match< SCEVMinMaxExpr, Op0_t, Op1_t > m_scev_MinMax(const Op0_t &Op0, const Op1_t &Op1)
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()
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...
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
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)
constexpr from_range_t from_range
auto dyn_cast_if_present(const Y &Val)
dyn_cast_if_present<X> - Functionally identical to dyn_cast, except that a null (or none in the case ...
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
unsigned short computeExpressionSize(ArrayRef< const SCEV * > Args)
auto uninitialized_copy(R &&Src, IterTy Dst)
bool isa_and_nonnull(const Y &Val)
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO, const DominatorTree &DT)
Returns true if the arithmetic part of the WO 's result is used only along the paths control dependen...
DomTreeNodeBase< BasicBlock > DomTreeNode
LLVM_ABI bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step)
Attempt to match a simple first order recurrence cycle of the form: iv = phi Ty [Start,...
auto dyn_cast_or_null(const Y &Val)
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
iterator_range< pointee_iterator< WrappedIteratorT > > make_pointee_range(RangeT &&Range)
auto reverse(ContainerTy &&C)
LLVM_ABI bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
LLVM_ABI bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
LLVM_ABI bool isFinite(const Loop *L)
Return true if this loop can be assumed to run for a finite number of iterations.
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
LLVM_ABI bool programUndefinedIfPoison(const Instruction *Inst)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isPointerTy(const Type *T)
FunctionAddr VTableAddr Count
LLVM_ABI ConstantRange getVScaleRange(const Function *F, unsigned BitWidth)
Determine the possible constant range of vscale with the given bit width, based on the vscale_range f...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
LLVM_ABI bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)
Return true if the given value is known to be non-zero when defined.
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
LLVM_ABI bool propagatesPoison(const Use &PoisonOp)
Return true if PoisonOp's user yields poison or raises UB if its operand PoisonOp is poison.
@ UMin
Unsigned integer min implemented in terms of select(cmp()).
@ Mul
Product of integers.
@ SMax
Signed integer max implemented in terms of select(cmp()).
@ SMin
Signed integer min implemented in terms of select(cmp()).
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
DWARFExpression::Operation Op
auto max_element(R &&Range)
Provide wrappers to std::max_element which take ranges instead of having to pass begin/end explicitly...
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
ArrayRef(const T &OneElt) -> ArrayRef< T >
LLVM_ABI unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Return the number of times the sign bit of the register is replicated into the other bits.
constexpr unsigned BitWidth
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
constexpr bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
iterator_range< df_iterator< T > > depth_first(const T &G)
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be poison, but may be undef.
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
Implement std::hash so that hash_code can be used in STL containers.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
A special type used by analysis passes to provide an address that identifies that particular analysis...
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
bool isNonNegative() const
Returns true if this value is known to be non-negative.
static LLVM_ABI KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for ashr(LHS, RHS).
unsigned getBitWidth() const
Get the bit width of this value.
static LLVM_ABI KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for lshr(LHS, RHS).
KnownBits zextOrTrunc(unsigned BitWidth) const
Return known bits for a zero extension or truncation of the value we're tracking.
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
APInt getMinValue() const
Return the minimal unsigned value possible given these KnownBits.
bool isNegative() const
Returns true if this value is known to be negative.
static LLVM_ABI KnownBits shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW=false, bool NSW=false, bool ShAmtNonZero=false)
Compute known bits for shl(LHS, RHS).
An object of this class is returned by queries that could not be answered.
LLVM_ABI SCEVCouldNotCompute()
static LLVM_ABI bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This class defines a simple visitor class that may be used for various SCEV analysis purposes.
A utility class that uses RAII to save and restore the value of a variable.
Information about the number of loop iterations for which a loop exit's branch condition evaluates to...
LLVM_ABI ExitLimit(const SCEV *E)
Construct either an exact exit limit from a constant, or an unknown one from a SCEVCouldNotCompute.
const SCEV * ExactNotTaken
const SCEV * SymbolicMaxNotTaken
SmallVector< const SCEVPredicate *, 4 > Predicates
A vector of predicate guards for this ExitLimit.
const SCEV * ConstantMaxNotTaken