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-operations-implication-depth",
cl::Hidden,
184 cl::desc(
"Maximum depth of recursive SCEV operations implication analysis"),
188 "scalar-evolution-max-value-compare-depth",
cl::Hidden,
189 cl::desc(
"Maximum depth of recursive value complexity comparisons"),
194 cl::desc(
"Maximum depth of recursive arithmetics"),
198 "scalar-evolution-max-constant-evolving-depth",
cl::Hidden,
203 cl::desc(
"Maximum depth of recursive SExt/ZExt/Trunc"),
208 cl::desc(
"Max coefficients in AddRec during evolving"),
213 cl::desc(
"Size of the expression which is considered huge"),
218 cl::desc(
"Threshold for switching to iteratively computing SCEV ranges"),
222 "scalar-evolution-max-loop-guard-collection-depth",
cl::Hidden,
223 cl::desc(
"Maximum depth for recursive loop guard collection"),
cl::init(1));
228 cl::desc(
"When printing analysis, include information on every instruction"));
231 "scalar-evolution-use-expensive-range-sharpening",
cl::Hidden,
233 cl::desc(
"Use more powerful methods of sharpening expression ranges. May "
234 "be costly in terms of compile time"));
238 cl::desc(
"Handle <= and >= in finite loops"),
242 "scalar-evolution-use-context-for-no-wrap-flag-strenghening",
cl::Hidden,
243 cl::desc(
"Infer nuw/nsw flags using context where suitable"),
280#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
298 OS <<
"(ptrtoaddr " << *
Op->getType() <<
" " <<
Op <<
" to "
305 OS <<
"(trunc " << *
Op->getType() <<
" " <<
Op <<
" to "
312 OS <<
"(zext " << *
Op->getType() <<
" " <<
Op <<
" to " << *ZExt->
getType()
319 OS <<
"(sext " << *
Op->getType() <<
" " <<
Op <<
" to " << *SExt->
getType()
348 const char *OpStr =
nullptr;
361 OpStr =
" umin_seq ";
383 OS <<
"(" << UDiv->
getLHS() <<
" /u " << UDiv->
getRHS() <<
")";
390 OS <<
"***COULDNOTCOMPUTE***";
432 if (!
Mul)
return false;
436 if (!SC)
return false;
450 auto &Entry = ConstantSCEVs[V];
459 static_cast<SCEVConstant *
>(UniqueSCEVs.lookup(ID, Token)))
462 new (SCEVAllocator)
SCEVConstant(ID.Intern(SCEVAllocator), V);
463 UniqueSCEVs.insert(S, Token);
478 ConstantInt::get(ITy, V,
isSigned,
true));
486 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
488 SCEV *S =
new (SCEVAllocator)
SCEVVScale(ID.Intern(SCEVAllocator), Ty);
489 UniqueSCEVs.insert(S, Token);
510 "Must be a non-bit-width-changing pointer-to-integer cast!");
522 "Cannot truncate non-integer value!");
529 "Cannot zero extend non-integer value!");
536 "Cannot sign extend non-integer value!");
541 SE->forgetMemoizedResults({
this});
544 SE->UniqueSCEVs.erase(
this);
550void SCEVUnknown::allUsesReplacedWith(
Value *New) {
552 SE->forgetMemoizedResults({
this});
555 SE->UniqueSCEVs.erase(
this);
577 if (LIsPointer != RIsPointer)
578 return (
int)LIsPointer - (int)RIsPointer;
583 return (
int)LID - (int)RID;
588 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
589 return (
int)LArgNo - (int)RArgNo;
595 if (
auto L = LGV->getLinkage() - RGV->getLinkage())
598 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
599 auto LT = GV->getLinkage();
606 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
607 return LGV->getName().compare(RGV->getName());
618 if (LParent != RParent) {
621 if (LDepth != RDepth)
622 return (
int)LDepth - (int)RDepth;
626 unsigned LNumOps = LInst->getNumOperands(),
627 RNumOps = RInst->getNumOperands();
628 if (LNumOps != RNumOps)
629 return (
int)LNumOps - (int)RNumOps;
631 for (
unsigned Idx :
seq(LNumOps)) {
633 RInst->getOperand(Idx),
Depth + 1);
651 if (
LHS.getPointer() ==
RHS.getPointer())
652 return (
int)
LHS.getUseNoWrapFlags() - (int)
RHS.getUseNoWrapFlags();
657 return (
int)LType - (int)RType;
680 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
681 if (LBitWidth != RBitWidth)
682 return (
int)LBitWidth - (int)RBitWidth;
683 return LA.
ult(
RA) ? -1 : 1;
689 return LTy->getBitWidth() - RTy->getBitWidth();
700 if (LLoop != RLoop) {
702 assert(LHead != RHead &&
"Two loops share the same header?");
706 "No dominance between recurrences used by one SCEV?");
729 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
730 if (LNumOps != RNumOps)
731 return (
int)LNumOps - (int)RNumOps;
733 for (
unsigned i = 0; i != LNumOps; ++i) {
742 assert(LBitWidth != RBitWidth &&
"distinct SCEVs compare equal");
743 return (
int)LBitWidth - (int)RBitWidth;
763 if (
Ops.size() < 2)
return;
769 if (
Ops.size() == 2) {
773 if (IsLessComplex(
RHS,
LHS))
797template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
801 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
803 for (
unsigned Idx = 0; Idx <
Ops.size();) {
811 Ops.erase(
Ops.begin() + Idx);
818 assert(Folded &&
"Must have folded value");
822 if (Folded && IsAbsorber(Folded->
getAPInt()))
826 if (Folded && !IsIdentity(Folded->
getAPInt()))
827 Ops.insert(
Ops.begin(), Folded);
829 return Ops.size() == 1 ?
Ops[0] :
nullptr;
904 APInt OddFactorial(W, 1);
906 for (
unsigned i = 3; i <=
K; ++i) {
909 OddFactorial *= (i >> TwoFactors);
913 unsigned CalculationBits = W +
T;
927 for (
unsigned i = 1; i !=
K; ++i) {
960 "use-specific flags only supported for affine AddRecs");
962 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1003 ConversionFn CreatePtrCast;
1007 ConversionFn CreatePtrCast)
1008 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
1011 Type *TargetTy, ConversionFn CreatePtrCast) {
1013 return Rewriter.visit(Scev);
1039 "Should only reach pointer-typed SCEVUnknown's.");
1044 return SE.getZero(TargetTy);
1045 return CreatePtrCast(Expr);
1050 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1054 if (DL.hasUnstableRepresentation(
Op->getType()))
1057 Type *Ty = DL.getAddressType(
Op->getType());
1068 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1070 SCEV *S =
new (SCEVAllocator)
1072 UniqueSCEVs.insert(S, Token);
1075 return static_cast<const SCEV *
>(S);
1078 "We must have succeeded in sinking the cast, "
1079 "and ending up with an integer-typed expression!");
1086 "This is not a truncating conversion!");
1088 "This is not a conversion to a SCEVable type!");
1089 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1094 ID.AddPointer(
Op.getOpaqueValue());
1097 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1120 UniqueSCEVs.insert(S, Token);
1133 unsigned numTruncs = 0;
1134 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1142 if (numTruncs < 2) {
1152 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1159 for (
const SCEV *
Op : AddRec->operands())
1174 UniqueSCEVs.insert(S, Token);
1215struct ExtendOpTraitsBase {
1216 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
SCEVUse,
Type *,
1221template <
typename ExtendOp>
struct ExtendOpTraits {
1237 static const GetExtendExprTy GetExtendExpr;
1239 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1240 ICmpInst::Predicate *Pred,
1241 ScalarEvolution *SE) {
1246const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1253 static const GetExtendExprTy GetExtendExpr;
1255 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1256 ICmpInst::Predicate *Pred,
1257 ScalarEvolution *SE) {
1262const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1274template <
typename ExtendOpTy>
1277 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1278 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1294 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1307 auto PreStartFlags =
1325 const SCEV *OperandExtendedStart =
1327 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1328 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1340 const SCEV *OverflowLimit =
1341 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1343 if (OverflowLimit &&
1351template <
typename ExtendOpTy>
1355 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1363 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1398template <
typename ExtendOpTy>
1399bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1402 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1412 APInt StartAI = StartC->
getAPInt();
1414 for (
unsigned Delta : {-2, -1, 1, 2}) {
1415 const SCEV *PreStart =
getConstant(StartAI - Delta);
1416 const auto *PreAR =
static_cast<SCEVAddRecExpr *
>(
1417 findExistingSCEVInCache(
scAddRecExpr, {PreStart, Step},
L));
1421 if (PreAR &&
any(PreAR->getNoWrapFlags(WrapType))) {
1424 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1425 DeltaS, &Pred,
this);
1443 const unsigned BitWidth =
C.getBitWidth();
1461 const APInt &ConstantStart,
1476 auto I = FoldCache.
insert({ID, S});
1480 auto &UserIDs = FoldCacheUser[
I.first->second];
1481 assert(
count(UserIDs, ID) == 1 &&
"unexpected duplicates in UserIDs");
1482 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1483 if (UserIDs[
I] == ID) {
1488 I.first->second = S;
1490 FoldCacheUser[S].push_back(ID);
1496 "This is not an extending conversion!");
1498 "This is not a conversion to a SCEVable type!");
1499 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1503 if (
const SCEV *S = FoldCache.lookup(ID))
1515 "This is not an extending conversion!");
1517 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1529 const SCEV *Start, *Step;
1534 if (AR->hasNoUnsignedWrap()) {
1545 ID.AddPointer(
Op.getOpaqueValue());
1548 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1553 UniqueSCEVs.insert(S, Token);
1563 const SCEV *
X = ST->getOperand();
1596 const SCEV *CastedMaxBECount =
1600 if (MaxBECount == RecastedMaxBECount) {
1609 const SCEV *WideMaxBECount =
1611 const SCEV *OperandExtendedAdd =
1617 if (ZAdd == OperandExtendedAdd) {
1628 OperandExtendedAdd =
1634 if (ZAdd == OperandExtendedAdd) {
1655 !AC.assumptions().empty()) {
1657 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1659 if (AR->hasNoUnsignedWrap()) {
1694 const APInt &
C = SC->getAPInt();
1698 const SCEV *SResidual =
1706 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1730 if (SA->hasNoUnsignedWrap()) {
1743 if (SA->hasNoSignedWrap() &&
1746 C->isNegative() && !
C->isMinSignedValue() && C2->
sge(
C->abs())) {
1765 const SCEV *SResidual =
1776 if (SM->hasNoUnsignedWrap()) {
1798 const SCEV *TruncRHS;
1835 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1839 UniqueSCEVs.insert(S, Token);
1848 "This is not an extending conversion!");
1850 "This is not a conversion to a SCEVable type!");
1851 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1855 if (
const SCEV *S = FoldCache.lookup(ID))
1867 "This is not an extending conversion!");
1869 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1886 const SCEV *Start, *Step;
1891 if (AR->hasNoSignedWrap()) {
1902 ID.AddPointer(
Op.getOpaqueValue());
1905 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1911 UniqueSCEVs.insert(S, Token);
1921 const SCEV *
X = ST->getOperand();
1932 if (SA->hasNoSignedWrap()) {
1954 const SCEV *SResidual =
1987 const SCEV *CastedMaxBECount =
1991 if (MaxBECount == RecastedMaxBECount) {
2000 const SCEV *WideMaxBECount =
2002 const SCEV *OperandExtendedAdd =
2008 if (SAdd == OperandExtendedAdd) {
2019 OperandExtendedAdd =
2025 if (SAdd == OperandExtendedAdd) {
2045 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2047 if (AR->hasNoSignedWrap()) {
2061 const APInt &
C = SC->getAPInt();
2065 const SCEV *SResidual =
2073 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2100 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
2104 UniqueSCEVs.insert(S, Token);
2120 assert(Expr->
getType() == Ty &&
"requested type must match");
2132 "This is not an extending conversion!");
2134 "This is not a conversion to a SCEVable type!");
2139 if (SC->getAPInt().isNegative())
2144 const SCEV *NewOp =
T->getOperand();
2163 for (
const SCEV *
Op : AR->operands())
2201 APInt &AccumulatedConstant,
2205 bool Interesting =
false;
2212 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2214 AccumulatedConstant += Scale *
C->getAPInt();
2219 for (; i !=
Ops.size(); ++i) {
2228 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2234 auto Pair = M.insert({
Key, NewScale});
2238 Pair.first->second += NewScale;
2246 auto Pair = M.insert({
Ops[i], Scale});
2250 Pair.first->second += Scale;
2268 case Instruction::Add:
2270 case Instruction::Sub:
2272 case Instruction::Mul:
2286 const SCEV *
A = (this->*Extension)(
Operation(LHS, RHS), WideTy, 0);
2287 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2288 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2296 if (BinOp == Instruction::Mul)
2302 APInt C = RHSC->getAPInt();
2303 unsigned NumBits =
C.getBitWidth();
2304 bool IsSub = (BinOp == Instruction::Sub);
2305 bool IsNegativeConst = (
Signed &&
C.isNegative());
2307 bool OverflowDown = IsSub ^ IsNegativeConst;
2309 if (IsNegativeConst) {
2322 APInt Limit = Min + Magnitude;
2328 APInt Limit = Max - Magnitude;
2337 return std::nullopt;
2346 bool Deduced =
false;
2352 bool CanUseNSW =
true;
2353 const APInt *ShiftAmt;
2358 return std::nullopt;
2362 Opcode = Instruction::Mul;
2364 }
else if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
2365 Opcode != Instruction::Mul) {
2366 return std::nullopt;
2385 return std::nullopt;
2393 using namespace std::placeholders;
2400 assert(CanAnalyze &&
"don't call from other places!");
2407 auto IsKnownNonNegative = [&](
SCEVUse U) {
2416 if (SignOrUnsignWrap != SignOrUnsignMask &&
2423 return Instruction::Add;
2425 return Instruction::Mul;
2454 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2461 if (UDiv->getOperand(1) ==
Ops[1])
2464 if (UDiv->getOperand(1) ==
Ops[0])
2481 "only nuw or nsw allowed");
2483 "only nuw or nsw allowed");
2484 assert(!
Ops.empty() &&
"Cannot get empty add!");
2485 if (
Ops.size() == 1)
return Ops[0];
2488 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2490 "SCEVAddExpr operand types don't match!");
2492 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2493 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2498 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2499 [](
const APInt &
C) {
return C.isZero(); },
2500 [](
const APInt &
C) {
return false; });
2519 return {getOrCreateAddExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
2524 if (
Add->getNoWrapFlags(ExprFlags) != ExprFlags)
2525 Add->setNoWrapFlags(ComputeFlags(
Ops));
2526 return {S, UseFlags};
2533 bool FoundMatch =
false;
2534 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2535 if (
Ops[i] ==
Ops[i+1]) {
2547 --i; e -=
Count - 1;
2557 auto FindTruncSrcType = [&]() ->
Type * {
2563 return T->getOperand()->getType();
2565 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2567 return T->getOperand()->getType();
2571 if (
auto *SrcType = FindTruncSrcType()) {
2578 if (
T->getOperand()->getType() != SrcType) {
2587 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2590 if (
T->getOperand()->getType() != SrcType) {
2619 if (
Ops.size() == 2) {
2629 auto C2 =
C->getAPInt();
2632 APInt ConstAdd = C1 + C2;
2633 auto AddFlags = AddExpr->getNoWrapFlags();
2674 if (
Ops.size() == 2 &&
2685 if (Idx <
Ops.size()) {
2686 bool DeletedAdd =
false;
2697 Ops.erase(
Ops.begin()+Idx);
2700 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2723 struct APIntCompare {
2724 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2725 return LHS.ult(RHS);
2732 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2734 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2737 if (AccumulatedConstant != 0)
2739 for (
auto &MulOp : MulOpLists) {
2740 if (MulOp.first == 1) {
2742 }
else if (MulOp.first != 0) {
2751 if (
Ops.size() == 1)
2760 if (M->getNumOperands() == 2)
2761 return M->getOperand(OpIdx == 0);
2763 append_range(Remaining, M->operands().drop_front(OpIdx + 1));
2772 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2776 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2784 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp) {
2785 if (MulOpSCEV ==
Ops[AddOp]) {
2796 for (
unsigned OMulOp = 0, OE = OtherMul->
getNumOperands(); OMulOp != OE;
2798 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2800 Cofactors.
push_back(StripFactor(OtherMul, OMulOp));
2809 if (!Cofactors.
empty()) {
2817 if (
Ops.size() == DeadIndices.
size() + 1)
2824 Ops.erase(
Ops.begin() + Idx);
2828 Ops.push_back(OuterMul);
2847 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2850 Ops.erase(
Ops.begin()+i);
2855 if (!LIOps.
empty()) {
2880 auto *DefI = getDefiningScopeBound(LIOps);
2882 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2894 if (
Ops.size() == 1)
return NewRec;
2897 for (
unsigned i = 0;; ++i)
2898 if (
Ops[i] == AddRec) {
2908 for (
unsigned OtherIdx = Idx+1;
2916 "AddRecExprs are not sorted in reverse dominance order?");
2923 if (OtherAddRec->getLoop() == AddRecLoop) {
2924 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2926 if (i >= AddRecOps.
size()) {
2927 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2931 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
2934 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
2950 "Tried to add SCEVUse flags after operands changed");
2951 return {getOrCreateAddExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
2959 ID.AddPointer(
Op.getOpaqueValue());
2965 S =
new (SCEVAllocator)
2967 UniqueSCEVs.insert(S, Token);
2978 FoldingSetNodeID
ID;
2981 ID.AddPointer(
Op.getOpaqueValue());
2983 FoldingSetInsertToken Token;
2985 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.lookup(ID, Token));
2989 S =
new (SCEVAllocator)
2990 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
2991 UniqueSCEVs.insert(S, Token);
2993 LoopUsers[
L].push_back(S);
3002 FoldingSetNodeID
ID;
3005 ID.AddPointer(
Op.getOpaqueValue());
3006 FoldingSetInsertToken Token;
3007 SCEVMulExpr *S =
static_cast<SCEVMulExpr *
>(UniqueSCEVs.lookup(ID, Token));
3011 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3013 UniqueSCEVs.insert(S, Token);
3022 FoldingSetNodeID
ID;
3024 ID.AddPointer(
LHS.getOpaqueValue());
3025 ID.AddPointer(
RHS.getOpaqueValue());
3026 FoldingSetInsertToken Token;
3027 SCEV *S = UniqueSCEVs.lookup(ID, Token);
3029 S =
new (SCEVAllocator) SCEVUDivExpr(
ID.Intern(SCEVAllocator),
LHS,
RHS);
3030 UniqueSCEVs.insert(S, Token);
3039 if (j > 1 && k / j != i) Overflow =
true;
3055 if (n == 0 || n == k)
return 1;
3056 if (k > n)
return 0;
3062 for (
uint64_t i = 1; i <= k; ++i) {
3063 r =
umul_ov(r, n-(i-1), Overflow);
3072 struct FindConstantInAddMulChain {
3073 bool FoundConstant =
false;
3075 bool follow(
const SCEV *S) {
3080 bool isDone()
const {
3081 return FoundConstant;
3085 FindConstantInAddMulChain
F;
3087 ST.visitAll(StartExpr);
3088 return F.FoundConstant;
3097 "only nuw or nsw allowed");
3099 "only nuw or nsw allowed");
3100 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3101 if (
Ops.size() == 1)
return Ops[0];
3103 Type *ETy =
Ops[0]->getType();
3105 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3107 "SCEVMulExpr operand types don't match!");
3112 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3113 [](
const APInt &
C) {
return C.isOne(); },
3114 [](
const APInt &
C) {
return C.isZero(); });
3131 return {getOrCreateMulExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
3136 if (
Mul->getNoWrapFlags(ExprFlags) != ExprFlags)
3137 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3138 return {S, UseFlags};
3142 if (
Ops.size() == 2) {
3150 const SCEV *Op0, *Op1;
3158 if (
Ops[0]->isAllOnesValue()) {
3163 bool AnyFolded =
false;
3164 for (
const SCEV *AddOp :
Add->operands()) {
3184 if (AddRec->hasNoSignedWrap()) {
3215 APInt C1V = LHSC->getAPInt();
3225 const SCEV *NewMul =
nullptr;
3229 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3244 if (Idx <
Ops.size()) {
3245 bool DeletedMul =
false;
3251 Ops.erase(
Ops.begin()+Idx);
3275 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3278 Ops.erase(
Ops.begin()+i);
3283 if (!LIOps.
empty()) {
3295 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3311 if (
Ops.size() == 1)
return NewRec;
3314 for (
unsigned i = 0;; ++i)
3315 if (
Ops[i] == AddRec) {
3336 bool OpsModified =
false;
3337 for (
unsigned OtherIdx = Idx+1;
3351 bool Overflow =
false;
3358 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3359 uint64_t Coeff1 =
Choose(x, 2*x - y, Overflow);
3362 z < ze && !Overflow; ++z) {
3363 uint64_t Coeff2 =
Choose(2*x - y, x-z, Overflow);
3365 if (LargerThan64Bits)
3366 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3368 Coeff = Coeff1*Coeff2;
3381 const SCEV *NewAddRec =
3383 if (
Ops.size() == 2)
return NewAddRec;
3384 Ops[Idx] = NewAddRec;
3385 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3402 "Tried to add SCEVUse flags after operands changed");
3403 return {getOrCreateMulExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
3410 "SCEVURemExpr operand types don't match!");
3415 if (RHSC->getValue()->isOne())
3416 return getZero(LHS->getType());
3419 if (RHSC->getAPInt().isPowerOf2()) {
3420 Type *FullTy = LHS->getType();
3436 assert(!LHS->getType()->isPointerTy() &&
3437 "SCEVUDivExpr operand can't be pointer!");
3438 assert(LHS->getType() == RHS->getType() &&
3439 "SCEVUDivExpr operand types don't match!");
3449 if (RHSC->getValue()->isOne())
3454 if (!RHSC->getValue()->isZero()) {
3458 Type *Ty = LHS->getType();
3459 unsigned LZ = RHSC->getAPInt().countl_zero();
3463 if (!RHSC->getAPInt().isPowerOf2())
3471 const APInt &StepInt = Step->getAPInt();
3472 const APInt &DivInt = RHSC->getAPInt();
3473 if (!StepInt.
urem(DivInt) &&
3479 for (
const SCEV *
Op : AR->operands())
3485 const APInt *StartRem;
3498 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3502 const SCEV *NewStart =
3504 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3506 const SCEV *NewLHS =
3516 if (M->hasNoUnsignedWrap()) {
3518 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3519 const SCEV *
Op = M->getOperand(i);
3546 if (
auto *DivisorConstant =
3548 bool Overflow =
false;
3550 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3561 if (
A->hasNoUnsignedWrap()) {
3563 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3570 if (
Operands.size() ==
A->getNumOperands())
3582 const APInt &
N = RHSC->getAPInt();
3583 const APInt *NMinusM, *M;
3587 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3588 *NMinusM ==
N - *M) {
3597 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3607 return getZero(LHS->getType());
3611 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3612 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3613 if (
Mul->getOperand(i) == RHS) {
3624 const SCEV *NewLHS, *NewRHS;
3629 return getOrCreateUDivExpr(LHS, RHS);
3648 if (StepChrec->getLoop() == L) {
3667 "only nuw or nsw allowed");
3673 "SCEVAddRecExpr operand types don't match!");
3674 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3678 "SCEVAddRecExpr operand is not available at loop entry!");
3700 const Loop *NestedLoop = NestedAR->getLoop();
3701 if (L->contains(NestedLoop)
3704 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3706 Operands[0] = NestedAR->getStart();
3710 bool AllInvariant =
all_of(
3722 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3733 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3744 "Tried to add SCEVUse flags after operands changed");
3745 return {getOrCreateAddRecExpr(
Operands, L, ExprFlags), UseFlags};
3761 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3765 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3779 bool FirstIter =
true;
3781 for (
SCEVUse IndexExpr : IndexExprs) {
3788 Offsets.push_back(FieldOffset);
3791 CurTy = STy->getTypeAtIndex(Index);
3796 "The first index of a GEP indexes a pointer");
3797 CurTy = SrcElementTy;
3808 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3809 Offsets.push_back(LocalOffset);
3814 if (Offsets.empty())
3827 "GEP should not change type mid-flight.");
3831SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3835 "L must be passed to find existing AddRecs");
3839 ID.AddPointer(
Op.getOpaqueValue());
3843 return UniqueSCEVs.lookup(ID, Token);
3853 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3854 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3855 if (
Ops.size() == 1)
return Ops[0];
3858 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3860 "Operand types don't match!");
3863 "min/max should be consistently pointerish");
3889 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3891 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3896 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3898 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3904 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3910 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3915 if (Idx <
Ops.size()) {
3916 bool DeletedAny =
false;
3917 while (
Ops[Idx]->getSCEVType() == Kind) {
3919 Ops.erase(
Ops.begin()+Idx);
3937 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3938 if (
Ops[i] ==
Ops[i + 1] ||
3939 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3942 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3945 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3948 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3954 if (
Ops.size() == 1)
return Ops[0];
3956 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
3963 ID.AddPointer(
Op.getOpaqueValue());
3965 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
3967 return ExistingSCEV;
3970 SCEV *S =
new (SCEVAllocator)
3973 UniqueSCEVs.insert(S, Token);
3981class SCEVSequentialMinMaxDeduplicatingVisitor final
3982 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
3983 std::optional<const SCEV *>> {
3984 using RetVal = std::optional<const SCEV *>;
3991 bool canRecurseInto(
SCEVTypes Kind)
const {
3994 return RootKind == Kind || NonSequentialRootKind == Kind;
3999 if (!SeenOps.
insert(S).second)
4000 return std::nullopt;
4004 if (!canRecurseInto(Kind))
4014 return std::nullopt;
4024 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4026 : SE(SE), RootKind(RootKind),
4027 NonSequentialRootKind(
4028 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4032 SmallVectorImpl<SCEVUse> &NewOps) {
4037 for (
const SCEV *
Op : OrigOps) {
4042 Ops.emplace_back(*NewOp);
4046 NewOps = std::move(
Ops);
4090struct SCEVPoisonCollector {
4091 bool LookThroughMaybePoisonBlocking;
4092 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4093 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4094 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4096 bool follow(
const SCEV *S) {
4097 if (!LookThroughMaybePoisonBlocking &&
4107 bool isDone()
const {
return false; }
4117 SCEVPoisonCollector PC1(
true);
4122 if (PC1.MaybePoison.
empty())
4128 SCEVPoisonCollector PC2(
false);
4138 SCEVPoisonCollector PC(
false);
4161 unsigned NumVisitedInsts = 0;
4163 while (!Worklist.
empty()) {
4165 if (!Visited.
insert(V).second)
4174 if (++NumVisitedInsts > InstLimit)
4185 if (PDI->isDisjoint())
4192 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4199 if (
I->hasPoisonGeneratingAnnotations())
4210 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4211 "Not a SCEVSequentialMinMaxExpr!");
4212 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4213 if (
Ops.size() == 1)
4217 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4219 "Operand types don't match!");
4222 "min/max should be consistently pointerish");
4230 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4237 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4247 bool DeletedAny =
false;
4248 while (Idx <
Ops.size()) {
4249 if (
Ops[Idx]->getSCEVType() != Kind) {
4254 Ops.erase(
Ops.begin() + Idx);
4255 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4256 SMME->operands().end());
4264 const SCEV *SaturationPoint;
4275 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4276 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4288 Ops.erase(
Ops.begin() + i);
4293 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4294 Ops.erase(
Ops.begin() + i);
4304 ID.AddPointer(
Op.getOpaqueValue());
4306 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
4308 return ExistingSCEV;
4312 SCEV *S =
new (SCEVAllocator)
4315 UniqueSCEVs.insert(S, Token);
4363 if (
Size.isScalable())
4384 "Cannot get offset for structure containing scalable vector types");
4398 if (
SCEV *S = UniqueSCEVs.lookup(ID, Token)) {
4400 "Stale SCEVUnknown in uniquing map!");
4403 SCEV *S =
new (SCEVAllocator)
SCEVUnknown(ID.Intern(SCEVAllocator), V,
this,
4404 FirstUnknown, NextUnknownOrderID++);
4406 UniqueSCEVs.insert(S, Token);
4421 return Ty->isIntOrPtrTy();
4428 if (Ty->isPointerTy())
4439 if (Ty->isIntegerTy())
4443 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4455 bool PreciseA, PreciseB;
4456 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4457 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4458 if (!PreciseA || !PreciseB)
4461 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4462 DT.dominates(ScopeB, ScopeA);
4466 return CouldNotCompute.get();
4469bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4472 return SU && SU->getValue() ==
nullptr;
4475 return !ContainsNulls;
4480 if (
I != HasRecMap.end())
4485 HasRecMap.insert({S, FoundAddRec});
4493 if (
SI == ExprValueMap.
end())
4495 return SI->second.getArrayRef();
4501void ScalarEvolution::eraseValueFromMap(
Value *V) {
4503 if (
I != ValueExprMap.end()) {
4504 auto EVIt = ExprValueMap.find(
I->second);
4505 bool Removed = EVIt->second.remove(V);
4507 assert(Removed &&
"Value not in ExprValueMap?");
4508 ValueExprMap.erase(
I);
4512void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4516 auto It = ValueExprMap.find_as(V);
4517 if (It == ValueExprMap.end()) {
4519 ExprValueMap[S].insert(V);
4530 return createSCEVIter(V);
4537 if (
I != ValueExprMap.end()) {
4538 const SCEV *S =
I->second;
4539 assert(checkValidity(S) &&
4540 "existing SCEV has not been properly invalidated");
4552 Type *Ty = V->getType();
4568 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4581 return (
const SCEV *)
nullptr;
4587 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4591 Type *Ty = V->getType();
4597 assert(
P->getType()->isPointerTy());
4612 if (AddOp->getType()->isPointerTy()) {
4613 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4630 return getZero(LHS->getType());
4635 if (RHS->getType()->isPointerTy()) {
4636 if (!LHS->getType()->isPointerTy() ||
4646 const bool RHSIsNotMinSigned =
4677 Type *SrcTy = V->getType();
4678 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4679 "Cannot truncate or zero extend with non-integer arguments!");
4689 Type *SrcTy = V->getType();
4690 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4691 "Cannot truncate or zero extend with non-integer arguments!");
4700 Type *SrcTy = V->getType();
4701 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4702 "Cannot noop or zero extend with non-integer arguments!");
4704 "getNoopOrZeroExtend cannot truncate!");
4711 Type *SrcTy = V->getType();
4712 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4713 "Cannot noop or sign extend with non-integer arguments!");
4715 "getNoopOrSignExtend cannot truncate!");
4722 Type *SrcTy = V->getType();
4723 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4724 "Cannot noop or any extend with non-integer arguments!");
4726 "getNoopOrAnyExtend cannot truncate!");
4733 Type *SrcTy = V->getType();
4734 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4735 "Cannot truncate or noop with non-integer arguments!");
4737 "getTruncateOrNoop cannot extend!");
4745 const SCEV *PromotedLHS = LHS;
4746 const SCEV *PromotedRHS = RHS;
4766 assert(!
Ops.empty() &&
"At least one operand must be!");
4768 if (
Ops.size() == 1)
4772 Type *MaxType =
nullptr;
4778 assert(MaxType &&
"Failed to find maximum type!");
4791 if (!V->getType()->isPointerTy())
4796 V = AddRec->getStart();
4798 const SCEV *PtrOp =
nullptr;
4799 for (
const SCEV *AddOp :
Add->operands()) {
4800 if (AddOp->getType()->isPointerTy()) {
4801 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4805 assert(PtrOp &&
"Must have pointer op");
4817 for (
User *U :
I->users()) {
4819 if (Visited.
insert(UserInsn).second)
4833 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4834 bool IgnoreOtherLoops =
true) {
4837 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4839 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4844 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4846 SeenLoopVariantSCEVUnknown =
true;
4850 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4854 SeenOtherLoops =
true;
4858 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4860 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4863 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4864 : SCEVRewriteVisitor(SE),
L(
L) {}
4867 bool SeenLoopVariantSCEVUnknown =
false;
4868 bool SeenOtherLoops =
false;
4877 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4878 SCEVPostIncRewriter
Rewriter(L, SE);
4880 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4885 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4887 SeenLoopVariantSCEVUnknown =
true;
4891 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4895 SeenOtherLoops =
true;
4899 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4901 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4904 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4905 : SCEVRewriteVisitor(SE),
L(
L) {}
4908 bool SeenLoopVariantSCEVUnknown =
false;
4909 bool SeenOtherLoops =
false;
4915class SCEVBackedgeConditionFolder
4918 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4919 ScalarEvolution &SE) {
4920 bool IsPosBECond =
false;
4921 Value *BECond =
nullptr;
4922 if (BasicBlock *Latch =
L->getLoopLatch()) {
4924 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
4925 "Both outgoing branches should not target same header!");
4926 BECond = BI->getCondition();
4927 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
4932 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
4936 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4937 const SCEV *
Result = Expr;
4942 switch (
I->getOpcode()) {
4943 case Instruction::Select: {
4945 std::optional<const SCEV *> Res =
4946 compareWithBackedgeCondition(
SI->getCondition());
4954 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
4965 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
4966 bool IsPosBECond, ScalarEvolution &SE)
4967 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
4968 IsPositiveBECond(IsPosBECond) {}
4970 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
4974 Value *BackedgeCond =
nullptr;
4976 bool IsPositiveBECond;
4979std::optional<const SCEV *>
4980SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
4985 if (BackedgeCond == IC)
4988 return std::nullopt;
4993 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4994 ScalarEvolution &SE) {
5000 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5007 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5017 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5018 : SCEVRewriteVisitor(SE),
L(
L) {}
5026void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5042 const APInt &BECountAP = BECountMax->getAPInt();
5043 unsigned NoOverflowBitWidth =
5052ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5062 if (!SignedWrapViaInductionTried.insert(AR).second)
5087 AC.assumptions().empty())
5095 const SCEV *OverflowLimit =
5097 if (OverflowLimit &&
5105ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5115 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5140 AC.assumptions().empty())
5149 const SCEV *OverflowLimit =
5178 IsNSW = OBO->hasNoSignedWrap();
5179 IsNUW = OBO->hasNoUnsignedWrap();
5185 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5197 return std::nullopt;
5203 switch (
Op->getOpcode()) {
5204 case Instruction::Add:
5205 case Instruction::Sub:
5206 case Instruction::Mul:
5207 case Instruction::UDiv:
5208 case Instruction::URem:
5209 case Instruction::And:
5210 case Instruction::AShr:
5211 case Instruction::Shl:
5214 case Instruction::Or: {
5217 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5227 case Instruction::Xor:
5231 if (RHSC->getValue().isSignMask())
5232 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5234 if (V->getType()->isIntegerTy(1))
5235 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5238 case Instruction::LShr:
5247 if (SA->getValue().ult(
BitWidth)) {
5249 ConstantInt::get(SA->getContext(),
5251 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5256 case Instruction::ExtractValue: {
5258 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5266 bool Signed = WO->isSigned();
5269 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5274 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5285 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5286 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5288 return std::nullopt;
5314 if (
Op == SymbolicPHI)
5319 if (SourceBits != NewBits)
5337 if (!L || L->getHeader() != PN->
getParent())
5395std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5396ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5404 assert(L &&
"Expecting an integer loop header phi");
5409 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5410 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5411 Value *
V = PN->getIncomingValue(i);
5412 if (
L->contains(PN->getIncomingBlock(i))) {
5415 }
else if (BEValueV != V) {
5419 }
else if (!StartValueV) {
5421 }
else if (StartValueV != V) {
5422 StartValueV =
nullptr;
5426 if (!BEValueV || !StartValueV)
5427 return std::nullopt;
5429 const SCEV *BEValue =
getSCEV(BEValueV);
5436 return std::nullopt;
5440 unsigned FoundIndex =
Add->getNumOperands();
5441 Type *TruncTy =
nullptr;
5443 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5446 if (FoundIndex == e) {
5451 if (FoundIndex ==
Add->getNumOperands())
5452 return std::nullopt;
5456 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5457 if (i != FoundIndex)
5458 Ops.push_back(
Add->getOperand(i));
5464 return std::nullopt;
5517 const SCEV *StartVal =
getSCEV(StartValueV);
5518 const SCEV *PHISCEV =
5545 auto getExtendedExpr = [&](
const SCEV *Expr,
5546 bool CreateSignExtend) ->
const SCEV * {
5549 const SCEV *ExtendedExpr =
5552 return ExtendedExpr;
5560 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5561 const SCEV *ExtendedExpr) ->
bool {
5562 return Expr != ExtendedExpr &&
5566 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5567 if (PredIsKnownFalse(StartVal, StartExtended)) {
5569 return std::nullopt;
5574 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5575 if (PredIsKnownFalse(Accum, AccumExtended)) {
5577 return std::nullopt;
5580 auto AppendPredicate = [&](
const SCEV *Expr,
5581 const SCEV *ExtendedExpr) ->
void {
5582 if (Expr != ExtendedExpr &&
5590 AppendPredicate(StartVal, StartExtended);
5591 AppendPredicate(Accum, AccumExtended);
5599 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5600 std::make_pair(NewAR, Predicates);
5602 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5606std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5611 return std::nullopt;
5614 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5615 if (
I != PredicatedSCEVRewrites.end()) {
5616 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5619 if (Rewrite.first == SymbolicPHI)
5620 return std::nullopt;
5624 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5628 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5629 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5634 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5635 return std::nullopt;
5655 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5656 if (Expr1 != Expr2 &&
5657 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5658 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5693const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5695 Value *StartValueV) {
5698 assert(BEValueV && StartValueV);
5700 const SCEV *Accum =
nullptr;
5703 if (BO->Opcode != Instruction::Add)
5706 if (BO->LHS == PN &&
L->isLoopInvariant(BO->RHS))
5708 else if (BO->RHS == PN &&
L->isLoopInvariant(BO->LHS))
5722 if (!
GEP ||
GEP->getPointerOperand() != PN ||
GEP->getNumIndices() != 1)
5725 if (!
L->isLoopInvariant(Idx))
5734 const SCEV *StartVal =
getSCEV(StartValueV);
5735 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5736 insertValueToMap(PN, PHISCEV);
5739 inferNoWrapViaConstantRanges(AR);
5746 "Accum is defined outside L, but is not invariant?");
5747 if (isAddRecNeverPoison(BEInst, L))
5754const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5762 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5768 }
else if (BEValueV != V) {
5772 }
else if (!StartValueV) {
5774 }
else if (StartValueV != V) {
5775 StartValueV =
nullptr;
5779 if (!BEValueV || !StartValueV)
5782 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5783 "PHI node already processed?");
5787 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5792 insertValueToMap(PN, SymbolicName);
5796 const SCEV *BEValue =
getSCEV(BEValueV);
5806 unsigned FoundIndex =
Add->getNumOperands();
5807 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5808 if (
Add->getOperand(i) == SymbolicName)
5809 if (FoundIndex == e) {
5814 if (FoundIndex !=
Add->getNumOperands()) {
5817 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5818 if (i != FoundIndex)
5819 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5831 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5838 if (
GEP->getOperand(0) == PN)
5846 const SCEV *StartVal =
getSCEV(StartValueV);
5847 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5852 forgetMemoizedResults({SymbolicName});
5853 insertValueToMap(PN, PHISCEV);
5856 inferNoWrapViaConstantRanges(AR);
5880 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5881 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5883 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5884 const SCEV *StartVal =
getSCEV(StartValueV);
5885 if (Start == StartVal) {
5889 forgetMemoizedResults({SymbolicName});
5890 insertValueToMap(PN, Shifted);
5900 eraseValueFromMap(PN);
5915 Use &LeftUse =
Merge->getOperandUse(0);
5916 Use &RightUse =
Merge->getOperandUse(1);
5952 assert(IDom &&
"At least the entry block should dominate PN");
5960const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
5965 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
5982 CommonInst = IncomingInst;
5998ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6004 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6005 bool SCEVExprsIdentical =
6007 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6008 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6011const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6012 if (
const SCEV *S = createAddRecFromPHI(PN))
6022 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6025 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6034 struct FindClosure {
6035 const SCEV *OperandToFind;
6041 bool canRecurseInto(
SCEVTypes Kind)
const {
6044 return RootKind == Kind || NonSequentialRootKind == Kind ||
6049 : OperandToFind(OperandToFind), RootKind(RootKind),
6050 NonSequentialRootKind(
6054 bool follow(
const SCEV *S) {
6055 Found = S == OperandToFind;
6057 return !isDone() && canRecurseInto(S->
getSCEVType());
6060 bool isDone()
const {
return Found; }
6063 FindClosure FC(OperandToFind, RootKind);
6068std::optional<const SCEV *>
6069ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6079 switch (ICI->getPredicate()) {
6093 bool Signed = ICI->isSigned();
6094 const SCEV *LA =
getSCEV(TrueVal);
6102 if (LA == LS &&
RA == RS)
6104 if (LA == RS &&
RA == LS)
6107 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6108 if (
Op->getType()->isPointerTy()) {
6119 LS = CoerceOperand(LS);
6120 RS = CoerceOperand(RS);
6144 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6145 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6159 X = ZExt->getOperand();
6161 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6172 return std::nullopt;
6175static std::optional<const SCEV *>
6177 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6181 "Unexpected operands of a select.");
6193 return std::nullopt;
6208static std::optional<const SCEV *>
6212 return std::nullopt;
6215 const auto *SETrue = SE->
getSCEV(TrueVal);
6216 const auto *SEFalse = SE->
getSCEV(FalseVal);
6220const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6222 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6224 V->getType() ==
TrueVal->getType() &&
6225 "Types of select hands and of the result must match.");
6228 if (!
V->getType()->isIntegerTy(1))
6231 if (std::optional<const SCEV *> S =
6244 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6248 if (std::optional<const SCEV *> S =
6249 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6255 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6261 assert(
GEP->getSourceElementType()->isSized() &&
6262 "GEP source element type must be sized");
6265 for (
Value *Index :
GEP->indices())
6270APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6273 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6276 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6278 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6281 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6299 return GetShiftedByZeros(TZ);
6309 return GetShiftedByZeros(TZ);
6313 if (
M->hasNoUnsignedWrap()) {
6316 for (
const SCEV *Operand :
M->operands().drop_front())
6324 for (
const SCEV *Operand :
M->operands())
6326 return GetShiftedByZeros(TZ);
6331 if (
N->hasNoUnsignedWrap())
6332 return GetGCDMultiple(
N);
6335 for (
const SCEV *Operand :
N->operands().drop_front())
6337 return GetShiftedByZeros(TZ);
6354 CtxI = &*F.getEntryBlock().begin();
6361 .allowEphemerals(
true))
6362 .countMinTrailingZeros();
6363 return GetShiftedByZeros(
Known);
6376 return getConstantMultipleImpl(S, CtxI);
6378 auto I = ConstantMultipleCache.find(S);
6379 if (
I != ConstantMultipleCache.end())
6382 APInt Result = getConstantMultipleImpl(S, CtxI);
6383 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6384 assert(InsertPair.second &&
"Should insert a new key");
6385 return InsertPair.first->second;
6402 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6405 if (std::optional<ConstantRange>
Range = CB->getRange())
6409 if (std::optional<ConstantRange>
Range =
A->getRange())
6412 return std::nullopt;
6419 UnsignedRanges.erase(AddRec);
6420 SignedRanges.erase(AddRec);
6421 ConstantMultipleCache.erase(AddRec);
6426getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6452 Value *Start, *Step;
6459 assert(L && L->getHeader() ==
P->getParent());
6472 case Instruction::AShr:
6473 case Instruction::LShr:
6474 case Instruction::Shl:
6489 KnownStep.getBitWidth() ==
BitWidth);
6492 auto MaxShiftAmt = KnownStep.getMaxValue();
6494 bool Overflow =
false;
6495 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6502 case Instruction::AShr: {
6510 if (KnownStart.isNonNegative())
6513 KnownStart.getMaxValue() + 1);
6514 if (KnownStart.isNegative())
6517 KnownEnd.getMaxValue() + 1);
6520 case Instruction::LShr: {
6529 KnownStart.getMaxValue() + 1);
6531 case Instruction::Shl: {
6535 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6536 return ConstantRange(KnownStart.getMinValue(),
6537 KnownEnd.getMaxValue() + 1);
6562 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6569ScalarEvolution::getRangeRefIter(
const SCEV *S,
6570 ScalarEvolution::RangeSignHint SignHint) {
6571 DenseMap<const SCEV *, ConstantRange> &Cache =
6572 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6575 SmallPtrSet<const SCEV *, 8> Seen;
6579 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6580 if (!Seen.
insert(Expr).second)
6613 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6614 const SCEV *
P = WorkList[
I];
6618 for (
const SCEV *
Op :
P->operands())
6631 if (!WorkList.
empty()) {
6636 getRangeRef(
P, SignHint);
6640 return getRangeRef(S, SignHint, 0);
6643const APInt *ScalarEvolution::getConstantAPIntOrNull(
const SCEV *S) {
6645 return &
C->getAPInt();
6653 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6654 DenseMap<const SCEV *, ConstantRange> &Cache =
6655 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6662 auto I = Cache.
find(S);
6663 if (
I != Cache.
end())
6667 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6672 return getRangeRefIter(S, SignHint);
6675 ConstantRange ConservativeResult(
BitWidth,
true);
6676 using OBO = OverflowingBinaryOperator;
6680 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6684 ConservativeResult =
6691 ConservativeResult = ConstantRange(
6707 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6714 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6721 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6726 return setRange(Cast, SignHint,
X);
6731 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6732 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6734 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6735 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6736 ConservativeResult =
6737 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6739 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6740 unsigned WrapType = OBO::AnyWrap;
6741 if (
Add->hasNoSignedWrap())
6742 WrapType |= OBO::NoSignedWrap;
6743 if (
Add->hasNoUnsignedWrap())
6744 WrapType |= OBO::NoUnsignedWrap;
6746 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6748 return setRange(
Add, SignHint,
6749 ConservativeResult.intersectWith(
X, RangeType));
6753 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6755 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6756 return setRange(
Mul, SignHint,
6757 ConservativeResult.intersectWith(
X, RangeType));
6761 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6762 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6763 return setRange(UDiv, SignHint,
6764 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6772 if (!UnsignedMinValue.
isZero())
6773 ConservativeResult = ConservativeResult.intersectWith(
6774 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6783 bool AllNonNeg =
true;
6784 bool AllNonPos =
true;
6785 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6792 ConservativeResult = ConservativeResult.intersectWith(
6797 ConservativeResult = ConservativeResult.intersectWith(
6806 const SCEV *MaxBEScev =
6820 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6822 ConservativeResult =
6823 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6826 auto RangeFromFactoring = getRangeViaFactoring(
6828 ConservativeResult =
6829 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6835 const SCEV *SymbolicMaxBECount =
6840 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6841 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6842 ConservativeResult =
6843 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6848 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6858 ID = Intrinsic::umax;
6861 ID = Intrinsic::smax;
6865 ID = Intrinsic::umin;
6868 ID = Intrinsic::smin;
6875 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6876 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6878 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6879 return setRange(S, SignHint,
6880 ConservativeResult.intersectWith(
X, RangeType));
6889 ConservativeResult =
6890 ConservativeResult.intersectWith(*MDRange, RangeType);
6895 auto CR = getRangeForUnknownRecurrence(U);
6896 ConservativeResult = ConservativeResult.intersectWith(CR);
6907 if (
U->getType()->isPointerTy()) {
6910 unsigned PtrIdxDiff =
6911 DL.getPointerTypeSizeInBits(
U->getType()) -
BitWidth;
6912 NS = NS > PtrIdxDiff ? NS - PtrIdxDiff : 1;
6917 if (!
Known.Zero.getHiBits(NS).isZero())
6918 Known.Zero.setHighBits(NS);
6919 if (!
Known.One.getHiBits(NS).isZero())
6920 Known.One.setHighBits(NS);
6923 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
6924 ConservativeResult = ConservativeResult.intersectWith(
6925 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
6928 ConservativeResult = ConservativeResult.intersectWith(
6933 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6937 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
6938 DL, CanBeNull,
nullptr);
6954 ConservativeResult = ConservativeResult.intersectWith(
6964 return getRangeRef(AR, SignHint,
Depth + 1);
6968 ConstantRange RangeFromOps(
BitWidth,
false);
6970 for (
const auto &
Op :
Phi->operands()) {
6972 RangeFromOps = RangeFromOps.unionWith(OpRange);
6974 if (RangeFromOps.isFullSet())
6977 ConservativeResult =
6978 ConservativeResult.intersectWith(RangeFromOps, RangeType);
6984 if (
II->getIntrinsicID() == Intrinsic::vscale) {
6986 ConservativeResult = ConservativeResult.difference(Disallowed);
6989 return setRange(U, SignHint, std::move(ConservativeResult));
6995 return setRange(S, SignHint, std::move(ConservativeResult));
7003static std::pair<ConstantRange, bool>
7011 if (Step == 0 || MaxBECount == 0)
7012 return {StartRange,
true};
7018 return {ConstantRange::getFull(
BitWidth),
false};
7034 return {ConstantRange::getFull(
BitWidth),
false};
7047 APInt MovedBoundary;
7052 MovedBoundary = StartLower - std::move(
Offset);
7055 MovedBoundary = StartUpper + std::move(
Offset);
7059 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7066 if (StartRange.
contains(MovedBoundary))
7067 return {ConstantRange::getFull(
BitWidth),
false};
7070 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7072 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7080std::pair<ConstantRange, SCEVFlags>
7081ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7082 const APInt &MaxBECount) {
7086 "mismatched bit widths");
7095 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7097 StartSRange, MaxBECount,
7099 ConstantRange SR = SR1.unionWith(SR2);
7116ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7118 ScalarEvolution::RangeSignHint SignHint) {
7119 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7121 "This only works for non-self-wrapping AddRecs!");
7122 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7126 return ConstantRange::getFull(
BitWidth);
7134 return ConstantRange::getFull(
BitWidth);
7138 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7140 MaxItersWithoutWrap))
7141 return ConstantRange::getFull(
BitWidth);
7162 ConstantRange StartRange = getRangeRef(Start, SignHint);
7163 ConstantRange EndRange = getRangeRef(
End, SignHint);
7164 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7168 return RangeBetween;
7173 return ConstantRange::getFull(
BitWidth);
7176 isKnownPredicateViaConstantRanges(LEPred, Start,
End))
7177 return RangeBetween;
7179 isKnownPredicateViaConstantRanges(GEPred, Start,
End))
7180 return RangeBetween;
7181 return ConstantRange::getFull(
BitWidth);
7186 const APInt &MaxBECount) {
7193 "mismatched bit widths");
7195 struct SelectPattern {
7196 Value *Condition =
nullptr;
7200 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7202 std::optional<unsigned> CastOp;
7216 CastOp = SCast->getSCEVType();
7217 S = SCast->getOperand();
7220 using namespace llvm::PatternMatch;
7227 Condition =
nullptr;
7259 bool isRecognized() {
return Condition !=
nullptr; }
7262 SelectPattern StartPattern(*
this,
BitWidth, Start);
7263 if (!StartPattern.isRecognized())
7264 return ConstantRange::getFull(
BitWidth);
7266 SelectPattern StepPattern(*
this,
BitWidth, Step);
7267 if (!StepPattern.isRecognized())
7268 return ConstantRange::getFull(
BitWidth);
7270 if (StartPattern.Condition != StepPattern.Condition) {
7274 return ConstantRange::getFull(
BitWidth);
7285 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7286 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7287 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7288 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7290 ConstantRange TrueRange =
7291 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7292 ConstantRange FalseRange =
7293 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7306 PDI && PDI->isDisjoint()) {
7321ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7334 SmallPtrSet<const SCEV *, 16> Visited;
7336 auto pushOp = [&](
const SCEV *S) {
7337 if (!Visited.
insert(S).second)
7340 if (Visited.
size() > 30) {
7351 while (!Worklist.
empty()) {
7353 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7354 if (!Bound || DT.dominates(Bound, DefI))
7361 return Bound ? Bound : &*F.getEntryBlock().begin();
7367 return getDefiningScopeBound(
Ops, Discard);
7370bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7372 if (
A->getParent() ==
B->getParent() &&
7377 auto *BLoop = LI.getLoopFor(
B->getParent());
7378 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7379 BLoop->getLoopPreheader() ==
A->getParent() &&
7381 A->getParent()->end()) &&
7389 SCEVPoisonCollector PC(
true);
7391 return PC.MaybePoison.
empty();
7394bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7404bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7421 for (
const Use &
Op :
I->operands()) {
7427 auto *DefI = getDefiningScopeBound(SCEVOps);
7428 return isGuaranteedToTransferExecutionTo(DefI,
I);
7431bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7433 if (isSCEVExprNeverPoison(
I))
7444 auto *ExitingBB =
L->getExitingBlock();
7448 SmallPtrSet<const Value *, 16> KnownPoison;
7457 while (!Worklist.
empty()) {
7460 for (
const Use &U :
Poison->uses()) {
7463 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7467 if (KnownPoison.
insert(PoisonUser).second)
7475ScalarEvolution::LoopProperties
7476ScalarEvolution::getLoopProperties(
const Loop *L) {
7477 using LoopProperties = ScalarEvolution::LoopProperties;
7479 auto Itr = LoopPropertiesCache.find(L);
7480 if (Itr == LoopPropertiesCache.end()) {
7483 return !
SI->isSimple();
7493 return I->mayWriteToMemory();
7496 LoopProperties LP = {
true,
7499 for (
auto *BB :
L->getBlocks())
7500 for (
auto &
I : *BB) {
7502 LP.HasNoAbnormalExits =
false;
7503 if (HasSideEffects(&
I))
7504 LP.HasNoSideEffects =
false;
7505 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7509 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7510 assert(InsertPair.second &&
"We just checked!");
7511 Itr = InsertPair.first;
7524const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7530 Stack.emplace_back(V,
false);
7531 while (!Stack.empty()) {
7532 auto E = Stack.back();
7533 Value *CurV = E.getPointer();
7541 const SCEV *CreatedSCEV =
nullptr;
7544 CreatedSCEV = createSCEV(CurV);
7549 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7553 insertValueToMap(CurV, CreatedSCEV);
7556 Stack.back().setInt(
true);
7559 Stack.emplace_back(
Op,
false);
7576 if (!DT.isReachableFromEntry(
I->getParent()))
7589 switch (BO->Opcode) {
7590 case Instruction::Add:
7591 case Instruction::Mul: {
7598 Ops.push_back(BO->
Op);
7602 Ops.push_back(BO->RHS);
7606 (BO->Opcode == Instruction::Add &&
7607 (NewBO->Opcode != Instruction::Add &&
7608 NewBO->Opcode != Instruction::Sub)) ||
7609 (BO->Opcode == Instruction::Mul &&
7610 NewBO->Opcode != Instruction::Mul)) {
7611 Ops.push_back(BO->LHS);
7616 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7619 Ops.push_back(BO->LHS);
7627 case Instruction::Sub:
7628 case Instruction::UDiv:
7629 case Instruction::URem:
7631 case Instruction::AShr:
7632 case Instruction::Shl:
7633 case Instruction::Xor:
7637 case Instruction::And:
7638 case Instruction::Or:
7642 case Instruction::LShr:
7649 Ops.push_back(BO->LHS);
7650 Ops.push_back(BO->RHS);
7654 switch (
U->getOpcode()) {
7655 case Instruction::Trunc:
7656 case Instruction::ZExt:
7657 case Instruction::SExt:
7658 case Instruction::PtrToAddr:
7659 case Instruction::PtrToInt:
7660 Ops.push_back(
U->getOperand(0));
7663 case Instruction::BitCast:
7665 Ops.push_back(
U->getOperand(0));
7670 case Instruction::SDiv:
7671 case Instruction::SRem:
7672 Ops.push_back(
U->getOperand(0));
7673 Ops.push_back(
U->getOperand(1));
7676 case Instruction::GetElementPtr:
7678 "GEP source element type must be sized");
7682 case Instruction::IntToPtr:
7685 case Instruction::PHI:
7716 Ops.push_back(CondICmp->getOperand(0));
7717 Ops.push_back(CondICmp->getOperand(1));
7737 case Instruction::Select: {
7739 auto CanSimplifyToUnknown = [
this,
U]() {
7757 if (CanSimplifyToUnknown())
7764 case Instruction::Call:
7765 case Instruction::Invoke:
7772 switch (
II->getIntrinsicID()) {
7773 case Intrinsic::abs:
7774 Ops.push_back(
II->getArgOperand(0));
7776 case Intrinsic::umax:
7777 case Intrinsic::umin:
7778 case Intrinsic::smax:
7779 case Intrinsic::smin:
7780 case Intrinsic::usub_sat:
7781 case Intrinsic::uadd_sat:
7782 Ops.push_back(
II->getArgOperand(0));
7783 Ops.push_back(
II->getArgOperand(1));
7785 case Intrinsic::start_loop_iterations:
7786 case Intrinsic::annotation:
7787 case Intrinsic::ptr_annotation:
7788 Ops.push_back(
II->getArgOperand(0));
7800const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7809 if (!DT.isReachableFromEntry(
I->getParent()))
7824 switch (BO->Opcode) {
7825 case Instruction::Add: {
7851 if (BO->Opcode == Instruction::Sub)
7859 if (BO->Opcode == Instruction::Sub)
7866 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7867 NewBO->Opcode != Instruction::Sub)) {
7877 case Instruction::Mul: {
7898 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7907 case Instruction::UDiv:
7911 case Instruction::URem:
7915 case Instruction::Sub: {
7918 Flags = getNoWrapFlagsFromUB(BO->
Op);
7923 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
7926 if (HasPtrLHS || HasPtrRHS) {
7931 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
7932 bool BothPtr) ->
const SCEV * {
7935 const SCEV *PtrSCEV =
getSCEV(PtrOp);
7945 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
7946 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
7954 case Instruction::And:
7960 if (CI->isMinusOne())
7962 const APInt &
A = CI->getValue();
7968 unsigned LZ =
A.countl_zero();
7969 unsigned TZ =
A.countr_zero();
7974 APInt EffectiveMask =
7976 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
7979 const SCEV *ShiftedLHS =
nullptr;
7983 unsigned MulZeros = OpC->getAPInt().countr_zero();
7984 unsigned GCD = std::min(MulZeros, TZ);
7989 const SCEV *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8011 case Instruction::Or:
8020 case Instruction::Xor:
8023 if (CI->isMinusOne())
8032 if (LBO->getOpcode() == Instruction::And &&
8033 LCI->getValue() == CI->getValue())
8034 if (
const SCEVZeroExtendExpr *Z =
8037 const SCEV *Z0 =
Z->getOperand();
8044 if (CI->getValue().isMask(Z0TySize))
8050 APInt Trunc = CI->getValue().trunc(Z0TySize);
8059 case Instruction::Shl:
8077 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8086 ConstantInt *
X = ConstantInt::get(
8092 case Instruction::AShr:
8114 const SCEV *AddTruncateExpr =
nullptr;
8115 ConstantInt *ShlAmtCI =
nullptr;
8116 const SCEV *AddConstant =
nullptr;
8118 if (L &&
L->getOpcode() == Instruction::Add) {
8126 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8133 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8141 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8146 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8151 if (AddTruncateExpr && ShlAmtCI) {
8163 const APInt &ShlAmt = ShlAmtCI->
getValue();
8167 const SCEV *CompositeExpr =
8169 if (
L->getOpcode() != Instruction::Shl)
8170 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8179 switch (
U->getOpcode()) {
8180 case Instruction::Trunc:
8183 case Instruction::ZExt:
8186 case Instruction::SExt:
8196 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8197 Type *Ty =
U->getType();
8205 case Instruction::BitCast:
8211 case Instruction::PtrToAddr: {
8218 case Instruction::PtrToInt:
8222 case Instruction::IntToPtr:
8226 case Instruction::SDiv:
8233 case Instruction::SRem:
8240 case Instruction::GetElementPtr:
8243 case Instruction::PHI:
8246 case Instruction::Select:
8247 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8250 case Instruction::Call:
8251 case Instruction::Invoke:
8256 switch (
II->getIntrinsicID()) {
8257 case Intrinsic::abs:
8261 case Intrinsic::umax:
8265 case Intrinsic::umin:
8269 case Intrinsic::smax:
8273 case Intrinsic::smin:
8277 case Intrinsic::usub_sat: {
8278 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8279 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8283 case Intrinsic::uadd_sat: {
8284 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8285 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8289 case Intrinsic::start_loop_iterations:
8290 case Intrinsic::annotation:
8291 case Intrinsic::ptr_annotation:
8295 case Intrinsic::vscale:
8315 auto *ExitCountType = ExitCount->
getType();
8316 assert(ExitCountType->isIntegerTy());
8318 1 + ExitCountType->getScalarSizeInBits());
8331 auto CanAddOneWithoutOverflow = [&]() {
8333 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8344 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8374 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8375 assert(L->isLoopExiting(ExitingBlock) &&
8376 "Exiting block must actually branch out of the loop!");
8385 const auto *MaxExitCount =
8393 L->getExitingBlocks(ExitingBlocks);
8396 if (ExitingBlocks.
empty() ||
8411 LoopGuards &Guards) {
8415 const SCEV *TCExpr =
8423 : (
unsigned)Multiple.getZExtValue();
8427 const SCEV *ExitCount) {
8450 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8451 assert(L->isLoopExiting(ExitingBlock) &&
8452 "Exiting block must actually branch out of the loop!");
8462 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8464 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8466 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8476 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8479 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8482 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8490 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8497 return getBackedgeTakenInfo(L).getExact(L,
this);
8499 return getBackedgeTakenInfo(L).getConstantMax(
this);
8501 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8508 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8513 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8517 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8527 for (
PHINode &PN : Header->phis())
8528 if (Visited.
insert(&PN).second)
8532ScalarEvolution::BackedgeTakenInfo &
8533ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8534 auto &BTI = getBackedgeTakenInfo(L);
8535 if (BTI.hasFullInfo())
8538 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8541 return Pair.first->second;
8543 BackedgeTakenInfo
Result =
8544 computeBackedgeTakenCount(L,
true);
8546 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8549ScalarEvolution::BackedgeTakenInfo &
8550ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8556 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8557 BackedgeTakenCounts.try_emplace(L);
8559 return Pair.first->second;
8564 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8571 if (
Result.hasAnyInfo()) {
8574 auto LoopUsersIt = LoopUsers.find(L);
8575 if (LoopUsersIt != LoopUsers.end())
8577 forgetMemoizedResults(ToForget);
8580 for (PHINode &PN :
L->getHeader()->phis())
8581 ConstantEvolutionLoopExitValue.erase(&PN);
8589 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8598 BackedgeTakenCounts.clear();
8599 PredicatedBackedgeTakenCounts.clear();
8600 BECountUsers.clear();
8601 LoopPropertiesCache.clear();
8602 ConstantEvolutionLoopExitValue.clear();
8603 ValueExprMap.clear();
8604 ValuesAtScopes.clear();
8605 ValuesAtScopesUsers.clear();
8606 LoopDispositions.clear();
8607 BlockDispositions.clear();
8608 UnsignedRanges.clear();
8609 SignedRanges.clear();
8610 ExprValueMap.clear();
8612 ConstantMultipleCache.clear();
8613 PredicatedSCEVRewrites.clear();
8615 FoldCacheUser.clear();
8617void ScalarEvolution::visitAndClearUsers(
8622 if (ValueExprMap.
empty()) {
8626 while (!Worklist.
empty()) {
8633 if (It != ValueExprMap.
end()) {
8635 eraseValueFromMap(It->first);
8637 ConstantEvolutionLoopExitValue.erase(PN);
8651 while (!LoopWorklist.
empty()) {
8655 forgetBackedgeTakenCounts(CurrL,
false);
8656 forgetBackedgeTakenCounts(CurrL,
true);
8659 PredicatedSCEVRewrites.remove_if(
8660 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8662 auto LoopUsersItr = LoopUsers.find(CurrL);
8663 if (LoopUsersItr != LoopUsers.end())
8668 visitAndClearUsers(Worklist, Visited, ToForget);
8670 LoopPropertiesCache.erase(CurrL);
8673 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8675 forgetMemoizedResults(ToForget);
8692 visitAndClearUsers(Worklist, Visited, ToForget);
8694 forgetMemoizedResults(ToForget);
8705 visitAndClearUsers(Worklist, Visited, ToForget);
8707 forgetMemoizedResults(ToForget);
8715 auto InvalidateValue = [&](
Value *Val) {
8719 struct InvalidationRootCollector {
8723 InvalidationRootCollector(
Loop *L) : L(L) {}
8725 bool follow(
const SCEV *S) {
8731 if (L->contains(AddRec->
getLoop()))
8736 bool isDone()
const {
return false; }
8739 InvalidationRootCollector
C(L);
8741 forgetMemoizedResults(
C.Roots);
8764 BlockDispositions.clear();
8765 LoopDispositions.clear();
8782 while (!Worklist.
empty()) {
8784 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8785 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8786 if (!LoopDispoRemoved && !BlockDispoRemoved)
8788 auto Users = SCEVUsers.find(Curr);
8789 if (
Users != SCEVUsers.end())
8802const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8806 if (!isComplete() || ExitNotTaken.
empty())
8817 for (
const auto &ENT : ExitNotTaken) {
8818 const SCEV *BECount = ENT.ExactNotTaken;
8821 "We should only have known counts for exiting blocks that dominate "
8824 Ops.push_back(BECount);
8829 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8830 "Predicate should be always true!");
8839const ScalarEvolution::ExitNotTakenInfo *
8840ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8841 const BasicBlock *ExitingBlock,
8842 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8843 for (
const auto &ENT : ExitNotTaken)
8844 if (ENT.ExitingBlock == ExitingBlock) {
8845 if (ENT.hasAlwaysTruePredicate())
8847 else if (Predicates) {
8857const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8859 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8860 if (!getConstantMax())
8863 for (
const auto &ENT : ExitNotTaken)
8864 if (!ENT.hasAlwaysTruePredicate()) {
8872 "No point in having a non-constant max backedge taken count!");
8873 return getConstantMax();
8876const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8878 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8886 for (
const auto &ENT : ExitNotTaken) {
8887 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8890 "We should only have known counts for exiting blocks that "
8896 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8897 "Predicate should be always true!");
8900 if (ExitCounts.
empty())
8909bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8911 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8912 return !ENT.hasAlwaysTruePredicate();
8914 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8930 this->ExactNotTaken = E = ConstantMaxNotTaken;
8931 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8936 "Exact is not allowed to be less precise than Constant Max");
8939 "Exact is not allowed to be less precise than Symbolic Max");
8942 "Symbolic Max is not allowed to be less precise than Constant Max");
8945 "No point in having a non-constant max backedge taken count!");
8947 for (
const auto PredList : PredLists)
8948 for (
const auto *
P : PredList) {
8956 "Backedge count should be int");
8959 "Max backedge count should be int");
8972ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8974 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8975 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8976 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8978 ExitNotTaken.reserve(ExitCounts.
size());
8979 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8980 std::back_inserter(ExitNotTaken),
8981 [&](
const EdgeExitInfo &EEI) {
8982 BasicBlock *ExitBB = EEI.first;
8983 const ExitLimit &EL = EEI.second;
8984 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
8985 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
8990 "No point in having a non-constant max backedge taken count!");
8994ScalarEvolution::BackedgeTakenInfo
8995ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
8996 bool AllowPredicates) {
8998 L->getExitingBlocks(ExitingBlocks);
9000 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9003 bool CouldComputeBECount =
true;
9005 const SCEV *MustExitMaxBECount =
nullptr;
9006 const SCEV *MayExitMaxBECount =
nullptr;
9007 bool MustExitMaxOrZero =
false;
9008 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9019 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9020 if (ExitIfTrue == CI->
isZero())
9024 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9026 assert((AllowPredicates || EL.Predicates.empty()) &&
9027 "Predicated exit limit when predicates are not allowed!");
9032 ++NumExitCountsComputed;
9036 CouldComputeBECount =
false;
9043 "Exact is known but symbolic isn't?");
9044 ++NumExitCountsNotComputed;
9059 DT.dominates(ExitBB, Latch)) {
9060 if (!MustExitMaxBECount) {
9061 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9062 MustExitMaxOrZero = EL.MaxOrZero;
9065 EL.ConstantMaxNotTaken);
9069 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9072 EL.ConstantMaxNotTaken);
9076 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9080 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9086 for (
const auto &Pair : ExitCounts) {
9088 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9090 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9091 {
L, AllowPredicates});
9093 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9094 MaxBECount, MaxOrZero);
9097ScalarEvolution::ExitLimit
9098ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9099 bool IsOnlyExit,
bool AllowPredicates) {
9100 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9104 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9109 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9110 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9111 "It should have one successor in loop and one exit block!");
9122 if (!
L->contains(SBB)) {
9127 assert(Exit &&
"Exiting block must have at least one exit");
9128 return computeExitLimitFromSingleExitSwitch(
9129 L, SI, Exit, IsOnlyExit);
9136 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9137 bool AllowPredicates) {
9138 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9139 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9140 ControlsOnlyExit, AllowPredicates);
9143std::optional<ScalarEvolution::ExitLimit>
9144ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9145 bool ExitIfTrue,
bool ControlsOnlyExit,
9146 bool AllowPredicates) {
9148 (void)this->ExitIfTrue;
9149 (void)this->AllowPredicates;
9151 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9152 this->AllowPredicates == AllowPredicates &&
9153 "Variance in assumed invariant key components!");
9154 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9155 if (Itr == TripCountMap.end())
9156 return std::nullopt;
9160void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9162 bool ControlsOnlyExit,
9163 bool AllowPredicates,
9165 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9166 this->AllowPredicates == AllowPredicates &&
9167 "Variance in assumed invariant key components!");
9169 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9170 assert(InsertResult.second &&
"Expected successful insertion!");
9175ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9176 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9177 bool ControlsOnlyExit,
bool AllowPredicates) {
9179 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9183 ExitLimit EL = computeExitLimitFromCondImpl(
9184 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9185 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9189ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9190 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9191 bool ControlsOnlyExit,
bool AllowPredicates) {
9193 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9194 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9195 return *LimitFromBinOp;
9201 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9202 if (EL.hasFullInfo() || !AllowPredicates)
9206 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9226 const WithOverflowInst *WO;
9241 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9242 ControlsOnlyExit, AllowPredicates);
9243 if (EL.hasAnyInfo())
9248 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9251std::optional<ScalarEvolution::ExitLimit>
9252ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9256 bool AllowPredicates) {
9265 return std::nullopt;
9269 ExitLimit EL0 = computeExitLimitFromCondCached(
9270 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9271 ExitLimit EL1 = computeExitLimitFromCondCached(
9272 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9277 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9282 if (EitherMayExit) {
9292 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9294 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9297 EL1.ConstantMaxNotTaken);
9299 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9301 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9304 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9308 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9309 BECount = EL0.ExactNotTaken;
9322 SymbolicMaxBECount =
9324 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9328ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9329 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9330 bool AllowPredicates) {
9342 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9344 if (EL.hasAnyInfo())
9347 auto *ExhaustiveCount =
9348 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9351 return ExhaustiveCount;
9353 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9356ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9358 bool ControlsOnlyExit,
bool AllowPredicates) {
9383 ConstantRange CompRange =
9401 InnerLHS = ZExt->getOperand();
9448 if (EL.hasAnyInfo())
9465 if (EL.hasAnyInfo())
return EL;
9498 ControlsOnlyExit, AllowPredicates);
9499 if (EL.hasAnyInfo())
9517 ControlsOnlyExit, AllowPredicates);
9518 if (EL.hasAnyInfo())
9529ScalarEvolution::ExitLimit
9530ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9532 BasicBlock *ExitingBlock,
9533 bool ControlsOnlyExit) {
9534 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9537 if (
Switch->getDefaultDest() == ExitingBlock)
9541 "Default case must not exit the loop!");
9547 if (EL.hasAnyInfo())
9559 "Evaluation of SCEV at constant didn't fold correctly?");
9563ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9573 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9580 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9582 unsigned &OutShiftAmt) {
9583 using namespace PatternMatch;
9585 ConstantInt *ShiftAmt;
9587 OutOpCode = Instruction::LShr;
9589 OutOpCode = Instruction::AShr;
9591 OutOpCode = Instruction::Shl;
9596 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9611 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9613 unsigned &ShiftAmtOut) {
9614 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9630 if (MatchPositiveShift(
LHS, V, OpC, Amt)) {
9631 PostShiftOpCode = OpC;
9637 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9640 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9646 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9653 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9659 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9671 ConstantInt *StableValue =
nullptr;
9676 case Instruction::AShr: {
9683 if (
Known.isNonNegative())
9684 StableValue = ConstantInt::get(Ty, 0);
9685 else if (
Known.isNegative())
9686 StableValue = ConstantInt::get(Ty, -1,
true);
9692 case Instruction::LShr:
9693 case Instruction::Shl:
9703 "Otherwise cannot be an operand to a branch instruction");
9705 if (
Result->isNullValue()) {
9714 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9716 const SCEV *StartSCEV =
getSCEV(StartValue);
9720 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9721 MaxBTC = std::min(MaxBTC, RangeBTC);
9725 const SCEV *UpperBound =
9743 if (
const Function *
F = CI->getCalledFunction())
9753 if (!L->contains(
I))
return false;
9758 return L->getHeader() ==
I->getParent();
9837 if (!
I)
return nullptr;
9851 std::vector<Constant*>
Operands(
I->getNumOperands());
9853 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9862 if (!
C)
return nullptr;
9884 if (IncomingVal != CurrentVal) {
9887 IncomingVal = CurrentVal;
9899ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9902 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9911 DenseMap<Instruction *, Constant *> CurrentIterVals;
9913 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9919 for (PHINode &
PHI : Header->phis()) {
9921 CurrentIterVals[&
PHI] = StartCST;
9923 if (!CurrentIterVals.
count(PN))
9924 return RetVal =
nullptr;
9930 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9933 unsigned IterationNum = 0;
9935 for (; ; ++IterationNum) {
9936 if (IterationNum == NumIterations)
9937 return RetVal = CurrentIterVals[PN];
9941 DenseMap<Instruction *, Constant *> NextIterVals;
9946 NextIterVals[PN] = NextPHI;
9948 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9954 for (
const auto &
I : CurrentIterVals) {
9956 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9961 for (
const auto &
I : PHIsToCompute) {
9962 PHINode *
PHI =
I.first;
9965 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9968 if (NextPHI !=
I.second)
9969 StoppedEvolving =
false;
9974 if (StoppedEvolving)
9975 return RetVal = CurrentIterVals[PN];
9977 CurrentIterVals.swap(NextIterVals);
9981const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
9991 DenseMap<Instruction *, Constant *> CurrentIterVals;
9993 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9996 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
9998 for (PHINode &
PHI : Header->phis()) {
10000 CurrentIterVals[&
PHI] = StartCST;
10002 if (!CurrentIterVals.
count(PN))
10010 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10017 if (CondVal->getValue() ==
uint64_t(ExitWhen)) {
10018 ++NumBruteForceTripCountsComputed;
10023 DenseMap<Instruction *, Constant *> NextIterVals;
10029 for (
const auto &
I : CurrentIterVals) {
10031 if (!
PHI ||
PHI->getParent() != Header)
continue;
10034 for (PHINode *
PHI : PHIsToCompute) {
10036 if (NextPHI)
continue;
10038 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10041 CurrentIterVals.
swap(NextIterVals);
10052 auto &
Values = ValuesAtScopes[V];
10056 return LS.second ? LS.second :
SCEVUse(V);
10058 Values.emplace_back(L,
nullptr);
10061 SCEVUse C = computeSCEVAtScope(V, L);
10062 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10063 if (LS.first == L) {
10069 ValuesAtScopesUsers[
C.getPointer()].push_back({L, V});
10096 switch (V->getSCEVType()) {
10129 assert(!
C->getType()->isPointerTy() &&
10130 "Can only have one pointer, and it must be last");
10155const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10156 SmallVectorImpl<SCEVUse> &NewOps) {
10190SCEVUse ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10191 switch (
V->getSCEVType()) {
10202 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10213 for (++i; i !=
e; ++i)
10253 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10263 for (++i; i !=
e; ++i) {
10268 return getWithOperands(V, NewOps);
10283 const Loop *CurrLoop = this->LI[
I->getParent()];
10294 if (BackedgeTakenCount->
isZero()) {
10295 Value *InitValue =
nullptr;
10296 bool MultipleInitValues =
false;
10302 MultipleInitValues =
true;
10307 if (!MultipleInitValues && InitValue)
10316 unsigned InLoopPred =
10327 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10341 SmallVector<Constant *, 4>
Operands;
10343 bool MadeImprovement =
false;
10358 MadeImprovement |= OrigV != OpV;
10363 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10368 if (!MadeImprovement)
10389const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10391 return stripInjectiveFunctions(ZExt->getOperand());
10393 return stripInjectiveFunctions(SExt->getOperand());
10411 assert(
A != 0 &&
"A must be non-zero.");
10427 if (MinTZ < Mult2 && L->getLoopPredecessor())
10429 if (MinTZ < Mult2) {
10452 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10472static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10478 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10479 << *AddRec <<
'\n');
10482 if (!LC || !MC || !
NC) {
10483 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10484 return std::nullopt;
10490 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10498 N =
N.sext(NewWidth);
10499 M = M.sext(NewWidth);
10500 L = L.sext(NewWidth);
10517 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10518 <<
", multiplied by " <<
T <<
'\n');
10527 std::optional<APInt>
Y) {
10529 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10532 return XW.
slt(YW) ? *
X : *
Y;
10535 return std::nullopt;
10536 return X ? *
X : *
Y;
10553 return std::nullopt;
10554 unsigned W =
X->getBitWidth();
10574static std::optional<APInt>
10580 return std::nullopt;
10583 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10584 std::optional<APInt>
X =
10587 return std::nullopt;
10592 return std::nullopt;
10607static std::optional<APInt>
10611 "Starting value of addrec should be 0");
10612 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10613 <<
Range <<
", addrec " << *AddRec <<
'\n');
10617 "Addrec's initial value should be in range");
10623 return std::nullopt;
10633 auto SolveForBoundary =
10634 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10637 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10638 << Bound <<
" (before multiplying by " << M <<
")\n");
10641 std::optional<APInt> SO;
10644 "signed overflow\n");
10648 "unsigned overflow\n");
10649 std::optional<APInt> UO =
10652 auto LeavesRange = [&] (
const APInt &
X) {
10655 if (
Range.contains(V0->getValue()))
10660 if (
Range.contains(
V1->getValue()))
10669 return {std::nullopt,
false};
10674 if (LeavesRange(*Min))
10675 return { Min,
true };
10676 std::optional<APInt> Max = Min == SO ? UO : SO;
10677 if (LeavesRange(*Max))
10678 return { Max,
true };
10681 return {std::nullopt,
true};
10688 auto SL = SolveForBoundary(
Lower);
10689 auto SU = SolveForBoundary(
Upper);
10692 if (!SL.second || !SU.second)
10693 return std::nullopt;
10736ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10738 bool ControlsOnlyExit,
10739 bool AllowPredicates) {
10750 if (
C->getValue()->isZero())
return C;
10754 const SCEVAddRecExpr *AddRec =
10757 if (!AddRec && AllowPredicates)
10763 if (!AddRec || AddRec->
getLoop() != L)
10774 return ExitLimit(R, R, R,
false, Predicates);
10832 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10862 const SCEV *
Exact =
10870 const SCEV *SymbolicMax =
10872 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10881 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10889 return ExitLimit(
E, M, S,
false, Predicates);
10892ScalarEvolution::ExitLimit
10893ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10901 if (!
C->getValue()->isZero())
10911std::pair<const BasicBlock *, const BasicBlock *>
10912ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10923 if (
const Loop *L = LI.getLoopFor(BB))
10924 return {
L->getLoopPredecessor(),
L->getHeader()};
10926 return {
nullptr, BB};
10935 if (
A ==
B)
return true;
10950 if (ComputesEqualValues(AI, BI))
10958 const SCEV *Op0, *Op1;
10977 auto TrivialCase = [&](
bool TriviallyTrue) {
10986 const SCEV *NewLHS, *NewRHS;
11010 return TrivialCase(
false);
11011 return TrivialCase(
true);
11030 RAdd->hasNoSignedWrap()) ||
11032 RAdd->hasNoUnsignedWrap())) {
11052 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
11053 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
11056 C->getAPInt().isStrictlyPositive()) ||
11080 const APInt &
RA = RC->getAPInt();
11082 bool SimplifiedByConstantRange =
false;
11087 return TrivialCase(
true);
11089 return TrivialCase(
false);
11098 Changed = SimplifiedByConstantRange =
true;
11102 if (!SimplifiedByConstantRange) {
11119 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11125 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11131 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11137 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11157 return TrivialCase(
true);
11159 return TrivialCase(
false);
11264 auto NonRecursive = [OrNegative](
const SCEV *S) {
11266 return C->getAPInt().isPowerOf2() ||
11267 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11273 if (NonRecursive(S))
11283 const SCEV *S, uint64_t M,
11292 APInt C = Cst->getAPInt();
11293 return C.urem(M) == 0;
11299 const SCEV *SmodM =
11320 [&](
SCEVUse Op) { return isKnownMultipleOf(Op, M, Predicates); }))
11327 return isKnownMultipleOf(Op, M, Predicates);
11333 return isKnownMultipleOf(Op, M, Predicates);
11340 for (
auto *
A : *Predicates)
11341 if (
A->implies(
P, *
this))
11354std::pair<const SCEV *, const SCEV *>
11357 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11359 return { Start, Start };
11361 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11370 getUsedLoops(LHS, LoopsUsed);
11371 getUsedLoops(RHS, LoopsUsed);
11373 if (LoopsUsed.
empty())
11378 for (
const auto *L1 : LoopsUsed)
11379 for (
const auto *L2 : LoopsUsed)
11380 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11381 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11382 "Domination relationship is not a linear order");
11412 SplitRHS.second) &&
11422 isKnownPredicateViaSplitting(Pred, LHS, RHS) ||
11423 isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11433 return std::nullopt;
11448 if (KnownWithoutContext)
11449 return KnownWithoutContext;
11456 return std::nullopt;
11462 const Loop *L = LHS->getLoop();
11467std::optional<ScalarEvolution::MonotonicPredicateType>
11470 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11476 auto ResultSwapped =
11479 assert(*ResultSwapped != *Result &&
11480 "monotonicity should flip as we flip the predicate");
11487std::optional<ScalarEvolution::MonotonicPredicateType>
11488ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11502 return std::nullopt;
11506 "Should be greater or less!");
11510 if (!LHS->hasNoUnsignedWrap())
11511 return std::nullopt;
11515 "Relational predicate is either signed or unsigned!");
11516 if (!
LHS->hasNoSignedWrap())
11517 return std::nullopt;
11519 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11527 return std::nullopt;
11530std::optional<ScalarEvolution::LoopInvariantPredicate>
11537 return std::nullopt;
11544 if (!ArLHS || ArLHS->
getLoop() != L)
11545 return std::nullopt;
11549 return std::nullopt;
11575 return std::nullopt;
11612 return std::nullopt;
11615std::optional<ScalarEvolution::LoopInvariantPredicate>
11620 Pred, LHS, RHS, L, CtxI, MaxIter))
11630 Pred, LHS, RHS, L, CtxI,
Op))
11632 return std::nullopt;
11635std::optional<ScalarEvolution::LoopInvariantPredicate>
11650 return std::nullopt;
11657 if (!AR || AR->
getLoop() != L)
11658 return std::nullopt;
11663 Pred = Pred.dropSameSign();
11667 return std::nullopt;
11673 if (Step != One && Step != MinusOne)
11674 return std::nullopt;
11680 return std::nullopt;
11686 return std::nullopt;
11694 if (Step == MinusOne)
11698 return std::nullopt;
11704bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11710 auto CheckRange = [&](
bool IsSigned) {
11713 return RangeLHS.
icmp(Pred, RangeRHS);
11722 if (CheckRange(
true) || CheckRange(
false))
11731bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11738 APInt &OutC2,
SCEVFlags ExpectedFlags) {
11739 SCEVUse XNonConstOp, XConstOp;
11740 SCEVUse YNonConstOp, YConstOp;
11744 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11747 XFlagsPresent = ExpectedFlags;
11752 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11755 YFlagsPresent = ExpectedFlags;
11758 if (YNonConstOp != XNonConstOp)
11766 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11769 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11829bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11850bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11851 const SCEV *
LHS,
const SCEV *
RHS) {
11856 return any_of(*BB, [&](
const Instruction &
I) {
11857 using namespace llvm::PatternMatch;
11862 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11876 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11881 "This cannot be done on broken IR!");
11884 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11893 if (LoopContinuePredicate &&
11894 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11895 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11900 if (WalkingBEDominatingConds)
11906 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11907 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11914 const SCEV *LoopCounter =
11922 for (
auto &AssumeVH : AC.assumptions()) {
11929 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11933 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11936 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11937 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11938 assert(DTN &&
"should reach the loop header before reaching the root!");
11941 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11959 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
11972 if (!DT.isReachableFromEntry(BB))
11976 "This cannot be done on broken IR!");
11984 const bool ProvingStrictComparison =
11986 bool ProvedNonStrictComparison =
false;
11987 bool ProvedNonEquality =
false;
11990 if (!ProvedNonStrictComparison)
11991 ProvedNonStrictComparison = Fn(NonStrictPredicate);
11992 if (!ProvedNonEquality)
11994 if (ProvedNonStrictComparison && ProvedNonEquality)
11999 if (ProvingStrictComparison) {
12001 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
12003 if (SplitAndProve(ProofFn))
12008 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
12010 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
12012 if (ProvingStrictComparison) {
12014 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
12016 if (SplitAndProve(ProofFn))
12025 const Loop *ContainingLoop = LI.getLoopFor(BB);
12027 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
12031 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
12032 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
12035 if (!BlockEntryPredicate)
12044 for (
auto &AssumeVH : AC.assumptions()) {
12048 if (!DT.dominates(CI, BB))
12051 if (ProveViaCond(CI->getArgOperand(0),
false))
12057 F.getParent(), Intrinsic::experimental_guard);
12059 for (
const auto *GU : GuardDecl->users())
12061 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12062 if (ProveViaCond(Guard->getArgOperand(0),
false))
12077 "LHS is not available at Loop Entry");
12079 "RHS is not available at Loop Entry");
12081 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12092 if (FoundCondValue ==
12096 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12100 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12103 const Value *Op0, *Op1;
12106 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12110 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12111 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12115 if (!ICI)
return false;
12119 CmpPredicate FoundPred;
12128 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12131bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12132 const SCEV *
RHS, CmpPredicate FoundPred,
12133 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12134 const Instruction *CtxI) {
12144 auto *WideType = FoundLHS->
getType();
12156 TruncFoundLHS, TruncFoundRHS, CtxI))
12182 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12186bool ScalarEvolution::isImpliedCondBalancedTypes(
12191 "Types should be balanced!");
12198 if (FoundLHS == FoundRHS)
12202 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12214 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12229 LHS, FoundLHS, FoundRHS, CtxI);
12231 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12238 assert(P1 != P2 &&
"Handled earlier!");
12242 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12246 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12249 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12250 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12251 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12256 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12267 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12268 CanonicalRHS, CanonicalFoundLHS,
12269 CanonicalFoundRHS);
12274 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12275 CanonicalRHS, CanonicalFoundLHS,
12276 CanonicalFoundRHS);
12283 const SCEVConstant *
C =
nullptr;
12284 const SCEV *
V =
nullptr;
12302 if (Min ==
C->getAPInt()) {
12307 APInt SharperMin = Min + 1;
12310 case ICmpInst::ICMP_SGE:
12311 case ICmpInst::ICMP_UGE:
12314 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12319 case ICmpInst::ICMP_SGT:
12320 case ICmpInst::ICMP_UGT:
12330 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12335 case ICmpInst::ICMP_SLE:
12336 case ICmpInst::ICMP_ULE:
12337 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12338 LHS, V, getConstant(SharperMin), CtxI))
12342 case ICmpInst::ICMP_SLT:
12343 case ICmpInst::ICMP_ULT:
12344 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12345 LHS, V, getConstant(Min), CtxI))
12359 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12363 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12366 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12382std::optional<APInt>
12389 APInt DiffMul(BW, 1);
12392 for (
unsigned I = 0;
I < 8; ++
I) {
12401 if (LAR->getLoop() != MAR->getLoop())
12402 return std::nullopt;
12406 if (!LAR->isAffine() || !MAR->isAffine())
12407 return std::nullopt;
12409 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12410 return std::nullopt;
12412 Less = LAR->getStart();
12413 More = MAR->getStart();
12418 auto MatchConstMul =
12419 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12424 return std::nullopt;
12426 if (
auto MatchedMore = MatchConstMul(More)) {
12427 if (
auto MatchedLess = MatchConstMul(
Less)) {
12428 if (MatchedMore->second == MatchedLess->second) {
12429 More = MatchedMore->first;
12430 Less = MatchedLess->first;
12431 DiffMul *= MatchedMore->second;
12442 Diff +=
C->getAPInt() * DiffMul;
12445 Diff -=
C->getAPInt() * DiffMul;
12448 Multiplicity[S] +=
Mul;
12450 auto Decompose = [&](
const SCEV *S,
int Mul) {
12457 Decompose(More, 1);
12458 Decompose(
Less, -1);
12462 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12463 for (
const auto &[S,
Mul] : Multiplicity) {
12468 return std::nullopt;
12470 }
else if (
Mul == -1) {
12472 return std::nullopt;
12475 return std::nullopt;
12479 if (NewMore == More || NewLess ==
Less)
12480 return std::nullopt;
12486 if (!More && !
Less)
12490 if (!More || !
Less)
12491 return std::nullopt;
12495 return std::nullopt;
12498bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12520 const auto *Latch = L->getLoopLatch();
12523 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12532 const auto *Latch = L->getLoopLatch();
12535 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12545bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12548 const SCEV *FoundLHS,
12549 const SCEV *FoundRHS) {
12558 if (!AddRecFoundLHS)
12565 const Loop *
L = AddRecFoundLHS->getLoop();
12566 if (L != AddRecLHS->getLoop())
12605 if (!RDiff || *LDiff != *RDiff)
12608 if (LDiff->isMinValue())
12611 APInt FoundRHSLimit;
12614 FoundRHSLimit = -(*RDiff);
12626bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12627 const SCEV *
RHS,
const SCEV *FoundLHS,
12628 const SCEV *FoundRHS,
unsigned Depth) {
12629 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12633 bool Erased = PendingMerges.erase(LPhi);
12634 assert(Erased &&
"Failed to erase LPhi!");
12638 bool Erased = PendingMerges.erase(RPhi);
12639 assert(Erased &&
"Failed to erase RPhi!");
12647 if (!PendingMerges.insert(Phi).second)
12661 if (!PendingMerges.insert(Phi).second)
12667 if (!LPhi && !RPhi)
12678 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12682 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12683 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12684 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12685 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12688 if (RPhi && RPhi->getParent() == LBB) {
12695 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12696 if (!ProvedEasily(L, R))
12707 auto *RLoop = RAR->
getLoop();
12708 auto *Predecessor = RLoop->getLoopPredecessor();
12709 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12711 if (!ProvedEasily(L1, RAR->
getStart()))
12713 auto *Latch = RLoop->getLoopLatch();
12714 assert(Latch &&
"Loop with AddRec with no latch?");
12735 if (
auto *
Loop = LI.getLoopFor(LBB))
12738 if (!ProvedEasily(L,
RHS))
12745bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12748 const SCEV *FoundLHS,
12749 const SCEV *FoundRHS) {
12752 if (
RHS == FoundRHS) {
12757 if (
LHS != FoundLHS)
12764 Value *Shiftee, *ShiftValue;
12766 using namespace PatternMatch;
12767 if (
match(SUFoundRHS->getValue(),
12769 auto *ShifteeS =
getSCEV(Shiftee);
12787bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12788 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12789 const SCEV *FoundRHS) {
12821 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12829 return Diff == FoundDiff;
12832bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12834 const SCEV *FoundLHS,
12835 const SCEV *FoundRHS,
12836 const Instruction *CtxI) {
12837 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12839 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12841 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12842 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12844 isImpliedCondOperandsViaMatchingDiff(Pred,
LHS,
RHS, FoundLHS,
12846 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12850template <
typename MinMaxExprType>
12852 const SCEV *Candidate) {
12857 return is_contained(MinMaxExpr->operands(), Candidate);
12870 const SCEV *LStart, *RStart, *Step;
12967bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12969 const SCEV *FoundLHS,
12970 const SCEV *FoundRHS,
12974 "LHS and RHS have different sizes?");
12977 "FoundLHS and FoundRHS have different sizes?");
13011 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
13013 return Ext->getOperand();
13020 auto *OrigLHS =
LHS;
13021 auto *OrigFoundLHS = FoundLHS;
13022 LHS = GetOpFromSExt(
LHS);
13023 FoundLHS = GetOpFromSExt(FoundLHS);
13026 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
13029 FoundRHS,
Depth + 1);
13042 if (!LHSAddExpr->hasNoSignedWrap())
13045 SCEVUse LL = LHSAddExpr->getOperand(0);
13046 SCEVUse LR = LHSAddExpr->getOperand(1);
13050 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
13051 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
13056 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
13062 using namespace llvm::PatternMatch;
13081 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13089 auto *DTy = Denominator->getType();
13090 auto *FRHSTy = FoundRHS->
getType();
13091 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13110 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13121 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13123 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13131 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13164bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13168 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13172 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13175bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13178 const SCEV *FoundLHS,
13179 const SCEV *FoundRHS) {
13215 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13221bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13222 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13223 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13237 ConstantRange FoundLHSRange =
13241 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13248 return LHSRange.
icmp(Pred, ConstRHS);
13251bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13252 bool IsSigned,
bool Invert) {
13259 APInt MaxRHS = getRangeMax(
RHS,
true, Invert);
13264 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13267 APInt MaxRHS = getRangeMax(
RHS,
false, Invert);
13272 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13285ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
const SCEV *Stride,
13287 bool IsSigned,
bool Invert) {
13302 APInt MinStart = getRangeMin(Start, IsSigned, Invert);
13315 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13321 APInt MaxEnd = getRangeMax(
End, IsSigned, Invert);
13327 :
APIntOps::umax(MaxEnd, MinStart);
13329 APInt Delta = MaxEnd - MinStart;
13333 const SCEV *DeltaExpr =
13341ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13342 const Loop *L,
bool IsSigned,
bool Invert,
13343 bool ControlsOnlyExit,
bool AllowPredicates) {
13353 bool PredicatedIV =
false;
13355 if (!
IV && !Invert) {
13359 auto canProveNUW = [&]() {
13362 if (!ControlsOnlyExit)
13383 Limit = Limit.
zext(OuterBitWidth);
13395 Type *Ty = ZExt->getType();
13405 if (!
IV && AllowPredicates) {
13410 PredicatedIV =
true;
13414 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13428 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13435 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13438 const SCEV *GuardedStride = Stride;
13442 bool IVMayOverflow =
true;
13446 if (!PositiveStride) {
13449 GuardedStride = LoopGuardedStride;
13450 PositiveStride =
true;
13457 if (!PositiveStride) {
13506 const SCEVPredicate *
P =
13527 auto wouldZeroStrideBeUB = [&]() {
13539 if (!wouldZeroStrideBeUB()) {
13546 IVMayOverflow = canIVOverflowOnLT(
RHS, GuardedStride, IsSigned, Invert);
13547 if (IVMayOverflow && !NoWrap)
13560 const SCEV *
Start =
IV->getStart();
13566 const SCEV *OrigStart =
Start;
13567 const SCEV *OrigRHS =
RHS;
13568 if (
Start->getType()->isPointerTy()) {
13582 assert(!Invert &&
"RHS must be loop-invariant for Invert");
13584 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13585 any(RHSAddRec->getNoWrapFlags())) {
13598 const SCEV *RHSStart = RHSAddRec->getStart();
13599 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13611 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13620 BECountIfBackedgeTaken =
13647 bool AddingStrideMinusOneMayOverflow = IVMayOverflow && [&] {
13694 if (!Invert && (Start == Stride || Start ==
getMinusSCEV(Stride, One))) {
13711 auto StepBack = [&](
const SCEV *
V,
const SCEV *
Offset) ->
const SCEV * {
13716 auto Distance = [&](
const SCEV *From,
const SCEV *To) {
13720 const SCEV *OrigPrevStart = StepBack(OrigStart, Stride);
13727 if ((!AddingStrideMinusOneMayOverflow ||
13759 const SCEV *Numerator =
13765 auto canProveRHSIsAtOrBeyondStart = [&]() {
13770 auto SwapIfInverted = [&](
const SCEV *
A,
const SCEV *
B) {
13771 return Invert ? std::pair(
B,
A) : std::pair(
A,
B);
13780 auto [GELHS, GERHS] = SwapIfInverted(OrigRHS, OrigStart);
13795 auto [GTLHS, GTRHS] = SwapIfInverted(OrigRHS, StepBack(OrigStart, One));
13801 if (canProveRHSIsAtOrBeyondStart()) {
13824 const SCEV *Delta = Distance(Start,
End);
13825 if (!AddingStrideMinusOneMayOverflow) {
13837 const SCEV *ConstantMaxBECount;
13838 bool MaxOrZero =
false;
13840 ConstantMaxBECount = BECount;
13842 ConstantMaxBECount = computeMaxBECountForLT(
13849 const APInt *IfTaken, *RangeMax;
13852 IfTaken->
ugt(*RangeMax)) {
13853 ConstantMaxBECount =
getZero(BECountIfBackedgeTaken->getType());
13855 ConstantMaxBECount = BECountIfBackedgeTaken;
13865 const SCEV *SymbolicMaxBECount =
13867 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13873 if (
Range.isFullSet())
13878 if (!SC->getValue()->isZero()) {
13884 return ShiftedAddRec->getNumIterationsInRange(
13885 Range.subtract(SC->getAPInt()), SE);
13929 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13930 "Linear scev computation is off in a bad way!");
13961 assert(!
Last->isZero() &&
"Recurrency with zero step?");
13994 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13996 SE->ConstantEvolutionLoopExitValue.erase(PN);
13997 SE->eraseValueFromMap(getValPtr());
14001void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
14002 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14012 : CallbackVH(
V), SE(se) {}
14021 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
14023 LoopDispositions(64), BlockDispositions(64) {
14035 F.getParent(), Intrinsic::experimental_guard);
14036 HasGuards = GuardDecl && !GuardDecl->use_empty();
14040 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
14041 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14042 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14043 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14044 PendingMerges(
std::
move(Arg.PendingMerges)),
14045 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14046 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14047 PredicatedBackedgeTakenCounts(
14048 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14049 BECountUsers(
std::
move(Arg.BECountUsers)),
14050 ConstantEvolutionLoopExitValue(
14051 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14052 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14053 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14054 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14055 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14056 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14057 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14058 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14059 SignedRanges(
std::
move(Arg.SignedRanges)),
14060 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14061 UniquePreds(
std::
move(Arg.UniquePreds)),
14062 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14063 ConstantSCEVs(
std::
move(Arg.ConstantSCEVs)),
14064 LoopUsers(
std::
move(Arg.LoopUsers)),
14065 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14066 FirstUnknown(Arg.FirstUnknown),
14067 NextUnknownOrderID(Arg.NextUnknownOrderID) {
14068 Arg.FirstUnknown =
nullptr;
14077 Tmp->~SCEVUnknown();
14079 FirstUnknown =
nullptr;
14081 ExprValueMap.clear();
14082 ValueExprMap.clear();
14084 BackedgeTakenCounts.clear();
14085 PredicatedBackedgeTakenCounts.clear();
14087 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14088 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14089 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14090 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14112 L->getHeader()->printAsOperand(OS,
false);
14116 L->getExitingBlocks(ExitingBlocks);
14117 if (ExitingBlocks.
size() != 1)
14118 OS <<
"<multiple exits> ";
14122 OS <<
"backedge-taken count is ";
14125 OS <<
"Unpredictable backedge-taken count.";
14128 if (ExitingBlocks.
size() > 1)
14129 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14130 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14138 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14141 OS <<
"\n Predicates:\n";
14142 for (
const auto *
P : Predicates)
14150 L->getHeader()->printAsOperand(OS,
false);
14155 OS <<
"constant max backedge-taken count is ";
14158 OS <<
", actual taken count either this or zero.";
14160 OS <<
"Unpredictable constant max backedge-taken count. ";
14165 L->getHeader()->printAsOperand(OS,
false);
14170 OS <<
"symbolic max backedge-taken count is ";
14173 OS <<
", actual taken count either this or zero.";
14175 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14179 if (ExitingBlocks.
size() > 1)
14180 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14181 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14191 OS <<
"\n predicated symbolic max exit count for "
14192 << ExitingBlock->
getName() <<
": ";
14194 OS <<
"\n Predicates:\n";
14195 for (
const auto *
P : Predicates)
14206 L->getHeader()->printAsOperand(OS,
false);
14209 OS <<
"Predicated backedge-taken count is ";
14212 OS <<
"Unpredictable predicated backedge-taken count.";
14214 OS <<
" Predicates:\n";
14215 for (
const auto *
P : Preds)
14220 auto *PredConstantMax =
14222 if (PredConstantMax != ConstantBTC) {
14224 L->getHeader()->printAsOperand(OS,
false);
14227 OS <<
"Predicated constant max backedge-taken count is ";
14230 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14232 OS <<
" Predicates:\n";
14233 for (
const auto *
P : Preds)
14238 auto *PredSymbolicMax =
14240 if (SymbolicBTC != PredSymbolicMax) {
14242 L->getHeader()->printAsOperand(OS,
false);
14245 OS <<
"Predicated symbolic max backedge-taken count is ";
14248 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14250 OS <<
" Predicates:\n";
14251 for (
const auto *
P : Preds)
14257 L->getHeader()->printAsOperand(OS,
false);
14284 OS <<
"Computable";
14294 OS <<
"DoesNotDominate";
14300 OS <<
"ProperlyDominates";
14317 OS <<
"Classifying expressions for: ";
14318 F.printAsOperand(OS,
false);
14333 const Loop *L = LI.getLoopFor(
I.getParent());
14348 OS <<
"\t\t" "Exits: ";
14351 OS <<
"<<Unknown>>";
14357 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14359 Iter->getHeader()->printAsOperand(OS,
false);
14367 InnerL->getHeader()->printAsOperand(OS,
false);
14378 OS <<
"Determining loop execution counts for: ";
14379 F.printAsOperand(OS,
false);
14390 auto &
Values = LoopDispositions[S];
14391 for (
auto &V :
Values) {
14392 if (V.getPointer() == L)
14397 auto &Values2 = LoopDispositions[S];
14399 if (V.getPointer() == L) {
14408ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14426 if (L->contains(AR->
getLoop()) &&
14428 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14433 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14434 " dominate the contained loop's header?");
14461 bool HasVarying =
false;
14462 bool HasUniform =
false;
14507 auto &
Values = BlockDispositions[S];
14508 for (
auto &V :
Values) {
14509 if (V.getPointer() == BB)
14514 auto &Values2 = BlockDispositions[S];
14516 if (V.getPointer() == BB) {
14525ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14554 bool Proper =
true;
14565 if (Instruction *
I =
14567 if (
I->getParent() == BB)
14569 if (DT.properlyDominates(
I->getParent(), BB))
14588void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14591 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14592 auto It = BECounts.find(L);
14593 if (It != BECounts.end()) {
14594 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14595 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14597 auto UserIt = BECountUsers.find(S);
14598 assert(UserIt != BECountUsers.end());
14603 BECounts.erase(It);
14611 while (!Worklist.
empty()) {
14613 auto Users = SCEVUsers.find(Curr);
14614 if (
Users != SCEVUsers.end())
14615 for (
const auto *User :
Users->second)
14616 if (ToForget.
insert(User).second)
14620 for (
const auto *S : ToForget)
14621 forgetMemoizedResultsImpl(S);
14623 PredicatedSCEVRewrites.remove_if(
14624 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14627void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14628 LoopDispositions.erase(S);
14629 BlockDispositions.erase(S);
14630 UnsignedRanges.erase(S);
14631 SignedRanges.erase(S);
14632 HasRecMap.erase(S);
14633 ConstantMultipleCache.erase(S);
14636 UnsignedWrapViaInductionTried.erase(AR);
14637 SignedWrapViaInductionTried.erase(AR);
14640 auto ExprIt = ExprValueMap.find(S);
14641 if (ExprIt != ExprValueMap.end()) {
14642 for (
Value *V : ExprIt->second) {
14643 auto ValueIt = ValueExprMap.find_as(V);
14644 if (ValueIt != ValueExprMap.end())
14645 ValueExprMap.erase(ValueIt);
14647 ExprValueMap.erase(ExprIt);
14650 auto ScopeIt = ValuesAtScopes.find(S);
14651 if (ScopeIt != ValuesAtScopes.end()) {
14652 for (
const auto &Pair : ScopeIt->second)
14654 llvm::erase(ValuesAtScopesUsers[Pair.second.getPointer()],
14655 std::make_pair(Pair.first, S));
14656 ValuesAtScopes.erase(ScopeIt);
14659 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14660 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14661 for (
const auto &Pair : ScopeUserIt->second)
14664 llvm::erase_if(ValuesAtScopes[Pair.second], [&](
const auto &LS) {
14665 return LS.first == Pair.first && LS.second.getPointer() == S;
14667 ValuesAtScopesUsers.erase(ScopeUserIt);
14670 auto BEUsersIt = BECountUsers.find(S);
14671 if (BEUsersIt != BECountUsers.end()) {
14673 auto Copy = BEUsersIt->second;
14674 for (
const auto &Pair : Copy)
14675 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14676 BECountUsers.erase(BEUsersIt);
14679 auto FoldUser = FoldCacheUser.find(S);
14680 if (FoldUser != FoldCacheUser.end())
14681 for (
auto &KV : FoldUser->second)
14682 FoldCache.erase(KV);
14683 FoldCacheUser.erase(S);
14687ScalarEvolution::getUsedLoops(
const SCEV *S,
14689 struct FindUsedLoops {
14690 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14691 : LoopsUsed(LoopsUsed) {}
14692 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14693 bool follow(
const SCEV *S) {
14699 bool isDone()
const {
return false; }
14702 FindUsedLoops
F(LoopsUsed);
14703 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14706void ScalarEvolution::getReachableBlocks(
14709 Worklist.
push_back(&F.getEntryBlock());
14710 while (!Worklist.
empty()) {
14712 if (!Reachable.
insert(BB).second)
14720 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14727 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14731 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14766 SCEVMapper SCM(SE2);
14768 SE2.getReachableBlocks(ReachableBlocks, F);
14770 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14788 while (!LoopStack.
empty()) {
14794 if (!ReachableBlocks.
contains(L->getHeader()))
14799 auto It = BackedgeTakenCounts.find(L);
14800 if (It == BackedgeTakenCounts.end())
14804 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14824 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14825 if (Delta && !Delta->
isZero()) {
14826 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14827 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14828 dbgs() <<
"New: " << *NewBECount <<
"\n";
14829 dbgs() <<
"Delta: " << *Delta <<
"\n";
14837 while (!Worklist.
empty()) {
14839 if (ValidLoops.
insert(L).second)
14840 Worklist.
append(L->begin(), L->end());
14842 for (
const auto &KV : ValueExprMap) {
14847 "AddRec references invalid loop");
14852 auto It = ExprValueMap.find(KV.second);
14853 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14854 dbgs() <<
"Value " << *KV.first
14855 <<
" is in ValueExprMap but not in ExprValueMap\n";
14860 if (!ReachableBlocks.
contains(
I->getParent()))
14862 const SCEV *OldSCEV = SCM.visit(KV.second);
14864 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14865 if (Delta && !Delta->
isZero()) {
14866 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14867 <<
"Old: " << *OldSCEV <<
"\n"
14868 <<
"New: " << *NewSCEV <<
"\n"
14869 <<
"Delta: " << *Delta <<
"\n";
14875 for (
const auto &KV : ExprValueMap) {
14876 for (
Value *V : KV.second) {
14877 const SCEV *S = ValueExprMap.lookup(V);
14879 dbgs() <<
"Value " << *V
14880 <<
" is in ExprValueMap but not in ValueExprMap\n";
14883 if (S != KV.first) {
14884 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14885 << *KV.first <<
"\n";
14892 for (
const auto &S : UniqueSCEVs) {
14897 auto It = SCEVUsers.find(
Op);
14898 if (It != SCEVUsers.end() && It->second.count(&S))
14900 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14901 <<
" is not being tracked!\n";
14907 for (
const auto &ValueAndVec : ValuesAtScopes) {
14909 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14910 const Loop *L = LoopAndValueAtScope.first;
14911 SCEVUse ValueAtScope = LoopAndValueAtScope.second;
14913 auto It = ValuesAtScopesUsers.find(ValueAtScope.
getPointer());
14914 if (It != ValuesAtScopesUsers.end() &&
14917 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14918 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14924 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14925 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14926 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14927 const Loop *L = LoopAndValue.first;
14928 const SCEV *
Value = LoopAndValue.second;
14930 auto It = ValuesAtScopes.find(
Value);
14933 if (It != ValuesAtScopes.end() &&
any_of(It->second, [&](
const auto &LS) {
14934 return LS.first == L && LS.second.getPointer() == ValueAtScope;
14937 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14938 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14944 auto VerifyBECountUsers = [&](
bool Predicated) {
14946 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14947 for (
const auto &LoopAndBEInfo : BECounts) {
14948 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14949 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14951 auto UserIt = BECountUsers.find(S);
14952 if (UserIt != BECountUsers.end() &&
14953 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14955 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14956 <<
" missing from BECountUsers\n";
14963 VerifyBECountUsers(
false);
14964 VerifyBECountUsers(
true);
14967 for (
auto &[S,
Values] : LoopDispositions) {
14968 for (
auto [
Loop, CachedDisposition] :
Values) {
14970 if (CachedDisposition != RecomputedDisposition) {
14971 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
14972 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
14973 << RecomputedDisposition <<
"\n";
14980 for (
auto &[S,
Values] : BlockDispositions) {
14981 for (
auto [BB, CachedDisposition] :
Values) {
14983 if (CachedDisposition != RecomputedDisposition) {
14984 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
14985 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
14986 <<
", actual " << RecomputedDisposition <<
"\n";
14993 for (
auto [
FoldID, Expr] : FoldCache) {
14994 auto I = FoldCacheUser.find(Expr);
14995 if (
I == FoldCacheUser.end()) {
14996 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
15001 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
15005 for (
auto [Expr, IDs] : FoldCacheUser) {
15006 for (
auto &
FoldID : IDs) {
15009 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
15014 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
15015 <<
" != " << *Expr <<
"!\n";
15026 for (
auto [S, Multiple] : ConstantMultipleCache) {
15028 if ((Multiple != 0 && RecomputedMultiple != 0 &&
15029 Multiple.
urem(RecomputedMultiple) != 0 &&
15030 RecomputedMultiple.
urem(Multiple) != 0)) {
15031 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
15032 << *S <<
" : Computed " << RecomputedMultiple
15033 <<
" but cache contains " << Multiple <<
"!\n";
15041 FunctionAnalysisManager::Invalidator &Inv) {
15073 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15074 <<
F.getName() <<
"':\n";
15080 "Scalar Evolution Analysis",
false,
true)
15129 const SCEV *LHS,
const SCEV *RHS) {
15131 assert(LHS->getType() == RHS->getType() &&
15132 "Type mismatch between LHS and RHS");
15135 ID.AddInteger(Pred);
15136 ID.AddPointer(LHS);
15137 ID.AddPointer(RHS);
15139 if (
const auto *S = UniquePreds.lookup(ID, Token))
15143 UniquePreds.insert(Eq, Token);
15154 ID.AddInteger(AddedFlags);
15156 if (
const auto *S = UniquePreds.lookup(ID, Token))
15158 auto *OF =
new (SCEVAllocator)
15160 UniquePreds.insert(OF, Token);
15180 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15181 return Rewriter.visit(S);
15187 for (
const auto *Pred : U->getPredicates())
15189 if (IPred->getLHS() == Expr &&
15191 return IPred->getRHS();
15193 if (IPred->getLHS() == Expr &&
15194 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15195 return IPred->getRHS();
15198 return convertToAddRecWithPreds(Expr);
15201 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15217 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15234 explicit SCEVPredicateRewriter(
15235 const Loop *L, ScalarEvolution &SE,
15236 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15237 const SCEVPredicate *Pred)
15238 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15240 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15243 return Pred && Pred->
implies(
P, SE);
15249 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15252 return addOverflowAssumption(
A);
15261 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15265 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15267 if (!PredicatedRewrite)
15269 for (
const auto *
P : PredicatedRewrite->second){
15272 if (L != WP->getExpr()->getLoop())
15275 if (!addOverflowAssumption(
P))
15278 return PredicatedRewrite->first;
15281 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15282 const SCEVPredicate *Pred;
15291 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15298 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15318 if (!Step->
isOne())
15343 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15344 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15357 return Op->LHS == LHS &&
Op->RHS == RHS;
15364 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15366 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15391 const SCEV *Start = AR->getStart();
15392 const SCEV *OpStart =
Op->AR->getStart();
15397 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15406 const SCEV *Step = AR->getStepRecurrence(SE);
15407 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15428 SCEVFlags ScevFlags = AR->getNoWrapFlags();
15450 for (
const auto *
P : Preds)
15463 return this->implies(I, SE);
15475 const Loop *L = NWrap->getExpr()->getLoop();
15482 return RewrittenAR &&
15488 for (
const auto *Pred : Preds)
15489 Pred->print(OS,
Depth);
15494 for (
const auto *Pred : Set->Preds)
15502 bool CheckImplies = Preds.
size() < 16;
15505 if (CheckImplies &&
implies(
N, SE))
15511 for (
auto *
P : Preds) {
15512 if (CheckImplies &&
N->implies(
P, SE))
15516 Preds = std::move(PrunedPreds);
15517 Preds.push_back(
N);
15524 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15533 SCEVUsers[
Op].insert(
User);
15537 const SCEV *Expr = SE.getSCEV(V);
15542 RewriteEntry &Entry = RewriteMap[Expr];
15545 if (Entry.second && Generation == Entry.first)
15546 return Entry.second;
15551 Expr = Entry.second;
15553 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15554 Entry = {Generation, NewSCEV};
15560 if (!BackedgeCount) {
15562 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15563 for (
const auto *
P : Preds)
15566 return BackedgeCount;
15570 if (!SymbolicMaxBackedgeCount) {
15572 SymbolicMaxBackedgeCount =
15573 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15574 for (
const auto *
P : Preds)
15577 return SymbolicMaxBackedgeCount;
15581 if (!SmallConstantMaxTripCount) {
15583 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15584 for (
const auto *
P : Preds)
15587 return *SmallConstantMaxTripCount;
15591 if (Preds->implies(&Pred, SE))
15596 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15597 updateGeneration();
15610void PredicatedScalarEvolution::updateGeneration() {
15612 if (++Generation == 0) {
15613 for (
auto &
II : RewriteMap) {
15614 const SCEV *Rewritten =
II.second.second;
15624 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15630 ExtraPreds->
append(NewPreds);
15636 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15642 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15645 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15649 for (
auto *BB : L.getBlocks())
15650 for (
auto &
I : *BB) {
15651 if (!SE.isSCEVable(
I.getType()))
15654 auto *Expr = SE.getSCEV(&
I);
15655 auto II = RewriteMap.find(Expr);
15657 if (
II == RewriteMap.end())
15661 if (
II->second.second == Expr)
15666 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15670void ScalarEvolution::LoopGuards::collectPending() {
15671 const Loop *L = PendingLoop;
15674 PendingLoop =
nullptr;
15679 collectFromBlock(SE, *
this, L->getHeader(), Pred,
VisitedBlocks);
15682void ScalarEvolution::LoopGuards::collectFromPHI(
15690 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15691 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15705 auto &RewriteMap =
G->second.RewriteMap;
15706 if (RewriteMap.empty())
15708 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15709 if (S == RewriteMap.end())
15715 return {C0, SM->getSCEVType()};
15718 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15719 MinMaxPattern
P2) -> MinMaxPattern {
15720 auto [C1,
T1] =
P1;
15721 auto [C2, T2] =
P2;
15722 if (!C1 || !C2 ||
T1 != T2)
15726 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15728 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15730 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15732 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15737 auto P = GetMinMaxConst(0);
15738 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15741 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15744 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15747 Guards.RewriteMap.insert({
LHS,
RHS});
15755 const APInt &DivisorVal,
15757 const APInt *ExprVal;
15770 const APInt &DivisorVal,
15772 const APInt *ExprVal;
15780 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15794 const SCEV *URemRHS =
nullptr;
15798 const SCEV *Multiple =
15800 DivInfo[URemLHS] = Multiple;
15802 Multiples[URemLHS] =
C->getAPInt();
15822 auto IsMinMaxSCEVWithNonNegativeConstant =
15826 if (
MinMax->getNumOperands() != 2)
15829 if (
C->getAPInt().isNegative())
15831 SCTy =
MinMax->getSCEVType();
15840 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15842 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15847 auto *DivisibleExpr =
15855void ScalarEvolution::LoopGuards::collectFromBlock(
15857 const BasicBlock *
Block,
const BasicBlock *Pred,
15865 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15876 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15878 if (From == FromRewritten)
15880 RewriteMap[From] = To;
15886 auto GetMaybeRewritten = [&](
const SCEV *S) {
15887 return RewriteMap.lookup_or(S, S);
15894 const SCEV *MatchLHS,
15895 const SCEV *MatchRHS) {
15896 const SCEVConstant *C1;
15899 if (!
match(MatchLHS,
15911 const SCEV *RewrittenLHS = GetMaybeRewritten(LHSUnknown);
15912 ExactRegion = ExactRegion.intersectWith(SE.
getUnsignedRange(RewrittenLHS),
15917 if (ExactRegion.isEmptySet() || ExactRegion.isWrappedSet() ||
15918 ExactRegion.isFullSet())
15921 const SCEV *RegionMin = SE.
getConstant(ExactRegion.getUnsignedMin());
15922 const SCEV *RegionMax = SE.
getConstant(ExactRegion.getUnsignedMax());
15923 const SCEV *ClampedLHS =
15925 AddRewrite(LHSUnknown, RewrittenLHS, ClampedLHS);
15928 if (MatchRangeCheckIdiom(Predicate,
LHS,
RHS))
15941 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15943 const APInt &DividesBy =
15958 switch (Predicate) {
15987 SmallPtrSet<const SCEV *, 16> Visited;
15989 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
15993 while (!Worklist.
empty()) {
15997 if (!Visited.
insert(From).second)
15999 const SCEV *FromRewritten = GetMaybeRewritten(From);
16000 const SCEV *To =
nullptr;
16002 switch (Predicate) {
16007 EnqueueOperands(
UMax);
16013 EnqueueOperands(
SMax);
16019 EnqueueOperands(
UMin);
16025 EnqueueOperands(
SMin);
16033 const SCEV *OneAlignedUp =
16035 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16047 const SCEVConstant *
C;
16056 Guards.NotEqual.insert({
LHS,
RHS});
16065 AddRewrite(From, FromRewritten, To);
16082 SE.F.
getParent(), Intrinsic::experimental_guard);
16084 for (
const auto *GU : GuardDecl->users())
16086 if (Guard->getFunction() ==
Block->getParent() &&
16095 unsigned NumCollectedConditions = 0;
16097 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16099 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16101 const CondBrInst *LoopEntryPredicate =
16103 if (!LoopEntryPredicate)
16108 NumCollectedConditions++;
16112 if (
Depth > 0 && NumCollectedConditions == 2)
16120 if (Pair.second->hasNPredecessorsOrMore(2) &&
16122 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16123 for (
auto &Phi : Pair.second->phis())
16134 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16135 SmallVector<Value *, 8> Worklist;
16136 SmallPtrSet<Value *, 8> Visited;
16138 while (!Worklist.
empty()) {
16145 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16169 DenseMap<const SCEV *, APInt> Multiples;
16171 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16178 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16179 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16183 for (
const auto &[K, Divisor] : Multiples) {
16184 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16185 Guards.RewriteMap[
K] =
16187 Guards.
rewrite(K), Divisor, SE),
16196 Guards.PreserveNUW =
true;
16197 Guards.PreserveNSW =
true;
16198 for (
const SCEV *Expr : ExprsToRewrite) {
16199 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16200 Guards.PreserveNUW &=
16202 Guards.PreserveNSW &=
16209 if (ExprsToRewrite.size() > 1) {
16210 for (
const SCEV *Expr : ExprsToRewrite) {
16211 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16212 Guards.RewriteMap.erase(Expr);
16213 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16222 class SCEVLoopGuardRewriter
16233 NotEqual(Guards.NotEqual) {
16234 if (Guards.PreserveNUW)
16236 if (Guards.PreserveNSW)
16243 return Map.lookup_or(Expr, Expr);
16247 if (
const SCEV *S = Map.lookup(Expr))
16254 if (
const SCEV *S = Map.lookup(Expr))
16261 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16262 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16263 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16265 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16266 if (
const SCEV *S = Map.lookup(NarrowExt))
16267 return SE.getZeroExtendExpr(S, Ty);
16268 Bitwidth = Bitwidth / 2;
16276 if (
const SCEV *S = Map.lookup(Expr))
16283 if (
const SCEV *S = Map.lookup(Expr))
16289 if (
const SCEV *S = Map.lookup(Expr))
16295 if (
const SCEV *S = Map.lookup(Expr))
16300 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16305 if (NotEqual.contains({LHS, RHS})) {
16307 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16308 return SE.getUMaxExpr(OneAlignedUp, S);
16315 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16326 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16327 return SE.getAddExpr(
16330 if (
const SCEV *S = Map.lookup(
Add))
16331 return SE.getAddExpr(Expr->
getOperand(0), S);
16339 const SCEV *S =
nullptr;
16346 S = Map.lookup(SE.getAddExpr(NewC, Expr->
getOperand(1)));
16349 return SE.getAddExpr(S, SE.getMinusOne(Expr->
getType()));
16384 if (RewriteMap.empty() && NotEqual.empty())
16387 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16388 return Rewriter.visit(Expr);
16402 if (Guards.PendingLoop)
16403 Guards.collectPending();
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 SCEVFlags StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, ArrayRef< SCEVUse > Ops, SCEVFlags Flags)
static APInt extractConstantWithoutWrapping(ScalarEvolution &SE, const SCEVConstant *ConstantTerm, const SCEVAddExpr *WholeAddExpr)
static int CompareSCEVComplexity(const LoopInfo *const LI, SCEVUse LHS, SCEVUse RHS, DominatorTree &DT)
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 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.
virt reg 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...
unsigned getOrderID() const
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()
friend class ScalarEvolution
static LoopGuards collectOnDemand(const Loop *L, ScalarEvolution &SE)
Return loop guards for loop L, which are collected on first use.
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.
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.
void sort(IteratorTy Start, IteratorTy End)
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.
@ End
Run the machine verifier once, at the end of the pipeline.
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