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"),
340#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
358 OS <<
"(ptrtoaddr " << *
Op->getType() <<
" " << *
Op <<
" to "
365 OS <<
"(trunc " << *
Op->getType() <<
" " << *
Op <<
" to "
372 OS <<
"(zext " << *
Op->getType() <<
" " << *
Op <<
" to "
379 OS <<
"(sext " << *
Op->getType() <<
" " << *
Op <<
" to "
408 const char *OpStr =
nullptr;
421 OpStr =
" umin_seq ";
445 OS <<
"(" << *UDiv->
getLHS() <<
" /u " << *UDiv->
getRHS() <<
")";
452 OS <<
"***COULDNOTCOMPUTE***";
494 if (!
Mul)
return false;
498 if (!SC)
return false;
512 auto &Entry = ConstantSCEVs[V];
521 static_cast<SCEVConstant *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP)))
524 new (SCEVAllocator)
SCEVConstant(ID.Intern(SCEVAllocator), V);
525 UniqueSCEVs.InsertNode(S, IP);
540 ConstantInt::get(ITy, V,
isSigned,
true));
548 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
550 SCEV *S =
new (SCEVAllocator)
SCEVVScale(ID.Intern(SCEVAllocator), Ty);
551 UniqueSCEVs.InsertNode(S, IP);
572 "Must be a non-bit-width-changing pointer-to-integer cast!");
584 "Cannot truncate non-integer value!");
591 "Cannot zero extend non-integer value!");
598 "Cannot sign extend non-integer value!");
603 SE->forgetMemoizedResults({
this});
606 SE->UniqueSCEVs.RemoveNode(
this);
612void SCEVUnknown::allUsesReplacedWith(
Value *New) {
614 SE->forgetMemoizedResults({
this});
617 SE->UniqueSCEVs.RemoveNode(
this);
639 if (LIsPointer != RIsPointer)
640 return (
int)LIsPointer - (int)RIsPointer;
645 return (
int)LID - (int)RID;
650 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
651 return (
int)LArgNo - (int)RArgNo;
657 if (
auto L = LGV->getLinkage() - RGV->getLinkage())
660 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
661 auto LT = GV->getLinkage();
668 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
669 return LGV->getName().compare(RGV->getName());
680 if (LParent != RParent) {
683 if (LDepth != RDepth)
684 return (
int)LDepth - (int)RDepth;
688 unsigned LNumOps = LInst->getNumOperands(),
689 RNumOps = RInst->getNumOperands();
690 if (LNumOps != RNumOps)
691 return (
int)LNumOps - (int)RNumOps;
693 for (
unsigned Idx :
seq(LNumOps)) {
695 RInst->getOperand(Idx),
Depth + 1);
709static std::optional<int>
719 return (
int)LType - (int)RType;
744 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
745 if (LBitWidth != RBitWidth)
746 return (
int)LBitWidth - (int)RBitWidth;
747 return LA.
ult(
RA) ? -1 : 1;
753 return LTy->getBitWidth() - RTy->getBitWidth();
764 if (LLoop != RLoop) {
766 assert(LHead != RHead &&
"Two loops share the same header?");
770 "No dominance between recurrences used by one SCEV?");
793 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
794 if (LNumOps != RNumOps)
795 return (
int)LNumOps - (int)RNumOps;
797 for (
unsigned i = 0; i != LNumOps; ++i) {
823 if (
Ops.size() < 2)
return;
828 return Complexity && *Complexity < 0;
830 if (
Ops.size() == 2) {
834 if (IsLessComplex(
RHS,
LHS))
847 for (
unsigned i = 0, e =
Ops.size(); i != e-2; ++i) {
853 for (
unsigned j = i+1; j != e &&
Ops[j]->getSCEVType() == Complexity; ++j) {
858 if (i == e-2)
return;
880template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
884 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
886 for (
unsigned Idx = 0; Idx <
Ops.size();) {
894 Ops.erase(
Ops.begin() + Idx);
901 assert(Folded &&
"Must have folded value");
905 if (Folded && IsAbsorber(Folded->
getAPInt()))
909 if (Folded && !IsIdentity(Folded->
getAPInt()))
910 Ops.insert(
Ops.begin(), Folded);
912 return Ops.size() == 1 ?
Ops[0] :
nullptr;
987 APInt OddFactorial(W, 1);
989 for (
unsigned i = 3; i <= K; ++i) {
992 OddFactorial *= (i >> TwoFactors);
996 unsigned CalculationBits = W +
T;
1010 for (
unsigned i = 1; i != K; ++i) {
1043 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1072 ConversionFn CreatePtrCast;
1076 ConversionFn CreatePtrCast)
1077 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
1080 Type *TargetTy, ConversionFn CreatePtrCast) {
1082 return Rewriter.visit(Scev);
1118 "Should only reach pointer-typed SCEVUnknown's.");
1123 return SE.getZero(TargetTy);
1124 return CreatePtrCast(Expr);
1129 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1133 if (DL.hasUnstableRepresentation(
Op->getType()))
1136 Type *Ty = DL.getAddressType(
Op->getType());
1147 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
1149 SCEV *S =
new (SCEVAllocator)
1151 UniqueSCEVs.InsertNode(S, IP);
1154 return static_cast<const SCEV *
>(S);
1157 "We must have succeeded in sinking the cast, "
1158 "and ending up with an integer-typed expression!");
1165 "This is not a truncating conversion!");
1167 "This is not a conversion to a SCEVable type!");
1168 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1176 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1198 UniqueSCEVs.InsertNode(S, IP);
1211 unsigned numTruncs = 0;
1212 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1220 if (numTruncs < 2) {
1230 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
1237 for (
const SCEV *
Op : AddRec->operands())
1252 UniqueSCEVs.InsertNode(S, IP);
1293struct ExtendOpTraitsBase {
1294 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
const SCEV *,
Type *,
1299template <
typename ExtendOp>
struct ExtendOpTraits {
1315 static const GetExtendExprTy GetExtendExpr;
1317 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1318 ICmpInst::Predicate *Pred,
1319 ScalarEvolution *SE) {
1324const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1331 static const GetExtendExprTy GetExtendExpr;
1333 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1334 ICmpInst::Predicate *Pred,
1335 ScalarEvolution *SE) {
1340const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1352template <
typename ExtendOpTy>
1355 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1356 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1372 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1385 auto PreStartFlags =
1403 const SCEV *OperandExtendedStart =
1405 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1406 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1418 const SCEV *OverflowLimit =
1419 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1421 if (OverflowLimit &&
1429template <
typename ExtendOpTy>
1433 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1441 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1476template <
typename ExtendOpTy>
1477bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1480 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1490 APInt StartAI = StartC->
getAPInt();
1492 for (
unsigned Delta : {-2, -1, 1, 2}) {
1493 const SCEV *PreStart =
getConstant(StartAI - Delta);
1495 FoldingSetNodeID
ID;
1497 ID.AddPointer(PreStart);
1498 ID.AddPointer(Step);
1502 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
1506 if (PreAR &&
any(PreAR->getNoWrapFlags(WrapType))) {
1509 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1510 DeltaS, &Pred,
this);
1528 const unsigned BitWidth =
C.getBitWidth();
1546 const APInt &ConstantStart,
1561 auto I = FoldCache.
insert({ID, S});
1565 auto &UserIDs = FoldCacheUser[
I.first->second];
1566 assert(
count(UserIDs, ID) == 1 &&
"unexpected duplicates in UserIDs");
1567 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1568 if (UserIDs[
I] == ID) {
1573 I.first->second = S;
1575 FoldCacheUser[S].push_back(ID);
1581 "This is not an extending conversion!");
1583 "This is not a conversion to a SCEVable type!");
1584 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1588 if (
const SCEV *S = FoldCache.lookup(ID))
1600 "This is not an extending conversion!");
1602 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1614 const SCEV *Start, *Step;
1619 if (AR->hasNoUnsignedWrap()) {
1633 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1637 UniqueSCEVs.InsertNode(S, IP);
1647 const SCEV *
X = ST->getOperand();
1680 const SCEV *CastedMaxBECount =
1684 if (MaxBECount == RecastedMaxBECount) {
1693 const SCEV *WideMaxBECount =
1695 const SCEV *OperandExtendedAdd =
1701 if (ZAdd == OperandExtendedAdd) {
1712 OperandExtendedAdd =
1718 if (ZAdd == OperandExtendedAdd) {
1739 !AC.assumptions().empty()) {
1741 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1743 if (AR->hasNoUnsignedWrap()) {
1778 const APInt &
C = SC->getAPInt();
1782 const SCEV *SResidual =
1790 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1814 if (SA->hasNoUnsignedWrap()) {
1827 if (SA->hasNoSignedWrap() &&
1830 C->isNegative() && !
C->isMinSignedValue() && C2->
sge(
C->abs())) {
1849 const SCEV *SResidual =
1860 if (
SM->hasNoUnsignedWrap()) {
1882 const SCEV *TruncRHS;
1919 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1922 UniqueSCEVs.InsertNode(S, IP);
1931 "This is not an extending conversion!");
1933 "This is not a conversion to a SCEVable type!");
1934 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1938 if (
const SCEV *S = FoldCache.lookup(ID))
1950 "This is not an extending conversion!");
1952 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1969 const SCEV *Start, *Step;
1974 if (AR->hasNoSignedWrap()) {
1988 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1993 UniqueSCEVs.InsertNode(S, IP);
2003 const SCEV *
X = ST->getOperand();
2014 if (SA->hasNoSignedWrap()) {
2036 const SCEV *SResidual =
2069 const SCEV *CastedMaxBECount =
2073 if (MaxBECount == RecastedMaxBECount) {
2082 const SCEV *WideMaxBECount =
2084 const SCEV *OperandExtendedAdd =
2090 if (SAdd == OperandExtendedAdd) {
2101 OperandExtendedAdd =
2107 if (SAdd == OperandExtendedAdd) {
2127 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2129 if (AR->hasNoSignedWrap()) {
2143 const APInt &
C = SC->getAPInt();
2147 const SCEV *SResidual =
2155 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2182 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
2185 UniqueSCEVs.InsertNode(S, IP);
2202 assert(Expr->
getType() == Ty &&
"requested type must match");
2215 "This is not an extending conversion!");
2217 "This is not a conversion to a SCEVable type!");
2222 if (SC->getAPInt().isNegative())
2227 const SCEV *NewOp =
T->getOperand();
2246 for (
const SCEV *
Op : AR->operands())
2284 APInt &AccumulatedConstant,
2288 bool Interesting =
false;
2295 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2297 AccumulatedConstant += Scale *
C->getAPInt();
2302 for (; i !=
Ops.size(); ++i) {
2311 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2317 auto Pair = M.insert({
Key, NewScale});
2321 Pair.first->second += NewScale;
2329 auto Pair = M.insert({
Ops[i], Scale});
2333 Pair.first->second += Scale;
2352 case Instruction::Add:
2355 case Instruction::Sub:
2358 case Instruction::Mul:
2372 const SCEV *
A = (this->*Extension)(
2374 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2375 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2383 if (BinOp == Instruction::Mul)
2389 APInt C = RHSC->getAPInt();
2390 unsigned NumBits =
C.getBitWidth();
2391 bool IsSub = (BinOp == Instruction::Sub);
2392 bool IsNegativeConst = (
Signed &&
C.isNegative());
2394 bool OverflowDown = IsSub ^ IsNegativeConst;
2396 if (IsNegativeConst) {
2409 APInt Limit = Min + Magnitude;
2415 APInt Limit = Max - Magnitude;
2420std::optional<SCEV::NoWrapFlags>
2425 return std::nullopt;
2434 bool Deduced =
false;
2440 bool CanUseNSW =
true;
2441 const APInt *ShiftAmt;
2446 return std::nullopt;
2450 Opcode = Instruction::Mul;
2452 }
else if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
2453 Opcode != Instruction::Mul) {
2454 return std::nullopt;
2473 return std::nullopt;
2483 using namespace std::placeholders;
2490 assert(CanAnalyze &&
"don't call from other places!");
2497 auto IsKnownNonNegative = [&](
SCEVUse U) {
2506 if (SignOrUnsignWrap != SignOrUnsignMask &&
2513 return Instruction::Add;
2515 return Instruction::Mul;
2526 Opcode,
C, OBO::NoSignedWrap);
2534 Opcode,
C, OBO::NoUnsignedWrap);
2544 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2551 if (UDiv->getOperand(1) ==
Ops[1])
2554 if (UDiv->getOperand(1) ==
Ops[0])
2570 "only nuw or nsw allowed");
2571 assert(!
Ops.empty() &&
"Cannot get empty add!");
2572 if (
Ops.size() == 1)
return Ops[0];
2575 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2577 "SCEVAddExpr operand types don't match!");
2579 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2580 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2585 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2586 [](
const APInt &
C) {
return C.isZero(); },
2587 [](
const APInt &
C) {
return false; });
2600 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2605 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2606 Add->setNoWrapFlags(ComputeFlags(
Ops));
2614 bool FoundMatch =
false;
2615 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2616 if (
Ops[i] ==
Ops[i+1]) {
2628 --i; e -=
Count - 1;
2638 auto FindTruncSrcType = [&]() ->
Type * {
2644 return T->getOperand()->getType();
2646 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2648 return T->getOperand()->getType();
2652 if (
auto *SrcType = FindTruncSrcType()) {
2659 if (
T->getOperand()->getType() != SrcType) {
2668 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2671 if (
T->getOperand()->getType() != SrcType) {
2699 if (
Ops.size() == 2) {
2709 auto C2 =
C->getAPInt();
2712 APInt ConstAdd = C1 + C2;
2713 auto AddFlags = AddExpr->getNoWrapFlags();
2754 if (
Ops.size() == 2 &&
2765 if (Idx <
Ops.size()) {
2766 bool DeletedAdd =
false;
2777 Ops.erase(
Ops.begin()+Idx);
2780 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2803 struct APIntCompare {
2804 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2805 return LHS.ult(RHS);
2812 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2813 for (
const SCEV *NewOp : NewOps)
2814 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2817 if (AccumulatedConstant != 0)
2819 for (
auto &MulOp : MulOpLists) {
2820 if (MulOp.first == 1) {
2822 }
else if (MulOp.first != 0) {
2831 if (
Ops.size() == 1)
2840 if (M->getNumOperands() == 2)
2841 return M->getOperand(
OpIdx == 0);
2852 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2856 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2864 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp) {
2865 if (MulOpSCEV ==
Ops[AddOp]) {
2876 for (
unsigned OMulOp = 0, OE = OtherMul->
getNumOperands(); OMulOp != OE;
2878 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2880 Cofactors.
push_back(StripFactor(OtherMul, OMulOp));
2889 if (!Cofactors.
empty()) {
2897 if (
Ops.size() == DeadIndices.
size() + 1)
2904 Ops.erase(
Ops.begin() + Idx);
2908 Ops.push_back(OuterMul);
2927 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2930 Ops.erase(
Ops.begin()+i);
2935 if (!LIOps.
empty()) {
2960 auto *DefI = getDefiningScopeBound(LIOps);
2962 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2974 if (
Ops.size() == 1)
return NewRec;
2977 for (
unsigned i = 0;; ++i)
2978 if (
Ops[i] == AddRec) {
2988 for (
unsigned OtherIdx = Idx+1;
2996 "AddRecExprs are not sorted in reverse dominance order?");
3003 if (OtherAddRec->getLoop() == AddRecLoop) {
3004 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
3006 if (i >= AddRecOps.
size()) {
3007 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
3011 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
3014 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3029 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
3040 static_cast<SCEVAddExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
3044 S =
new (SCEVAllocator)
3046 UniqueSCEVs.InsertNode(S, IP);
3057 FoldingSetNodeID
ID;
3059 for (
const SCEV *
Op :
Ops)
3064 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
3068 S =
new (SCEVAllocator)
3069 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3070 UniqueSCEVs.InsertNode(S, IP);
3072 LoopUsers[
L].push_back(S);
3081 FoldingSetNodeID
ID;
3083 for (
const SCEV *
Op :
Ops)
3087 static_cast<SCEVMulExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
3091 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3093 UniqueSCEVs.InsertNode(S, IP);
3103 if (j > 1 && k / j != i) Overflow =
true;
3119 if (n == 0 || n == k)
return 1;
3120 if (k > n)
return 0;
3126 for (
uint64_t i = 1; i <= k; ++i) {
3127 r =
umul_ov(r, n-(i-1), Overflow);
3136 struct FindConstantInAddMulChain {
3137 bool FoundConstant =
false;
3139 bool follow(
const SCEV *S) {
3144 bool isDone()
const {
3145 return FoundConstant;
3149 FindConstantInAddMulChain
F;
3151 ST.visitAll(StartExpr);
3152 return F.FoundConstant;
3160 "only nuw or nsw allowed");
3161 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3162 if (
Ops.size() == 1)
return Ops[0];
3164 Type *ETy =
Ops[0]->getType();
3166 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3168 "SCEVMulExpr operand types don't match!");
3173 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3174 [](
const APInt &
C) {
return C.isOne(); },
3175 [](
const APInt &
C) {
return C.isZero(); });
3186 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3191 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3192 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3197 if (
Ops.size() == 2) {
3205 const SCEV *Op0, *Op1;
3213 if (
Ops[0]->isAllOnesValue()) {
3218 bool AnyFolded =
false;
3219 for (
const SCEV *AddOp :
Add->operands()) {
3239 if (AddRec->hasNoSignedWrap()) {
3246 AddRec->getNoWrapFlags(FlagsMask));
3269 APInt C1V = LHSC->getAPInt();
3279 const SCEV *NewMul =
nullptr;
3283 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3298 if (Idx <
Ops.size()) {
3299 bool DeletedMul =
false;
3305 Ops.erase(
Ops.begin()+Idx);
3329 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3332 Ops.erase(
Ops.begin()+i);
3337 if (!LIOps.
empty()) {
3350 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3366 if (
Ops.size() == 1)
return NewRec;
3369 for (
unsigned i = 0;; ++i)
3370 if (
Ops[i] == AddRec) {
3391 bool OpsModified =
false;
3392 for (
unsigned OtherIdx = Idx+1;
3406 bool Overflow =
false;
3413 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3417 z < ze && !Overflow; ++z) {
3420 if (LargerThan64Bits)
3421 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3423 Coeff = Coeff1*Coeff2;
3438 if (
Ops.size() == 2)
return NewAddRec;
3439 Ops[Idx] = NewAddRec;
3440 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3456 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3463 "SCEVURemExpr operand types don't match!");
3468 if (RHSC->getValue()->isOne())
3469 return getZero(LHS->getType());
3472 if (RHSC->getAPInt().isPowerOf2()) {
3473 Type *FullTy = LHS->getType();
3489 assert(!LHS->getType()->isPointerTy() &&
3490 "SCEVUDivExpr operand can't be pointer!");
3491 assert(LHS->getType() == RHS->getType() &&
3492 "SCEVUDivExpr operand types don't match!");
3499 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
3507 if (RHSC->getValue()->isOne())
3512 if (!RHSC->getValue()->isZero()) {
3516 Type *Ty = LHS->getType();
3517 unsigned LZ = RHSC->getAPInt().countl_zero();
3521 if (!RHSC->getAPInt().isPowerOf2())
3529 const APInt &StepInt = Step->getAPInt();
3530 const APInt &DivInt = RHSC->getAPInt();
3531 if (!StepInt.
urem(DivInt) &&
3537 for (
const SCEV *
Op : AR->operands())
3543 const APInt *StartRem;
3556 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3560 const SCEV *NewStart =
3562 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3564 const SCEV *NewLHS =
3567 if (LHS != NewLHS) {
3577 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
3586 for (
const SCEV *
Op : M->operands())
3590 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3591 const SCEV *
Op = M->getOperand(i);
3618 if (
auto *DivisorConstant =
3620 bool Overflow =
false;
3622 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3633 for (
const SCEV *
Op :
A->operands())
3637 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3644 if (Operands.
size() ==
A->getNumOperands())
3656 const APInt &
N = RHSC->getAPInt();
3657 const APInt *NMinusM, *M;
3661 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3662 *NMinusM ==
N - *M) {
3671 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3681 return getZero(LHS->getType());
3685 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3686 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3687 if (
Mul->getOperand(i) == RHS) {
3698 const SCEV *NewLHS, *NewRHS;
3706 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
3709 UniqueSCEVs.InsertNode(S, IP);
3746 if (StepChrec->getLoop() == L) {
3760 if (Operands.
size() == 1)
return Operands[0];
3765 "SCEVAddRecExpr operand types don't match!");
3766 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3768 for (
const SCEV *
Op : Operands)
3770 "SCEVAddRecExpr operand is not available at loop entry!");
3773 if (Operands.
back()->isZero()) {
3788 const Loop *NestedLoop = NestedAR->getLoop();
3789 if (L->contains(NestedLoop)
3792 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3794 Operands[0] = NestedAR->getStart();
3798 bool AllInvariant =
all_of(
3810 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3821 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3825 Operands[0] = NestedAR;
3831 return getOrCreateAddRecExpr(Operands, L, Flags);
3847 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3851 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3865 bool FirstIter =
true;
3867 for (
SCEVUse IndexExpr : IndexExprs) {
3874 Offsets.push_back(FieldOffset);
3877 CurTy = STy->getTypeAtIndex(Index);
3882 "The first index of a GEP indexes a pointer");
3883 CurTy = SrcElementTy;
3894 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3895 Offsets.push_back(LocalOffset);
3900 if (Offsets.empty())
3913 "GEP should not change type mid-flight.");
3917SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3924 return UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
3927SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3934 return UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
3944 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3945 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3946 if (
Ops.size() == 1)
return Ops[0];
3949 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3951 "Operand types don't match!");
3954 "min/max should be consistently pointerish");
3980 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3982 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3987 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3989 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3995 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
4001 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
4006 if (Idx <
Ops.size()) {
4007 bool DeletedAny =
false;
4008 while (
Ops[Idx]->getSCEVType() == Kind) {
4010 Ops.erase(
Ops.begin()+Idx);
4028 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
4029 if (
Ops[i] ==
Ops[i + 1] ||
4030 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
4033 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
4036 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
4039 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
4045 if (
Ops.size() == 1)
return Ops[0];
4047 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
4056 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
4058 return ExistingSCEV;
4061 SCEV *S =
new (SCEVAllocator)
4064 UniqueSCEVs.InsertNode(S, IP);
4072class SCEVSequentialMinMaxDeduplicatingVisitor final
4073 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4074 std::optional<const SCEV *>> {
4075 using RetVal = std::optional<const SCEV *>;
4083 bool canRecurseInto(
SCEVTypes Kind)
const {
4086 return RootKind == Kind || NonSequentialRootKind == Kind;
4089 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
4091 "Only for min/max expressions.");
4094 if (!canRecurseInto(Kind))
4104 return std::nullopt;
4111 RetVal
visit(
const SCEV *S) {
4113 if (!SeenOps.
insert(S).second)
4114 return std::nullopt;
4115 return Base::visit(S);
4119 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4121 : SE(SE), RootKind(RootKind),
4122 NonSequentialRootKind(
4123 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4127 SmallVectorImpl<SCEVUse> &NewOps) {
4132 for (
const SCEV *
Op : OrigOps) {
4137 Ops.emplace_back(*NewOp);
4141 NewOps = std::move(
Ops);
4145 RetVal visitConstant(
const SCEVConstant *Constant) {
return Constant; }
4147 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4149 RetVal visitPtrToAddrExpr(
const SCEVPtrToAddrExpr *Expr) {
return Expr; }
4151 RetVal visitTruncateExpr(
const SCEVTruncateExpr *Expr) {
return Expr; }
4153 RetVal visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
return Expr; }
4155 RetVal visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
return Expr; }
4157 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4159 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4161 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4163 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4165 RetVal visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
4166 return visitAnyMinMaxExpr(Expr);
4169 RetVal visitUMaxExpr(
const SCEVUMaxExpr *Expr) {
4170 return visitAnyMinMaxExpr(Expr);
4173 RetVal visitSMinExpr(
const SCEVSMinExpr *Expr) {
4174 return visitAnyMinMaxExpr(Expr);
4177 RetVal visitUMinExpr(
const SCEVUMinExpr *Expr) {
4178 return visitAnyMinMaxExpr(Expr);
4181 RetVal visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *Expr) {
4182 return visitAnyMinMaxExpr(Expr);
4185 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4187 RetVal visitCouldNotCompute(
const SCEVCouldNotCompute *Expr) {
return Expr; }
4229struct SCEVPoisonCollector {
4230 bool LookThroughMaybePoisonBlocking;
4231 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4232 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4233 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4235 bool follow(
const SCEV *S) {
4236 if (!LookThroughMaybePoisonBlocking &&
4246 bool isDone()
const {
return false; }
4256 SCEVPoisonCollector PC1(
true);
4261 if (PC1.MaybePoison.empty())
4267 SCEVPoisonCollector PC2(
false);
4277 SCEVPoisonCollector PC(
false);
4300 while (!Worklist.
empty()) {
4302 if (!Visited.
insert(V).second)
4306 if (Visited.
size() > 16)
4322 if (PDI->isDisjoint())
4329 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4336 if (
I->hasPoisonGeneratingAnnotations())
4347 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4348 "Not a SCEVSequentialMinMaxExpr!");
4349 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4350 if (
Ops.size() == 1)
4354 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4356 "Operand types don't match!");
4359 "min/max should be consistently pointerish");
4367 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4374 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4384 bool DeletedAny =
false;
4385 while (Idx <
Ops.size()) {
4386 if (
Ops[Idx]->getSCEVType() != Kind) {
4391 Ops.erase(
Ops.begin() + Idx);
4392 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4393 SMME->operands().end());
4401 const SCEV *SaturationPoint;
4412 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4413 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4425 Ops.erase(
Ops.begin() + i);
4430 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4431 Ops.erase(
Ops.begin() + i);
4443 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
4445 return ExistingSCEV;
4449 SCEV *S =
new (SCEVAllocator)
4452 UniqueSCEVs.InsertNode(S, IP);
4500 if (
Size.isScalable())
4521 "Cannot get offset for structure containing scalable vector types");
4535 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) {
4537 "Stale SCEVUnknown in uniquing map!");
4540 SCEV *S =
new (SCEVAllocator)
SCEVUnknown(ID.Intern(SCEVAllocator), V,
this,
4543 UniqueSCEVs.InsertNode(S, IP);
4558 return Ty->isIntOrPtrTy();
4565 if (Ty->isPointerTy())
4576 if (Ty->isIntegerTy())
4580 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4592 bool PreciseA, PreciseB;
4593 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4594 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4595 if (!PreciseA || !PreciseB)
4598 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4599 DT.dominates(ScopeB, ScopeA);
4603 return CouldNotCompute.get();
4606bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4609 return SU && SU->getValue() ==
nullptr;
4612 return !ContainsNulls;
4617 if (
I != HasRecMap.end())
4622 HasRecMap.insert({S, FoundAddRec});
4630 if (
SI == ExprValueMap.
end())
4632 return SI->second.getArrayRef();
4638void ScalarEvolution::eraseValueFromMap(
Value *V) {
4640 if (
I != ValueExprMap.end()) {
4641 auto EVIt = ExprValueMap.find(
I->second);
4642 bool Removed = EVIt->second.remove(V);
4644 assert(Removed &&
"Value not in ExprValueMap?");
4645 ValueExprMap.erase(
I);
4649void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4653 auto It = ValueExprMap.find_as(V);
4654 if (It == ValueExprMap.end()) {
4656 ExprValueMap[S].insert(V);
4667 return createSCEVIter(V);
4674 if (
I != ValueExprMap.end()) {
4675 const SCEV *S =
I->second;
4676 assert(checkValidity(S) &&
4677 "existing SCEV has not been properly invalidated");
4690 Type *Ty = V->getType();
4706 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4719 return (
const SCEV *)
nullptr;
4725 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4729 Type *Ty = V->getType();
4735 assert(
P->getType()->isPointerTy());
4750 if (AddOp->getType()->isPointerTy()) {
4751 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4769 return getZero(LHS->getType());
4774 if (RHS->getType()->isPointerTy()) {
4775 if (!LHS->getType()->isPointerTy() ||
4785 const bool RHSIsNotMinSigned =
4816 Type *SrcTy = V->getType();
4817 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4818 "Cannot truncate or zero extend with non-integer arguments!");
4828 Type *SrcTy = V->getType();
4829 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4830 "Cannot truncate or zero extend with non-integer arguments!");
4840 Type *SrcTy = V->getType();
4841 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4842 "Cannot noop or zero extend with non-integer arguments!");
4844 "getNoopOrZeroExtend cannot truncate!");
4852 Type *SrcTy = V->getType();
4853 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4854 "Cannot noop or sign extend with non-integer arguments!");
4856 "getNoopOrSignExtend cannot truncate!");
4864 Type *SrcTy = V->getType();
4865 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4866 "Cannot noop or any extend with non-integer arguments!");
4868 "getNoopOrAnyExtend cannot truncate!");
4876 Type *SrcTy = V->getType();
4877 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4878 "Cannot truncate or noop with non-integer arguments!");
4880 "getTruncateOrNoop cannot extend!");
4888 const SCEV *PromotedLHS = LHS;
4889 const SCEV *PromotedRHS = RHS;
4909 assert(!
Ops.empty() &&
"At least one operand must be!");
4911 if (
Ops.size() == 1)
4915 Type *MaxType =
nullptr;
4921 assert(MaxType &&
"Failed to find maximum type!");
4934 if (!V->getType()->isPointerTy())
4939 V = AddRec->getStart();
4941 const SCEV *PtrOp =
nullptr;
4942 for (
const SCEV *AddOp :
Add->operands()) {
4943 if (AddOp->getType()->isPointerTy()) {
4944 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4948 assert(PtrOp &&
"Must have pointer op");
4960 for (
User *U :
I->users()) {
4962 if (Visited.
insert(UserInsn).second)
4976 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4977 bool IgnoreOtherLoops =
true) {
4980 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4982 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4987 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4989 SeenLoopVariantSCEVUnknown =
true;
4993 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4997 SeenOtherLoops =
true;
5001 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
5003 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
5006 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
5007 : SCEVRewriteVisitor(SE),
L(
L) {}
5010 bool SeenLoopVariantSCEVUnknown =
false;
5011 bool SeenOtherLoops =
false;
5020 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
5021 SCEVPostIncRewriter
Rewriter(L, SE);
5023 return Rewriter.hasSeenLoopVariantSCEVUnknown()
5028 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5030 SeenLoopVariantSCEVUnknown =
true;
5034 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5038 SeenOtherLoops =
true;
5042 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
5044 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
5047 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
5048 : SCEVRewriteVisitor(SE),
L(
L) {}
5051 bool SeenLoopVariantSCEVUnknown =
false;
5052 bool SeenOtherLoops =
false;
5058class SCEVBackedgeConditionFolder
5061 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5062 ScalarEvolution &SE) {
5063 bool IsPosBECond =
false;
5064 Value *BECond =
nullptr;
5065 if (BasicBlock *Latch =
L->getLoopLatch()) {
5067 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
5068 "Both outgoing branches should not target same header!");
5069 BECond = BI->getCondition();
5070 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
5075 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
5079 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5080 const SCEV *
Result = Expr;
5085 switch (
I->getOpcode()) {
5086 case Instruction::Select: {
5088 std::optional<const SCEV *> Res =
5089 compareWithBackedgeCondition(
SI->getCondition());
5097 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5108 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5109 bool IsPosBECond, ScalarEvolution &SE)
5110 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5111 IsPositiveBECond(IsPosBECond) {}
5113 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5117 Value *BackedgeCond =
nullptr;
5119 bool IsPositiveBECond;
5122std::optional<const SCEV *>
5123SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5128 if (BackedgeCond == IC)
5131 return std::nullopt;
5136 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5137 ScalarEvolution &SE) {
5143 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5150 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5160 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5161 : SCEVRewriteVisitor(SE),
L(
L) {}
5169void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5185 const APInt &BECountAP = BECountMax->getAPInt();
5186 unsigned NoOverflowBitWidth =
5195ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5205 if (!SignedWrapViaInductionTried.insert(AR).second)
5230 AC.assumptions().empty())
5238 const SCEV *OverflowLimit =
5240 if (OverflowLimit &&
5248ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5258 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5284 AC.assumptions().empty())
5323 IsNSW = OBO->hasNoSignedWrap();
5324 IsNUW = OBO->hasNoUnsignedWrap();
5330 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5342 return std::nullopt;
5348 switch (
Op->getOpcode()) {
5349 case Instruction::Add:
5350 case Instruction::Sub:
5351 case Instruction::Mul:
5352 case Instruction::UDiv:
5353 case Instruction::URem:
5354 case Instruction::And:
5355 case Instruction::AShr:
5356 case Instruction::Shl:
5359 case Instruction::Or: {
5362 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5372 case Instruction::Xor:
5376 if (RHSC->getValue().isSignMask())
5377 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5379 if (V->getType()->isIntegerTy(1))
5380 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5383 case Instruction::LShr:
5392 if (SA->getValue().ult(
BitWidth)) {
5394 ConstantInt::get(SA->getContext(),
5396 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5401 case Instruction::ExtractValue: {
5403 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5411 bool Signed = WO->isSigned();
5414 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5419 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5430 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5431 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5433 return std::nullopt;
5459 if (
Op == SymbolicPHI)
5464 if (SourceBits != NewBits)
5482 if (!L || L->getHeader() != PN->
getParent())
5540std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5541ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5549 assert(L &&
"Expecting an integer loop header phi");
5554 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5555 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5556 Value *
V = PN->getIncomingValue(i);
5557 if (
L->contains(PN->getIncomingBlock(i))) {
5560 }
else if (BEValueV != V) {
5564 }
else if (!StartValueV) {
5566 }
else if (StartValueV != V) {
5567 StartValueV =
nullptr;
5571 if (!BEValueV || !StartValueV)
5572 return std::nullopt;
5574 const SCEV *BEValue =
getSCEV(BEValueV);
5581 return std::nullopt;
5585 unsigned FoundIndex =
Add->getNumOperands();
5586 Type *TruncTy =
nullptr;
5588 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5591 if (FoundIndex == e) {
5596 if (FoundIndex ==
Add->getNumOperands())
5597 return std::nullopt;
5601 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5602 if (i != FoundIndex)
5603 Ops.push_back(
Add->getOperand(i));
5609 return std::nullopt;
5662 const SCEV *StartVal =
getSCEV(StartValueV);
5663 const SCEV *PHISCEV =
5690 auto getExtendedExpr = [&](
const SCEV *Expr,
5691 bool CreateSignExtend) ->
const SCEV * {
5694 const SCEV *ExtendedExpr =
5697 return ExtendedExpr;
5705 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5706 const SCEV *ExtendedExpr) ->
bool {
5707 return Expr != ExtendedExpr &&
5711 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5712 if (PredIsKnownFalse(StartVal, StartExtended)) {
5714 return std::nullopt;
5719 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5720 if (PredIsKnownFalse(Accum, AccumExtended)) {
5722 return std::nullopt;
5725 auto AppendPredicate = [&](
const SCEV *Expr,
5726 const SCEV *ExtendedExpr) ->
void {
5727 if (Expr != ExtendedExpr &&
5735 AppendPredicate(StartVal, StartExtended);
5736 AppendPredicate(Accum, AccumExtended);
5744 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5745 std::make_pair(NewAR, Predicates);
5747 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5751std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5756 return std::nullopt;
5759 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5760 if (
I != PredicatedSCEVRewrites.end()) {
5761 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5764 if (Rewrite.first == SymbolicPHI)
5765 return std::nullopt;
5769 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5773 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5774 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5779 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5780 return std::nullopt;
5800 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5801 if (Expr1 != Expr2 &&
5802 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5803 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5820const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5822 Value *StartValueV) {
5825 assert(BEValueV && StartValueV);
5831 if (BO->Opcode != Instruction::Add)
5834 const SCEV *Accum =
nullptr;
5835 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5837 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5851 insertValueToMap(PN, PHISCEV);
5854 inferNoWrapViaConstantRanges(AR);
5861 "Accum is defined outside L, but is not invariant?");
5862 if (isAddRecNeverPoison(BEInst, L))
5869const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5870 const Loop *
L = LI.getLoopFor(PN->
getParent());
5877 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5883 }
else if (BEValueV != V) {
5887 }
else if (!StartValueV) {
5889 }
else if (StartValueV != V) {
5890 StartValueV =
nullptr;
5894 if (!BEValueV || !StartValueV)
5897 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5898 "PHI node already processed?");
5902 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5907 insertValueToMap(PN, SymbolicName);
5911 const SCEV *BEValue =
getSCEV(BEValueV);
5921 unsigned FoundIndex =
Add->getNumOperands();
5922 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5923 if (
Add->getOperand(i) == SymbolicName)
5924 if (FoundIndex == e) {
5929 if (FoundIndex !=
Add->getNumOperands()) {
5932 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5933 if (i != FoundIndex)
5934 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5946 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5953 if (
GEP->getOperand(0) == PN) {
5954 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
5972 const SCEV *StartVal =
getSCEV(StartValueV);
5973 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5978 forgetMemoizedResults({SymbolicName});
5979 insertValueToMap(PN, PHISCEV);
5982 inferNoWrapViaConstantRanges(AR);
6006 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
6007 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
6009 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
6010 const SCEV *StartVal =
getSCEV(StartValueV);
6011 if (Start == StartVal) {
6015 forgetMemoizedResults({SymbolicName});
6016 insertValueToMap(PN, Shifted);
6026 eraseValueFromMap(PN);
6041 Use &LeftUse =
Merge->getOperandUse(0);
6042 Use &RightUse =
Merge->getOperandUse(1);
6078 assert(IDom &&
"At least the entry block should dominate PN");
6086const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
6091 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6108 CommonInst = IncomingInst;
6124ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6130 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6131 bool SCEVExprsIdentical =
6133 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6134 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6137const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6138 if (
const SCEV *S = createAddRecFromPHI(PN))
6148 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6151 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6160 struct FindClosure {
6161 const SCEV *OperandToFind;
6167 bool canRecurseInto(
SCEVTypes Kind)
const {
6170 return RootKind == Kind || NonSequentialRootKind == Kind ||
6175 : OperandToFind(OperandToFind), RootKind(RootKind),
6176 NonSequentialRootKind(
6180 bool follow(
const SCEV *S) {
6181 Found = S == OperandToFind;
6183 return !isDone() && canRecurseInto(S->
getSCEVType());
6186 bool isDone()
const {
return Found; }
6189 FindClosure FC(OperandToFind, RootKind);
6194std::optional<const SCEV *>
6195ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6205 switch (ICI->getPredicate()) {
6219 bool Signed = ICI->isSigned();
6220 const SCEV *LA =
getSCEV(TrueVal);
6228 if (LA == LS &&
RA == RS)
6230 if (LA == RS &&
RA == LS)
6233 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6234 if (
Op->getType()->isPointerTy()) {
6245 LS = CoerceOperand(LS);
6246 RS = CoerceOperand(RS);
6270 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6271 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6285 X = ZExt->getOperand();
6287 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6298 return std::nullopt;
6301static std::optional<const SCEV *>
6303 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6307 "Unexpected operands of a select.");
6319 return std::nullopt;
6334static std::optional<const SCEV *>
6338 return std::nullopt;
6341 const auto *SETrue = SE->
getSCEV(TrueVal);
6342 const auto *SEFalse = SE->
getSCEV(FalseVal);
6346const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6348 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6350 V->getType() ==
TrueVal->getType() &&
6351 "Types of select hands and of the result must match.");
6354 if (!
V->getType()->isIntegerTy(1))
6357 if (std::optional<const SCEV *> S =
6370 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6374 if (std::optional<const SCEV *> S =
6375 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6381 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6387 assert(
GEP->getSourceElementType()->isSized() &&
6388 "GEP source element type must be sized");
6391 for (
Value *Index :
GEP->indices())
6396APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6399 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6402 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6404 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6407 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6425 return GetShiftedByZeros(TZ);
6435 return GetShiftedByZeros(TZ);
6439 if (
M->hasNoUnsignedWrap()) {
6442 for (
const SCEV *Operand :
M->operands().drop_front())
6450 for (
const SCEV *Operand :
M->operands())
6452 return GetShiftedByZeros(TZ);
6457 if (
N->hasNoUnsignedWrap())
6458 return GetGCDMultiple(
N);
6461 for (
const SCEV *Operand :
N->operands().drop_front())
6463 return GetShiftedByZeros(TZ);
6480 CtxI = &*F.getEntryBlock().begin();
6487 .allowEphemerals(
true))
6488 .countMinTrailingZeros();
6489 return GetShiftedByZeros(
Known);
6502 return getConstantMultipleImpl(S, CtxI);
6504 auto I = ConstantMultipleCache.find(S);
6505 if (
I != ConstantMultipleCache.end())
6508 APInt Result = getConstantMultipleImpl(S, CtxI);
6509 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6510 assert(InsertPair.second &&
"Should insert a new key");
6511 return InsertPair.first->second;
6528 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6531 if (std::optional<ConstantRange>
Range = CB->getRange())
6535 if (std::optional<ConstantRange>
Range =
A->getRange())
6538 return std::nullopt;
6545 UnsignedRanges.erase(AddRec);
6546 SignedRanges.erase(AddRec);
6547 ConstantMultipleCache.erase(AddRec);
6552getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6578 Value *Start, *Step;
6585 assert(L && L->getHeader() ==
P->getParent());
6598 case Instruction::AShr:
6599 case Instruction::LShr:
6600 case Instruction::Shl:
6615 KnownStep.getBitWidth() ==
BitWidth);
6618 auto MaxShiftAmt = KnownStep.getMaxValue();
6620 bool Overflow =
false;
6621 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6628 case Instruction::AShr: {
6636 if (KnownStart.isNonNegative())
6639 KnownStart.getMaxValue() + 1);
6640 if (KnownStart.isNegative())
6643 KnownEnd.getMaxValue() + 1);
6646 case Instruction::LShr: {
6655 KnownStart.getMaxValue() + 1);
6657 case Instruction::Shl: {
6661 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6662 return ConstantRange(KnownStart.getMinValue(),
6663 KnownEnd.getMaxValue() + 1);
6688 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6695ScalarEvolution::getRangeRefIter(
const SCEV *S,
6696 ScalarEvolution::RangeSignHint SignHint) {
6697 DenseMap<const SCEV *, ConstantRange> &Cache =
6698 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6701 SmallPtrSet<const SCEV *, 8> Seen;
6705 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6706 if (!Seen.
insert(Expr).second)
6739 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6740 const SCEV *
P = WorkList[
I];
6744 for (
const SCEV *
Op :
P->operands())
6757 if (!WorkList.
empty()) {
6762 getRangeRef(
P, SignHint);
6766 return getRangeRef(S, SignHint, 0);
6773 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6774 DenseMap<const SCEV *, ConstantRange> &Cache =
6775 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6782 auto I = Cache.
find(S);
6783 if (
I != Cache.
end())
6787 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6792 return getRangeRefIter(S, SignHint);
6795 ConstantRange ConservativeResult(
BitWidth,
true);
6796 using OBO = OverflowingBinaryOperator;
6800 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6804 ConservativeResult =
6811 ConservativeResult = ConstantRange(
6827 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6834 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6841 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6846 return setRange(Cast, SignHint,
X);
6851 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6852 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6854 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6855 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6856 ConservativeResult =
6857 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6859 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6860 unsigned WrapType = OBO::AnyWrap;
6861 if (
Add->hasNoSignedWrap())
6862 WrapType |= OBO::NoSignedWrap;
6863 if (
Add->hasNoUnsignedWrap())
6864 WrapType |= OBO::NoUnsignedWrap;
6866 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6868 return setRange(
Add, SignHint,
6869 ConservativeResult.intersectWith(
X, RangeType));
6873 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6875 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6876 return setRange(
Mul, SignHint,
6877 ConservativeResult.intersectWith(
X, RangeType));
6881 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6882 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6883 return setRange(UDiv, SignHint,
6884 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6892 if (!UnsignedMinValue.
isZero())
6893 ConservativeResult = ConservativeResult.intersectWith(
6894 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6903 bool AllNonNeg =
true;
6904 bool AllNonPos =
true;
6905 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6912 ConservativeResult = ConservativeResult.intersectWith(
6917 ConservativeResult = ConservativeResult.intersectWith(
6926 const SCEV *MaxBEScev =
6940 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6942 ConservativeResult =
6943 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6946 auto RangeFromFactoring = getRangeViaFactoring(
6948 ConservativeResult =
6949 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6955 const SCEV *SymbolicMaxBECount =
6960 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6961 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6962 ConservativeResult =
6963 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6968 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6978 ID = Intrinsic::umax;
6981 ID = Intrinsic::smax;
6985 ID = Intrinsic::umin;
6988 ID = Intrinsic::smin;
6995 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6996 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6998 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6999 return setRange(S, SignHint,
7000 ConservativeResult.intersectWith(
X, RangeType));
7009 ConservativeResult =
7010 ConservativeResult.intersectWith(*MDRange, RangeType);
7015 auto CR = getRangeForUnknownRecurrence(U);
7016 ConservativeResult = ConservativeResult.intersectWith(CR);
7027 if (
U->getType()->isPointerTy()) {
7030 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
7031 int ptrIdxDiff = ptrSize -
BitWidth;
7032 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
7038 if (!
Known.Zero.getHiBits(NS).isZero())
7039 Known.Zero.setHighBits(NS);
7040 if (!
Known.One.getHiBits(NS).isZero())
7041 Known.One.setHighBits(NS);
7044 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
7045 ConservativeResult = ConservativeResult.intersectWith(
7046 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
7049 ConservativeResult = ConservativeResult.intersectWith(
7054 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
7058 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
7059 DL, CanBeNull,
nullptr);
7069 uint64_t
Align =
U->getValue()->getPointerAlignment(DL).value();
7070 uint64_t Rem = MaxVal.
urem(Align);
7075 ConservativeResult = ConservativeResult.intersectWith(
7085 return getRangeRef(AR, SignHint,
Depth + 1);
7089 ConstantRange RangeFromOps(
BitWidth,
false);
7091 for (
const auto &
Op :
Phi->operands()) {
7093 RangeFromOps = RangeFromOps.unionWith(OpRange);
7095 if (RangeFromOps.isFullSet())
7098 ConservativeResult =
7099 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7105 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7107 ConservativeResult = ConservativeResult.difference(Disallowed);
7110 return setRange(U, SignHint, std::move(ConservativeResult));
7116 return setRange(S, SignHint, std::move(ConservativeResult));
7124static std::pair<ConstantRange, bool>
7132 if (Step == 0 || MaxBECount == 0)
7133 return {StartRange,
true};
7139 return {ConstantRange::getFull(
BitWidth),
false};
7155 return {ConstantRange::getFull(
BitWidth),
false};
7168 APInt MovedBoundary;
7173 MovedBoundary = StartLower - std::move(
Offset);
7176 MovedBoundary = StartUpper + std::move(
Offset);
7180 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7187 if (StartRange.
contains(MovedBoundary))
7188 return {ConstantRange::getFull(
BitWidth),
false};
7191 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7193 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7201std::pair<ConstantRange, SCEV::NoWrapFlags>
7202ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7203 const APInt &MaxBECount) {
7207 "mismatched bit widths");
7216 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7218 StartSRange, MaxBECount,
7220 ConstantRange SR = SR1.unionWith(SR2);
7237ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7239 ScalarEvolution::RangeSignHint SignHint) {
7240 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7242 "This only works for non-self-wrapping AddRecs!");
7243 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7247 return ConstantRange::getFull(
BitWidth);
7255 return ConstantRange::getFull(
BitWidth);
7259 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7261 MaxItersWithoutWrap))
7262 return ConstantRange::getFull(
BitWidth);
7283 ConstantRange StartRange = getRangeRef(Start, SignHint);
7284 ConstantRange EndRange = getRangeRef(End, SignHint);
7285 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7289 return RangeBetween;
7294 return ConstantRange::getFull(
BitWidth);
7297 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7298 return RangeBetween;
7300 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7301 return RangeBetween;
7302 return ConstantRange::getFull(
BitWidth);
7307 const APInt &MaxBECount) {
7314 "mismatched bit widths");
7316 struct SelectPattern {
7317 Value *Condition =
nullptr;
7321 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7323 std::optional<unsigned> CastOp;
7337 CastOp = SCast->getSCEVType();
7338 S = SCast->getOperand();
7341 using namespace llvm::PatternMatch;
7348 Condition =
nullptr;
7380 bool isRecognized() {
return Condition !=
nullptr; }
7383 SelectPattern StartPattern(*
this,
BitWidth, Start);
7384 if (!StartPattern.isRecognized())
7385 return ConstantRange::getFull(
BitWidth);
7387 SelectPattern StepPattern(*
this,
BitWidth, Step);
7388 if (!StepPattern.isRecognized())
7389 return ConstantRange::getFull(
BitWidth);
7391 if (StartPattern.Condition != StepPattern.Condition) {
7395 return ConstantRange::getFull(
BitWidth);
7406 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7407 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7408 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7409 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7411 ConstantRange TrueRange =
7412 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7413 ConstantRange FalseRange =
7414 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7426 PDI && PDI->isDisjoint()) {
7441ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7454 SmallPtrSet<const SCEV *, 16> Visited;
7456 auto pushOp = [&](
const SCEV *S) {
7457 if (!Visited.
insert(S).second)
7460 if (Visited.
size() > 30) {
7471 while (!Worklist.
empty()) {
7473 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7474 if (!Bound || DT.dominates(Bound, DefI))
7481 return Bound ? Bound : &*F.getEntryBlock().begin();
7487 return getDefiningScopeBound(
Ops, Discard);
7490bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7492 if (
A->getParent() ==
B->getParent() &&
7497 auto *BLoop = LI.getLoopFor(
B->getParent());
7498 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7499 BLoop->getLoopPreheader() ==
A->getParent() &&
7501 A->getParent()->end()) &&
7509 SCEVPoisonCollector PC(
true);
7511 return PC.MaybePoison.empty();
7514bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7524bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7541 for (
const Use &
Op :
I->operands()) {
7547 auto *DefI = getDefiningScopeBound(SCEVOps);
7548 return isGuaranteedToTransferExecutionTo(DefI,
I);
7551bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7553 if (isSCEVExprNeverPoison(
I))
7564 auto *ExitingBB =
L->getExitingBlock();
7568 SmallPtrSet<const Value *, 16> KnownPoison;
7577 while (!Worklist.
empty()) {
7580 for (
const Use &U :
Poison->uses()) {
7583 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7587 if (KnownPoison.
insert(PoisonUser).second)
7595ScalarEvolution::LoopProperties
7596ScalarEvolution::getLoopProperties(
const Loop *L) {
7597 using LoopProperties = ScalarEvolution::LoopProperties;
7599 auto Itr = LoopPropertiesCache.find(L);
7600 if (Itr == LoopPropertiesCache.end()) {
7603 return !
SI->isSimple();
7613 return I->mayWriteToMemory();
7616 LoopProperties LP = {
true,
7619 for (
auto *BB :
L->getBlocks())
7620 for (
auto &
I : *BB) {
7622 LP.HasNoAbnormalExits =
false;
7623 if (HasSideEffects(&
I))
7624 LP.HasNoSideEffects =
false;
7625 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7629 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7630 assert(InsertPair.second &&
"We just checked!");
7631 Itr = InsertPair.first;
7644const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7650 Stack.emplace_back(V,
false);
7651 while (!Stack.empty()) {
7652 auto E = Stack.back();
7653 Value *CurV = E.getPointer();
7661 const SCEV *CreatedSCEV =
nullptr;
7664 CreatedSCEV = createSCEV(CurV);
7669 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7673 insertValueToMap(CurV, CreatedSCEV);
7676 Stack.back().setInt(
true);
7679 Stack.emplace_back(
Op,
false);
7696 if (!DT.isReachableFromEntry(
I->getParent()))
7709 switch (BO->Opcode) {
7710 case Instruction::Add:
7711 case Instruction::Mul: {
7718 Ops.push_back(BO->
Op);
7722 Ops.push_back(BO->RHS);
7726 (BO->Opcode == Instruction::Add &&
7727 (NewBO->Opcode != Instruction::Add &&
7728 NewBO->Opcode != Instruction::Sub)) ||
7729 (BO->Opcode == Instruction::Mul &&
7730 NewBO->Opcode != Instruction::Mul)) {
7731 Ops.push_back(BO->LHS);
7736 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7739 Ops.push_back(BO->LHS);
7747 case Instruction::Sub:
7748 case Instruction::UDiv:
7749 case Instruction::URem:
7751 case Instruction::AShr:
7752 case Instruction::Shl:
7753 case Instruction::Xor:
7757 case Instruction::And:
7758 case Instruction::Or:
7762 case Instruction::LShr:
7769 Ops.push_back(BO->LHS);
7770 Ops.push_back(BO->RHS);
7774 switch (
U->getOpcode()) {
7775 case Instruction::Trunc:
7776 case Instruction::ZExt:
7777 case Instruction::SExt:
7778 case Instruction::PtrToAddr:
7779 case Instruction::PtrToInt:
7780 Ops.push_back(
U->getOperand(0));
7783 case Instruction::BitCast:
7785 Ops.push_back(
U->getOperand(0));
7790 case Instruction::SDiv:
7791 case Instruction::SRem:
7792 Ops.push_back(
U->getOperand(0));
7793 Ops.push_back(
U->getOperand(1));
7796 case Instruction::GetElementPtr:
7798 "GEP source element type must be sized");
7802 case Instruction::IntToPtr:
7805 case Instruction::PHI:
7836 Ops.push_back(CondICmp->getOperand(0));
7837 Ops.push_back(CondICmp->getOperand(1));
7857 case Instruction::Select: {
7859 auto CanSimplifyToUnknown = [
this,
U]() {
7877 if (CanSimplifyToUnknown())
7884 case Instruction::Call:
7885 case Instruction::Invoke:
7892 switch (
II->getIntrinsicID()) {
7893 case Intrinsic::abs:
7894 Ops.push_back(
II->getArgOperand(0));
7896 case Intrinsic::umax:
7897 case Intrinsic::umin:
7898 case Intrinsic::smax:
7899 case Intrinsic::smin:
7900 case Intrinsic::usub_sat:
7901 case Intrinsic::uadd_sat:
7902 Ops.push_back(
II->getArgOperand(0));
7903 Ops.push_back(
II->getArgOperand(1));
7905 case Intrinsic::start_loop_iterations:
7906 case Intrinsic::annotation:
7907 case Intrinsic::ptr_annotation:
7908 Ops.push_back(
II->getArgOperand(0));
7920const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7929 if (!DT.isReachableFromEntry(
I->getParent()))
7944 switch (BO->Opcode) {
7945 case Instruction::Add: {
7971 if (BO->Opcode == Instruction::Sub)
7979 if (BO->Opcode == Instruction::Sub)
7986 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7987 NewBO->Opcode != Instruction::Sub)) {
7997 case Instruction::Mul: {
8018 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
8027 case Instruction::UDiv:
8031 case Instruction::URem:
8035 case Instruction::Sub: {
8038 Flags = getNoWrapFlagsFromUB(BO->
Op);
8043 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
8046 if (HasPtrLHS || HasPtrRHS) {
8051 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
8052 bool BothPtr) ->
const SCEV * {
8055 const SCEV *PtrSCEV =
getSCEV(PtrOp);
8065 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
8066 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
8074 case Instruction::And:
8080 if (CI->isMinusOne())
8082 const APInt &
A = CI->getValue();
8088 unsigned LZ =
A.countl_zero();
8089 unsigned TZ =
A.countr_zero();
8094 APInt EffectiveMask =
8096 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
8099 const SCEV *ShiftedLHS =
nullptr;
8103 unsigned MulZeros = OpC->getAPInt().countr_zero();
8104 unsigned GCD = std::min(MulZeros, TZ);
8109 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8131 case Instruction::Or:
8140 case Instruction::Xor:
8143 if (CI->isMinusOne())
8152 if (LBO->getOpcode() == Instruction::And &&
8153 LCI->getValue() == CI->getValue())
8154 if (
const SCEVZeroExtendExpr *Z =
8157 const SCEV *Z0 =
Z->getOperand();
8164 if (CI->getValue().isMask(Z0TySize))
8170 APInt Trunc = CI->getValue().trunc(Z0TySize);
8179 case Instruction::Shl:
8197 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8206 ConstantInt *
X = ConstantInt::get(
8212 case Instruction::AShr:
8234 const SCEV *AddTruncateExpr =
nullptr;
8235 ConstantInt *ShlAmtCI =
nullptr;
8236 const SCEV *AddConstant =
nullptr;
8238 if (L &&
L->getOpcode() == Instruction::Add) {
8246 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8253 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8261 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8266 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8271 if (AddTruncateExpr && ShlAmtCI) {
8283 const APInt &ShlAmt = ShlAmtCI->
getValue();
8287 const SCEV *CompositeExpr =
8289 if (
L->getOpcode() != Instruction::Shl)
8290 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8299 switch (
U->getOpcode()) {
8300 case Instruction::Trunc:
8303 case Instruction::ZExt:
8306 case Instruction::SExt:
8316 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8317 Type *Ty =
U->getType();
8325 case Instruction::BitCast:
8331 case Instruction::PtrToAddr: {
8338 case Instruction::PtrToInt: {
8344 const SCEV *PtrSCEV =
getSCEV(
U->getOperand(0));
8353 case Instruction::IntToPtr:
8357 case Instruction::SDiv:
8364 case Instruction::SRem:
8371 case Instruction::GetElementPtr:
8374 case Instruction::PHI:
8377 case Instruction::Select:
8378 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8381 case Instruction::Call:
8382 case Instruction::Invoke:
8387 switch (
II->getIntrinsicID()) {
8388 case Intrinsic::abs:
8392 case Intrinsic::umax:
8396 case Intrinsic::umin:
8400 case Intrinsic::smax:
8404 case Intrinsic::smin:
8408 case Intrinsic::usub_sat: {
8409 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8410 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8414 case Intrinsic::uadd_sat: {
8415 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8416 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8420 case Intrinsic::start_loop_iterations:
8421 case Intrinsic::annotation:
8422 case Intrinsic::ptr_annotation:
8426 case Intrinsic::vscale:
8446 auto *ExitCountType = ExitCount->
getType();
8447 assert(ExitCountType->isIntegerTy());
8449 1 + ExitCountType->getScalarSizeInBits());
8462 auto CanAddOneWithoutOverflow = [&]() {
8464 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8475 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8505 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8506 assert(L->isLoopExiting(ExitingBlock) &&
8507 "Exiting block must actually branch out of the loop!");
8516 const auto *MaxExitCount =
8524 L->getExitingBlocks(ExitingBlocks);
8526 std::optional<unsigned> Res;
8527 for (
auto *ExitingBB : ExitingBlocks) {
8531 Res = std::gcd(*Res, Multiple);
8533 return Res.value_or(1);
8537 const SCEV *ExitCount) {
8567 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8568 assert(L->isLoopExiting(ExitingBlock) &&
8569 "Exiting block must actually branch out of the loop!");
8579 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8581 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8583 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8593 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8596 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8599 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8607 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8614 return getBackedgeTakenInfo(L).getExact(L,
this);
8616 return getBackedgeTakenInfo(L).getConstantMax(
this);
8618 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8625 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8630 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8634 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8637ScalarEvolution::BackedgeTakenInfo &
8638ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8639 auto &BTI = getBackedgeTakenInfo(L);
8640 if (BTI.hasFullInfo())
8643 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8646 return Pair.first->second;
8648 BackedgeTakenInfo Result =
8649 computeBackedgeTakenCount(L,
true);
8651 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8654ScalarEvolution::BackedgeTakenInfo &
8655ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8661 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8662 BackedgeTakenCounts.try_emplace(L);
8664 return Pair.first->second;
8669 BackedgeTakenInfo Result = computeBackedgeTakenCount(L);
8676 if (Result.hasAnyInfo()) {
8679 auto LoopUsersIt = LoopUsers.find(L);
8680 if (LoopUsersIt != LoopUsers.end())
8682 forgetMemoizedResults(ToForget);
8685 for (
PHINode &PN : L->getHeader()->phis())
8686 ConstantEvolutionLoopExitValue.erase(&PN);
8694 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8703 BackedgeTakenCounts.clear();
8704 PredicatedBackedgeTakenCounts.clear();
8705 BECountUsers.clear();
8706 LoopPropertiesCache.clear();
8707 ConstantEvolutionLoopExitValue.clear();
8708 ValueExprMap.clear();
8709 ValuesAtScopes.clear();
8710 ValuesAtScopesUsers.clear();
8711 LoopDispositions.clear();
8712 BlockDispositions.clear();
8713 UnsignedRanges.clear();
8714 SignedRanges.clear();
8715 ExprValueMap.clear();
8717 ConstantMultipleCache.clear();
8718 PredicatedSCEVRewrites.clear();
8720 FoldCacheUser.clear();
8722void ScalarEvolution::visitAndClearUsers(
8726 while (!Worklist.
empty()) {
8733 if (It != ValueExprMap.
end()) {
8735 eraseValueFromMap(It->first);
8737 ConstantEvolutionLoopExitValue.erase(PN);
8749 while (!LoopWorklist.
empty()) {
8753 forgetBackedgeTakenCounts(CurrL,
false);
8754 forgetBackedgeTakenCounts(CurrL,
true);
8757 PredicatedSCEVRewrites.remove_if(
8758 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8760 auto LoopUsersItr = LoopUsers.find(CurrL);
8761 if (LoopUsersItr != LoopUsers.end())
8765 for (
PHINode &PN : CurrL->getHeader()->phis()) {
8766 ConstantEvolutionLoopExitValue.erase(&PN);
8767 auto VIt = ValueExprMap.find_as(
static_cast<Value *
>(&PN));
8768 if (VIt != ValueExprMap.end())
8772 LoopPropertiesCache.erase(CurrL);
8775 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8777 forgetMemoizedResults(ToForget);
8794 visitAndClearUsers(Worklist, Visited, ToForget);
8796 forgetMemoizedResults(ToForget);
8808 struct InvalidationRootCollector {
8812 InvalidationRootCollector(
Loop *L) : L(L) {}
8814 bool follow(
const SCEV *S) {
8820 if (L->contains(AddRec->
getLoop()))
8825 bool isDone()
const {
return false; }
8828 InvalidationRootCollector
C(L);
8830 forgetMemoizedResults(
C.Roots);
8843 BlockDispositions.clear();
8844 LoopDispositions.clear();
8861 while (!Worklist.
empty()) {
8863 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8864 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8865 if (!LoopDispoRemoved && !BlockDispoRemoved)
8867 auto Users = SCEVUsers.find(Curr);
8868 if (
Users != SCEVUsers.end())
8881const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8885 if (!isComplete() || ExitNotTaken.
empty())
8896 for (
const auto &ENT : ExitNotTaken) {
8897 const SCEV *BECount = ENT.ExactNotTaken;
8900 "We should only have known counts for exiting blocks that dominate "
8903 Ops.push_back(BECount);
8908 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8909 "Predicate should be always true!");
8918const ScalarEvolution::ExitNotTakenInfo *
8919ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8920 const BasicBlock *ExitingBlock,
8921 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8922 for (
const auto &ENT : ExitNotTaken)
8923 if (ENT.ExitingBlock == ExitingBlock) {
8924 if (ENT.hasAlwaysTruePredicate())
8926 else if (Predicates) {
8936const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8938 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8939 if (!getConstantMax())
8942 for (
const auto &ENT : ExitNotTaken)
8943 if (!ENT.hasAlwaysTruePredicate()) {
8951 "No point in having a non-constant max backedge taken count!");
8952 return getConstantMax();
8955const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8957 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8965 for (
const auto &ENT : ExitNotTaken) {
8966 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8969 "We should only have known counts for exiting blocks that "
8975 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8976 "Predicate should be always true!");
8979 if (ExitCounts.
empty())
8988bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8990 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8991 return !ENT.hasAlwaysTruePredicate();
8993 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
9009 this->ExactNotTaken = E = ConstantMaxNotTaken;
9010 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
9015 "Exact is not allowed to be less precise than Constant Max");
9018 "Exact is not allowed to be less precise than Symbolic Max");
9021 "Symbolic Max is not allowed to be less precise than Constant Max");
9024 "No point in having a non-constant max backedge taken count!");
9026 for (
const auto PredList : PredLists)
9027 for (
const auto *
P : PredList) {
9035 "Backedge count should be int");
9038 "Max backedge count should be int");
9051ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
9053 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
9054 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
9055 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9057 ExitNotTaken.reserve(ExitCounts.
size());
9058 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
9059 std::back_inserter(ExitNotTaken),
9060 [&](
const EdgeExitInfo &EEI) {
9061 BasicBlock *ExitBB = EEI.first;
9062 const ExitLimit &EL = EEI.second;
9063 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
9064 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
9069 "No point in having a non-constant max backedge taken count!");
9073ScalarEvolution::BackedgeTakenInfo
9074ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
9075 bool AllowPredicates) {
9077 L->getExitingBlocks(ExitingBlocks);
9079 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9082 bool CouldComputeBECount =
true;
9084 const SCEV *MustExitMaxBECount =
nullptr;
9085 const SCEV *MayExitMaxBECount =
nullptr;
9086 bool MustExitMaxOrZero =
false;
9087 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9098 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9099 if (ExitIfTrue == CI->
isZero())
9103 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9105 assert((AllowPredicates || EL.Predicates.empty()) &&
9106 "Predicated exit limit when predicates are not allowed!");
9111 ++NumExitCountsComputed;
9115 CouldComputeBECount =
false;
9122 "Exact is known but symbolic isn't?");
9123 ++NumExitCountsNotComputed;
9138 DT.dominates(ExitBB, Latch)) {
9139 if (!MustExitMaxBECount) {
9140 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9141 MustExitMaxOrZero = EL.MaxOrZero;
9144 EL.ConstantMaxNotTaken);
9148 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9151 EL.ConstantMaxNotTaken);
9155 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9159 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9165 for (
const auto &Pair : ExitCounts) {
9167 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9169 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9170 {
L, AllowPredicates});
9172 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9173 MaxBECount, MaxOrZero);
9176ScalarEvolution::ExitLimit
9177ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9178 bool IsOnlyExit,
bool AllowPredicates) {
9179 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9183 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9188 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9189 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9190 "It should have one successor in loop and one exit block!");
9201 if (!
L->contains(SBB)) {
9206 assert(Exit &&
"Exiting block must have at least one exit");
9207 return computeExitLimitFromSingleExitSwitch(
9208 L, SI, Exit, IsOnlyExit);
9215 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9216 bool AllowPredicates) {
9217 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9218 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9219 ControlsOnlyExit, AllowPredicates);
9222std::optional<ScalarEvolution::ExitLimit>
9223ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9224 bool ExitIfTrue,
bool ControlsOnlyExit,
9225 bool AllowPredicates) {
9227 (void)this->ExitIfTrue;
9228 (void)this->AllowPredicates;
9230 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9231 this->AllowPredicates == AllowPredicates &&
9232 "Variance in assumed invariant key components!");
9233 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9234 if (Itr == TripCountMap.end())
9235 return std::nullopt;
9239void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9241 bool ControlsOnlyExit,
9242 bool AllowPredicates,
9244 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9245 this->AllowPredicates == AllowPredicates &&
9246 "Variance in assumed invariant key components!");
9248 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9249 assert(InsertResult.second &&
"Expected successful insertion!");
9254ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9255 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9256 bool ControlsOnlyExit,
bool AllowPredicates) {
9258 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9262 ExitLimit EL = computeExitLimitFromCondImpl(
9263 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9264 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9268ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9269 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9270 bool ControlsOnlyExit,
bool AllowPredicates) {
9272 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9273 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9274 return *LimitFromBinOp;
9280 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9281 if (EL.hasFullInfo() || !AllowPredicates)
9285 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9305 const WithOverflowInst *WO;
9320 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9321 ControlsOnlyExit, AllowPredicates);
9322 if (EL.hasAnyInfo())
9327 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9330std::optional<ScalarEvolution::ExitLimit>
9331ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9335 bool AllowPredicates) {
9344 return std::nullopt;
9348 ExitLimit EL0 = computeExitLimitFromCondCached(
9349 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9350 ExitLimit EL1 = computeExitLimitFromCondCached(
9351 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9356 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9361 if (EitherMayExit) {
9371 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9373 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9376 EL1.ConstantMaxNotTaken);
9378 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9380 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9383 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9387 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9388 BECount = EL0.ExactNotTaken;
9401 SymbolicMaxBECount =
9403 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9407ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9408 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9409 bool AllowPredicates) {
9421 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9423 if (EL.hasAnyInfo())
9426 auto *ExhaustiveCount =
9427 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9430 return ExhaustiveCount;
9432 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9435ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9437 bool ControlsOnlyExit,
bool AllowPredicates) {
9462 ConstantRange CompRange =
9480 InnerLHS = ZExt->getOperand();
9527 if (EL.hasAnyInfo())
9544 if (EL.hasAnyInfo())
return EL;
9576 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9578 if (EL.hasAnyInfo())
9594 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9596 if (EL.hasAnyInfo())
9607ScalarEvolution::ExitLimit
9608ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9610 BasicBlock *ExitingBlock,
9611 bool ControlsOnlyExit) {
9612 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9615 if (
Switch->getDefaultDest() == ExitingBlock)
9619 "Default case must not exit the loop!");
9625 if (EL.hasAnyInfo())
9637 "Evaluation of SCEV at constant didn't fold correctly?");
9641ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9651 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9658 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9660 unsigned &OutShiftAmt) {
9661 using namespace PatternMatch;
9663 ConstantInt *ShiftAmt;
9665 OutOpCode = Instruction::LShr;
9667 OutOpCode = Instruction::AShr;
9669 OutOpCode = Instruction::Shl;
9674 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9689 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9691 unsigned &ShiftAmtOut) {
9692 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9708 if (MatchPositiveShift(
LHS, V, OpC, Amt)) {
9709 PostShiftOpCode = OpC;
9715 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9718 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9724 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9731 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9737 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9749 ConstantInt *StableValue =
nullptr;
9754 case Instruction::AShr: {
9761 if (
Known.isNonNegative())
9762 StableValue = ConstantInt::get(Ty, 0);
9763 else if (
Known.isNegative())
9764 StableValue = ConstantInt::get(Ty, -1,
true);
9770 case Instruction::LShr:
9771 case Instruction::Shl:
9781 "Otherwise cannot be an operand to a branch instruction");
9783 if (
Result->isNullValue()) {
9792 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9794 const SCEV *StartSCEV =
getSCEV(StartValue);
9798 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9799 MaxBTC = std::min(MaxBTC, RangeBTC);
9803 const SCEV *UpperBound =
9820 if (
const Function *
F = CI->getCalledFunction())
9829 if (!L->contains(
I))
return false;
9834 return L->getHeader() ==
I->getParent();
9910 if (!
I)
return nullptr;
9923 std::vector<Constant*> Operands(
I->getNumOperands());
9925 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9929 if (!Operands[i])
return nullptr;
9934 if (!
C)
return nullptr;
9956 if (IncomingVal != CurrentVal) {
9959 IncomingVal = CurrentVal;
9971ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9974 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9983 DenseMap<Instruction *, Constant *> CurrentIterVals;
9985 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9991 for (PHINode &
PHI : Header->phis()) {
9993 CurrentIterVals[&
PHI] = StartCST;
9995 if (!CurrentIterVals.
count(PN))
9996 return RetVal =
nullptr;
10002 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
10005 unsigned IterationNum = 0;
10007 for (; ; ++IterationNum) {
10008 if (IterationNum == NumIterations)
10009 return RetVal = CurrentIterVals[PN];
10013 DenseMap<Instruction *, Constant *> NextIterVals;
10018 NextIterVals[PN] = NextPHI;
10020 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
10026 for (
const auto &
I : CurrentIterVals) {
10028 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
10033 for (
const auto &
I : PHIsToCompute) {
10034 PHINode *
PHI =
I.first;
10037 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10040 if (NextPHI !=
I.second)
10041 StoppedEvolving =
false;
10046 if (StoppedEvolving)
10047 return RetVal = CurrentIterVals[PN];
10049 CurrentIterVals.swap(NextIterVals);
10053const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
10063 DenseMap<Instruction *, Constant *> CurrentIterVals;
10065 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10068 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
10070 for (PHINode &
PHI : Header->phis()) {
10072 CurrentIterVals[&
PHI] = StartCST;
10074 if (!CurrentIterVals.
count(PN))
10082 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10089 if (CondVal->getValue() == uint64_t(ExitWhen)) {
10090 ++NumBruteForceTripCountsComputed;
10095 DenseMap<Instruction *, Constant *> NextIterVals;
10101 for (
const auto &
I : CurrentIterVals) {
10103 if (!
PHI ||
PHI->getParent() != Header)
continue;
10106 for (PHINode *
PHI : PHIsToCompute) {
10108 if (NextPHI)
continue;
10110 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10113 CurrentIterVals.
swap(NextIterVals);
10126 return LS.second ? LS.second : V;
10128 Values.emplace_back(L,
nullptr);
10131 const SCEV *
C = computeSCEVAtScope(V, L);
10132 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10133 if (LS.first == L) {
10136 ValuesAtScopesUsers[
C].push_back({L, V});
10147 switch (V->getSCEVType()) {
10180 assert(!
C->getType()->isPointerTy() &&
10181 "Can only have one pointer, and it must be last");
10206const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10207 SmallVectorImpl<SCEVUse> &NewOps) {
10241const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10242 switch (
V->getSCEVType()) {
10253 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10264 for (++i; i !=
e; ++i)
10308 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10318 for (++i; i !=
e; ++i) {
10323 return getWithOperands(V, NewOps);
10338 const Loop *CurrLoop = this->LI[
I->getParent()];
10349 if (BackedgeTakenCount->
isZero()) {
10350 Value *InitValue =
nullptr;
10351 bool MultipleInitValues =
false;
10357 MultipleInitValues =
true;
10362 if (!MultipleInitValues && InitValue)
10371 unsigned InLoopPred =
10382 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10396 SmallVector<Constant *, 4> Operands;
10397 Operands.
reserve(
I->getNumOperands());
10398 bool MadeImprovement =
false;
10413 MadeImprovement |= OrigV != OpV;
10418 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10423 if (!MadeImprovement)
10444const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10446 return stripInjectiveFunctions(ZExt->getOperand());
10448 return stripInjectiveFunctions(SExt->getOperand());
10466 assert(
A != 0 &&
"A must be non-zero.");
10482 if (MinTZ < Mult2 && L->getLoopPredecessor())
10484 if (MinTZ < Mult2) {
10507 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10527static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10533 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10534 << *AddRec <<
'\n');
10537 if (!LC || !MC || !
NC) {
10538 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10539 return std::nullopt;
10545 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10553 N =
N.sext(NewWidth);
10554 M = M.sext(NewWidth);
10555 L = L.sext(NewWidth);
10572 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10573 <<
", multiplied by " <<
T <<
'\n');
10582 std::optional<APInt>
Y) {
10584 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10587 return XW.
slt(YW) ? *
X : *
Y;
10590 return std::nullopt;
10591 return X ? *
X : *
Y;
10608 return std::nullopt;
10609 unsigned W =
X->getBitWidth();
10629static std::optional<APInt>
10635 return std::nullopt;
10638 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10639 std::optional<APInt>
X =
10642 return std::nullopt;
10647 return std::nullopt;
10662static std::optional<APInt>
10666 "Starting value of addrec should be 0");
10667 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10668 <<
Range <<
", addrec " << *AddRec <<
'\n');
10672 "Addrec's initial value should be in range");
10678 return std::nullopt;
10688 auto SolveForBoundary =
10689 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10692 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10693 << Bound <<
" (before multiplying by " << M <<
")\n");
10696 std::optional<APInt> SO;
10699 "signed overflow\n");
10703 "unsigned overflow\n");
10704 std::optional<APInt> UO =
10707 auto LeavesRange = [&] (
const APInt &
X) {
10715 if (
Range.contains(
V1->getValue()))
10724 return {std::nullopt,
false};
10729 if (LeavesRange(*Min))
10730 return { Min,
true };
10731 std::optional<APInt> Max = Min == SO ? UO : SO;
10732 if (LeavesRange(*Max))
10733 return { Max,
true };
10736 return {std::nullopt,
true};
10743 auto SL = SolveForBoundary(
Lower);
10744 auto SU = SolveForBoundary(
Upper);
10747 if (!SL.second || !SU.second)
10748 return std::nullopt;
10791ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10793 bool ControlsOnlyExit,
10794 bool AllowPredicates) {
10805 if (
C->getValue()->isZero())
return C;
10809 const SCEVAddRecExpr *AddRec =
10812 if (!AddRec && AllowPredicates)
10818 if (!AddRec || AddRec->
getLoop() != L)
10829 return ExitLimit(R, R, R,
false, Predicates);
10887 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10913 const SCEV *
Exact =
10921 const SCEV *SymbolicMax =
10923 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10932 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10940 return ExitLimit(
E, M, S,
false, Predicates);
10943ScalarEvolution::ExitLimit
10944ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10952 if (!
C->getValue()->isZero())
10962std::pair<const BasicBlock *, const BasicBlock *>
10963ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10974 if (
const Loop *L = LI.getLoopFor(BB))
10975 return {
L->getLoopPredecessor(),
L->getHeader()};
10977 return {
nullptr, BB};
10986 if (
A ==
B)
return true;
11001 if (ComputesEqualValues(AI, BI))
11009 const SCEV *Op0, *Op1;
11028 auto TrivialCase = [&](
bool TriviallyTrue) {
11037 const SCEV *NewLHS, *NewRHS;
11061 return TrivialCase(
false);
11062 return TrivialCase(
true);
11081 RAdd->hasNoSignedWrap()) ||
11083 RAdd->hasNoUnsignedWrap())) {
11103 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
11104 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
11107 C->getAPInt().isStrictlyPositive()) ||
11131 const APInt &
RA = RC->getAPInt();
11133 bool SimplifiedByConstantRange =
false;
11138 return TrivialCase(
true);
11140 return TrivialCase(
false);
11149 Changed = SimplifiedByConstantRange =
true;
11153 if (!SimplifiedByConstantRange) {
11170 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11176 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11182 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11188 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11200 return TrivialCase(
true);
11202 return TrivialCase(
false);
11307 auto NonRecursive = [OrNegative](
const SCEV *S) {
11309 return C->getAPInt().isPowerOf2() ||
11310 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11316 if (NonRecursive(S))
11342 APInt C = Cst->getAPInt();
11343 return C.urem(M) == 0;
11351 const SCEV *SmodM =
11366 for (
auto *
A : Assumptions)
11367 if (
A->implies(
P, *
this))
11380std::pair<const SCEV *, const SCEV *>
11383 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11385 return { Start, Start };
11387 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11396 getUsedLoops(LHS, LoopsUsed);
11397 getUsedLoops(RHS, LoopsUsed);
11399 if (LoopsUsed.
empty())
11404 for (
const auto *L1 : LoopsUsed)
11405 for (
const auto *L2 : LoopsUsed)
11406 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11407 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11408 "Domination relationship is not a linear order");
11438 SplitRHS.second) &&
11450 if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
11454 return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11464 return std::nullopt;
11479 if (KnownWithoutContext)
11480 return KnownWithoutContext;
11487 return std::nullopt;
11493 const Loop *L = LHS->getLoop();
11498std::optional<ScalarEvolution::MonotonicPredicateType>
11501 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11507 auto ResultSwapped =
11510 assert(*ResultSwapped != *Result &&
11511 "monotonicity should flip as we flip the predicate");
11518std::optional<ScalarEvolution::MonotonicPredicateType>
11519ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11533 return std::nullopt;
11537 "Should be greater or less!");
11541 if (!LHS->hasNoUnsignedWrap())
11542 return std::nullopt;
11546 "Relational predicate is either signed or unsigned!");
11547 if (!
LHS->hasNoSignedWrap())
11548 return std::nullopt;
11550 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11558 return std::nullopt;
11561std::optional<ScalarEvolution::LoopInvariantPredicate>
11568 return std::nullopt;
11575 if (!ArLHS || ArLHS->
getLoop() != L)
11576 return std::nullopt;
11580 return std::nullopt;
11606 return std::nullopt;
11643 return std::nullopt;
11646std::optional<ScalarEvolution::LoopInvariantPredicate>
11651 Pred, LHS, RHS, L, CtxI, MaxIter))
11661 Pred, LHS, RHS, L, CtxI,
Op))
11663 return std::nullopt;
11666std::optional<ScalarEvolution::LoopInvariantPredicate>
11681 return std::nullopt;
11688 if (!AR || AR->
getLoop() != L)
11689 return std::nullopt;
11694 Pred = Pred.dropSameSign();
11698 return std::nullopt;
11704 if (Step != One && Step != MinusOne)
11705 return std::nullopt;
11711 return std::nullopt;
11717 return std::nullopt;
11725 if (Step == MinusOne)
11729 return std::nullopt;
11735bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11741 auto CheckRange = [&](
bool IsSigned) {
11744 return RangeLHS.
icmp(Pred, RangeRHS);
11753 if (CheckRange(
true) || CheckRange(
false))
11762bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11771 SCEVUse XNonConstOp, XConstOp;
11772 SCEVUse YNonConstOp, YConstOp;
11776 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11779 XFlagsPresent = ExpectedFlags;
11784 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11787 YFlagsPresent = ExpectedFlags;
11790 if (YNonConstOp != XNonConstOp)
11798 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11801 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11861bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11882bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11883 const SCEV *
LHS,
const SCEV *
RHS) {
11888 return any_of(*BB, [&](
const Instruction &
I) {
11889 using namespace llvm::PatternMatch;
11894 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11908 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11913 "This cannot be done on broken IR!");
11916 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11925 if (LoopContinuePredicate &&
11926 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11927 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11932 if (WalkingBEDominatingConds)
11938 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11939 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11946 const SCEV *LoopCounter =
11954 for (
auto &AssumeVH : AC.assumptions()) {
11961 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11965 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11968 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11969 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11970 assert(DTN &&
"should reach the loop header before reaching the root!");
11973 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11991 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
12004 if (!DT.isReachableFromEntry(BB))
12008 "This cannot be done on broken IR!");
12016 const bool ProvingStrictComparison =
12018 bool ProvedNonStrictComparison =
false;
12019 bool ProvedNonEquality =
false;
12022 if (!ProvedNonStrictComparison)
12023 ProvedNonStrictComparison = Fn(NonStrictPredicate);
12024 if (!ProvedNonEquality)
12026 if (ProvedNonStrictComparison && ProvedNonEquality)
12031 if (ProvingStrictComparison) {
12033 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
12035 if (SplitAndProve(ProofFn))
12040 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
12042 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
12044 if (ProvingStrictComparison) {
12046 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
12048 if (SplitAndProve(ProofFn))
12057 const Loop *ContainingLoop = LI.getLoopFor(BB);
12059 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
12063 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
12064 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
12067 if (!BlockEntryPredicate)
12076 for (
auto &AssumeVH : AC.assumptions()) {
12080 if (!DT.dominates(CI, BB))
12083 if (ProveViaCond(CI->getArgOperand(0),
false))
12089 F.getParent(), Intrinsic::experimental_guard);
12091 for (
const auto *GU : GuardDecl->users())
12093 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12094 if (ProveViaCond(Guard->getArgOperand(0),
false))
12109 "LHS is not available at Loop Entry");
12111 "RHS is not available at Loop Entry");
12113 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12124 if (FoundCondValue ==
12128 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12132 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12135 const Value *Op0, *Op1;
12138 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12142 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12143 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12147 if (!ICI)
return false;
12151 CmpPredicate FoundPred;
12160 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12163bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12164 const SCEV *
RHS, CmpPredicate FoundPred,
12165 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12166 const Instruction *CtxI) {
12176 auto *WideType = FoundLHS->
getType();
12188 TruncFoundLHS, TruncFoundRHS, CtxI))
12214 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12218bool ScalarEvolution::isImpliedCondBalancedTypes(
12223 "Types should be balanced!");
12230 if (FoundLHS == FoundRHS)
12234 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12246 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12263 LHS, FoundLHS, FoundRHS, CtxI);
12265 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12287 assert(P1 != P2 &&
"Handled earlier!");
12291 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12295 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12298 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12299 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12300 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12305 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12316 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12317 CanonicalRHS, CanonicalFoundLHS,
12318 CanonicalFoundRHS);
12323 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12324 CanonicalRHS, CanonicalFoundLHS,
12325 CanonicalFoundRHS);
12332 const SCEVConstant *
C =
nullptr;
12333 const SCEV *
V =
nullptr;
12351 if (Min ==
C->getAPInt()) {
12356 APInt SharperMin = Min + 1;
12359 case ICmpInst::ICMP_SGE:
12360 case ICmpInst::ICMP_UGE:
12363 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12368 case ICmpInst::ICMP_SGT:
12369 case ICmpInst::ICMP_UGT:
12379 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12384 case ICmpInst::ICMP_SLE:
12385 case ICmpInst::ICMP_ULE:
12386 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12387 LHS, V, getConstant(SharperMin), CtxI))
12391 case ICmpInst::ICMP_SLT:
12392 case ICmpInst::ICMP_ULT:
12393 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12394 LHS, V, getConstant(Min), CtxI))
12408 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12412 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12415 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12431std::optional<APInt>
12438 APInt DiffMul(BW, 1);
12441 for (
unsigned I = 0;
I < 8; ++
I) {
12450 if (LAR->getLoop() != MAR->getLoop())
12451 return std::nullopt;
12455 if (!LAR->isAffine() || !MAR->isAffine())
12456 return std::nullopt;
12458 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12459 return std::nullopt;
12461 Less = LAR->getStart();
12462 More = MAR->getStart();
12467 auto MatchConstMul =
12468 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12473 return std::nullopt;
12475 if (
auto MatchedMore = MatchConstMul(More)) {
12476 if (
auto MatchedLess = MatchConstMul(
Less)) {
12477 if (MatchedMore->second == MatchedLess->second) {
12478 More = MatchedMore->first;
12479 Less = MatchedLess->first;
12480 DiffMul *= MatchedMore->second;
12491 Diff +=
C->getAPInt() * DiffMul;
12494 Diff -=
C->getAPInt() * DiffMul;
12497 Multiplicity[S] +=
Mul;
12499 auto Decompose = [&](
const SCEV *S,
int Mul) {
12506 Decompose(More, 1);
12507 Decompose(
Less, -1);
12511 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12512 for (
const auto &[S,
Mul] : Multiplicity) {
12517 return std::nullopt;
12519 }
else if (
Mul == -1) {
12521 return std::nullopt;
12524 return std::nullopt;
12528 if (NewMore == More || NewLess ==
Less)
12529 return std::nullopt;
12535 if (!More && !
Less)
12539 if (!More || !
Less)
12540 return std::nullopt;
12544 return std::nullopt;
12547bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12569 const auto *Latch = L->getLoopLatch();
12572 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12581 const auto *Latch = L->getLoopLatch();
12584 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12594bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12597 const SCEV *FoundLHS,
12598 const SCEV *FoundRHS) {
12607 if (!AddRecFoundLHS)
12614 const Loop *
L = AddRecFoundLHS->getLoop();
12615 if (L != AddRecLHS->getLoop())
12654 if (!RDiff || *LDiff != *RDiff)
12657 if (LDiff->isMinValue())
12660 APInt FoundRHSLimit;
12663 FoundRHSLimit = -(*RDiff);
12675bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12676 const SCEV *
RHS,
const SCEV *FoundLHS,
12677 const SCEV *FoundRHS,
unsigned Depth) {
12678 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12682 bool Erased = PendingMerges.erase(LPhi);
12683 assert(Erased &&
"Failed to erase LPhi!");
12687 bool Erased = PendingMerges.erase(RPhi);
12688 assert(Erased &&
"Failed to erase RPhi!");
12696 if (!PendingMerges.insert(Phi).second)
12710 if (!PendingMerges.insert(Phi).second)
12716 if (!LPhi && !RPhi)
12727 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12731 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12732 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12733 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12734 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12737 if (RPhi && RPhi->getParent() == LBB) {
12744 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12745 if (!ProvedEasily(L, R))
12756 auto *RLoop = RAR->
getLoop();
12757 auto *Predecessor = RLoop->getLoopPredecessor();
12758 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12760 if (!ProvedEasily(L1, RAR->
getStart()))
12762 auto *Latch = RLoop->getLoopLatch();
12763 assert(Latch &&
"Loop with AddRec with no latch?");
12784 if (
auto *Loop = LI.getLoopFor(LBB))
12787 if (!ProvedEasily(L,
RHS))
12794bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12797 const SCEV *FoundLHS,
12798 const SCEV *FoundRHS) {
12801 if (
RHS == FoundRHS) {
12806 if (
LHS != FoundLHS)
12813 Value *Shiftee, *ShiftValue;
12815 using namespace PatternMatch;
12816 if (
match(SUFoundRHS->getValue(),
12818 auto *ShifteeS =
getSCEV(Shiftee);
12836bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12837 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12838 const SCEV *FoundRHS) {
12870 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12878 return Diff == FoundDiff;
12881bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12883 const SCEV *FoundLHS,
12884 const SCEV *FoundRHS,
12885 const Instruction *CtxI) {
12886 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12888 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12890 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12891 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12893 isImpliedCondOperandsViaMatchingDiff(Pred,
LHS,
RHS, FoundLHS,
12895 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12899template <
typename MinMaxExprType>
12901 const SCEV *Candidate) {
12906 return is_contained(MinMaxExpr->operands(), Candidate);
12919 const SCEV *LStart, *RStart, *Step;
12992bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12994 const SCEV *FoundLHS,
12995 const SCEV *FoundRHS,
12999 "LHS and RHS have different sizes?");
13002 "FoundLHS and FoundRHS have different sizes?");
13036 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
13038 return Ext->getOperand();
13045 auto *OrigLHS =
LHS;
13046 auto *OrigFoundLHS = FoundLHS;
13047 LHS = GetOpFromSExt(
LHS);
13048 FoundLHS = GetOpFromSExt(FoundLHS);
13051 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
13054 FoundRHS,
Depth + 1);
13067 if (!LHSAddExpr->hasNoSignedWrap())
13070 SCEVUse LL = LHSAddExpr->getOperand(0);
13071 SCEVUse LR = LHSAddExpr->getOperand(1);
13075 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
13076 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
13081 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
13087 using namespace llvm::PatternMatch;
13106 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13114 auto *DTy = Denominator->getType();
13115 auto *FRHSTy = FoundRHS->
getType();
13116 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13135 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13146 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13148 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13156 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13189bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13193 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13196 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13199bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13202 const SCEV *FoundLHS,
13203 const SCEV *FoundRHS) {
13239 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13245bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13246 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13247 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13261 ConstantRange FoundLHSRange =
13265 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13272 return LHSRange.
icmp(Pred, ConstRHS);
13275bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13288 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13296 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13299bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
13311 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
13319 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
13331const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
13332 const SCEV *Stride,
13363 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13374 :
APIntOps::umax(MaxEnd, MinStart);
13381ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13382 const Loop *L,
bool IsSigned,
13383 bool ControlsOnlyExit,
bool AllowPredicates) {
13387 bool PredicatedIV =
false;
13392 auto canProveNUW = [&]() {
13395 if (!ControlsOnlyExit)
13416 Limit = Limit.
zext(OuterBitWidth);
13428 Type *Ty = ZExt->getType();
13439 if (!
IV && AllowPredicates) {
13444 PredicatedIV =
true;
13448 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13462 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13465 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13470 if (!PositiveStride) {
13522 auto wouldZeroStrideBeUB = [&]() {
13534 if (!wouldZeroStrideBeUB()) {
13538 }
else if (!NoWrap) {
13541 if (canIVOverflowOnLT(
RHS, Stride, IsSigned))
13554 const SCEV *
Start =
IV->getStart();
13560 const SCEV *OrigStart =
Start;
13561 const SCEV *OrigRHS =
RHS;
13562 if (
Start->getType()->isPointerTy()) {
13573 const SCEV *End =
nullptr, *BECount =
nullptr,
13574 *BECountIfBackedgeTaken =
nullptr;
13577 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13578 any(RHSAddRec->getNoWrapFlags())) {
13591 const SCEV *RHSStart = RHSAddRec->getStart();
13592 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13604 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13613 BECountIfBackedgeTaken =
13618 if (BECount ==
nullptr) {
13623 const SCEV *MaxBECount = computeMaxBECountForLT(
13626 MaxBECount,
false , Predicates);
13633 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13660 const SCEV *Numerator =
13666 auto canProveRHSGreaterThanEqualStart = [&]() {
13685 auto *StartMinusOne =
13692 if (canProveRHSGreaterThanEqualStart()) {
13707 BECountIfBackedgeTaken =
13723 bool MayAddOverflow = [&] {
13769 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13783 if (!MayAddOverflow) {
13795 const SCEV *ConstantMaxBECount;
13796 bool MaxOrZero =
false;
13798 ConstantMaxBECount = BECount;
13799 }
else if (BECountIfBackedgeTaken &&
13804 ConstantMaxBECount = BECountIfBackedgeTaken;
13807 ConstantMaxBECount = computeMaxBECountForLT(
13815 const SCEV *SymbolicMaxBECount =
13817 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13821ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13822 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13823 bool ControlsOnlyExit,
bool AllowPredicates) {
13830 if (!
IV && AllowPredicates)
13837 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13841 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13854 if (!Stride->
isOne() && !NoWrap)
13855 if (canIVOverflowOnGT(
RHS, Stride, IsSigned))
13858 const SCEV *
Start =
IV->getStart();
13859 const SCEV *End =
RHS;
13870 if (
Start->getType()->isPointerTy()) {
13905 const SCEV *ConstantMaxBECount =
13912 ConstantMaxBECount = BECount;
13913 const SCEV *SymbolicMaxBECount =
13916 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13922 if (
Range.isFullSet())
13927 if (!SC->getValue()->isZero()) {
13933 return ShiftedAddRec->getNumIterationsInRange(
13934 Range.subtract(SC->getAPInt()), SE);
13965 APInt ExitVal = (End +
A).udiv(
A);
13978 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13979 "Linear scev computation is off in a bad way!");
14010 assert(!
Last->isZero() &&
"Recurrency with zero step?");
14036 Ty =
Store->getValueOperand()->getType();
14037 PtrTy =
Store->getPointerOperandType();
14039 Ty =
Load->getType();
14040 PtrTy =
Load->getPointerOperandType();
14054 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14056 SE->ConstantEvolutionLoopExitValue.erase(PN);
14057 SE->eraseValueFromMap(getValPtr());
14061void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
14062 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14072 : CallbackVH(
V), SE(se) {}
14081 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
14083 LoopDispositions(64), BlockDispositions(64) {
14095 F.getParent(), Intrinsic::experimental_guard);
14096 HasGuards = GuardDecl && !GuardDecl->use_empty();
14100 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
14101 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14102 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14103 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14104 PendingMerges(
std::
move(Arg.PendingMerges)),
14105 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14106 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14107 PredicatedBackedgeTakenCounts(
14108 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14109 BECountUsers(
std::
move(Arg.BECountUsers)),
14110 ConstantEvolutionLoopExitValue(
14111 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14112 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14113 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14114 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14115 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14116 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14117 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14118 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14119 SignedRanges(
std::
move(Arg.SignedRanges)),
14120 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14121 UniquePreds(
std::
move(Arg.UniquePreds)),
14122 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14123 ConstantSCEVs(
std::
move(Arg.ConstantSCEVs)),
14124 LoopUsers(
std::
move(Arg.LoopUsers)),
14125 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14126 FirstUnknown(Arg.FirstUnknown) {
14127 Arg.FirstUnknown =
nullptr;
14136 Tmp->~SCEVUnknown();
14138 FirstUnknown =
nullptr;
14140 ExprValueMap.clear();
14141 ValueExprMap.clear();
14143 BackedgeTakenCounts.clear();
14144 PredicatedBackedgeTakenCounts.clear();
14146 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14147 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14148 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14149 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14171 L->getHeader()->printAsOperand(OS,
false);
14175 L->getExitingBlocks(ExitingBlocks);
14176 if (ExitingBlocks.
size() != 1)
14177 OS <<
"<multiple exits> ";
14181 OS <<
"backedge-taken count is ";
14184 OS <<
"Unpredictable backedge-taken count.";
14187 if (ExitingBlocks.
size() > 1)
14188 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14189 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14197 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14200 OS <<
"\n Predicates:\n";
14201 for (
const auto *
P : Predicates)
14209 L->getHeader()->printAsOperand(OS,
false);
14214 OS <<
"constant max backedge-taken count is ";
14217 OS <<
", actual taken count either this or zero.";
14219 OS <<
"Unpredictable constant max backedge-taken count. ";
14224 L->getHeader()->printAsOperand(OS,
false);
14229 OS <<
"symbolic max backedge-taken count is ";
14232 OS <<
", actual taken count either this or zero.";
14234 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14238 if (ExitingBlocks.
size() > 1)
14239 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14240 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14250 OS <<
"\n predicated symbolic max exit count for "
14251 << ExitingBlock->
getName() <<
": ";
14253 OS <<
"\n Predicates:\n";
14254 for (
const auto *
P : Predicates)
14265 L->getHeader()->printAsOperand(OS,
false);
14268 OS <<
"Predicated backedge-taken count is ";
14271 OS <<
"Unpredictable predicated backedge-taken count.";
14273 OS <<
" Predicates:\n";
14274 for (
const auto *
P : Preds)
14279 auto *PredConstantMax =
14281 if (PredConstantMax != ConstantBTC) {
14283 L->getHeader()->printAsOperand(OS,
false);
14286 OS <<
"Predicated constant max backedge-taken count is ";
14289 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14291 OS <<
" Predicates:\n";
14292 for (
const auto *
P : Preds)
14297 auto *PredSymbolicMax =
14299 if (SymbolicBTC != PredSymbolicMax) {
14301 L->getHeader()->printAsOperand(OS,
false);
14304 OS <<
"Predicated symbolic max backedge-taken count is ";
14307 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14309 OS <<
" Predicates:\n";
14310 for (
const auto *
P : Preds)
14316 L->getHeader()->printAsOperand(OS,
false);
14343 OS <<
"Computable";
14353 OS <<
"DoesNotDominate";
14359 OS <<
"ProperlyDominates";
14376 OS <<
"Classifying expressions for: ";
14377 F.printAsOperand(OS,
false);
14392 const Loop *L = LI.getLoopFor(
I.getParent());
14407 OS <<
"\t\t" "Exits: ";
14410 OS <<
"<<Unknown>>";
14416 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14418 Iter->getHeader()->printAsOperand(OS,
false);
14426 InnerL->getHeader()->printAsOperand(OS,
false);
14437 OS <<
"Determining loop execution counts for: ";
14438 F.printAsOperand(OS,
false);
14446 auto &
Values = LoopDispositions[S];
14447 for (
auto &V :
Values) {
14448 if (V.getPointer() == L)
14453 auto &Values2 = LoopDispositions[S];
14455 if (V.getPointer() == L) {
14464ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14482 if (L->contains(AR->
getLoop()) &&
14484 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14489 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14490 " dominate the contained loop's header?");
14517 bool HasVarying =
false;
14518 bool HasUniform =
false;
14560 auto &
Values = BlockDispositions[S];
14561 for (
auto &V :
Values) {
14562 if (V.getPointer() == BB)
14567 auto &Values2 = BlockDispositions[S];
14569 if (V.getPointer() == BB) {
14578ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14607 bool Proper =
true;
14618 if (Instruction *
I =
14620 if (
I->getParent() == BB)
14622 if (DT.properlyDominates(
I->getParent(), BB))
14645void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14648 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14649 auto It = BECounts.find(L);
14650 if (It != BECounts.end()) {
14651 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14652 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14654 auto UserIt = BECountUsers.find(S);
14655 assert(UserIt != BECountUsers.end());
14660 BECounts.erase(It);
14668 while (!Worklist.
empty()) {
14670 auto Users = SCEVUsers.find(Curr);
14671 if (
Users != SCEVUsers.end())
14672 for (
const auto *User :
Users->second)
14673 if (ToForget.
insert(User).second)
14677 for (
const auto *S : ToForget)
14678 forgetMemoizedResultsImpl(S);
14680 PredicatedSCEVRewrites.remove_if(
14681 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14684void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14685 LoopDispositions.erase(S);
14686 BlockDispositions.erase(S);
14687 UnsignedRanges.erase(S);
14688 SignedRanges.erase(S);
14689 HasRecMap.erase(S);
14690 ConstantMultipleCache.erase(S);
14693 UnsignedWrapViaInductionTried.erase(AR);
14694 SignedWrapViaInductionTried.erase(AR);
14697 auto ExprIt = ExprValueMap.find(S);
14698 if (ExprIt != ExprValueMap.end()) {
14699 for (
Value *V : ExprIt->second) {
14700 auto ValueIt = ValueExprMap.find_as(V);
14701 if (ValueIt != ValueExprMap.end())
14702 ValueExprMap.erase(ValueIt);
14704 ExprValueMap.erase(ExprIt);
14707 auto ScopeIt = ValuesAtScopes.find(S);
14708 if (ScopeIt != ValuesAtScopes.end()) {
14709 for (
const auto &Pair : ScopeIt->second)
14712 std::make_pair(Pair.first, S));
14713 ValuesAtScopes.erase(ScopeIt);
14716 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14717 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14718 for (
const auto &Pair : ScopeUserIt->second)
14719 llvm::erase(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
14720 ValuesAtScopesUsers.erase(ScopeUserIt);
14723 auto BEUsersIt = BECountUsers.find(S);
14724 if (BEUsersIt != BECountUsers.end()) {
14726 auto Copy = BEUsersIt->second;
14727 for (
const auto &Pair : Copy)
14728 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14729 BECountUsers.erase(BEUsersIt);
14732 auto FoldUser = FoldCacheUser.find(S);
14733 if (FoldUser != FoldCacheUser.end())
14734 for (
auto &KV : FoldUser->second)
14735 FoldCache.erase(KV);
14736 FoldCacheUser.erase(S);
14740ScalarEvolution::getUsedLoops(
const SCEV *S,
14742 struct FindUsedLoops {
14743 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14744 : LoopsUsed(LoopsUsed) {}
14745 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14746 bool follow(
const SCEV *S) {
14752 bool isDone()
const {
return false; }
14755 FindUsedLoops
F(LoopsUsed);
14756 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14759void ScalarEvolution::getReachableBlocks(
14762 Worklist.
push_back(&F.getEntryBlock());
14763 while (!Worklist.
empty()) {
14765 if (!Reachable.
insert(BB).second)
14773 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14780 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14784 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14819 SCEVMapper SCM(SE2);
14821 SE2.getReachableBlocks(ReachableBlocks, F);
14823 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14841 while (!LoopStack.
empty()) {
14847 if (!ReachableBlocks.
contains(L->getHeader()))
14852 auto It = BackedgeTakenCounts.find(L);
14853 if (It == BackedgeTakenCounts.end())
14857 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14877 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14878 if (Delta && !Delta->
isZero()) {
14879 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14880 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14881 dbgs() <<
"New: " << *NewBECount <<
"\n";
14882 dbgs() <<
"Delta: " << *Delta <<
"\n";
14890 while (!Worklist.
empty()) {
14892 if (ValidLoops.
insert(L).second)
14893 Worklist.
append(L->begin(), L->end());
14895 for (
const auto &KV : ValueExprMap) {
14900 "AddRec references invalid loop");
14905 auto It = ExprValueMap.find(KV.second);
14906 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14907 dbgs() <<
"Value " << *KV.first
14908 <<
" is in ValueExprMap but not in ExprValueMap\n";
14913 if (!ReachableBlocks.
contains(
I->getParent()))
14915 const SCEV *OldSCEV = SCM.visit(KV.second);
14917 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14918 if (Delta && !Delta->
isZero()) {
14919 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14920 <<
"Old: " << *OldSCEV <<
"\n"
14921 <<
"New: " << *NewSCEV <<
"\n"
14922 <<
"Delta: " << *Delta <<
"\n";
14928 for (
const auto &KV : ExprValueMap) {
14929 for (
Value *V : KV.second) {
14930 const SCEV *S = ValueExprMap.lookup(V);
14932 dbgs() <<
"Value " << *V
14933 <<
" is in ExprValueMap but not in ValueExprMap\n";
14936 if (S != KV.first) {
14937 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14938 << *KV.first <<
"\n";
14945 for (
const auto &S : UniqueSCEVs) {
14950 auto It = SCEVUsers.find(
Op);
14951 if (It != SCEVUsers.end() && It->second.count(&S))
14953 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14954 <<
" is not being tracked!\n";
14960 for (
const auto &ValueAndVec : ValuesAtScopes) {
14962 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14963 const Loop *L = LoopAndValueAtScope.first;
14964 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
14966 auto It = ValuesAtScopesUsers.find(ValueAtScope);
14967 if (It != ValuesAtScopesUsers.end() &&
14970 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14971 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14977 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14978 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14979 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14980 const Loop *L = LoopAndValue.first;
14981 const SCEV *
Value = LoopAndValue.second;
14983 auto It = ValuesAtScopes.find(
Value);
14984 if (It != ValuesAtScopes.end() &&
14985 is_contained(It->second, std::make_pair(L, ValueAtScope)))
14987 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14988 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14994 auto VerifyBECountUsers = [&](
bool Predicated) {
14996 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14997 for (
const auto &LoopAndBEInfo : BECounts) {
14998 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14999 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
15001 auto UserIt = BECountUsers.find(S);
15002 if (UserIt != BECountUsers.end() &&
15003 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
15005 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
15006 <<
" missing from BECountUsers\n";
15013 VerifyBECountUsers(
false);
15014 VerifyBECountUsers(
true);
15017 for (
auto &[S,
Values] : LoopDispositions) {
15018 for (
auto [
Loop, CachedDisposition] :
Values) {
15020 if (CachedDisposition != RecomputedDisposition) {
15021 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
15022 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
15023 << RecomputedDisposition <<
"\n";
15030 for (
auto &[S,
Values] : BlockDispositions) {
15031 for (
auto [BB, CachedDisposition] :
Values) {
15033 if (CachedDisposition != RecomputedDisposition) {
15034 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
15035 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
15036 <<
", actual " << RecomputedDisposition <<
"\n";
15043 for (
auto [
FoldID, Expr] : FoldCache) {
15044 auto I = FoldCacheUser.find(Expr);
15045 if (
I == FoldCacheUser.end()) {
15046 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
15051 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
15055 for (
auto [Expr, IDs] : FoldCacheUser) {
15056 for (
auto &
FoldID : IDs) {
15059 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
15064 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
15065 <<
" != " << *Expr <<
"!\n";
15076 for (
auto [S, Multiple] : ConstantMultipleCache) {
15078 if ((Multiple != 0 && RecomputedMultiple != 0 &&
15079 Multiple.
urem(RecomputedMultiple) != 0 &&
15080 RecomputedMultiple.
urem(Multiple) != 0)) {
15081 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
15082 << *S <<
" : Computed " << RecomputedMultiple
15083 <<
" but cache contains " << Multiple <<
"!\n";
15091 FunctionAnalysisManager::Invalidator &Inv) {
15123 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15124 <<
F.getName() <<
"':\n";
15130 "Scalar Evolution Analysis",
false,
true)
15179 const SCEV *LHS,
const SCEV *RHS) {
15181 assert(LHS->getType() == RHS->getType() &&
15182 "Type mismatch between LHS and RHS");
15185 ID.AddInteger(Pred);
15186 ID.AddPointer(LHS);
15187 ID.AddPointer(RHS);
15188 void *IP =
nullptr;
15189 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(ID, IP))
15193 UniquePreds.InsertNode(Eq, IP);
15204 ID.AddInteger(AddedFlags);
15205 void *IP =
nullptr;
15206 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(ID, IP))
15208 auto *OF =
new (SCEVAllocator)
15210 UniquePreds.InsertNode(OF, IP);
15230 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15231 return Rewriter.visit(S);
15237 for (
const auto *Pred : U->getPredicates())
15239 if (IPred->getLHS() == Expr &&
15241 return IPred->getRHS();
15243 if (IPred->getLHS() == Expr &&
15244 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15245 return IPred->getRHS();
15248 return convertToAddRecWithPreds(Expr);
15251 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15267 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15284 explicit SCEVPredicateRewriter(
15285 const Loop *L, ScalarEvolution &SE,
15286 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15287 const SCEVPredicate *Pred)
15288 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15290 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15293 return Pred && Pred->
implies(
P, SE);
15299 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15302 return addOverflowAssumption(
A);
15311 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15315 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15317 if (!PredicatedRewrite)
15319 for (
const auto *
P : PredicatedRewrite->second){
15322 if (L != WP->getExpr()->getLoop())
15325 if (!addOverflowAssumption(
P))
15328 return PredicatedRewrite->first;
15331 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15332 const SCEVPredicate *Pred;
15341 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15348 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15368 if (!Step->
isOne())
15393 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15394 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15407 return Op->LHS == LHS &&
Op->RHS == RHS;
15414 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15416 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15441 const SCEV *Start = AR->getStart();
15442 const SCEV *OpStart =
Op->AR->getStart();
15447 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15456 const SCEV *Step = AR->getStepRecurrence(SE);
15457 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15510 if (Step->getValue()->getValue().isNonNegative())
15514 return ImpliedFlags;
15521 for (
const auto *
P : Preds)
15534 return this->implies(I, SE);
15546 const Loop *L = NWrap->getExpr()->getLoop();
15553 return RewrittenAR &&
15559 for (
const auto *Pred : Preds)
15560 Pred->print(OS,
Depth);
15565 for (
const auto *Pred : Set->Preds)
15573 bool CheckImplies = Preds.
size() < 16;
15576 if (CheckImplies &&
implies(
N, SE))
15582 for (
auto *
P : Preds) {
15583 if (CheckImplies &&
N->implies(
P, SE))
15587 Preds = std::move(PrunedPreds);
15588 Preds.push_back(
N);
15595 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15600 for (
const auto *
Op :
Ops)
15605 SCEVUsers[
Op].insert(
User);
15614 SCEVUsers[
Op].insert(
User);
15618 const SCEV *Expr = SE.getSCEV(V);
15623 RewriteEntry &Entry = RewriteMap[Expr];
15626 if (Entry.second && Generation == Entry.first)
15627 return Entry.second;
15632 Expr = Entry.second;
15634 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15635 Entry = {Generation, NewSCEV};
15641 if (!BackedgeCount) {
15643 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15644 for (
const auto *
P : Preds)
15647 return BackedgeCount;
15651 if (!SymbolicMaxBackedgeCount) {
15653 SymbolicMaxBackedgeCount =
15654 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15655 for (
const auto *
P : Preds)
15658 return SymbolicMaxBackedgeCount;
15662 if (!SmallConstantMaxTripCount) {
15664 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15665 for (
const auto *
P : Preds)
15668 return *SmallConstantMaxTripCount;
15672 if (Preds->implies(&Pred, SE))
15677 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15678 updateGeneration();
15691void PredicatedScalarEvolution::updateGeneration() {
15693 if (++Generation == 0) {
15694 for (
auto &
II : RewriteMap) {
15695 const SCEV *Rewritten =
II.second.second;
15717 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15723 ExtraPreds->
append(NewPreds);
15729 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15735 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15738 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15742 for (
auto *BB : L.getBlocks())
15743 for (
auto &
I : *BB) {
15744 if (!SE.isSCEVable(
I.getType()))
15747 auto *Expr = SE.getSCEV(&
I);
15748 auto II = RewriteMap.find(Expr);
15750 if (
II == RewriteMap.end())
15754 if (
II->second.second == Expr)
15759 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15767 LoopGuards Guards(SE);
15775void ScalarEvolution::LoopGuards::collectFromPHI(
15783 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15784 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15798 auto &RewriteMap =
G->second.RewriteMap;
15799 if (RewriteMap.empty())
15801 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15802 if (S == RewriteMap.end())
15808 return {C0,
SM->getSCEVType()};
15811 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15812 MinMaxPattern
P2) -> MinMaxPattern {
15813 auto [C1,
T1] =
P1;
15814 auto [C2, T2] =
P2;
15815 if (!C1 || !C2 ||
T1 != T2)
15819 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15821 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15823 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15825 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15830 auto P = GetMinMaxConst(0);
15831 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15834 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15837 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15840 Guards.RewriteMap.insert({
LHS,
RHS});
15848 const APInt &DivisorVal,
15850 const APInt *ExprVal;
15863 const APInt &DivisorVal,
15865 const APInt *ExprVal;
15873 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15887 const SCEV *URemRHS =
nullptr;
15891 const SCEV *Multiple =
15893 DivInfo[URemLHS] = Multiple;
15895 Multiples[URemLHS] =
C->getAPInt();
15915 auto IsMinMaxSCEVWithNonNegativeConstant =
15919 if (
MinMax->getNumOperands() != 2)
15922 if (
C->getAPInt().isNegative())
15924 SCTy =
MinMax->getSCEVType();
15933 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15935 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15940 auto *DivisibleExpr =
15948void ScalarEvolution::LoopGuards::collectFromBlock(
15950 const BasicBlock *
Block,
const BasicBlock *Pred,
15958 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15969 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15971 if (From == FromRewritten)
15973 RewriteMap[From] = To;
15979 auto GetMaybeRewritten = [&](
const SCEV *S) {
15980 return RewriteMap.lookup_or(S, S);
15987 const SCEV *MatchLHS,
15988 const SCEV *MatchRHS) {
15989 const SCEVConstant *C1;
15992 if (!
match(MatchLHS,
16004 const SCEV *RewrittenLHS = GetMaybeRewritten(LHSUnknown);
16005 ExactRegion = ExactRegion.intersectWith(SE.
getUnsignedRange(RewrittenLHS),
16010 if (ExactRegion.isEmptySet() || ExactRegion.isWrappedSet() ||
16011 ExactRegion.isFullSet())
16014 const SCEV *RegionMin = SE.
getConstant(ExactRegion.getUnsignedMin());
16015 const SCEV *RegionMax = SE.
getConstant(ExactRegion.getUnsignedMax());
16016 const SCEV *ClampedLHS =
16018 AddRewrite(LHSUnknown, RewrittenLHS, ClampedLHS);
16021 if (MatchRangeCheckIdiom(Predicate,
LHS,
RHS))
16034 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
16036 const APInt &DividesBy =
16051 switch (Predicate) {
16080 SmallPtrSet<const SCEV *, 16> Visited;
16082 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
16086 while (!Worklist.
empty()) {
16090 if (!Visited.
insert(From).second)
16092 const SCEV *FromRewritten = GetMaybeRewritten(From);
16093 const SCEV *To =
nullptr;
16095 switch (Predicate) {
16100 EnqueueOperands(
UMax);
16106 EnqueueOperands(
SMax);
16112 EnqueueOperands(
UMin);
16118 EnqueueOperands(
SMin);
16126 const SCEV *OneAlignedUp =
16128 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16140 const SCEVConstant *
C;
16149 Guards.NotEqual.insert({
LHS,
RHS});
16158 AddRewrite(From, FromRewritten, To);
16175 SE.F.
getParent(), Intrinsic::experimental_guard);
16177 for (
const auto *GU : GuardDecl->users())
16179 if (Guard->getFunction() ==
Block->getParent() &&
16188 unsigned NumCollectedConditions = 0;
16190 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16192 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16194 const CondBrInst *LoopEntryPredicate =
16196 if (!LoopEntryPredicate)
16201 NumCollectedConditions++;
16205 if (
Depth > 0 && NumCollectedConditions == 2)
16213 if (Pair.second->hasNPredecessorsOrMore(2) &&
16215 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16216 for (
auto &Phi : Pair.second->phis())
16227 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16228 SmallVector<Value *, 8> Worklist;
16229 SmallPtrSet<Value *, 8> Visited;
16231 while (!Worklist.
empty()) {
16238 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16262 DenseMap<const SCEV *, APInt> Multiples;
16264 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16271 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16272 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16276 for (
const auto &[K, Divisor] : Multiples) {
16277 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16278 Guards.RewriteMap[
K] =
16280 Guards.
rewrite(K), Divisor, SE),
16289 Guards.PreserveNUW =
true;
16290 Guards.PreserveNSW =
true;
16291 for (
const SCEV *Expr : ExprsToRewrite) {
16292 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16293 Guards.PreserveNUW &=
16295 Guards.PreserveNSW &=
16302 if (ExprsToRewrite.size() > 1) {
16303 for (
const SCEV *Expr : ExprsToRewrite) {
16304 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16305 Guards.RewriteMap.erase(Expr);
16306 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16315 class SCEVLoopGuardRewriter
16326 NotEqual(Guards.NotEqual) {
16327 if (Guards.PreserveNUW)
16329 if (Guards.PreserveNSW)
16336 return Map.lookup_or(Expr, Expr);
16340 if (
const SCEV *S = Map.lookup(Expr))
16347 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16348 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16349 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16351 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16352 if (
const SCEV *S = Map.lookup(NarrowExt))
16353 return SE.getZeroExtendExpr(S, Ty);
16354 Bitwidth = Bitwidth / 2;
16362 if (
const SCEV *S = Map.lookup(Expr))
16369 if (
const SCEV *S = Map.lookup(Expr))
16375 if (
const SCEV *S = Map.lookup(Expr))
16381 if (
const SCEV *S = Map.lookup(Expr))
16386 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16391 if (NotEqual.contains({LHS, RHS})) {
16393 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16394 return SE.getUMaxExpr(OneAlignedUp, S);
16401 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16412 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16413 return SE.getAddExpr(
16416 if (
const SCEV *S = Map.lookup(
Add))
16417 return SE.getAddExpr(Expr->
getOperand(0), S);
16425 const SCEV *S =
nullptr;
16432 S = Map.lookup(SE.getAddExpr(NewC, Expr->
getOperand(1)));
16435 return SE.getAddExpr(S, SE.getMinusOne(Expr->
getType()));
16448 : SE.getAddExpr(Operands,
16464 : SE.getMulExpr(Operands,
16470 if (RewriteMap.empty() && NotEqual.empty())
16473 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16474 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< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
static bool isSigned(unsigned Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
Value * getPointer(Value *Ptr)
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
static constexpr Value * getValue(Ty &ValueOrUse)
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
MachineInstr unsigned OpIdx
static constexpr unsigned SM(unsigned Version)
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
PowerPC Reduce CR logical Operation
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
const SmallVectorImpl< MachineOperand > & Cond
static DominatorTree getDomTree(Function &F)
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
SI optimize exec mask operations pre RA
static void visit(BasicBlock &Start, std::function< bool(BasicBlock *)> op)
This file provides utility classes that use RAII to save and restore values.
bool SCEVMinMaxExprContains(const SCEV *Root, const SCEV *OperandToFind, SCEVTypes RootKind)
static cl::opt< unsigned > MaxAddRecSize("scalar-evolution-max-add-rec-size", cl::Hidden, cl::desc("Max coefficients in AddRec during evolving"), cl::init(8))
static cl::opt< unsigned > RangeIterThreshold("scev-range-iter-threshold", cl::Hidden, cl::desc("Threshold for switching to iteratively computing SCEV ranges"), cl::init(32))
static const Loop * isIntegerLoopHeaderPHI(const PHINode *PN, LoopInfo &LI)
static unsigned getConstantTripCount(const SCEVConstant *ExitCount)
static int CompareValueComplexity(const LoopInfo *const LI, Value *LV, Value *RV, unsigned Depth)
Compare the two values LV and RV in terms of their "complexity" where "complexity" is a partial (and ...
static const SCEV * getNextSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static void 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 hasHugeExpression(ArrayRef< SCEVUse > Ops)
Returns true if Ops contains a huge SCEV (the subtree of S contains at least HugeExprThreshold nodes)...
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 RangeRefPHIAllowedOperands(DominatorTree &DT, PHINode *PHI)
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 BinaryOperator * getCommonInstForPHI(PHINode *PN)
static bool isDivisibilityGuard(const SCEV *LHS, const SCEV *RHS, ScalarEvolution &SE)
static std::optional< const SCEV * > createNodeForSelectViaUMinSeq(ScalarEvolution *SE, const SCEV *CondExpr, const SCEV *TrueExpr, const SCEV *FalseExpr)
static Constant * BuildConstantFromSCEV(const SCEV *V)
This builds up a Constant using the ConstantExpr interface.
static ConstantInt * EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C, ScalarEvolution &SE)
static const SCEV * BinomialCoefficient(const SCEV *It, unsigned K, ScalarEvolution &SE, Type *ResultTy)
Compute BC(It, K). The result has width W. Assume, K > 0.
static cl::opt< unsigned > MaxCastDepth("scalar-evolution-max-cast-depth", cl::Hidden, cl::desc("Maximum depth of recursive SExt/ZExt/Trunc"), cl::init(8))
static bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr, const SCEV *Candidate)
Is MaybeMinMaxExpr an (U|S)(Min|Max) of Candidate and some other values?
static PHINode * getConstantEvolvingPHI(Value *V, const Loop *L)
getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node in the loop that V is deri...
static const SCEV * SolveLinEquationWithOverflow(const APInt &A, const SCEV *B, SmallVectorImpl< const SCEVPredicate * > *Predicates, ScalarEvolution &SE, const Loop *L)
Finds the minimum unsigned root of the following equation:
static cl::opt< unsigned > MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, cl::desc("Maximum number of iterations SCEV will " "symbolically execute a constant " "derived loop"), cl::init(100))
static 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 SCEV::NoWrapFlags StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, ArrayRef< SCEVUse > Ops, SCEV::NoWrapFlags Flags)
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 CollectAddOperandsWithScales(SmallDenseMap< SCEVUse, APInt, 16 > &M, SmallVectorImpl< SCEVUse > &NewOps, APInt &AccumulatedConstant, ArrayRef< SCEVUse > 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 const SCEV * constantFoldAndGroupOps(ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT, SmallVectorImpl< SCEVUse > &Ops, FoldT Fold, IsIdentityT IsIdentity, IsAbsorberT IsAbsorber)
Performs a number of common optimizations on the passed Ops.
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 void GroupByComplexity(SmallVectorImpl< SCEVUse > &Ops, LoopInfo *LI, DominatorTree &DT)
Given a list of SCEV objects, order them by their complexity, and group objects of the same complexit...
static bool collectDivisibilityInformation(ICmpInst::Predicate Predicate, const SCEV *LHS, const SCEV *RHS, DenseMap< const SCEV *, const SCEV * > &DivInfo, DenseMap< const SCEV *, APInt > &Multiples, ScalarEvolution &SE)
static cl::opt< unsigned > MaxSCEVOperationsImplicationDepth("scalar-evolution-max-scev-operations-implication-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV operations implication analysis"), cl::init(2))
static void PushDefUseChildren(Instruction *I, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push users of the given Instruction onto the given Worklist.
static std::optional< APInt > SolveQuadraticAddRecRange(const SCEVAddRecExpr *AddRec, const ConstantRange &Range, ScalarEvolution &SE)
Let c(n) be the value of the quadratic chrec {0,+,M,+,N} after n iterations.
static cl::opt< bool > UseContextForNoWrapFlagInference("scalar-evolution-use-context-for-no-wrap-flag-strenghening", cl::Hidden, cl::desc("Infer nuw/nsw flags using context where suitable"), cl::init(true))
static cl::opt< bool > EnableFiniteLoopControl("scalar-evolution-finite-loop", cl::Hidden, cl::desc("Handle <= and >= in finite loops"), cl::init(true))
static bool getOperandsForSelectLikePHI(DominatorTree &DT, PHINode *PN, Value *&Cond, Value *&LHS, Value *&RHS)
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 bool MatchBinarySub(const SCEV *S, SCEVUse &LHS, SCEVUse &RHS)
static std::optional< ConstantRange > GetRangeFromMetadata(Value *V)
Helper method to assign a range to V from metadata present in the IR.
static cl::opt< unsigned > HugeExprThreshold("scalar-evolution-huge-expr-threshold", cl::Hidden, cl::desc("Size of the expression which is considered huge"), cl::init(4096))
static Type * isSimpleCastedPHI(const SCEV *Op, const SCEVUnknown *SymbolicPHI, bool &Signed, ScalarEvolution &SE)
Helper function to createAddRecFromPHIWithCasts.
static Constant * EvaluateExpression(Value *V, const Loop *L, DenseMap< Instruction *, Constant * > &Vals, const DataLayout &DL, const TargetLibraryInfo *TLI)
EvaluateExpression - Given an expression that passes the getConstantEvolvingPHI predicate,...
static const SCEV * getPreviousSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static const SCEV * MatchNotExpr(const SCEV *Expr)
If Expr computes ~A, return A else return nullptr.
static std::pair< ConstantRange, bool > getRangeForAffineARHelper(APInt Step, const ConstantRange &StartRange, const APInt &MaxBECount, bool Signed)
static cl::opt< unsigned > MaxValueCompareDepth("scalar-evolution-max-value-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive value complexity comparisons"), cl::init(2))
static const SCEV * applyDivisibilityOnMinMaxExpr(const SCEV *MinMaxExpr, APInt Divisor, ScalarEvolution &SE)
static cl::opt< bool, true > VerifySCEVOpt("verify-scev", cl::Hidden, cl::location(VerifySCEV), cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"))
static const SCEV * getSignedOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static cl::opt< unsigned > MaxArithDepth("scalar-evolution-max-arith-depth", cl::Hidden, cl::desc("Maximum depth of recursive arithmetics"), cl::init(32))
static bool HasSameValue(const SCEV *A, const SCEV *B)
SCEV structural equivalence is usually sufficient for testing whether two expressions are equal,...
static uint64_t Choose(uint64_t n, uint64_t k, bool &Overflow)
Compute the result of "n choose k", the binomial coefficient.
static std::optional< int > CompareSCEVComplexity(const LoopInfo *const LI, const SCEV *LHS, const SCEV *RHS, DominatorTree &DT, unsigned Depth=0)
static bool 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?
static bool BrPHIToSelect(DominatorTree &DT, CondBrInst *BI, PHINode *Merge, Value *&C, Value *&LHS, Value *&RHS)
This file defines the scope_exit class, which executes user-defined cleanup logic at scope exit.
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 SymbolRef::Type getType(const Symbol *Sym)
LocallyHashedType DenseMapInfo< LocallyHashedType >::Empty
static std::optional< bool > isImpliedCondOperands(CmpInst::Predicate Pred, const Value *ALHS, const Value *ARHS, const Value *BLHS, const Value *BRHS)
Return true if "icmp Pred BLHS BRHS" is true whenever "icmp PredALHS ARHS" is true.
Virtual Register Rewriter
static const uint32_t IV[8]
SCEVCastSinkingRewriter(ScalarEvolution &SE, Type *TargetTy, ConversionFn CreatePtrCast)
static const SCEV * rewrite(const SCEV *Scev, ScalarEvolution &SE, Type *TargetTy, ConversionFn CreatePtrCast)
const SCEV * visitUnknown(const SCEVUnknown *Expr)
const SCEV * visitMulExpr(const SCEVMulExpr *Expr)
const SCEV * visitAddExpr(const SCEVAddExpr *Expr)
const SCEV * visit(const SCEV *S)
Class for arbitrary precision integers.
LLVM_ABI APInt umul_ov(const APInt &RHS, bool &Overflow) const
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
uint64_t getZExtValue() const
Get zero extended value.
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.
LLVM_ABI APInt uadd_ov(const APInt &RHS, bool &Overflow) const
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
bool isNonPositive() const
Determine if this APInt Value is non-positive (<= 0).
unsigned countTrailingZeros() const
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
unsigned logBase2() const
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
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.
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
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()
Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
Get the array size.
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
MutableArrayRef< WeakVH > assumptions()
Access the list of assumption handles currently tracked for this function.
LLVM 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; assumes that the block is well-formed.
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
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.
Conditional Branch instruction.
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
static LLVM_ABI Constant * getNot(Constant *C)
static Constant * getPtrAdd(Constant *Ptr, Constant *Offset, GEPNoWrapFlags NW=GEPNoWrapFlags::none(), std::optional< ConstantRange > InRange=std::nullopt, Type *OnlyIfReduced=nullptr)
Create a getelementptr i8, ptr, offset constant expression.
static LLVM_ABI Constant * getPtrToAddr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static LLVM_ABI Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
static LLVM_ABI Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
This is the shared class of boolean and integer constants.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
static LLVM_ABI ConstantInt * getBool(LLVMContext &Context, bool V)
This class represents a range of values.
LLVM_ABI ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
LLVM_ABI ConstantRange zextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
PreferredRangeType
If represented precisely, the result of some range operations may consist of multiple disjoint ranges...
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI ConstantRange urem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned remainder operation of...
LLVM_ABI bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
LLVM_ABI bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other?
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI ConstantRange zeroExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
LLVM_ABI bool isSignWrappedSet() const
Return true if this set wraps around the signed domain.
LLVM_ABI APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
LLVM_ABI bool isWrappedSet() const
Return true if this set wraps around the unsigned domain.
LLVM_ABI void print(raw_ostream &OS) const
Print out the bounds to a stream.
LLVM_ABI ConstantRange truncate(uint32_t BitWidth, unsigned NoWrapKind=0) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
LLVM_ABI ConstantRange signExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI bool contains(const APInt &Val) const
Return true if the specified value is in the set.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
LLVM_ABI ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
LLVM_ABI APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
static LLVM_ABI ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
LLVM_ABI unsigned getMinSignedBits() const
Compute the maximal number of bits needed to represent every value in this signed range.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
LLVM_ABI ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
LLVM_ABI ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
static LLVM_ABI ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)
Produce the range that contains X if and only if "X BinOp Other" does not wrap.
This is an important base class in LLVM.
A parsed version of the target data layout string in and methods for querying it.
LLVM_ABI const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
LLVM_ABI 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
Return the entry for the specified key, or a default constructed value if no such entry exists.
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.
This class describes a reference to an interned FoldingSetNodeID, which can be a useful to store node...
This class is used to gather all the unique data bits of a node.
void AddInteger(signed I)
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)
bool isEquality() const
Return true if this predicate is either EQ or NE.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
static bool isLE(Predicate P)
Return true if the predicate is SLE or ULE.
LLVM_ABI bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
LLVM_ABI bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
LLVM_ABI bool isIdenticalToWhenDefined(const Instruction *I, bool IntersectAttrs=false) const LLVM_READONLY
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...
Class to represent integer types.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
A helper class to return the specified delimiter string after the first invocation of operator String...
An instruction for reading from memory.
Analysis pass that exposes the LoopInfo for a function.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within 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 LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
LLVM_ABI void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
LLVM_ABI const SCEVPredicate & getPredicate() const
LLVM_ABI const SCEV * getPredicatedSCEV(const SCEV *Expr)
Returns the rewritten SCEV for Expr in the context of the current SCEV predicate.
LLVM_ABI bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2, ArrayRef< const SCEVPredicate * > ExtraPreds={}) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds and ExtraPreds.
LLVM_ABI bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've statically proved that V doesn't wrap.
LLVM_ABI const SCEVAddRecExpr * getAsAddRec(Value *V, SmallVectorImpl< const SCEVPredicate * > *WrapPredsAdded=nullptr)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
LLVM_ABI void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
LLVM_ABI PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
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 void addPredicates(ArrayRef< const SCEVPredicate * > Preds)
Adds all predicates in Preds.
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
LLVM_ABI const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
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
SCEVUse getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
This is the base class for unary cast operator classes.
SCEVUse getOperand() const
LLVM_ABI SCEVCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, SCEVUse 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, SCEVUse 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
ArrayRef< SCEVUse > operands() const
bool hasNoSelfWrap() const
size_t getNumOperands() const
bool hasNoSignedWrap() const
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
SCEVUse getOperand(unsigned i) const
This class represents an assumption made using SCEV expressions which can be checked at run-time.
SCEVPredicate(const SCEVPredicate &)=default
virtual bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const =0
Returns true if this predicate implies N.
This class represents a cast from a pointer to a pointer-sized integer value, without capturing the p...
This visitor recursively visits a SCEV expression and re-writes it.
const SCEV * visitSignExtendExpr(const SCEVSignExtendExpr *Expr)
const SCEV * visit(const SCEV *S)
const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)
const SCEV * visitSMinExpr(const SCEVSMinExpr *Expr)
SCEVRewriteVisitor(ScalarEvolution &SE)
const SCEV * visitUMinExpr(const SCEVUMinExpr *Expr)
This class represents a signed minimum selection.
This node is the base class for sequential/in-order min/max selections.
static SCEVTypes getEquivalentNonSequentialSCEVType(SCEVTypes Ty)
This class represents a sign extension of a small integer value to a larger integer value.
Visit all nodes in the expression tree using worklist traversal.
This class represents a truncation of an integer value to a smaller integer value.
This class represents a binary unsigned division operation.
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.
SCEVUnionPredicate getUnionWith(const SCEVPredicate *N, ScalarEvolution &SE) const
Returns a new SCEVUnionPredicate that is the union of this predicate and the given predicate N.
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.
unsigned short getExpressionSize() const
SCEVNoWrapFlags NoWrapFlags
LLVM_ABI bool isOne() const
Return true if the expression is a constant one.
SCEV(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, unsigned short ExpressionSize, Type *Ty)
static constexpr auto FlagNUW
LLVM_ABI void computeAndSetCanonical(ScalarEvolution &SE)
Compute and set the canonical SCEV, by constructing a SCEV with the same operands,...
LLVM_ABI bool isZero() const
Return true if the expression is a constant zero.
const SCEV * CanonicalSCEV
Pointer to the canonical version of the SCEV, i.e.
static constexpr auto FlagAnyWrap
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.
static constexpr auto FlagNSW
LLVM_ABI ArrayRef< SCEVUse > operands() const
Return operands of this SCEV expression.
Type * getType() const
Return the LLVM type of this SCEV expression.
LLVM_ABI void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
SCEVTypes getSCEVType() const
static constexpr auto FlagNW
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.
LLVM_ABI const SCEV * getUDivExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
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 * getUDivCeilSCEV(const SCEV *N, const SCEV *D)
Compute ceil(N / D).
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterations(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L at given Context duri...
LLVM_ABI Type * getWiderType(Type *Ty1, Type *Ty2) const
LLVM_ABI const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)
LLVM_ABI bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
LLVM_ABI 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 * getURemExpr(SCEVUse LHS, SCEVUse RHS)
Represents an unsigned remainder expression based on unsigned division.
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 * 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 * getSMinExpr(SCEVUse LHS, SCEVUse 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 SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &Operands)
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.
LLVM_ABI const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
LLVM_ABI const SCEV * getAddRecExpr(SCEVUse Start, SCEVUse Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
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.
static LLVM_ABI bool isGuaranteedNotToBePoison(const SCEV *Op)
Returns true if Op is guaranteed to not be poison.
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< SCEVUse > &Operands)
LLVM_ABI std::optional< bool > evaluatePredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Check whether the condition described by Pred, LHS, and RHS is true or false in the given Context.
LLVM_ABI unsigned getSmallConstantMaxTripCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Returns the upper bound of the loop trip count as a normal unsigned value.
LLVM_ABI 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.
LLVM_ABI bool SimplifyICmpOperands(CmpPredicate &Pred, SCEVUse &LHS, SCEVUse &RHS, unsigned Depth=0)
Simplify LHS and RHS in a comparison with predicate Pred.
APInt getUnsignedRangeMin(const SCEV *S)
Determine the min of the unsigned range for a particular SCEV.
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 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 * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
LLVM_ABI Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
LLVM_ABI const SCEVPredicate * getComparePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
LLVM_ABI bool haveSameSign(const SCEV *S1, const SCEV *S2)
Return true if we know that S1 and S2 must have the same sign.
LLVM_ABI const SCEV * getNotSCEV(const SCEV *V)
Return the SCEV object corresponding to ~V.
LLVM_ABI const SCEV * getElementCount(Type *Ty, ElementCount EC, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
LLVM_ABI bool instructionCouldExistWithOperands(const SCEV *A, const SCEV *B)
Return true if there exists a point in the program at which both A and B could be operands to the sam...
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
LLVM_ABI void print(raw_ostream &OS) const
LLVM_ABI const SCEV * 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 bool isLoopUniform(const SCEV *S, const Loop *L)
Returns true if the given SCEV is loop-uniform with respect to the specified loop L.
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)
LLVM_ABI const SCEV * getUMaxExpr(SCEVUse LHS, SCEVUse RHS)
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags Mask)
Convenient NoWrapFlags manipulation.
@ 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 APInt getNonZeroConstantMultiple(const SCEV *S)
const SCEV * getMinusOne(Type *Ty)
Return a SCEV for the constant -1 of a specific type.
static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
LLVM_ABI bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
LLVM_ABI BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB)
Return the "disposition" of the given SCEV with respect to the given block.
LLVM_ABI const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
LLVM_ABI const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
Promote the operands to the wider of the types using zero-extension, and then perform a umin operatio...
LLVM_ABI bool loopIsFiniteByAssumption(const Loop *L)
Return true if this loop is finite by assumption.
LLVM_ABI const SCEV * getExistingSCEV(Value *V)
Return an existing SCEV for V if there is one, otherwise return nullptr.
LLVM_ABI APInt getConstantMultiple(const SCEV *S, const Instruction *CtxI=nullptr)
Returns the max constant multiple of S.
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
@ LoopComputable
The SCEV varies predictably with the loop.
@ LoopVariant
The SCEV is loop-variant (unknown).
@ LoopInvariant
The SCEV is loop-invariant.
@ LoopUniform
The SCEV is loop-uniform.
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 const SCEV * getMulExpr(SmallVectorImpl< SCEVUse > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
LLVM_ABI bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
LLVM_ABI uint32_t getMinTrailingZeros(const SCEV *S, const Instruction *CtxI=nullptr)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
@ DominatesBlock
The SCEV dominates the block.
@ ProperlyDominatesBlock
The SCEV properly dominates the block.
@ DoesNotDominateBlock
The SCEV does not dominate the block.
LLVM_ABI const SCEV * 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 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.
LLVM_ABI const SCEV * getAddExpr(SmallVectorImpl< SCEVUse > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
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 bool isKnownPredicate(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
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 * getPtrToAddrExpr(const SCEV *Op)
LLVM_ABI const SCEVAddRecExpr * convertSCEVToAddRecWithPredicates(const SCEV *S, const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Preds)
Tries to convert the S expression to an AddRec expression, adding additional predicates to Preds as r...
LLVM_ABI const SCEV * getSMaxExpr(SCEVUse LHS, SCEVUse RHS)
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.
LLVM_ABI bool isKnownViaInduction(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
We'd like to check the predicate on every iteration of the most dominated loop between loops used in ...
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 * getUDivExactExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
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 * getGEPExpr(GEPOperator *GEP, ArrayRef< SCEVUse > IndexExprs)
Returns an expression for a GEP.
LLVM_ABI const SCEV * getUMinExpr(SCEVUse LHS, SCEVUse RHS, bool Sequential=false)
LLVM_ABI void registerUser(const SCEV *User, ArrayRef< const SCEV * > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
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.
const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
LLVM_ABI void verify() const
LLVMContext & getContext() const
Implements a dense probed hash-table based set with some number of buckets stored inline.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
TypeSize getElementOffset(unsigned Idx) const
TypeSize getSizeInBits() const
Class to represent struct types.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)
bool isPointerTy() const
True if this is an instance of PointerType.
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 isIntegerTy() const
True if this is an instance of IntegerType.
static LLVM_ABI IntegerType * getIntNTy(LLVMContext &C, unsigned N)
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
LLVMContext & getContext() const
All values hold a context through their type.
unsigned getValueID() const
Return an ID for the concrete type of this object.
LLVM_ABI void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
LLVM_ABI std::optional< APInt > SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, unsigned RangeWidth)
Let q(n) = An^2 + Bn + C, and BW = bit width of the value range (e.g.
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
LLVM_ABI APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
constexpr bool any(E Val)
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.
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
auto m_BasicBlock()
Match an arbitrary basic block value and ignore it.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
auto m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
match_bind< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
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.
brc_match< Cond_t, match_bind< BasicBlock >, match_bind< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
CastOperator_match< OpTy, Instruction::PtrToInt > m_PtrToInt(const OpTy &Op)
Matches PtrToInt.
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
bind_cst_ty m_scev_APInt(const APInt *&C)
Match an SCEV constant and bind it to an APInt.
cst_pred_ty< is_all_ones > m_scev_AllOnes()
Match an integer with all bits set.
SCEVUnaryExpr_match< SCEVZeroExtendExpr, Op0_t > m_scev_ZExt(const Op0_t &Op0)
is_undef_or_poison m_scev_UndefOrPoison()
Match an SCEVUnknown wrapping undef or poison.
cst_pred_ty< is_one > m_scev_One()
Match an integer 1.
specificloop_ty m_SpecificLoop(const Loop *L)
SCEVUnaryExpr_match< SCEVSignExtendExpr, Op0_t > m_scev_SExt(const Op0_t &Op0)
match_bind< const SCEVMulExpr > m_scev_Mul(const SCEVMulExpr *&V)
cst_pred_ty< is_zero > m_scev_Zero()
Match an integer 0.
SCEVUnaryExpr_match< SCEVTruncateExpr, Op0_t > m_scev_Trunc(const Op0_t &Op0)
bool match(const SCEV *S, const Pattern &P)
SCEVBinaryExpr_match< SCEVUDivExpr, Op0_t, Op1_t > m_scev_UDiv(const Op0_t &Op0, const Op1_t &Op1)
specificscev_ty m_scev_Specific(const SCEV *S)
Match if we have a specific specified SCEV.
SCEVAffineAddRec_match< Op0_t, Op1_t, match_isa< const Loop > > m_scev_AffineAddRec(const Op0_t &Op0, const Op1_t &Op1)
match_bind< const SCEVUnknown > m_SCEVUnknown(const SCEVUnknown *&V)
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagNUW, true > m_scev_c_NUWMul(const Op0_t &Op0, const Op1_t &Op1)
match_bind< const SCEVAddExpr > m_scev_Add(const SCEVAddExpr *&V)
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagAnyWrap, true > m_scev_c_Mul(const Op0_t &Op0, const Op1_t &Op1)
SCEVBinaryExpr_match< SCEVSMaxExpr, Op0_t, Op1_t > m_scev_SMax(const Op0_t &Op0, const Op1_t &Op1)
SCEVURem_match< Op0_t, Op1_t > m_scev_URem(Op0_t LHS, Op1_t RHS, ScalarEvolution &SE)
Match the mathematical pattern A - (A / B) * B, where A and B can be arbitrary expressions.
@ Valid
The data is already valid.
initializer< Ty > init(const Ty &Val)
LocationClass< Ty > location(Ty &L)
@ Switch
The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...
NodeAddr< PhiNode * > Phi
friend class Instruction
Iterator for Instructions in a `BasicBlock.
unsigned getOpcode(const VPValue *V)
Return the instruction opcode for the recipe defining V or 0 for unsupported recipes and VPValues not...
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.
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...
RelativeUniformCounterPtr Values
@ Known
Known to have no common set bits.
LLVM_ABI bool canConstantFoldCallTo(const CallBase *Call, const Function *F)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
InterleavedRange< Range > interleaved(const Range &R, StringRef Separator=", ", StringRef Prefix="", StringRef Suffix="")
Output range R as a sequence of interleaved elements.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
auto successors(const MachineBasicBlock *BB)
scope_exit(Callable) -> scope_exit< Callable >
@ BinaryOp
One of the operands is a binary op.
@ Load
The value being inserted comes from a load (InsertElement only).
@ Store
The extracted value is stored (ExtractElement only).
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.
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.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
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...
unsigned short computeExpressionSize(ArrayRef< SCEVUse > Args)
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)
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.
constexpr T divideCeil(U Numerator, V Denominator)
Returns the integer ceil(Numerator / Denominator).
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()).
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
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 auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
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)
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.
SCEVUseT< const SCEV * > SCEVUse
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.
static LLVM_ABI KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for ashr(LHS, RHS).
static LLVM_ABI KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for lshr(LHS, RHS).
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