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)) {
1777 if (matchURem(
Op, LHS, RHS))
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())
1843 if (SM->getNumOperands() == 2)
1845 if (MulLHS->getAPInt().isPowerOf2())
1848 MulLHS->getAPInt().logBase2();
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();
2702 if (
Ops.size() == 2) {
2704 if (
Mul &&
Mul->getNumOperands() == 2 &&
2705 Mul->getOperand(0)->isAllOnesValue()) {
2708 if (matchURem(
Mul->getOperand(1),
X,
Y) &&
X ==
Ops[1]) {
2719 if (Idx <
Ops.size()) {
2720 bool DeletedAdd =
false;
2731 Ops.erase(
Ops.begin()+Idx);
2734 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2757 struct APIntCompare {
2758 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2759 return LHS.ult(RHS);
2766 std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists;
2767 for (
const SCEV *NewOp : NewOps)
2768 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2771 if (AccumulatedConstant != 0)
2773 for (
auto &MulOp : MulOpLists) {
2774 if (MulOp.first == 1) {
2776 }
else if (MulOp.first != 0) {
2785 if (
Ops.size() == 1)
2796 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2797 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2800 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp)
2801 if (MulOpSCEV ==
Ops[AddOp]) {
2803 const SCEV *InnerMul =
Mul->getOperand(MulOp == 0);
2804 if (
Mul->getNumOperands() != 2) {
2808 Mul->operands().take_front(MulOp));
2816 if (
Ops.size() == 2)
return OuterMul;
2818 Ops.erase(
Ops.begin()+AddOp);
2819 Ops.erase(
Ops.begin()+Idx-1);
2821 Ops.erase(
Ops.begin()+Idx);
2822 Ops.erase(
Ops.begin()+AddOp-1);
2824 Ops.push_back(OuterMul);
2829 for (
unsigned OtherMulIdx = Idx+1;
2836 OMulOp != e; ++OMulOp)
2837 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2839 const SCEV *InnerMul1 =
Mul->getOperand(MulOp == 0);
2840 if (
Mul->getNumOperands() != 2) {
2842 Mul->operands().take_front(MulOp));
2849 OtherMul->
operands().take_front(OMulOp));
2854 const SCEV *InnerMulSum =
2858 if (
Ops.size() == 2)
return OuterMul;
2859 Ops.erase(
Ops.begin()+Idx);
2860 Ops.erase(
Ops.begin()+OtherMulIdx-1);
2861 Ops.push_back(OuterMul);
2881 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2884 Ops.erase(
Ops.begin()+i);
2889 if (!LIOps.
empty()) {
2914 auto *DefI = getDefiningScopeBound(LIOps);
2916 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2928 if (
Ops.size() == 1)
return NewRec;
2931 for (
unsigned i = 0;; ++i)
2932 if (
Ops[i] == AddRec) {
2942 for (
unsigned OtherIdx = Idx+1;
2950 "AddRecExprs are not sorted in reverse dominance order?");
2957 if (OtherAddRec->getLoop() == AddRecLoop) {
2958 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2960 if (i >= AddRecOps.
size()) {
2961 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2965 AddRecOps[i], OtherAddRec->getOperand(i)};
2968 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
2983 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2995 static_cast<SCEVAddExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
2999 S =
new (SCEVAllocator)
3001 UniqueSCEVs.InsertNode(S, IP);
3011 FoldingSetNodeID
ID;
3013 for (
const SCEV *
Op :
Ops)
3018 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3020 const SCEV **
O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
3022 S =
new (SCEVAllocator)
3023 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3024 UniqueSCEVs.InsertNode(S, IP);
3025 LoopUsers[
L].push_back(S);
3035 FoldingSetNodeID
ID;
3037 for (
const SCEV *
Op :
Ops)
3041 static_cast<SCEVMulExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3043 const SCEV **
O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
3045 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3047 UniqueSCEVs.InsertNode(S, IP);
3056 if (j > 1 && k / j != i) Overflow =
true;
3072 if (n == 0 || n == k)
return 1;
3073 if (k > n)
return 0;
3079 for (
uint64_t i = 1; i <= k; ++i) {
3080 r =
umul_ov(r, n-(i-1), Overflow);
3089 struct FindConstantInAddMulChain {
3090 bool FoundConstant =
false;
3092 bool follow(
const SCEV *S) {
3097 bool isDone()
const {
3098 return FoundConstant;
3102 FindConstantInAddMulChain
F;
3104 ST.visitAll(StartExpr);
3105 return F.FoundConstant;
3113 "only nuw or nsw allowed");
3114 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3115 if (
Ops.size() == 1)
return Ops[0];
3117 Type *ETy =
Ops[0]->getType();
3119 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3121 "SCEVMulExpr operand types don't match!");
3126 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3127 [](
const APInt &
C) {
return C.isOne(); },
3128 [](
const APInt &
C) {
return C.isZero(); });
3139 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3144 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3145 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3150 if (
Ops.size() == 2) {
3167 if (
Ops[0]->isAllOnesValue()) {
3172 bool AnyFolded =
false;
3173 for (
const SCEV *AddOp :
Add->operands()) {
3200 AddRec->getNoWrapFlags(FlagsMask));
3223 const APInt &LHSV = LHSC->getAPInt();
3239 if (Idx <
Ops.size()) {
3240 bool DeletedMul =
false;
3246 Ops.erase(
Ops.begin()+Idx);
3270 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3273 Ops.erase(
Ops.begin()+i);
3278 if (!LIOps.
empty()) {
3291 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3307 if (
Ops.size() == 1)
return NewRec;
3310 for (
unsigned i = 0;; ++i)
3311 if (
Ops[i] == AddRec) {
3332 bool OpsModified =
false;
3333 for (
unsigned OtherIdx = Idx+1;
3347 bool Overflow =
false;
3354 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3358 z < ze && !Overflow; ++z) {
3361 if (LargerThan64Bits)
3362 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3364 Coeff = Coeff1*Coeff2;
3379 if (
Ops.size() == 2)
return NewAddRec;
3380 Ops[Idx] = NewAddRec;
3381 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3397 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3405 "SCEVURemExpr operand types don't match!");
3410 if (RHSC->getValue()->isOne())
3411 return getZero(LHS->getType());
3414 if (RHSC->getAPInt().isPowerOf2()) {
3415 Type *FullTy = LHS->getType();
3432 assert(!LHS->getType()->isPointerTy() &&
3433 "SCEVUDivExpr operand can't be pointer!");
3434 assert(LHS->getType() == RHS->getType() &&
3435 "SCEVUDivExpr operand types don't match!");
3442 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3450 if (RHSC->getValue()->isOne())
3455 if (!RHSC->getValue()->isZero()) {
3459 Type *Ty = LHS->getType();
3460 unsigned LZ = RHSC->getAPInt().countl_zero();
3464 if (!RHSC->getAPInt().isPowerOf2())
3472 const APInt &StepInt = Step->getAPInt();
3473 const APInt &DivInt = RHSC->getAPInt();
3474 if (!StepInt.
urem(DivInt) &&
3480 for (
const SCEV *
Op : AR->operands())
3488 if (StartC && !DivInt.
urem(StepInt) &&
3494 const APInt &StartRem = StartInt.
urem(StepInt);
3495 if (StartRem != 0) {
3496 const SCEV *NewLHS =
3499 if (LHS != NewLHS) {
3509 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3518 for (
const SCEV *
Op : M->operands())
3522 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3523 const SCEV *
Op = M->getOperand(i);
3535 if (
auto *DivisorConstant =
3537 bool Overflow =
false;
3539 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3550 for (
const SCEV *
Op :
A->operands())
3554 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3561 if (
Operands.size() ==
A->getNumOperands())
3568 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3574 AE && AE->getNumOperands() == 2) {
3576 const APInt &NegC = VC->getAPInt();
3579 if (MME && MME->getNumOperands() == 2 &&
3582 MME->getOperand(1) == RHS)
3583 return getZero(LHS->getType());
3591 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
3594 UniqueSCEVs.InsertNode(S, IP);
3624 if (!
Mul || !
Mul->hasNoUnsignedWrap())
3631 if (LHSCst == RHSCst) {
3639 APInt Factor =
gcd(LHSCst, RHSCst);
3657 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3658 if (
Mul->getOperand(i) == RHS) {
3677 if (StepChrec->getLoop() == L) {
3696 "SCEVAddRecExpr operand types don't match!");
3697 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3701 "SCEVAddRecExpr operand is not available at loop entry!");
3719 const Loop *NestedLoop = NestedAR->getLoop();
3720 if (L->contains(NestedLoop)
3723 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3725 Operands[0] = NestedAR->getStart();
3729 bool AllInvariant =
all_of(
3741 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3752 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3762 return getOrCreateAddRecExpr(
Operands, L, Flags);
3780 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3791 bool FirstIter =
true;
3793 for (
const SCEV *IndexExpr : IndexExprs) {
3800 Offsets.push_back(FieldOffset);
3803 CurTy = STy->getTypeAtIndex(Index);
3808 "The first index of a GEP indexes a pointer");
3809 CurTy =
GEP->getSourceElementType();
3820 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3821 Offsets.push_back(LocalOffset);
3826 if (Offsets.empty())
3839 "GEP should not change type mid-flight.");
3843SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3846 ID.AddInteger(SCEVType);
3850 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3860 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3861 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3862 if (
Ops.size() == 1)
return Ops[0];
3865 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3867 "Operand types don't match!");
3870 "min/max should be consistently pointerish");
3896 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3898 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3903 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3905 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3911 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3917 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3922 if (Idx <
Ops.size()) {
3923 bool DeletedAny =
false;
3924 while (
Ops[Idx]->getSCEVType() == Kind) {
3926 Ops.erase(
Ops.begin()+Idx);
3944 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3945 if (
Ops[i] ==
Ops[i + 1] ||
3946 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3949 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3952 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3955 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3961 if (
Ops.size() == 1)
return Ops[0];
3963 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
3968 ID.AddInteger(Kind);
3972 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3974 return ExistingSCEV;
3975 const SCEV **O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
3977 SCEV *S =
new (SCEVAllocator)
3980 UniqueSCEVs.InsertNode(S, IP);
3987class SCEVSequentialMinMaxDeduplicatingVisitor final
3988 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
3989 std::optional<const SCEV *>> {
3990 using RetVal = std::optional<const SCEV *>;
3998 bool canRecurseInto(
SCEVTypes Kind)
const {
4001 return RootKind == Kind || NonSequentialRootKind == Kind;
4004 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
4006 "Only for min/max expressions.");
4009 if (!canRecurseInto(Kind))
4019 return std::nullopt;
4026 RetVal
visit(
const SCEV *S) {
4028 if (!SeenOps.
insert(S).second)
4029 return std::nullopt;
4030 return Base::visit(S);
4034 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4036 : SE(SE), RootKind(RootKind),
4037 NonSequentialRootKind(
4038 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4042 SmallVectorImpl<const SCEV *> &NewOps) {
4047 for (
const SCEV *
Op : OrigOps) {
4052 Ops.emplace_back(*NewOp);
4056 NewOps = std::move(
Ops);
4060 RetVal visitConstant(
const SCEVConstant *Constant) {
return Constant; }
4062 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4064 RetVal visitPtrToIntExpr(
const SCEVPtrToIntExpr *Expr) {
return Expr; }
4066 RetVal visitTruncateExpr(
const SCEVTruncateExpr *Expr) {
return Expr; }
4068 RetVal visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
return Expr; }
4070 RetVal visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
return Expr; }
4072 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4074 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4076 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4078 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4080 RetVal visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
4081 return visitAnyMinMaxExpr(Expr);
4084 RetVal visitUMaxExpr(
const SCEVUMaxExpr *Expr) {
4085 return visitAnyMinMaxExpr(Expr);
4088 RetVal visitSMinExpr(
const SCEVSMinExpr *Expr) {
4089 return visitAnyMinMaxExpr(Expr);
4092 RetVal visitUMinExpr(
const SCEVUMinExpr *Expr) {
4093 return visitAnyMinMaxExpr(Expr);
4096 RetVal visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *Expr) {
4097 return visitAnyMinMaxExpr(Expr);
4100 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4102 RetVal visitCouldNotCompute(
const SCEVCouldNotCompute *Expr) {
return Expr; }
4144struct SCEVPoisonCollector {
4145 bool LookThroughMaybePoisonBlocking;
4146 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4147 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4148 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4150 bool follow(
const SCEV *S) {
4151 if (!LookThroughMaybePoisonBlocking &&
4161 bool isDone()
const {
return false; }
4171 SCEVPoisonCollector PC1(
true);
4176 if (PC1.MaybePoison.empty())
4182 SCEVPoisonCollector PC2(
false);
4192 SCEVPoisonCollector PC(
false);
4215 while (!Worklist.
empty()) {
4217 if (!Visited.
insert(V).second)
4221 if (Visited.
size() > 16)
4226 if (PoisonVals.
contains(V) || ::isGuaranteedNotToBePoison(V))
4237 if (PDI->isDisjoint())
4244 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4251 if (
I->hasPoisonGeneratingAnnotations())
4262 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4263 "Not a SCEVSequentialMinMaxExpr!");
4264 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4265 if (
Ops.size() == 1)
4269 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4271 "Operand types don't match!");
4274 "min/max should be consistently pointerish");
4282 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4289 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4299 bool DeletedAny =
false;
4300 while (Idx <
Ops.size()) {
4301 if (
Ops[Idx]->getSCEVType() != Kind) {
4306 Ops.erase(
Ops.begin() + Idx);
4307 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4308 SMME->operands().end());
4316 const SCEV *SaturationPoint;
4327 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4328 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4340 Ops.erase(
Ops.begin() + i);
4345 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4346 Ops.erase(
Ops.begin() + i);
4354 ID.AddInteger(Kind);
4358 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4360 return ExistingSCEV;
4362 const SCEV **O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
4364 SCEV *S =
new (SCEVAllocator)
4367 UniqueSCEVs.InsertNode(S, IP);
4415 if (
Size.isScalable())
4436 "Cannot get offset for structure containing scalable vector types");
4450 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP)) {
4452 "Stale SCEVUnknown in uniquing map!");
4458 UniqueSCEVs.InsertNode(S, IP);
4472 return Ty->isIntOrPtrTy();
4479 if (Ty->isPointerTy())
4490 if (Ty->isIntegerTy())
4494 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4506 bool PreciseA, PreciseB;
4507 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4508 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4509 if (!PreciseA || !PreciseB)
4512 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4513 DT.dominates(ScopeB, ScopeA);
4517 return CouldNotCompute.get();
4520bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4523 return SU && SU->getValue() ==
nullptr;
4526 return !ContainsNulls;
4531 if (
I != HasRecMap.end())
4536 HasRecMap.insert({S, FoundAddRec});
4544 if (
SI == ExprValueMap.
end())
4546 return SI->second.getArrayRef();
4552void ScalarEvolution::eraseValueFromMap(
Value *V) {
4554 if (
I != ValueExprMap.end()) {
4555 auto EVIt = ExprValueMap.find(
I->second);
4556 bool Removed = EVIt->second.remove(V);
4558 assert(Removed &&
"Value not in ExprValueMap?");
4559 ValueExprMap.erase(
I);
4563void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4567 auto It = ValueExprMap.find_as(V);
4568 if (It == ValueExprMap.end()) {
4570 ExprValueMap[S].insert(V);
4581 return createSCEVIter(V);
4588 if (
I != ValueExprMap.end()) {
4589 const SCEV *S =
I->second;
4590 assert(checkValidity(S) &&
4591 "existing SCEV has not been properly invalidated");
4604 Type *Ty = V->getType();
4612 if (!
Add ||
Add->getNumOperands() != 2 ||
4613 !
Add->getOperand(0)->isAllOnesValue())
4626 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4639 return (
const SCEV *)
nullptr;
4645 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4649 Type *Ty = V->getType();
4655 assert(
P->getType()->isPointerTy());
4668 const SCEV **PtrOp =
nullptr;
4669 for (
const SCEV *&AddOp :
Ops) {
4670 if (AddOp->getType()->isPointerTy()) {
4671 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4689 return getZero(LHS->getType());
4694 if (RHS->getType()->isPointerTy()) {
4695 if (!LHS->getType()->isPointerTy() ||
4705 const bool RHSIsNotMinSigned =
4736 Type *SrcTy = V->getType();
4737 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4738 "Cannot truncate or zero extend with non-integer arguments!");
4748 Type *SrcTy = V->getType();
4749 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4750 "Cannot truncate or zero extend with non-integer arguments!");
4760 Type *SrcTy = V->getType();
4761 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4762 "Cannot noop or zero extend with non-integer arguments!");
4764 "getNoopOrZeroExtend cannot truncate!");
4772 Type *SrcTy = V->getType();
4773 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4774 "Cannot noop or sign extend with non-integer arguments!");
4776 "getNoopOrSignExtend cannot truncate!");
4784 Type *SrcTy = V->getType();
4785 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4786 "Cannot noop or any extend with non-integer arguments!");
4788 "getNoopOrAnyExtend cannot truncate!");
4796 Type *SrcTy = V->getType();
4797 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4798 "Cannot truncate or noop with non-integer arguments!");
4800 "getTruncateOrNoop cannot extend!");
4808 const SCEV *PromotedLHS = LHS;
4809 const SCEV *PromotedRHS = RHS;
4829 assert(!
Ops.empty() &&
"At least one operand must be!");
4831 if (
Ops.size() == 1)
4835 Type *MaxType =
nullptr;
4836 for (
const auto *S :
Ops)
4841 assert(MaxType &&
"Failed to find maximum type!");
4845 for (
const auto *S :
Ops)
4854 if (!V->getType()->isPointerTy())
4859 V = AddRec->getStart();
4861 const SCEV *PtrOp =
nullptr;
4862 for (
const SCEV *AddOp :
Add->operands()) {
4863 if (AddOp->getType()->isPointerTy()) {
4864 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4868 assert(PtrOp &&
"Must have pointer op");
4880 for (
User *U :
I->users()) {
4882 if (Visited.
insert(UserInsn).second)
4896 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4897 bool IgnoreOtherLoops =
true) {
4900 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4902 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4907 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4909 SeenLoopVariantSCEVUnknown =
true;
4913 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4917 SeenOtherLoops =
true;
4921 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4923 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4926 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4927 : SCEVRewriteVisitor(SE),
L(
L) {}
4930 bool SeenLoopVariantSCEVUnknown =
false;
4931 bool SeenOtherLoops =
false;
4940 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4941 SCEVPostIncRewriter
Rewriter(L, SE);
4943 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4948 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4950 SeenLoopVariantSCEVUnknown =
true;
4954 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4958 SeenOtherLoops =
true;
4962 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4964 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4967 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4968 : SCEVRewriteVisitor(SE),
L(
L) {}
4971 bool SeenLoopVariantSCEVUnknown =
false;
4972 bool SeenOtherLoops =
false;
4978class SCEVBackedgeConditionFolder
4981 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4982 ScalarEvolution &SE) {
4983 bool IsPosBECond =
false;
4984 Value *BECond =
nullptr;
4985 if (BasicBlock *Latch =
L->getLoopLatch()) {
4989 "Both outgoing branches should not target same header!");
4996 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
5000 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5001 const SCEV *
Result = Expr;
5006 switch (
I->getOpcode()) {
5007 case Instruction::Select: {
5009 std::optional<const SCEV *> Res =
5010 compareWithBackedgeCondition(
SI->getCondition());
5018 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5029 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5030 bool IsPosBECond, ScalarEvolution &SE)
5031 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5032 IsPositiveBECond(IsPosBECond) {}
5034 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5038 Value *BackedgeCond =
nullptr;
5040 bool IsPositiveBECond;
5043std::optional<const SCEV *>
5044SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5049 if (BackedgeCond == IC)
5052 return std::nullopt;
5057 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5058 ScalarEvolution &SE) {
5064 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5071 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5078 bool isValid() {
return Valid; }
5081 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5082 : SCEVRewriteVisitor(SE),
L(
L) {}
5091ScalarEvolution::proveNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5095 using OBO = OverflowingBinaryOperator;
5103 const APInt &BECountAP = BECountMax->getAPInt();
5104 unsigned NoOverflowBitWidth =
5116 Instruction::Add, IncRange, OBO::NoSignedWrap);
5117 if (NSWRegion.contains(AddRecRange))
5126 Instruction::Add, IncRange, OBO::NoUnsignedWrap);
5127 if (NUWRegion.contains(AddRecRange))
5135ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5145 if (!SignedWrapViaInductionTried.insert(AR).second)
5170 AC.assumptions().empty())
5178 const SCEV *OverflowLimit =
5180 if (OverflowLimit &&
5188ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5198 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5224 AC.assumptions().empty())
5257 Operator *
Op =
nullptr;
5259 explicit BinaryOp(Operator *
Op)
5263 IsNSW = OBO->hasNoSignedWrap();
5264 IsNUW = OBO->hasNoUnsignedWrap();
5268 explicit BinaryOp(
unsigned Opcode,
Value *
LHS,
Value *
RHS,
bool IsNSW =
false,
5270 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5282 return std::nullopt;
5288 switch (
Op->getOpcode()) {
5289 case Instruction::Add:
5290 case Instruction::Sub:
5291 case Instruction::Mul:
5292 case Instruction::UDiv:
5293 case Instruction::URem:
5294 case Instruction::And:
5295 case Instruction::AShr:
5296 case Instruction::Shl:
5297 return BinaryOp(
Op);
5299 case Instruction::Or: {
5302 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5304 return BinaryOp(
Op);
5307 case Instruction::Xor:
5311 if (RHSC->getValue().isSignMask())
5312 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5314 if (V->getType()->isIntegerTy(1))
5315 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5316 return BinaryOp(
Op);
5318 case Instruction::LShr:
5327 if (SA->getValue().ult(
BitWidth)) {
5329 ConstantInt::get(SA->getContext(),
5331 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5334 return BinaryOp(
Op);
5336 case Instruction::ExtractValue: {
5338 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5346 bool Signed = WO->isSigned();
5349 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5354 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5365 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5366 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5368 return std::nullopt;
5394 if (
Op == SymbolicPHI)
5399 if (SourceBits != NewBits)
5412 if (
X != SymbolicPHI)
5414 Signed = SExt !=
nullptr;
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) {
6336 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6339 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6341 auto GetGCDMultiple = [
this](
const SCEVNAryExpr *
N) {
6344 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6362 return GetShiftedByZeros(TZ);
6372 return GetShiftedByZeros(TZ);
6376 if (
M->hasNoUnsignedWrap()) {
6379 for (
const SCEV *Operand :
M->operands().drop_front())
6387 for (
const SCEV *Operand :
M->operands())
6389 return GetShiftedByZeros(TZ);
6394 if (
N->hasNoUnsignedWrap())
6395 return GetGCDMultiple(
N);
6398 for (
const SCEV *Operand :
N->operands().drop_front())
6400 return GetShiftedByZeros(TZ);
6413 .countMinTrailingZeros();
6414 return GetShiftedByZeros(Known);
6423 auto I = ConstantMultipleCache.find(S);
6424 if (
I != ConstantMultipleCache.end())
6427 APInt Result = getConstantMultipleImpl(S);
6428 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6429 assert(InsertPair.second &&
"Should insert a new key");
6430 return InsertPair.first->second;
6446 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6449 if (std::optional<ConstantRange>
Range = CB->getRange())
6453 if (std::optional<ConstantRange>
Range =
A->getRange())
6456 return std::nullopt;
6463 UnsignedRanges.erase(AddRec);
6464 SignedRanges.erase(AddRec);
6465 ConstantMultipleCache.erase(AddRec);
6470getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6496 Value *Start, *Step;
6503 assert(L && L->getHeader() ==
P->getParent());
6516 case Instruction::AShr:
6517 case Instruction::LShr:
6518 case Instruction::Shl:
6533 KnownStep.getBitWidth() ==
BitWidth);
6536 auto MaxShiftAmt = KnownStep.getMaxValue();
6538 bool Overflow =
false;
6539 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6546 case Instruction::AShr: {
6554 if (KnownStart.isNonNegative())
6557 KnownStart.getMaxValue() + 1);
6558 if (KnownStart.isNegative())
6561 KnownEnd.getMaxValue() + 1);
6564 case Instruction::LShr: {
6573 KnownStart.getMaxValue() + 1);
6575 case Instruction::Shl: {
6579 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6580 return ConstantRange(KnownStart.getMinValue(),
6581 KnownEnd.getMaxValue() + 1);
6589ScalarEvolution::getRangeRefIter(
const SCEV *S,
6590 ScalarEvolution::RangeSignHint SignHint) {
6591 DenseMap<const SCEV *, ConstantRange> &Cache =
6592 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6595 SmallPtrSet<const SCEV *, 8> Seen;
6599 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6600 if (!Seen.
insert(Expr).second)
6633 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6634 const SCEV *
P = WorkList[
I];
6638 for (
const SCEV *
Op :
P->operands())
6644 if (!PendingPhiRangesIter.insert(
P).second)
6651 if (!WorkList.
empty()) {
6656 getRangeRef(
P, SignHint);
6660 PendingPhiRangesIter.erase(
P);
6664 return getRangeRef(S, SignHint, 0);
6671 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6672 DenseMap<const SCEV *, ConstantRange> &Cache =
6673 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6681 if (
I != Cache.
end())
6685 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6690 return getRangeRefIter(S, SignHint);
6693 ConstantRange ConservativeResult(
BitWidth,
true);
6694 using OBO = OverflowingBinaryOperator;
6698 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6702 ConservativeResult =
6709 ConservativeResult = ConstantRange(
6725 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6732 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6739 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6743 ConstantRange
X = getRangeRef(PtrToInt->
getOperand(), SignHint,
Depth + 1);
6744 return setRange(PtrToInt, SignHint,
X);
6748 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6749 unsigned WrapType = OBO::AnyWrap;
6750 if (
Add->hasNoSignedWrap())
6751 WrapType |= OBO::NoSignedWrap;
6752 if (
Add->hasNoUnsignedWrap())
6753 WrapType |= OBO::NoUnsignedWrap;
6755 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6757 return setRange(
Add, SignHint,
6758 ConservativeResult.intersectWith(
X, RangeType));
6762 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6764 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6765 return setRange(
Mul, SignHint,
6766 ConservativeResult.intersectWith(
X, RangeType));
6770 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6771 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6772 return setRange(UDiv, SignHint,
6773 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6781 if (!UnsignedMinValue.
isZero())
6782 ConservativeResult = ConservativeResult.intersectWith(
6783 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6792 bool AllNonNeg =
true;
6793 bool AllNonPos =
true;
6794 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6801 ConservativeResult = ConservativeResult.intersectWith(
6806 ConservativeResult = ConservativeResult.intersectWith(
6815 const SCEV *MaxBEScev =
6829 auto RangeFromAffine = getRangeForAffineAR(
6831 ConservativeResult =
6832 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6834 auto RangeFromFactoring = getRangeViaFactoring(
6836 ConservativeResult =
6837 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6843 const SCEV *SymbolicMaxBECount =
6848 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6849 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6850 ConservativeResult =
6851 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6856 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6866 ID = Intrinsic::umax;
6869 ID = Intrinsic::smax;
6873 ID = Intrinsic::umin;
6876 ID = Intrinsic::smin;
6883 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6884 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6886 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6887 return setRange(S, SignHint,
6888 ConservativeResult.intersectWith(
X, RangeType));
6897 ConservativeResult =
6898 ConservativeResult.intersectWith(*MDRange, RangeType);
6903 auto CR = getRangeForUnknownRecurrence(U);
6904 ConservativeResult = ConservativeResult.intersectWith(CR);
6915 if (
U->getType()->isPointerTy()) {
6918 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
6919 int ptrIdxDiff = ptrSize -
BitWidth;
6920 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
6933 ConservativeResult = ConservativeResult.intersectWith(
6937 ConservativeResult = ConservativeResult.intersectWith(
6942 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6945 bool CanBeNull, CanBeFreed;
6946 uint64_t DerefBytes =
6947 V->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed);
6957 uint64_t
Align =
U->getValue()->getPointerAlignment(DL).value();
6958 uint64_t Rem = MaxVal.
urem(Align);
6963 ConservativeResult = ConservativeResult.intersectWith(
6971 if (PendingPhiRanges.insert(Phi).second) {
6972 ConstantRange RangeFromOps(
BitWidth,
false);
6974 for (
const auto &
Op :
Phi->operands()) {
6976 RangeFromOps = RangeFromOps.unionWith(OpRange);
6978 if (RangeFromOps.isFullSet())
6981 ConservativeResult =
6982 ConservativeResult.intersectWith(RangeFromOps, RangeType);
6983 bool Erased = PendingPhiRanges.erase(Phi);
6984 assert(Erased &&
"Failed to erase Phi properly?");
6991 if (
II->getIntrinsicID() == Intrinsic::vscale) {
6993 ConservativeResult = ConservativeResult.difference(Disallowed);
6996 return setRange(U, SignHint, std::move(ConservativeResult));
7002 return setRange(S, SignHint, std::move(ConservativeResult));
7011 const APInt &MaxBECount,
7018 if (Step == 0 || MaxBECount == 0)
7025 return ConstantRange::getFull(
BitWidth);
7041 return ConstantRange::getFull(
BitWidth);
7053 APInt MovedBoundary = Descending ? (StartLower - std::move(
Offset))
7054 : (StartUpper + std::move(
Offset));
7059 if (StartRange.
contains(MovedBoundary))
7060 return ConstantRange::getFull(
BitWidth);
7063 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7065 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7074 const APInt &MaxBECount) {
7078 "mismatched bit widths");
7087 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7089 StartSRange, MaxBECount,
7101ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7103 ScalarEvolution::RangeSignHint SignHint) {
7104 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7106 "This only works for non-self-wrapping AddRecs!");
7107 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7111 return ConstantRange::getFull(
BitWidth);
7119 return ConstantRange::getFull(
BitWidth);
7123 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7125 MaxItersWithoutWrap))
7126 return ConstantRange::getFull(
BitWidth);
7147 ConstantRange StartRange = getRangeRef(Start, SignHint);
7148 ConstantRange EndRange = getRangeRef(End, SignHint);
7149 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7153 return RangeBetween;
7158 return ConstantRange::getFull(
BitWidth);
7161 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7162 return RangeBetween;
7164 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7165 return RangeBetween;
7166 return ConstantRange::getFull(
BitWidth);
7171 const APInt &MaxBECount) {
7178 "mismatched bit widths");
7180 struct SelectPattern {
7181 Value *Condition =
nullptr;
7185 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7187 std::optional<unsigned> CastOp;
7201 CastOp = SCast->getSCEVType();
7202 S = SCast->getOperand();
7205 using namespace llvm::PatternMatch;
7212 Condition =
nullptr;
7244 bool isRecognized() {
return Condition !=
nullptr; }
7247 SelectPattern StartPattern(*
this,
BitWidth, Start);
7248 if (!StartPattern.isRecognized())
7249 return ConstantRange::getFull(
BitWidth);
7251 SelectPattern StepPattern(*
this,
BitWidth, Step);
7252 if (!StepPattern.isRecognized())
7253 return ConstantRange::getFull(
BitWidth);
7255 if (StartPattern.Condition != StepPattern.Condition) {
7259 return ConstantRange::getFull(
BitWidth);
7270 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7271 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7272 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7273 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7275 ConstantRange TrueRange =
7276 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount);
7277 ConstantRange FalseRange =
7278 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount);
7300ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7314 SmallPtrSet<const SCEV *, 16> Visited;
7316 auto pushOp = [&](
const SCEV *S) {
7317 if (!Visited.
insert(S).second)
7320 if (Visited.
size() > 30) {
7327 for (
const auto *S :
Ops)
7331 while (!Worklist.
empty()) {
7333 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7334 if (!Bound || DT.dominates(Bound, DefI))
7341 return Bound ? Bound : &*F.getEntryBlock().begin();
7347 return getDefiningScopeBound(
Ops, Discard);
7350bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7352 if (
A->getParent() ==
B->getParent() &&
7357 auto *BLoop = LI.getLoopFor(
B->getParent());
7358 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7359 BLoop->getLoopPreheader() ==
A->getParent() &&
7361 A->getParent()->end()) &&
7368bool ScalarEvolution::isGuaranteedNotToBePoison(
const SCEV *
Op) {
7369 SCEVPoisonCollector PC(
true);
7371 return PC.MaybePoison.empty();
7374bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7380 return M && (!
isKnownNonZero(Op1) || !isGuaranteedNotToBePoison(Op1));
7384bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7401 for (
const Use &
Op :
I->operands()) {
7407 auto *DefI = getDefiningScopeBound(SCEVOps);
7408 return isGuaranteedToTransferExecutionTo(DefI,
I);
7411bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7413 if (isSCEVExprNeverPoison(
I))
7424 auto *ExitingBB =
L->getExitingBlock();
7428 SmallPtrSet<const Value *, 16> KnownPoison;
7437 while (!Worklist.
empty()) {
7440 for (
const Use &U :
Poison->uses()) {
7443 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7447 if (KnownPoison.
insert(PoisonUser).second)
7455ScalarEvolution::LoopProperties
7456ScalarEvolution::getLoopProperties(
const Loop *L) {
7457 using LoopProperties = ScalarEvolution::LoopProperties;
7459 auto Itr = LoopPropertiesCache.find(L);
7460 if (Itr == LoopPropertiesCache.end()) {
7463 return !
SI->isSimple();
7473 return I->mayWriteToMemory();
7476 LoopProperties LP = {
true,
7479 for (
auto *BB :
L->getBlocks())
7480 for (
auto &
I : *BB) {
7482 LP.HasNoAbnormalExits =
false;
7483 if (HasSideEffects(&
I))
7484 LP.HasNoSideEffects =
false;
7485 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7489 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7490 assert(InsertPair.second &&
"We just checked!");
7491 Itr = InsertPair.first;
7504const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7510 Stack.emplace_back(V,
true);
7511 Stack.emplace_back(V,
false);
7512 while (!Stack.empty()) {
7513 auto E = Stack.pop_back_val();
7514 Value *CurV = E.getPointer();
7520 const SCEV *CreatedSCEV =
nullptr;
7523 CreatedSCEV = createSCEV(CurV);
7528 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7532 insertValueToMap(CurV, CreatedSCEV);
7536 Stack.emplace_back(CurV,
true);
7538 Stack.emplace_back(
Op,
false);
7555 if (!DT.isReachableFromEntry(
I->getParent()))
7568 switch (BO->Opcode) {
7569 case Instruction::Add:
7570 case Instruction::Mul: {
7577 Ops.push_back(BO->
Op);
7581 Ops.push_back(BO->RHS);
7585 (BO->Opcode == Instruction::Add &&
7586 (NewBO->Opcode != Instruction::Add &&
7587 NewBO->Opcode != Instruction::Sub)) ||
7588 (BO->Opcode == Instruction::Mul &&
7589 NewBO->Opcode != Instruction::Mul)) {
7590 Ops.push_back(BO->LHS);
7595 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7598 Ops.push_back(BO->LHS);
7606 case Instruction::Sub:
7607 case Instruction::UDiv:
7608 case Instruction::URem:
7610 case Instruction::AShr:
7611 case Instruction::Shl:
7612 case Instruction::Xor:
7616 case Instruction::And:
7617 case Instruction::Or:
7621 case Instruction::LShr:
7628 Ops.push_back(BO->LHS);
7629 Ops.push_back(BO->RHS);
7633 switch (
U->getOpcode()) {
7634 case Instruction::Trunc:
7635 case Instruction::ZExt:
7636 case Instruction::SExt:
7637 case Instruction::PtrToInt:
7638 Ops.push_back(
U->getOperand(0));
7641 case Instruction::BitCast:
7643 Ops.push_back(
U->getOperand(0));
7648 case Instruction::SDiv:
7649 case Instruction::SRem:
7650 Ops.push_back(
U->getOperand(0));
7651 Ops.push_back(
U->getOperand(1));
7654 case Instruction::GetElementPtr:
7656 "GEP source element type must be sized");
7660 case Instruction::IntToPtr:
7663 case Instruction::PHI:
7667 case Instruction::Select: {
7669 auto CanSimplifyToUnknown = [
this,
U]() {
7687 if (CanSimplifyToUnknown())
7694 case Instruction::Call:
7695 case Instruction::Invoke:
7702 switch (
II->getIntrinsicID()) {
7703 case Intrinsic::abs:
7704 Ops.push_back(
II->getArgOperand(0));
7706 case Intrinsic::umax:
7707 case Intrinsic::umin:
7708 case Intrinsic::smax:
7709 case Intrinsic::smin:
7710 case Intrinsic::usub_sat:
7711 case Intrinsic::uadd_sat:
7712 Ops.push_back(
II->getArgOperand(0));
7713 Ops.push_back(
II->getArgOperand(1));
7715 case Intrinsic::start_loop_iterations:
7716 case Intrinsic::annotation:
7717 case Intrinsic::ptr_annotation:
7718 Ops.push_back(
II->getArgOperand(0));
7730const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7739 if (!DT.isReachableFromEntry(
I->getParent()))
7754 switch (BO->Opcode) {
7755 case Instruction::Add: {
7781 if (BO->Opcode == Instruction::Sub)
7789 if (BO->Opcode == Instruction::Sub)
7796 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7797 NewBO->Opcode != Instruction::Sub)) {
7807 case Instruction::Mul: {
7828 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7837 case Instruction::UDiv:
7841 case Instruction::URem:
7845 case Instruction::Sub: {
7848 Flags = getNoWrapFlagsFromUB(BO->
Op);
7853 case Instruction::And:
7859 if (CI->isMinusOne())
7861 const APInt &
A = CI->getValue();
7867 unsigned LZ =
A.countl_zero();
7868 unsigned TZ =
A.countr_zero();
7873 APInt EffectiveMask =
7875 if ((LZ != 0 || TZ != 0) && !((~
A & ~Known.
Zero) & EffectiveMask)) {
7878 const SCEV *ShiftedLHS =
nullptr;
7882 unsigned MulZeros = OpC->getAPInt().countr_zero();
7883 unsigned GCD = std::min(MulZeros, TZ);
7888 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
7910 case Instruction::Or:
7919 case Instruction::Xor:
7922 if (CI->isMinusOne())
7931 if (LBO->getOpcode() == Instruction::And &&
7932 LCI->getValue() == CI->getValue())
7933 if (
const SCEVZeroExtendExpr *Z =
7936 const SCEV *Z0 =
Z->getOperand();
7943 if (CI->getValue().isMask(Z0TySize))
7949 APInt Trunc = CI->getValue().trunc(Z0TySize);
7958 case Instruction::Shl:
7976 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
7984 ConstantInt *
X = ConstantInt::get(
7990 case Instruction::AShr:
8012 const SCEV *AddTruncateExpr =
nullptr;
8013 ConstantInt *ShlAmtCI =
nullptr;
8014 const SCEV *AddConstant =
nullptr;
8016 if (L &&
L->getOpcode() == Instruction::Add) {
8024 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8031 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8039 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8044 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8049 if (AddTruncateExpr && ShlAmtCI) {
8061 const APInt &ShlAmt = ShlAmtCI->
getValue();
8065 const SCEV *CompositeExpr =
8067 if (
L->getOpcode() != Instruction::Shl)
8068 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8077 switch (
U->getOpcode()) {
8078 case Instruction::Trunc:
8081 case Instruction::ZExt:
8084 case Instruction::SExt:
8094 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8095 Type *Ty =
U->getType();
8103 case Instruction::BitCast:
8109 case Instruction::PtrToInt: {
8112 Type *DstIntTy =
U->getType();
8120 case Instruction::IntToPtr:
8124 case Instruction::SDiv:
8131 case Instruction::SRem:
8138 case Instruction::GetElementPtr:
8141 case Instruction::PHI:
8144 case Instruction::Select:
8145 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8148 case Instruction::Call:
8149 case Instruction::Invoke:
8154 switch (
II->getIntrinsicID()) {
8155 case Intrinsic::abs:
8159 case Intrinsic::umax:
8163 case Intrinsic::umin:
8167 case Intrinsic::smax:
8171 case Intrinsic::smin:
8175 case Intrinsic::usub_sat: {
8176 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8177 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8181 case Intrinsic::uadd_sat: {
8182 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8183 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8187 case Intrinsic::start_loop_iterations:
8188 case Intrinsic::annotation:
8189 case Intrinsic::ptr_annotation:
8193 case Intrinsic::vscale:
8213 auto *ExitCountType = ExitCount->
getType();
8214 assert(ExitCountType->isIntegerTy());
8216 1 + ExitCountType->getScalarSizeInBits());
8229 auto CanAddOneWithoutOverflow = [&]() {
8231 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8242 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8272 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8273 assert(L->isLoopExiting(ExitingBlock) &&
8274 "Exiting block must actually branch out of the loop!");
8283 const auto *MaxExitCount =
8291 L->getExitingBlocks(ExitingBlocks);
8293 std::optional<unsigned> Res;
8294 for (
auto *ExitingBB : ExitingBlocks) {
8298 Res = std::gcd(*Res, Multiple);
8300 return Res.value_or(1);
8304 const SCEV *ExitCount) {
8334 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8335 assert(L->isLoopExiting(ExitingBlock) &&
8336 "Exiting block must actually branch out of the loop!");
8346 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8348 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8350 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8360 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8363 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8366 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8374 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8381 return getBackedgeTakenInfo(L).getExact(L,
this);
8383 return getBackedgeTakenInfo(L).getConstantMax(
this);
8385 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8392 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8397 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8401 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8411 for (
PHINode &PN : Header->phis())
8412 if (Visited.
insert(&PN).second)
8416ScalarEvolution::BackedgeTakenInfo &
8417ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8418 auto &BTI = getBackedgeTakenInfo(L);
8419 if (BTI.hasFullInfo())
8422 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8425 return Pair.first->second;
8427 BackedgeTakenInfo
Result =
8428 computeBackedgeTakenCount(L,
true);
8430 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8433ScalarEvolution::BackedgeTakenInfo &
8434ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8440 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8441 BackedgeTakenCounts.try_emplace(L);
8443 return Pair.first->second;
8448 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8455 if (
Result.hasAnyInfo()) {
8458 auto LoopUsersIt = LoopUsers.find(L);
8459 if (LoopUsersIt != LoopUsers.end())
8461 forgetMemoizedResults(ToForget);
8464 for (PHINode &PN :
L->getHeader()->phis())
8465 ConstantEvolutionLoopExitValue.erase(&PN);
8473 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8482 BackedgeTakenCounts.clear();
8483 PredicatedBackedgeTakenCounts.clear();
8484 BECountUsers.clear();
8485 LoopPropertiesCache.clear();
8486 ConstantEvolutionLoopExitValue.clear();
8487 ValueExprMap.clear();
8488 ValuesAtScopes.clear();
8489 ValuesAtScopesUsers.clear();
8490 LoopDispositions.clear();
8491 BlockDispositions.clear();
8492 UnsignedRanges.clear();
8493 SignedRanges.clear();
8494 ExprValueMap.clear();
8496 ConstantMultipleCache.clear();
8497 PredicatedSCEVRewrites.clear();
8499 FoldCacheUser.clear();
8501void ScalarEvolution::visitAndClearUsers(
8505 while (!Worklist.
empty()) {
8512 if (It != ValueExprMap.
end()) {
8513 eraseValueFromMap(It->first);
8516 ConstantEvolutionLoopExitValue.erase(PN);
8530 while (!LoopWorklist.
empty()) {
8534 forgetBackedgeTakenCounts(CurrL,
false);
8535 forgetBackedgeTakenCounts(CurrL,
true);
8538 for (
auto I = PredicatedSCEVRewrites.begin();
8539 I != PredicatedSCEVRewrites.end();) {
8540 std::pair<const SCEV *, const Loop *> Entry =
I->first;
8541 if (Entry.second == CurrL)
8542 PredicatedSCEVRewrites.erase(
I++);
8547 auto LoopUsersItr = LoopUsers.find(CurrL);
8548 if (LoopUsersItr != LoopUsers.end())
8553 visitAndClearUsers(Worklist, Visited, ToForget);
8555 LoopPropertiesCache.erase(CurrL);
8558 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8560 forgetMemoizedResults(ToForget);
8577 visitAndClearUsers(Worklist, Visited, ToForget);
8579 forgetMemoizedResults(ToForget);
8591 struct InvalidationRootCollector {
8595 InvalidationRootCollector(
Loop *L) : L(L) {}
8597 bool follow(
const SCEV *S) {
8603 if (L->contains(AddRec->
getLoop()))
8608 bool isDone()
const {
return false; }
8611 InvalidationRootCollector
C(L);
8613 forgetMemoizedResults(
C.Roots);
8626 BlockDispositions.clear();
8627 LoopDispositions.clear();
8644 while (!Worklist.
empty()) {
8646 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8647 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8648 if (!LoopDispoRemoved && !BlockDispoRemoved)
8650 auto Users = SCEVUsers.find(Curr);
8651 if (
Users != SCEVUsers.end())
8664const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8668 if (!isComplete() || ExitNotTaken.
empty())
8679 for (
const auto &ENT : ExitNotTaken) {
8680 const SCEV *BECount = ENT.ExactNotTaken;
8683 "We should only have known counts for exiting blocks that dominate "
8686 Ops.push_back(BECount);
8691 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8692 "Predicate should be always true!");
8701const ScalarEvolution::ExitNotTakenInfo *
8702ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8703 const BasicBlock *ExitingBlock,
8704 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8705 for (
const auto &ENT : ExitNotTaken)
8706 if (ENT.ExitingBlock == ExitingBlock) {
8707 if (ENT.hasAlwaysTruePredicate())
8709 else if (Predicates) {
8719const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8721 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8722 if (!getConstantMax())
8725 for (
const auto &ENT : ExitNotTaken)
8726 if (!ENT.hasAlwaysTruePredicate()) {
8734 "No point in having a non-constant max backedge taken count!");
8735 return getConstantMax();
8738const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8740 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8748 for (
const auto &ENT : ExitNotTaken) {
8749 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8752 "We should only have known counts for exiting blocks that "
8758 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8759 "Predicate should be always true!");
8762 if (ExitCounts.
empty())
8771bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8773 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8774 return !ENT.hasAlwaysTruePredicate();
8776 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8792 this->ExactNotTaken = E = ConstantMaxNotTaken;
8793 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8798 "Exact is not allowed to be less precise than Constant Max");
8801 "Exact is not allowed to be less precise than Symbolic Max");
8804 "Symbolic Max is not allowed to be less precise than Constant Max");
8807 "No point in having a non-constant max backedge taken count!");
8809 for (
const auto PredList : PredLists)
8810 for (
const auto *
P : PredList) {
8818 "Backedge count should be int");
8821 "Max backedge count should be int");
8834ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8836 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8837 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8838 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8840 ExitNotTaken.reserve(ExitCounts.
size());
8841 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8842 std::back_inserter(ExitNotTaken),
8843 [&](
const EdgeExitInfo &EEI) {
8844 BasicBlock *ExitBB = EEI.first;
8845 const ExitLimit &EL = EEI.second;
8846 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
8847 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
8852 "No point in having a non-constant max backedge taken count!");
8856ScalarEvolution::BackedgeTakenInfo
8857ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
8858 bool AllowPredicates) {
8860 L->getExitingBlocks(ExitingBlocks);
8862 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8865 bool CouldComputeBECount =
true;
8867 const SCEV *MustExitMaxBECount =
nullptr;
8868 const SCEV *MayExitMaxBECount =
nullptr;
8869 bool MustExitMaxOrZero =
false;
8870 bool IsOnlyExit = ExitingBlocks.
size() == 1;
8882 if (ExitIfTrue == CI->
isZero())
8886 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
8888 assert((AllowPredicates || EL.Predicates.empty()) &&
8889 "Predicated exit limit when predicates are not allowed!");
8894 ++NumExitCountsComputed;
8898 CouldComputeBECount =
false;
8905 "Exact is known but symbolic isn't?");
8906 ++NumExitCountsNotComputed;
8921 DT.dominates(ExitBB, Latch)) {
8922 if (!MustExitMaxBECount) {
8923 MustExitMaxBECount = EL.ConstantMaxNotTaken;
8924 MustExitMaxOrZero = EL.MaxOrZero;
8927 EL.ConstantMaxNotTaken);
8931 MayExitMaxBECount = EL.ConstantMaxNotTaken;
8934 EL.ConstantMaxNotTaken);
8938 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
8942 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
8948 for (
const auto &Pair : ExitCounts) {
8950 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
8952 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
8953 {
L, AllowPredicates});
8955 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
8956 MaxBECount, MaxOrZero);
8959ScalarEvolution::ExitLimit
8960ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
8961 bool IsOnlyExit,
bool AllowPredicates) {
8962 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
8966 if (!Latch || !DT.dominates(ExitingBlock, Latch))
8974 "It should have one successor in loop and one exit block!");
8985 if (!
L->contains(SBB)) {
8990 assert(Exit &&
"Exiting block must have at least one exit");
8991 return computeExitLimitFromSingleExitSwitch(
8992 L, SI, Exit, IsOnlyExit);
8999 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9000 bool AllowPredicates) {
9001 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9002 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9003 ControlsOnlyExit, AllowPredicates);
9006std::optional<ScalarEvolution::ExitLimit>
9007ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9008 bool ExitIfTrue,
bool ControlsOnlyExit,
9009 bool AllowPredicates) {
9011 (void)this->ExitIfTrue;
9012 (void)this->AllowPredicates;
9014 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9015 this->AllowPredicates == AllowPredicates &&
9016 "Variance in assumed invariant key components!");
9017 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9018 if (Itr == TripCountMap.end())
9019 return std::nullopt;
9023void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9025 bool ControlsOnlyExit,
9026 bool AllowPredicates,
9028 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9029 this->AllowPredicates == AllowPredicates &&
9030 "Variance in assumed invariant key components!");
9032 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9033 assert(InsertResult.second &&
"Expected successful insertion!");
9038ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9039 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9040 bool ControlsOnlyExit,
bool AllowPredicates) {
9042 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9046 ExitLimit EL = computeExitLimitFromCondImpl(
9047 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9048 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9052ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9053 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9054 bool ControlsOnlyExit,
bool AllowPredicates) {
9056 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9057 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates))
9058 return *LimitFromBinOp;
9064 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9065 if (EL.hasFullInfo() || !AllowPredicates)
9069 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9089 const WithOverflowInst *WO;
9104 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9105 ControlsOnlyExit, AllowPredicates);
9106 if (EL.hasAnyInfo())
9111 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9114std::optional<ScalarEvolution::ExitLimit>
9115ScalarEvolution::computeExitLimitFromCondFromBinOp(
9116 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9117 bool ControlsOnlyExit,
bool AllowPredicates) {
9126 return std::nullopt;
9131 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9132 ExitLimit EL0 = computeExitLimitFromCondCached(
9133 Cache, L, Op0, ExitIfTrue, ControlsOnlyExit && !EitherMayExit,
9135 ExitLimit EL1 = computeExitLimitFromCondCached(
9136 Cache, L, Op1, ExitIfTrue, ControlsOnlyExit && !EitherMayExit,
9140 const Constant *NeutralElement = ConstantInt::get(ExitCond->
getType(), IsAnd);
9142 return Op1 == NeutralElement ? EL0 : EL1;
9144 return Op0 == NeutralElement ? EL1 : EL0;
9149 if (EitherMayExit) {
9159 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9161 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9164 EL1.ConstantMaxNotTaken);
9166 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9168 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9171 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9175 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9176 BECount = EL0.ExactNotTaken;
9189 SymbolicMaxBECount =
9191 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9195ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9196 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9197 bool AllowPredicates) {
9209 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9211 if (EL.hasAnyInfo())
9214 auto *ExhaustiveCount =
9215 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9218 return ExhaustiveCount;
9220 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9223ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9224 const Loop *L, CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
9225 bool ControlsOnlyExit,
bool AllowPredicates) {
9250 ConstantRange CompRange =
9266 auto *InnerLHS =
LHS;
9268 InnerLHS = ZExt->getOperand();
9315 if (EL.hasAnyInfo())
9332 if (EL.hasAnyInfo())
return EL;
9364 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9366 if (EL.hasAnyInfo())
9382 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9384 if (EL.hasAnyInfo())
9395ScalarEvolution::ExitLimit
9396ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9398 BasicBlock *ExitingBlock,
9399 bool ControlsOnlyExit) {
9400 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9403 if (
Switch->getDefaultDest() == ExitingBlock)
9407 "Default case must not exit the loop!");
9413 if (EL.hasAnyInfo())
9425 "Evaluation of SCEV at constant didn't fold correctly?");
9429ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9439 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9445 auto MatchPositiveShift =
9448 using namespace PatternMatch;
9450 ConstantInt *ShiftAmt;
9452 OutOpCode = Instruction::LShr;
9454 OutOpCode = Instruction::AShr;
9456 OutOpCode = Instruction::Shl;
9471 auto MatchShiftRecurrence =
9473 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9488 if (MatchPositiveShift(
LHS, V, OpC)) {
9489 PostShiftOpCode = OpC;
9495 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9498 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9504 MatchPositiveShift(BEValue, OpLHS, OpCodeOut) &&
9511 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9516 if (!MatchShiftRecurrence(
LHS, PN, OpCode))
9528 ConstantInt *StableValue =
nullptr;
9533 case Instruction::AShr: {
9541 StableValue = ConstantInt::get(Ty, 0);
9543 StableValue = ConstantInt::get(Ty, -1,
true);
9549 case Instruction::LShr:
9550 case Instruction::Shl:
9560 "Otherwise cannot be an operand to a branch instruction");
9562 if (
Result->isZeroValue()) {
9564 const SCEV *UpperBound =
9581 if (
const Function *
F = CI->getCalledFunction())
9590 if (!L->contains(
I))
return false;
9595 return L->getHeader() ==
I->getParent();
9671 if (!
I)
return nullptr;
9684 std::vector<Constant*>
Operands(
I->getNumOperands());
9686 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9695 if (!
C)
return nullptr;
9717 if (IncomingVal != CurrentVal) {
9720 IncomingVal = CurrentVal;
9732ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9735 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9744 DenseMap<Instruction *, Constant *> CurrentIterVals;
9746 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9752 for (PHINode &
PHI : Header->phis()) {
9754 CurrentIterVals[&
PHI] = StartCST;
9756 if (!CurrentIterVals.
count(PN))
9757 return RetVal =
nullptr;
9763 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9766 unsigned IterationNum = 0;
9768 for (; ; ++IterationNum) {
9769 if (IterationNum == NumIterations)
9770 return RetVal = CurrentIterVals[PN];
9774 DenseMap<Instruction *, Constant *> NextIterVals;
9779 NextIterVals[PN] = NextPHI;
9781 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9787 for (
const auto &
I : CurrentIterVals) {
9789 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9794 for (
const auto &
I : PHIsToCompute) {
9795 PHINode *
PHI =
I.first;
9798 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9801 if (NextPHI !=
I.second)
9802 StoppedEvolving =
false;
9807 if (StoppedEvolving)
9808 return RetVal = CurrentIterVals[PN];
9810 CurrentIterVals.swap(NextIterVals);
9814const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
9824 DenseMap<Instruction *, Constant *> CurrentIterVals;
9826 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9829 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
9831 for (PHINode &
PHI : Header->phis()) {
9833 CurrentIterVals[&
PHI] = StartCST;
9835 if (!CurrentIterVals.
count(PN))
9843 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
9850 if (CondVal->getValue() == uint64_t(ExitWhen)) {
9851 ++NumBruteForceTripCountsComputed;
9856 DenseMap<Instruction *, Constant *> NextIterVals;
9862 for (
const auto &
I : CurrentIterVals) {
9864 if (!
PHI ||
PHI->getParent() != Header)
continue;
9867 for (PHINode *
PHI : PHIsToCompute) {
9869 if (NextPHI)
continue;
9871 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9874 CurrentIterVals.
swap(NextIterVals);
9885 for (
auto &LS : Values)
9887 return LS.second ? LS.second : V;
9892 const SCEV *
C = computeSCEVAtScope(V, L);
9893 for (
auto &LS :
reverse(ValuesAtScopes[V]))
9894 if (LS.first == L) {
9897 ValuesAtScopesUsers[
C].push_back({L, V});
9908 switch (V->getSCEVType()) {
9941 assert(!
C->getType()->isPointerTy() &&
9942 "Can only have one pointer, and it must be last");
9969ScalarEvolution::getWithOperands(
const SCEV *S,
9970 SmallVectorImpl<const SCEV *> &NewOps) {
10004const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10005 switch (
V->getSCEVType()) {
10016 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10027 for (++i; i !=
e; ++i)
10071 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10073 if (OpAtScope !=
Ops[i]) {
10081 for (++i; i !=
e; ++i) {
10086 return getWithOperands(V, NewOps);
10101 const Loop *CurrLoop = this->LI[
I->getParent()];
10112 if (BackedgeTakenCount->
isZero()) {
10113 Value *InitValue =
nullptr;
10114 bool MultipleInitValues =
false;
10120 MultipleInitValues =
true;
10125 if (!MultipleInitValues && InitValue)
10134 unsigned InLoopPred =
10145 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10161 bool MadeImprovement =
false;
10176 MadeImprovement |= OrigV != OpV;
10181 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10186 if (!MadeImprovement)
10207const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10209 return stripInjectiveFunctions(ZExt->getOperand());
10211 return stripInjectiveFunctions(SExt->getOperand());
10230 assert(
A != 0 &&
"A must be non-zero.");
10266 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10286static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10292 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10293 << *AddRec <<
'\n');
10296 if (!LC || !MC || !
NC) {
10297 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10298 return std::nullopt;
10304 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10312 N =
N.sext(NewWidth);
10313 M = M.sext(NewWidth);
10314 L = L.sext(NewWidth);
10331 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10332 <<
", multiplied by " <<
T <<
'\n');
10341 std::optional<APInt>
Y) {
10343 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10346 return XW.
slt(YW) ? *
X : *
Y;
10349 return std::nullopt;
10350 return X ? *
X : *
Y;
10367 return std::nullopt;
10368 unsigned W =
X->getBitWidth();
10388static std::optional<APInt>
10394 return std::nullopt;
10397 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10398 std::optional<APInt>
X =
10401 return std::nullopt;
10406 return std::nullopt;
10421static std::optional<APInt>
10425 "Starting value of addrec should be 0");
10426 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10427 <<
Range <<
", addrec " << *AddRec <<
'\n');
10431 "Addrec's initial value should be in range");
10437 return std::nullopt;
10447 auto SolveForBoundary =
10448 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10451 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10452 << Bound <<
" (before multiplying by " << M <<
")\n");
10455 std::optional<APInt> SO;
10458 "signed overflow\n");
10462 "unsigned overflow\n");
10463 std::optional<APInt> UO =
10466 auto LeavesRange = [&] (
const APInt &
X) {
10483 return {std::nullopt,
false};
10488 if (LeavesRange(*Min))
10489 return { Min,
true };
10490 std::optional<APInt> Max = Min == SO ? UO : SO;
10491 if (LeavesRange(*Max))
10492 return { Max,
true };
10495 return {std::nullopt,
true};
10502 auto SL = SolveForBoundary(
Lower);
10503 auto SU = SolveForBoundary(
Upper);
10506 if (!SL.second || !SU.second)
10507 return std::nullopt;
10550ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10552 bool ControlsOnlyExit,
10553 bool AllowPredicates) {
10564 if (
C->getValue()->isZero())
return C;
10568 const SCEVAddRecExpr *AddRec =
10571 if (!AddRec && AllowPredicates)
10577 if (!AddRec || AddRec->
getLoop() != L)
10588 return ExitLimit(R, R, R,
false, Predicates);
10646 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10672 const SCEV *
Exact =
10680 const SCEV *SymbolicMax =
10682 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10691 AllowPredicates ? &Predicates :
nullptr, *
this);
10699 return ExitLimit(
E, M, S,
false, Predicates);
10702ScalarEvolution::ExitLimit
10703ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10711 if (!
C->getValue()->isZero())
10721std::pair<const BasicBlock *, const BasicBlock *>
10722ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10733 if (
const Loop *L = LI.getLoopFor(BB))
10734 return {
L->getLoopPredecessor(),
L->getHeader()};
10736 return {
nullptr, BB};
10745 if (
A ==
B)
return true;
10760 if (ComputesEqualValues(AI, BI))
10769 if (!
Add ||
Add->getNumOperands() != 2)
10772 ME && ME->getNumOperands() == 2 && ME->getOperand(0)->isAllOnesValue()) {
10773 LHS =
Add->getOperand(1);
10774 RHS = ME->getOperand(1);
10778 ME && ME->getNumOperands() == 2 && ME->getOperand(0)->isAllOnesValue()) {
10779 LHS =
Add->getOperand(0);
10780 RHS = ME->getOperand(1);
10791 auto TrivialCase = [&](
bool TriviallyTrue) {
10805 return TrivialCase(
false);
10806 return TrivialCase(
true);
10829 const APInt &
RA = RC->getAPInt();
10831 bool SimplifiedByConstantRange =
false;
10836 return TrivialCase(
true);
10838 return TrivialCase(
false);
10847 Changed = SimplifiedByConstantRange =
true;
10851 if (!SimplifiedByConstantRange) {
10868 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
10874 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
10880 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
10886 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
10898 return TrivialCase(
true);
10900 return TrivialCase(
false);
11005 auto NonRecursive = [
this, OrNegative](
const SCEV *S) {
11007 return C->getAPInt().isPowerOf2() ||
11008 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11011 return isa<SCEVVScale>(S) && F.hasFnAttribute(Attribute::VScaleRange);
11014 if (NonRecursive(S))
11040 APInt C = Cst->getAPInt();
11041 return C.urem(M) == 0;
11049 const SCEV *SmodM =
11064 for (
auto *
A : Assumptions)
11065 if (
A->implies(
P, *
this))
11073std::pair<const SCEV *, const SCEV *>
11076 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11078 return { Start, Start };
11080 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11089 getUsedLoops(LHS, LoopsUsed);
11090 getUsedLoops(RHS, LoopsUsed);
11092 if (LoopsUsed.
empty())
11097 for (
const auto *L1 : LoopsUsed)
11098 for (
const auto *L2 : LoopsUsed)
11099 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11100 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11101 "Domination relationship is not a linear order");
11131 SplitRHS.second) &&
11143 if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
11147 return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11157 return std::nullopt;
11172 if (KnownWithoutContext)
11173 return KnownWithoutContext;
11180 return std::nullopt;
11186 const Loop *L = LHS->getLoop();
11191std::optional<ScalarEvolution::MonotonicPredicateType>
11194 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11200 auto ResultSwapped =
11203 assert(*ResultSwapped != *Result &&
11204 "monotonicity should flip as we flip the predicate");
11211std::optional<ScalarEvolution::MonotonicPredicateType>
11212ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11226 return std::nullopt;
11230 "Should be greater or less!");
11234 if (!LHS->hasNoUnsignedWrap())
11235 return std::nullopt;
11239 "Relational predicate is either signed or unsigned!");
11240 if (!
LHS->hasNoSignedWrap())
11241 return std::nullopt;
11243 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11251 return std::nullopt;
11254std::optional<ScalarEvolution::LoopInvariantPredicate>
11261 return std::nullopt;
11268 if (!ArLHS || ArLHS->
getLoop() != L)
11269 return std::nullopt;
11273 return std::nullopt;
11299 return std::nullopt;
11336 return std::nullopt;
11339std::optional<ScalarEvolution::LoopInvariantPredicate>
11344 Pred, LHS, RHS, L, CtxI, MaxIter))
11352 for (
auto *
Op :
UMin->operands())
11354 Pred, LHS, RHS, L, CtxI,
Op))
11356 return std::nullopt;
11359std::optional<ScalarEvolution::LoopInvariantPredicate>
11374 return std::nullopt;
11381 if (!AR || AR->
getLoop() != L)
11382 return std::nullopt;
11386 return std::nullopt;
11392 if (Step != One && Step != MinusOne)
11393 return std::nullopt;
11399 return std::nullopt;
11405 return std::nullopt;
11413 if (Step == MinusOne)
11417 return std::nullopt;
11423bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11429 auto CheckRange = [&](
bool IsSigned) {
11432 return RangeLHS.
icmp(Pred, RangeRHS);
11441 if (CheckRange(
true) || CheckRange(
false))
11450bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11457 auto MatchBinaryAddToConst = [
this](
const SCEV *
X,
const SCEV *
Y,
11458 APInt &OutC1, APInt &OutC2,
11460 const SCEV *XNonConstOp, *XConstOp;
11461 const SCEV *YNonConstOp, *YConstOp;
11465 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11468 XFlagsPresent = ExpectedFlags;
11473 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11476 YFlagsPresent = ExpectedFlags;
11479 if (YNonConstOp != XNonConstOp)
11487 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11490 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11550bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11572bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11573 const SCEV *
LHS,
const SCEV *
RHS) {
11578 return any_of(*BB, [&](
const Instruction &
I) {
11579 using namespace llvm::PatternMatch;
11584 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11598 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11603 "This cannot be done on broken IR!");
11606 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11615 if (LoopContinuePredicate && LoopContinuePredicate->
isConditional() &&
11616 isImpliedCond(Pred, LHS, RHS,
11618 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11623 if (WalkingBEDominatingConds)
11629 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11630 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11637 const SCEV *LoopCounter =
11645 for (
auto &AssumeVH : AC.assumptions()) {
11652 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11656 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11659 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11660 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11661 assert(DTN &&
"should reach the loop header before reaching the root!");
11664 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11672 if (!ContinuePredicate || !ContinuePredicate->
isConditional())
11686 assert(DT.dominates(DominatingEdge, Latch) &&
"should be!");
11688 if (isImpliedCond(Pred, LHS, RHS, Condition,
11702 if (!DT.isReachableFromEntry(BB))
11706 "This cannot be done on broken IR!");
11714 const bool ProvingStrictComparison =
11716 bool ProvedNonStrictComparison =
false;
11717 bool ProvedNonEquality =
false;
11720 if (!ProvedNonStrictComparison)
11721 ProvedNonStrictComparison = Fn(NonStrictPredicate);
11722 if (!ProvedNonEquality)
11724 if (ProvedNonStrictComparison && ProvedNonEquality)
11729 if (ProvingStrictComparison) {
11731 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
11733 if (SplitAndProve(ProofFn))
11738 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
11740 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
11742 if (ProvingStrictComparison) {
11744 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
11746 if (SplitAndProve(ProofFn))
11755 const Loop *ContainingLoop = LI.getLoopFor(BB);
11757 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
11761 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
11762 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
11774 for (
auto &AssumeVH : AC.assumptions()) {
11778 if (!DT.dominates(CI, BB))
11781 if (ProveViaCond(CI->getArgOperand(0),
false))
11787 F.getParent(), Intrinsic::experimental_guard);
11789 for (
const auto *GU : GuardDecl->users())
11791 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
11792 if (ProveViaCond(Guard->getArgOperand(0),
false))
11807 "LHS is not available at Loop Entry");
11809 "RHS is not available at Loop Entry");
11811 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11822 if (FoundCondValue ==
11826 if (!PendingLoopPredicates.insert(FoundCondValue).second)
11830 make_scope_exit([&]() { PendingLoopPredicates.erase(FoundCondValue); });
11833 const Value *Op0, *Op1;
11836 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
11840 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
11841 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
11845 if (!ICI)
return false;
11849 CmpPredicate FoundPred;
11858 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
11861bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
11862 const SCEV *
RHS, CmpPredicate FoundPred,
11863 const SCEV *FoundLHS,
const SCEV *FoundRHS,
11864 const Instruction *CtxI) {
11874 auto *WideType = FoundLHS->
getType();
11886 TruncFoundLHS, TruncFoundRHS, CtxI))
11912 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
11916bool ScalarEvolution::isImpliedCondBalancedTypes(
11917 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
11918 const SCEV *FoundLHS,
const SCEV *FoundRHS,
const Instruction *CtxI) {
11921 "Types should be balanced!");
11928 if (FoundLHS == FoundRHS)
11932 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
11944 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
11961 LHS, FoundLHS, FoundRHS, CtxI);
11963 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
11985 assert(P1 != P2 &&
"Handled earlier!");
11989 if (IsSignFlippedPredicate(Pred, FoundPred)) {
11994 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
11997 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
11998 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
11999 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12004 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12015 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12016 CanonicalRHS, CanonicalFoundLHS,
12017 CanonicalFoundRHS);
12022 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12023 CanonicalRHS, CanonicalFoundLHS,
12024 CanonicalFoundRHS);
12031 const SCEVConstant *
C =
nullptr;
12032 const SCEV *
V =
nullptr;
12050 if (Min ==
C->getAPInt()) {
12055 APInt SharperMin = Min + 1;
12058 case ICmpInst::ICMP_SGE:
12059 case ICmpInst::ICMP_UGE:
12062 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12067 case ICmpInst::ICMP_SGT:
12068 case ICmpInst::ICMP_UGT:
12078 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12083 case ICmpInst::ICMP_SLE:
12084 case ICmpInst::ICMP_ULE:
12085 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12086 LHS, V, getConstant(SharperMin), CtxI))
12090 case ICmpInst::ICMP_SLT:
12091 case ICmpInst::ICMP_ULT:
12092 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12093 LHS, V, getConstant(Min), CtxI))
12107 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12111 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12114 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12121bool ScalarEvolution::splitBinaryAdd(
const SCEV *Expr,
12122 const SCEV *&L,
const SCEV *&R,
12125 if (!AE || AE->getNumOperands() != 2)
12128 L = AE->getOperand(0);
12129 R = AE->getOperand(1);
12130 Flags = AE->getNoWrapFlags();
12134std::optional<APInt>
12141 APInt DiffMul(BW, 1);
12144 for (
unsigned I = 0;
I < 8; ++
I) {
12153 if (LAR->getLoop() != MAR->getLoop())
12154 return std::nullopt;
12158 if (!LAR->isAffine() || !MAR->isAffine())
12159 return std::nullopt;
12161 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12162 return std::nullopt;
12164 Less = LAR->getStart();
12165 More = MAR->getStart();
12170 auto MatchConstMul =
12171 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12173 if (!M || M->getNumOperands() != 2 ||
12175 return std::nullopt;
12179 if (
auto MatchedMore = MatchConstMul(More)) {
12180 if (
auto MatchedLess = MatchConstMul(
Less)) {
12181 if (MatchedMore->second == MatchedLess->second) {
12182 More = MatchedMore->first;
12183 Less = MatchedLess->first;
12184 DiffMul *= MatchedMore->second;
12195 Diff +=
C->getAPInt() * DiffMul;
12198 Diff -=
C->getAPInt() * DiffMul;
12201 Multiplicity[S] +=
Mul;
12203 auto Decompose = [&](
const SCEV *S,
int Mul) {
12210 Decompose(More, 1);
12211 Decompose(
Less, -1);
12215 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12216 for (
const auto &[S,
Mul] : Multiplicity) {
12221 return std::nullopt;
12223 }
else if (
Mul == -1) {
12225 return std::nullopt;
12228 return std::nullopt;
12232 if (NewMore == More || NewLess ==
Less)
12233 return std::nullopt;
12239 if (!More && !
Less)
12243 if (!More || !
Less)
12244 return std::nullopt;
12248 return std::nullopt;
12251bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12275 if (!L->contains(ContextBB) || !DT.
dominates(ContextBB, L->getLoopLatch()))
12286 if (!L->contains(ContextBB) || !DT.
dominates(ContextBB, L->getLoopLatch()))
12296bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12299 const SCEV *FoundLHS,
12300 const SCEV *FoundRHS) {
12309 if (!AddRecFoundLHS)
12316 const Loop *
L = AddRecFoundLHS->getLoop();
12317 if (L != AddRecLHS->getLoop())
12356 if (!RDiff || *LDiff != *RDiff)
12359 if (LDiff->isMinValue())
12362 APInt FoundRHSLimit;
12365 FoundRHSLimit = -(*RDiff);
12377bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12378 const SCEV *
RHS,
const SCEV *FoundLHS,
12379 const SCEV *FoundRHS,
unsigned Depth) {
12380 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12384 bool Erased = PendingMerges.erase(LPhi);
12385 assert(Erased &&
"Failed to erase LPhi!");
12389 bool Erased = PendingMerges.erase(RPhi);
12390 assert(Erased &&
"Failed to erase RPhi!");
12398 if (!PendingMerges.insert(Phi).second)
12412 if (!PendingMerges.insert(Phi).second)
12418 if (!LPhi && !RPhi)
12429 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12433 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12434 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12435 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12436 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12439 if (RPhi && RPhi->getParent() == LBB) {
12446 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12447 if (!ProvedEasily(L, R))
12458 auto *RLoop = RAR->
getLoop();
12459 auto *Predecessor = RLoop->getLoopPredecessor();
12460 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12462 if (!ProvedEasily(L1, RAR->
getStart()))
12464 auto *Latch = RLoop->getLoopLatch();
12465 assert(Latch &&
"Loop with AddRec with no latch?");
12486 if (
auto *Loop = LI.getLoopFor(LBB))
12489 if (!ProvedEasily(L,
RHS))
12496bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12499 const SCEV *FoundLHS,
12500 const SCEV *FoundRHS) {
12503 if (
RHS == FoundRHS) {
12508 if (
LHS != FoundLHS)
12515 Value *Shiftee, *ShiftValue;
12517 using namespace PatternMatch;
12518 if (
match(SUFoundRHS->getValue(),
12520 auto *ShifteeS =
getSCEV(Shiftee);
12538bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12540 const SCEV *FoundLHS,
12541 const SCEV *FoundRHS,
12542 const Instruction *CtxI) {
12543 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12545 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12547 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12548 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12550 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12554template <
typename MinMaxExprType>
12556 const SCEV *Candidate) {
12561 return is_contained(MinMaxExpr->operands(), Candidate);
12574 const SCEV *LStart, *RStart, *Step;
12624bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12626 const SCEV *FoundLHS,
12627 const SCEV *FoundRHS,
12631 "LHS and RHS have different sizes?");
12634 "FoundLHS and FoundRHS have different sizes?");
12668 auto GetOpFromSExt = [&](
const SCEV *S) {
12670 return Ext->getOperand();
12677 auto *OrigLHS =
LHS;
12678 auto *OrigFoundLHS = FoundLHS;
12679 LHS = GetOpFromSExt(
LHS);
12680 FoundLHS = GetOpFromSExt(FoundLHS);
12683 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
12686 FoundRHS,
Depth + 1);
12699 if (!LHSAddExpr->hasNoSignedWrap())
12702 auto *LL = LHSAddExpr->getOperand(0);
12703 auto *LR = LHSAddExpr->getOperand(1);
12707 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
12708 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
12713 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
12719 using namespace llvm::PatternMatch;
12738 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
12746 auto *DTy = Denominator->getType();
12747 auto *FRHSTy = FoundRHS->
getType();
12748 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
12767 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
12778 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
12780 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
12788 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
12821bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
12825 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
12828 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
12831bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
12834 const SCEV *FoundLHS,
12835 const SCEV *FoundRHS) {
12871 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
12877bool ScalarEvolution::isImpliedCondOperandsViaRanges(
12878 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
12879 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
12893 ConstantRange FoundLHSRange =
12897 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
12904 return LHSRange.
icmp(Pred, ConstRHS);
12907bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
12920 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
12928 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
12931bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
12943 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
12951 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
12963const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
12964 const SCEV *Stride,
12995 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13006 :
APIntOps::umax(MaxEnd, MinStart);
13013ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13014 const Loop *L,
bool IsSigned,
13015 bool ControlsOnlyExit,
bool AllowPredicates) {
13019 bool PredicatedIV =
false;
13024 auto canProveNUW = [&]() {
13027 if (!ControlsOnlyExit)
13048 Limit = Limit.
zext(OuterBitWidth);
13060 Type *Ty = ZExt->getType();
13071 if (!
IV && AllowPredicates) {
13076 PredicatedIV =
true;
13080 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13094 bool NoWrap = ControlsOnlyExit &&
IV->getNoWrapFlags(WrapType);
13097 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13102 if (!PositiveStride) {
13154 auto wouldZeroStrideBeUB = [&]() {
13166 if (!wouldZeroStrideBeUB()) {
13170 }
else if (!NoWrap) {
13173 if (canIVOverflowOnLT(
RHS, Stride, IsSigned))
13186 const SCEV *
Start =
IV->getStart();
13192 const SCEV *OrigStart =
Start;
13193 const SCEV *OrigRHS =
RHS;
13194 if (
Start->getType()->isPointerTy()) {
13205 const SCEV *End =
nullptr, *BECount =
nullptr,
13206 *BECountIfBackedgeTaken =
nullptr;
13209 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13210 RHSAddRec->getNoWrapFlags()) {
13223 const SCEV *RHSStart = RHSAddRec->getStart();
13224 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13236 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13245 BECountIfBackedgeTaken =
13250 if (BECount ==
nullptr) {
13255 const SCEV *MaxBECount = computeMaxBECountForLT(
13258 MaxBECount,
false , Predicates);
13265 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13292 const SCEV *Numerator =
13298 auto canProveRHSGreaterThanEqualStart = [&]() {
13317 auto *StartMinusOne =
13324 if (canProveRHSGreaterThanEqualStart()) {
13339 BECountIfBackedgeTaken =
13355 bool MayAddOverflow = [&] {
13401 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13415 if (!MayAddOverflow) {
13427 const SCEV *ConstantMaxBECount;
13428 bool MaxOrZero =
false;
13430 ConstantMaxBECount = BECount;
13431 }
else if (BECountIfBackedgeTaken &&
13436 ConstantMaxBECount = BECountIfBackedgeTaken;
13439 ConstantMaxBECount = computeMaxBECountForLT(
13447 const SCEV *SymbolicMaxBECount =
13449 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13453ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13454 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13455 bool ControlsOnlyExit,
bool AllowPredicates) {
13462 if (!
IV && AllowPredicates)
13469 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13473 bool NoWrap = ControlsOnlyExit &&
IV->getNoWrapFlags(WrapType);
13486 if (!Stride->
isOne() && !NoWrap)
13487 if (canIVOverflowOnGT(
RHS, Stride, IsSigned))
13490 const SCEV *
Start =
IV->getStart();
13491 const SCEV *End =
RHS;
13502 if (
Start->getType()->isPointerTy()) {
13537 const SCEV *ConstantMaxBECount =
13544 ConstantMaxBECount = BECount;
13545 const SCEV *SymbolicMaxBECount =
13548 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13554 if (
Range.isFullSet())
13559 if (!SC->getValue()->isZero()) {
13565 return ShiftedAddRec->getNumIterationsInRange(
13566 Range.subtract(SC->getAPInt()), SE);
13597 APInt ExitVal = (End +
A).udiv(
A);
13610 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13611 "Linear scev computation is off in a bad way!");
13642 assert(!
Last->isZero() &&
"Recurrency with zero step?");
13670 Ty = Store->getValueOperand()->getType();
13672 Ty = Load->getType();
13685 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13687 SE->ConstantEvolutionLoopExitValue.erase(PN);
13688 SE->eraseValueFromMap(getValPtr());
13692void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
13693 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13703 : CallbackVH(
V), SE(se) {}
13712 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
13714 LoopDispositions(64), BlockDispositions(64) {
13726 F.getParent(), Intrinsic::experimental_guard);
13727 HasGuards = GuardDecl && !GuardDecl->use_empty();
13731 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
13732 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
13733 ValueExprMap(
std::
move(Arg.ValueExprMap)),
13734 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
13735 PendingPhiRanges(
std::
move(Arg.PendingPhiRanges)),
13736 PendingMerges(
std::
move(Arg.PendingMerges)),
13737 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
13738 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
13739 PredicatedBackedgeTakenCounts(
13740 std::
move(Arg.PredicatedBackedgeTakenCounts)),
13741 BECountUsers(
std::
move(Arg.BECountUsers)),
13742 ConstantEvolutionLoopExitValue(
13743 std::
move(Arg.ConstantEvolutionLoopExitValue)),
13744 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
13745 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
13746 LoopDispositions(
std::
move(Arg.LoopDispositions)),
13747 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
13748 BlockDispositions(
std::
move(Arg.BlockDispositions)),
13749 SCEVUsers(
std::
move(Arg.SCEVUsers)),
13750 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
13751 SignedRanges(
std::
move(Arg.SignedRanges)),
13752 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
13753 UniquePreds(
std::
move(Arg.UniquePreds)),
13754 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
13755 LoopUsers(
std::
move(Arg.LoopUsers)),
13756 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
13757 FirstUnknown(Arg.FirstUnknown) {
13758 Arg.FirstUnknown =
nullptr;
13767 Tmp->~SCEVUnknown();
13769 FirstUnknown =
nullptr;
13771 ExprValueMap.clear();
13772 ValueExprMap.clear();
13774 BackedgeTakenCounts.clear();
13775 PredicatedBackedgeTakenCounts.clear();
13777 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
13778 assert(PendingPhiRanges.empty() &&
"getRangeRef garbage");
13779 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
13780 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
13781 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
13803 L->getHeader()->printAsOperand(OS,
false);
13807 L->getExitingBlocks(ExitingBlocks);
13808 if (ExitingBlocks.
size() != 1)
13809 OS <<
"<multiple exits> ";
13813 OS <<
"backedge-taken count is ";
13816 OS <<
"Unpredictable backedge-taken count.";
13819 if (ExitingBlocks.
size() > 1)
13820 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
13821 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
13829 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
13832 OS <<
"\n Predicates:\n";
13833 for (
const auto *
P : Predicates)
13841 L->getHeader()->printAsOperand(OS,
false);
13846 OS <<
"constant max backedge-taken count is ";
13849 OS <<
", actual taken count either this or zero.";
13851 OS <<
"Unpredictable constant max backedge-taken count. ";
13856 L->getHeader()->printAsOperand(OS,
false);
13861 OS <<
"symbolic max backedge-taken count is ";
13864 OS <<
", actual taken count either this or zero.";
13866 OS <<
"Unpredictable symbolic max backedge-taken count. ";
13870 if (ExitingBlocks.
size() > 1)
13871 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
13872 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
13882 OS <<
"\n predicated symbolic max exit count for "
13883 << ExitingBlock->
getName() <<
": ";
13885 OS <<
"\n Predicates:\n";
13886 for (
const auto *
P : Predicates)
13896 assert(!Preds.
empty() &&
"Different predicated BTC, but no predicates");
13898 L->getHeader()->printAsOperand(OS,
false);
13901 OS <<
"Predicated backedge-taken count is ";
13904 OS <<
"Unpredictable predicated backedge-taken count.";
13906 OS <<
" Predicates:\n";
13907 for (
const auto *
P : Preds)
13912 auto *PredConstantMax =
13914 if (PredConstantMax != ConstantBTC) {
13916 "different predicated constant max BTC but no predicates");
13918 L->getHeader()->printAsOperand(OS,
false);
13921 OS <<
"Predicated constant max backedge-taken count is ";
13924 OS <<
"Unpredictable predicated constant max backedge-taken count.";
13926 OS <<
" Predicates:\n";
13927 for (
const auto *
P : Preds)
13932 auto *PredSymbolicMax =
13934 if (SymbolicBTC != PredSymbolicMax) {
13936 "Different predicated symbolic max BTC, but no predicates");
13938 L->getHeader()->printAsOperand(OS,
false);
13941 OS <<
"Predicated symbolic max backedge-taken count is ";
13944 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
13946 OS <<
" Predicates:\n";
13947 for (
const auto *
P : Preds)
13953 L->getHeader()->printAsOperand(OS,
false);
13969 OS <<
"Computable";
13978 OS <<
"DoesNotDominate";
13984 OS <<
"ProperlyDominates";
14001 OS <<
"Classifying expressions for: ";
14002 F.printAsOperand(OS,
false);
14017 const Loop *L = LI.getLoopFor(
I.getParent());
14032 OS <<
"\t\t" "Exits: ";
14035 OS <<
"<<Unknown>>";
14041 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14043 OS <<
"\t\t" "LoopDispositions: { ";
14049 Iter->getHeader()->printAsOperand(OS,
false);
14057 OS <<
"\t\t" "LoopDispositions: { ";
14063 InnerL->getHeader()->printAsOperand(OS,
false);
14074 OS <<
"Determining loop execution counts for: ";
14075 F.printAsOperand(OS,
false);
14083 auto &Values = LoopDispositions[S];
14084 for (
auto &V : Values) {
14085 if (V.getPointer() == L)
14090 auto &Values2 = LoopDispositions[S];
14092 if (V.getPointer() == L) {
14101ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14120 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14121 " dominate the contained loop's header?");
14148 bool HasVarying =
false;
14182 auto &Values = BlockDispositions[S];
14183 for (
auto &V : Values) {
14184 if (V.getPointer() == BB)
14189 auto &Values2 = BlockDispositions[S];
14191 if (V.getPointer() == BB) {
14200ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14229 bool Proper =
true;
14240 if (Instruction *
I =
14242 if (
I->getParent() == BB)
14244 if (DT.properlyDominates(
I->getParent(), BB))
14267void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14270 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14271 auto It = BECounts.find(L);
14272 if (It != BECounts.end()) {
14273 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14274 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14276 auto UserIt = BECountUsers.find(S);
14277 assert(UserIt != BECountUsers.end());
14282 BECounts.erase(It);
14290 while (!Worklist.
empty()) {
14292 auto Users = SCEVUsers.find(Curr);
14293 if (
Users != SCEVUsers.end())
14294 for (
const auto *User :
Users->second)
14295 if (ToForget.
insert(User).second)
14299 for (
const auto *S : ToForget)
14300 forgetMemoizedResultsImpl(S);
14302 for (
auto I = PredicatedSCEVRewrites.begin();
14303 I != PredicatedSCEVRewrites.end();) {
14304 std::pair<const SCEV *, const Loop *>
Entry =
I->first;
14305 if (ToForget.count(
Entry.first))
14306 PredicatedSCEVRewrites.erase(
I++);
14312void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14313 LoopDispositions.erase(S);
14314 BlockDispositions.erase(S);
14315 UnsignedRanges.erase(S);
14316 SignedRanges.erase(S);
14317 HasRecMap.erase(S);
14318 ConstantMultipleCache.erase(S);
14321 UnsignedWrapViaInductionTried.erase(AR);
14322 SignedWrapViaInductionTried.erase(AR);
14325 auto ExprIt = ExprValueMap.find(S);
14326 if (ExprIt != ExprValueMap.end()) {
14327 for (
Value *V : ExprIt->second) {
14328 auto ValueIt = ValueExprMap.find_as(V);
14329 if (ValueIt != ValueExprMap.end())
14330 ValueExprMap.erase(ValueIt);
14332 ExprValueMap.erase(ExprIt);
14335 auto ScopeIt = ValuesAtScopes.find(S);
14336 if (ScopeIt != ValuesAtScopes.end()) {
14337 for (
const auto &Pair : ScopeIt->second)
14340 std::make_pair(Pair.first, S));
14341 ValuesAtScopes.erase(ScopeIt);
14344 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14345 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14346 for (
const auto &Pair : ScopeUserIt->second)
14347 llvm::erase(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
14348 ValuesAtScopesUsers.erase(ScopeUserIt);
14351 auto BEUsersIt = BECountUsers.find(S);
14352 if (BEUsersIt != BECountUsers.end()) {
14354 auto Copy = BEUsersIt->second;
14355 for (
const auto &Pair : Copy)
14356 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14357 BECountUsers.erase(BEUsersIt);
14360 auto FoldUser = FoldCacheUser.find(S);
14361 if (FoldUser != FoldCacheUser.end())
14362 for (
auto &KV : FoldUser->second)
14363 FoldCache.erase(KV);
14364 FoldCacheUser.erase(S);
14368ScalarEvolution::getUsedLoops(
const SCEV *S,
14370 struct FindUsedLoops {
14371 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14372 : LoopsUsed(LoopsUsed) {}
14373 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14374 bool follow(
const SCEV *S) {
14380 bool isDone()
const {
return false; }
14383 FindUsedLoops
F(LoopsUsed);
14384 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14387void ScalarEvolution::getReachableBlocks(
14390 Worklist.
push_back(&F.getEntryBlock());
14391 while (!Worklist.
empty()) {
14393 if (!Reachable.
insert(BB).second)
14401 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14408 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14412 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14447 SCEVMapper SCM(SE2);
14449 SE2.getReachableBlocks(ReachableBlocks, F);
14451 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14469 while (!LoopStack.
empty()) {
14475 if (!ReachableBlocks.
contains(L->getHeader()))
14480 auto It = BackedgeTakenCounts.find(L);
14481 if (It == BackedgeTakenCounts.end())
14485 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14505 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14506 if (Delta && !Delta->
isZero()) {
14507 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14508 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14509 dbgs() <<
"New: " << *NewBECount <<
"\n";
14510 dbgs() <<
"Delta: " << *Delta <<
"\n";
14518 while (!Worklist.
empty()) {
14520 if (ValidLoops.
insert(L).second)
14521 Worklist.
append(L->begin(), L->end());
14523 for (
const auto &KV : ValueExprMap) {
14528 "AddRec references invalid loop");
14533 auto It = ExprValueMap.find(KV.second);
14534 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14535 dbgs() <<
"Value " << *KV.first
14536 <<
" is in ValueExprMap but not in ExprValueMap\n";
14541 if (!ReachableBlocks.
contains(
I->getParent()))
14543 const SCEV *OldSCEV = SCM.visit(KV.second);
14545 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14546 if (Delta && !Delta->
isZero()) {
14547 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14548 <<
"Old: " << *OldSCEV <<
"\n"
14549 <<
"New: " << *NewSCEV <<
"\n"
14550 <<
"Delta: " << *Delta <<
"\n";
14556 for (
const auto &KV : ExprValueMap) {
14557 for (
Value *V : KV.second) {
14558 const SCEV *S = ValueExprMap.lookup(V);
14560 dbgs() <<
"Value " << *V
14561 <<
" is in ExprValueMap but not in ValueExprMap\n";
14564 if (S != KV.first) {
14565 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14566 << *KV.first <<
"\n";
14573 for (
const auto &S : UniqueSCEVs) {
14578 auto It = SCEVUsers.find(
Op);
14579 if (It != SCEVUsers.end() && It->second.count(&S))
14581 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14582 <<
" is not being tracked!\n";
14588 for (
const auto &ValueAndVec : ValuesAtScopes) {
14590 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14591 const Loop *L = LoopAndValueAtScope.first;
14592 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
14594 auto It = ValuesAtScopesUsers.find(ValueAtScope);
14595 if (It != ValuesAtScopesUsers.end() &&
14598 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14599 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14605 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14606 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14607 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14608 const Loop *L = LoopAndValue.first;
14609 const SCEV *
Value = LoopAndValue.second;
14611 auto It = ValuesAtScopes.find(
Value);
14612 if (It != ValuesAtScopes.end() &&
14613 is_contained(It->second, std::make_pair(L, ValueAtScope)))
14615 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14616 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14622 auto VerifyBECountUsers = [&](
bool Predicated) {
14624 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14625 for (
const auto &LoopAndBEInfo : BECounts) {
14626 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14627 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14629 auto UserIt = BECountUsers.find(S);
14630 if (UserIt != BECountUsers.end() &&
14631 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14633 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14634 <<
" missing from BECountUsers\n";
14641 VerifyBECountUsers(
false);
14642 VerifyBECountUsers(
true);
14645 for (
auto &[S, Values] : LoopDispositions) {
14646 for (
auto [
Loop, CachedDisposition] : Values) {
14648 if (CachedDisposition != RecomputedDisposition) {
14649 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
14650 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
14651 << RecomputedDisposition <<
"\n";
14658 for (
auto &[S, Values] : BlockDispositions) {
14659 for (
auto [BB, CachedDisposition] : Values) {
14661 if (CachedDisposition != RecomputedDisposition) {
14662 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
14663 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
14664 <<
", actual " << RecomputedDisposition <<
"\n";
14671 for (
auto [
FoldID, Expr] : FoldCache) {
14672 auto I = FoldCacheUser.find(Expr);
14673 if (
I == FoldCacheUser.end()) {
14674 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
14679 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
14683 for (
auto [Expr, IDs] : FoldCacheUser) {
14684 for (
auto &
FoldID : IDs) {
14687 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
14692 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
14693 <<
" != " << *Expr <<
"!\n";
14704 for (
auto [S, Multiple] : ConstantMultipleCache) {
14706 if ((Multiple != 0 && RecomputedMultiple != 0 &&
14707 Multiple.
urem(RecomputedMultiple) != 0 &&
14708 RecomputedMultiple.
urem(Multiple) != 0)) {
14709 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
14710 << *S <<
" : Computed " << RecomputedMultiple
14711 <<
" but cache contains " << Multiple <<
"!\n";
14719 FunctionAnalysisManager::Invalidator &Inv) {
14751 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
14752 <<
F.getName() <<
"':\n";
14758 "Scalar Evolution Analysis",
false,
true)
14807 const SCEV *LHS,
const SCEV *RHS) {
14809 assert(LHS->getType() == RHS->getType() &&
14810 "Type mismatch between LHS and RHS");
14813 ID.AddInteger(Pred);
14814 ID.AddPointer(LHS);
14815 ID.AddPointer(RHS);
14816 void *IP =
nullptr;
14817 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
14821 UniquePreds.InsertNode(Eq, IP);
14832 ID.AddInteger(AddedFlags);
14833 void *IP =
nullptr;
14834 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
14836 auto *OF =
new (SCEVAllocator)
14838 UniquePreds.InsertNode(OF, IP);
14858 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
14859 return Rewriter.visit(S);
14865 for (
const auto *Pred : U->getPredicates())
14867 if (IPred->getLHS() == Expr &&
14869 return IPred->getRHS();
14871 if (IPred->getLHS() == Expr &&
14872 IPred->getPredicate() == ICmpInst::ICMP_EQ)
14873 return IPred->getRHS();
14876 return convertToAddRecWithPreds(Expr);
14879 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
14895 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
14912 explicit SCEVPredicateRewriter(
14913 const Loop *L, ScalarEvolution &SE,
14914 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
14915 const SCEVPredicate *Pred)
14916 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
14918 bool addOverflowAssumption(
const SCEVPredicate *
P) {
14921 return Pred && Pred->
implies(
P, SE);
14927 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
14930 return addOverflowAssumption(
A);
14939 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
14943 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
14945 if (!PredicatedRewrite)
14947 for (
const auto *
P : PredicatedRewrite->second){
14950 if (L != WP->getExpr()->getLoop())
14953 if (!addOverflowAssumption(
P))
14956 return PredicatedRewrite->first;
14959 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
14960 const SCEVPredicate *Pred;
14969 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
14976 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
14996 if (!Step->
isOne())
15021 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15022 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15035 return Op->LHS == LHS &&
Op->RHS == RHS;
15042 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15044 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15069 const SCEV *Start = AR->getStart();
15070 const SCEV *OpStart =
Op->AR->getStart();
15075 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15078 const SCEV *Step = AR->getStepRecurrence(SE);
15079 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15132 if (Step->getValue()->getValue().isNonNegative())
15136 return ImpliedFlags;
15143 for (
const auto *
P : Preds)
15156 return this->implies(I, SE);
15164 for (
const auto *Pred : Preds)
15165 Pred->print(OS,
Depth);
15170 for (
const auto *Pred : Set->Preds)
15182 for (
auto *
P : Preds) {
15183 if (
N->implies(
P, SE))
15187 Preds = std::move(PrunedPreds);
15188 Preds.push_back(
N);
15195 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15200 for (
const auto *
Op :
Ops)
15205 SCEVUsers[
Op].insert(
User);
15209 const SCEV *Expr = SE.getSCEV(V);
15210 RewriteEntry &Entry = RewriteMap[Expr];
15213 if (Entry.second && Generation == Entry.first)
15214 return Entry.second;
15219 Expr = Entry.second;
15221 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15222 Entry = {Generation, NewSCEV};
15228 if (!BackedgeCount) {
15230 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15231 for (
const auto *
P : Preds)
15234 return BackedgeCount;
15238 if (!SymbolicMaxBackedgeCount) {
15240 SymbolicMaxBackedgeCount =
15241 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15242 for (
const auto *
P : Preds)
15245 return SymbolicMaxBackedgeCount;
15249 if (!SmallConstantMaxTripCount) {
15251 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15252 for (
const auto *
P : Preds)
15255 return *SmallConstantMaxTripCount;
15259 if (Preds->implies(&Pred, SE))
15264 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15265 updateGeneration();
15272void PredicatedScalarEvolution::updateGeneration() {
15274 if (++Generation == 0) {
15275 for (
auto &
II : RewriteMap) {
15276 const SCEV *Rewritten =
II.second.second;
15293 auto II = FlagsMap.insert({V, Flags});
15306 auto II = FlagsMap.find(V);
15308 if (
II != FlagsMap.end())
15317 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15322 for (
const auto *
P : NewPreds)
15325 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15331 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15334 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {
15335 for (
auto I :
Init.FlagsMap)
15336 FlagsMap.insert(
I);
15341 for (
auto *BB : L.getBlocks())
15342 for (
auto &
I : *BB) {
15343 if (!SE.isSCEVable(
I.getType()))
15346 auto *Expr = SE.getSCEV(&
I);
15347 auto II = RewriteMap.find(Expr);
15349 if (
II == RewriteMap.end())
15353 if (
II->second.second == Expr)
15358 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15367bool ScalarEvolution::matchURem(
const SCEV *Expr,
const SCEV *&LHS,
15368 const SCEV *&RHS) {
15377 LHS = Trunc->getOperand();
15383 if (LHS->getType() != Expr->
getType())
15390 if (
Add ==
nullptr ||
Add->getNumOperands() != 2)
15393 const SCEV *
A =
Add->getOperand(1);
15396 if (
Mul ==
nullptr)
15399 const auto MatchURemWithDivisor = [&](
const SCEV *
B) {
15411 return MatchURemWithDivisor(
Mul->getOperand(1)) ||
15412 MatchURemWithDivisor(
Mul->getOperand(2));
15415 if (
Mul->getNumOperands() == 2)
15416 return MatchURemWithDivisor(
Mul->getOperand(1)) ||
15417 MatchURemWithDivisor(
Mul->getOperand(0)) ||
15427 LoopGuards Guards(SE);
15431 collectFromBlock(SE, Guards, Header, Pred, VisitedBlocks);
15435void ScalarEvolution::LoopGuards::collectFromPHI(
15443 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15444 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15450 collectFromBlock(SE,
G->second, Phi.getParent(),
InBlock, VisitedBlocks,
15452 auto &RewriteMap =
G->second.RewriteMap;
15453 if (RewriteMap.empty())
15455 auto S = RewriteMap.find(SE.
getSCEV(Phi.getIncomingValue(IncomingIdx)));
15456 if (S == RewriteMap.end())
15462 return {C0, SM->getSCEVType()};
15465 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15466 MinMaxPattern P2) -> MinMaxPattern {
15467 auto [C1,
T1] =
P1;
15468 auto [C2, T2] = P2;
15469 if (!C1 || !C2 ||
T1 != T2)
15473 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15475 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15477 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15479 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15484 auto P = GetMinMaxConst(0);
15485 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15488 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15491 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15494 Guards.RewriteMap.insert({
LHS,
RHS});
15498void ScalarEvolution::LoopGuards::collectFromBlock(
15500 const BasicBlock *
Block,
const BasicBlock *Pred,
15501 SmallPtrSetImpl<const BasicBlock *> &VisitedBlocks,
unsigned Depth) {
15505 DenseMap<const SCEV *, const SCEV *>
15522 &ExprsToRewrite]() {
15523 const SCEVConstant *C1;
15536 if (ExactRegion.isWrappedSet() || ExactRegion.isFullSet())
15538 auto [
I,
Inserted] = RewriteMap.try_emplace(LHSUnknown);
15539 const SCEV *RewrittenLHS =
Inserted ? LHSUnknown :
I->second;
15547 if (MatchRangeCheckIdiom())
15553 auto IsMinMaxSCEVWithNonNegativeConstant =
15554 [&](
const SCEV *Expr,
SCEVTypes &SCTy,
const SCEV *&
LHS,
15555 const SCEV *&
RHS) {
15557 if (MinMax->getNumOperands() != 2)
15560 if (
C->getAPInt().isNegative())
15562 SCTy = MinMax->getSCEVType();
15563 LHS = MinMax->getOperand(0);
15564 RHS = MinMax->getOperand(1);
15573 auto GetNonNegExprAndPosDivisor = [&](
const SCEV *Expr,
const SCEV *Divisor,
15574 APInt &ExprVal, APInt &DivisorVal) {
15577 if (!ConstExpr || !ConstDivisor)
15579 ExprVal = ConstExpr->getAPInt();
15580 DivisorVal = ConstDivisor->getAPInt();
15581 return ExprVal.isNonNegative() && !DivisorVal.isNonPositive();
15587 auto GetNextSCEVDividesByDivisor = [&](
const SCEV *Expr,
15588 const SCEV *Divisor) {
15591 if (!GetNonNegExprAndPosDivisor(Expr, Divisor, ExprVal, DivisorVal))
15593 APInt Rem = ExprVal.
urem(DivisorVal);
15596 return SE.
getConstant(ExprVal + DivisorVal - Rem);
15603 auto GetPreviousSCEVDividesByDivisor = [&](
const SCEV *Expr,
15604 const SCEV *Divisor) {
15607 if (!GetNonNegExprAndPosDivisor(Expr, Divisor, ExprVal, DivisorVal))
15609 APInt Rem = ExprVal.
urem(DivisorVal);
15617 std::function<
const SCEV *(
const SCEV *,
const SCEV *)>
15618 ApplyDivisibiltyOnMinMaxExpr = [&](
const SCEV *MinMaxExpr,
15619 const SCEV *Divisor) {
15620 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15622 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15628 "Expected non-negative operand!");
15629 auto *DivisibleExpr =
15630 IsMin ? GetPreviousSCEVDividesByDivisor(MinMaxLHS, Divisor)
15631 : GetNextSCEVDividesByDivisor(MinMaxLHS, Divisor);
15633 ApplyDivisibiltyOnMinMaxExpr(MinMaxRHS, Divisor), DivisibleExpr};
15642 const SCEV *URemLHS =
nullptr;
15643 const SCEV *URemRHS =
nullptr;
15644 if (SE.matchURem(
LHS, URemLHS, URemRHS)) {
15646 auto I = RewriteMap.find(LHSUnknown);
15647 const SCEV *RewrittenLHS =
15648 I != RewriteMap.end() ?
I->second : LHSUnknown;
15649 RewrittenLHS = ApplyDivisibiltyOnMinMaxExpr(RewrittenLHS, URemRHS);
15650 const auto *Multiple =
15652 RewriteMap[LHSUnknown] = Multiple;
15673 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15675 if (From == FromRewritten)
15677 RewriteMap[From] = To;
15683 auto GetMaybeRewritten = [&](
const SCEV *S) {
15684 return RewriteMap.lookup_or(S, S);
15694 std::function<bool(
const SCEV *,
const SCEV *&)> HasDivisibiltyInfo =
15695 [&](
const SCEV *Expr,
const SCEV *&DividesBy) {
15697 if (
Mul->getNumOperands() != 2)
15699 auto *MulLHS =
Mul->getOperand(0);
15700 auto *MulRHS =
Mul->getOperand(1);
15704 if (Div->getOperand(1) == MulRHS) {
15705 DividesBy = MulRHS;
15710 return HasDivisibiltyInfo(MinMax->getOperand(0), DividesBy) ||
15711 HasDivisibiltyInfo(MinMax->getOperand(1), DividesBy);
15716 std::function<bool(
const SCEV *,
const SCEV *&)> IsKnownToDivideBy =
15717 [&](
const SCEV *Expr,
const SCEV *DividesBy) {
15721 return IsKnownToDivideBy(MinMax->getOperand(0), DividesBy) &&
15722 IsKnownToDivideBy(MinMax->getOperand(1), DividesBy);
15726 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15727 const SCEV *DividesBy =
nullptr;
15728 if (HasDivisibiltyInfo(RewrittenLHS, DividesBy))
15731 IsKnownToDivideBy(RewrittenLHS, DividesBy) ? DividesBy :
nullptr;
15745 switch (Predicate) {
15753 RHS = DividesBy ? GetPreviousSCEVDividesByDivisor(
RHS, DividesBy) :
RHS;
15759 RHS = DividesBy ? GetNextSCEVDividesByDivisor(
RHS, DividesBy) :
RHS;
15763 RHS = DividesBy ? GetPreviousSCEVDividesByDivisor(
RHS, DividesBy) :
RHS;
15767 RHS = DividesBy ? GetNextSCEVDividesByDivisor(
RHS, DividesBy) :
RHS;
15774 SmallPtrSet<const SCEV *, 16> Visited;
15776 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
15780 while (!Worklist.
empty()) {
15784 if (!Visited.
insert(From).second)
15786 const SCEV *FromRewritten = GetMaybeRewritten(From);
15787 const SCEV *To =
nullptr;
15789 switch (Predicate) {
15794 EnqueueOperands(
UMax);
15800 EnqueueOperands(
SMax);
15806 EnqueueOperands(
UMin);
15812 EnqueueOperands(
SMin);
15820 const SCEV *OneAlignedUp =
15821 DividesBy ? GetNextSCEVDividesByDivisor(One, DividesBy) : One;
15822 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
15830 AddRewrite(From, FromRewritten, To);
15847 SE.F.
getParent(), Intrinsic::experimental_guard);
15849 for (
const auto *GU : GuardDecl->users())
15851 if (Guard->getFunction() ==
Block->getParent() &&
15860 unsigned NumCollectedConditions = 0;
15862 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
15864 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
15865 VisitedBlocks.
insert(Pair.second);
15866 const BranchInst *LoopEntryPredicate =
15873 NumCollectedConditions++;
15877 if (
Depth > 0 && NumCollectedConditions == 2)
15885 if (Pair.second->hasNPredecessorsOrMore(2) &&
15887 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
15888 for (
auto &Phi : Pair.second->phis())
15889 collectFromPHI(SE, Guards, Phi, VisitedBlocks, IncomingGuards,
Depth);
15896 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
15897 SmallVector<Value *, 8> Worklist;
15898 SmallPtrSet<Value *, 8> Visited;
15900 while (!Worklist.
empty()) {
15907 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
15910 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap);
15926 Guards.PreserveNUW =
true;
15927 Guards.PreserveNSW =
true;
15928 for (
const SCEV *Expr : ExprsToRewrite) {
15929 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
15930 Guards.PreserveNUW &=
15932 Guards.PreserveNSW &=
15939 if (ExprsToRewrite.size() > 1) {
15940 for (
const SCEV *Expr : ExprsToRewrite) {
15941 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
15942 Guards.RewriteMap.erase(Expr);
15943 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
15952 class SCEVLoopGuardRewriter
15962 if (Guards.PreserveNUW)
15964 if (Guards.PreserveNSW)
15971 return Map.lookup_or(Expr, Expr);
15975 if (
const SCEV *S = Map.lookup(Expr))
15982 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
15983 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
15984 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
15986 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
15987 if (
const SCEV *S = Map.lookup(NarrowExt))
15988 return SE.getZeroExtendExpr(S, Ty);
15989 Bitwidth = Bitwidth / 2;
15997 if (
const SCEV *S = Map.lookup(Expr))
16004 if (
const SCEV *S = Map.lookup(Expr))
16010 if (
const SCEV *S = Map.lookup(Expr))
16022 if (
const SCEV *S = Map.lookup(
16024 return SE.getAddExpr(Expr->
getOperand(0), S);
16058 if (RewriteMap.empty())
16061 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16062 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...
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)
mir Rename Register Operands
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 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 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 const SCEV * SolveLinEquationWithOverflow(const APInt &A, const SCEV *B, SmallVectorImpl< const SCEVPredicate * > *Predicates, ScalarEvolution &SE)
Finds the minimum unsigned root of the following equation:
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 * 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 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.
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< ResultElem > 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, bool HasCoroSuspendInst=false) 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 const SCEV * getGEPExpr(GEPOperator *GEP, const SmallVectorImpl< const SCEV * > &IndexExprs)
Returns an expression for a GEP.
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 APInt getConstantMultiple(const SCEV *S)
Returns the max constant multiple of S.
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 uint32_t getMinTrailingZeros(const SCEV *S)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
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.
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.
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
@ DominatesBlock
The SCEV dominates the block.
@ ProperlyDominatesBlock
The SCEV properly dominates the block.
@ DoesNotDominateBlock
The SCEV does not dominate the block.
LLVM_ABI const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
LLVM_ABI const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI void getPoisonGeneratingValues(SmallPtrSetImpl< const Value * > &Result, const SCEV *S)
Return the set of Values that, if poison, will definitively result in S being poison as well.
LLVM_ABI void forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
LLVM_ABI const SCEV * getVScale(Type *Ty)
LLVM_ABI unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
LLVM_ABI bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
LLVM_ABI const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
LLVM_ABI 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
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)
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)
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
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.
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)
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)
SCEVUnaryExpr_match< SCEVSignExtendExpr, Op0_t > m_scev_SExt(const Op0_t &Op0)
cst_pred_ty< is_zero > m_scev_Zero()
Match an integer 0.
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.
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)
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