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 APInt C1V = LHSC->getAPInt();
3233 const SCEV *NewMul =
nullptr;
3237 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3252 if (Idx <
Ops.size()) {
3253 bool DeletedMul =
false;
3259 Ops.erase(
Ops.begin()+Idx);
3283 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3286 Ops.erase(
Ops.begin()+i);
3291 if (!LIOps.
empty()) {
3304 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3320 if (
Ops.size() == 1)
return NewRec;
3323 for (
unsigned i = 0;; ++i)
3324 if (
Ops[i] == AddRec) {
3345 bool OpsModified =
false;
3346 for (
unsigned OtherIdx = Idx+1;
3360 bool Overflow =
false;
3367 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3371 z < ze && !Overflow; ++z) {
3374 if (LargerThan64Bits)
3375 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3377 Coeff = Coeff1*Coeff2;
3392 if (
Ops.size() == 2)
return NewAddRec;
3393 Ops[Idx] = NewAddRec;
3394 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3410 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3418 "SCEVURemExpr operand types don't match!");
3423 if (RHSC->getValue()->isOne())
3424 return getZero(LHS->getType());
3427 if (RHSC->getAPInt().isPowerOf2()) {
3428 Type *FullTy = LHS->getType();
3445 assert(!LHS->getType()->isPointerTy() &&
3446 "SCEVUDivExpr operand can't be pointer!");
3447 assert(LHS->getType() == RHS->getType() &&
3448 "SCEVUDivExpr operand types don't match!");
3455 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3463 if (RHSC->getValue()->isOne())
3468 if (!RHSC->getValue()->isZero()) {
3472 Type *Ty = LHS->getType();
3473 unsigned LZ = RHSC->getAPInt().countl_zero();
3477 if (!RHSC->getAPInt().isPowerOf2())
3485 const APInt &StepInt = Step->getAPInt();
3486 const APInt &DivInt = RHSC->getAPInt();
3487 if (!StepInt.
urem(DivInt) &&
3493 for (
const SCEV *
Op : AR->operands())
3501 if (StartC && !DivInt.
urem(StepInt) &&
3507 const APInt &StartRem = StartInt.
urem(StepInt);
3508 if (StartRem != 0) {
3509 const SCEV *NewLHS =
3512 if (LHS != NewLHS) {
3522 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3531 for (
const SCEV *
Op : M->operands())
3535 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3536 const SCEV *
Op = M->getOperand(i);
3548 if (
auto *DivisorConstant =
3550 bool Overflow =
false;
3552 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3563 for (
const SCEV *
Op :
A->operands())
3567 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3574 if (
Operands.size() ==
A->getNumOperands())
3581 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3587 AE && AE->getNumOperands() == 2) {
3589 const APInt &NegC = VC->getAPInt();
3592 if (MME && MME->getNumOperands() == 2 &&
3595 MME->getOperand(1) == RHS)
3596 return getZero(LHS->getType());
3604 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
3607 UniqueSCEVs.InsertNode(S, IP);
3637 if (!
Mul || !
Mul->hasNoUnsignedWrap())
3644 if (LHSCst == RHSCst) {
3652 APInt Factor =
gcd(LHSCst, RHSCst);
3670 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3671 if (
Mul->getOperand(i) == RHS) {
3690 if (StepChrec->getLoop() == L) {
3709 "SCEVAddRecExpr operand types don't match!");
3710 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3714 "SCEVAddRecExpr operand is not available at loop entry!");
3732 const Loop *NestedLoop = NestedAR->getLoop();
3733 if (L->contains(NestedLoop)
3736 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3738 Operands[0] = NestedAR->getStart();
3742 bool AllInvariant =
all_of(
3754 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3765 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3775 return getOrCreateAddRecExpr(
Operands, L, Flags);
3793 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3804 bool FirstIter =
true;
3806 for (
const SCEV *IndexExpr : IndexExprs) {
3813 Offsets.push_back(FieldOffset);
3816 CurTy = STy->getTypeAtIndex(Index);
3821 "The first index of a GEP indexes a pointer");
3822 CurTy =
GEP->getSourceElementType();
3833 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3834 Offsets.push_back(LocalOffset);
3839 if (Offsets.empty())
3852 "GEP should not change type mid-flight.");
3856SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3859 ID.AddInteger(SCEVType);
3863 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3873 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3874 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3875 if (
Ops.size() == 1)
return Ops[0];
3878 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3880 "Operand types don't match!");
3883 "min/max should be consistently pointerish");
3909 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3911 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3916 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3918 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3924 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3930 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3935 if (Idx <
Ops.size()) {
3936 bool DeletedAny =
false;
3937 while (
Ops[Idx]->getSCEVType() == Kind) {
3939 Ops.erase(
Ops.begin()+Idx);
3957 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3958 if (
Ops[i] ==
Ops[i + 1] ||
3959 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3962 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3965 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3968 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3974 if (
Ops.size() == 1)
return Ops[0];
3976 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
3981 ID.AddInteger(Kind);
3985 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3987 return ExistingSCEV;
3988 const SCEV **O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
3990 SCEV *S =
new (SCEVAllocator)
3993 UniqueSCEVs.InsertNode(S, IP);
4000class SCEVSequentialMinMaxDeduplicatingVisitor final
4001 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4002 std::optional<const SCEV *>> {
4003 using RetVal = std::optional<const SCEV *>;
4011 bool canRecurseInto(
SCEVTypes Kind)
const {
4014 return RootKind == Kind || NonSequentialRootKind == Kind;
4017 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
4019 "Only for min/max expressions.");
4022 if (!canRecurseInto(Kind))
4032 return std::nullopt;
4039 RetVal
visit(
const SCEV *S) {
4041 if (!SeenOps.
insert(S).second)
4042 return std::nullopt;
4043 return Base::visit(S);
4047 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4049 : SE(SE), RootKind(RootKind),
4050 NonSequentialRootKind(
4051 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4055 SmallVectorImpl<const SCEV *> &NewOps) {
4060 for (
const SCEV *
Op : OrigOps) {
4065 Ops.emplace_back(*NewOp);
4069 NewOps = std::move(
Ops);
4073 RetVal visitConstant(
const SCEVConstant *Constant) {
return Constant; }
4075 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4077 RetVal visitPtrToIntExpr(
const SCEVPtrToIntExpr *Expr) {
return Expr; }
4079 RetVal visitTruncateExpr(
const SCEVTruncateExpr *Expr) {
return Expr; }
4081 RetVal visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
return Expr; }
4083 RetVal visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
return Expr; }
4085 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4087 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4089 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4091 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4093 RetVal visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
4094 return visitAnyMinMaxExpr(Expr);
4097 RetVal visitUMaxExpr(
const SCEVUMaxExpr *Expr) {
4098 return visitAnyMinMaxExpr(Expr);
4101 RetVal visitSMinExpr(
const SCEVSMinExpr *Expr) {
4102 return visitAnyMinMaxExpr(Expr);
4105 RetVal visitUMinExpr(
const SCEVUMinExpr *Expr) {
4106 return visitAnyMinMaxExpr(Expr);
4109 RetVal visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *Expr) {
4110 return visitAnyMinMaxExpr(Expr);
4113 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4115 RetVal visitCouldNotCompute(
const SCEVCouldNotCompute *Expr) {
return Expr; }
4157struct SCEVPoisonCollector {
4158 bool LookThroughMaybePoisonBlocking;
4159 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4160 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4161 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4163 bool follow(
const SCEV *S) {
4164 if (!LookThroughMaybePoisonBlocking &&
4174 bool isDone()
const {
return false; }
4184 SCEVPoisonCollector PC1(
true);
4189 if (PC1.MaybePoison.empty())
4195 SCEVPoisonCollector PC2(
false);
4205 SCEVPoisonCollector PC(
false);
4228 while (!Worklist.
empty()) {
4230 if (!Visited.
insert(V).second)
4234 if (Visited.
size() > 16)
4239 if (PoisonVals.
contains(V) || ::isGuaranteedNotToBePoison(V))
4250 if (PDI->isDisjoint())
4257 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4264 if (
I->hasPoisonGeneratingAnnotations())
4275 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4276 "Not a SCEVSequentialMinMaxExpr!");
4277 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4278 if (
Ops.size() == 1)
4282 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4284 "Operand types don't match!");
4287 "min/max should be consistently pointerish");
4295 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4302 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4312 bool DeletedAny =
false;
4313 while (Idx <
Ops.size()) {
4314 if (
Ops[Idx]->getSCEVType() != Kind) {
4319 Ops.erase(
Ops.begin() + Idx);
4320 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4321 SMME->operands().end());
4329 const SCEV *SaturationPoint;
4340 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4341 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4353 Ops.erase(
Ops.begin() + i);
4358 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4359 Ops.erase(
Ops.begin() + i);
4367 ID.AddInteger(Kind);
4371 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4373 return ExistingSCEV;
4375 const SCEV **O = SCEVAllocator.Allocate<
const SCEV *>(
Ops.size());
4377 SCEV *S =
new (SCEVAllocator)
4380 UniqueSCEVs.InsertNode(S, IP);
4428 if (
Size.isScalable())
4449 "Cannot get offset for structure containing scalable vector types");
4463 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP)) {
4465 "Stale SCEVUnknown in uniquing map!");
4471 UniqueSCEVs.InsertNode(S, IP);
4485 return Ty->isIntOrPtrTy();
4492 if (Ty->isPointerTy())
4503 if (Ty->isIntegerTy())
4507 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4519 bool PreciseA, PreciseB;
4520 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4521 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4522 if (!PreciseA || !PreciseB)
4525 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4526 DT.dominates(ScopeB, ScopeA);
4530 return CouldNotCompute.get();
4533bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4536 return SU && SU->getValue() ==
nullptr;
4539 return !ContainsNulls;
4544 if (
I != HasRecMap.end())
4549 HasRecMap.insert({S, FoundAddRec});
4557 if (
SI == ExprValueMap.
end())
4559 return SI->second.getArrayRef();
4565void ScalarEvolution::eraseValueFromMap(
Value *V) {
4567 if (
I != ValueExprMap.end()) {
4568 auto EVIt = ExprValueMap.find(
I->second);
4569 bool Removed = EVIt->second.remove(V);
4571 assert(Removed &&
"Value not in ExprValueMap?");
4572 ValueExprMap.erase(
I);
4576void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4580 auto It = ValueExprMap.find_as(V);
4581 if (It == ValueExprMap.end()) {
4583 ExprValueMap[S].insert(V);
4594 return createSCEVIter(V);
4601 if (
I != ValueExprMap.end()) {
4602 const SCEV *S =
I->second;
4603 assert(checkValidity(S) &&
4604 "existing SCEV has not been properly invalidated");
4617 Type *Ty = V->getType();
4625 if (!
Add ||
Add->getNumOperands() != 2 ||
4626 !
Add->getOperand(0)->isAllOnesValue())
4639 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4652 return (
const SCEV *)
nullptr;
4658 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4662 Type *Ty = V->getType();
4668 assert(
P->getType()->isPointerTy());
4681 const SCEV **PtrOp =
nullptr;
4682 for (
const SCEV *&AddOp :
Ops) {
4683 if (AddOp->getType()->isPointerTy()) {
4684 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4702 return getZero(LHS->getType());
4707 if (RHS->getType()->isPointerTy()) {
4708 if (!LHS->getType()->isPointerTy() ||
4718 const bool RHSIsNotMinSigned =
4749 Type *SrcTy = V->getType();
4750 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4751 "Cannot truncate or zero extend with non-integer arguments!");
4761 Type *SrcTy = V->getType();
4762 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4763 "Cannot truncate or zero extend with non-integer arguments!");
4773 Type *SrcTy = V->getType();
4774 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4775 "Cannot noop or zero extend with non-integer arguments!");
4777 "getNoopOrZeroExtend cannot truncate!");
4785 Type *SrcTy = V->getType();
4786 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4787 "Cannot noop or sign extend with non-integer arguments!");
4789 "getNoopOrSignExtend cannot truncate!");
4797 Type *SrcTy = V->getType();
4798 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4799 "Cannot noop or any extend with non-integer arguments!");
4801 "getNoopOrAnyExtend cannot truncate!");
4809 Type *SrcTy = V->getType();
4810 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4811 "Cannot truncate or noop with non-integer arguments!");
4813 "getTruncateOrNoop cannot extend!");
4821 const SCEV *PromotedLHS = LHS;
4822 const SCEV *PromotedRHS = RHS;
4842 assert(!
Ops.empty() &&
"At least one operand must be!");
4844 if (
Ops.size() == 1)
4848 Type *MaxType =
nullptr;
4849 for (
const auto *S :
Ops)
4854 assert(MaxType &&
"Failed to find maximum type!");
4858 for (
const auto *S :
Ops)
4867 if (!V->getType()->isPointerTy())
4872 V = AddRec->getStart();
4874 const SCEV *PtrOp =
nullptr;
4875 for (
const SCEV *AddOp :
Add->operands()) {
4876 if (AddOp->getType()->isPointerTy()) {
4877 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4881 assert(PtrOp &&
"Must have pointer op");
4893 for (
User *U :
I->users()) {
4895 if (Visited.
insert(UserInsn).second)
4909 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4910 bool IgnoreOtherLoops =
true) {
4913 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4915 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4920 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4922 SeenLoopVariantSCEVUnknown =
true;
4926 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4930 SeenOtherLoops =
true;
4934 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4936 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4939 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4940 : SCEVRewriteVisitor(SE),
L(
L) {}
4943 bool SeenLoopVariantSCEVUnknown =
false;
4944 bool SeenOtherLoops =
false;
4953 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4954 SCEVPostIncRewriter
Rewriter(L, SE);
4956 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4961 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4963 SeenLoopVariantSCEVUnknown =
true;
4967 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4971 SeenOtherLoops =
true;
4975 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4977 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4980 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4981 : SCEVRewriteVisitor(SE),
L(
L) {}
4984 bool SeenLoopVariantSCEVUnknown =
false;
4985 bool SeenOtherLoops =
false;
4991class SCEVBackedgeConditionFolder
4994 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4995 ScalarEvolution &SE) {
4996 bool IsPosBECond =
false;
4997 Value *BECond =
nullptr;
4998 if (BasicBlock *Latch =
L->getLoopLatch()) {
5002 "Both outgoing branches should not target same header!");
5009 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
5013 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5014 const SCEV *
Result = Expr;
5019 switch (
I->getOpcode()) {
5020 case Instruction::Select: {
5022 std::optional<const SCEV *> Res =
5023 compareWithBackedgeCondition(
SI->getCondition());
5031 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5042 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5043 bool IsPosBECond, ScalarEvolution &SE)
5044 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5045 IsPositiveBECond(IsPosBECond) {}
5047 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5051 Value *BackedgeCond =
nullptr;
5053 bool IsPositiveBECond;
5056std::optional<const SCEV *>
5057SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5062 if (BackedgeCond == IC)
5065 return std::nullopt;
5070 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5071 ScalarEvolution &SE) {
5077 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5084 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5091 bool isValid() {
return Valid; }
5094 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5095 : SCEVRewriteVisitor(SE),
L(
L) {}
5104ScalarEvolution::proveNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5108 using OBO = OverflowingBinaryOperator;
5116 const APInt &BECountAP = BECountMax->getAPInt();
5117 unsigned NoOverflowBitWidth =
5129 Instruction::Add, IncRange, OBO::NoSignedWrap);
5130 if (NSWRegion.contains(AddRecRange))
5139 Instruction::Add, IncRange, OBO::NoUnsignedWrap);
5140 if (NUWRegion.contains(AddRecRange))
5148ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5158 if (!SignedWrapViaInductionTried.insert(AR).second)
5183 AC.assumptions().empty())
5191 const SCEV *OverflowLimit =
5193 if (OverflowLimit &&
5201ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5211 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5237 AC.assumptions().empty())
5272 explicit BinaryOp(Operator *
Op)
5276 IsNSW = OBO->hasNoSignedWrap();
5277 IsNUW = OBO->hasNoUnsignedWrap();
5281 explicit BinaryOp(
unsigned Opcode,
Value *
LHS,
Value *
RHS,
bool IsNSW =
false,
5283 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5295 return std::nullopt;
5301 switch (
Op->getOpcode()) {
5302 case Instruction::Add:
5303 case Instruction::Sub:
5304 case Instruction::Mul:
5305 case Instruction::UDiv:
5306 case Instruction::URem:
5307 case Instruction::And:
5308 case Instruction::AShr:
5309 case Instruction::Shl:
5310 return BinaryOp(
Op);
5312 case Instruction::Or: {
5315 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5317 return BinaryOp(
Op);
5320 case Instruction::Xor:
5324 if (RHSC->getValue().isSignMask())
5325 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5327 if (V->getType()->isIntegerTy(1))
5328 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5329 return BinaryOp(
Op);
5331 case Instruction::LShr:
5340 if (SA->getValue().ult(
BitWidth)) {
5342 ConstantInt::get(SA->getContext(),
5344 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5347 return BinaryOp(
Op);
5349 case Instruction::ExtractValue: {
5351 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5359 bool Signed = WO->isSigned();
5362 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5367 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5378 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5379 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5381 return std::nullopt;
5407 if (
Op == SymbolicPHI)
5412 if (SourceBits != NewBits)
5425 if (
X != SymbolicPHI)
5427 Signed = SExt !=
nullptr;
5435 if (!L || L->getHeader() != PN->
getParent())
5493std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5494ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5502 assert(L &&
"Expecting an integer loop header phi");
5507 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5508 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5509 Value *
V = PN->getIncomingValue(i);
5510 if (
L->contains(PN->getIncomingBlock(i))) {
5513 }
else if (BEValueV != V) {
5517 }
else if (!StartValueV) {
5519 }
else if (StartValueV != V) {
5520 StartValueV =
nullptr;
5524 if (!BEValueV || !StartValueV)
5525 return std::nullopt;
5527 const SCEV *BEValue =
getSCEV(BEValueV);
5534 return std::nullopt;
5538 unsigned FoundIndex =
Add->getNumOperands();
5539 Type *TruncTy =
nullptr;
5541 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5544 if (FoundIndex == e) {
5549 if (FoundIndex ==
Add->getNumOperands())
5550 return std::nullopt;
5554 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5555 if (i != FoundIndex)
5556 Ops.push_back(
Add->getOperand(i));
5562 return std::nullopt;
5615 const SCEV *StartVal =
getSCEV(StartValueV);
5616 const SCEV *PHISCEV =
5643 auto getExtendedExpr = [&](
const SCEV *Expr,
5644 bool CreateSignExtend) ->
const SCEV * {
5647 const SCEV *ExtendedExpr =
5650 return ExtendedExpr;
5658 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5659 const SCEV *ExtendedExpr) ->
bool {
5660 return Expr != ExtendedExpr &&
5664 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5665 if (PredIsKnownFalse(StartVal, StartExtended)) {
5667 return std::nullopt;
5672 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5673 if (PredIsKnownFalse(Accum, AccumExtended)) {
5675 return std::nullopt;
5678 auto AppendPredicate = [&](
const SCEV *Expr,
5679 const SCEV *ExtendedExpr) ->
void {
5680 if (Expr != ExtendedExpr &&
5688 AppendPredicate(StartVal, StartExtended);
5689 AppendPredicate(Accum, AccumExtended);
5697 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5698 std::make_pair(NewAR, Predicates);
5700 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5704std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5709 return std::nullopt;
5712 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5713 if (
I != PredicatedSCEVRewrites.end()) {
5714 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5717 if (Rewrite.first == SymbolicPHI)
5718 return std::nullopt;
5722 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5726 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5727 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5732 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5733 return std::nullopt;
5750 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5751 if (Expr1 != Expr2 &&
5752 !Preds->implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5753 !Preds->implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5770const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5772 Value *StartValueV) {
5775 assert(BEValueV && StartValueV);
5781 if (BO->Opcode != Instruction::Add)
5784 const SCEV *Accum =
nullptr;
5785 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5787 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5801 insertValueToMap(PN, PHISCEV);
5806 proveNoWrapViaConstantRanges(AR)));
5814 "Accum is defined outside L, but is not invariant?");
5815 if (isAddRecNeverPoison(BEInst, L))
5822const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5823 const Loop *
L = LI.getLoopFor(PN->
getParent());
5830 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5836 }
else if (BEValueV != V) {
5840 }
else if (!StartValueV) {
5842 }
else if (StartValueV != V) {
5843 StartValueV =
nullptr;
5847 if (!BEValueV || !StartValueV)
5850 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5851 "PHI node already processed?");
5855 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5860 insertValueToMap(PN, SymbolicName);
5864 const SCEV *BEValue =
getSCEV(BEValueV);
5874 unsigned FoundIndex =
Add->getNumOperands();
5875 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5876 if (
Add->getOperand(i) == SymbolicName)
5877 if (FoundIndex == e) {
5882 if (FoundIndex !=
Add->getNumOperands()) {
5885 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5886 if (i != FoundIndex)
5887 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5899 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5906 if (
GEP->getOperand(0) == PN) {
5907 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
5925 const SCEV *StartVal =
getSCEV(StartValueV);
5926 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5931 forgetMemoizedResults(SymbolicName);
5932 insertValueToMap(PN, PHISCEV);
5937 proveNoWrapViaConstantRanges(AR)));
5962 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5963 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5965 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5966 const SCEV *StartVal =
getSCEV(StartValueV);
5967 if (Start == StartVal) {
5971 forgetMemoizedResults(SymbolicName);
5972 insertValueToMap(PN, Shifted);
5982 eraseValueFromMap(PN);
6002 Use &LeftUse =
Merge->getOperandUse(0);
6003 Use &RightUse =
Merge->getOperandUse(1);
6020const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
6022 [&](
BasicBlock *BB) {
return DT.isReachableFromEntry(BB); };
6037 assert(IDom &&
"At least the entry block should dominate PN");
6046 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6062ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6063 BinaryOperator *CommonInst =
nullptr;
6074 CommonInst = IncomingInst;
6081 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6082 bool SCEVExprsIdentical =
6084 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6085 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6088const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6089 if (
const SCEV *S = createAddRecFromPHI(PN))
6099 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6102 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6111 struct FindClosure {
6112 const SCEV *OperandToFind;
6118 bool canRecurseInto(
SCEVTypes Kind)
const {
6121 return RootKind == Kind || NonSequentialRootKind == Kind ||
6126 : OperandToFind(OperandToFind), RootKind(RootKind),
6127 NonSequentialRootKind(
6131 bool follow(
const SCEV *S) {
6132 Found = S == OperandToFind;
6134 return !isDone() && canRecurseInto(S->
getSCEVType());
6137 bool isDone()
const {
return Found; }
6140 FindClosure FC(OperandToFind, RootKind);
6145std::optional<const SCEV *>
6146ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6156 switch (ICI->getPredicate()) {
6170 bool Signed = ICI->isSigned();
6171 const SCEV *LA =
getSCEV(TrueVal);
6179 if (LA == LS &&
RA == RS)
6181 if (LA == RS &&
RA == LS)
6184 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6185 if (
Op->getType()->isPointerTy()) {
6196 LS = CoerceOperand(LS);
6197 RS = CoerceOperand(RS);
6221 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6222 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6236 X = ZExt->getOperand();
6238 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6249 return std::nullopt;
6252static std::optional<const SCEV *>
6254 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6258 "Unexpected operands of a select.");
6270 return std::nullopt;
6285static std::optional<const SCEV *>
6289 return std::nullopt;
6292 const auto *SETrue = SE->
getSCEV(TrueVal);
6293 const auto *SEFalse = SE->
getSCEV(FalseVal);
6297const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6299 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6301 V->getType() ==
TrueVal->getType() &&
6302 "Types of select hands and of the result must match.");
6305 if (!
V->getType()->isIntegerTy(1))
6308 if (std::optional<const SCEV *> S =
6321 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6325 if (std::optional<const SCEV *> S =
6326 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6332 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6338 assert(
GEP->getSourceElementType()->isSized() &&
6339 "GEP source element type must be sized");
6342 for (
Value *Index :
GEP->indices())
6347APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S) {
6349 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6352 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6354 auto GetGCDMultiple = [
this](
const SCEVNAryExpr *
N) {
6357 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6375 return GetShiftedByZeros(TZ);
6385 return GetShiftedByZeros(TZ);
6389 if (
M->hasNoUnsignedWrap()) {
6392 for (
const SCEV *Operand :
M->operands().drop_front())
6400 for (
const SCEV *Operand :
M->operands())
6402 return GetShiftedByZeros(TZ);
6407 if (
N->hasNoUnsignedWrap())
6408 return GetGCDMultiple(
N);
6411 for (
const SCEV *Operand :
N->operands().drop_front())
6413 return GetShiftedByZeros(TZ);
6426 .countMinTrailingZeros();
6427 return GetShiftedByZeros(Known);
6436 auto I = ConstantMultipleCache.find(S);
6437 if (
I != ConstantMultipleCache.end())
6440 APInt Result = getConstantMultipleImpl(S);
6441 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6442 assert(InsertPair.second &&
"Should insert a new key");
6443 return InsertPair.first->second;
6459 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6462 if (std::optional<ConstantRange>
Range = CB->getRange())
6466 if (std::optional<ConstantRange>
Range =
A->getRange())
6469 return std::nullopt;
6476 UnsignedRanges.erase(AddRec);
6477 SignedRanges.erase(AddRec);
6478 ConstantMultipleCache.erase(AddRec);
6483getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6509 Value *Start, *Step;
6516 assert(L && L->getHeader() ==
P->getParent());
6529 case Instruction::AShr:
6530 case Instruction::LShr:
6531 case Instruction::Shl:
6546 KnownStep.getBitWidth() ==
BitWidth);
6549 auto MaxShiftAmt = KnownStep.getMaxValue();
6551 bool Overflow =
false;
6552 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6559 case Instruction::AShr: {
6567 if (KnownStart.isNonNegative())
6570 KnownStart.getMaxValue() + 1);
6571 if (KnownStart.isNegative())
6574 KnownEnd.getMaxValue() + 1);
6577 case Instruction::LShr: {
6586 KnownStart.getMaxValue() + 1);
6588 case Instruction::Shl: {
6592 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6593 return ConstantRange(KnownStart.getMinValue(),
6594 KnownEnd.getMaxValue() + 1);
6602ScalarEvolution::getRangeRefIter(
const SCEV *S,
6603 ScalarEvolution::RangeSignHint SignHint) {
6604 DenseMap<const SCEV *, ConstantRange> &Cache =
6605 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6608 SmallPtrSet<const SCEV *, 8> Seen;
6612 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6613 if (!Seen.
insert(Expr).second)
6646 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6647 const SCEV *
P = WorkList[
I];
6651 for (
const SCEV *
Op :
P->operands())
6657 if (!PendingPhiRangesIter.insert(
P).second)
6664 if (!WorkList.
empty()) {
6669 getRangeRef(
P, SignHint);
6673 PendingPhiRangesIter.erase(
P);
6677 return getRangeRef(S, SignHint, 0);
6684 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6685 DenseMap<const SCEV *, ConstantRange> &Cache =
6686 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6694 if (
I != Cache.
end())
6698 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6703 return getRangeRefIter(S, SignHint);
6706 ConstantRange ConservativeResult(
BitWidth,
true);
6707 using OBO = OverflowingBinaryOperator;
6711 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6715 ConservativeResult =
6722 ConservativeResult = ConstantRange(
6738 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6745 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6752 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6756 ConstantRange
X = getRangeRef(PtrToInt->
getOperand(), SignHint,
Depth + 1);
6757 return setRange(PtrToInt, SignHint,
X);
6761 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6762 unsigned WrapType = OBO::AnyWrap;
6763 if (
Add->hasNoSignedWrap())
6764 WrapType |= OBO::NoSignedWrap;
6765 if (
Add->hasNoUnsignedWrap())
6766 WrapType |= OBO::NoUnsignedWrap;
6768 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6770 return setRange(
Add, SignHint,
6771 ConservativeResult.intersectWith(
X, RangeType));
6775 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6777 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6778 return setRange(
Mul, SignHint,
6779 ConservativeResult.intersectWith(
X, RangeType));
6783 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6784 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6785 return setRange(UDiv, SignHint,
6786 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6794 if (!UnsignedMinValue.
isZero())
6795 ConservativeResult = ConservativeResult.intersectWith(
6796 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6805 bool AllNonNeg =
true;
6806 bool AllNonPos =
true;
6807 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6814 ConservativeResult = ConservativeResult.intersectWith(
6819 ConservativeResult = ConservativeResult.intersectWith(
6828 const SCEV *MaxBEScev =
6842 auto RangeFromAffine = getRangeForAffineAR(
6844 ConservativeResult =
6845 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6847 auto RangeFromFactoring = getRangeViaFactoring(
6849 ConservativeResult =
6850 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6856 const SCEV *SymbolicMaxBECount =
6861 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6862 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6863 ConservativeResult =
6864 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6869 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6879 ID = Intrinsic::umax;
6882 ID = Intrinsic::smax;
6886 ID = Intrinsic::umin;
6889 ID = Intrinsic::smin;
6896 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6897 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6899 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6900 return setRange(S, SignHint,
6901 ConservativeResult.intersectWith(
X, RangeType));
6910 ConservativeResult =
6911 ConservativeResult.intersectWith(*MDRange, RangeType);
6916 auto CR = getRangeForUnknownRecurrence(U);
6917 ConservativeResult = ConservativeResult.intersectWith(CR);
6928 if (
U->getType()->isPointerTy()) {
6931 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
6932 int ptrIdxDiff = ptrSize -
BitWidth;
6933 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
6946 ConservativeResult = ConservativeResult.intersectWith(
6950 ConservativeResult = ConservativeResult.intersectWith(
6955 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6958 bool CanBeNull, CanBeFreed;
6959 uint64_t DerefBytes =
6960 V->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed);
6970 uint64_t
Align =
U->getValue()->getPointerAlignment(DL).value();
6971 uint64_t Rem = MaxVal.
urem(Align);
6976 ConservativeResult = ConservativeResult.intersectWith(
6984 if (PendingPhiRanges.insert(Phi).second) {
6985 ConstantRange RangeFromOps(
BitWidth,
false);
6987 for (
const auto &
Op :
Phi->operands()) {
6989 RangeFromOps = RangeFromOps.unionWith(OpRange);
6991 if (RangeFromOps.isFullSet())
6994 ConservativeResult =
6995 ConservativeResult.intersectWith(RangeFromOps, RangeType);
6996 bool Erased = PendingPhiRanges.erase(Phi);
6997 assert(Erased &&
"Failed to erase Phi properly?");
7004 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7006 ConservativeResult = ConservativeResult.difference(Disallowed);
7009 return setRange(U, SignHint, std::move(ConservativeResult));
7015 return setRange(S, SignHint, std::move(ConservativeResult));
7024 const APInt &MaxBECount,
7031 if (Step == 0 || MaxBECount == 0)
7038 return ConstantRange::getFull(
BitWidth);
7054 return ConstantRange::getFull(
BitWidth);
7066 APInt MovedBoundary = Descending ? (StartLower - std::move(
Offset))
7067 : (StartUpper + std::move(
Offset));
7072 if (StartRange.
contains(MovedBoundary))
7073 return ConstantRange::getFull(
BitWidth);
7076 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7078 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7087 const APInt &MaxBECount) {
7091 "mismatched bit widths");
7100 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7102 StartSRange, MaxBECount,
7114ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7116 ScalarEvolution::RangeSignHint SignHint) {
7117 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7119 "This only works for non-self-wrapping AddRecs!");
7120 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7124 return ConstantRange::getFull(
BitWidth);
7132 return ConstantRange::getFull(
BitWidth);
7136 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7138 MaxItersWithoutWrap))
7139 return ConstantRange::getFull(
BitWidth);
7160 ConstantRange StartRange = getRangeRef(Start, SignHint);
7161 ConstantRange EndRange = getRangeRef(End, SignHint);
7162 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7166 return RangeBetween;
7171 return ConstantRange::getFull(
BitWidth);
7174 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7175 return RangeBetween;
7177 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7178 return RangeBetween;
7179 return ConstantRange::getFull(
BitWidth);
7184 const APInt &MaxBECount) {
7191 "mismatched bit widths");
7193 struct SelectPattern {
7194 Value *Condition =
nullptr;
7198 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7200 std::optional<unsigned> CastOp;
7214 CastOp = SCast->getSCEVType();
7215 S = SCast->getOperand();
7218 using namespace llvm::PatternMatch;
7225 Condition =
nullptr;
7257 bool isRecognized() {
return Condition !=
nullptr; }
7260 SelectPattern StartPattern(*
this,
BitWidth, Start);
7261 if (!StartPattern.isRecognized())
7262 return ConstantRange::getFull(
BitWidth);
7264 SelectPattern StepPattern(*
this,
BitWidth, Step);
7265 if (!StepPattern.isRecognized())
7266 return ConstantRange::getFull(
BitWidth);
7268 if (StartPattern.Condition != StepPattern.Condition) {
7272 return ConstantRange::getFull(
BitWidth);
7283 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7284 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7285 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7286 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7288 ConstantRange TrueRange =
7289 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount);
7290 ConstantRange FalseRange =
7291 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount);
7313ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7327 SmallPtrSet<const SCEV *, 16> Visited;
7329 auto pushOp = [&](
const SCEV *S) {
7330 if (!Visited.
insert(S).second)
7333 if (Visited.
size() > 30) {
7340 for (
const auto *S :
Ops)
7344 while (!Worklist.
empty()) {
7346 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7347 if (!Bound || DT.dominates(Bound, DefI))
7354 return Bound ? Bound : &*F.getEntryBlock().begin();
7360 return getDefiningScopeBound(
Ops, Discard);
7363bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7365 if (
A->getParent() ==
B->getParent() &&
7370 auto *BLoop = LI.getLoopFor(
B->getParent());
7371 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7372 BLoop->getLoopPreheader() ==
A->getParent() &&
7374 A->getParent()->end()) &&
7381bool ScalarEvolution::isGuaranteedNotToBePoison(
const SCEV *
Op) {
7382 SCEVPoisonCollector PC(
true);
7384 return PC.MaybePoison.empty();
7387bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7393 return M && (!
isKnownNonZero(Op1) || !isGuaranteedNotToBePoison(Op1));
7397bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7414 for (
const Use &
Op :
I->operands()) {
7420 auto *DefI = getDefiningScopeBound(SCEVOps);
7421 return isGuaranteedToTransferExecutionTo(DefI,
I);
7424bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7426 if (isSCEVExprNeverPoison(
I))
7437 auto *ExitingBB =
L->getExitingBlock();
7441 SmallPtrSet<const Value *, 16> KnownPoison;
7450 while (!Worklist.
empty()) {
7453 for (
const Use &U :
Poison->uses()) {
7456 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7460 if (KnownPoison.
insert(PoisonUser).second)
7468ScalarEvolution::LoopProperties
7469ScalarEvolution::getLoopProperties(
const Loop *L) {
7470 using LoopProperties = ScalarEvolution::LoopProperties;
7472 auto Itr = LoopPropertiesCache.find(L);
7473 if (Itr == LoopPropertiesCache.end()) {
7476 return !
SI->isSimple();
7486 return I->mayWriteToMemory();
7489 LoopProperties LP = {
true,
7492 for (
auto *BB :
L->getBlocks())
7493 for (
auto &
I : *BB) {
7495 LP.HasNoAbnormalExits =
false;
7496 if (HasSideEffects(&
I))
7497 LP.HasNoSideEffects =
false;
7498 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7502 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7503 assert(InsertPair.second &&
"We just checked!");
7504 Itr = InsertPair.first;
7517const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7523 Stack.emplace_back(V,
true);
7524 Stack.emplace_back(V,
false);
7525 while (!Stack.empty()) {
7526 auto E = Stack.pop_back_val();
7527 Value *CurV = E.getPointer();
7533 const SCEV *CreatedSCEV =
nullptr;
7536 CreatedSCEV = createSCEV(CurV);
7541 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7545 insertValueToMap(CurV, CreatedSCEV);
7549 Stack.emplace_back(CurV,
true);
7551 Stack.emplace_back(
Op,
false);
7568 if (!DT.isReachableFromEntry(
I->getParent()))
7581 switch (BO->Opcode) {
7582 case Instruction::Add:
7583 case Instruction::Mul: {
7590 Ops.push_back(BO->
Op);
7594 Ops.push_back(BO->RHS);
7598 (BO->Opcode == Instruction::Add &&
7599 (NewBO->Opcode != Instruction::Add &&
7600 NewBO->Opcode != Instruction::Sub)) ||
7601 (BO->Opcode == Instruction::Mul &&
7602 NewBO->Opcode != Instruction::Mul)) {
7603 Ops.push_back(BO->LHS);
7608 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7611 Ops.push_back(BO->LHS);
7619 case Instruction::Sub:
7620 case Instruction::UDiv:
7621 case Instruction::URem:
7623 case Instruction::AShr:
7624 case Instruction::Shl:
7625 case Instruction::Xor:
7629 case Instruction::And:
7630 case Instruction::Or:
7634 case Instruction::LShr:
7641 Ops.push_back(BO->LHS);
7642 Ops.push_back(BO->RHS);
7646 switch (
U->getOpcode()) {
7647 case Instruction::Trunc:
7648 case Instruction::ZExt:
7649 case Instruction::SExt:
7650 case Instruction::PtrToInt:
7651 Ops.push_back(
U->getOperand(0));
7654 case Instruction::BitCast:
7656 Ops.push_back(
U->getOperand(0));
7661 case Instruction::SDiv:
7662 case Instruction::SRem:
7663 Ops.push_back(
U->getOperand(0));
7664 Ops.push_back(
U->getOperand(1));
7667 case Instruction::GetElementPtr:
7669 "GEP source element type must be sized");
7673 case Instruction::IntToPtr:
7676 case Instruction::PHI:
7680 case Instruction::Select: {
7682 auto CanSimplifyToUnknown = [
this,
U]() {
7700 if (CanSimplifyToUnknown())
7707 case Instruction::Call:
7708 case Instruction::Invoke:
7715 switch (
II->getIntrinsicID()) {
7716 case Intrinsic::abs:
7717 Ops.push_back(
II->getArgOperand(0));
7719 case Intrinsic::umax:
7720 case Intrinsic::umin:
7721 case Intrinsic::smax:
7722 case Intrinsic::smin:
7723 case Intrinsic::usub_sat:
7724 case Intrinsic::uadd_sat:
7725 Ops.push_back(
II->getArgOperand(0));
7726 Ops.push_back(
II->getArgOperand(1));
7728 case Intrinsic::start_loop_iterations:
7729 case Intrinsic::annotation:
7730 case Intrinsic::ptr_annotation:
7731 Ops.push_back(
II->getArgOperand(0));
7743const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7752 if (!DT.isReachableFromEntry(
I->getParent()))
7767 switch (BO->Opcode) {
7768 case Instruction::Add: {
7794 if (BO->Opcode == Instruction::Sub)
7802 if (BO->Opcode == Instruction::Sub)
7809 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7810 NewBO->Opcode != Instruction::Sub)) {
7820 case Instruction::Mul: {
7841 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7850 case Instruction::UDiv:
7854 case Instruction::URem:
7858 case Instruction::Sub: {
7861 Flags = getNoWrapFlagsFromUB(BO->
Op);
7866 case Instruction::And:
7872 if (CI->isMinusOne())
7874 const APInt &
A = CI->getValue();
7880 unsigned LZ =
A.countl_zero();
7881 unsigned TZ =
A.countr_zero();
7886 APInt EffectiveMask =
7888 if ((LZ != 0 || TZ != 0) && !((~
A & ~Known.
Zero) & EffectiveMask)) {
7891 const SCEV *ShiftedLHS =
nullptr;
7895 unsigned MulZeros = OpC->getAPInt().countr_zero();
7896 unsigned GCD = std::min(MulZeros, TZ);
7901 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
7923 case Instruction::Or:
7932 case Instruction::Xor:
7935 if (CI->isMinusOne())
7944 if (LBO->getOpcode() == Instruction::And &&
7945 LCI->getValue() == CI->getValue())
7946 if (
const SCEVZeroExtendExpr *Z =
7949 const SCEV *Z0 =
Z->getOperand();
7956 if (CI->getValue().isMask(Z0TySize))
7962 APInt Trunc = CI->getValue().trunc(Z0TySize);
7971 case Instruction::Shl:
7989 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
7997 ConstantInt *
X = ConstantInt::get(
8003 case Instruction::AShr:
8025 const SCEV *AddTruncateExpr =
nullptr;
8026 ConstantInt *ShlAmtCI =
nullptr;
8027 const SCEV *AddConstant =
nullptr;
8029 if (L &&
L->getOpcode() == Instruction::Add) {
8037 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8044 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8052 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8057 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8062 if (AddTruncateExpr && ShlAmtCI) {
8074 const APInt &ShlAmt = ShlAmtCI->
getValue();
8078 const SCEV *CompositeExpr =
8080 if (
L->getOpcode() != Instruction::Shl)
8081 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8090 switch (
U->getOpcode()) {
8091 case Instruction::Trunc:
8094 case Instruction::ZExt:
8097 case Instruction::SExt:
8107 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8108 Type *Ty =
U->getType();
8116 case Instruction::BitCast:
8122 case Instruction::PtrToInt: {
8125 Type *DstIntTy =
U->getType();
8133 case Instruction::IntToPtr:
8137 case Instruction::SDiv:
8144 case Instruction::SRem:
8151 case Instruction::GetElementPtr:
8154 case Instruction::PHI:
8157 case Instruction::Select:
8158 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8161 case Instruction::Call:
8162 case Instruction::Invoke:
8167 switch (
II->getIntrinsicID()) {
8168 case Intrinsic::abs:
8172 case Intrinsic::umax:
8176 case Intrinsic::umin:
8180 case Intrinsic::smax:
8184 case Intrinsic::smin:
8188 case Intrinsic::usub_sat: {
8189 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8190 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8194 case Intrinsic::uadd_sat: {
8195 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8196 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8200 case Intrinsic::start_loop_iterations:
8201 case Intrinsic::annotation:
8202 case Intrinsic::ptr_annotation:
8206 case Intrinsic::vscale:
8226 auto *ExitCountType = ExitCount->
getType();
8227 assert(ExitCountType->isIntegerTy());
8229 1 + ExitCountType->getScalarSizeInBits());
8242 auto CanAddOneWithoutOverflow = [&]() {
8244 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8255 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8285 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8286 assert(L->isLoopExiting(ExitingBlock) &&
8287 "Exiting block must actually branch out of the loop!");
8296 const auto *MaxExitCount =
8304 L->getExitingBlocks(ExitingBlocks);
8306 std::optional<unsigned> Res;
8307 for (
auto *ExitingBB : ExitingBlocks) {
8311 Res = std::gcd(*Res, Multiple);
8313 return Res.value_or(1);
8317 const SCEV *ExitCount) {
8347 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8348 assert(L->isLoopExiting(ExitingBlock) &&
8349 "Exiting block must actually branch out of the loop!");
8359 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8361 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8363 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8373 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8376 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8379 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8387 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8394 return getBackedgeTakenInfo(L).getExact(L,
this);
8396 return getBackedgeTakenInfo(L).getConstantMax(
this);
8398 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8405 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8410 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8414 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8424 for (
PHINode &PN : Header->phis())
8425 if (Visited.
insert(&PN).second)
8429ScalarEvolution::BackedgeTakenInfo &
8430ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8431 auto &BTI = getBackedgeTakenInfo(L);
8432 if (BTI.hasFullInfo())
8435 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8438 return Pair.first->second;
8440 BackedgeTakenInfo
Result =
8441 computeBackedgeTakenCount(L,
true);
8443 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8446ScalarEvolution::BackedgeTakenInfo &
8447ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8453 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8454 BackedgeTakenCounts.try_emplace(L);
8456 return Pair.first->second;
8461 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8468 if (
Result.hasAnyInfo()) {
8471 auto LoopUsersIt = LoopUsers.find(L);
8472 if (LoopUsersIt != LoopUsers.end())
8474 forgetMemoizedResults(ToForget);
8477 for (PHINode &PN :
L->getHeader()->phis())
8478 ConstantEvolutionLoopExitValue.erase(&PN);
8486 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8495 BackedgeTakenCounts.clear();
8496 PredicatedBackedgeTakenCounts.clear();
8497 BECountUsers.clear();
8498 LoopPropertiesCache.clear();
8499 ConstantEvolutionLoopExitValue.clear();
8500 ValueExprMap.clear();
8501 ValuesAtScopes.clear();
8502 ValuesAtScopesUsers.clear();
8503 LoopDispositions.clear();
8504 BlockDispositions.clear();
8505 UnsignedRanges.clear();
8506 SignedRanges.clear();
8507 ExprValueMap.clear();
8509 ConstantMultipleCache.clear();
8510 PredicatedSCEVRewrites.clear();
8512 FoldCacheUser.clear();
8514void ScalarEvolution::visitAndClearUsers(
8518 while (!Worklist.
empty()) {
8525 if (It != ValueExprMap.
end()) {
8526 eraseValueFromMap(It->first);
8529 ConstantEvolutionLoopExitValue.erase(PN);
8543 while (!LoopWorklist.
empty()) {
8547 forgetBackedgeTakenCounts(CurrL,
false);
8548 forgetBackedgeTakenCounts(CurrL,
true);
8551 for (
auto I = PredicatedSCEVRewrites.begin();
8552 I != PredicatedSCEVRewrites.end();) {
8553 std::pair<const SCEV *, const Loop *> Entry =
I->first;
8554 if (Entry.second == CurrL)
8555 PredicatedSCEVRewrites.erase(
I++);
8560 auto LoopUsersItr = LoopUsers.find(CurrL);
8561 if (LoopUsersItr != LoopUsers.end())
8566 visitAndClearUsers(Worklist, Visited, ToForget);
8568 LoopPropertiesCache.erase(CurrL);
8571 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8573 forgetMemoizedResults(ToForget);
8590 visitAndClearUsers(Worklist, Visited, ToForget);
8592 forgetMemoizedResults(ToForget);
8604 struct InvalidationRootCollector {
8608 InvalidationRootCollector(
Loop *L) : L(L) {}
8610 bool follow(
const SCEV *S) {
8616 if (L->contains(AddRec->
getLoop()))
8621 bool isDone()
const {
return false; }
8624 InvalidationRootCollector
C(L);
8626 forgetMemoizedResults(
C.Roots);
8639 BlockDispositions.clear();
8640 LoopDispositions.clear();
8657 while (!Worklist.
empty()) {
8659 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8660 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8661 if (!LoopDispoRemoved && !BlockDispoRemoved)
8663 auto Users = SCEVUsers.find(Curr);
8664 if (
Users != SCEVUsers.end())
8677const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8681 if (!isComplete() || ExitNotTaken.
empty())
8692 for (
const auto &ENT : ExitNotTaken) {
8693 const SCEV *BECount = ENT.ExactNotTaken;
8696 "We should only have known counts for exiting blocks that dominate "
8699 Ops.push_back(BECount);
8704 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8705 "Predicate should be always true!");
8714const ScalarEvolution::ExitNotTakenInfo *
8715ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8716 const BasicBlock *ExitingBlock,
8717 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8718 for (
const auto &ENT : ExitNotTaken)
8719 if (ENT.ExitingBlock == ExitingBlock) {
8720 if (ENT.hasAlwaysTruePredicate())
8722 else if (Predicates) {
8732const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8734 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8735 if (!getConstantMax())
8738 for (
const auto &ENT : ExitNotTaken)
8739 if (!ENT.hasAlwaysTruePredicate()) {
8747 "No point in having a non-constant max backedge taken count!");
8748 return getConstantMax();
8751const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8753 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8761 for (
const auto &ENT : ExitNotTaken) {
8762 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8765 "We should only have known counts for exiting blocks that "
8771 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8772 "Predicate should be always true!");
8775 if (ExitCounts.
empty())
8784bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8786 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8787 return !ENT.hasAlwaysTruePredicate();
8789 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8805 this->ExactNotTaken = E = ConstantMaxNotTaken;
8806 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8811 "Exact is not allowed to be less precise than Constant Max");
8814 "Exact is not allowed to be less precise than Symbolic Max");
8817 "Symbolic Max is not allowed to be less precise than Constant Max");
8820 "No point in having a non-constant max backedge taken count!");
8822 for (
const auto PredList : PredLists)
8823 for (
const auto *
P : PredList) {
8831 "Backedge count should be int");
8834 "Max backedge count should be int");
8847ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8849 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8850 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8851 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8853 ExitNotTaken.reserve(ExitCounts.
size());
8854 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8855 std::back_inserter(ExitNotTaken),
8856 [&](
const EdgeExitInfo &EEI) {
8857 BasicBlock *ExitBB = EEI.first;
8858 const ExitLimit &EL = EEI.second;
8859 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
8860 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
8865 "No point in having a non-constant max backedge taken count!");
8869ScalarEvolution::BackedgeTakenInfo
8870ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
8871 bool AllowPredicates) {
8873 L->getExitingBlocks(ExitingBlocks);
8875 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8878 bool CouldComputeBECount =
true;
8880 const SCEV *MustExitMaxBECount =
nullptr;
8881 const SCEV *MayExitMaxBECount =
nullptr;
8882 bool MustExitMaxOrZero =
false;
8883 bool IsOnlyExit = ExitingBlocks.
size() == 1;
8895 if (ExitIfTrue == CI->
isZero())
8899 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
8901 assert((AllowPredicates || EL.Predicates.empty()) &&
8902 "Predicated exit limit when predicates are not allowed!");
8907 ++NumExitCountsComputed;
8911 CouldComputeBECount =
false;
8918 "Exact is known but symbolic isn't?");
8919 ++NumExitCountsNotComputed;
8934 DT.dominates(ExitBB, Latch)) {
8935 if (!MustExitMaxBECount) {
8936 MustExitMaxBECount = EL.ConstantMaxNotTaken;
8937 MustExitMaxOrZero = EL.MaxOrZero;
8940 EL.ConstantMaxNotTaken);
8944 MayExitMaxBECount = EL.ConstantMaxNotTaken;
8947 EL.ConstantMaxNotTaken);
8951 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
8955 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
8961 for (
const auto &Pair : ExitCounts) {
8963 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
8965 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
8966 {
L, AllowPredicates});
8968 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
8969 MaxBECount, MaxOrZero);
8972ScalarEvolution::ExitLimit
8973ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
8974 bool IsOnlyExit,
bool AllowPredicates) {
8975 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
8979 if (!Latch || !DT.dominates(ExitingBlock, Latch))
8987 "It should have one successor in loop and one exit block!");
8998 if (!
L->contains(SBB)) {
9003 assert(Exit &&
"Exiting block must have at least one exit");
9004 return computeExitLimitFromSingleExitSwitch(
9005 L, SI, Exit, IsOnlyExit);
9012 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9013 bool AllowPredicates) {
9014 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9015 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9016 ControlsOnlyExit, AllowPredicates);
9019std::optional<ScalarEvolution::ExitLimit>
9020ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9021 bool ExitIfTrue,
bool ControlsOnlyExit,
9022 bool AllowPredicates) {
9024 (void)this->ExitIfTrue;
9025 (void)this->AllowPredicates;
9027 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9028 this->AllowPredicates == AllowPredicates &&
9029 "Variance in assumed invariant key components!");
9030 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9031 if (Itr == TripCountMap.end())
9032 return std::nullopt;
9036void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9038 bool ControlsOnlyExit,
9039 bool AllowPredicates,
9041 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9042 this->AllowPredicates == AllowPredicates &&
9043 "Variance in assumed invariant key components!");
9045 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9046 assert(InsertResult.second &&
"Expected successful insertion!");
9051ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9052 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9053 bool ControlsOnlyExit,
bool AllowPredicates) {
9055 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9059 ExitLimit EL = computeExitLimitFromCondImpl(
9060 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9061 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9065ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9066 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9067 bool ControlsOnlyExit,
bool AllowPredicates) {
9069 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9070 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates))
9071 return *LimitFromBinOp;
9077 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9078 if (EL.hasFullInfo() || !AllowPredicates)
9082 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9102 const WithOverflowInst *WO;
9117 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9118 ControlsOnlyExit, AllowPredicates);
9119 if (EL.hasAnyInfo())
9124 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9127std::optional<ScalarEvolution::ExitLimit>
9128ScalarEvolution::computeExitLimitFromCondFromBinOp(
9129 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9130 bool ControlsOnlyExit,
bool AllowPredicates) {
9139 return std::nullopt;
9144 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9145 ExitLimit EL0 = computeExitLimitFromCondCached(
9146 Cache, L, Op0, ExitIfTrue, ControlsOnlyExit && !EitherMayExit,
9148 ExitLimit EL1 = computeExitLimitFromCondCached(
9149 Cache, L, Op1, ExitIfTrue, ControlsOnlyExit && !EitherMayExit,
9153 const Constant *NeutralElement = ConstantInt::get(ExitCond->
getType(), IsAnd);
9155 return Op1 == NeutralElement ? EL0 : EL1;
9157 return Op0 == NeutralElement ? EL1 : EL0;
9162 if (EitherMayExit) {
9172 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9174 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9177 EL1.ConstantMaxNotTaken);
9179 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9181 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9184 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9188 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9189 BECount = EL0.ExactNotTaken;
9202 SymbolicMaxBECount =
9204 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9208ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9209 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9210 bool AllowPredicates) {
9222 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9224 if (EL.hasAnyInfo())
9227 auto *ExhaustiveCount =
9228 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9231 return ExhaustiveCount;
9233 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9236ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9237 const Loop *L, CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
9238 bool ControlsOnlyExit,
bool AllowPredicates) {
9263 ConstantRange CompRange =
9279 auto *InnerLHS =
LHS;
9281 InnerLHS = ZExt->getOperand();
9328 if (EL.hasAnyInfo())
9345 if (EL.hasAnyInfo())
return EL;
9377 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9379 if (EL.hasAnyInfo())
9395 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9397 if (EL.hasAnyInfo())
9408ScalarEvolution::ExitLimit
9409ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9411 BasicBlock *ExitingBlock,
9412 bool ControlsOnlyExit) {
9413 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9416 if (
Switch->getDefaultDest() == ExitingBlock)
9420 "Default case must not exit the loop!");
9426 if (EL.hasAnyInfo())
9438 "Evaluation of SCEV at constant didn't fold correctly?");
9442ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9452 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9458 auto MatchPositiveShift =
9461 using namespace PatternMatch;
9463 ConstantInt *ShiftAmt;
9465 OutOpCode = Instruction::LShr;
9467 OutOpCode = Instruction::AShr;
9469 OutOpCode = Instruction::Shl;
9484 auto MatchShiftRecurrence =
9486 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9501 if (MatchPositiveShift(
LHS, V, OpC)) {
9502 PostShiftOpCode = OpC;
9508 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9511 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9517 MatchPositiveShift(BEValue, OpLHS, OpCodeOut) &&
9524 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9529 if (!MatchShiftRecurrence(
LHS, PN, OpCode))
9541 ConstantInt *StableValue =
nullptr;
9546 case Instruction::AShr: {
9554 StableValue = ConstantInt::get(Ty, 0);
9556 StableValue = ConstantInt::get(Ty, -1,
true);
9562 case Instruction::LShr:
9563 case Instruction::Shl:
9573 "Otherwise cannot be an operand to a branch instruction");
9575 if (
Result->isZeroValue()) {
9577 const SCEV *UpperBound =
9594 if (
const Function *
F = CI->getCalledFunction())
9603 if (!L->contains(
I))
return false;
9608 return L->getHeader() ==
I->getParent();
9684 if (!
I)
return nullptr;
9697 std::vector<Constant*>
Operands(
I->getNumOperands());
9699 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9708 if (!
C)
return nullptr;
9730 if (IncomingVal != CurrentVal) {
9733 IncomingVal = CurrentVal;
9745ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9748 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9757 DenseMap<Instruction *, Constant *> CurrentIterVals;
9759 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9765 for (PHINode &
PHI : Header->phis()) {
9767 CurrentIterVals[&
PHI] = StartCST;
9769 if (!CurrentIterVals.
count(PN))
9770 return RetVal =
nullptr;
9776 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9779 unsigned IterationNum = 0;
9781 for (; ; ++IterationNum) {
9782 if (IterationNum == NumIterations)
9783 return RetVal = CurrentIterVals[PN];
9787 DenseMap<Instruction *, Constant *> NextIterVals;
9792 NextIterVals[PN] = NextPHI;
9794 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9800 for (
const auto &
I : CurrentIterVals) {
9802 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9807 for (
const auto &
I : PHIsToCompute) {
9808 PHINode *
PHI =
I.first;
9811 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9814 if (NextPHI !=
I.second)
9815 StoppedEvolving =
false;
9820 if (StoppedEvolving)
9821 return RetVal = CurrentIterVals[PN];
9823 CurrentIterVals.swap(NextIterVals);
9827const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
9837 DenseMap<Instruction *, Constant *> CurrentIterVals;
9839 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9842 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
9844 for (PHINode &
PHI : Header->phis()) {
9846 CurrentIterVals[&
PHI] = StartCST;
9848 if (!CurrentIterVals.
count(PN))
9856 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
9863 if (CondVal->getValue() == uint64_t(ExitWhen)) {
9864 ++NumBruteForceTripCountsComputed;
9869 DenseMap<Instruction *, Constant *> NextIterVals;
9875 for (
const auto &
I : CurrentIterVals) {
9877 if (!
PHI ||
PHI->getParent() != Header)
continue;
9880 for (PHINode *
PHI : PHIsToCompute) {
9882 if (NextPHI)
continue;
9884 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9887 CurrentIterVals.
swap(NextIterVals);
9898 for (
auto &LS : Values)
9900 return LS.second ? LS.second : V;
9905 const SCEV *
C = computeSCEVAtScope(V, L);
9906 for (
auto &LS :
reverse(ValuesAtScopes[V]))
9907 if (LS.first == L) {
9910 ValuesAtScopesUsers[
C].push_back({L, V});
9921 switch (V->getSCEVType()) {
9954 assert(!
C->getType()->isPointerTy() &&
9955 "Can only have one pointer, and it must be last");
9982ScalarEvolution::getWithOperands(
const SCEV *S,
9983 SmallVectorImpl<const SCEV *> &NewOps) {
10017const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10018 switch (
V->getSCEVType()) {
10029 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10040 for (++i; i !=
e; ++i)
10084 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10086 if (OpAtScope !=
Ops[i]) {
10094 for (++i; i !=
e; ++i) {
10099 return getWithOperands(V, NewOps);
10114 const Loop *CurrLoop = this->LI[
I->getParent()];
10125 if (BackedgeTakenCount->
isZero()) {
10126 Value *InitValue =
nullptr;
10127 bool MultipleInitValues =
false;
10133 MultipleInitValues =
true;
10138 if (!MultipleInitValues && InitValue)
10147 unsigned InLoopPred =
10158 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10174 bool MadeImprovement =
false;
10189 MadeImprovement |= OrigV != OpV;
10194 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10199 if (!MadeImprovement)
10220const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10222 return stripInjectiveFunctions(ZExt->getOperand());
10224 return stripInjectiveFunctions(SExt->getOperand());
10243 assert(
A != 0 &&
"A must be non-zero.");
10279 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10299static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10305 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10306 << *AddRec <<
'\n');
10309 if (!LC || !MC || !
NC) {
10310 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10311 return std::nullopt;
10317 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10325 N =
N.sext(NewWidth);
10326 M = M.sext(NewWidth);
10327 L = L.sext(NewWidth);
10344 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10345 <<
", multiplied by " <<
T <<
'\n');
10354 std::optional<APInt>
Y) {
10356 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10359 return XW.
slt(YW) ? *
X : *
Y;
10362 return std::nullopt;
10363 return X ? *
X : *
Y;
10380 return std::nullopt;
10381 unsigned W =
X->getBitWidth();
10401static std::optional<APInt>
10407 return std::nullopt;
10410 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10411 std::optional<APInt>
X =
10414 return std::nullopt;
10419 return std::nullopt;
10434static std::optional<APInt>
10438 "Starting value of addrec should be 0");
10439 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10440 <<
Range <<
", addrec " << *AddRec <<
'\n');
10444 "Addrec's initial value should be in range");
10450 return std::nullopt;
10460 auto SolveForBoundary =
10461 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10464 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10465 << Bound <<
" (before multiplying by " << M <<
")\n");
10468 std::optional<APInt> SO;
10471 "signed overflow\n");
10475 "unsigned overflow\n");
10476 std::optional<APInt> UO =
10479 auto LeavesRange = [&] (
const APInt &
X) {
10496 return {std::nullopt,
false};
10501 if (LeavesRange(*Min))
10502 return { Min,
true };
10503 std::optional<APInt> Max = Min == SO ? UO : SO;
10504 if (LeavesRange(*Max))
10505 return { Max,
true };
10508 return {std::nullopt,
true};
10515 auto SL = SolveForBoundary(
Lower);
10516 auto SU = SolveForBoundary(
Upper);
10519 if (!SL.second || !SU.second)
10520 return std::nullopt;
10563ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10565 bool ControlsOnlyExit,
10566 bool AllowPredicates) {
10577 if (
C->getValue()->isZero())
return C;
10581 const SCEVAddRecExpr *AddRec =
10584 if (!AddRec && AllowPredicates)
10590 if (!AddRec || AddRec->
getLoop() != L)
10601 return ExitLimit(R, R, R,
false, Predicates);
10659 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10685 const SCEV *
Exact =
10693 const SCEV *SymbolicMax =
10695 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10704 AllowPredicates ? &Predicates :
nullptr, *
this);
10712 return ExitLimit(
E, M, S,
false, Predicates);
10715ScalarEvolution::ExitLimit
10716ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10724 if (!
C->getValue()->isZero())
10734std::pair<const BasicBlock *, const BasicBlock *>
10735ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10746 if (
const Loop *L = LI.getLoopFor(BB))
10747 return {
L->getLoopPredecessor(),
L->getHeader()};
10749 return {
nullptr, BB};
10758 if (
A ==
B)
return true;
10773 if (ComputesEqualValues(AI, BI))
10782 if (!
Add ||
Add->getNumOperands() != 2)
10785 ME && ME->getNumOperands() == 2 && ME->getOperand(0)->isAllOnesValue()) {
10786 LHS =
Add->getOperand(1);
10787 RHS = ME->getOperand(1);
10791 ME && ME->getNumOperands() == 2 && ME->getOperand(0)->isAllOnesValue()) {
10792 LHS =
Add->getOperand(0);
10793 RHS = ME->getOperand(1);
10804 auto TrivialCase = [&](
bool TriviallyTrue) {
10813 const SCEV *NewLHS, *NewRHS;
10837 return TrivialCase(
false);
10838 return TrivialCase(
true);
10861 const APInt &
RA = RC->getAPInt();
10863 bool SimplifiedByConstantRange =
false;
10868 return TrivialCase(
true);
10870 return TrivialCase(
false);
10879 Changed = SimplifiedByConstantRange =
true;
10883 if (!SimplifiedByConstantRange) {
10900 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
10906 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
10912 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
10918 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
10930 return TrivialCase(
true);
10932 return TrivialCase(
false);
11037 auto NonRecursive = [
this, OrNegative](
const SCEV *S) {
11039 return C->getAPInt().isPowerOf2() ||
11040 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11043 return isa<SCEVVScale>(S) && F.hasFnAttribute(Attribute::VScaleRange);
11046 if (NonRecursive(S))
11072 APInt C = Cst->getAPInt();
11073 return C.urem(M) == 0;
11081 const SCEV *SmodM =
11096 for (
auto *
A : Assumptions)
11097 if (
A->implies(
P, *
this))
11105std::pair<const SCEV *, const SCEV *>
11108 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11110 return { Start, Start };
11112 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11121 getUsedLoops(LHS, LoopsUsed);
11122 getUsedLoops(RHS, LoopsUsed);
11124 if (LoopsUsed.
empty())
11129 for (
const auto *L1 : LoopsUsed)
11130 for (
const auto *L2 : LoopsUsed)
11131 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11132 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11133 "Domination relationship is not a linear order");
11163 SplitRHS.second) &&
11175 if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
11179 return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11189 return std::nullopt;
11204 if (KnownWithoutContext)
11205 return KnownWithoutContext;
11212 return std::nullopt;
11218 const Loop *L = LHS->getLoop();
11223std::optional<ScalarEvolution::MonotonicPredicateType>
11226 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11232 auto ResultSwapped =
11235 assert(*ResultSwapped != *Result &&
11236 "monotonicity should flip as we flip the predicate");
11243std::optional<ScalarEvolution::MonotonicPredicateType>
11244ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11258 return std::nullopt;
11262 "Should be greater or less!");
11266 if (!LHS->hasNoUnsignedWrap())
11267 return std::nullopt;
11271 "Relational predicate is either signed or unsigned!");
11272 if (!
LHS->hasNoSignedWrap())
11273 return std::nullopt;
11275 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11283 return std::nullopt;
11286std::optional<ScalarEvolution::LoopInvariantPredicate>
11293 return std::nullopt;
11300 if (!ArLHS || ArLHS->
getLoop() != L)
11301 return std::nullopt;
11305 return std::nullopt;
11331 return std::nullopt;
11368 return std::nullopt;
11371std::optional<ScalarEvolution::LoopInvariantPredicate>
11376 Pred, LHS, RHS, L, CtxI, MaxIter))
11384 for (
auto *
Op :
UMin->operands())
11386 Pred, LHS, RHS, L, CtxI,
Op))
11388 return std::nullopt;
11391std::optional<ScalarEvolution::LoopInvariantPredicate>
11406 return std::nullopt;
11413 if (!AR || AR->
getLoop() != L)
11414 return std::nullopt;
11418 return std::nullopt;
11424 if (Step != One && Step != MinusOne)
11425 return std::nullopt;
11431 return std::nullopt;
11437 return std::nullopt;
11445 if (Step == MinusOne)
11449 return std::nullopt;
11455bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11461 auto CheckRange = [&](
bool IsSigned) {
11464 return RangeLHS.
icmp(Pred, RangeRHS);
11473 if (CheckRange(
true) || CheckRange(
false))
11482bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11489 auto MatchBinaryAddToConst = [
this](
const SCEV *
X,
const SCEV *
Y,
11490 APInt &OutC1, APInt &OutC2,
11492 const SCEV *XNonConstOp, *XConstOp;
11493 const SCEV *YNonConstOp, *YConstOp;
11497 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11500 XFlagsPresent = ExpectedFlags;
11505 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11508 YFlagsPresent = ExpectedFlags;
11511 if (YNonConstOp != XNonConstOp)
11519 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11522 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11582bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11604bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11605 const SCEV *
LHS,
const SCEV *
RHS) {
11610 return any_of(*BB, [&](
const Instruction &
I) {
11611 using namespace llvm::PatternMatch;
11616 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11630 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11635 "This cannot be done on broken IR!");
11638 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11647 if (LoopContinuePredicate && LoopContinuePredicate->
isConditional() &&
11648 isImpliedCond(Pred, LHS, RHS,
11650 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11655 if (WalkingBEDominatingConds)
11661 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11662 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11669 const SCEV *LoopCounter =
11677 for (
auto &AssumeVH : AC.assumptions()) {
11684 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11688 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11691 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11692 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11693 assert(DTN &&
"should reach the loop header before reaching the root!");
11696 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11704 if (!ContinuePredicate || !ContinuePredicate->
isConditional())
11718 assert(DT.dominates(DominatingEdge, Latch) &&
"should be!");
11720 if (isImpliedCond(Pred, LHS, RHS, Condition,
11734 if (!DT.isReachableFromEntry(BB))
11738 "This cannot be done on broken IR!");
11746 const bool ProvingStrictComparison =
11748 bool ProvedNonStrictComparison =
false;
11749 bool ProvedNonEquality =
false;
11752 if (!ProvedNonStrictComparison)
11753 ProvedNonStrictComparison = Fn(NonStrictPredicate);
11754 if (!ProvedNonEquality)
11756 if (ProvedNonStrictComparison && ProvedNonEquality)
11761 if (ProvingStrictComparison) {
11763 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
11765 if (SplitAndProve(ProofFn))
11770 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
11772 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
11774 if (ProvingStrictComparison) {
11776 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
11778 if (SplitAndProve(ProofFn))
11787 const Loop *ContainingLoop = LI.getLoopFor(BB);
11789 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
11793 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
11794 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
11806 for (
auto &AssumeVH : AC.assumptions()) {
11810 if (!DT.dominates(CI, BB))
11813 if (ProveViaCond(CI->getArgOperand(0),
false))
11819 F.getParent(), Intrinsic::experimental_guard);
11821 for (
const auto *GU : GuardDecl->users())
11823 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
11824 if (ProveViaCond(Guard->getArgOperand(0),
false))
11839 "LHS is not available at Loop Entry");
11841 "RHS is not available at Loop Entry");
11843 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11854 if (FoundCondValue ==
11858 if (!PendingLoopPredicates.insert(FoundCondValue).second)
11862 make_scope_exit([&]() { PendingLoopPredicates.erase(FoundCondValue); });
11865 const Value *Op0, *Op1;
11868 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
11872 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
11873 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
11877 if (!ICI)
return false;
11881 CmpPredicate FoundPred;
11890 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
11893bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
11894 const SCEV *
RHS, CmpPredicate FoundPred,
11895 const SCEV *FoundLHS,
const SCEV *FoundRHS,
11896 const Instruction *CtxI) {
11906 auto *WideType = FoundLHS->
getType();
11918 TruncFoundLHS, TruncFoundRHS, CtxI))
11944 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
11948bool ScalarEvolution::isImpliedCondBalancedTypes(
11949 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
11950 const SCEV *FoundLHS,
const SCEV *FoundRHS,
const Instruction *CtxI) {
11953 "Types should be balanced!");
11960 if (FoundLHS == FoundRHS)
11964 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
11976 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
11993 LHS, FoundLHS, FoundRHS, CtxI);
11995 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12017 assert(P1 != P2 &&
"Handled earlier!");
12021 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12026 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12029 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12030 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12031 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12036 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12047 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12048 CanonicalRHS, CanonicalFoundLHS,
12049 CanonicalFoundRHS);
12054 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12055 CanonicalRHS, CanonicalFoundLHS,
12056 CanonicalFoundRHS);
12063 const SCEVConstant *
C =
nullptr;
12064 const SCEV *
V =
nullptr;
12082 if (Min ==
C->getAPInt()) {
12087 APInt SharperMin = Min + 1;
12090 case ICmpInst::ICMP_SGE:
12091 case ICmpInst::ICMP_UGE:
12094 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12099 case ICmpInst::ICMP_SGT:
12100 case ICmpInst::ICMP_UGT:
12110 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12115 case ICmpInst::ICMP_SLE:
12116 case ICmpInst::ICMP_ULE:
12117 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12118 LHS, V, getConstant(SharperMin), CtxI))
12122 case ICmpInst::ICMP_SLT:
12123 case ICmpInst::ICMP_ULT:
12124 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12125 LHS, V, getConstant(Min), CtxI))
12139 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12143 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12146 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12153bool ScalarEvolution::splitBinaryAdd(
const SCEV *Expr,
12154 const SCEV *&L,
const SCEV *&R,
12157 if (!AE || AE->getNumOperands() != 2)
12160 L = AE->getOperand(0);
12161 R = AE->getOperand(1);
12162 Flags = AE->getNoWrapFlags();
12166std::optional<APInt>
12173 APInt DiffMul(BW, 1);
12176 for (
unsigned I = 0;
I < 8; ++
I) {
12185 if (LAR->getLoop() != MAR->getLoop())
12186 return std::nullopt;
12190 if (!LAR->isAffine() || !MAR->isAffine())
12191 return std::nullopt;
12193 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12194 return std::nullopt;
12196 Less = LAR->getStart();
12197 More = MAR->getStart();
12202 auto MatchConstMul =
12203 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12205 if (!M || M->getNumOperands() != 2 ||
12207 return std::nullopt;
12211 if (
auto MatchedMore = MatchConstMul(More)) {
12212 if (
auto MatchedLess = MatchConstMul(
Less)) {
12213 if (MatchedMore->second == MatchedLess->second) {
12214 More = MatchedMore->first;
12215 Less = MatchedLess->first;
12216 DiffMul *= MatchedMore->second;
12227 Diff +=
C->getAPInt() * DiffMul;
12230 Diff -=
C->getAPInt() * DiffMul;
12233 Multiplicity[S] +=
Mul;
12235 auto Decompose = [&](
const SCEV *S,
int Mul) {
12242 Decompose(More, 1);
12243 Decompose(
Less, -1);
12247 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12248 for (
const auto &[S,
Mul] : Multiplicity) {
12253 return std::nullopt;
12255 }
else if (
Mul == -1) {
12257 return std::nullopt;
12260 return std::nullopt;
12264 if (NewMore == More || NewLess ==
Less)
12265 return std::nullopt;
12271 if (!More && !
Less)
12275 if (!More || !
Less)
12276 return std::nullopt;
12280 return std::nullopt;
12283bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12307 if (!L->contains(ContextBB) || !DT.
dominates(ContextBB, L->getLoopLatch()))
12318 if (!L->contains(ContextBB) || !DT.
dominates(ContextBB, L->getLoopLatch()))
12328bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12331 const SCEV *FoundLHS,
12332 const SCEV *FoundRHS) {
12341 if (!AddRecFoundLHS)
12348 const Loop *
L = AddRecFoundLHS->getLoop();
12349 if (L != AddRecLHS->getLoop())
12388 if (!RDiff || *LDiff != *RDiff)
12391 if (LDiff->isMinValue())
12394 APInt FoundRHSLimit;
12397 FoundRHSLimit = -(*RDiff);
12409bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12410 const SCEV *
RHS,
const SCEV *FoundLHS,
12411 const SCEV *FoundRHS,
unsigned Depth) {
12412 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12416 bool Erased = PendingMerges.erase(LPhi);
12417 assert(Erased &&
"Failed to erase LPhi!");
12421 bool Erased = PendingMerges.erase(RPhi);
12422 assert(Erased &&
"Failed to erase RPhi!");
12430 if (!PendingMerges.insert(Phi).second)
12444 if (!PendingMerges.insert(Phi).second)
12450 if (!LPhi && !RPhi)
12461 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12465 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12466 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12467 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12468 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12471 if (RPhi && RPhi->getParent() == LBB) {
12478 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12479 if (!ProvedEasily(L, R))
12490 auto *RLoop = RAR->
getLoop();
12491 auto *Predecessor = RLoop->getLoopPredecessor();
12492 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12494 if (!ProvedEasily(L1, RAR->
getStart()))
12496 auto *Latch = RLoop->getLoopLatch();
12497 assert(Latch &&
"Loop with AddRec with no latch?");
12518 if (
auto *Loop = LI.getLoopFor(LBB))
12521 if (!ProvedEasily(L,
RHS))
12528bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12531 const SCEV *FoundLHS,
12532 const SCEV *FoundRHS) {
12535 if (
RHS == FoundRHS) {
12540 if (
LHS != FoundLHS)
12547 Value *Shiftee, *ShiftValue;
12549 using namespace PatternMatch;
12550 if (
match(SUFoundRHS->getValue(),
12552 auto *ShifteeS =
getSCEV(Shiftee);
12570bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12572 const SCEV *FoundLHS,
12573 const SCEV *FoundRHS,
12574 const Instruction *CtxI) {
12575 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12577 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12579 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12580 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12582 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12586template <
typename MinMaxExprType>
12588 const SCEV *Candidate) {
12593 return is_contained(MinMaxExpr->operands(), Candidate);
12606 const SCEV *LStart, *RStart, *Step;
12656bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12658 const SCEV *FoundLHS,
12659 const SCEV *FoundRHS,
12663 "LHS and RHS have different sizes?");
12666 "FoundLHS and FoundRHS have different sizes?");
12700 auto GetOpFromSExt = [&](
const SCEV *S) {
12702 return Ext->getOperand();
12709 auto *OrigLHS =
LHS;
12710 auto *OrigFoundLHS = FoundLHS;
12711 LHS = GetOpFromSExt(
LHS);
12712 FoundLHS = GetOpFromSExt(FoundLHS);
12715 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
12718 FoundRHS,
Depth + 1);
12731 if (!LHSAddExpr->hasNoSignedWrap())
12734 auto *LL = LHSAddExpr->getOperand(0);
12735 auto *LR = LHSAddExpr->getOperand(1);
12739 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
12740 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
12745 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
12751 using namespace llvm::PatternMatch;
12770 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
12778 auto *DTy = Denominator->getType();
12779 auto *FRHSTy = FoundRHS->
getType();
12780 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
12799 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
12810 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
12812 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
12820 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
12853bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
12857 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
12860 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
12863bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
12866 const SCEV *FoundLHS,
12867 const SCEV *FoundRHS) {
12903 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
12909bool ScalarEvolution::isImpliedCondOperandsViaRanges(
12910 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
12911 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
12925 ConstantRange FoundLHSRange =
12929 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
12936 return LHSRange.
icmp(Pred, ConstRHS);
12939bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
12952 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
12960 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
12963bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
12975 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
12983 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
12995const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
12996 const SCEV *Stride,
13027 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13038 :
APIntOps::umax(MaxEnd, MinStart);
13045ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13046 const Loop *L,
bool IsSigned,
13047 bool ControlsOnlyExit,
bool AllowPredicates) {
13051 bool PredicatedIV =
false;
13056 auto canProveNUW = [&]() {
13059 if (!ControlsOnlyExit)
13080 Limit = Limit.
zext(OuterBitWidth);
13092 Type *Ty = ZExt->getType();
13103 if (!
IV && AllowPredicates) {
13108 PredicatedIV =
true;
13112 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13126 bool NoWrap = ControlsOnlyExit &&
IV->getNoWrapFlags(WrapType);
13129 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13134 if (!PositiveStride) {
13186 auto wouldZeroStrideBeUB = [&]() {
13198 if (!wouldZeroStrideBeUB()) {
13202 }
else if (!NoWrap) {
13205 if (canIVOverflowOnLT(
RHS, Stride, IsSigned))
13218 const SCEV *
Start =
IV->getStart();
13224 const SCEV *OrigStart =
Start;
13225 const SCEV *OrigRHS =
RHS;
13226 if (
Start->getType()->isPointerTy()) {
13237 const SCEV *End =
nullptr, *BECount =
nullptr,
13238 *BECountIfBackedgeTaken =
nullptr;
13241 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13242 RHSAddRec->getNoWrapFlags()) {
13255 const SCEV *RHSStart = RHSAddRec->getStart();
13256 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13268 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13277 BECountIfBackedgeTaken =
13282 if (BECount ==
nullptr) {
13287 const SCEV *MaxBECount = computeMaxBECountForLT(
13290 MaxBECount,
false , Predicates);
13297 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13324 const SCEV *Numerator =
13330 auto canProveRHSGreaterThanEqualStart = [&]() {
13349 auto *StartMinusOne =
13356 if (canProveRHSGreaterThanEqualStart()) {
13371 BECountIfBackedgeTaken =
13387 bool MayAddOverflow = [&] {
13433 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13447 if (!MayAddOverflow) {
13459 const SCEV *ConstantMaxBECount;
13460 bool MaxOrZero =
false;
13462 ConstantMaxBECount = BECount;
13463 }
else if (BECountIfBackedgeTaken &&
13468 ConstantMaxBECount = BECountIfBackedgeTaken;
13471 ConstantMaxBECount = computeMaxBECountForLT(
13479 const SCEV *SymbolicMaxBECount =
13481 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13485ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13486 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13487 bool ControlsOnlyExit,
bool AllowPredicates) {
13494 if (!
IV && AllowPredicates)
13501 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13505 bool NoWrap = ControlsOnlyExit &&
IV->getNoWrapFlags(WrapType);
13518 if (!Stride->
isOne() && !NoWrap)
13519 if (canIVOverflowOnGT(
RHS, Stride, IsSigned))
13522 const SCEV *
Start =
IV->getStart();
13523 const SCEV *End =
RHS;
13534 if (
Start->getType()->isPointerTy()) {
13569 const SCEV *ConstantMaxBECount =
13576 ConstantMaxBECount = BECount;
13577 const SCEV *SymbolicMaxBECount =
13580 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13586 if (
Range.isFullSet())
13591 if (!SC->getValue()->isZero()) {
13597 return ShiftedAddRec->getNumIterationsInRange(
13598 Range.subtract(SC->getAPInt()), SE);
13629 APInt ExitVal = (End +
A).udiv(
A);
13642 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13643 "Linear scev computation is off in a bad way!");
13674 assert(!
Last->isZero() &&
"Recurrency with zero step?");
13702 Ty = Store->getValueOperand()->getType();
13704 Ty = Load->getType();
13717 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13719 SE->ConstantEvolutionLoopExitValue.erase(PN);
13720 SE->eraseValueFromMap(getValPtr());
13724void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
13725 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13735 : CallbackVH(
V), SE(se) {}
13744 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
13746 LoopDispositions(64), BlockDispositions(64) {
13758 F.getParent(), Intrinsic::experimental_guard);
13759 HasGuards = GuardDecl && !GuardDecl->use_empty();
13763 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
13764 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
13765 ValueExprMap(
std::
move(Arg.ValueExprMap)),
13766 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
13767 PendingPhiRanges(
std::
move(Arg.PendingPhiRanges)),
13768 PendingMerges(
std::
move(Arg.PendingMerges)),
13769 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
13770 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
13771 PredicatedBackedgeTakenCounts(
13772 std::
move(Arg.PredicatedBackedgeTakenCounts)),
13773 BECountUsers(
std::
move(Arg.BECountUsers)),
13774 ConstantEvolutionLoopExitValue(
13775 std::
move(Arg.ConstantEvolutionLoopExitValue)),
13776 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
13777 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
13778 LoopDispositions(
std::
move(Arg.LoopDispositions)),
13779 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
13780 BlockDispositions(
std::
move(Arg.BlockDispositions)),
13781 SCEVUsers(
std::
move(Arg.SCEVUsers)),
13782 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
13783 SignedRanges(
std::
move(Arg.SignedRanges)),
13784 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
13785 UniquePreds(
std::
move(Arg.UniquePreds)),
13786 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
13787 LoopUsers(
std::
move(Arg.LoopUsers)),
13788 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
13789 FirstUnknown(Arg.FirstUnknown) {
13790 Arg.FirstUnknown =
nullptr;
13799 Tmp->~SCEVUnknown();
13801 FirstUnknown =
nullptr;
13803 ExprValueMap.clear();
13804 ValueExprMap.clear();
13806 BackedgeTakenCounts.clear();
13807 PredicatedBackedgeTakenCounts.clear();
13809 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
13810 assert(PendingPhiRanges.empty() &&
"getRangeRef garbage");
13811 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
13812 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
13813 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
13835 L->getHeader()->printAsOperand(OS,
false);
13839 L->getExitingBlocks(ExitingBlocks);
13840 if (ExitingBlocks.
size() != 1)
13841 OS <<
"<multiple exits> ";
13845 OS <<
"backedge-taken count is ";
13848 OS <<
"Unpredictable backedge-taken count.";
13851 if (ExitingBlocks.
size() > 1)
13852 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
13853 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
13861 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
13864 OS <<
"\n Predicates:\n";
13865 for (
const auto *
P : Predicates)
13873 L->getHeader()->printAsOperand(OS,
false);
13878 OS <<
"constant max backedge-taken count is ";
13881 OS <<
", actual taken count either this or zero.";
13883 OS <<
"Unpredictable constant max backedge-taken count. ";
13888 L->getHeader()->printAsOperand(OS,
false);
13893 OS <<
"symbolic max backedge-taken count is ";
13896 OS <<
", actual taken count either this or zero.";
13898 OS <<
"Unpredictable symbolic max backedge-taken count. ";
13902 if (ExitingBlocks.
size() > 1)
13903 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
13904 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
13914 OS <<
"\n predicated symbolic max exit count for "
13915 << ExitingBlock->
getName() <<
": ";
13917 OS <<
"\n Predicates:\n";
13918 for (
const auto *
P : Predicates)
13928 assert(!Preds.
empty() &&
"Different predicated BTC, but no predicates");
13930 L->getHeader()->printAsOperand(OS,
false);
13933 OS <<
"Predicated backedge-taken count is ";
13936 OS <<
"Unpredictable predicated backedge-taken count.";
13938 OS <<
" Predicates:\n";
13939 for (
const auto *
P : Preds)
13944 auto *PredConstantMax =
13946 if (PredConstantMax != ConstantBTC) {
13948 "different predicated constant max BTC but no predicates");
13950 L->getHeader()->printAsOperand(OS,
false);
13953 OS <<
"Predicated constant max backedge-taken count is ";
13956 OS <<
"Unpredictable predicated constant max backedge-taken count.";
13958 OS <<
" Predicates:\n";
13959 for (
const auto *
P : Preds)
13964 auto *PredSymbolicMax =
13966 if (SymbolicBTC != PredSymbolicMax) {
13968 "Different predicated symbolic max BTC, but no predicates");
13970 L->getHeader()->printAsOperand(OS,
false);
13973 OS <<
"Predicated symbolic max backedge-taken count is ";
13976 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
13978 OS <<
" Predicates:\n";
13979 for (
const auto *
P : Preds)
13985 L->getHeader()->printAsOperand(OS,
false);
14001 OS <<
"Computable";
14010 OS <<
"DoesNotDominate";
14016 OS <<
"ProperlyDominates";
14033 OS <<
"Classifying expressions for: ";
14034 F.printAsOperand(OS,
false);
14049 const Loop *L = LI.getLoopFor(
I.getParent());
14064 OS <<
"\t\t" "Exits: ";
14067 OS <<
"<<Unknown>>";
14073 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14075 OS <<
"\t\t" "LoopDispositions: { ";
14081 Iter->getHeader()->printAsOperand(OS,
false);
14089 OS <<
"\t\t" "LoopDispositions: { ";
14095 InnerL->getHeader()->printAsOperand(OS,
false);
14106 OS <<
"Determining loop execution counts for: ";
14107 F.printAsOperand(OS,
false);
14115 auto &Values = LoopDispositions[S];
14116 for (
auto &V : Values) {
14117 if (V.getPointer() == L)
14122 auto &Values2 = LoopDispositions[S];
14124 if (V.getPointer() == L) {
14133ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14152 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14153 " dominate the contained loop's header?");
14180 bool HasVarying =
false;
14214 auto &Values = BlockDispositions[S];
14215 for (
auto &V : Values) {
14216 if (V.getPointer() == BB)
14221 auto &Values2 = BlockDispositions[S];
14223 if (V.getPointer() == BB) {
14232ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14261 bool Proper =
true;
14272 if (Instruction *
I =
14274 if (
I->getParent() == BB)
14276 if (DT.properlyDominates(
I->getParent(), BB))
14299void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14302 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14303 auto It = BECounts.find(L);
14304 if (It != BECounts.end()) {
14305 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14306 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14308 auto UserIt = BECountUsers.find(S);
14309 assert(UserIt != BECountUsers.end());
14314 BECounts.erase(It);
14322 while (!Worklist.
empty()) {
14324 auto Users = SCEVUsers.find(Curr);
14325 if (
Users != SCEVUsers.end())
14326 for (
const auto *User :
Users->second)
14327 if (ToForget.
insert(User).second)
14331 for (
const auto *S : ToForget)
14332 forgetMemoizedResultsImpl(S);
14334 for (
auto I = PredicatedSCEVRewrites.begin();
14335 I != PredicatedSCEVRewrites.end();) {
14336 std::pair<const SCEV *, const Loop *>
Entry =
I->first;
14337 if (ToForget.count(
Entry.first))
14338 PredicatedSCEVRewrites.erase(
I++);
14344void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14345 LoopDispositions.erase(S);
14346 BlockDispositions.erase(S);
14347 UnsignedRanges.erase(S);
14348 SignedRanges.erase(S);
14349 HasRecMap.erase(S);
14350 ConstantMultipleCache.erase(S);
14353 UnsignedWrapViaInductionTried.erase(AR);
14354 SignedWrapViaInductionTried.erase(AR);
14357 auto ExprIt = ExprValueMap.find(S);
14358 if (ExprIt != ExprValueMap.end()) {
14359 for (
Value *V : ExprIt->second) {
14360 auto ValueIt = ValueExprMap.find_as(V);
14361 if (ValueIt != ValueExprMap.end())
14362 ValueExprMap.erase(ValueIt);
14364 ExprValueMap.erase(ExprIt);
14367 auto ScopeIt = ValuesAtScopes.find(S);
14368 if (ScopeIt != ValuesAtScopes.end()) {
14369 for (
const auto &Pair : ScopeIt->second)
14372 std::make_pair(Pair.first, S));
14373 ValuesAtScopes.erase(ScopeIt);
14376 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14377 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14378 for (
const auto &Pair : ScopeUserIt->second)
14379 llvm::erase(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
14380 ValuesAtScopesUsers.erase(ScopeUserIt);
14383 auto BEUsersIt = BECountUsers.find(S);
14384 if (BEUsersIt != BECountUsers.end()) {
14386 auto Copy = BEUsersIt->second;
14387 for (
const auto &Pair : Copy)
14388 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14389 BECountUsers.erase(BEUsersIt);
14392 auto FoldUser = FoldCacheUser.find(S);
14393 if (FoldUser != FoldCacheUser.end())
14394 for (
auto &KV : FoldUser->second)
14395 FoldCache.erase(KV);
14396 FoldCacheUser.erase(S);
14400ScalarEvolution::getUsedLoops(
const SCEV *S,
14402 struct FindUsedLoops {
14403 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14404 : LoopsUsed(LoopsUsed) {}
14405 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14406 bool follow(
const SCEV *S) {
14412 bool isDone()
const {
return false; }
14415 FindUsedLoops
F(LoopsUsed);
14416 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14419void ScalarEvolution::getReachableBlocks(
14422 Worklist.
push_back(&F.getEntryBlock());
14423 while (!Worklist.
empty()) {
14425 if (!Reachable.
insert(BB).second)
14433 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14440 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14444 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14479 SCEVMapper SCM(SE2);
14481 SE2.getReachableBlocks(ReachableBlocks, F);
14483 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14501 while (!LoopStack.
empty()) {
14507 if (!ReachableBlocks.
contains(L->getHeader()))
14512 auto It = BackedgeTakenCounts.find(L);
14513 if (It == BackedgeTakenCounts.end())
14517 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14537 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14538 if (Delta && !Delta->
isZero()) {
14539 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14540 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14541 dbgs() <<
"New: " << *NewBECount <<
"\n";
14542 dbgs() <<
"Delta: " << *Delta <<
"\n";
14550 while (!Worklist.
empty()) {
14552 if (ValidLoops.
insert(L).second)
14553 Worklist.
append(L->begin(), L->end());
14555 for (
const auto &KV : ValueExprMap) {
14560 "AddRec references invalid loop");
14565 auto It = ExprValueMap.find(KV.second);
14566 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14567 dbgs() <<
"Value " << *KV.first
14568 <<
" is in ValueExprMap but not in ExprValueMap\n";
14573 if (!ReachableBlocks.
contains(
I->getParent()))
14575 const SCEV *OldSCEV = SCM.visit(KV.second);
14577 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14578 if (Delta && !Delta->
isZero()) {
14579 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14580 <<
"Old: " << *OldSCEV <<
"\n"
14581 <<
"New: " << *NewSCEV <<
"\n"
14582 <<
"Delta: " << *Delta <<
"\n";
14588 for (
const auto &KV : ExprValueMap) {
14589 for (
Value *V : KV.second) {
14590 const SCEV *S = ValueExprMap.lookup(V);
14592 dbgs() <<
"Value " << *V
14593 <<
" is in ExprValueMap but not in ValueExprMap\n";
14596 if (S != KV.first) {
14597 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14598 << *KV.first <<
"\n";
14605 for (
const auto &S : UniqueSCEVs) {
14610 auto It = SCEVUsers.find(
Op);
14611 if (It != SCEVUsers.end() && It->second.count(&S))
14613 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14614 <<
" is not being tracked!\n";
14620 for (
const auto &ValueAndVec : ValuesAtScopes) {
14622 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14623 const Loop *L = LoopAndValueAtScope.first;
14624 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
14626 auto It = ValuesAtScopesUsers.find(ValueAtScope);
14627 if (It != ValuesAtScopesUsers.end() &&
14630 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14631 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14637 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14638 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14639 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14640 const Loop *L = LoopAndValue.first;
14641 const SCEV *
Value = LoopAndValue.second;
14643 auto It = ValuesAtScopes.find(
Value);
14644 if (It != ValuesAtScopes.end() &&
14645 is_contained(It->second, std::make_pair(L, ValueAtScope)))
14647 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14648 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14654 auto VerifyBECountUsers = [&](
bool Predicated) {
14656 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14657 for (
const auto &LoopAndBEInfo : BECounts) {
14658 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14659 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14661 auto UserIt = BECountUsers.find(S);
14662 if (UserIt != BECountUsers.end() &&
14663 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14665 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14666 <<
" missing from BECountUsers\n";
14673 VerifyBECountUsers(
false);
14674 VerifyBECountUsers(
true);
14677 for (
auto &[S, Values] : LoopDispositions) {
14678 for (
auto [
Loop, CachedDisposition] : Values) {
14680 if (CachedDisposition != RecomputedDisposition) {
14681 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
14682 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
14683 << RecomputedDisposition <<
"\n";
14690 for (
auto &[S, Values] : BlockDispositions) {
14691 for (
auto [BB, CachedDisposition] : Values) {
14693 if (CachedDisposition != RecomputedDisposition) {
14694 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
14695 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
14696 <<
", actual " << RecomputedDisposition <<
"\n";
14703 for (
auto [
FoldID, Expr] : FoldCache) {
14704 auto I = FoldCacheUser.find(Expr);
14705 if (
I == FoldCacheUser.end()) {
14706 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
14711 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
14715 for (
auto [Expr, IDs] : FoldCacheUser) {
14716 for (
auto &
FoldID : IDs) {
14719 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
14724 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
14725 <<
" != " << *Expr <<
"!\n";
14736 for (
auto [S, Multiple] : ConstantMultipleCache) {
14738 if ((Multiple != 0 && RecomputedMultiple != 0 &&
14739 Multiple.
urem(RecomputedMultiple) != 0 &&
14740 RecomputedMultiple.
urem(Multiple) != 0)) {
14741 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
14742 << *S <<
" : Computed " << RecomputedMultiple
14743 <<
" but cache contains " << Multiple <<
"!\n";
14751 FunctionAnalysisManager::Invalidator &Inv) {
14783 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
14784 <<
F.getName() <<
"':\n";
14790 "Scalar Evolution Analysis",
false,
true)
14839 const SCEV *LHS,
const SCEV *RHS) {
14841 assert(LHS->getType() == RHS->getType() &&
14842 "Type mismatch between LHS and RHS");
14845 ID.AddInteger(Pred);
14846 ID.AddPointer(LHS);
14847 ID.AddPointer(RHS);
14848 void *IP =
nullptr;
14849 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
14853 UniquePreds.InsertNode(Eq, IP);
14864 ID.AddInteger(AddedFlags);
14865 void *IP =
nullptr;
14866 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
14868 auto *OF =
new (SCEVAllocator)
14870 UniquePreds.InsertNode(OF, IP);
14890 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
14891 return Rewriter.visit(S);
14897 for (
const auto *Pred : U->getPredicates())
14899 if (IPred->getLHS() == Expr &&
14901 return IPred->getRHS();
14903 if (IPred->getLHS() == Expr &&
14904 IPred->getPredicate() == ICmpInst::ICMP_EQ)
14905 return IPred->getRHS();
14908 return convertToAddRecWithPreds(Expr);
14911 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
14927 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
14944 explicit SCEVPredicateRewriter(
14945 const Loop *L, ScalarEvolution &SE,
14946 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
14947 const SCEVPredicate *Pred)
14948 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
14950 bool addOverflowAssumption(
const SCEVPredicate *
P) {
14953 return Pred && Pred->
implies(
P, SE);
14959 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
14962 return addOverflowAssumption(
A);
14971 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
14975 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
14977 if (!PredicatedRewrite)
14979 for (
const auto *
P : PredicatedRewrite->second){
14982 if (L != WP->getExpr()->getLoop())
14985 if (!addOverflowAssumption(
P))
14988 return PredicatedRewrite->first;
14991 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
14992 const SCEVPredicate *Pred;
15001 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15008 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15028 if (!Step->
isOne())
15053 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15054 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15067 return Op->LHS == LHS &&
Op->RHS == RHS;
15074 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15076 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15101 const SCEV *Start = AR->getStart();
15102 const SCEV *OpStart =
Op->AR->getStart();
15107 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15110 const SCEV *Step = AR->getStepRecurrence(SE);
15111 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15164 if (Step->getValue()->getValue().isNonNegative())
15168 return ImpliedFlags;
15175 for (
const auto *
P : Preds)
15188 return this->implies(I, SE);
15196 for (
const auto *Pred : Preds)
15197 Pred->print(OS,
Depth);
15202 for (
const auto *Pred : Set->Preds)
15210 bool CheckImplies = Preds.
size() < 16;
15213 if (CheckImplies &&
implies(
N, SE))
15219 for (
auto *
P : Preds) {
15220 if (CheckImplies &&
N->implies(
P, SE))
15224 Preds = std::move(PrunedPreds);
15225 Preds.push_back(
N);
15232 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15237 for (
const auto *
Op :
Ops)
15242 SCEVUsers[
Op].insert(
User);
15246 const SCEV *Expr = SE.getSCEV(V);
15247 RewriteEntry &Entry = RewriteMap[Expr];
15250 if (Entry.second && Generation == Entry.first)
15251 return Entry.second;
15256 Expr = Entry.second;
15258 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15259 Entry = {Generation, NewSCEV};
15265 if (!BackedgeCount) {
15267 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15268 for (
const auto *
P : Preds)
15271 return BackedgeCount;
15275 if (!SymbolicMaxBackedgeCount) {
15277 SymbolicMaxBackedgeCount =
15278 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15279 for (
const auto *
P : Preds)
15282 return SymbolicMaxBackedgeCount;
15286 if (!SmallConstantMaxTripCount) {
15288 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15289 for (
const auto *
P : Preds)
15292 return *SmallConstantMaxTripCount;
15296 if (Preds->implies(&Pred, SE))
15301 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15302 updateGeneration();
15309void PredicatedScalarEvolution::updateGeneration() {
15311 if (++Generation == 0) {
15312 for (
auto &
II : RewriteMap) {
15313 const SCEV *Rewritten =
II.second.second;
15330 auto II = FlagsMap.insert({V, Flags});
15343 auto II = FlagsMap.find(V);
15345 if (
II != FlagsMap.end())
15354 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15359 for (
const auto *
P : NewPreds)
15362 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15368 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15371 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {
15372 for (
auto I :
Init.FlagsMap)
15373 FlagsMap.insert(
I);
15378 for (
auto *BB : L.getBlocks())
15379 for (
auto &
I : *BB) {
15380 if (!SE.isSCEVable(
I.getType()))
15383 auto *Expr = SE.getSCEV(&
I);
15384 auto II = RewriteMap.find(Expr);
15386 if (
II == RewriteMap.end())
15390 if (
II->second.second == Expr)
15395 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15404bool ScalarEvolution::matchURem(
const SCEV *Expr,
const SCEV *&LHS,
15405 const SCEV *&RHS) {
15414 LHS = Trunc->getOperand();
15420 if (LHS->getType() != Expr->
getType())
15427 if (
Add ==
nullptr ||
Add->getNumOperands() != 2)
15430 const SCEV *
A =
Add->getOperand(1);
15433 if (
Mul ==
nullptr)
15436 const auto MatchURemWithDivisor = [&](
const SCEV *
B) {
15448 return MatchURemWithDivisor(
Mul->getOperand(1)) ||
15449 MatchURemWithDivisor(
Mul->getOperand(2));
15452 if (
Mul->getNumOperands() == 2)
15453 return MatchURemWithDivisor(
Mul->getOperand(1)) ||
15454 MatchURemWithDivisor(
Mul->getOperand(0)) ||
15464 LoopGuards Guards(SE);
15468 collectFromBlock(SE, Guards, Header, Pred, VisitedBlocks);
15472void ScalarEvolution::LoopGuards::collectFromPHI(
15480 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15481 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15493 collectFromBlock(SE,
G->second, Phi.getParent(),
InBlock, VisitedBlocks,
15495 auto &RewriteMap =
G->second.RewriteMap;
15496 if (RewriteMap.empty())
15498 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15499 if (S == RewriteMap.end())
15505 return {C0, SM->getSCEVType()};
15508 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15509 MinMaxPattern P2) -> MinMaxPattern {
15510 auto [C1,
T1] =
P1;
15511 auto [C2, T2] = P2;
15512 if (!C1 || !C2 ||
T1 != T2)
15516 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15518 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15520 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15522 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15527 auto P = GetMinMaxConst(0);
15528 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15531 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15534 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15537 Guards.RewriteMap.insert({
LHS,
RHS});
15541void ScalarEvolution::LoopGuards::collectFromBlock(
15543 const BasicBlock *
Block,
const BasicBlock *Pred,
15544 SmallPtrSetImpl<const BasicBlock *> &VisitedBlocks,
unsigned Depth) {
15551 DenseMap<const SCEV *, const SCEV *>
15568 &ExprsToRewrite]() {
15569 const SCEVConstant *C1;
15582 if (ExactRegion.isWrappedSet() || ExactRegion.isFullSet())
15584 auto [
I,
Inserted] = RewriteMap.try_emplace(LHSUnknown);
15585 const SCEV *RewrittenLHS =
Inserted ? LHSUnknown :
I->second;
15593 if (MatchRangeCheckIdiom())
15599 auto IsMinMaxSCEVWithNonNegativeConstant =
15600 [&](
const SCEV *Expr,
SCEVTypes &SCTy,
const SCEV *&
LHS,
15601 const SCEV *&
RHS) {
15603 if (MinMax->getNumOperands() != 2)
15606 if (
C->getAPInt().isNegative())
15608 SCTy = MinMax->getSCEVType();
15609 LHS = MinMax->getOperand(0);
15610 RHS = MinMax->getOperand(1);
15619 auto GetNonNegExprAndPosDivisor = [&](
const SCEV *Expr,
const SCEV *Divisor,
15620 APInt &ExprVal, APInt &DivisorVal) {
15623 if (!ConstExpr || !ConstDivisor)
15625 ExprVal = ConstExpr->getAPInt();
15626 DivisorVal = ConstDivisor->getAPInt();
15627 return ExprVal.isNonNegative() && !DivisorVal.isNonPositive();
15633 auto GetNextSCEVDividesByDivisor = [&](
const SCEV *Expr,
15634 const SCEV *Divisor) {
15637 if (!GetNonNegExprAndPosDivisor(Expr, Divisor, ExprVal, DivisorVal))
15639 APInt Rem = ExprVal.
urem(DivisorVal);
15642 return SE.
getConstant(ExprVal + DivisorVal - Rem);
15649 auto GetPreviousSCEVDividesByDivisor = [&](
const SCEV *Expr,
15650 const SCEV *Divisor) {
15653 if (!GetNonNegExprAndPosDivisor(Expr, Divisor, ExprVal, DivisorVal))
15655 APInt Rem = ExprVal.
urem(DivisorVal);
15663 std::function<
const SCEV *(
const SCEV *,
const SCEV *)>
15664 ApplyDivisibiltyOnMinMaxExpr = [&](
const SCEV *MinMaxExpr,
15665 const SCEV *Divisor) {
15666 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15668 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15674 "Expected non-negative operand!");
15675 auto *DivisibleExpr =
15676 IsMin ? GetPreviousSCEVDividesByDivisor(MinMaxLHS, Divisor)
15677 : GetNextSCEVDividesByDivisor(MinMaxLHS, Divisor);
15679 ApplyDivisibiltyOnMinMaxExpr(MinMaxRHS, Divisor), DivisibleExpr};
15688 const SCEV *URemLHS =
nullptr;
15689 const SCEV *URemRHS =
nullptr;
15690 if (SE.matchURem(
LHS, URemLHS, URemRHS)) {
15692 auto I = RewriteMap.find(LHSUnknown);
15693 const SCEV *RewrittenLHS =
15694 I != RewriteMap.end() ?
I->second : LHSUnknown;
15695 RewrittenLHS = ApplyDivisibiltyOnMinMaxExpr(RewrittenLHS, URemRHS);
15696 const auto *Multiple =
15698 RewriteMap[LHSUnknown] = Multiple;
15719 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15721 if (From == FromRewritten)
15723 RewriteMap[From] = To;
15729 auto GetMaybeRewritten = [&](
const SCEV *S) {
15730 return RewriteMap.lookup_or(S, S);
15740 std::function<bool(
const SCEV *,
const SCEV *&)> HasDivisibiltyInfo =
15741 [&](
const SCEV *Expr,
const SCEV *&DividesBy) {
15743 if (
Mul->getNumOperands() != 2)
15745 auto *MulLHS =
Mul->getOperand(0);
15746 auto *MulRHS =
Mul->getOperand(1);
15750 if (Div->getOperand(1) == MulRHS) {
15751 DividesBy = MulRHS;
15756 return HasDivisibiltyInfo(MinMax->getOperand(0), DividesBy) ||
15757 HasDivisibiltyInfo(MinMax->getOperand(1), DividesBy);
15762 std::function<bool(
const SCEV *,
const SCEV *&)> IsKnownToDivideBy =
15763 [&](
const SCEV *Expr,
const SCEV *DividesBy) {
15767 return IsKnownToDivideBy(MinMax->getOperand(0), DividesBy) &&
15768 IsKnownToDivideBy(MinMax->getOperand(1), DividesBy);
15772 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15773 const SCEV *DividesBy =
nullptr;
15774 if (HasDivisibiltyInfo(RewrittenLHS, DividesBy))
15777 IsKnownToDivideBy(RewrittenLHS, DividesBy) ? DividesBy :
nullptr;
15791 switch (Predicate) {
15799 RHS = DividesBy ? GetPreviousSCEVDividesByDivisor(
RHS, DividesBy) :
RHS;
15805 RHS = DividesBy ? GetNextSCEVDividesByDivisor(
RHS, DividesBy) :
RHS;
15809 RHS = DividesBy ? GetPreviousSCEVDividesByDivisor(
RHS, DividesBy) :
RHS;
15813 RHS = DividesBy ? GetNextSCEVDividesByDivisor(
RHS, DividesBy) :
RHS;
15820 SmallPtrSet<const SCEV *, 16> Visited;
15822 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
15826 while (!Worklist.
empty()) {
15830 if (!Visited.
insert(From).second)
15832 const SCEV *FromRewritten = GetMaybeRewritten(From);
15833 const SCEV *To =
nullptr;
15835 switch (Predicate) {
15840 EnqueueOperands(
UMax);
15846 EnqueueOperands(
SMax);
15852 EnqueueOperands(
UMin);
15858 EnqueueOperands(
SMin);
15866 const SCEV *OneAlignedUp =
15867 DividesBy ? GetNextSCEVDividesByDivisor(One, DividesBy) : One;
15868 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
15876 AddRewrite(From, FromRewritten, To);
15893 SE.F.
getParent(), Intrinsic::experimental_guard);
15895 for (
const auto *GU : GuardDecl->users())
15897 if (Guard->getFunction() ==
Block->getParent() &&
15906 unsigned NumCollectedConditions = 0;
15908 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
15910 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
15911 VisitedBlocks.
insert(Pair.second);
15912 const BranchInst *LoopEntryPredicate =
15919 NumCollectedConditions++;
15923 if (
Depth > 0 && NumCollectedConditions == 2)
15931 if (Pair.second->hasNPredecessorsOrMore(2) &&
15933 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
15934 for (
auto &Phi : Pair.second->phis())
15935 collectFromPHI(SE, Guards, Phi, VisitedBlocks, IncomingGuards,
Depth);
15942 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
15943 SmallVector<Value *, 8> Worklist;
15944 SmallPtrSet<Value *, 8> Visited;
15946 while (!Worklist.
empty()) {
15953 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
15956 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap);
15972 Guards.PreserveNUW =
true;
15973 Guards.PreserveNSW =
true;
15974 for (
const SCEV *Expr : ExprsToRewrite) {
15975 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
15976 Guards.PreserveNUW &=
15978 Guards.PreserveNSW &=
15985 if (ExprsToRewrite.size() > 1) {
15986 for (
const SCEV *Expr : ExprsToRewrite) {
15987 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
15988 Guards.RewriteMap.erase(Expr);
15989 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
15998 class SCEVLoopGuardRewriter
16008 if (Guards.PreserveNUW)
16010 if (Guards.PreserveNSW)
16017 return Map.lookup_or(Expr, Expr);
16021 if (
const SCEV *S = Map.lookup(Expr))
16028 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16029 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16030 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16032 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16033 if (
const SCEV *S = Map.lookup(NarrowExt))
16034 return SE.getZeroExtendExpr(S, Ty);
16035 Bitwidth = Bitwidth / 2;
16043 if (
const SCEV *S = Map.lookup(Expr))
16050 if (
const SCEV *S = Map.lookup(Expr))
16056 if (
const SCEV *S = Map.lookup(Expr))
16068 if (
const SCEV *S = Map.lookup(
16070 return SE.getAddExpr(Expr->
getOperand(0), S);
16104 if (RewriteMap.empty())
16107 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16108 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 isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool isSignMask() const
Check if the APInt's value is returned by getSignMask.
LLVM_ABI APInt urem(const APInt &RHS) const
Unsigned remainder operation.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
bool isNegative() const
Determine sign of this APInt.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
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) 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.
class_match< const SCEVVScale > m_SCEVVScale()
bind_cst_ty m_scev_APInt(const APInt *&C)
Match an SCEV constant and bind it to an APInt.
cst_pred_ty< is_all_ones > m_scev_AllOnes()
Match an integer with all bits set.
SCEVUnaryExpr_match< SCEVZeroExtendExpr, Op0_t > m_scev_ZExt(const Op0_t &Op0)
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)
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, true > m_scev_c_Mul(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