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"));
243 cl::desc(
"Handle <= and >= in finite loops"),
247 "scalar-evolution-use-context-for-no-wrap-flag-strenghening",
cl::Hidden,
248 cl::desc(
"Infer nuw/nsw flags using context where suitable"),
285#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
303 OS <<
"(ptrtoaddr " << *
Op->getType() <<
" " <<
Op <<
" to "
310 OS <<
"(trunc " << *
Op->getType() <<
" " <<
Op <<
" to "
317 OS <<
"(zext " << *
Op->getType() <<
" " <<
Op <<
" to " << *ZExt->
getType()
324 OS <<
"(sext " << *
Op->getType() <<
" " <<
Op <<
" to " << *SExt->
getType()
353 const char *OpStr =
nullptr;
366 OpStr =
" umin_seq ";
388 OS <<
"(" << UDiv->
getLHS() <<
" /u " << UDiv->
getRHS() <<
")";
395 OS <<
"***COULDNOTCOMPUTE***";
437 if (!
Mul)
return false;
441 if (!SC)
return false;
455 auto &Entry = ConstantSCEVs[V];
464 static_cast<SCEVConstant *
>(UniqueSCEVs.lookup(ID, Token)))
467 new (SCEVAllocator)
SCEVConstant(ID.Intern(SCEVAllocator), V);
468 UniqueSCEVs.insert(S, Token);
483 ConstantInt::get(ITy, V,
isSigned,
true));
491 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
493 SCEV *S =
new (SCEVAllocator)
SCEVVScale(ID.Intern(SCEVAllocator), Ty);
494 UniqueSCEVs.insert(S, Token);
515 "Must be a non-bit-width-changing pointer-to-integer cast!");
527 "Cannot truncate non-integer value!");
534 "Cannot zero extend non-integer value!");
541 "Cannot sign extend non-integer value!");
546 SE->forgetMemoizedResults({
this});
549 SE->UniqueSCEVs.erase(
this);
555void SCEVUnknown::allUsesReplacedWith(
Value *New) {
557 SE->forgetMemoizedResults({
this});
560 SE->UniqueSCEVs.erase(
this);
582 if (LIsPointer != RIsPointer)
583 return (
int)LIsPointer - (int)RIsPointer;
588 return (
int)LID - (int)RID;
593 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
594 return (
int)LArgNo - (int)RArgNo;
600 if (
auto L = LGV->getLinkage() - RGV->getLinkage())
603 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
604 auto LT = GV->getLinkage();
611 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
612 return LGV->getName().compare(RGV->getName());
623 if (LParent != RParent) {
626 if (LDepth != RDepth)
627 return (
int)LDepth - (int)RDepth;
631 unsigned LNumOps = LInst->getNumOperands(),
632 RNumOps = RInst->getNumOperands();
633 if (LNumOps != RNumOps)
634 return (
int)LNumOps - (int)RNumOps;
636 for (
unsigned Idx :
seq(LNumOps)) {
638 RInst->getOperand(Idx),
Depth + 1);
652static std::optional<int>
662 return (
int)LType - (int)RType;
687 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
688 if (LBitWidth != RBitWidth)
689 return (
int)LBitWidth - (int)RBitWidth;
690 return LA.
ult(
RA) ? -1 : 1;
696 return LTy->getBitWidth() - RTy->getBitWidth();
707 if (LLoop != RLoop) {
709 assert(LHead != RHead &&
"Two loops share the same header?");
713 "No dominance between recurrences used by one SCEV?");
736 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
737 if (LNumOps != RNumOps)
738 return (
int)LNumOps - (int)RNumOps;
740 for (
unsigned i = 0; i != LNumOps; ++i) {
766 if (
Ops.size() < 2)
return;
771 return Complexity && *Complexity < 0;
773 if (
Ops.size() == 2) {
777 if (IsLessComplex(
RHS,
LHS))
790 for (
unsigned i = 0, e =
Ops.size(); i != e-2; ++i) {
796 for (
unsigned j = i+1; j != e &&
Ops[j]->getSCEVType() == Complexity; ++j) {
801 if (i == e-2)
return;
823template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
827 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
829 for (
unsigned Idx = 0; Idx <
Ops.size();) {
837 Ops.erase(
Ops.begin() + Idx);
844 assert(Folded &&
"Must have folded value");
848 if (Folded && IsAbsorber(Folded->
getAPInt()))
852 if (Folded && !IsIdentity(Folded->
getAPInt()))
853 Ops.insert(
Ops.begin(), Folded);
855 return Ops.size() == 1 ?
Ops[0] :
nullptr;
930 APInt OddFactorial(W, 1);
932 for (
unsigned i = 3; i <=
K; ++i) {
935 OddFactorial *= (i >> TwoFactors);
939 unsigned CalculationBits = W +
T;
953 for (
unsigned i = 1; i !=
K; ++i) {
986 "use-specific flags only supported for affine AddRecs");
988 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1029 ConversionFn CreatePtrCast;
1033 ConversionFn CreatePtrCast)
1034 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
1037 Type *TargetTy, ConversionFn CreatePtrCast) {
1039 return Rewriter.visit(Scev);
1065 "Should only reach pointer-typed SCEVUnknown's.");
1070 return SE.getZero(TargetTy);
1071 return CreatePtrCast(Expr);
1076 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1080 if (DL.hasUnstableRepresentation(
Op->getType()))
1083 Type *Ty = DL.getAddressType(
Op->getType());
1094 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1096 SCEV *S =
new (SCEVAllocator)
1098 UniqueSCEVs.insert(S, Token);
1101 return static_cast<const SCEV *
>(S);
1104 "We must have succeeded in sinking the cast, "
1105 "and ending up with an integer-typed expression!");
1112 "This is not a truncating conversion!");
1114 "This is not a conversion to a SCEVable type!");
1115 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1120 ID.AddPointer(
Op.getOpaqueValue());
1123 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1146 UniqueSCEVs.insert(S, Token);
1159 unsigned numTruncs = 0;
1160 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1168 if (numTruncs < 2) {
1178 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1185 for (
const SCEV *
Op : AddRec->operands())
1200 UniqueSCEVs.insert(S, Token);
1241struct ExtendOpTraitsBase {
1242 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
SCEVUse,
Type *,
1247template <
typename ExtendOp>
struct ExtendOpTraits {
1263 static const GetExtendExprTy GetExtendExpr;
1265 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1266 ICmpInst::Predicate *Pred,
1267 ScalarEvolution *SE) {
1272const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1279 static const GetExtendExprTy GetExtendExpr;
1281 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1282 ICmpInst::Predicate *Pred,
1283 ScalarEvolution *SE) {
1288const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1300template <
typename ExtendOpTy>
1303 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1304 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1320 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1333 auto PreStartFlags =
1351 const SCEV *OperandExtendedStart =
1353 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1354 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1366 const SCEV *OverflowLimit =
1367 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1369 if (OverflowLimit &&
1377template <
typename ExtendOpTy>
1381 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1389 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1424template <
typename ExtendOpTy>
1425bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1428 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1438 APInt StartAI = StartC->
getAPInt();
1440 for (
unsigned Delta : {-2, -1, 1, 2}) {
1441 const SCEV *PreStart =
getConstant(StartAI - Delta);
1442 const auto *PreAR =
static_cast<SCEVAddRecExpr *
>(
1443 findExistingSCEVInCache(
scAddRecExpr, {PreStart, Step},
L));
1447 if (PreAR &&
any(PreAR->getNoWrapFlags(WrapType))) {
1450 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1451 DeltaS, &Pred,
this);
1469 const unsigned BitWidth =
C.getBitWidth();
1487 const APInt &ConstantStart,
1502 auto I = FoldCache.
insert({ID, S});
1506 auto &UserIDs = FoldCacheUser[
I.first->second];
1507 assert(
count(UserIDs, ID) == 1 &&
"unexpected duplicates in UserIDs");
1508 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1509 if (UserIDs[
I] == ID) {
1514 I.first->second = S;
1516 FoldCacheUser[S].push_back(ID);
1522 "This is not an extending conversion!");
1524 "This is not a conversion to a SCEVable type!");
1525 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1529 if (
const SCEV *S = FoldCache.lookup(ID))
1541 "This is not an extending conversion!");
1543 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1555 const SCEV *Start, *Step;
1560 if (AR->hasNoUnsignedWrap()) {
1571 ID.AddPointer(
Op.getOpaqueValue());
1574 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1579 UniqueSCEVs.insert(S, Token);
1589 const SCEV *
X = ST->getOperand();
1622 const SCEV *CastedMaxBECount =
1626 if (MaxBECount == RecastedMaxBECount) {
1635 const SCEV *WideMaxBECount =
1637 const SCEV *OperandExtendedAdd =
1643 if (ZAdd == OperandExtendedAdd) {
1654 OperandExtendedAdd =
1660 if (ZAdd == OperandExtendedAdd) {
1681 !AC.assumptions().empty()) {
1683 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1685 if (AR->hasNoUnsignedWrap()) {
1720 const APInt &
C = SC->getAPInt();
1724 const SCEV *SResidual =
1732 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1756 if (SA->hasNoUnsignedWrap()) {
1769 if (SA->hasNoSignedWrap() &&
1772 C->isNegative() && !
C->isMinSignedValue() && C2->
sge(
C->abs())) {
1791 const SCEV *SResidual =
1802 if (SM->hasNoUnsignedWrap()) {
1824 const SCEV *TruncRHS;
1861 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1865 UniqueSCEVs.insert(S, Token);
1874 "This is not an extending conversion!");
1876 "This is not a conversion to a SCEVable type!");
1877 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1881 if (
const SCEV *S = FoldCache.lookup(ID))
1893 "This is not an extending conversion!");
1895 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1912 const SCEV *Start, *Step;
1917 if (AR->hasNoSignedWrap()) {
1928 ID.AddPointer(
Op.getOpaqueValue());
1931 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1937 UniqueSCEVs.insert(S, Token);
1947 const SCEV *
X = ST->getOperand();
1958 if (SA->hasNoSignedWrap()) {
1980 const SCEV *SResidual =
2013 const SCEV *CastedMaxBECount =
2017 if (MaxBECount == RecastedMaxBECount) {
2026 const SCEV *WideMaxBECount =
2028 const SCEV *OperandExtendedAdd =
2034 if (SAdd == OperandExtendedAdd) {
2045 OperandExtendedAdd =
2051 if (SAdd == OperandExtendedAdd) {
2071 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2073 if (AR->hasNoSignedWrap()) {
2087 const APInt &
C = SC->getAPInt();
2091 const SCEV *SResidual =
2099 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2126 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
2130 UniqueSCEVs.insert(S, Token);
2146 assert(Expr->
getType() == Ty &&
"requested type must match");
2158 "This is not an extending conversion!");
2160 "This is not a conversion to a SCEVable type!");
2165 if (SC->getAPInt().isNegative())
2170 const SCEV *NewOp =
T->getOperand();
2189 for (
const SCEV *
Op : AR->operands())
2227 APInt &AccumulatedConstant,
2231 bool Interesting =
false;
2238 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2240 AccumulatedConstant += Scale *
C->getAPInt();
2245 for (; i !=
Ops.size(); ++i) {
2254 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2260 auto Pair = M.insert({
Key, NewScale});
2264 Pair.first->second += NewScale;
2272 auto Pair = M.insert({
Ops[i], Scale});
2276 Pair.first->second += Scale;
2294 case Instruction::Add:
2296 case Instruction::Sub:
2298 case Instruction::Mul:
2312 const SCEV *
A = (this->*Extension)(
Operation(LHS, RHS), WideTy, 0);
2313 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2314 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2322 if (BinOp == Instruction::Mul)
2328 APInt C = RHSC->getAPInt();
2329 unsigned NumBits =
C.getBitWidth();
2330 bool IsSub = (BinOp == Instruction::Sub);
2331 bool IsNegativeConst = (
Signed &&
C.isNegative());
2333 bool OverflowDown = IsSub ^ IsNegativeConst;
2335 if (IsNegativeConst) {
2348 APInt Limit = Min + Magnitude;
2354 APInt Limit = Max - Magnitude;
2363 return std::nullopt;
2372 bool Deduced =
false;
2378 bool CanUseNSW =
true;
2379 const APInt *ShiftAmt;
2384 return std::nullopt;
2388 Opcode = Instruction::Mul;
2390 }
else if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
2391 Opcode != Instruction::Mul) {
2392 return std::nullopt;
2411 return std::nullopt;
2419 using namespace std::placeholders;
2426 assert(CanAnalyze &&
"don't call from other places!");
2433 auto IsKnownNonNegative = [&](
SCEVUse U) {
2442 if (SignOrUnsignWrap != SignOrUnsignMask &&
2449 return Instruction::Add;
2451 return Instruction::Mul;
2480 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2487 if (UDiv->getOperand(1) ==
Ops[1])
2490 if (UDiv->getOperand(1) ==
Ops[0])
2507 "only nuw or nsw allowed");
2509 "only nuw or nsw allowed");
2510 assert(!
Ops.empty() &&
"Cannot get empty add!");
2511 if (
Ops.size() == 1)
return Ops[0];
2514 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2516 "SCEVAddExpr operand types don't match!");
2518 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2519 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2524 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2525 [](
const APInt &
C) {
return C.isZero(); },
2526 [](
const APInt &
C) {
return false; });
2545 return {getOrCreateAddExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
2550 if (
Add->getNoWrapFlags(ExprFlags) != ExprFlags)
2551 Add->setNoWrapFlags(ComputeFlags(
Ops));
2552 return {S, UseFlags};
2559 bool FoundMatch =
false;
2560 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2561 if (
Ops[i] ==
Ops[i+1]) {
2573 --i; e -=
Count - 1;
2583 auto FindTruncSrcType = [&]() ->
Type * {
2589 return T->getOperand()->getType();
2591 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2593 return T->getOperand()->getType();
2597 if (
auto *SrcType = FindTruncSrcType()) {
2604 if (
T->getOperand()->getType() != SrcType) {
2613 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2616 if (
T->getOperand()->getType() != SrcType) {
2645 if (
Ops.size() == 2) {
2655 auto C2 =
C->getAPInt();
2658 APInt ConstAdd = C1 + C2;
2659 auto AddFlags = AddExpr->getNoWrapFlags();
2700 if (
Ops.size() == 2 &&
2711 if (Idx <
Ops.size()) {
2712 bool DeletedAdd =
false;
2723 Ops.erase(
Ops.begin()+Idx);
2726 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2749 struct APIntCompare {
2750 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2751 return LHS.ult(RHS);
2758 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2760 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2763 if (AccumulatedConstant != 0)
2765 for (
auto &MulOp : MulOpLists) {
2766 if (MulOp.first == 1) {
2768 }
else if (MulOp.first != 0) {
2777 if (
Ops.size() == 1)
2786 if (M->getNumOperands() == 2)
2787 return M->getOperand(OpIdx == 0);
2789 append_range(Remaining, M->operands().drop_front(OpIdx + 1));
2798 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2802 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2810 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp) {
2811 if (MulOpSCEV ==
Ops[AddOp]) {
2822 for (
unsigned OMulOp = 0, OE = OtherMul->
getNumOperands(); OMulOp != OE;
2824 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2826 Cofactors.
push_back(StripFactor(OtherMul, OMulOp));
2835 if (!Cofactors.
empty()) {
2843 if (
Ops.size() == DeadIndices.
size() + 1)
2850 Ops.erase(
Ops.begin() + Idx);
2854 Ops.push_back(OuterMul);
2873 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2876 Ops.erase(
Ops.begin()+i);
2881 if (!LIOps.
empty()) {
2906 auto *DefI = getDefiningScopeBound(LIOps);
2908 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2920 if (
Ops.size() == 1)
return NewRec;
2923 for (
unsigned i = 0;; ++i)
2924 if (
Ops[i] == AddRec) {
2934 for (
unsigned OtherIdx = Idx+1;
2942 "AddRecExprs are not sorted in reverse dominance order?");
2949 if (OtherAddRec->getLoop() == AddRecLoop) {
2950 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2952 if (i >= AddRecOps.
size()) {
2953 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2957 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
2960 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
2976 "Tried to add SCEVUse flags after operands changed");
2977 return {getOrCreateAddExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
2985 ID.AddPointer(
Op.getOpaqueValue());
2991 S =
new (SCEVAllocator)
2993 UniqueSCEVs.insert(S, Token);
3004 FoldingSetNodeID
ID;
3007 ID.AddPointer(
Op.getOpaqueValue());
3009 FoldingSetInsertToken Token;
3011 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.lookup(ID, Token));
3015 S =
new (SCEVAllocator)
3016 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3017 UniqueSCEVs.insert(S, Token);
3019 LoopUsers[
L].push_back(S);
3028 FoldingSetNodeID
ID;
3031 ID.AddPointer(
Op.getOpaqueValue());
3032 FoldingSetInsertToken Token;
3033 SCEVMulExpr *S =
static_cast<SCEVMulExpr *
>(UniqueSCEVs.lookup(ID, Token));
3037 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3039 UniqueSCEVs.insert(S, Token);
3048 FoldingSetNodeID
ID;
3050 ID.AddPointer(
LHS.getOpaqueValue());
3051 ID.AddPointer(
RHS.getOpaqueValue());
3052 FoldingSetInsertToken Token;
3053 SCEV *S = UniqueSCEVs.lookup(ID, Token);
3055 S =
new (SCEVAllocator) SCEVUDivExpr(
ID.Intern(SCEVAllocator),
LHS,
RHS);
3056 UniqueSCEVs.insert(S, Token);
3065 if (j > 1 && k / j != i) Overflow =
true;
3081 if (n == 0 || n == k)
return 1;
3082 if (k > n)
return 0;
3088 for (
uint64_t i = 1; i <= k; ++i) {
3089 r =
umul_ov(r, n-(i-1), Overflow);
3098 struct FindConstantInAddMulChain {
3099 bool FoundConstant =
false;
3101 bool follow(
const SCEV *S) {
3106 bool isDone()
const {
3107 return FoundConstant;
3111 FindConstantInAddMulChain
F;
3113 ST.visitAll(StartExpr);
3114 return F.FoundConstant;
3123 "only nuw or nsw allowed");
3125 "only nuw or nsw allowed");
3126 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3127 if (
Ops.size() == 1)
return Ops[0];
3129 Type *ETy =
Ops[0]->getType();
3131 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3133 "SCEVMulExpr operand types don't match!");
3138 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3139 [](
const APInt &
C) {
return C.isOne(); },
3140 [](
const APInt &
C) {
return C.isZero(); });
3157 return {getOrCreateMulExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
3162 if (
Mul->getNoWrapFlags(ExprFlags) != ExprFlags)
3163 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3164 return {S, UseFlags};
3168 if (
Ops.size() == 2) {
3176 const SCEV *Op0, *Op1;
3184 if (
Ops[0]->isAllOnesValue()) {
3189 bool AnyFolded =
false;
3190 for (
const SCEV *AddOp :
Add->operands()) {
3210 if (AddRec->hasNoSignedWrap()) {
3241 APInt C1V = LHSC->getAPInt();
3251 const SCEV *NewMul =
nullptr;
3255 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3270 if (Idx <
Ops.size()) {
3271 bool DeletedMul =
false;
3277 Ops.erase(
Ops.begin()+Idx);
3301 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3304 Ops.erase(
Ops.begin()+i);
3309 if (!LIOps.
empty()) {
3321 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3337 if (
Ops.size() == 1)
return NewRec;
3340 for (
unsigned i = 0;; ++i)
3341 if (
Ops[i] == AddRec) {
3362 bool OpsModified =
false;
3363 for (
unsigned OtherIdx = Idx+1;
3377 bool Overflow =
false;
3384 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3385 uint64_t Coeff1 =
Choose(x, 2*x - y, Overflow);
3388 z < ze && !Overflow; ++z) {
3389 uint64_t Coeff2 =
Choose(2*x - y, x-z, Overflow);
3391 if (LargerThan64Bits)
3392 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3394 Coeff = Coeff1*Coeff2;
3407 const SCEV *NewAddRec =
3409 if (
Ops.size() == 2)
return NewAddRec;
3410 Ops[Idx] = NewAddRec;
3411 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3428 "Tried to add SCEVUse flags after operands changed");
3429 return {getOrCreateMulExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
3436 "SCEVURemExpr operand types don't match!");
3441 if (RHSC->getValue()->isOne())
3442 return getZero(LHS->getType());
3445 if (RHSC->getAPInt().isPowerOf2()) {
3446 Type *FullTy = LHS->getType();
3462 assert(!LHS->getType()->isPointerTy() &&
3463 "SCEVUDivExpr operand can't be pointer!");
3464 assert(LHS->getType() == RHS->getType() &&
3465 "SCEVUDivExpr operand types don't match!");
3475 if (RHSC->getValue()->isOne())
3480 if (!RHSC->getValue()->isZero()) {
3484 Type *Ty = LHS->getType();
3485 unsigned LZ = RHSC->getAPInt().countl_zero();
3489 if (!RHSC->getAPInt().isPowerOf2())
3497 const APInt &StepInt = Step->getAPInt();
3498 const APInt &DivInt = RHSC->getAPInt();
3499 if (!StepInt.
urem(DivInt) &&
3505 for (
const SCEV *
Op : AR->operands())
3511 const APInt *StartRem;
3524 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3528 const SCEV *NewStart =
3530 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3532 const SCEV *NewLHS =
3542 if (M->hasNoUnsignedWrap()) {
3544 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3545 const SCEV *
Op = M->getOperand(i);
3572 if (
auto *DivisorConstant =
3574 bool Overflow =
false;
3576 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3587 if (
A->hasNoUnsignedWrap()) {
3589 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3596 if (
Operands.size() ==
A->getNumOperands())
3608 const APInt &
N = RHSC->getAPInt();
3609 const APInt *NMinusM, *M;
3613 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3614 *NMinusM ==
N - *M) {
3623 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3633 return getZero(LHS->getType());
3637 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3638 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3639 if (
Mul->getOperand(i) == RHS) {
3650 const SCEV *NewLHS, *NewRHS;
3655 return getOrCreateUDivExpr(LHS, RHS);
3674 if (StepChrec->getLoop() == L) {
3693 "only nuw or nsw allowed");
3699 "SCEVAddRecExpr operand types don't match!");
3700 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3704 "SCEVAddRecExpr operand is not available at loop entry!");
3726 const Loop *NestedLoop = NestedAR->getLoop();
3727 if (L->contains(NestedLoop)
3730 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3732 Operands[0] = NestedAR->getStart();
3736 bool AllInvariant =
all_of(
3748 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3759 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3770 "Tried to add SCEVUse flags after operands changed");
3771 return {getOrCreateAddRecExpr(
Operands, L, ExprFlags), UseFlags};
3787 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3791 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3805 bool FirstIter =
true;
3807 for (
SCEVUse IndexExpr : IndexExprs) {
3814 Offsets.push_back(FieldOffset);
3817 CurTy = STy->getTypeAtIndex(Index);
3822 "The first index of a GEP indexes a pointer");
3823 CurTy = SrcElementTy;
3834 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3835 Offsets.push_back(LocalOffset);
3840 if (Offsets.empty())
3853 "GEP should not change type mid-flight.");
3857SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3861 "L must be passed to find existing AddRecs");
3865 ID.AddPointer(
Op.getOpaqueValue());
3869 return UniqueSCEVs.lookup(ID, Token);
3879 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3880 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3881 if (
Ops.size() == 1)
return Ops[0];
3884 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3886 "Operand types don't match!");
3889 "min/max should be consistently pointerish");
3915 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3917 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3922 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3924 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3930 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3936 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3941 if (Idx <
Ops.size()) {
3942 bool DeletedAny =
false;
3943 while (
Ops[Idx]->getSCEVType() == Kind) {
3945 Ops.erase(
Ops.begin()+Idx);
3963 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3964 if (
Ops[i] ==
Ops[i + 1] ||
3965 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3968 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3971 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3974 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3980 if (
Ops.size() == 1)
return Ops[0];
3982 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
3989 ID.AddPointer(
Op.getOpaqueValue());
3991 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
3993 return ExistingSCEV;
3996 SCEV *S =
new (SCEVAllocator)
3999 UniqueSCEVs.insert(S, Token);
4007class SCEVSequentialMinMaxDeduplicatingVisitor final
4008 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4009 std::optional<const SCEV *>> {
4010 using RetVal = std::optional<const SCEV *>;
4017 bool canRecurseInto(
SCEVTypes Kind)
const {
4020 return RootKind == Kind || NonSequentialRootKind == Kind;
4025 if (!SeenOps.
insert(S).second)
4026 return std::nullopt;
4030 if (!canRecurseInto(Kind))
4040 return std::nullopt;
4050 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4052 : SE(SE), RootKind(RootKind),
4053 NonSequentialRootKind(
4054 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4058 SmallVectorImpl<SCEVUse> &NewOps) {
4063 for (
const SCEV *
Op : OrigOps) {
4068 Ops.emplace_back(*NewOp);
4072 NewOps = std::move(
Ops);
4116struct SCEVPoisonCollector {
4117 bool LookThroughMaybePoisonBlocking;
4118 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4119 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4120 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4122 bool follow(
const SCEV *S) {
4123 if (!LookThroughMaybePoisonBlocking &&
4133 bool isDone()
const {
return false; }
4143 SCEVPoisonCollector PC1(
true);
4148 if (PC1.MaybePoison.
empty())
4154 SCEVPoisonCollector PC2(
false);
4164 SCEVPoisonCollector PC(
false);
4187 while (!Worklist.
empty()) {
4189 if (!Visited.
insert(V).second)
4193 if (Visited.
size() > 16)
4209 if (PDI->isDisjoint())
4216 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4223 if (
I->hasPoisonGeneratingAnnotations())
4234 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4235 "Not a SCEVSequentialMinMaxExpr!");
4236 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4237 if (
Ops.size() == 1)
4241 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4243 "Operand types don't match!");
4246 "min/max should be consistently pointerish");
4254 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4261 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4271 bool DeletedAny =
false;
4272 while (Idx <
Ops.size()) {
4273 if (
Ops[Idx]->getSCEVType() != Kind) {
4278 Ops.erase(
Ops.begin() + Idx);
4279 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4280 SMME->operands().end());
4288 const SCEV *SaturationPoint;
4299 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4300 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4312 Ops.erase(
Ops.begin() + i);
4317 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4318 Ops.erase(
Ops.begin() + i);
4328 ID.AddPointer(
Op.getOpaqueValue());
4330 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
4332 return ExistingSCEV;
4336 SCEV *S =
new (SCEVAllocator)
4339 UniqueSCEVs.insert(S, Token);
4387 if (
Size.isScalable())
4408 "Cannot get offset for structure containing scalable vector types");
4422 if (
SCEV *S = UniqueSCEVs.lookup(ID, Token)) {
4424 "Stale SCEVUnknown in uniquing map!");
4427 SCEV *S =
new (SCEVAllocator)
SCEVUnknown(ID.Intern(SCEVAllocator), V,
this,
4430 UniqueSCEVs.insert(S, Token);
4445 return Ty->isIntOrPtrTy();
4452 if (Ty->isPointerTy())
4463 if (Ty->isIntegerTy())
4467 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4479 bool PreciseA, PreciseB;
4480 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4481 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4482 if (!PreciseA || !PreciseB)
4485 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4486 DT.dominates(ScopeB, ScopeA);
4490 return CouldNotCompute.get();
4493bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4496 return SU && SU->getValue() ==
nullptr;
4499 return !ContainsNulls;
4504 if (
I != HasRecMap.end())
4509 HasRecMap.insert({S, FoundAddRec});
4517 if (
SI == ExprValueMap.
end())
4519 return SI->second.getArrayRef();
4525void ScalarEvolution::eraseValueFromMap(
Value *V) {
4527 if (
I != ValueExprMap.end()) {
4528 auto EVIt = ExprValueMap.find(
I->second);
4529 bool Removed = EVIt->second.remove(V);
4531 assert(Removed &&
"Value not in ExprValueMap?");
4532 ValueExprMap.erase(
I);
4536void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4540 auto It = ValueExprMap.find_as(V);
4541 if (It == ValueExprMap.end()) {
4543 ExprValueMap[S].insert(V);
4554 return createSCEVIter(V);
4561 if (
I != ValueExprMap.end()) {
4562 const SCEV *S =
I->second;
4563 assert(checkValidity(S) &&
4564 "existing SCEV has not been properly invalidated");
4576 Type *Ty = V->getType();
4592 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4605 return (
const SCEV *)
nullptr;
4611 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4615 Type *Ty = V->getType();
4621 assert(
P->getType()->isPointerTy());
4636 if (AddOp->getType()->isPointerTy()) {
4637 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4654 return getZero(LHS->getType());
4659 if (RHS->getType()->isPointerTy()) {
4660 if (!LHS->getType()->isPointerTy() ||
4670 const bool RHSIsNotMinSigned =
4701 Type *SrcTy = V->getType();
4702 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4703 "Cannot truncate or zero extend with non-integer arguments!");
4713 Type *SrcTy = V->getType();
4714 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4715 "Cannot truncate or zero extend with non-integer arguments!");
4724 Type *SrcTy = V->getType();
4725 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4726 "Cannot noop or zero extend with non-integer arguments!");
4728 "getNoopOrZeroExtend cannot truncate!");
4735 Type *SrcTy = V->getType();
4736 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4737 "Cannot noop or sign extend with non-integer arguments!");
4739 "getNoopOrSignExtend cannot truncate!");
4746 Type *SrcTy = V->getType();
4747 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4748 "Cannot noop or any extend with non-integer arguments!");
4750 "getNoopOrAnyExtend cannot truncate!");
4757 Type *SrcTy = V->getType();
4758 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4759 "Cannot truncate or noop with non-integer arguments!");
4761 "getTruncateOrNoop cannot extend!");
4769 const SCEV *PromotedLHS = LHS;
4770 const SCEV *PromotedRHS = RHS;
4790 assert(!
Ops.empty() &&
"At least one operand must be!");
4792 if (
Ops.size() == 1)
4796 Type *MaxType =
nullptr;
4802 assert(MaxType &&
"Failed to find maximum type!");
4815 if (!V->getType()->isPointerTy())
4820 V = AddRec->getStart();
4822 const SCEV *PtrOp =
nullptr;
4823 for (
const SCEV *AddOp :
Add->operands()) {
4824 if (AddOp->getType()->isPointerTy()) {
4825 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4829 assert(PtrOp &&
"Must have pointer op");
4841 for (
User *U :
I->users()) {
4843 if (Visited.
insert(UserInsn).second)
4857 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4858 bool IgnoreOtherLoops =
true) {
4861 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4863 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4868 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4870 SeenLoopVariantSCEVUnknown =
true;
4874 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4878 SeenOtherLoops =
true;
4882 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4884 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4887 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4888 : SCEVRewriteVisitor(SE),
L(
L) {}
4891 bool SeenLoopVariantSCEVUnknown =
false;
4892 bool SeenOtherLoops =
false;
4901 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4902 SCEVPostIncRewriter
Rewriter(L, SE);
4904 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4909 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4911 SeenLoopVariantSCEVUnknown =
true;
4915 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4919 SeenOtherLoops =
true;
4923 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4925 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4928 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4929 : SCEVRewriteVisitor(SE),
L(
L) {}
4932 bool SeenLoopVariantSCEVUnknown =
false;
4933 bool SeenOtherLoops =
false;
4939class SCEVBackedgeConditionFolder
4942 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4943 ScalarEvolution &SE) {
4944 bool IsPosBECond =
false;
4945 Value *BECond =
nullptr;
4946 if (BasicBlock *Latch =
L->getLoopLatch()) {
4948 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
4949 "Both outgoing branches should not target same header!");
4950 BECond = BI->getCondition();
4951 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
4956 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
4960 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4961 const SCEV *
Result = Expr;
4966 switch (
I->getOpcode()) {
4967 case Instruction::Select: {
4969 std::optional<const SCEV *> Res =
4970 compareWithBackedgeCondition(
SI->getCondition());
4978 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
4989 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
4990 bool IsPosBECond, ScalarEvolution &SE)
4991 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
4992 IsPositiveBECond(IsPosBECond) {}
4994 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
4998 Value *BackedgeCond =
nullptr;
5000 bool IsPositiveBECond;
5003std::optional<const SCEV *>
5004SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5009 if (BackedgeCond == IC)
5012 return std::nullopt;
5017 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5018 ScalarEvolution &SE) {
5024 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5031 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5041 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5042 : SCEVRewriteVisitor(SE),
L(
L) {}
5050void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5066 const APInt &BECountAP = BECountMax->getAPInt();
5067 unsigned NoOverflowBitWidth =
5076ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5086 if (!SignedWrapViaInductionTried.insert(AR).second)
5111 AC.assumptions().empty())
5119 const SCEV *OverflowLimit =
5121 if (OverflowLimit &&
5129ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5139 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5164 AC.assumptions().empty())
5173 const SCEV *OverflowLimit =
5202 IsNSW = OBO->hasNoSignedWrap();
5203 IsNUW = OBO->hasNoUnsignedWrap();
5209 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5221 return std::nullopt;
5227 switch (
Op->getOpcode()) {
5228 case Instruction::Add:
5229 case Instruction::Sub:
5230 case Instruction::Mul:
5231 case Instruction::UDiv:
5232 case Instruction::URem:
5233 case Instruction::And:
5234 case Instruction::AShr:
5235 case Instruction::Shl:
5238 case Instruction::Or: {
5241 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5251 case Instruction::Xor:
5255 if (RHSC->getValue().isSignMask())
5256 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5258 if (V->getType()->isIntegerTy(1))
5259 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5262 case Instruction::LShr:
5271 if (SA->getValue().ult(
BitWidth)) {
5273 ConstantInt::get(SA->getContext(),
5275 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5280 case Instruction::ExtractValue: {
5282 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5290 bool Signed = WO->isSigned();
5293 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5298 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5309 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5310 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5312 return std::nullopt;
5338 if (
Op == SymbolicPHI)
5343 if (SourceBits != NewBits)
5361 if (!L || L->getHeader() != PN->
getParent())
5419std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5420ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5428 assert(L &&
"Expecting an integer loop header phi");
5433 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5434 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5435 Value *
V = PN->getIncomingValue(i);
5436 if (
L->contains(PN->getIncomingBlock(i))) {
5439 }
else if (BEValueV != V) {
5443 }
else if (!StartValueV) {
5445 }
else if (StartValueV != V) {
5446 StartValueV =
nullptr;
5450 if (!BEValueV || !StartValueV)
5451 return std::nullopt;
5453 const SCEV *BEValue =
getSCEV(BEValueV);
5460 return std::nullopt;
5464 unsigned FoundIndex =
Add->getNumOperands();
5465 Type *TruncTy =
nullptr;
5467 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5470 if (FoundIndex == e) {
5475 if (FoundIndex ==
Add->getNumOperands())
5476 return std::nullopt;
5480 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5481 if (i != FoundIndex)
5482 Ops.push_back(
Add->getOperand(i));
5488 return std::nullopt;
5541 const SCEV *StartVal =
getSCEV(StartValueV);
5542 const SCEV *PHISCEV =
5569 auto getExtendedExpr = [&](
const SCEV *Expr,
5570 bool CreateSignExtend) ->
const SCEV * {
5573 const SCEV *ExtendedExpr =
5576 return ExtendedExpr;
5584 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5585 const SCEV *ExtendedExpr) ->
bool {
5586 return Expr != ExtendedExpr &&
5590 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5591 if (PredIsKnownFalse(StartVal, StartExtended)) {
5593 return std::nullopt;
5598 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5599 if (PredIsKnownFalse(Accum, AccumExtended)) {
5601 return std::nullopt;
5604 auto AppendPredicate = [&](
const SCEV *Expr,
5605 const SCEV *ExtendedExpr) ->
void {
5606 if (Expr != ExtendedExpr &&
5614 AppendPredicate(StartVal, StartExtended);
5615 AppendPredicate(Accum, AccumExtended);
5623 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5624 std::make_pair(NewAR, Predicates);
5626 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5630std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5635 return std::nullopt;
5638 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5639 if (
I != PredicatedSCEVRewrites.end()) {
5640 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5643 if (Rewrite.first == SymbolicPHI)
5644 return std::nullopt;
5648 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5652 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5653 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5658 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5659 return std::nullopt;
5679 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5680 if (Expr1 != Expr2 &&
5681 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5682 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5717const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5719 Value *StartValueV) {
5722 assert(BEValueV && StartValueV);
5724 const SCEV *Accum =
nullptr;
5727 if (BO->Opcode != Instruction::Add)
5730 if (BO->LHS == PN &&
L->isLoopInvariant(BO->RHS))
5732 else if (BO->RHS == PN &&
L->isLoopInvariant(BO->LHS))
5746 if (!
GEP ||
GEP->getPointerOperand() != PN ||
GEP->getNumIndices() != 1)
5749 if (!
L->isLoopInvariant(Idx))
5758 const SCEV *StartVal =
getSCEV(StartValueV);
5759 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5760 insertValueToMap(PN, PHISCEV);
5763 inferNoWrapViaConstantRanges(AR);
5770 "Accum is defined outside L, but is not invariant?");
5771 if (isAddRecNeverPoison(BEInst, L))
5778const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5786 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5792 }
else if (BEValueV != V) {
5796 }
else if (!StartValueV) {
5798 }
else if (StartValueV != V) {
5799 StartValueV =
nullptr;
5803 if (!BEValueV || !StartValueV)
5806 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5807 "PHI node already processed?");
5811 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5816 insertValueToMap(PN, SymbolicName);
5820 const SCEV *BEValue =
getSCEV(BEValueV);
5830 unsigned FoundIndex =
Add->getNumOperands();
5831 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5832 if (
Add->getOperand(i) == SymbolicName)
5833 if (FoundIndex == e) {
5838 if (FoundIndex !=
Add->getNumOperands()) {
5841 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5842 if (i != FoundIndex)
5843 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5855 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5862 if (
GEP->getOperand(0) == PN)
5870 const SCEV *StartVal =
getSCEV(StartValueV);
5871 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5876 forgetMemoizedResults({SymbolicName});
5877 insertValueToMap(PN, PHISCEV);
5880 inferNoWrapViaConstantRanges(AR);
5904 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5905 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5907 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5908 const SCEV *StartVal =
getSCEV(StartValueV);
5909 if (Start == StartVal) {
5913 forgetMemoizedResults({SymbolicName});
5914 insertValueToMap(PN, Shifted);
5924 eraseValueFromMap(PN);
5939 Use &LeftUse =
Merge->getOperandUse(0);
5940 Use &RightUse =
Merge->getOperandUse(1);
5976 assert(IDom &&
"At least the entry block should dominate PN");
5984const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
5989 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6006 CommonInst = IncomingInst;
6022ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6028 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6029 bool SCEVExprsIdentical =
6031 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6032 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6035const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6036 if (
const SCEV *S = createAddRecFromPHI(PN))
6046 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6049 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6058 struct FindClosure {
6059 const SCEV *OperandToFind;
6065 bool canRecurseInto(
SCEVTypes Kind)
const {
6068 return RootKind == Kind || NonSequentialRootKind == Kind ||
6073 : OperandToFind(OperandToFind), RootKind(RootKind),
6074 NonSequentialRootKind(
6078 bool follow(
const SCEV *S) {
6079 Found = S == OperandToFind;
6081 return !isDone() && canRecurseInto(S->
getSCEVType());
6084 bool isDone()
const {
return Found; }
6087 FindClosure FC(OperandToFind, RootKind);
6092std::optional<const SCEV *>
6093ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6103 switch (ICI->getPredicate()) {
6117 bool Signed = ICI->isSigned();
6118 const SCEV *LA =
getSCEV(TrueVal);
6126 if (LA == LS &&
RA == RS)
6128 if (LA == RS &&
RA == LS)
6131 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6132 if (
Op->getType()->isPointerTy()) {
6143 LS = CoerceOperand(LS);
6144 RS = CoerceOperand(RS);
6168 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6169 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6183 X = ZExt->getOperand();
6185 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6196 return std::nullopt;
6199static std::optional<const SCEV *>
6201 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6205 "Unexpected operands of a select.");
6217 return std::nullopt;
6232static std::optional<const SCEV *>
6236 return std::nullopt;
6239 const auto *SETrue = SE->
getSCEV(TrueVal);
6240 const auto *SEFalse = SE->
getSCEV(FalseVal);
6244const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6246 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6248 V->getType() ==
TrueVal->getType() &&
6249 "Types of select hands and of the result must match.");
6252 if (!
V->getType()->isIntegerTy(1))
6255 if (std::optional<const SCEV *> S =
6268 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6272 if (std::optional<const SCEV *> S =
6273 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6279 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6285 assert(
GEP->getSourceElementType()->isSized() &&
6286 "GEP source element type must be sized");
6289 for (
Value *Index :
GEP->indices())
6294APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6297 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6300 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6302 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6305 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6323 return GetShiftedByZeros(TZ);
6333 return GetShiftedByZeros(TZ);
6337 if (
M->hasNoUnsignedWrap()) {
6340 for (
const SCEV *Operand :
M->operands().drop_front())
6348 for (
const SCEV *Operand :
M->operands())
6350 return GetShiftedByZeros(TZ);
6355 if (
N->hasNoUnsignedWrap())
6356 return GetGCDMultiple(
N);
6359 for (
const SCEV *Operand :
N->operands().drop_front())
6361 return GetShiftedByZeros(TZ);
6378 CtxI = &*F.getEntryBlock().begin();
6385 .allowEphemerals(
true))
6386 .countMinTrailingZeros();
6387 return GetShiftedByZeros(
Known);
6400 return getConstantMultipleImpl(S, CtxI);
6402 auto I = ConstantMultipleCache.find(S);
6403 if (
I != ConstantMultipleCache.end())
6406 APInt Result = getConstantMultipleImpl(S, CtxI);
6407 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6408 assert(InsertPair.second &&
"Should insert a new key");
6409 return InsertPair.first->second;
6426 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6429 if (std::optional<ConstantRange>
Range = CB->getRange())
6433 if (std::optional<ConstantRange>
Range =
A->getRange())
6436 return std::nullopt;
6443 UnsignedRanges.erase(AddRec);
6444 SignedRanges.erase(AddRec);
6445 ConstantMultipleCache.erase(AddRec);
6450getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6476 Value *Start, *Step;
6483 assert(L && L->getHeader() ==
P->getParent());
6496 case Instruction::AShr:
6497 case Instruction::LShr:
6498 case Instruction::Shl:
6513 KnownStep.getBitWidth() ==
BitWidth);
6516 auto MaxShiftAmt = KnownStep.getMaxValue();
6518 bool Overflow =
false;
6519 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6526 case Instruction::AShr: {
6534 if (KnownStart.isNonNegative())
6537 KnownStart.getMaxValue() + 1);
6538 if (KnownStart.isNegative())
6541 KnownEnd.getMaxValue() + 1);
6544 case Instruction::LShr: {
6553 KnownStart.getMaxValue() + 1);
6555 case Instruction::Shl: {
6559 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6560 return ConstantRange(KnownStart.getMinValue(),
6561 KnownEnd.getMaxValue() + 1);
6586 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6593ScalarEvolution::getRangeRefIter(
const SCEV *S,
6594 ScalarEvolution::RangeSignHint SignHint) {
6595 DenseMap<const SCEV *, ConstantRange> &Cache =
6596 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6599 SmallPtrSet<const SCEV *, 8> Seen;
6603 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6604 if (!Seen.
insert(Expr).second)
6637 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6638 const SCEV *
P = WorkList[
I];
6642 for (
const SCEV *
Op :
P->operands())
6655 if (!WorkList.
empty()) {
6660 getRangeRef(
P, SignHint);
6664 return getRangeRef(S, SignHint, 0);
6667const APInt *ScalarEvolution::getConstantAPIntOrNull(
const SCEV *S) {
6669 return &
C->getAPInt();
6677 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6678 DenseMap<const SCEV *, ConstantRange> &Cache =
6679 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6686 auto I = Cache.
find(S);
6687 if (
I != Cache.
end())
6691 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6696 return getRangeRefIter(S, SignHint);
6699 ConstantRange ConservativeResult(
BitWidth,
true);
6700 using OBO = OverflowingBinaryOperator;
6704 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6708 ConservativeResult =
6715 ConservativeResult = ConstantRange(
6731 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6738 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6745 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6750 return setRange(Cast, SignHint,
X);
6755 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6756 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6758 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6759 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6760 ConservativeResult =
6761 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6763 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6764 unsigned WrapType = OBO::AnyWrap;
6765 if (
Add->hasNoSignedWrap())
6766 WrapType |= OBO::NoSignedWrap;
6767 if (
Add->hasNoUnsignedWrap())
6768 WrapType |= OBO::NoUnsignedWrap;
6770 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6772 return setRange(
Add, SignHint,
6773 ConservativeResult.intersectWith(
X, RangeType));
6777 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6779 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6780 return setRange(
Mul, SignHint,
6781 ConservativeResult.intersectWith(
X, RangeType));
6785 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6786 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6787 return setRange(UDiv, SignHint,
6788 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6796 if (!UnsignedMinValue.
isZero())
6797 ConservativeResult = ConservativeResult.intersectWith(
6798 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6807 bool AllNonNeg =
true;
6808 bool AllNonPos =
true;
6809 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6816 ConservativeResult = ConservativeResult.intersectWith(
6821 ConservativeResult = ConservativeResult.intersectWith(
6830 const SCEV *MaxBEScev =
6844 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6846 ConservativeResult =
6847 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6850 auto RangeFromFactoring = getRangeViaFactoring(
6852 ConservativeResult =
6853 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6859 const SCEV *SymbolicMaxBECount =
6864 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6865 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6866 ConservativeResult =
6867 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6872 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6882 ID = Intrinsic::umax;
6885 ID = Intrinsic::smax;
6889 ID = Intrinsic::umin;
6892 ID = Intrinsic::smin;
6899 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6900 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6902 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6903 return setRange(S, SignHint,
6904 ConservativeResult.intersectWith(
X, RangeType));
6913 ConservativeResult =
6914 ConservativeResult.intersectWith(*MDRange, RangeType);
6919 auto CR = getRangeForUnknownRecurrence(U);
6920 ConservativeResult = ConservativeResult.intersectWith(CR);
6931 if (
U->getType()->isPointerTy()) {
6934 unsigned PtrIdxDiff =
6935 DL.getPointerTypeSizeInBits(
U->getType()) -
BitWidth;
6936 NS = NS > PtrIdxDiff ? NS - PtrIdxDiff : 1;
6941 if (!
Known.Zero.getHiBits(NS).isZero())
6942 Known.Zero.setHighBits(NS);
6943 if (!
Known.One.getHiBits(NS).isZero())
6944 Known.One.setHighBits(NS);
6947 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
6948 ConservativeResult = ConservativeResult.intersectWith(
6949 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
6952 ConservativeResult = ConservativeResult.intersectWith(
6957 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6961 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
6962 DL, CanBeNull,
nullptr);
6978 ConservativeResult = ConservativeResult.intersectWith(
6988 return getRangeRef(AR, SignHint,
Depth + 1);
6992 ConstantRange RangeFromOps(
BitWidth,
false);
6994 for (
const auto &
Op :
Phi->operands()) {
6996 RangeFromOps = RangeFromOps.unionWith(OpRange);
6998 if (RangeFromOps.isFullSet())
7001 ConservativeResult =
7002 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7008 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7010 ConservativeResult = ConservativeResult.difference(Disallowed);
7013 return setRange(U, SignHint, std::move(ConservativeResult));
7019 return setRange(S, SignHint, std::move(ConservativeResult));
7027static std::pair<ConstantRange, bool>
7035 if (Step == 0 || MaxBECount == 0)
7036 return {StartRange,
true};
7042 return {ConstantRange::getFull(
BitWidth),
false};
7058 return {ConstantRange::getFull(
BitWidth),
false};
7071 APInt MovedBoundary;
7076 MovedBoundary = StartLower - std::move(
Offset);
7079 MovedBoundary = StartUpper + std::move(
Offset);
7083 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7090 if (StartRange.
contains(MovedBoundary))
7091 return {ConstantRange::getFull(
BitWidth),
false};
7094 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7096 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7104std::pair<ConstantRange, SCEVFlags>
7105ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7106 const APInt &MaxBECount) {
7110 "mismatched bit widths");
7119 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7121 StartSRange, MaxBECount,
7123 ConstantRange SR = SR1.unionWith(SR2);
7140ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7142 ScalarEvolution::RangeSignHint SignHint) {
7143 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7145 "This only works for non-self-wrapping AddRecs!");
7146 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7150 return ConstantRange::getFull(
BitWidth);
7158 return ConstantRange::getFull(
BitWidth);
7162 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7164 MaxItersWithoutWrap))
7165 return ConstantRange::getFull(
BitWidth);
7186 ConstantRange StartRange = getRangeRef(Start, SignHint);
7187 ConstantRange EndRange = getRangeRef(End, SignHint);
7188 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7192 return RangeBetween;
7197 return ConstantRange::getFull(
BitWidth);
7200 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7201 return RangeBetween;
7203 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7204 return RangeBetween;
7205 return ConstantRange::getFull(
BitWidth);
7210 const APInt &MaxBECount) {
7217 "mismatched bit widths");
7219 struct SelectPattern {
7220 Value *Condition =
nullptr;
7224 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7226 std::optional<unsigned> CastOp;
7240 CastOp = SCast->getSCEVType();
7241 S = SCast->getOperand();
7244 using namespace llvm::PatternMatch;
7251 Condition =
nullptr;
7283 bool isRecognized() {
return Condition !=
nullptr; }
7286 SelectPattern StartPattern(*
this,
BitWidth, Start);
7287 if (!StartPattern.isRecognized())
7288 return ConstantRange::getFull(
BitWidth);
7290 SelectPattern StepPattern(*
this,
BitWidth, Step);
7291 if (!StepPattern.isRecognized())
7292 return ConstantRange::getFull(
BitWidth);
7294 if (StartPattern.Condition != StepPattern.Condition) {
7298 return ConstantRange::getFull(
BitWidth);
7309 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7310 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7311 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7312 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7314 ConstantRange TrueRange =
7315 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7316 ConstantRange FalseRange =
7317 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7330 PDI && PDI->isDisjoint()) {
7345ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7358 SmallPtrSet<const SCEV *, 16> Visited;
7360 auto pushOp = [&](
const SCEV *S) {
7361 if (!Visited.
insert(S).second)
7364 if (Visited.
size() > 30) {
7375 while (!Worklist.
empty()) {
7377 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7378 if (!Bound || DT.dominates(Bound, DefI))
7385 return Bound ? Bound : &*F.getEntryBlock().begin();
7391 return getDefiningScopeBound(
Ops, Discard);
7394bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7396 if (
A->getParent() ==
B->getParent() &&
7401 auto *BLoop = LI.getLoopFor(
B->getParent());
7402 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7403 BLoop->getLoopPreheader() ==
A->getParent() &&
7405 A->getParent()->end()) &&
7413 SCEVPoisonCollector PC(
true);
7415 return PC.MaybePoison.
empty();
7418bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7428bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7445 for (
const Use &
Op :
I->operands()) {
7451 auto *DefI = getDefiningScopeBound(SCEVOps);
7452 return isGuaranteedToTransferExecutionTo(DefI,
I);
7455bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7457 if (isSCEVExprNeverPoison(
I))
7468 auto *ExitingBB =
L->getExitingBlock();
7472 SmallPtrSet<const Value *, 16> KnownPoison;
7481 while (!Worklist.
empty()) {
7484 for (
const Use &U :
Poison->uses()) {
7487 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7491 if (KnownPoison.
insert(PoisonUser).second)
7499ScalarEvolution::LoopProperties
7500ScalarEvolution::getLoopProperties(
const Loop *L) {
7501 using LoopProperties = ScalarEvolution::LoopProperties;
7503 auto Itr = LoopPropertiesCache.find(L);
7504 if (Itr == LoopPropertiesCache.end()) {
7507 return !
SI->isSimple();
7517 return I->mayWriteToMemory();
7520 LoopProperties LP = {
true,
7523 for (
auto *BB :
L->getBlocks())
7524 for (
auto &
I : *BB) {
7526 LP.HasNoAbnormalExits =
false;
7527 if (HasSideEffects(&
I))
7528 LP.HasNoSideEffects =
false;
7529 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7533 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7534 assert(InsertPair.second &&
"We just checked!");
7535 Itr = InsertPair.first;
7548const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7554 Stack.emplace_back(V,
false);
7555 while (!Stack.empty()) {
7556 auto E = Stack.back();
7557 Value *CurV = E.getPointer();
7565 const SCEV *CreatedSCEV =
nullptr;
7568 CreatedSCEV = createSCEV(CurV);
7573 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7577 insertValueToMap(CurV, CreatedSCEV);
7580 Stack.back().setInt(
true);
7583 Stack.emplace_back(
Op,
false);
7600 if (!DT.isReachableFromEntry(
I->getParent()))
7613 switch (BO->Opcode) {
7614 case Instruction::Add:
7615 case Instruction::Mul: {
7622 Ops.push_back(BO->
Op);
7626 Ops.push_back(BO->RHS);
7630 (BO->Opcode == Instruction::Add &&
7631 (NewBO->Opcode != Instruction::Add &&
7632 NewBO->Opcode != Instruction::Sub)) ||
7633 (BO->Opcode == Instruction::Mul &&
7634 NewBO->Opcode != Instruction::Mul)) {
7635 Ops.push_back(BO->LHS);
7640 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7643 Ops.push_back(BO->LHS);
7651 case Instruction::Sub:
7652 case Instruction::UDiv:
7653 case Instruction::URem:
7655 case Instruction::AShr:
7656 case Instruction::Shl:
7657 case Instruction::Xor:
7661 case Instruction::And:
7662 case Instruction::Or:
7666 case Instruction::LShr:
7673 Ops.push_back(BO->LHS);
7674 Ops.push_back(BO->RHS);
7678 switch (
U->getOpcode()) {
7679 case Instruction::Trunc:
7680 case Instruction::ZExt:
7681 case Instruction::SExt:
7682 case Instruction::PtrToAddr:
7683 case Instruction::PtrToInt:
7684 Ops.push_back(
U->getOperand(0));
7687 case Instruction::BitCast:
7689 Ops.push_back(
U->getOperand(0));
7694 case Instruction::SDiv:
7695 case Instruction::SRem:
7696 Ops.push_back(
U->getOperand(0));
7697 Ops.push_back(
U->getOperand(1));
7700 case Instruction::GetElementPtr:
7702 "GEP source element type must be sized");
7706 case Instruction::IntToPtr:
7709 case Instruction::PHI:
7740 Ops.push_back(CondICmp->getOperand(0));
7741 Ops.push_back(CondICmp->getOperand(1));
7761 case Instruction::Select: {
7763 auto CanSimplifyToUnknown = [
this,
U]() {
7781 if (CanSimplifyToUnknown())
7788 case Instruction::Call:
7789 case Instruction::Invoke:
7796 switch (
II->getIntrinsicID()) {
7797 case Intrinsic::abs:
7798 Ops.push_back(
II->getArgOperand(0));
7800 case Intrinsic::umax:
7801 case Intrinsic::umin:
7802 case Intrinsic::smax:
7803 case Intrinsic::smin:
7804 case Intrinsic::usub_sat:
7805 case Intrinsic::uadd_sat:
7806 Ops.push_back(
II->getArgOperand(0));
7807 Ops.push_back(
II->getArgOperand(1));
7809 case Intrinsic::start_loop_iterations:
7810 case Intrinsic::annotation:
7811 case Intrinsic::ptr_annotation:
7812 Ops.push_back(
II->getArgOperand(0));
7824const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7833 if (!DT.isReachableFromEntry(
I->getParent()))
7848 switch (BO->Opcode) {
7849 case Instruction::Add: {
7875 if (BO->Opcode == Instruction::Sub)
7883 if (BO->Opcode == Instruction::Sub)
7890 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7891 NewBO->Opcode != Instruction::Sub)) {
7901 case Instruction::Mul: {
7922 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7931 case Instruction::UDiv:
7935 case Instruction::URem:
7939 case Instruction::Sub: {
7942 Flags = getNoWrapFlagsFromUB(BO->
Op);
7947 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
7950 if (HasPtrLHS || HasPtrRHS) {
7955 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
7956 bool BothPtr) ->
const SCEV * {
7959 const SCEV *PtrSCEV =
getSCEV(PtrOp);
7969 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
7970 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
7978 case Instruction::And:
7984 if (CI->isMinusOne())
7986 const APInt &
A = CI->getValue();
7992 unsigned LZ =
A.countl_zero();
7993 unsigned TZ =
A.countr_zero();
7998 APInt EffectiveMask =
8000 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
8003 const SCEV *ShiftedLHS =
nullptr;
8007 unsigned MulZeros = OpC->getAPInt().countr_zero();
8008 unsigned GCD = std::min(MulZeros, TZ);
8013 const SCEV *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8035 case Instruction::Or:
8044 case Instruction::Xor:
8047 if (CI->isMinusOne())
8056 if (LBO->getOpcode() == Instruction::And &&
8057 LCI->getValue() == CI->getValue())
8058 if (
const SCEVZeroExtendExpr *Z =
8061 const SCEV *Z0 =
Z->getOperand();
8068 if (CI->getValue().isMask(Z0TySize))
8074 APInt Trunc = CI->getValue().trunc(Z0TySize);
8083 case Instruction::Shl:
8101 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8110 ConstantInt *
X = ConstantInt::get(
8116 case Instruction::AShr:
8138 const SCEV *AddTruncateExpr =
nullptr;
8139 ConstantInt *ShlAmtCI =
nullptr;
8140 const SCEV *AddConstant =
nullptr;
8142 if (L &&
L->getOpcode() == Instruction::Add) {
8150 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8157 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8165 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8170 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8175 if (AddTruncateExpr && ShlAmtCI) {
8187 const APInt &ShlAmt = ShlAmtCI->
getValue();
8191 const SCEV *CompositeExpr =
8193 if (
L->getOpcode() != Instruction::Shl)
8194 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8203 switch (
U->getOpcode()) {
8204 case Instruction::Trunc:
8207 case Instruction::ZExt:
8210 case Instruction::SExt:
8220 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8221 Type *Ty =
U->getType();
8229 case Instruction::BitCast:
8235 case Instruction::PtrToAddr: {
8242 case Instruction::PtrToInt:
8246 case Instruction::IntToPtr:
8250 case Instruction::SDiv:
8257 case Instruction::SRem:
8264 case Instruction::GetElementPtr:
8267 case Instruction::PHI:
8270 case Instruction::Select:
8271 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8274 case Instruction::Call:
8275 case Instruction::Invoke:
8280 switch (
II->getIntrinsicID()) {
8281 case Intrinsic::abs:
8285 case Intrinsic::umax:
8289 case Intrinsic::umin:
8293 case Intrinsic::smax:
8297 case Intrinsic::smin:
8301 case Intrinsic::usub_sat: {
8302 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8303 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8307 case Intrinsic::uadd_sat: {
8308 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8309 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8313 case Intrinsic::start_loop_iterations:
8314 case Intrinsic::annotation:
8315 case Intrinsic::ptr_annotation:
8319 case Intrinsic::vscale:
8339 auto *ExitCountType = ExitCount->
getType();
8340 assert(ExitCountType->isIntegerTy());
8342 1 + ExitCountType->getScalarSizeInBits());
8355 auto CanAddOneWithoutOverflow = [&]() {
8357 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8368 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8398 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8399 assert(L->isLoopExiting(ExitingBlock) &&
8400 "Exiting block must actually branch out of the loop!");
8409 const auto *MaxExitCount =
8417 L->getExitingBlocks(ExitingBlocks);
8420 if (ExitingBlocks.
empty() ||
8436 const LoopGuards &Guards) {
8440 const SCEV *TCExpr =
8448 : (
unsigned)Multiple.getZExtValue();
8452 const SCEV *ExitCount) {
8474 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8475 assert(L->isLoopExiting(ExitingBlock) &&
8476 "Exiting block must actually branch out of the loop!");
8486 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8488 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8490 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8500 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8503 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8506 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8514 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8521 return getBackedgeTakenInfo(L).getExact(L,
this);
8523 return getBackedgeTakenInfo(L).getConstantMax(
this);
8525 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8532 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8537 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8541 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8551 for (
PHINode &PN : Header->phis())
8552 if (Visited.
insert(&PN).second)
8556ScalarEvolution::BackedgeTakenInfo &
8557ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8558 auto &BTI = getBackedgeTakenInfo(L);
8559 if (BTI.hasFullInfo())
8562 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8565 return Pair.first->second;
8567 BackedgeTakenInfo
Result =
8568 computeBackedgeTakenCount(L,
true);
8570 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8573ScalarEvolution::BackedgeTakenInfo &
8574ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8580 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8581 BackedgeTakenCounts.try_emplace(L);
8583 return Pair.first->second;
8588 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8595 if (
Result.hasAnyInfo()) {
8598 auto LoopUsersIt = LoopUsers.find(L);
8599 if (LoopUsersIt != LoopUsers.end())
8601 forgetMemoizedResults(ToForget);
8604 for (PHINode &PN :
L->getHeader()->phis())
8605 ConstantEvolutionLoopExitValue.erase(&PN);
8613 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8622 BackedgeTakenCounts.clear();
8623 PredicatedBackedgeTakenCounts.clear();
8624 BECountUsers.clear();
8625 LoopPropertiesCache.clear();
8626 ConstantEvolutionLoopExitValue.clear();
8627 ValueExprMap.clear();
8628 ValuesAtScopes.clear();
8629 ValuesAtScopesUsers.clear();
8630 LoopDispositions.clear();
8631 BlockDispositions.clear();
8632 UnsignedRanges.clear();
8633 SignedRanges.clear();
8634 ExprValueMap.clear();
8636 ConstantMultipleCache.clear();
8637 PredicatedSCEVRewrites.clear();
8639 FoldCacheUser.clear();
8641void ScalarEvolution::visitAndClearUsers(
8646 if (ValueExprMap.
empty()) {
8650 while (!Worklist.
empty()) {
8657 if (It != ValueExprMap.
end()) {
8659 eraseValueFromMap(It->first);
8661 ConstantEvolutionLoopExitValue.erase(PN);
8675 while (!LoopWorklist.
empty()) {
8679 forgetBackedgeTakenCounts(CurrL,
false);
8680 forgetBackedgeTakenCounts(CurrL,
true);
8683 PredicatedSCEVRewrites.remove_if(
8684 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8686 auto LoopUsersItr = LoopUsers.find(CurrL);
8687 if (LoopUsersItr != LoopUsers.end())
8692 visitAndClearUsers(Worklist, Visited, ToForget);
8694 LoopPropertiesCache.erase(CurrL);
8697 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8699 forgetMemoizedResults(ToForget);
8716 visitAndClearUsers(Worklist, Visited, ToForget);
8718 forgetMemoizedResults(ToForget);
8729 visitAndClearUsers(Worklist, Visited, ToForget);
8731 forgetMemoizedResults(ToForget);
8739 auto InvalidateValue = [&](
Value *Val) {
8743 struct InvalidationRootCollector {
8747 InvalidationRootCollector(
Loop *L) : L(L) {}
8749 bool follow(
const SCEV *S) {
8755 if (L->contains(AddRec->
getLoop()))
8760 bool isDone()
const {
return false; }
8763 InvalidationRootCollector
C(L);
8765 forgetMemoizedResults(
C.Roots);
8788 BlockDispositions.clear();
8789 LoopDispositions.clear();
8806 while (!Worklist.
empty()) {
8808 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8809 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8810 if (!LoopDispoRemoved && !BlockDispoRemoved)
8812 auto Users = SCEVUsers.find(Curr);
8813 if (
Users != SCEVUsers.end())
8826const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8830 if (!isComplete() || ExitNotTaken.
empty())
8841 for (
const auto &ENT : ExitNotTaken) {
8842 const SCEV *BECount = ENT.ExactNotTaken;
8845 "We should only have known counts for exiting blocks that dominate "
8848 Ops.push_back(BECount);
8853 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8854 "Predicate should be always true!");
8863const ScalarEvolution::ExitNotTakenInfo *
8864ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8865 const BasicBlock *ExitingBlock,
8866 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8867 for (
const auto &ENT : ExitNotTaken)
8868 if (ENT.ExitingBlock == ExitingBlock) {
8869 if (ENT.hasAlwaysTruePredicate())
8871 else if (Predicates) {
8881const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8883 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8884 if (!getConstantMax())
8887 for (
const auto &ENT : ExitNotTaken)
8888 if (!ENT.hasAlwaysTruePredicate()) {
8896 "No point in having a non-constant max backedge taken count!");
8897 return getConstantMax();
8900const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8902 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8910 for (
const auto &ENT : ExitNotTaken) {
8911 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8914 "We should only have known counts for exiting blocks that "
8920 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8921 "Predicate should be always true!");
8924 if (ExitCounts.
empty())
8933bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8935 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8936 return !ENT.hasAlwaysTruePredicate();
8938 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8954 this->ExactNotTaken = E = ConstantMaxNotTaken;
8955 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8960 "Exact is not allowed to be less precise than Constant Max");
8963 "Exact is not allowed to be less precise than Symbolic Max");
8966 "Symbolic Max is not allowed to be less precise than Constant Max");
8969 "No point in having a non-constant max backedge taken count!");
8971 for (
const auto PredList : PredLists)
8972 for (
const auto *
P : PredList) {
8980 "Backedge count should be int");
8983 "Max backedge count should be int");
8996ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8998 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8999 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
9000 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9002 ExitNotTaken.reserve(ExitCounts.
size());
9003 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
9004 std::back_inserter(ExitNotTaken),
9005 [&](
const EdgeExitInfo &EEI) {
9006 BasicBlock *ExitBB = EEI.first;
9007 const ExitLimit &EL = EEI.second;
9008 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
9009 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
9014 "No point in having a non-constant max backedge taken count!");
9018ScalarEvolution::BackedgeTakenInfo
9019ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
9020 bool AllowPredicates) {
9022 L->getExitingBlocks(ExitingBlocks);
9024 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9027 bool CouldComputeBECount =
true;
9029 const SCEV *MustExitMaxBECount =
nullptr;
9030 const SCEV *MayExitMaxBECount =
nullptr;
9031 bool MustExitMaxOrZero =
false;
9032 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9043 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9044 if (ExitIfTrue == CI->
isZero())
9048 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9050 assert((AllowPredicates || EL.Predicates.empty()) &&
9051 "Predicated exit limit when predicates are not allowed!");
9056 ++NumExitCountsComputed;
9060 CouldComputeBECount =
false;
9067 "Exact is known but symbolic isn't?");
9068 ++NumExitCountsNotComputed;
9083 DT.dominates(ExitBB, Latch)) {
9084 if (!MustExitMaxBECount) {
9085 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9086 MustExitMaxOrZero = EL.MaxOrZero;
9089 EL.ConstantMaxNotTaken);
9093 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9096 EL.ConstantMaxNotTaken);
9100 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9104 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9110 for (
const auto &Pair : ExitCounts) {
9112 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9114 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9115 {
L, AllowPredicates});
9117 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9118 MaxBECount, MaxOrZero);
9121ScalarEvolution::ExitLimit
9122ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9123 bool IsOnlyExit,
bool AllowPredicates) {
9124 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9128 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9133 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9134 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9135 "It should have one successor in loop and one exit block!");
9146 if (!
L->contains(SBB)) {
9151 assert(Exit &&
"Exiting block must have at least one exit");
9152 return computeExitLimitFromSingleExitSwitch(
9153 L, SI, Exit, IsOnlyExit);
9160 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9161 bool AllowPredicates) {
9162 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9163 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9164 ControlsOnlyExit, AllowPredicates);
9167std::optional<ScalarEvolution::ExitLimit>
9168ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9169 bool ExitIfTrue,
bool ControlsOnlyExit,
9170 bool AllowPredicates) {
9172 (void)this->ExitIfTrue;
9173 (void)this->AllowPredicates;
9175 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9176 this->AllowPredicates == AllowPredicates &&
9177 "Variance in assumed invariant key components!");
9178 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9179 if (Itr == TripCountMap.end())
9180 return std::nullopt;
9184void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9186 bool ControlsOnlyExit,
9187 bool AllowPredicates,
9189 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9190 this->AllowPredicates == AllowPredicates &&
9191 "Variance in assumed invariant key components!");
9193 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9194 assert(InsertResult.second &&
"Expected successful insertion!");
9199ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9200 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9201 bool ControlsOnlyExit,
bool AllowPredicates) {
9203 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9207 ExitLimit EL = computeExitLimitFromCondImpl(
9208 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9209 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9213ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9214 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9215 bool ControlsOnlyExit,
bool AllowPredicates) {
9217 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9218 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9219 return *LimitFromBinOp;
9225 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9226 if (EL.hasFullInfo() || !AllowPredicates)
9230 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9250 const WithOverflowInst *WO;
9265 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9266 ControlsOnlyExit, AllowPredicates);
9267 if (EL.hasAnyInfo())
9272 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9275std::optional<ScalarEvolution::ExitLimit>
9276ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9280 bool AllowPredicates) {
9289 return std::nullopt;
9293 ExitLimit EL0 = computeExitLimitFromCondCached(
9294 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9295 ExitLimit EL1 = computeExitLimitFromCondCached(
9296 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9301 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9306 if (EitherMayExit) {
9316 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9318 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9321 EL1.ConstantMaxNotTaken);
9323 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9325 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9328 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9332 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9333 BECount = EL0.ExactNotTaken;
9346 SymbolicMaxBECount =
9348 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9352ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9353 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9354 bool AllowPredicates) {
9366 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9368 if (EL.hasAnyInfo())
9371 auto *ExhaustiveCount =
9372 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9375 return ExhaustiveCount;
9377 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9380ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9382 bool ControlsOnlyExit,
bool AllowPredicates) {
9407 ConstantRange CompRange =
9425 InnerLHS = ZExt->getOperand();
9472 if (EL.hasAnyInfo())
9489 if (EL.hasAnyInfo())
return EL;
9522 ControlsOnlyExit, AllowPredicates);
9523 if (EL.hasAnyInfo())
9541 ControlsOnlyExit, AllowPredicates);
9542 if (EL.hasAnyInfo())
9553ScalarEvolution::ExitLimit
9554ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9556 BasicBlock *ExitingBlock,
9557 bool ControlsOnlyExit) {
9558 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9561 if (
Switch->getDefaultDest() == ExitingBlock)
9565 "Default case must not exit the loop!");
9571 if (EL.hasAnyInfo())
9583 "Evaluation of SCEV at constant didn't fold correctly?");
9587ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9597 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9604 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9606 unsigned &OutShiftAmt) {
9607 using namespace PatternMatch;
9609 ConstantInt *ShiftAmt;
9611 OutOpCode = Instruction::LShr;
9613 OutOpCode = Instruction::AShr;
9615 OutOpCode = Instruction::Shl;
9620 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9635 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9637 unsigned &ShiftAmtOut) {
9638 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9654 if (MatchPositiveShift(
LHS, V, OpC, Amt)) {
9655 PostShiftOpCode = OpC;
9661 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9664 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9670 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9677 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9683 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9695 ConstantInt *StableValue =
nullptr;
9700 case Instruction::AShr: {
9707 if (
Known.isNonNegative())
9708 StableValue = ConstantInt::get(Ty, 0);
9709 else if (
Known.isNegative())
9710 StableValue = ConstantInt::get(Ty, -1,
true);
9716 case Instruction::LShr:
9717 case Instruction::Shl:
9727 "Otherwise cannot be an operand to a branch instruction");
9729 if (
Result->isNullValue()) {
9738 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9740 const SCEV *StartSCEV =
getSCEV(StartValue);
9744 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9745 MaxBTC = std::min(MaxBTC, RangeBTC);
9749 const SCEV *UpperBound =
9767 if (
const Function *
F = CI->getCalledFunction())
9777 if (!L->contains(
I))
return false;
9782 return L->getHeader() ==
I->getParent();
9861 if (!
I)
return nullptr;
9875 std::vector<Constant*>
Operands(
I->getNumOperands());
9877 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9886 if (!
C)
return nullptr;
9908 if (IncomingVal != CurrentVal) {
9911 IncomingVal = CurrentVal;
9923ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9926 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9935 DenseMap<Instruction *, Constant *> CurrentIterVals;
9937 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9943 for (PHINode &
PHI : Header->phis()) {
9945 CurrentIterVals[&
PHI] = StartCST;
9947 if (!CurrentIterVals.
count(PN))
9948 return RetVal =
nullptr;
9954 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9957 unsigned IterationNum = 0;
9959 for (; ; ++IterationNum) {
9960 if (IterationNum == NumIterations)
9961 return RetVal = CurrentIterVals[PN];
9965 DenseMap<Instruction *, Constant *> NextIterVals;
9970 NextIterVals[PN] = NextPHI;
9972 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9978 for (
const auto &
I : CurrentIterVals) {
9980 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9985 for (
const auto &
I : PHIsToCompute) {
9986 PHINode *
PHI =
I.first;
9989 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9992 if (NextPHI !=
I.second)
9993 StoppedEvolving =
false;
9998 if (StoppedEvolving)
9999 return RetVal = CurrentIterVals[PN];
10001 CurrentIterVals.swap(NextIterVals);
10005const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
10015 DenseMap<Instruction *, Constant *> CurrentIterVals;
10017 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10020 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
10022 for (PHINode &
PHI : Header->phis()) {
10024 CurrentIterVals[&
PHI] = StartCST;
10026 if (!CurrentIterVals.
count(PN))
10034 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10041 if (CondVal->getValue() ==
uint64_t(ExitWhen)) {
10042 ++NumBruteForceTripCountsComputed;
10047 DenseMap<Instruction *, Constant *> NextIterVals;
10053 for (
const auto &
I : CurrentIterVals) {
10055 if (!
PHI ||
PHI->getParent() != Header)
continue;
10058 for (PHINode *
PHI : PHIsToCompute) {
10060 if (NextPHI)
continue;
10062 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10065 CurrentIterVals.
swap(NextIterVals);
10073 auto &
Values = ValuesAtScopes[V];
10077 return LS.second ? LS.second :
SCEVUse(V);
10079 Values.emplace_back(L,
nullptr);
10082 SCEVUse C = computeSCEVAtScope(V, L);
10083 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10084 if (LS.first == L) {
10090 ValuesAtScopesUsers[
C.getPointer()].push_back({L, V});
10117 switch (V->getSCEVType()) {
10150 assert(!
C->getType()->isPointerTy() &&
10151 "Can only have one pointer, and it must be last");
10176const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10177 SmallVectorImpl<SCEVUse> &NewOps) {
10211SCEVUse ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10212 switch (
V->getSCEVType()) {
10223 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10234 for (++i; i !=
e; ++i)
10274 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10284 for (++i; i !=
e; ++i) {
10289 return getWithOperands(V, NewOps);
10304 const Loop *CurrLoop = this->LI[
I->getParent()];
10315 if (BackedgeTakenCount->
isZero()) {
10316 Value *InitValue =
nullptr;
10317 bool MultipleInitValues =
false;
10323 MultipleInitValues =
true;
10328 if (!MultipleInitValues && InitValue)
10337 unsigned InLoopPred =
10348 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10362 SmallVector<Constant *, 4>
Operands;
10364 bool MadeImprovement =
false;
10379 MadeImprovement |= OrigV != OpV;
10384 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10389 if (!MadeImprovement)
10410const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10412 return stripInjectiveFunctions(ZExt->getOperand());
10414 return stripInjectiveFunctions(SExt->getOperand());
10432 assert(
A != 0 &&
"A must be non-zero.");
10448 if (MinTZ < Mult2 && L->getLoopPredecessor())
10450 if (MinTZ < Mult2) {
10473 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10493static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10499 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10500 << *AddRec <<
'\n');
10503 if (!LC || !MC || !
NC) {
10504 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10505 return std::nullopt;
10511 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10519 N =
N.sext(NewWidth);
10520 M = M.sext(NewWidth);
10521 L = L.sext(NewWidth);
10538 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10539 <<
", multiplied by " <<
T <<
'\n');
10548 std::optional<APInt>
Y) {
10550 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10553 return XW.
slt(YW) ? *
X : *
Y;
10556 return std::nullopt;
10557 return X ? *
X : *
Y;
10574 return std::nullopt;
10575 unsigned W =
X->getBitWidth();
10595static std::optional<APInt>
10601 return std::nullopt;
10604 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10605 std::optional<APInt>
X =
10608 return std::nullopt;
10613 return std::nullopt;
10628static std::optional<APInt>
10632 "Starting value of addrec should be 0");
10633 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10634 <<
Range <<
", addrec " << *AddRec <<
'\n');
10638 "Addrec's initial value should be in range");
10644 return std::nullopt;
10654 auto SolveForBoundary =
10655 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10658 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10659 << Bound <<
" (before multiplying by " << M <<
")\n");
10662 std::optional<APInt> SO;
10665 "signed overflow\n");
10669 "unsigned overflow\n");
10670 std::optional<APInt> UO =
10673 auto LeavesRange = [&] (
const APInt &
X) {
10676 if (
Range.contains(V0->getValue()))
10681 if (
Range.contains(
V1->getValue()))
10690 return {std::nullopt,
false};
10695 if (LeavesRange(*Min))
10696 return { Min,
true };
10697 std::optional<APInt> Max = Min == SO ? UO : SO;
10698 if (LeavesRange(*Max))
10699 return { Max,
true };
10702 return {std::nullopt,
true};
10709 auto SL = SolveForBoundary(
Lower);
10710 auto SU = SolveForBoundary(
Upper);
10713 if (!SL.second || !SU.second)
10714 return std::nullopt;
10757ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10759 bool ControlsOnlyExit,
10760 bool AllowPredicates) {
10771 if (
C->getValue()->isZero())
return C;
10775 const SCEVAddRecExpr *AddRec =
10778 if (!AddRec && AllowPredicates)
10784 if (!AddRec || AddRec->
getLoop() != L)
10795 return ExitLimit(R, R, R,
false, Predicates);
10853 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10883 const SCEV *
Exact =
10891 const SCEV *SymbolicMax =
10893 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10902 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10910 return ExitLimit(
E, M, S,
false, Predicates);
10913ScalarEvolution::ExitLimit
10914ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10922 if (!
C->getValue()->isZero())
10932std::pair<const BasicBlock *, const BasicBlock *>
10933ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10944 if (
const Loop *L = LI.getLoopFor(BB))
10945 return {
L->getLoopPredecessor(),
L->getHeader()};
10947 return {
nullptr, BB};
10956 if (
A ==
B)
return true;
10971 if (ComputesEqualValues(AI, BI))
10979 const SCEV *Op0, *Op1;
10998 auto TrivialCase = [&](
bool TriviallyTrue) {
11007 const SCEV *NewLHS, *NewRHS;
11031 return TrivialCase(
false);
11032 return TrivialCase(
true);
11051 RAdd->hasNoSignedWrap()) ||
11053 RAdd->hasNoUnsignedWrap())) {
11073 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
11074 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
11077 C->getAPInt().isStrictlyPositive()) ||
11101 const APInt &
RA = RC->getAPInt();
11103 bool SimplifiedByConstantRange =
false;
11108 return TrivialCase(
true);
11110 return TrivialCase(
false);
11119 Changed = SimplifiedByConstantRange =
true;
11123 if (!SimplifiedByConstantRange) {
11140 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11146 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11152 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11158 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11178 return TrivialCase(
true);
11180 return TrivialCase(
false);
11285 auto NonRecursive = [OrNegative](
const SCEV *S) {
11287 return C->getAPInt().isPowerOf2() ||
11288 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11294 if (NonRecursive(S))
11304 const SCEV *S, uint64_t M,
11313 APInt C = Cst->getAPInt();
11314 return C.urem(M) == 0;
11320 const SCEV *SmodM =
11341 [&](
SCEVUse Op) { return isKnownMultipleOf(Op, M, Predicates); }))
11348 return isKnownMultipleOf(Op, M, Predicates);
11354 return isKnownMultipleOf(Op, M, Predicates);
11361 for (
auto *
A : *Predicates)
11362 if (
A->implies(
P, *
this))
11375std::pair<const SCEV *, const SCEV *>
11378 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11380 return { Start, Start };
11382 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11391 getUsedLoops(LHS, LoopsUsed);
11392 getUsedLoops(RHS, LoopsUsed);
11394 if (LoopsUsed.
empty())
11399 for (
const auto *L1 : LoopsUsed)
11400 for (
const auto *L2 : LoopsUsed)
11401 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11402 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11403 "Domination relationship is not a linear order");
11433 SplitRHS.second) &&
11443 isKnownPredicateViaSplitting(Pred, LHS, RHS) ||
11444 isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11454 return std::nullopt;
11469 if (KnownWithoutContext)
11470 return KnownWithoutContext;
11477 return std::nullopt;
11483 const Loop *L = LHS->getLoop();
11488std::optional<ScalarEvolution::MonotonicPredicateType>
11491 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11497 auto ResultSwapped =
11500 assert(*ResultSwapped != *Result &&
11501 "monotonicity should flip as we flip the predicate");
11508std::optional<ScalarEvolution::MonotonicPredicateType>
11509ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11523 return std::nullopt;
11527 "Should be greater or less!");
11531 if (!LHS->hasNoUnsignedWrap())
11532 return std::nullopt;
11536 "Relational predicate is either signed or unsigned!");
11537 if (!
LHS->hasNoSignedWrap())
11538 return std::nullopt;
11540 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11548 return std::nullopt;
11551std::optional<ScalarEvolution::LoopInvariantPredicate>
11558 return std::nullopt;
11565 if (!ArLHS || ArLHS->
getLoop() != L)
11566 return std::nullopt;
11570 return std::nullopt;
11596 return std::nullopt;
11633 return std::nullopt;
11636std::optional<ScalarEvolution::LoopInvariantPredicate>
11641 Pred, LHS, RHS, L, CtxI, MaxIter))
11651 Pred, LHS, RHS, L, CtxI,
Op))
11653 return std::nullopt;
11656std::optional<ScalarEvolution::LoopInvariantPredicate>
11671 return std::nullopt;
11678 if (!AR || AR->
getLoop() != L)
11679 return std::nullopt;
11684 Pred = Pred.dropSameSign();
11688 return std::nullopt;
11694 if (Step != One && Step != MinusOne)
11695 return std::nullopt;
11701 return std::nullopt;
11707 return std::nullopt;
11715 if (Step == MinusOne)
11719 return std::nullopt;
11725bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11731 auto CheckRange = [&](
bool IsSigned) {
11734 return RangeLHS.
icmp(Pred, RangeRHS);
11743 if (CheckRange(
true) || CheckRange(
false))
11752bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11759 APInt &OutC2,
SCEVFlags ExpectedFlags) {
11760 SCEVUse XNonConstOp, XConstOp;
11761 SCEVUse YNonConstOp, YConstOp;
11765 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11768 XFlagsPresent = ExpectedFlags;
11773 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11776 YFlagsPresent = ExpectedFlags;
11779 if (YNonConstOp != XNonConstOp)
11787 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11790 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11850bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11871bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11872 const SCEV *
LHS,
const SCEV *
RHS) {
11877 return any_of(*BB, [&](
const Instruction &
I) {
11878 using namespace llvm::PatternMatch;
11883 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11897 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11902 "This cannot be done on broken IR!");
11905 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11914 if (LoopContinuePredicate &&
11915 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11916 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11921 if (WalkingBEDominatingConds)
11927 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11928 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11935 const SCEV *LoopCounter =
11943 for (
auto &AssumeVH : AC.assumptions()) {
11950 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11954 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11957 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11958 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11959 assert(DTN &&
"should reach the loop header before reaching the root!");
11962 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11980 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
11993 if (!DT.isReachableFromEntry(BB))
11997 "This cannot be done on broken IR!");
12005 const bool ProvingStrictComparison =
12007 bool ProvedNonStrictComparison =
false;
12008 bool ProvedNonEquality =
false;
12011 if (!ProvedNonStrictComparison)
12012 ProvedNonStrictComparison = Fn(NonStrictPredicate);
12013 if (!ProvedNonEquality)
12015 if (ProvedNonStrictComparison && ProvedNonEquality)
12020 if (ProvingStrictComparison) {
12022 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
12024 if (SplitAndProve(ProofFn))
12029 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
12031 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
12033 if (ProvingStrictComparison) {
12035 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
12037 if (SplitAndProve(ProofFn))
12046 const Loop *ContainingLoop = LI.getLoopFor(BB);
12048 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
12052 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
12053 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
12056 if (!BlockEntryPredicate)
12065 for (
auto &AssumeVH : AC.assumptions()) {
12069 if (!DT.dominates(CI, BB))
12072 if (ProveViaCond(CI->getArgOperand(0),
false))
12078 F.getParent(), Intrinsic::experimental_guard);
12080 for (
const auto *GU : GuardDecl->users())
12082 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12083 if (ProveViaCond(Guard->getArgOperand(0),
false))
12098 "LHS is not available at Loop Entry");
12100 "RHS is not available at Loop Entry");
12102 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12113 if (FoundCondValue ==
12117 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12121 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12124 const Value *Op0, *Op1;
12127 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12131 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12132 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12136 if (!ICI)
return false;
12140 CmpPredicate FoundPred;
12149 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12152bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12153 const SCEV *
RHS, CmpPredicate FoundPred,
12154 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12155 const Instruction *CtxI) {
12165 auto *WideType = FoundLHS->
getType();
12177 TruncFoundLHS, TruncFoundRHS, CtxI))
12203 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12207bool ScalarEvolution::isImpliedCondBalancedTypes(
12212 "Types should be balanced!");
12219 if (FoundLHS == FoundRHS)
12223 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12235 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12250 LHS, FoundLHS, FoundRHS, CtxI);
12252 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12259 assert(P1 != P2 &&
"Handled earlier!");
12263 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12267 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12270 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12271 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12272 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12277 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12288 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12289 CanonicalRHS, CanonicalFoundLHS,
12290 CanonicalFoundRHS);
12295 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12296 CanonicalRHS, CanonicalFoundLHS,
12297 CanonicalFoundRHS);
12304 const SCEVConstant *
C =
nullptr;
12305 const SCEV *
V =
nullptr;
12323 if (Min ==
C->getAPInt()) {
12328 APInt SharperMin = Min + 1;
12331 case ICmpInst::ICMP_SGE:
12332 case ICmpInst::ICMP_UGE:
12335 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12340 case ICmpInst::ICMP_SGT:
12341 case ICmpInst::ICMP_UGT:
12351 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12356 case ICmpInst::ICMP_SLE:
12357 case ICmpInst::ICMP_ULE:
12358 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12359 LHS, V, getConstant(SharperMin), CtxI))
12363 case ICmpInst::ICMP_SLT:
12364 case ICmpInst::ICMP_ULT:
12365 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12366 LHS, V, getConstant(Min), CtxI))
12380 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12384 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12387 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12403std::optional<APInt>
12410 APInt DiffMul(BW, 1);
12413 for (
unsigned I = 0;
I < 8; ++
I) {
12422 if (LAR->getLoop() != MAR->getLoop())
12423 return std::nullopt;
12427 if (!LAR->isAffine() || !MAR->isAffine())
12428 return std::nullopt;
12430 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12431 return std::nullopt;
12433 Less = LAR->getStart();
12434 More = MAR->getStart();
12439 auto MatchConstMul =
12440 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12445 return std::nullopt;
12447 if (
auto MatchedMore = MatchConstMul(More)) {
12448 if (
auto MatchedLess = MatchConstMul(
Less)) {
12449 if (MatchedMore->second == MatchedLess->second) {
12450 More = MatchedMore->first;
12451 Less = MatchedLess->first;
12452 DiffMul *= MatchedMore->second;
12463 Diff +=
C->getAPInt() * DiffMul;
12466 Diff -=
C->getAPInt() * DiffMul;
12469 Multiplicity[S] +=
Mul;
12471 auto Decompose = [&](
const SCEV *S,
int Mul) {
12478 Decompose(More, 1);
12479 Decompose(
Less, -1);
12483 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12484 for (
const auto &[S,
Mul] : Multiplicity) {
12489 return std::nullopt;
12491 }
else if (
Mul == -1) {
12493 return std::nullopt;
12496 return std::nullopt;
12500 if (NewMore == More || NewLess ==
Less)
12501 return std::nullopt;
12507 if (!More && !
Less)
12511 if (!More || !
Less)
12512 return std::nullopt;
12516 return std::nullopt;
12519bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12541 const auto *Latch = L->getLoopLatch();
12544 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12553 const auto *Latch = L->getLoopLatch();
12556 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12566bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12569 const SCEV *FoundLHS,
12570 const SCEV *FoundRHS) {
12579 if (!AddRecFoundLHS)
12586 const Loop *
L = AddRecFoundLHS->getLoop();
12587 if (L != AddRecLHS->getLoop())
12626 if (!RDiff || *LDiff != *RDiff)
12629 if (LDiff->isMinValue())
12632 APInt FoundRHSLimit;
12635 FoundRHSLimit = -(*RDiff);
12647bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12648 const SCEV *
RHS,
const SCEV *FoundLHS,
12649 const SCEV *FoundRHS,
unsigned Depth) {
12650 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12654 bool Erased = PendingMerges.erase(LPhi);
12655 assert(Erased &&
"Failed to erase LPhi!");
12659 bool Erased = PendingMerges.erase(RPhi);
12660 assert(Erased &&
"Failed to erase RPhi!");
12668 if (!PendingMerges.insert(Phi).second)
12682 if (!PendingMerges.insert(Phi).second)
12688 if (!LPhi && !RPhi)
12699 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12703 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12704 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12705 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12706 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12709 if (RPhi && RPhi->getParent() == LBB) {
12716 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12717 if (!ProvedEasily(L, R))
12728 auto *RLoop = RAR->
getLoop();
12729 auto *Predecessor = RLoop->getLoopPredecessor();
12730 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12732 if (!ProvedEasily(L1, RAR->
getStart()))
12734 auto *Latch = RLoop->getLoopLatch();
12735 assert(Latch &&
"Loop with AddRec with no latch?");
12756 if (
auto *
Loop = LI.getLoopFor(LBB))
12759 if (!ProvedEasily(L,
RHS))
12766bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12769 const SCEV *FoundLHS,
12770 const SCEV *FoundRHS) {
12773 if (
RHS == FoundRHS) {
12778 if (
LHS != FoundLHS)
12785 Value *Shiftee, *ShiftValue;
12787 using namespace PatternMatch;
12788 if (
match(SUFoundRHS->getValue(),
12790 auto *ShifteeS =
getSCEV(Shiftee);
12808bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12809 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12810 const SCEV *FoundRHS) {
12842 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12850 return Diff == FoundDiff;
12853bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12855 const SCEV *FoundLHS,
12856 const SCEV *FoundRHS,
12857 const Instruction *CtxI) {
12858 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12860 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12862 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12863 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12865 isImpliedCondOperandsViaMatchingDiff(Pred,
LHS,
RHS, FoundLHS,
12867 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12871template <
typename MinMaxExprType>
12873 const SCEV *Candidate) {
12878 return is_contained(MinMaxExpr->operands(), Candidate);
12891 const SCEV *LStart, *RStart, *Step;
12988bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12990 const SCEV *FoundLHS,
12991 const SCEV *FoundRHS,
12995 "LHS and RHS have different sizes?");
12998 "FoundLHS and FoundRHS have different sizes?");
13032 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
13034 return Ext->getOperand();
13041 auto *OrigLHS =
LHS;
13042 auto *OrigFoundLHS = FoundLHS;
13043 LHS = GetOpFromSExt(
LHS);
13044 FoundLHS = GetOpFromSExt(FoundLHS);
13047 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
13050 FoundRHS,
Depth + 1);
13063 if (!LHSAddExpr->hasNoSignedWrap())
13066 SCEVUse LL = LHSAddExpr->getOperand(0);
13067 SCEVUse LR = LHSAddExpr->getOperand(1);
13071 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
13072 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
13077 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
13083 using namespace llvm::PatternMatch;
13102 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13110 auto *DTy = Denominator->getType();
13111 auto *FRHSTy = FoundRHS->
getType();
13112 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13131 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13142 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13144 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13152 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13185bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13189 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13193 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13196bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13199 const SCEV *FoundLHS,
13200 const SCEV *FoundRHS) {
13236 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13242bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13243 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13244 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13258 ConstantRange FoundLHSRange =
13262 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13269 return LHSRange.
icmp(Pred, ConstRHS);
13272bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13273 bool IsSigned,
bool Invert) {
13280 APInt MaxRHS = getRangeMax(
RHS,
true, Invert);
13285 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13288 APInt MaxRHS = getRangeMax(
RHS,
false, Invert);
13293 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13306ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
const SCEV *Stride,
13308 bool IsSigned,
bool Invert) {
13323 APInt MinStart = getRangeMin(Start, IsSigned, Invert);
13336 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13342 APInt MaxEnd = getRangeMax(End, IsSigned, Invert);
13348 :
APIntOps::umax(MaxEnd, MinStart);
13350 APInt Delta = MaxEnd - MinStart;
13354 const SCEV *DeltaExpr =
13362ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13363 const Loop *L,
bool IsSigned,
bool Invert,
13364 bool ControlsOnlyExit,
bool AllowPredicates) {
13368 std::optional<LoopGuards> CachedGuards;
13369 auto getGuards = [&]() ->
const LoopGuards & {
13372 return *CachedGuards;
13380 bool PredicatedIV =
false;
13382 if (!
IV && !Invert) {
13386 auto canProveNUW = [&]() {
13389 if (!ControlsOnlyExit)
13410 Limit = Limit.
zext(OuterBitWidth);
13423 Type *Ty = ZExt->getType();
13433 if (!
IV && AllowPredicates) {
13438 PredicatedIV =
true;
13442 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13456 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13463 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13466 const SCEV *GuardedStride = Stride;
13470 bool IVMayOverflow =
true;
13474 if (!PositiveStride) {
13475 const SCEV *LoopGuardedStride =
applyLoopGuards(Stride, getGuards());
13477 GuardedStride = LoopGuardedStride;
13478 PositiveStride =
true;
13485 if (!PositiveStride) {
13534 const SCEVPredicate *
P =
13555 auto wouldZeroStrideBeUB = [&]() {
13567 if (!wouldZeroStrideBeUB()) {
13574 IVMayOverflow = canIVOverflowOnLT(
RHS, GuardedStride, IsSigned, Invert);
13575 if (IVMayOverflow && !NoWrap)
13588 const SCEV *
Start =
IV->getStart();
13594 const SCEV *OrigStart =
Start;
13595 const SCEV *OrigRHS =
RHS;
13596 if (
Start->getType()->isPointerTy()) {
13610 assert(!Invert &&
"RHS must be loop-invariant for Invert");
13612 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13613 any(RHSAddRec->getNoWrapFlags())) {
13626 const SCEV *RHSStart = RHSAddRec->getStart();
13627 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13639 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13648 BECountIfBackedgeTaken =
13675 bool AddingStrideMinusOneMayOverflow = IVMayOverflow && [&] {
13722 if (!Invert && (Start == Stride || Start ==
getMinusSCEV(Stride, One))) {
13739 auto StepBack = [&](
const SCEV *
V,
const SCEV *
Offset) ->
const SCEV * {
13744 auto Distance = [&](
const SCEV *From,
const SCEV *To) {
13748 const SCEV *OrigPrevStart = StepBack(OrigStart, Stride);
13755 if ((!AddingStrideMinusOneMayOverflow ||
13787 const SCEV *Numerator =
13793 auto canProveRHSIsAtOrBeyondStart = [&]() {
13798 auto SwapIfInverted = [&](
const SCEV *
A,
const SCEV *
B) {
13799 return Invert ? std::pair(
B,
A) : std::pair(
A,
B);
13808 auto [GELHS, GERHS] = SwapIfInverted(OrigRHS, OrigStart);
13823 auto [GTLHS, GTRHS] = SwapIfInverted(OrigRHS, StepBack(OrigStart, One));
13829 if (canProveRHSIsAtOrBeyondStart()) {
13852 const SCEV *Delta = Distance(Start, End);
13853 if (!AddingStrideMinusOneMayOverflow) {
13865 const SCEV *ConstantMaxBECount;
13866 bool MaxOrZero =
false;
13868 ConstantMaxBECount = BECount;
13870 ConstantMaxBECount = computeMaxBECountForLT(
13877 const APInt *IfTaken, *RangeMax;
13880 IfTaken->
ugt(*RangeMax)) {
13881 ConstantMaxBECount =
getZero(BECountIfBackedgeTaken->getType());
13883 ConstantMaxBECount = BECountIfBackedgeTaken;
13893 const SCEV *SymbolicMaxBECount =
13895 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13901 if (
Range.isFullSet())
13906 if (!SC->getValue()->isZero()) {
13912 return ShiftedAddRec->getNumIterationsInRange(
13913 Range.subtract(SC->getAPInt()), SE);
13944 APInt ExitVal = (End +
A).udiv(
A);
13957 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13958 "Linear scev computation is off in a bad way!");
13989 assert(!
Last->isZero() &&
"Recurrency with zero step?");
14022 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14024 SE->ConstantEvolutionLoopExitValue.erase(PN);
14025 SE->eraseValueFromMap(getValPtr());
14029void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
14030 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14040 : CallbackVH(
V), SE(se) {}
14049 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
14051 LoopDispositions(64), BlockDispositions(64) {
14063 F.getParent(), Intrinsic::experimental_guard);
14064 HasGuards = GuardDecl && !GuardDecl->use_empty();
14068 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
14069 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14070 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14071 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14072 PendingMerges(
std::
move(Arg.PendingMerges)),
14073 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14074 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14075 PredicatedBackedgeTakenCounts(
14076 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14077 BECountUsers(
std::
move(Arg.BECountUsers)),
14078 ConstantEvolutionLoopExitValue(
14079 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14080 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14081 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14082 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14083 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14084 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14085 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14086 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14087 SignedRanges(
std::
move(Arg.SignedRanges)),
14088 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14089 UniquePreds(
std::
move(Arg.UniquePreds)),
14090 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14091 ConstantSCEVs(
std::
move(Arg.ConstantSCEVs)),
14092 LoopUsers(
std::
move(Arg.LoopUsers)),
14093 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14094 FirstUnknown(Arg.FirstUnknown) {
14095 Arg.FirstUnknown =
nullptr;
14104 Tmp->~SCEVUnknown();
14106 FirstUnknown =
nullptr;
14108 ExprValueMap.clear();
14109 ValueExprMap.clear();
14111 BackedgeTakenCounts.clear();
14112 PredicatedBackedgeTakenCounts.clear();
14114 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14115 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14116 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14117 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14139 L->getHeader()->printAsOperand(OS,
false);
14143 L->getExitingBlocks(ExitingBlocks);
14144 if (ExitingBlocks.
size() != 1)
14145 OS <<
"<multiple exits> ";
14149 OS <<
"backedge-taken count is ";
14152 OS <<
"Unpredictable backedge-taken count.";
14155 if (ExitingBlocks.
size() > 1)
14156 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14157 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14165 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14168 OS <<
"\n Predicates:\n";
14169 for (
const auto *
P : Predicates)
14177 L->getHeader()->printAsOperand(OS,
false);
14182 OS <<
"constant max backedge-taken count is ";
14185 OS <<
", actual taken count either this or zero.";
14187 OS <<
"Unpredictable constant max backedge-taken count. ";
14192 L->getHeader()->printAsOperand(OS,
false);
14197 OS <<
"symbolic max backedge-taken count is ";
14200 OS <<
", actual taken count either this or zero.";
14202 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14206 if (ExitingBlocks.
size() > 1)
14207 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14208 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14218 OS <<
"\n predicated symbolic max exit count for "
14219 << ExitingBlock->
getName() <<
": ";
14221 OS <<
"\n Predicates:\n";
14222 for (
const auto *
P : Predicates)
14233 L->getHeader()->printAsOperand(OS,
false);
14236 OS <<
"Predicated backedge-taken count is ";
14239 OS <<
"Unpredictable predicated backedge-taken count.";
14241 OS <<
" Predicates:\n";
14242 for (
const auto *
P : Preds)
14247 auto *PredConstantMax =
14249 if (PredConstantMax != ConstantBTC) {
14251 L->getHeader()->printAsOperand(OS,
false);
14254 OS <<
"Predicated constant max backedge-taken count is ";
14257 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14259 OS <<
" Predicates:\n";
14260 for (
const auto *
P : Preds)
14265 auto *PredSymbolicMax =
14267 if (SymbolicBTC != PredSymbolicMax) {
14269 L->getHeader()->printAsOperand(OS,
false);
14272 OS <<
"Predicated symbolic max backedge-taken count is ";
14275 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14277 OS <<
" Predicates:\n";
14278 for (
const auto *
P : Preds)
14284 L->getHeader()->printAsOperand(OS,
false);
14311 OS <<
"Computable";
14321 OS <<
"DoesNotDominate";
14327 OS <<
"ProperlyDominates";
14344 OS <<
"Classifying expressions for: ";
14345 F.printAsOperand(OS,
false);
14360 const Loop *L = LI.getLoopFor(
I.getParent());
14375 OS <<
"\t\t" "Exits: ";
14378 OS <<
"<<Unknown>>";
14384 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14386 Iter->getHeader()->printAsOperand(OS,
false);
14394 InnerL->getHeader()->printAsOperand(OS,
false);
14405 OS <<
"Determining loop execution counts for: ";
14406 F.printAsOperand(OS,
false);
14414 auto &
Values = LoopDispositions[S];
14415 for (
auto &V :
Values) {
14416 if (V.getPointer() == L)
14421 auto &Values2 = LoopDispositions[S];
14423 if (V.getPointer() == L) {
14432ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14450 if (L->contains(AR->
getLoop()) &&
14452 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14457 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14458 " dominate the contained loop's header?");
14485 bool HasVarying =
false;
14486 bool HasUniform =
false;
14528 auto &
Values = BlockDispositions[S];
14529 for (
auto &V :
Values) {
14530 if (V.getPointer() == BB)
14535 auto &Values2 = BlockDispositions[S];
14537 if (V.getPointer() == BB) {
14546ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14575 bool Proper =
true;
14586 if (Instruction *
I =
14588 if (
I->getParent() == BB)
14590 if (DT.properlyDominates(
I->getParent(), BB))
14609void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14612 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14613 auto It = BECounts.find(L);
14614 if (It != BECounts.end()) {
14615 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14616 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14618 auto UserIt = BECountUsers.find(S);
14619 assert(UserIt != BECountUsers.end());
14624 BECounts.erase(It);
14632 while (!Worklist.
empty()) {
14634 auto Users = SCEVUsers.find(Curr);
14635 if (
Users != SCEVUsers.end())
14636 for (
const auto *User :
Users->second)
14637 if (ToForget.
insert(User).second)
14641 for (
const auto *S : ToForget)
14642 forgetMemoizedResultsImpl(S);
14644 PredicatedSCEVRewrites.remove_if(
14645 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14648void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14649 LoopDispositions.erase(S);
14650 BlockDispositions.erase(S);
14651 UnsignedRanges.erase(S);
14652 SignedRanges.erase(S);
14653 HasRecMap.erase(S);
14654 ConstantMultipleCache.erase(S);
14657 UnsignedWrapViaInductionTried.erase(AR);
14658 SignedWrapViaInductionTried.erase(AR);
14661 auto ExprIt = ExprValueMap.find(S);
14662 if (ExprIt != ExprValueMap.end()) {
14663 for (
Value *V : ExprIt->second) {
14664 auto ValueIt = ValueExprMap.find_as(V);
14665 if (ValueIt != ValueExprMap.end())
14666 ValueExprMap.erase(ValueIt);
14668 ExprValueMap.erase(ExprIt);
14671 auto ScopeIt = ValuesAtScopes.find(S);
14672 if (ScopeIt != ValuesAtScopes.end()) {
14673 for (
const auto &Pair : ScopeIt->second)
14675 llvm::erase(ValuesAtScopesUsers[Pair.second.getPointer()],
14676 std::make_pair(Pair.first, S));
14677 ValuesAtScopes.erase(ScopeIt);
14680 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14681 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14682 for (
const auto &Pair : ScopeUserIt->second)
14685 llvm::erase_if(ValuesAtScopes[Pair.second], [&](
const auto &LS) {
14686 return LS.first == Pair.first && LS.second.getPointer() == S;
14688 ValuesAtScopesUsers.erase(ScopeUserIt);
14691 auto BEUsersIt = BECountUsers.find(S);
14692 if (BEUsersIt != BECountUsers.end()) {
14694 auto Copy = BEUsersIt->second;
14695 for (
const auto &Pair : Copy)
14696 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14697 BECountUsers.erase(BEUsersIt);
14700 auto FoldUser = FoldCacheUser.find(S);
14701 if (FoldUser != FoldCacheUser.end())
14702 for (
auto &KV : FoldUser->second)
14703 FoldCache.erase(KV);
14704 FoldCacheUser.erase(S);
14708ScalarEvolution::getUsedLoops(
const SCEV *S,
14710 struct FindUsedLoops {
14711 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14712 : LoopsUsed(LoopsUsed) {}
14713 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14714 bool follow(
const SCEV *S) {
14720 bool isDone()
const {
return false; }
14723 FindUsedLoops
F(LoopsUsed);
14724 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14727void ScalarEvolution::getReachableBlocks(
14730 Worklist.
push_back(&F.getEntryBlock());
14731 while (!Worklist.
empty()) {
14733 if (!Reachable.
insert(BB).second)
14741 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14748 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14752 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14787 SCEVMapper SCM(SE2);
14789 SE2.getReachableBlocks(ReachableBlocks, F);
14791 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14809 while (!LoopStack.
empty()) {
14815 if (!ReachableBlocks.
contains(L->getHeader()))
14820 auto It = BackedgeTakenCounts.find(L);
14821 if (It == BackedgeTakenCounts.end())
14825 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14845 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14846 if (Delta && !Delta->
isZero()) {
14847 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14848 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14849 dbgs() <<
"New: " << *NewBECount <<
"\n";
14850 dbgs() <<
"Delta: " << *Delta <<
"\n";
14858 while (!Worklist.
empty()) {
14860 if (ValidLoops.
insert(L).second)
14861 Worklist.
append(L->begin(), L->end());
14863 for (
const auto &KV : ValueExprMap) {
14868 "AddRec references invalid loop");
14873 auto It = ExprValueMap.find(KV.second);
14874 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14875 dbgs() <<
"Value " << *KV.first
14876 <<
" is in ValueExprMap but not in ExprValueMap\n";
14881 if (!ReachableBlocks.
contains(
I->getParent()))
14883 const SCEV *OldSCEV = SCM.visit(KV.second);
14885 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14886 if (Delta && !Delta->
isZero()) {
14887 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14888 <<
"Old: " << *OldSCEV <<
"\n"
14889 <<
"New: " << *NewSCEV <<
"\n"
14890 <<
"Delta: " << *Delta <<
"\n";
14896 for (
const auto &KV : ExprValueMap) {
14897 for (
Value *V : KV.second) {
14898 const SCEV *S = ValueExprMap.lookup(V);
14900 dbgs() <<
"Value " << *V
14901 <<
" is in ExprValueMap but not in ValueExprMap\n";
14904 if (S != KV.first) {
14905 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14906 << *KV.first <<
"\n";
14913 for (
const auto &S : UniqueSCEVs) {
14918 auto It = SCEVUsers.find(
Op);
14919 if (It != SCEVUsers.end() && It->second.count(&S))
14921 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14922 <<
" is not being tracked!\n";
14928 for (
const auto &ValueAndVec : ValuesAtScopes) {
14930 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14931 const Loop *L = LoopAndValueAtScope.first;
14932 SCEVUse ValueAtScope = LoopAndValueAtScope.second;
14934 auto It = ValuesAtScopesUsers.find(ValueAtScope.
getPointer());
14935 if (It != ValuesAtScopesUsers.end() &&
14938 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14939 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14945 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14946 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14947 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14948 const Loop *L = LoopAndValue.first;
14949 const SCEV *
Value = LoopAndValue.second;
14951 auto It = ValuesAtScopes.find(
Value);
14954 if (It != ValuesAtScopes.end() &&
any_of(It->second, [&](
const auto &LS) {
14955 return LS.first == L && LS.second.getPointer() == ValueAtScope;
14958 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14959 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14965 auto VerifyBECountUsers = [&](
bool Predicated) {
14967 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14968 for (
const auto &LoopAndBEInfo : BECounts) {
14969 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14970 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14972 auto UserIt = BECountUsers.find(S);
14973 if (UserIt != BECountUsers.end() &&
14974 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14976 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14977 <<
" missing from BECountUsers\n";
14984 VerifyBECountUsers(
false);
14985 VerifyBECountUsers(
true);
14988 for (
auto &[S,
Values] : LoopDispositions) {
14989 for (
auto [
Loop, CachedDisposition] :
Values) {
14991 if (CachedDisposition != RecomputedDisposition) {
14992 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
14993 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
14994 << RecomputedDisposition <<
"\n";
15001 for (
auto &[S,
Values] : BlockDispositions) {
15002 for (
auto [BB, CachedDisposition] :
Values) {
15004 if (CachedDisposition != RecomputedDisposition) {
15005 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
15006 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
15007 <<
", actual " << RecomputedDisposition <<
"\n";
15014 for (
auto [
FoldID, Expr] : FoldCache) {
15015 auto I = FoldCacheUser.find(Expr);
15016 if (
I == FoldCacheUser.end()) {
15017 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
15022 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
15026 for (
auto [Expr, IDs] : FoldCacheUser) {
15027 for (
auto &
FoldID : IDs) {
15030 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
15035 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
15036 <<
" != " << *Expr <<
"!\n";
15047 for (
auto [S, Multiple] : ConstantMultipleCache) {
15049 if ((Multiple != 0 && RecomputedMultiple != 0 &&
15050 Multiple.
urem(RecomputedMultiple) != 0 &&
15051 RecomputedMultiple.
urem(Multiple) != 0)) {
15052 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
15053 << *S <<
" : Computed " << RecomputedMultiple
15054 <<
" but cache contains " << Multiple <<
"!\n";
15062 FunctionAnalysisManager::Invalidator &Inv) {
15094 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15095 <<
F.getName() <<
"':\n";
15101 "Scalar Evolution Analysis",
false,
true)
15150 const SCEV *LHS,
const SCEV *RHS) {
15152 assert(LHS->getType() == RHS->getType() &&
15153 "Type mismatch between LHS and RHS");
15156 ID.AddInteger(Pred);
15157 ID.AddPointer(LHS);
15158 ID.AddPointer(RHS);
15160 if (
const auto *S = UniquePreds.lookup(ID, Token))
15164 UniquePreds.insert(Eq, Token);
15175 ID.AddInteger(AddedFlags);
15177 if (
const auto *S = UniquePreds.lookup(ID, Token))
15179 auto *OF =
new (SCEVAllocator)
15181 UniquePreds.insert(OF, Token);
15201 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15202 return Rewriter.visit(S);
15208 for (
const auto *Pred : U->getPredicates())
15210 if (IPred->getLHS() == Expr &&
15212 return IPred->getRHS();
15214 if (IPred->getLHS() == Expr &&
15215 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15216 return IPred->getRHS();
15219 return convertToAddRecWithPreds(Expr);
15222 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15238 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15255 explicit SCEVPredicateRewriter(
15256 const Loop *L, ScalarEvolution &SE,
15257 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15258 const SCEVPredicate *Pred)
15259 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15261 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15264 return Pred && Pred->
implies(
P, SE);
15270 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15273 return addOverflowAssumption(
A);
15282 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15286 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15288 if (!PredicatedRewrite)
15290 for (
const auto *
P : PredicatedRewrite->second){
15293 if (L != WP->getExpr()->getLoop())
15296 if (!addOverflowAssumption(
P))
15299 return PredicatedRewrite->first;
15302 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15303 const SCEVPredicate *Pred;
15312 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15319 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15339 if (!Step->
isOne())
15364 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15365 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15378 return Op->LHS == LHS &&
Op->RHS == RHS;
15385 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15387 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15412 const SCEV *Start = AR->getStart();
15413 const SCEV *OpStart =
Op->AR->getStart();
15418 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15427 const SCEV *Step = AR->getStepRecurrence(SE);
15428 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15449 SCEVFlags ScevFlags = AR->getNoWrapFlags();
15471 for (
const auto *
P : Preds)
15484 return this->implies(I, SE);
15496 const Loop *L = NWrap->getExpr()->getLoop();
15503 return RewrittenAR &&
15509 for (
const auto *Pred : Preds)
15510 Pred->print(OS,
Depth);
15515 for (
const auto *Pred : Set->Preds)
15523 bool CheckImplies = Preds.
size() < 16;
15526 if (CheckImplies &&
implies(
N, SE))
15532 for (
auto *
P : Preds) {
15533 if (CheckImplies &&
N->implies(
P, SE))
15537 Preds = std::move(PrunedPreds);
15538 Preds.push_back(
N);
15545 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15554 SCEVUsers[
Op].insert(
User);
15558 const SCEV *Expr = SE.getSCEV(V);
15563 RewriteEntry &Entry = RewriteMap[Expr];
15566 if (Entry.second && Generation == Entry.first)
15567 return Entry.second;
15572 Expr = Entry.second;
15574 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15575 Entry = {Generation, NewSCEV};
15581 if (!BackedgeCount) {
15583 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15584 for (
const auto *
P : Preds)
15587 return BackedgeCount;
15591 if (!SymbolicMaxBackedgeCount) {
15593 SymbolicMaxBackedgeCount =
15594 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15595 for (
const auto *
P : Preds)
15598 return SymbolicMaxBackedgeCount;
15602 if (!SmallConstantMaxTripCount) {
15604 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15605 for (
const auto *
P : Preds)
15608 return *SmallConstantMaxTripCount;
15612 if (Preds->implies(&Pred, SE))
15617 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15618 updateGeneration();
15631void PredicatedScalarEvolution::updateGeneration() {
15633 if (++Generation == 0) {
15634 for (
auto &
II : RewriteMap) {
15635 const SCEV *Rewritten =
II.second.second;
15645 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15651 ExtraPreds->
append(NewPreds);
15657 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15663 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15666 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15670 for (
auto *BB : L.getBlocks())
15671 for (
auto &
I : *BB) {
15672 if (!SE.isSCEVable(
I.getType()))
15675 auto *Expr = SE.getSCEV(&
I);
15676 auto II = RewriteMap.find(Expr);
15678 if (
II == RewriteMap.end())
15682 if (
II->second.second == Expr)
15687 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15695 LoopGuards Guards(SE);
15703void ScalarEvolution::LoopGuards::collectFromPHI(
15711 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15712 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15726 auto &RewriteMap =
G->second.RewriteMap;
15727 if (RewriteMap.empty())
15729 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15730 if (S == RewriteMap.end())
15736 return {C0, SM->getSCEVType()};
15739 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15740 MinMaxPattern
P2) -> MinMaxPattern {
15741 auto [C1,
T1] =
P1;
15742 auto [C2, T2] =
P2;
15743 if (!C1 || !C2 ||
T1 != T2)
15747 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15749 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15751 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15753 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15758 auto P = GetMinMaxConst(0);
15759 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15762 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15765 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15768 Guards.RewriteMap.insert({
LHS,
RHS});
15776 const APInt &DivisorVal,
15778 const APInt *ExprVal;
15791 const APInt &DivisorVal,
15793 const APInt *ExprVal;
15801 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15815 const SCEV *URemRHS =
nullptr;
15819 const SCEV *Multiple =
15821 DivInfo[URemLHS] = Multiple;
15823 Multiples[URemLHS] =
C->getAPInt();
15843 auto IsMinMaxSCEVWithNonNegativeConstant =
15847 if (
MinMax->getNumOperands() != 2)
15850 if (
C->getAPInt().isNegative())
15852 SCTy =
MinMax->getSCEVType();
15861 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15863 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15868 auto *DivisibleExpr =
15876void ScalarEvolution::LoopGuards::collectFromBlock(
15878 const BasicBlock *
Block,
const BasicBlock *Pred,
15886 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15897 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15899 if (From == FromRewritten)
15901 RewriteMap[From] = To;
15907 auto GetMaybeRewritten = [&](
const SCEV *S) {
15908 return RewriteMap.lookup_or(S, S);
15915 const SCEV *MatchLHS,
15916 const SCEV *MatchRHS) {
15917 const SCEVConstant *C1;
15920 if (!
match(MatchLHS,
15932 const SCEV *RewrittenLHS = GetMaybeRewritten(LHSUnknown);
15933 ExactRegion = ExactRegion.intersectWith(SE.
getUnsignedRange(RewrittenLHS),
15938 if (ExactRegion.isEmptySet() || ExactRegion.isWrappedSet() ||
15939 ExactRegion.isFullSet())
15942 const SCEV *RegionMin = SE.
getConstant(ExactRegion.getUnsignedMin());
15943 const SCEV *RegionMax = SE.
getConstant(ExactRegion.getUnsignedMax());
15944 const SCEV *ClampedLHS =
15946 AddRewrite(LHSUnknown, RewrittenLHS, ClampedLHS);
15949 if (MatchRangeCheckIdiom(Predicate,
LHS,
RHS))
15962 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15964 const APInt &DividesBy =
15979 switch (Predicate) {
16008 SmallPtrSet<const SCEV *, 16> Visited;
16010 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
16014 while (!Worklist.
empty()) {
16018 if (!Visited.
insert(From).second)
16020 const SCEV *FromRewritten = GetMaybeRewritten(From);
16021 const SCEV *To =
nullptr;
16023 switch (Predicate) {
16028 EnqueueOperands(
UMax);
16034 EnqueueOperands(
SMax);
16040 EnqueueOperands(
UMin);
16046 EnqueueOperands(
SMin);
16054 const SCEV *OneAlignedUp =
16056 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16068 const SCEVConstant *
C;
16077 Guards.NotEqual.insert({
LHS,
RHS});
16086 AddRewrite(From, FromRewritten, To);
16103 SE.F.
getParent(), Intrinsic::experimental_guard);
16105 for (
const auto *GU : GuardDecl->users())
16107 if (Guard->getFunction() ==
Block->getParent() &&
16116 unsigned NumCollectedConditions = 0;
16118 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16120 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16122 const CondBrInst *LoopEntryPredicate =
16124 if (!LoopEntryPredicate)
16129 NumCollectedConditions++;
16133 if (
Depth > 0 && NumCollectedConditions == 2)
16141 if (Pair.second->hasNPredecessorsOrMore(2) &&
16143 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16144 for (
auto &Phi : Pair.second->phis())
16155 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16156 SmallVector<Value *, 8> Worklist;
16157 SmallPtrSet<Value *, 8> Visited;
16159 while (!Worklist.
empty()) {
16166 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16190 DenseMap<const SCEV *, APInt> Multiples;
16192 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16199 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16200 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16204 for (
const auto &[K, Divisor] : Multiples) {
16205 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16206 Guards.RewriteMap[
K] =
16208 Guards.
rewrite(K), Divisor, SE),
16217 Guards.PreserveNUW =
true;
16218 Guards.PreserveNSW =
true;
16219 for (
const SCEV *Expr : ExprsToRewrite) {
16220 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16221 Guards.PreserveNUW &=
16223 Guards.PreserveNSW &=
16230 if (ExprsToRewrite.size() > 1) {
16231 for (
const SCEV *Expr : ExprsToRewrite) {
16232 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16233 Guards.RewriteMap.erase(Expr);
16234 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16243 class SCEVLoopGuardRewriter
16254 NotEqual(Guards.NotEqual) {
16255 if (Guards.PreserveNUW)
16257 if (Guards.PreserveNSW)
16264 return Map.lookup_or(Expr, Expr);
16268 if (
const SCEV *S = Map.lookup(Expr))
16275 if (
const SCEV *S = Map.lookup(Expr))
16282 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16283 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16284 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16286 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16287 if (
const SCEV *S = Map.lookup(NarrowExt))
16288 return SE.getZeroExtendExpr(S, Ty);
16289 Bitwidth = Bitwidth / 2;
16297 if (
const SCEV *S = Map.lookup(Expr))
16304 if (
const SCEV *S = Map.lookup(Expr))
16310 if (
const SCEV *S = Map.lookup(Expr))
16316 if (
const SCEV *S = Map.lookup(Expr))
16321 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16326 if (NotEqual.contains({LHS, RHS})) {
16328 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16329 return SE.getUMaxExpr(OneAlignedUp, S);
16336 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16347 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16348 return SE.getAddExpr(
16351 if (
const SCEV *S = Map.lookup(
Add))
16352 return SE.getAddExpr(Expr->
getOperand(0), S);
16360 const SCEV *S =
nullptr;
16367 S = Map.lookup(SE.getAddExpr(NewC, Expr->
getOperand(1)));
16370 return SE.getAddExpr(S, SE.getMinusOne(Expr->
getType()));
16405 if (RewriteMap.empty() && NotEqual.empty())
16408 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16409 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 bool hasNoUnsignedWrap(BinaryOperator &I)
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)
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 PushLoopPHIs(const Loop *L, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push PHI nodes in the header of the given loop onto the given Worklist.
static void insertFoldCacheEntry(const ScalarEvolution::FoldID &ID, const SCEV *S, DenseMap< ScalarEvolution::FoldID, const SCEV * > &FoldCache, DenseMap< const SCEV *, SmallVector< ScalarEvolution::FoldID, 2 > > &FoldCacheUser)
static cl::opt< bool > ClassifyExpressions("scalar-evolution-classify-expressions", cl::Hidden, cl::init(true), cl::desc("When printing analysis, include information on every instruction"))
static bool hasHugeExpression(ArrayRef< SCEVUse > Ops)
Returns true if Ops contains a huge SCEV (the subtree of S contains at least HugeExprThreshold nodes)...
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 bool IsKnownPredicateViaAddRecMonotonicity(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Is LHS Pred RHS true because one of them is an AddRec that is known not to go below its own start val...
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 PHINode * getConstantEvolvingPHI(Value *V, const Loop *L, const TargetLibraryInfo *TLI)
getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node in the loop that V is deri...
static bool canConstantFold(const Instruction *I, const TargetLibraryInfo *TLI)
Return true if we can constant fold an instruction of the specified type, assuming that all operands ...
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 PHINode * getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L, DenseMap< Instruction *, PHINode * > &PHIMap, const TargetLibraryInfo *TLI, unsigned Depth)
getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by recursing through each instructi...
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 SCEVFlags getNoWrapFlagsForGEP(GEPOperator *GEP, const SCEV *Accum, ScalarEvolution &SE)
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 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 bool IsKnownPredicateViaAddRecStart(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
static const SCEV * getPreStartForExtend(const SCEVAddRecExpr *AR, ScalarEvolution *SE, unsigned Depth)
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< 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 SCEVFlags StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, ArrayRef< SCEVUse > Ops, SCEVFlags Flags)
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 canConstantEvolve(Instruction *I, const Loop *L, const TargetLibraryInfo *TLI)
Determine whether this instruction can constant evolve within this loop assuming its operands can all...
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 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 std::optional< BinaryOp > MatchBinaryOp(Value *V, const DataLayout &DL, AssumptionCache &AC, const DominatorTree &DT, const Instruction *CtxI)
Try to map V into a BinaryOp, and return std::nullopt on failure.
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 * 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.
This is the base class for all instructions that perform data casts.
This class is the base class for the comparison instructions.
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 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:
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
iterator find(const_arg_type_t< KeyT > Val)
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
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_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive,...
void swap(DenseMapBase &RHS)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
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.
Insertion token: a failed lookup fills it in, the matching insert consumes it.
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)
This class represents a freeze function that returns random concrete value if an operand is either a ...
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.
This instruction inserts a single (scalar) element into a VectorType value.
This instruction inserts a struct field of array element value into an aggregate value.
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 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 SCEVUse getExitValue(ScalarEvolution &SE) const
Return the value of this recurrences when its loop exits, i.e.
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(SCEVFlags 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(SCEVFlags 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
SCEVFlags getNoWrapFlags(SCEVFlags Mask=FlagsNoWrapMask) const
bool hasNoSelfWrap() const
size_t getNumOperands() const
bool hasNoSignedWrap() 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 * visitPtrToAddrExpr(const SCEVPtrToAddrExpr *Expr)
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 SCEVFlags, 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.
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
static constexpr auto FlagsNoWrapMask
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.
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.
static constexpr auto FlagNone
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.
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 ...
static bool hasFlags(SCEVFlags Flags, SCEVFlags TestFlags)
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 * getZeroExtendExpr(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEV * getUDivCeilSCEV(const SCEV *N, const SCEV *D)
Compute ceil(N / D).
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterations(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L at given Context duri...
LLVM_ABI Type * getWiderType(Type *Ty1, Type *Ty2) const
LLVM_ABI const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)
LLVM_ABI bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
LLVM_ABI const SCEV * getElementCount(Type *Ty, ElementCount EC, SCEVFlags Flags=SCEV::FlagNone)
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 * 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 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 const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEVFlags Flags=SCEV::FlagNone, unsigned Depth=0)
Return LHS-RHS.
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 * 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 SCEVUse getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
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 void registerUser(const SCEV *User, ArrayRef< SCEVUse > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
LLVM_ABI const SCEV * getConstant(ConstantInt *V)
LLVM_ABI const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
LLVM_ABI const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
static SCEVFlags setFlags(SCEVFlags Flags, SCEVFlags OnFlags)
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 void forgetValues(ArrayRef< Value * > Values)
Batched forgetValue: invalidates all Values in one shared def-use walk, avoiding the redundant re-tra...
LLVM_ABI const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &Operands)
LLVM_ABI const SCEV * getCastExpr(SCEVTypes Kind, SCEVUse Op, Type *Ty)
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 SCEVUse getAddRecExpr(SCEVUse Start, SCEVUse Step, const Loop *L, SCEVFlagsPair Flags)
Get an add recurrence expression for the specified loop.
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 isKnownMultipleOf(const SCEV *S, uint64_t M, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Check that S is a multiple of M.
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.
static SCEVFlags clearFlags(SCEVFlags Flags, SCEVFlags OffFlags)
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.
static SCEVFlags maskFlags(SCEVFlags Flags, SCEVFlags Mask)
Convenient SCEVFlags manipulation.
LLVM_ABI bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
LLVM_ABI const SCEV * getTruncateExpr(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI SCEVUse getAddExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlagsPair Flags={}, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
LLVM_ABI const SCEV * getZeroExtendExprImpl(SCEVUse 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 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...
LLVM_ABI std::optional< SCEVFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
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 * getAnyExtendExpr(SCEVUse Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
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.
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 * getSignExtendExpr(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEV * getUMaxExpr(SCEVUse LHS, SCEVUse RHS)
@ 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.
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 SCEVUse getSCEVAtExit(const SCEV *S, const Loop *L, const BasicBlock *ExitingBlock)
Return the SCEV expression at the specified loop exit.
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 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 void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)
Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...
LLVM_ABI bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
LLVM_ABI std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
LLVM_ABI const SCEV * getCouldNotCompute()
LLVM_ABI bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
LLVM_ABI uint32_t getMinTrailingZeros(const SCEV *S, const Instruction *CtxI=nullptr)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
@ DominatesBlock
The SCEV dominates the block.
@ ProperlyDominatesBlock
The SCEV properly dominates the block.
@ DoesNotDominateBlock
The SCEV does not dominate the block.
LLVM_ABI const SCEV * 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 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 setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEVFlags Flags)
Update no-wrap flags of an AddRec.
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 SCEVUse getMulExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlagsPair Flags={}, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
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 const SCEV * getSignExtendExprImpl(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
APInt getUnsignedRangeMax(const SCEV *S)
Determine the max of the unsigned range for a particular SCEV.
ExitCountKind
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of ...
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
@ ConstantMaximum
A constant which provides an upper bound on the exact trip count.
@ Exact
An expression exactly describing the number of times the backedge has executed when a loop is exited.
LLVM_ABI 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 * getNegativeSCEV(const SCEV *V, SCEVFlags Flags=SCEV::FlagNone)
Return the SCEV object corresponding to -V.
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 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
This class represents the LLVM 'select' instruction.
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.
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.
iterator_range< user_iterator > users()
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.
LLVM_ABI APInt GreatestCommonDivisor(APInt A, APInt B, bool IsSigned=false)
Compute GCD of two APInt values.
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
constexpr bool any(E Val)
@ 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)
SCEVBinaryExpr_match< SCEVSMaxExpr, Op0_t, Op1_t, SCEV::FlagNone, true > m_scev_SMax(const Op0_t &Op0, const Op1_t &Op1)
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagNone, true > m_scev_c_Mul(const Op0_t &Op0, const Op1_t &Op1)
match_bind< const SCEVAddExpr > m_scev_Add(const SCEVAddExpr *&V)
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.
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.
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 >
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
@ BinaryOp
One of the operands is a binary op.
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 void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CtxI=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...
auto uninitialized_copy(R &&Src, IterTy Dst)
bool isa_and_nonnull(const Y &Val)
LLVM_ABI unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CtxI=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.
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
auto map_range(ContainerTy &&C, FuncTy F)
Return a range that applies F to the elements of C.
LLVM_ABI bool canConstantFoldCallTo(const CallBase *Call, const Function *F, const TargetLibraryInfo *TLI=nullptr)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
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,...
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Function *CtxF=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
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.
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.
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)
SCEVFlags
SCEVFlags are bitfield indices into SCEV's SubclassData.
ArrayRef(const T &OneElt) -> ArrayRef< T >
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.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
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.
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
iterator_range< df_iterator< T > > depth_first(const T &G)
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
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.
constexpr detail::IsaCheckPredicate< Types... > IsaPred
Function object wrapper for the llvm::isa type check.
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:
The no-wrap flags to apply when creating a SCEV expression, to the expression and use respectively.
SCEVFlags ExprFlags
Flags applied directly to a SCEV expression, must be valid wherever the expression is valid.
SCEVFlags UseFlags
Flags only applied to a SCEVUse.
SCEVPtrT getPointer() const
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