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) {
743 assert(LBitWidth != RBitWidth &&
"distinct SCEVs compare equal");
744 return (
int)LBitWidth - (int)RBitWidth;
764 if (
Ops.size() < 2)
return;
770 if (
Ops.size() == 2) {
774 if (IsLessComplex(
RHS,
LHS))
798template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
802 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
804 for (
unsigned Idx = 0; Idx <
Ops.size();) {
812 Ops.erase(
Ops.begin() + Idx);
819 assert(Folded &&
"Must have folded value");
823 if (Folded && IsAbsorber(Folded->
getAPInt()))
827 if (Folded && !IsIdentity(Folded->
getAPInt()))
828 Ops.insert(
Ops.begin(), Folded);
830 return Ops.size() == 1 ?
Ops[0] :
nullptr;
905 APInt OddFactorial(W, 1);
907 for (
unsigned i = 3; i <=
K; ++i) {
910 OddFactorial *= (i >> TwoFactors);
914 unsigned CalculationBits = W +
T;
928 for (
unsigned i = 1; i !=
K; ++i) {
961 "use-specific flags only supported for affine AddRecs");
963 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1004 ConversionFn CreatePtrCast;
1008 ConversionFn CreatePtrCast)
1009 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
1012 Type *TargetTy, ConversionFn CreatePtrCast) {
1014 return Rewriter.visit(Scev);
1040 "Should only reach pointer-typed SCEVUnknown's.");
1045 return SE.getZero(TargetTy);
1046 return CreatePtrCast(Expr);
1051 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1055 if (DL.hasUnstableRepresentation(
Op->getType()))
1058 Type *Ty = DL.getAddressType(
Op->getType());
1069 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1071 SCEV *S =
new (SCEVAllocator)
1073 UniqueSCEVs.insert(S, Token);
1076 return static_cast<const SCEV *
>(S);
1079 "We must have succeeded in sinking the cast, "
1080 "and ending up with an integer-typed expression!");
1087 "This is not a truncating conversion!");
1089 "This is not a conversion to a SCEVable type!");
1090 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1095 ID.AddPointer(
Op.getOpaqueValue());
1098 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1121 UniqueSCEVs.insert(S, Token);
1134 unsigned numTruncs = 0;
1135 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1143 if (numTruncs < 2) {
1153 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1160 for (
const SCEV *
Op : AddRec->operands())
1175 UniqueSCEVs.insert(S, Token);
1216struct ExtendOpTraitsBase {
1217 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
SCEVUse,
Type *,
1222template <
typename ExtendOp>
struct ExtendOpTraits {
1238 static const GetExtendExprTy GetExtendExpr;
1240 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1241 ICmpInst::Predicate *Pred,
1242 ScalarEvolution *SE) {
1247const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1254 static const GetExtendExprTy GetExtendExpr;
1256 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1257 ICmpInst::Predicate *Pred,
1258 ScalarEvolution *SE) {
1263const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1275template <
typename ExtendOpTy>
1278 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1279 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1295 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1308 auto PreStartFlags =
1326 const SCEV *OperandExtendedStart =
1328 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1329 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1341 const SCEV *OverflowLimit =
1342 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1344 if (OverflowLimit &&
1352template <
typename ExtendOpTy>
1356 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1364 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1399template <
typename ExtendOpTy>
1400bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1403 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1413 APInt StartAI = StartC->
getAPInt();
1415 for (
unsigned Delta : {-2, -1, 1, 2}) {
1416 const SCEV *PreStart =
getConstant(StartAI - Delta);
1417 const auto *PreAR =
static_cast<SCEVAddRecExpr *
>(
1418 findExistingSCEVInCache(
scAddRecExpr, {PreStart, Step},
L));
1422 if (PreAR &&
any(PreAR->getNoWrapFlags(WrapType))) {
1425 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1426 DeltaS, &Pred,
this);
1444 const unsigned BitWidth =
C.getBitWidth();
1462 const APInt &ConstantStart,
1477 auto I = FoldCache.
insert({ID, S});
1481 auto &UserIDs = FoldCacheUser[
I.first->second];
1482 assert(
count(UserIDs, ID) == 1 &&
"unexpected duplicates in UserIDs");
1483 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1484 if (UserIDs[
I] == ID) {
1489 I.first->second = S;
1491 FoldCacheUser[S].push_back(ID);
1497 "This is not an extending conversion!");
1499 "This is not a conversion to a SCEVable type!");
1500 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1504 if (
const SCEV *S = FoldCache.lookup(ID))
1516 "This is not an extending conversion!");
1518 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1530 const SCEV *Start, *Step;
1535 if (AR->hasNoUnsignedWrap()) {
1546 ID.AddPointer(
Op.getOpaqueValue());
1549 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1554 UniqueSCEVs.insert(S, Token);
1564 const SCEV *
X = ST->getOperand();
1597 const SCEV *CastedMaxBECount =
1601 if (MaxBECount == RecastedMaxBECount) {
1610 const SCEV *WideMaxBECount =
1612 const SCEV *OperandExtendedAdd =
1618 if (ZAdd == OperandExtendedAdd) {
1629 OperandExtendedAdd =
1635 if (ZAdd == OperandExtendedAdd) {
1656 !AC.assumptions().empty()) {
1658 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1660 if (AR->hasNoUnsignedWrap()) {
1695 const APInt &
C = SC->getAPInt();
1699 const SCEV *SResidual =
1707 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1731 if (SA->hasNoUnsignedWrap()) {
1744 if (SA->hasNoSignedWrap() &&
1747 C->isNegative() && !
C->isMinSignedValue() && C2->
sge(
C->abs())) {
1766 const SCEV *SResidual =
1777 if (SM->hasNoUnsignedWrap()) {
1799 const SCEV *TruncRHS;
1836 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1840 UniqueSCEVs.insert(S, Token);
1849 "This is not an extending conversion!");
1851 "This is not a conversion to a SCEVable type!");
1852 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1856 if (
const SCEV *S = FoldCache.lookup(ID))
1868 "This is not an extending conversion!");
1870 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1887 const SCEV *Start, *Step;
1892 if (AR->hasNoSignedWrap()) {
1903 ID.AddPointer(
Op.getOpaqueValue());
1906 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1912 UniqueSCEVs.insert(S, Token);
1922 const SCEV *
X = ST->getOperand();
1933 if (SA->hasNoSignedWrap()) {
1955 const SCEV *SResidual =
1988 const SCEV *CastedMaxBECount =
1992 if (MaxBECount == RecastedMaxBECount) {
2001 const SCEV *WideMaxBECount =
2003 const SCEV *OperandExtendedAdd =
2009 if (SAdd == OperandExtendedAdd) {
2020 OperandExtendedAdd =
2026 if (SAdd == OperandExtendedAdd) {
2046 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2048 if (AR->hasNoSignedWrap()) {
2062 const APInt &
C = SC->getAPInt();
2066 const SCEV *SResidual =
2074 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2101 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
2105 UniqueSCEVs.insert(S, Token);
2121 assert(Expr->
getType() == Ty &&
"requested type must match");
2133 "This is not an extending conversion!");
2135 "This is not a conversion to a SCEVable type!");
2140 if (SC->getAPInt().isNegative())
2145 const SCEV *NewOp =
T->getOperand();
2164 for (
const SCEV *
Op : AR->operands())
2202 APInt &AccumulatedConstant,
2206 bool Interesting =
false;
2213 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2215 AccumulatedConstant += Scale *
C->getAPInt();
2220 for (; i !=
Ops.size(); ++i) {
2229 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2235 auto Pair = M.insert({
Key, NewScale});
2239 Pair.first->second += NewScale;
2247 auto Pair = M.insert({
Ops[i], Scale});
2251 Pair.first->second += Scale;
2269 case Instruction::Add:
2271 case Instruction::Sub:
2273 case Instruction::Mul:
2287 const SCEV *
A = (this->*Extension)(
Operation(LHS, RHS), WideTy, 0);
2288 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2289 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2297 if (BinOp == Instruction::Mul)
2303 APInt C = RHSC->getAPInt();
2304 unsigned NumBits =
C.getBitWidth();
2305 bool IsSub = (BinOp == Instruction::Sub);
2306 bool IsNegativeConst = (
Signed &&
C.isNegative());
2308 bool OverflowDown = IsSub ^ IsNegativeConst;
2310 if (IsNegativeConst) {
2323 APInt Limit = Min + Magnitude;
2329 APInt Limit = Max - Magnitude;
2338 return std::nullopt;
2347 bool Deduced =
false;
2353 bool CanUseNSW =
true;
2354 const APInt *ShiftAmt;
2359 return std::nullopt;
2363 Opcode = Instruction::Mul;
2365 }
else if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
2366 Opcode != Instruction::Mul) {
2367 return std::nullopt;
2386 return std::nullopt;
2394 using namespace std::placeholders;
2401 assert(CanAnalyze &&
"don't call from other places!");
2408 auto IsKnownNonNegative = [&](
SCEVUse U) {
2417 if (SignOrUnsignWrap != SignOrUnsignMask &&
2424 return Instruction::Add;
2426 return Instruction::Mul;
2455 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2462 if (UDiv->getOperand(1) ==
Ops[1])
2465 if (UDiv->getOperand(1) ==
Ops[0])
2482 "only nuw or nsw allowed");
2484 "only nuw or nsw allowed");
2485 assert(!
Ops.empty() &&
"Cannot get empty add!");
2486 if (
Ops.size() == 1)
return Ops[0];
2489 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2491 "SCEVAddExpr operand types don't match!");
2493 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2494 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2499 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2500 [](
const APInt &
C) {
return C.isZero(); },
2501 [](
const APInt &
C) {
return false; });
2520 return {getOrCreateAddExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
2525 if (
Add->getNoWrapFlags(ExprFlags) != ExprFlags)
2526 Add->setNoWrapFlags(ComputeFlags(
Ops));
2527 return {S, UseFlags};
2534 bool FoundMatch =
false;
2535 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2536 if (
Ops[i] ==
Ops[i+1]) {
2548 --i; e -=
Count - 1;
2558 auto FindTruncSrcType = [&]() ->
Type * {
2564 return T->getOperand()->getType();
2566 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2568 return T->getOperand()->getType();
2572 if (
auto *SrcType = FindTruncSrcType()) {
2579 if (
T->getOperand()->getType() != SrcType) {
2588 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2591 if (
T->getOperand()->getType() != SrcType) {
2620 if (
Ops.size() == 2) {
2630 auto C2 =
C->getAPInt();
2633 APInt ConstAdd = C1 + C2;
2634 auto AddFlags = AddExpr->getNoWrapFlags();
2675 if (
Ops.size() == 2 &&
2686 if (Idx <
Ops.size()) {
2687 bool DeletedAdd =
false;
2698 Ops.erase(
Ops.begin()+Idx);
2701 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2724 struct APIntCompare {
2725 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2726 return LHS.ult(RHS);
2733 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2735 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2738 if (AccumulatedConstant != 0)
2740 for (
auto &MulOp : MulOpLists) {
2741 if (MulOp.first == 1) {
2743 }
else if (MulOp.first != 0) {
2752 if (
Ops.size() == 1)
2761 if (M->getNumOperands() == 2)
2762 return M->getOperand(OpIdx == 0);
2764 append_range(Remaining, M->operands().drop_front(OpIdx + 1));
2773 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2777 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2785 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp) {
2786 if (MulOpSCEV ==
Ops[AddOp]) {
2797 for (
unsigned OMulOp = 0, OE = OtherMul->
getNumOperands(); OMulOp != OE;
2799 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2801 Cofactors.
push_back(StripFactor(OtherMul, OMulOp));
2810 if (!Cofactors.
empty()) {
2818 if (
Ops.size() == DeadIndices.
size() + 1)
2825 Ops.erase(
Ops.begin() + Idx);
2829 Ops.push_back(OuterMul);
2848 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2851 Ops.erase(
Ops.begin()+i);
2856 if (!LIOps.
empty()) {
2881 auto *DefI = getDefiningScopeBound(LIOps);
2883 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2895 if (
Ops.size() == 1)
return NewRec;
2898 for (
unsigned i = 0;; ++i)
2899 if (
Ops[i] == AddRec) {
2909 for (
unsigned OtherIdx = Idx+1;
2917 "AddRecExprs are not sorted in reverse dominance order?");
2924 if (OtherAddRec->getLoop() == AddRecLoop) {
2925 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2927 if (i >= AddRecOps.
size()) {
2928 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2932 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
2935 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
2951 "Tried to add SCEVUse flags after operands changed");
2952 return {getOrCreateAddExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
2960 ID.AddPointer(
Op.getOpaqueValue());
2966 S =
new (SCEVAllocator)
2968 UniqueSCEVs.insert(S, Token);
2979 FoldingSetNodeID
ID;
2982 ID.AddPointer(
Op.getOpaqueValue());
2984 FoldingSetInsertToken Token;
2986 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.lookup(ID, Token));
2990 S =
new (SCEVAllocator)
2991 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
2992 UniqueSCEVs.insert(S, Token);
2994 LoopUsers[
L].push_back(S);
3003 FoldingSetNodeID
ID;
3006 ID.AddPointer(
Op.getOpaqueValue());
3007 FoldingSetInsertToken Token;
3008 SCEVMulExpr *S =
static_cast<SCEVMulExpr *
>(UniqueSCEVs.lookup(ID, Token));
3012 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3014 UniqueSCEVs.insert(S, Token);
3023 FoldingSetNodeID
ID;
3025 ID.AddPointer(
LHS.getOpaqueValue());
3026 ID.AddPointer(
RHS.getOpaqueValue());
3027 FoldingSetInsertToken Token;
3028 SCEV *S = UniqueSCEVs.lookup(ID, Token);
3030 S =
new (SCEVAllocator) SCEVUDivExpr(
ID.Intern(SCEVAllocator),
LHS,
RHS);
3031 UniqueSCEVs.insert(S, Token);
3040 if (j > 1 && k / j != i) Overflow =
true;
3056 if (n == 0 || n == k)
return 1;
3057 if (k > n)
return 0;
3063 for (
uint64_t i = 1; i <= k; ++i) {
3064 r =
umul_ov(r, n-(i-1), Overflow);
3073 struct FindConstantInAddMulChain {
3074 bool FoundConstant =
false;
3076 bool follow(
const SCEV *S) {
3081 bool isDone()
const {
3082 return FoundConstant;
3086 FindConstantInAddMulChain
F;
3088 ST.visitAll(StartExpr);
3089 return F.FoundConstant;
3098 "only nuw or nsw allowed");
3100 "only nuw or nsw allowed");
3101 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3102 if (
Ops.size() == 1)
return Ops[0];
3104 Type *ETy =
Ops[0]->getType();
3106 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3108 "SCEVMulExpr operand types don't match!");
3113 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3114 [](
const APInt &
C) {
return C.isOne(); },
3115 [](
const APInt &
C) {
return C.isZero(); });
3132 return {getOrCreateMulExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
3137 if (
Mul->getNoWrapFlags(ExprFlags) != ExprFlags)
3138 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3139 return {S, UseFlags};
3143 if (
Ops.size() == 2) {
3151 const SCEV *Op0, *Op1;
3159 if (
Ops[0]->isAllOnesValue()) {
3164 bool AnyFolded =
false;
3165 for (
const SCEV *AddOp :
Add->operands()) {
3185 if (AddRec->hasNoSignedWrap()) {
3216 APInt C1V = LHSC->getAPInt();
3226 const SCEV *NewMul =
nullptr;
3230 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3245 if (Idx <
Ops.size()) {
3246 bool DeletedMul =
false;
3252 Ops.erase(
Ops.begin()+Idx);
3276 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3279 Ops.erase(
Ops.begin()+i);
3284 if (!LIOps.
empty()) {
3296 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3312 if (
Ops.size() == 1)
return NewRec;
3315 for (
unsigned i = 0;; ++i)
3316 if (
Ops[i] == AddRec) {
3337 bool OpsModified =
false;
3338 for (
unsigned OtherIdx = Idx+1;
3352 bool Overflow =
false;
3359 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3360 uint64_t Coeff1 =
Choose(x, 2*x - y, Overflow);
3363 z < ze && !Overflow; ++z) {
3364 uint64_t Coeff2 =
Choose(2*x - y, x-z, Overflow);
3366 if (LargerThan64Bits)
3367 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3369 Coeff = Coeff1*Coeff2;
3382 const SCEV *NewAddRec =
3384 if (
Ops.size() == 2)
return NewAddRec;
3385 Ops[Idx] = NewAddRec;
3386 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3403 "Tried to add SCEVUse flags after operands changed");
3404 return {getOrCreateMulExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
3411 "SCEVURemExpr operand types don't match!");
3416 if (RHSC->getValue()->isOne())
3417 return getZero(LHS->getType());
3420 if (RHSC->getAPInt().isPowerOf2()) {
3421 Type *FullTy = LHS->getType();
3437 assert(!LHS->getType()->isPointerTy() &&
3438 "SCEVUDivExpr operand can't be pointer!");
3439 assert(LHS->getType() == RHS->getType() &&
3440 "SCEVUDivExpr operand types don't match!");
3450 if (RHSC->getValue()->isOne())
3455 if (!RHSC->getValue()->isZero()) {
3459 Type *Ty = LHS->getType();
3460 unsigned LZ = RHSC->getAPInt().countl_zero();
3464 if (!RHSC->getAPInt().isPowerOf2())
3472 const APInt &StepInt = Step->getAPInt();
3473 const APInt &DivInt = RHSC->getAPInt();
3474 if (!StepInt.
urem(DivInt) &&
3480 for (
const SCEV *
Op : AR->operands())
3486 const APInt *StartRem;
3499 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3503 const SCEV *NewStart =
3505 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3507 const SCEV *NewLHS =
3517 if (M->hasNoUnsignedWrap()) {
3519 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3520 const SCEV *
Op = M->getOperand(i);
3547 if (
auto *DivisorConstant =
3549 bool Overflow =
false;
3551 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3562 if (
A->hasNoUnsignedWrap()) {
3564 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3571 if (
Operands.size() ==
A->getNumOperands())
3583 const APInt &
N = RHSC->getAPInt();
3584 const APInt *NMinusM, *M;
3588 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3589 *NMinusM ==
N - *M) {
3598 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3608 return getZero(LHS->getType());
3612 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3613 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3614 if (
Mul->getOperand(i) == RHS) {
3625 const SCEV *NewLHS, *NewRHS;
3630 return getOrCreateUDivExpr(LHS, RHS);
3649 if (StepChrec->getLoop() == L) {
3668 "only nuw or nsw allowed");
3674 "SCEVAddRecExpr operand types don't match!");
3675 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3679 "SCEVAddRecExpr operand is not available at loop entry!");
3701 const Loop *NestedLoop = NestedAR->getLoop();
3702 if (L->contains(NestedLoop)
3705 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3707 Operands[0] = NestedAR->getStart();
3711 bool AllInvariant =
all_of(
3723 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3734 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3745 "Tried to add SCEVUse flags after operands changed");
3746 return {getOrCreateAddRecExpr(
Operands, L, ExprFlags), UseFlags};
3762 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3766 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3780 bool FirstIter =
true;
3782 for (
SCEVUse IndexExpr : IndexExprs) {
3789 Offsets.push_back(FieldOffset);
3792 CurTy = STy->getTypeAtIndex(Index);
3797 "The first index of a GEP indexes a pointer");
3798 CurTy = SrcElementTy;
3809 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3810 Offsets.push_back(LocalOffset);
3815 if (Offsets.empty())
3828 "GEP should not change type mid-flight.");
3832SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3836 "L must be passed to find existing AddRecs");
3840 ID.AddPointer(
Op.getOpaqueValue());
3844 return UniqueSCEVs.lookup(ID, Token);
3854 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3855 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3856 if (
Ops.size() == 1)
return Ops[0];
3859 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3861 "Operand types don't match!");
3864 "min/max should be consistently pointerish");
3890 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3892 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3897 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3899 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3905 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3911 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3916 if (Idx <
Ops.size()) {
3917 bool DeletedAny =
false;
3918 while (
Ops[Idx]->getSCEVType() == Kind) {
3920 Ops.erase(
Ops.begin()+Idx);
3938 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3939 if (
Ops[i] ==
Ops[i + 1] ||
3940 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3943 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3946 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3949 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3955 if (
Ops.size() == 1)
return Ops[0];
3957 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
3964 ID.AddPointer(
Op.getOpaqueValue());
3966 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
3968 return ExistingSCEV;
3971 SCEV *S =
new (SCEVAllocator)
3974 UniqueSCEVs.insert(S, Token);
3982class SCEVSequentialMinMaxDeduplicatingVisitor final
3983 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
3984 std::optional<const SCEV *>> {
3985 using RetVal = std::optional<const SCEV *>;
3992 bool canRecurseInto(
SCEVTypes Kind)
const {
3995 return RootKind == Kind || NonSequentialRootKind == Kind;
4000 if (!SeenOps.
insert(S).second)
4001 return std::nullopt;
4005 if (!canRecurseInto(Kind))
4015 return std::nullopt;
4025 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4027 : SE(SE), RootKind(RootKind),
4028 NonSequentialRootKind(
4029 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4033 SmallVectorImpl<SCEVUse> &NewOps) {
4038 for (
const SCEV *
Op : OrigOps) {
4043 Ops.emplace_back(*NewOp);
4047 NewOps = std::move(
Ops);
4091struct SCEVPoisonCollector {
4092 bool LookThroughMaybePoisonBlocking;
4093 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4094 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4095 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4097 bool follow(
const SCEV *S) {
4098 if (!LookThroughMaybePoisonBlocking &&
4108 bool isDone()
const {
return false; }
4118 SCEVPoisonCollector PC1(
true);
4123 if (PC1.MaybePoison.
empty())
4129 SCEVPoisonCollector PC2(
false);
4139 SCEVPoisonCollector PC(
false);
4162 unsigned NumVisitedInsts = 0;
4164 while (!Worklist.
empty()) {
4166 if (!Visited.
insert(V).second)
4175 if (++NumVisitedInsts > InstLimit)
4186 if (PDI->isDisjoint())
4193 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4200 if (
I->hasPoisonGeneratingAnnotations())
4211 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4212 "Not a SCEVSequentialMinMaxExpr!");
4213 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4214 if (
Ops.size() == 1)
4218 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4220 "Operand types don't match!");
4223 "min/max should be consistently pointerish");
4231 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4238 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4248 bool DeletedAny =
false;
4249 while (Idx <
Ops.size()) {
4250 if (
Ops[Idx]->getSCEVType() != Kind) {
4255 Ops.erase(
Ops.begin() + Idx);
4256 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4257 SMME->operands().end());
4265 const SCEV *SaturationPoint;
4276 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4277 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4289 Ops.erase(
Ops.begin() + i);
4294 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4295 Ops.erase(
Ops.begin() + i);
4305 ID.AddPointer(
Op.getOpaqueValue());
4307 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
4309 return ExistingSCEV;
4313 SCEV *S =
new (SCEVAllocator)
4316 UniqueSCEVs.insert(S, Token);
4364 if (
Size.isScalable())
4385 "Cannot get offset for structure containing scalable vector types");
4399 if (
SCEV *S = UniqueSCEVs.lookup(ID, Token)) {
4401 "Stale SCEVUnknown in uniquing map!");
4404 SCEV *S =
new (SCEVAllocator)
SCEVUnknown(ID.Intern(SCEVAllocator), V,
this,
4405 FirstUnknown, NextUnknownOrderID++);
4407 UniqueSCEVs.insert(S, Token);
4422 return Ty->isIntOrPtrTy();
4429 if (Ty->isPointerTy())
4440 if (Ty->isIntegerTy())
4444 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4456 bool PreciseA, PreciseB;
4457 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4458 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4459 if (!PreciseA || !PreciseB)
4462 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4463 DT.dominates(ScopeB, ScopeA);
4467 return CouldNotCompute.get();
4470bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4473 return SU && SU->getValue() ==
nullptr;
4476 return !ContainsNulls;
4481 if (
I != HasRecMap.end())
4486 HasRecMap.insert({S, FoundAddRec});
4494 if (
SI == ExprValueMap.
end())
4496 return SI->second.getArrayRef();
4502void ScalarEvolution::eraseValueFromMap(
Value *V) {
4504 if (
I != ValueExprMap.end()) {
4505 auto EVIt = ExprValueMap.find(
I->second);
4506 bool Removed = EVIt->second.remove(V);
4508 assert(Removed &&
"Value not in ExprValueMap?");
4509 ValueExprMap.erase(
I);
4513void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4517 auto It = ValueExprMap.find_as(V);
4518 if (It == ValueExprMap.end()) {
4520 ExprValueMap[S].insert(V);
4531 return createSCEVIter(V);
4538 if (
I != ValueExprMap.end()) {
4539 const SCEV *S =
I->second;
4540 assert(checkValidity(S) &&
4541 "existing SCEV has not been properly invalidated");
4553 Type *Ty = V->getType();
4569 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4582 return (
const SCEV *)
nullptr;
4588 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4592 Type *Ty = V->getType();
4598 assert(
P->getType()->isPointerTy());
4613 if (AddOp->getType()->isPointerTy()) {
4614 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4631 return getZero(LHS->getType());
4636 if (RHS->getType()->isPointerTy()) {
4637 if (!LHS->getType()->isPointerTy() ||
4647 const bool RHSIsNotMinSigned =
4678 Type *SrcTy = V->getType();
4679 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4680 "Cannot truncate or zero extend with non-integer arguments!");
4690 Type *SrcTy = V->getType();
4691 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4692 "Cannot truncate or zero extend with non-integer arguments!");
4701 Type *SrcTy = V->getType();
4702 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4703 "Cannot noop or zero extend with non-integer arguments!");
4705 "getNoopOrZeroExtend cannot truncate!");
4712 Type *SrcTy = V->getType();
4713 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4714 "Cannot noop or sign extend with non-integer arguments!");
4716 "getNoopOrSignExtend cannot truncate!");
4723 Type *SrcTy = V->getType();
4724 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4725 "Cannot noop or any extend with non-integer arguments!");
4727 "getNoopOrAnyExtend cannot truncate!");
4734 Type *SrcTy = V->getType();
4735 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4736 "Cannot truncate or noop with non-integer arguments!");
4738 "getTruncateOrNoop cannot extend!");
4746 const SCEV *PromotedLHS = LHS;
4747 const SCEV *PromotedRHS = RHS;
4767 assert(!
Ops.empty() &&
"At least one operand must be!");
4769 if (
Ops.size() == 1)
4773 Type *MaxType =
nullptr;
4779 assert(MaxType &&
"Failed to find maximum type!");
4792 if (!V->getType()->isPointerTy())
4797 V = AddRec->getStart();
4799 const SCEV *PtrOp =
nullptr;
4800 for (
const SCEV *AddOp :
Add->operands()) {
4801 if (AddOp->getType()->isPointerTy()) {
4802 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4806 assert(PtrOp &&
"Must have pointer op");
4818 for (
User *U :
I->users()) {
4820 if (Visited.
insert(UserInsn).second)
4834 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4835 bool IgnoreOtherLoops =
true) {
4838 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4840 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4845 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4847 SeenLoopVariantSCEVUnknown =
true;
4851 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4855 SeenOtherLoops =
true;
4859 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4861 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4864 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4865 : SCEVRewriteVisitor(SE),
L(
L) {}
4868 bool SeenLoopVariantSCEVUnknown =
false;
4869 bool SeenOtherLoops =
false;
4878 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4879 SCEVPostIncRewriter
Rewriter(L, SE);
4881 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4886 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4888 SeenLoopVariantSCEVUnknown =
true;
4892 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4896 SeenOtherLoops =
true;
4900 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4902 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4905 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4906 : SCEVRewriteVisitor(SE),
L(
L) {}
4909 bool SeenLoopVariantSCEVUnknown =
false;
4910 bool SeenOtherLoops =
false;
4916class SCEVBackedgeConditionFolder
4919 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4920 ScalarEvolution &SE) {
4921 bool IsPosBECond =
false;
4922 Value *BECond =
nullptr;
4923 if (BasicBlock *Latch =
L->getLoopLatch()) {
4925 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
4926 "Both outgoing branches should not target same header!");
4927 BECond = BI->getCondition();
4928 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
4933 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
4937 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4938 const SCEV *
Result = Expr;
4943 switch (
I->getOpcode()) {
4944 case Instruction::Select: {
4946 std::optional<const SCEV *> Res =
4947 compareWithBackedgeCondition(
SI->getCondition());
4955 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
4966 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
4967 bool IsPosBECond, ScalarEvolution &SE)
4968 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
4969 IsPositiveBECond(IsPosBECond) {}
4971 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
4975 Value *BackedgeCond =
nullptr;
4977 bool IsPositiveBECond;
4980std::optional<const SCEV *>
4981SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
4986 if (BackedgeCond == IC)
4989 return std::nullopt;
4994 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4995 ScalarEvolution &SE) {
5001 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5008 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5018 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5019 : SCEVRewriteVisitor(SE),
L(
L) {}
5027void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5043 const APInt &BECountAP = BECountMax->getAPInt();
5044 unsigned NoOverflowBitWidth =
5053ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5063 if (!SignedWrapViaInductionTried.insert(AR).second)
5088 AC.assumptions().empty())
5096 const SCEV *OverflowLimit =
5098 if (OverflowLimit &&
5106ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5116 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5141 AC.assumptions().empty())
5150 const SCEV *OverflowLimit =
5179 IsNSW = OBO->hasNoSignedWrap();
5180 IsNUW = OBO->hasNoUnsignedWrap();
5186 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5198 return std::nullopt;
5204 switch (
Op->getOpcode()) {
5205 case Instruction::Add:
5206 case Instruction::Sub:
5207 case Instruction::Mul:
5208 case Instruction::UDiv:
5209 case Instruction::URem:
5210 case Instruction::And:
5211 case Instruction::AShr:
5212 case Instruction::Shl:
5215 case Instruction::Or: {
5218 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5228 case Instruction::Xor:
5232 if (RHSC->getValue().isSignMask())
5233 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5235 if (V->getType()->isIntegerTy(1))
5236 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5239 case Instruction::LShr:
5248 if (SA->getValue().ult(
BitWidth)) {
5250 ConstantInt::get(SA->getContext(),
5252 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5257 case Instruction::ExtractValue: {
5259 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5267 bool Signed = WO->isSigned();
5270 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5275 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5286 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5287 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5289 return std::nullopt;
5315 if (
Op == SymbolicPHI)
5320 if (SourceBits != NewBits)
5338 if (!L || L->getHeader() != PN->
getParent())
5396std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5397ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5405 assert(L &&
"Expecting an integer loop header phi");
5410 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5411 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5412 Value *
V = PN->getIncomingValue(i);
5413 if (
L->contains(PN->getIncomingBlock(i))) {
5416 }
else if (BEValueV != V) {
5420 }
else if (!StartValueV) {
5422 }
else if (StartValueV != V) {
5423 StartValueV =
nullptr;
5427 if (!BEValueV || !StartValueV)
5428 return std::nullopt;
5430 const SCEV *BEValue =
getSCEV(BEValueV);
5437 return std::nullopt;
5441 unsigned FoundIndex =
Add->getNumOperands();
5442 Type *TruncTy =
nullptr;
5444 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5447 if (FoundIndex == e) {
5452 if (FoundIndex ==
Add->getNumOperands())
5453 return std::nullopt;
5457 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5458 if (i != FoundIndex)
5459 Ops.push_back(
Add->getOperand(i));
5465 return std::nullopt;
5518 const SCEV *StartVal =
getSCEV(StartValueV);
5519 const SCEV *PHISCEV =
5546 auto getExtendedExpr = [&](
const SCEV *Expr,
5547 bool CreateSignExtend) ->
const SCEV * {
5550 const SCEV *ExtendedExpr =
5553 return ExtendedExpr;
5561 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5562 const SCEV *ExtendedExpr) ->
bool {
5563 return Expr != ExtendedExpr &&
5567 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5568 if (PredIsKnownFalse(StartVal, StartExtended)) {
5570 return std::nullopt;
5575 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5576 if (PredIsKnownFalse(Accum, AccumExtended)) {
5578 return std::nullopt;
5581 auto AppendPredicate = [&](
const SCEV *Expr,
5582 const SCEV *ExtendedExpr) ->
void {
5583 if (Expr != ExtendedExpr &&
5591 AppendPredicate(StartVal, StartExtended);
5592 AppendPredicate(Accum, AccumExtended);
5600 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5601 std::make_pair(NewAR, Predicates);
5603 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5607std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5612 return std::nullopt;
5615 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5616 if (
I != PredicatedSCEVRewrites.end()) {
5617 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5620 if (Rewrite.first == SymbolicPHI)
5621 return std::nullopt;
5625 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5629 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5630 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5635 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5636 return std::nullopt;
5656 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5657 if (Expr1 != Expr2 &&
5658 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5659 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5694const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5696 Value *StartValueV) {
5699 assert(BEValueV && StartValueV);
5701 const SCEV *Accum =
nullptr;
5704 if (BO->Opcode != Instruction::Add)
5707 if (BO->LHS == PN &&
L->isLoopInvariant(BO->RHS))
5709 else if (BO->RHS == PN &&
L->isLoopInvariant(BO->LHS))
5723 if (!
GEP ||
GEP->getPointerOperand() != PN ||
GEP->getNumIndices() != 1)
5726 if (!
L->isLoopInvariant(Idx))
5735 const SCEV *StartVal =
getSCEV(StartValueV);
5736 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5737 insertValueToMap(PN, PHISCEV);
5740 inferNoWrapViaConstantRanges(AR);
5747 "Accum is defined outside L, but is not invariant?");
5748 if (isAddRecNeverPoison(BEInst, L))
5755const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5763 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5769 }
else if (BEValueV != V) {
5773 }
else if (!StartValueV) {
5775 }
else if (StartValueV != V) {
5776 StartValueV =
nullptr;
5780 if (!BEValueV || !StartValueV)
5783 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5784 "PHI node already processed?");
5788 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5793 insertValueToMap(PN, SymbolicName);
5797 const SCEV *BEValue =
getSCEV(BEValueV);
5807 unsigned FoundIndex =
Add->getNumOperands();
5808 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5809 if (
Add->getOperand(i) == SymbolicName)
5810 if (FoundIndex == e) {
5815 if (FoundIndex !=
Add->getNumOperands()) {
5818 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5819 if (i != FoundIndex)
5820 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5832 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5839 if (
GEP->getOperand(0) == PN)
5847 const SCEV *StartVal =
getSCEV(StartValueV);
5848 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5853 forgetMemoizedResults({SymbolicName});
5854 insertValueToMap(PN, PHISCEV);
5857 inferNoWrapViaConstantRanges(AR);
5881 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5882 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5884 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5885 const SCEV *StartVal =
getSCEV(StartValueV);
5886 if (Start == StartVal) {
5890 forgetMemoizedResults({SymbolicName});
5891 insertValueToMap(PN, Shifted);
5901 eraseValueFromMap(PN);
5916 Use &LeftUse =
Merge->getOperandUse(0);
5917 Use &RightUse =
Merge->getOperandUse(1);
5953 assert(IDom &&
"At least the entry block should dominate PN");
5961const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
5966 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
5983 CommonInst = IncomingInst;
5999ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6005 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6006 bool SCEVExprsIdentical =
6008 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6009 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6012const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6013 if (
const SCEV *S = createAddRecFromPHI(PN))
6023 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6026 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6035 struct FindClosure {
6036 const SCEV *OperandToFind;
6042 bool canRecurseInto(
SCEVTypes Kind)
const {
6045 return RootKind == Kind || NonSequentialRootKind == Kind ||
6050 : OperandToFind(OperandToFind), RootKind(RootKind),
6051 NonSequentialRootKind(
6055 bool follow(
const SCEV *S) {
6056 Found = S == OperandToFind;
6058 return !isDone() && canRecurseInto(S->
getSCEVType());
6061 bool isDone()
const {
return Found; }
6064 FindClosure FC(OperandToFind, RootKind);
6069std::optional<const SCEV *>
6070ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6080 switch (ICI->getPredicate()) {
6094 bool Signed = ICI->isSigned();
6095 const SCEV *LA =
getSCEV(TrueVal);
6103 if (LA == LS &&
RA == RS)
6105 if (LA == RS &&
RA == LS)
6108 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6109 if (
Op->getType()->isPointerTy()) {
6120 LS = CoerceOperand(LS);
6121 RS = CoerceOperand(RS);
6145 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6146 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6160 X = ZExt->getOperand();
6162 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6173 return std::nullopt;
6176static std::optional<const SCEV *>
6178 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6182 "Unexpected operands of a select.");
6194 return std::nullopt;
6209static std::optional<const SCEV *>
6213 return std::nullopt;
6216 const auto *SETrue = SE->
getSCEV(TrueVal);
6217 const auto *SEFalse = SE->
getSCEV(FalseVal);
6221const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6223 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6225 V->getType() ==
TrueVal->getType() &&
6226 "Types of select hands and of the result must match.");
6229 if (!
V->getType()->isIntegerTy(1))
6232 if (std::optional<const SCEV *> S =
6245 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6249 if (std::optional<const SCEV *> S =
6250 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6256 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6262 assert(
GEP->getSourceElementType()->isSized() &&
6263 "GEP source element type must be sized");
6266 for (
Value *Index :
GEP->indices())
6271APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6274 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6277 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6279 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6282 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6300 return GetShiftedByZeros(TZ);
6310 return GetShiftedByZeros(TZ);
6314 if (
M->hasNoUnsignedWrap()) {
6317 for (
const SCEV *Operand :
M->operands().drop_front())
6325 for (
const SCEV *Operand :
M->operands())
6327 return GetShiftedByZeros(TZ);
6332 if (
N->hasNoUnsignedWrap())
6333 return GetGCDMultiple(
N);
6336 for (
const SCEV *Operand :
N->operands().drop_front())
6338 return GetShiftedByZeros(TZ);
6355 CtxI = &*F.getEntryBlock().begin();
6362 .allowEphemerals(
true))
6363 .countMinTrailingZeros();
6364 return GetShiftedByZeros(
Known);
6377 return getConstantMultipleImpl(S, CtxI);
6379 auto I = ConstantMultipleCache.find(S);
6380 if (
I != ConstantMultipleCache.end())
6383 APInt Result = getConstantMultipleImpl(S, CtxI);
6384 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6385 assert(InsertPair.second &&
"Should insert a new key");
6386 return InsertPair.first->second;
6403 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6406 if (std::optional<ConstantRange>
Range = CB->getRange())
6410 if (std::optional<ConstantRange>
Range =
A->getRange())
6413 return std::nullopt;
6420 UnsignedRanges.erase(AddRec);
6421 SignedRanges.erase(AddRec);
6422 ConstantMultipleCache.erase(AddRec);
6427getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6453 Value *Start, *Step;
6460 assert(L && L->getHeader() ==
P->getParent());
6473 case Instruction::AShr:
6474 case Instruction::LShr:
6475 case Instruction::Shl:
6490 KnownStep.getBitWidth() ==
BitWidth);
6493 auto MaxShiftAmt = KnownStep.getMaxValue();
6495 bool Overflow =
false;
6496 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6503 case Instruction::AShr: {
6511 if (KnownStart.isNonNegative())
6514 KnownStart.getMaxValue() + 1);
6515 if (KnownStart.isNegative())
6518 KnownEnd.getMaxValue() + 1);
6521 case Instruction::LShr: {
6530 KnownStart.getMaxValue() + 1);
6532 case Instruction::Shl: {
6536 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6537 return ConstantRange(KnownStart.getMinValue(),
6538 KnownEnd.getMaxValue() + 1);
6563 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6570ScalarEvolution::getRangeRefIter(
const SCEV *S,
6571 ScalarEvolution::RangeSignHint SignHint) {
6572 DenseMap<const SCEV *, ConstantRange> &Cache =
6573 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6576 SmallPtrSet<const SCEV *, 8> Seen;
6580 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6581 if (!Seen.
insert(Expr).second)
6614 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6615 const SCEV *
P = WorkList[
I];
6619 for (
const SCEV *
Op :
P->operands())
6632 if (!WorkList.
empty()) {
6637 getRangeRef(
P, SignHint);
6641 return getRangeRef(S, SignHint, 0);
6644const APInt *ScalarEvolution::getConstantAPIntOrNull(
const SCEV *S) {
6646 return &
C->getAPInt();
6654 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6655 DenseMap<const SCEV *, ConstantRange> &Cache =
6656 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6663 auto I = Cache.
find(S);
6664 if (
I != Cache.
end())
6668 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6673 return getRangeRefIter(S, SignHint);
6676 ConstantRange ConservativeResult(
BitWidth,
true);
6677 using OBO = OverflowingBinaryOperator;
6681 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6685 ConservativeResult =
6692 ConservativeResult = ConstantRange(
6708 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6715 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6722 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6727 return setRange(Cast, SignHint,
X);
6732 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6733 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6735 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6736 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6737 ConservativeResult =
6738 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6740 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6741 unsigned WrapType = OBO::AnyWrap;
6742 if (
Add->hasNoSignedWrap())
6743 WrapType |= OBO::NoSignedWrap;
6744 if (
Add->hasNoUnsignedWrap())
6745 WrapType |= OBO::NoUnsignedWrap;
6747 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6749 return setRange(
Add, SignHint,
6750 ConservativeResult.intersectWith(
X, RangeType));
6754 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6756 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6757 return setRange(
Mul, SignHint,
6758 ConservativeResult.intersectWith(
X, RangeType));
6762 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6763 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6764 return setRange(UDiv, SignHint,
6765 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6773 if (!UnsignedMinValue.
isZero())
6774 ConservativeResult = ConservativeResult.intersectWith(
6775 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6784 bool AllNonNeg =
true;
6785 bool AllNonPos =
true;
6786 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6793 ConservativeResult = ConservativeResult.intersectWith(
6798 ConservativeResult = ConservativeResult.intersectWith(
6807 const SCEV *MaxBEScev =
6821 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6823 ConservativeResult =
6824 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6827 auto RangeFromFactoring = getRangeViaFactoring(
6829 ConservativeResult =
6830 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6836 const SCEV *SymbolicMaxBECount =
6841 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6842 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6843 ConservativeResult =
6844 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6849 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6859 ID = Intrinsic::umax;
6862 ID = Intrinsic::smax;
6866 ID = Intrinsic::umin;
6869 ID = Intrinsic::smin;
6876 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6877 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6879 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6880 return setRange(S, SignHint,
6881 ConservativeResult.intersectWith(
X, RangeType));
6890 ConservativeResult =
6891 ConservativeResult.intersectWith(*MDRange, RangeType);
6896 auto CR = getRangeForUnknownRecurrence(U);
6897 ConservativeResult = ConservativeResult.intersectWith(CR);
6908 if (
U->getType()->isPointerTy()) {
6911 unsigned PtrIdxDiff =
6912 DL.getPointerTypeSizeInBits(
U->getType()) -
BitWidth;
6913 NS = NS > PtrIdxDiff ? NS - PtrIdxDiff : 1;
6918 if (!
Known.Zero.getHiBits(NS).isZero())
6919 Known.Zero.setHighBits(NS);
6920 if (!
Known.One.getHiBits(NS).isZero())
6921 Known.One.setHighBits(NS);
6924 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
6925 ConservativeResult = ConservativeResult.intersectWith(
6926 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
6929 ConservativeResult = ConservativeResult.intersectWith(
6934 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6938 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
6939 DL, CanBeNull,
nullptr);
6955 ConservativeResult = ConservativeResult.intersectWith(
6965 return getRangeRef(AR, SignHint,
Depth + 1);
6969 ConstantRange RangeFromOps(
BitWidth,
false);
6971 for (
const auto &
Op :
Phi->operands()) {
6973 RangeFromOps = RangeFromOps.unionWith(OpRange);
6975 if (RangeFromOps.isFullSet())
6978 ConservativeResult =
6979 ConservativeResult.intersectWith(RangeFromOps, RangeType);
6985 if (
II->getIntrinsicID() == Intrinsic::vscale) {
6987 ConservativeResult = ConservativeResult.difference(Disallowed);
6990 return setRange(U, SignHint, std::move(ConservativeResult));
6996 return setRange(S, SignHint, std::move(ConservativeResult));
7004static std::pair<ConstantRange, bool>
7012 if (Step == 0 || MaxBECount == 0)
7013 return {StartRange,
true};
7019 return {ConstantRange::getFull(
BitWidth),
false};
7035 return {ConstantRange::getFull(
BitWidth),
false};
7048 APInt MovedBoundary;
7053 MovedBoundary = StartLower - std::move(
Offset);
7056 MovedBoundary = StartUpper + std::move(
Offset);
7060 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7067 if (StartRange.
contains(MovedBoundary))
7068 return {ConstantRange::getFull(
BitWidth),
false};
7071 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7073 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7081std::pair<ConstantRange, SCEVFlags>
7082ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7083 const APInt &MaxBECount) {
7087 "mismatched bit widths");
7096 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7098 StartSRange, MaxBECount,
7100 ConstantRange SR = SR1.unionWith(SR2);
7117ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7119 ScalarEvolution::RangeSignHint SignHint) {
7120 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7122 "This only works for non-self-wrapping AddRecs!");
7123 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7127 return ConstantRange::getFull(
BitWidth);
7135 return ConstantRange::getFull(
BitWidth);
7139 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7141 MaxItersWithoutWrap))
7142 return ConstantRange::getFull(
BitWidth);
7163 ConstantRange StartRange = getRangeRef(Start, SignHint);
7164 ConstantRange EndRange = getRangeRef(
End, SignHint);
7165 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7169 return RangeBetween;
7174 return ConstantRange::getFull(
BitWidth);
7177 isKnownPredicateViaConstantRanges(LEPred, Start,
End))
7178 return RangeBetween;
7180 isKnownPredicateViaConstantRanges(GEPred, Start,
End))
7181 return RangeBetween;
7182 return ConstantRange::getFull(
BitWidth);
7187 const APInt &MaxBECount) {
7194 "mismatched bit widths");
7196 struct SelectPattern {
7197 Value *Condition =
nullptr;
7201 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7203 std::optional<unsigned> CastOp;
7217 CastOp = SCast->getSCEVType();
7218 S = SCast->getOperand();
7221 using namespace llvm::PatternMatch;
7228 Condition =
nullptr;
7260 bool isRecognized() {
return Condition !=
nullptr; }
7263 SelectPattern StartPattern(*
this,
BitWidth, Start);
7264 if (!StartPattern.isRecognized())
7265 return ConstantRange::getFull(
BitWidth);
7267 SelectPattern StepPattern(*
this,
BitWidth, Step);
7268 if (!StepPattern.isRecognized())
7269 return ConstantRange::getFull(
BitWidth);
7271 if (StartPattern.Condition != StepPattern.Condition) {
7275 return ConstantRange::getFull(
BitWidth);
7286 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7287 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7288 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7289 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7291 ConstantRange TrueRange =
7292 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7293 ConstantRange FalseRange =
7294 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7307 PDI && PDI->isDisjoint()) {
7322ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7335 SmallPtrSet<const SCEV *, 16> Visited;
7337 auto pushOp = [&](
const SCEV *S) {
7338 if (!Visited.
insert(S).second)
7341 if (Visited.
size() > 30) {
7352 while (!Worklist.
empty()) {
7354 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7355 if (!Bound || DT.dominates(Bound, DefI))
7362 return Bound ? Bound : &*F.getEntryBlock().begin();
7368 return getDefiningScopeBound(
Ops, Discard);
7371bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7373 if (
A->getParent() ==
B->getParent() &&
7378 auto *BLoop = LI.getLoopFor(
B->getParent());
7379 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7380 BLoop->getLoopPreheader() ==
A->getParent() &&
7382 A->getParent()->end()) &&
7390 SCEVPoisonCollector PC(
true);
7392 return PC.MaybePoison.
empty();
7395bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7405bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7422 for (
const Use &
Op :
I->operands()) {
7428 auto *DefI = getDefiningScopeBound(SCEVOps);
7429 return isGuaranteedToTransferExecutionTo(DefI,
I);
7432bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7434 if (isSCEVExprNeverPoison(
I))
7445 auto *ExitingBB =
L->getExitingBlock();
7449 SmallPtrSet<const Value *, 16> KnownPoison;
7458 while (!Worklist.
empty()) {
7461 for (
const Use &U :
Poison->uses()) {
7464 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7468 if (KnownPoison.
insert(PoisonUser).second)
7476ScalarEvolution::LoopProperties
7477ScalarEvolution::getLoopProperties(
const Loop *L) {
7478 using LoopProperties = ScalarEvolution::LoopProperties;
7480 auto Itr = LoopPropertiesCache.find(L);
7481 if (Itr == LoopPropertiesCache.end()) {
7484 return !
SI->isSimple();
7494 return I->mayWriteToMemory();
7497 LoopProperties LP = {
true,
7500 for (
auto *BB :
L->getBlocks())
7501 for (
auto &
I : *BB) {
7503 LP.HasNoAbnormalExits =
false;
7504 if (HasSideEffects(&
I))
7505 LP.HasNoSideEffects =
false;
7506 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7510 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7511 assert(InsertPair.second &&
"We just checked!");
7512 Itr = InsertPair.first;
7525const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7531 Stack.emplace_back(V,
false);
7532 while (!Stack.empty()) {
7533 auto E = Stack.back();
7534 Value *CurV = E.getPointer();
7542 const SCEV *CreatedSCEV =
nullptr;
7545 CreatedSCEV = createSCEV(CurV);
7550 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7554 insertValueToMap(CurV, CreatedSCEV);
7557 Stack.back().setInt(
true);
7560 Stack.emplace_back(
Op,
false);
7577 if (!DT.isReachableFromEntry(
I->getParent()))
7590 switch (BO->Opcode) {
7591 case Instruction::Add:
7592 case Instruction::Mul: {
7599 Ops.push_back(BO->
Op);
7603 Ops.push_back(BO->RHS);
7607 (BO->Opcode == Instruction::Add &&
7608 (NewBO->Opcode != Instruction::Add &&
7609 NewBO->Opcode != Instruction::Sub)) ||
7610 (BO->Opcode == Instruction::Mul &&
7611 NewBO->Opcode != Instruction::Mul)) {
7612 Ops.push_back(BO->LHS);
7617 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7620 Ops.push_back(BO->LHS);
7628 case Instruction::Sub:
7629 case Instruction::UDiv:
7630 case Instruction::URem:
7632 case Instruction::AShr:
7633 case Instruction::Shl:
7634 case Instruction::Xor:
7638 case Instruction::And:
7639 case Instruction::Or:
7643 case Instruction::LShr:
7650 Ops.push_back(BO->LHS);
7651 Ops.push_back(BO->RHS);
7655 switch (
U->getOpcode()) {
7656 case Instruction::Trunc:
7657 case Instruction::ZExt:
7658 case Instruction::SExt:
7659 case Instruction::PtrToAddr:
7660 case Instruction::PtrToInt:
7661 Ops.push_back(
U->getOperand(0));
7664 case Instruction::BitCast:
7666 Ops.push_back(
U->getOperand(0));
7671 case Instruction::SDiv:
7672 case Instruction::SRem:
7673 Ops.push_back(
U->getOperand(0));
7674 Ops.push_back(
U->getOperand(1));
7677 case Instruction::GetElementPtr:
7679 "GEP source element type must be sized");
7683 case Instruction::IntToPtr:
7686 case Instruction::PHI:
7717 Ops.push_back(CondICmp->getOperand(0));
7718 Ops.push_back(CondICmp->getOperand(1));
7738 case Instruction::Select: {
7740 auto CanSimplifyToUnknown = [
this,
U]() {
7758 if (CanSimplifyToUnknown())
7765 case Instruction::Call:
7766 case Instruction::Invoke:
7773 switch (
II->getIntrinsicID()) {
7774 case Intrinsic::abs:
7775 Ops.push_back(
II->getArgOperand(0));
7777 case Intrinsic::umax:
7778 case Intrinsic::umin:
7779 case Intrinsic::smax:
7780 case Intrinsic::smin:
7781 case Intrinsic::usub_sat:
7782 case Intrinsic::uadd_sat:
7783 Ops.push_back(
II->getArgOperand(0));
7784 Ops.push_back(
II->getArgOperand(1));
7786 case Intrinsic::start_loop_iterations:
7787 case Intrinsic::annotation:
7788 case Intrinsic::ptr_annotation:
7789 Ops.push_back(
II->getArgOperand(0));
7801const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7810 if (!DT.isReachableFromEntry(
I->getParent()))
7825 switch (BO->Opcode) {
7826 case Instruction::Add: {
7852 if (BO->Opcode == Instruction::Sub)
7860 if (BO->Opcode == Instruction::Sub)
7867 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7868 NewBO->Opcode != Instruction::Sub)) {
7878 case Instruction::Mul: {
7899 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7908 case Instruction::UDiv:
7912 case Instruction::URem:
7916 case Instruction::Sub: {
7919 Flags = getNoWrapFlagsFromUB(BO->
Op);
7924 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
7927 if (HasPtrLHS || HasPtrRHS) {
7932 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
7933 bool BothPtr) ->
const SCEV * {
7936 const SCEV *PtrSCEV =
getSCEV(PtrOp);
7946 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
7947 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
7955 case Instruction::And:
7961 if (CI->isMinusOne())
7963 const APInt &
A = CI->getValue();
7969 unsigned LZ =
A.countl_zero();
7970 unsigned TZ =
A.countr_zero();
7975 APInt EffectiveMask =
7977 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
7980 const SCEV *ShiftedLHS =
nullptr;
7984 unsigned MulZeros = OpC->getAPInt().countr_zero();
7985 unsigned GCD = std::min(MulZeros, TZ);
7990 const SCEV *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8012 case Instruction::Or:
8021 case Instruction::Xor:
8024 if (CI->isMinusOne())
8033 if (LBO->getOpcode() == Instruction::And &&
8034 LCI->getValue() == CI->getValue())
8035 if (
const SCEVZeroExtendExpr *Z =
8038 const SCEV *Z0 =
Z->getOperand();
8045 if (CI->getValue().isMask(Z0TySize))
8051 APInt Trunc = CI->getValue().trunc(Z0TySize);
8060 case Instruction::Shl:
8078 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8087 ConstantInt *
X = ConstantInt::get(
8093 case Instruction::AShr:
8115 const SCEV *AddTruncateExpr =
nullptr;
8116 ConstantInt *ShlAmtCI =
nullptr;
8117 const SCEV *AddConstant =
nullptr;
8119 if (L &&
L->getOpcode() == Instruction::Add) {
8127 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8134 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8142 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8147 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8152 if (AddTruncateExpr && ShlAmtCI) {
8164 const APInt &ShlAmt = ShlAmtCI->
getValue();
8168 const SCEV *CompositeExpr =
8170 if (
L->getOpcode() != Instruction::Shl)
8171 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8180 switch (
U->getOpcode()) {
8181 case Instruction::Trunc:
8184 case Instruction::ZExt:
8187 case Instruction::SExt:
8197 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8198 Type *Ty =
U->getType();
8206 case Instruction::BitCast:
8212 case Instruction::PtrToAddr: {
8219 case Instruction::PtrToInt:
8223 case Instruction::IntToPtr:
8227 case Instruction::SDiv:
8234 case Instruction::SRem:
8241 case Instruction::GetElementPtr:
8244 case Instruction::PHI:
8247 case Instruction::Select:
8248 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8251 case Instruction::Call:
8252 case Instruction::Invoke:
8257 switch (
II->getIntrinsicID()) {
8258 case Intrinsic::abs:
8262 case Intrinsic::umax:
8266 case Intrinsic::umin:
8270 case Intrinsic::smax:
8274 case Intrinsic::smin:
8278 case Intrinsic::usub_sat: {
8279 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8280 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8284 case Intrinsic::uadd_sat: {
8285 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8286 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8290 case Intrinsic::start_loop_iterations:
8291 case Intrinsic::annotation:
8292 case Intrinsic::ptr_annotation:
8296 case Intrinsic::vscale:
8316 auto *ExitCountType = ExitCount->
getType();
8317 assert(ExitCountType->isIntegerTy());
8319 1 + ExitCountType->getScalarSizeInBits());
8332 auto CanAddOneWithoutOverflow = [&]() {
8334 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8345 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8375 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8376 assert(L->isLoopExiting(ExitingBlock) &&
8377 "Exiting block must actually branch out of the loop!");
8386 const auto *MaxExitCount =
8394 L->getExitingBlocks(ExitingBlocks);
8397 if (ExitingBlocks.
empty() ||
8413 const LoopGuards &Guards) {
8417 const SCEV *TCExpr =
8425 : (
unsigned)Multiple.getZExtValue();
8429 const SCEV *ExitCount) {
8451 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8452 assert(L->isLoopExiting(ExitingBlock) &&
8453 "Exiting block must actually branch out of the loop!");
8463 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8465 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8467 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8477 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8480 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8483 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8491 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8498 return getBackedgeTakenInfo(L).getExact(L,
this);
8500 return getBackedgeTakenInfo(L).getConstantMax(
this);
8502 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8509 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8514 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8518 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8528 for (
PHINode &PN : Header->phis())
8529 if (Visited.
insert(&PN).second)
8533ScalarEvolution::BackedgeTakenInfo &
8534ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8535 auto &BTI = getBackedgeTakenInfo(L);
8536 if (BTI.hasFullInfo())
8539 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8542 return Pair.first->second;
8544 BackedgeTakenInfo
Result =
8545 computeBackedgeTakenCount(L,
true);
8547 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8550ScalarEvolution::BackedgeTakenInfo &
8551ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8557 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8558 BackedgeTakenCounts.try_emplace(L);
8560 return Pair.first->second;
8565 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8572 if (
Result.hasAnyInfo()) {
8575 auto LoopUsersIt = LoopUsers.find(L);
8576 if (LoopUsersIt != LoopUsers.end())
8578 forgetMemoizedResults(ToForget);
8581 for (PHINode &PN :
L->getHeader()->phis())
8582 ConstantEvolutionLoopExitValue.erase(&PN);
8590 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8599 BackedgeTakenCounts.clear();
8600 PredicatedBackedgeTakenCounts.clear();
8601 BECountUsers.clear();
8602 LoopPropertiesCache.clear();
8603 ConstantEvolutionLoopExitValue.clear();
8604 ValueExprMap.clear();
8605 ValuesAtScopes.clear();
8606 ValuesAtScopesUsers.clear();
8607 LoopDispositions.clear();
8608 BlockDispositions.clear();
8609 UnsignedRanges.clear();
8610 SignedRanges.clear();
8611 ExprValueMap.clear();
8613 ConstantMultipleCache.clear();
8614 PredicatedSCEVRewrites.clear();
8616 FoldCacheUser.clear();
8618void ScalarEvolution::visitAndClearUsers(
8623 if (ValueExprMap.
empty()) {
8627 while (!Worklist.
empty()) {
8634 if (It != ValueExprMap.
end()) {
8636 eraseValueFromMap(It->first);
8638 ConstantEvolutionLoopExitValue.erase(PN);
8652 while (!LoopWorklist.
empty()) {
8656 forgetBackedgeTakenCounts(CurrL,
false);
8657 forgetBackedgeTakenCounts(CurrL,
true);
8660 PredicatedSCEVRewrites.remove_if(
8661 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8663 auto LoopUsersItr = LoopUsers.find(CurrL);
8664 if (LoopUsersItr != LoopUsers.end())
8669 visitAndClearUsers(Worklist, Visited, ToForget);
8671 LoopPropertiesCache.erase(CurrL);
8674 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8676 forgetMemoizedResults(ToForget);
8693 visitAndClearUsers(Worklist, Visited, ToForget);
8695 forgetMemoizedResults(ToForget);
8706 visitAndClearUsers(Worklist, Visited, ToForget);
8708 forgetMemoizedResults(ToForget);
8716 auto InvalidateValue = [&](
Value *Val) {
8720 struct InvalidationRootCollector {
8724 InvalidationRootCollector(
Loop *L) : L(L) {}
8726 bool follow(
const SCEV *S) {
8732 if (L->contains(AddRec->
getLoop()))
8737 bool isDone()
const {
return false; }
8740 InvalidationRootCollector
C(L);
8742 forgetMemoizedResults(
C.Roots);
8765 BlockDispositions.clear();
8766 LoopDispositions.clear();
8783 while (!Worklist.
empty()) {
8785 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8786 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8787 if (!LoopDispoRemoved && !BlockDispoRemoved)
8789 auto Users = SCEVUsers.find(Curr);
8790 if (
Users != SCEVUsers.end())
8803const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8807 if (!isComplete() || ExitNotTaken.
empty())
8818 for (
const auto &ENT : ExitNotTaken) {
8819 const SCEV *BECount = ENT.ExactNotTaken;
8822 "We should only have known counts for exiting blocks that dominate "
8825 Ops.push_back(BECount);
8830 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8831 "Predicate should be always true!");
8840const ScalarEvolution::ExitNotTakenInfo *
8841ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8842 const BasicBlock *ExitingBlock,
8843 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8844 for (
const auto &ENT : ExitNotTaken)
8845 if (ENT.ExitingBlock == ExitingBlock) {
8846 if (ENT.hasAlwaysTruePredicate())
8848 else if (Predicates) {
8858const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8860 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8861 if (!getConstantMax())
8864 for (
const auto &ENT : ExitNotTaken)
8865 if (!ENT.hasAlwaysTruePredicate()) {
8873 "No point in having a non-constant max backedge taken count!");
8874 return getConstantMax();
8877const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8879 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8887 for (
const auto &ENT : ExitNotTaken) {
8888 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8891 "We should only have known counts for exiting blocks that "
8897 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8898 "Predicate should be always true!");
8901 if (ExitCounts.
empty())
8910bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8912 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8913 return !ENT.hasAlwaysTruePredicate();
8915 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8931 this->ExactNotTaken = E = ConstantMaxNotTaken;
8932 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8937 "Exact is not allowed to be less precise than Constant Max");
8940 "Exact is not allowed to be less precise than Symbolic Max");
8943 "Symbolic Max is not allowed to be less precise than Constant Max");
8946 "No point in having a non-constant max backedge taken count!");
8948 for (
const auto PredList : PredLists)
8949 for (
const auto *
P : PredList) {
8957 "Backedge count should be int");
8960 "Max backedge count should be int");
8973ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8975 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8976 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8977 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8979 ExitNotTaken.reserve(ExitCounts.
size());
8980 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8981 std::back_inserter(ExitNotTaken),
8982 [&](
const EdgeExitInfo &EEI) {
8983 BasicBlock *ExitBB = EEI.first;
8984 const ExitLimit &EL = EEI.second;
8985 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
8986 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
8991 "No point in having a non-constant max backedge taken count!");
8995ScalarEvolution::BackedgeTakenInfo
8996ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
8997 bool AllowPredicates) {
8999 L->getExitingBlocks(ExitingBlocks);
9001 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9004 bool CouldComputeBECount =
true;
9006 const SCEV *MustExitMaxBECount =
nullptr;
9007 const SCEV *MayExitMaxBECount =
nullptr;
9008 bool MustExitMaxOrZero =
false;
9009 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9020 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9021 if (ExitIfTrue == CI->
isZero())
9025 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9027 assert((AllowPredicates || EL.Predicates.empty()) &&
9028 "Predicated exit limit when predicates are not allowed!");
9033 ++NumExitCountsComputed;
9037 CouldComputeBECount =
false;
9044 "Exact is known but symbolic isn't?");
9045 ++NumExitCountsNotComputed;
9060 DT.dominates(ExitBB, Latch)) {
9061 if (!MustExitMaxBECount) {
9062 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9063 MustExitMaxOrZero = EL.MaxOrZero;
9066 EL.ConstantMaxNotTaken);
9070 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9073 EL.ConstantMaxNotTaken);
9077 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9081 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9087 for (
const auto &Pair : ExitCounts) {
9089 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9091 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9092 {
L, AllowPredicates});
9094 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9095 MaxBECount, MaxOrZero);
9098ScalarEvolution::ExitLimit
9099ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9100 bool IsOnlyExit,
bool AllowPredicates) {
9101 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9105 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9110 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9111 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9112 "It should have one successor in loop and one exit block!");
9123 if (!
L->contains(SBB)) {
9128 assert(Exit &&
"Exiting block must have at least one exit");
9129 return computeExitLimitFromSingleExitSwitch(
9130 L, SI, Exit, IsOnlyExit);
9137 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9138 bool AllowPredicates) {
9139 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9140 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9141 ControlsOnlyExit, AllowPredicates);
9144std::optional<ScalarEvolution::ExitLimit>
9145ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9146 bool ExitIfTrue,
bool ControlsOnlyExit,
9147 bool AllowPredicates) {
9149 (void)this->ExitIfTrue;
9150 (void)this->AllowPredicates;
9152 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9153 this->AllowPredicates == AllowPredicates &&
9154 "Variance in assumed invariant key components!");
9155 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9156 if (Itr == TripCountMap.end())
9157 return std::nullopt;
9161void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9163 bool ControlsOnlyExit,
9164 bool AllowPredicates,
9166 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9167 this->AllowPredicates == AllowPredicates &&
9168 "Variance in assumed invariant key components!");
9170 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9171 assert(InsertResult.second &&
"Expected successful insertion!");
9176ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9177 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9178 bool ControlsOnlyExit,
bool AllowPredicates) {
9180 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9184 ExitLimit EL = computeExitLimitFromCondImpl(
9185 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9186 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9190ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9191 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9192 bool ControlsOnlyExit,
bool AllowPredicates) {
9194 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9195 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9196 return *LimitFromBinOp;
9202 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9203 if (EL.hasFullInfo() || !AllowPredicates)
9207 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9227 const WithOverflowInst *WO;
9242 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9243 ControlsOnlyExit, AllowPredicates);
9244 if (EL.hasAnyInfo())
9249 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9252std::optional<ScalarEvolution::ExitLimit>
9253ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9257 bool AllowPredicates) {
9266 return std::nullopt;
9270 ExitLimit EL0 = computeExitLimitFromCondCached(
9271 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9272 ExitLimit EL1 = computeExitLimitFromCondCached(
9273 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9278 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9283 if (EitherMayExit) {
9293 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9295 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9298 EL1.ConstantMaxNotTaken);
9300 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9302 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9305 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9309 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9310 BECount = EL0.ExactNotTaken;
9323 SymbolicMaxBECount =
9325 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9329ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9330 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9331 bool AllowPredicates) {
9343 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9345 if (EL.hasAnyInfo())
9348 auto *ExhaustiveCount =
9349 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9352 return ExhaustiveCount;
9354 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9357ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9359 bool ControlsOnlyExit,
bool AllowPredicates) {
9384 ConstantRange CompRange =
9402 InnerLHS = ZExt->getOperand();
9449 if (EL.hasAnyInfo())
9466 if (EL.hasAnyInfo())
return EL;
9499 ControlsOnlyExit, AllowPredicates);
9500 if (EL.hasAnyInfo())
9518 ControlsOnlyExit, AllowPredicates);
9519 if (EL.hasAnyInfo())
9530ScalarEvolution::ExitLimit
9531ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9533 BasicBlock *ExitingBlock,
9534 bool ControlsOnlyExit) {
9535 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9538 if (
Switch->getDefaultDest() == ExitingBlock)
9542 "Default case must not exit the loop!");
9548 if (EL.hasAnyInfo())
9560 "Evaluation of SCEV at constant didn't fold correctly?");
9564ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9574 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9581 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9583 unsigned &OutShiftAmt) {
9584 using namespace PatternMatch;
9586 ConstantInt *ShiftAmt;
9588 OutOpCode = Instruction::LShr;
9590 OutOpCode = Instruction::AShr;
9592 OutOpCode = Instruction::Shl;
9597 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9612 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9614 unsigned &ShiftAmtOut) {
9615 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9631 if (MatchPositiveShift(
LHS, V, OpC, Amt)) {
9632 PostShiftOpCode = OpC;
9638 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9641 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9647 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9654 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9660 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9672 ConstantInt *StableValue =
nullptr;
9677 case Instruction::AShr: {
9684 if (
Known.isNonNegative())
9685 StableValue = ConstantInt::get(Ty, 0);
9686 else if (
Known.isNegative())
9687 StableValue = ConstantInt::get(Ty, -1,
true);
9693 case Instruction::LShr:
9694 case Instruction::Shl:
9704 "Otherwise cannot be an operand to a branch instruction");
9706 if (
Result->isNullValue()) {
9715 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9717 const SCEV *StartSCEV =
getSCEV(StartValue);
9721 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9722 MaxBTC = std::min(MaxBTC, RangeBTC);
9726 const SCEV *UpperBound =
9744 if (
const Function *
F = CI->getCalledFunction())
9754 if (!L->contains(
I))
return false;
9759 return L->getHeader() ==
I->getParent();
9838 if (!
I)
return nullptr;
9852 std::vector<Constant*>
Operands(
I->getNumOperands());
9854 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9863 if (!
C)
return nullptr;
9885 if (IncomingVal != CurrentVal) {
9888 IncomingVal = CurrentVal;
9900ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9903 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9912 DenseMap<Instruction *, Constant *> CurrentIterVals;
9914 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9920 for (PHINode &
PHI : Header->phis()) {
9922 CurrentIterVals[&
PHI] = StartCST;
9924 if (!CurrentIterVals.
count(PN))
9925 return RetVal =
nullptr;
9931 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9934 unsigned IterationNum = 0;
9936 for (; ; ++IterationNum) {
9937 if (IterationNum == NumIterations)
9938 return RetVal = CurrentIterVals[PN];
9942 DenseMap<Instruction *, Constant *> NextIterVals;
9947 NextIterVals[PN] = NextPHI;
9949 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9955 for (
const auto &
I : CurrentIterVals) {
9957 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9962 for (
const auto &
I : PHIsToCompute) {
9963 PHINode *
PHI =
I.first;
9966 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9969 if (NextPHI !=
I.second)
9970 StoppedEvolving =
false;
9975 if (StoppedEvolving)
9976 return RetVal = CurrentIterVals[PN];
9978 CurrentIterVals.swap(NextIterVals);
9982const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
9992 DenseMap<Instruction *, Constant *> CurrentIterVals;
9994 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9997 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
9999 for (PHINode &
PHI : Header->phis()) {
10001 CurrentIterVals[&
PHI] = StartCST;
10003 if (!CurrentIterVals.
count(PN))
10011 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10018 if (CondVal->getValue() ==
uint64_t(ExitWhen)) {
10019 ++NumBruteForceTripCountsComputed;
10024 DenseMap<Instruction *, Constant *> NextIterVals;
10030 for (
const auto &
I : CurrentIterVals) {
10032 if (!
PHI ||
PHI->getParent() != Header)
continue;
10035 for (PHINode *
PHI : PHIsToCompute) {
10037 if (NextPHI)
continue;
10039 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10042 CurrentIterVals.
swap(NextIterVals);
10050 auto &
Values = ValuesAtScopes[V];
10054 return LS.second ? LS.second :
SCEVUse(V);
10056 Values.emplace_back(L,
nullptr);
10059 SCEVUse C = computeSCEVAtScope(V, L);
10060 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10061 if (LS.first == L) {
10067 ValuesAtScopesUsers[
C.getPointer()].push_back({L, V});
10094 switch (V->getSCEVType()) {
10127 assert(!
C->getType()->isPointerTy() &&
10128 "Can only have one pointer, and it must be last");
10153const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10154 SmallVectorImpl<SCEVUse> &NewOps) {
10188SCEVUse ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10189 switch (
V->getSCEVType()) {
10200 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10211 for (++i; i !=
e; ++i)
10251 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10261 for (++i; i !=
e; ++i) {
10266 return getWithOperands(V, NewOps);
10281 const Loop *CurrLoop = this->LI[
I->getParent()];
10292 if (BackedgeTakenCount->
isZero()) {
10293 Value *InitValue =
nullptr;
10294 bool MultipleInitValues =
false;
10300 MultipleInitValues =
true;
10305 if (!MultipleInitValues && InitValue)
10314 unsigned InLoopPred =
10325 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10339 SmallVector<Constant *, 4>
Operands;
10341 bool MadeImprovement =
false;
10356 MadeImprovement |= OrigV != OpV;
10361 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10366 if (!MadeImprovement)
10387const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10389 return stripInjectiveFunctions(ZExt->getOperand());
10391 return stripInjectiveFunctions(SExt->getOperand());
10409 assert(
A != 0 &&
"A must be non-zero.");
10425 if (MinTZ < Mult2 && L->getLoopPredecessor())
10427 if (MinTZ < Mult2) {
10450 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10470static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10476 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10477 << *AddRec <<
'\n');
10480 if (!LC || !MC || !
NC) {
10481 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10482 return std::nullopt;
10488 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10496 N =
N.sext(NewWidth);
10497 M = M.sext(NewWidth);
10498 L = L.sext(NewWidth);
10515 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10516 <<
", multiplied by " <<
T <<
'\n');
10525 std::optional<APInt>
Y) {
10527 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10530 return XW.
slt(YW) ? *
X : *
Y;
10533 return std::nullopt;
10534 return X ? *
X : *
Y;
10551 return std::nullopt;
10552 unsigned W =
X->getBitWidth();
10572static std::optional<APInt>
10578 return std::nullopt;
10581 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10582 std::optional<APInt>
X =
10585 return std::nullopt;
10590 return std::nullopt;
10605static std::optional<APInt>
10609 "Starting value of addrec should be 0");
10610 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10611 <<
Range <<
", addrec " << *AddRec <<
'\n');
10615 "Addrec's initial value should be in range");
10621 return std::nullopt;
10631 auto SolveForBoundary =
10632 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10635 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10636 << Bound <<
" (before multiplying by " << M <<
")\n");
10639 std::optional<APInt> SO;
10642 "signed overflow\n");
10646 "unsigned overflow\n");
10647 std::optional<APInt> UO =
10650 auto LeavesRange = [&] (
const APInt &
X) {
10653 if (
Range.contains(V0->getValue()))
10658 if (
Range.contains(
V1->getValue()))
10667 return {std::nullopt,
false};
10672 if (LeavesRange(*Min))
10673 return { Min,
true };
10674 std::optional<APInt> Max = Min == SO ? UO : SO;
10675 if (LeavesRange(*Max))
10676 return { Max,
true };
10679 return {std::nullopt,
true};
10686 auto SL = SolveForBoundary(
Lower);
10687 auto SU = SolveForBoundary(
Upper);
10690 if (!SL.second || !SU.second)
10691 return std::nullopt;
10734ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10736 bool ControlsOnlyExit,
10737 bool AllowPredicates) {
10748 if (
C->getValue()->isZero())
return C;
10752 const SCEVAddRecExpr *AddRec =
10755 if (!AddRec && AllowPredicates)
10761 if (!AddRec || AddRec->
getLoop() != L)
10772 return ExitLimit(R, R, R,
false, Predicates);
10830 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10860 const SCEV *
Exact =
10868 const SCEV *SymbolicMax =
10870 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10879 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10887 return ExitLimit(
E, M, S,
false, Predicates);
10890ScalarEvolution::ExitLimit
10891ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10899 if (!
C->getValue()->isZero())
10909std::pair<const BasicBlock *, const BasicBlock *>
10910ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10921 if (
const Loop *L = LI.getLoopFor(BB))
10922 return {
L->getLoopPredecessor(),
L->getHeader()};
10924 return {
nullptr, BB};
10933 if (
A ==
B)
return true;
10948 if (ComputesEqualValues(AI, BI))
10956 const SCEV *Op0, *Op1;
10975 auto TrivialCase = [&](
bool TriviallyTrue) {
10984 const SCEV *NewLHS, *NewRHS;
11008 return TrivialCase(
false);
11009 return TrivialCase(
true);
11028 RAdd->hasNoSignedWrap()) ||
11030 RAdd->hasNoUnsignedWrap())) {
11050 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
11051 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
11054 C->getAPInt().isStrictlyPositive()) ||
11078 const APInt &
RA = RC->getAPInt();
11080 bool SimplifiedByConstantRange =
false;
11085 return TrivialCase(
true);
11087 return TrivialCase(
false);
11096 Changed = SimplifiedByConstantRange =
true;
11100 if (!SimplifiedByConstantRange) {
11117 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11123 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11129 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11135 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11155 return TrivialCase(
true);
11157 return TrivialCase(
false);
11262 auto NonRecursive = [OrNegative](
const SCEV *S) {
11264 return C->getAPInt().isPowerOf2() ||
11265 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11271 if (NonRecursive(S))
11281 const SCEV *S, uint64_t M,
11290 APInt C = Cst->getAPInt();
11291 return C.urem(M) == 0;
11297 const SCEV *SmodM =
11318 [&](
SCEVUse Op) { return isKnownMultipleOf(Op, M, Predicates); }))
11325 return isKnownMultipleOf(Op, M, Predicates);
11331 return isKnownMultipleOf(Op, M, Predicates);
11338 for (
auto *
A : *Predicates)
11339 if (
A->implies(
P, *
this))
11352std::pair<const SCEV *, const SCEV *>
11355 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11357 return { Start, Start };
11359 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11368 getUsedLoops(LHS, LoopsUsed);
11369 getUsedLoops(RHS, LoopsUsed);
11371 if (LoopsUsed.
empty())
11376 for (
const auto *L1 : LoopsUsed)
11377 for (
const auto *L2 : LoopsUsed)
11378 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11379 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11380 "Domination relationship is not a linear order");
11410 SplitRHS.second) &&
11420 isKnownPredicateViaSplitting(Pred, LHS, RHS) ||
11421 isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11431 return std::nullopt;
11446 if (KnownWithoutContext)
11447 return KnownWithoutContext;
11454 return std::nullopt;
11460 const Loop *L = LHS->getLoop();
11465std::optional<ScalarEvolution::MonotonicPredicateType>
11468 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11474 auto ResultSwapped =
11477 assert(*ResultSwapped != *Result &&
11478 "monotonicity should flip as we flip the predicate");
11485std::optional<ScalarEvolution::MonotonicPredicateType>
11486ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11500 return std::nullopt;
11504 "Should be greater or less!");
11508 if (!LHS->hasNoUnsignedWrap())
11509 return std::nullopt;
11513 "Relational predicate is either signed or unsigned!");
11514 if (!
LHS->hasNoSignedWrap())
11515 return std::nullopt;
11517 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11525 return std::nullopt;
11528std::optional<ScalarEvolution::LoopInvariantPredicate>
11535 return std::nullopt;
11542 if (!ArLHS || ArLHS->
getLoop() != L)
11543 return std::nullopt;
11547 return std::nullopt;
11573 return std::nullopt;
11610 return std::nullopt;
11613std::optional<ScalarEvolution::LoopInvariantPredicate>
11618 Pred, LHS, RHS, L, CtxI, MaxIter))
11628 Pred, LHS, RHS, L, CtxI,
Op))
11630 return std::nullopt;
11633std::optional<ScalarEvolution::LoopInvariantPredicate>
11648 return std::nullopt;
11655 if (!AR || AR->
getLoop() != L)
11656 return std::nullopt;
11661 Pred = Pred.dropSameSign();
11665 return std::nullopt;
11671 if (Step != One && Step != MinusOne)
11672 return std::nullopt;
11678 return std::nullopt;
11684 return std::nullopt;
11692 if (Step == MinusOne)
11696 return std::nullopt;
11702bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11708 auto CheckRange = [&](
bool IsSigned) {
11711 return RangeLHS.
icmp(Pred, RangeRHS);
11720 if (CheckRange(
true) || CheckRange(
false))
11729bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11736 APInt &OutC2,
SCEVFlags ExpectedFlags) {
11737 SCEVUse XNonConstOp, XConstOp;
11738 SCEVUse YNonConstOp, YConstOp;
11742 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11745 XFlagsPresent = ExpectedFlags;
11750 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11753 YFlagsPresent = ExpectedFlags;
11756 if (YNonConstOp != XNonConstOp)
11764 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11767 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11827bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11848bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11849 const SCEV *
LHS,
const SCEV *
RHS) {
11854 return any_of(*BB, [&](
const Instruction &
I) {
11855 using namespace llvm::PatternMatch;
11860 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11874 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11879 "This cannot be done on broken IR!");
11882 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11891 if (LoopContinuePredicate &&
11892 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11893 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11898 if (WalkingBEDominatingConds)
11904 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11905 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11912 const SCEV *LoopCounter =
11920 for (
auto &AssumeVH : AC.assumptions()) {
11927 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11931 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11934 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11935 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11936 assert(DTN &&
"should reach the loop header before reaching the root!");
11939 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11957 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
11970 if (!DT.isReachableFromEntry(BB))
11974 "This cannot be done on broken IR!");
11982 const bool ProvingStrictComparison =
11984 bool ProvedNonStrictComparison =
false;
11985 bool ProvedNonEquality =
false;
11988 if (!ProvedNonStrictComparison)
11989 ProvedNonStrictComparison = Fn(NonStrictPredicate);
11990 if (!ProvedNonEquality)
11992 if (ProvedNonStrictComparison && ProvedNonEquality)
11997 if (ProvingStrictComparison) {
11999 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
12001 if (SplitAndProve(ProofFn))
12006 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
12008 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
12010 if (ProvingStrictComparison) {
12012 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
12014 if (SplitAndProve(ProofFn))
12023 const Loop *ContainingLoop = LI.getLoopFor(BB);
12025 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
12029 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
12030 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
12033 if (!BlockEntryPredicate)
12042 for (
auto &AssumeVH : AC.assumptions()) {
12046 if (!DT.dominates(CI, BB))
12049 if (ProveViaCond(CI->getArgOperand(0),
false))
12055 F.getParent(), Intrinsic::experimental_guard);
12057 for (
const auto *GU : GuardDecl->users())
12059 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12060 if (ProveViaCond(Guard->getArgOperand(0),
false))
12075 "LHS is not available at Loop Entry");
12077 "RHS is not available at Loop Entry");
12079 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12090 if (FoundCondValue ==
12094 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12098 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12101 const Value *Op0, *Op1;
12104 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12108 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12109 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12113 if (!ICI)
return false;
12117 CmpPredicate FoundPred;
12126 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12129bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12130 const SCEV *
RHS, CmpPredicate FoundPred,
12131 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12132 const Instruction *CtxI) {
12142 auto *WideType = FoundLHS->
getType();
12154 TruncFoundLHS, TruncFoundRHS, CtxI))
12180 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12184bool ScalarEvolution::isImpliedCondBalancedTypes(
12189 "Types should be balanced!");
12196 if (FoundLHS == FoundRHS)
12200 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12212 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12227 LHS, FoundLHS, FoundRHS, CtxI);
12229 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12236 assert(P1 != P2 &&
"Handled earlier!");
12240 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12244 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12247 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12248 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12249 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12254 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12265 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12266 CanonicalRHS, CanonicalFoundLHS,
12267 CanonicalFoundRHS);
12272 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12273 CanonicalRHS, CanonicalFoundLHS,
12274 CanonicalFoundRHS);
12281 const SCEVConstant *
C =
nullptr;
12282 const SCEV *
V =
nullptr;
12300 if (Min ==
C->getAPInt()) {
12305 APInt SharperMin = Min + 1;
12308 case ICmpInst::ICMP_SGE:
12309 case ICmpInst::ICMP_UGE:
12312 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12317 case ICmpInst::ICMP_SGT:
12318 case ICmpInst::ICMP_UGT:
12328 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12333 case ICmpInst::ICMP_SLE:
12334 case ICmpInst::ICMP_ULE:
12335 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12336 LHS, V, getConstant(SharperMin), CtxI))
12340 case ICmpInst::ICMP_SLT:
12341 case ICmpInst::ICMP_ULT:
12342 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12343 LHS, V, getConstant(Min), CtxI))
12357 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12361 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12364 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12380std::optional<APInt>
12387 APInt DiffMul(BW, 1);
12390 for (
unsigned I = 0;
I < 8; ++
I) {
12399 if (LAR->getLoop() != MAR->getLoop())
12400 return std::nullopt;
12404 if (!LAR->isAffine() || !MAR->isAffine())
12405 return std::nullopt;
12407 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12408 return std::nullopt;
12410 Less = LAR->getStart();
12411 More = MAR->getStart();
12416 auto MatchConstMul =
12417 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12422 return std::nullopt;
12424 if (
auto MatchedMore = MatchConstMul(More)) {
12425 if (
auto MatchedLess = MatchConstMul(
Less)) {
12426 if (MatchedMore->second == MatchedLess->second) {
12427 More = MatchedMore->first;
12428 Less = MatchedLess->first;
12429 DiffMul *= MatchedMore->second;
12440 Diff +=
C->getAPInt() * DiffMul;
12443 Diff -=
C->getAPInt() * DiffMul;
12446 Multiplicity[S] +=
Mul;
12448 auto Decompose = [&](
const SCEV *S,
int Mul) {
12455 Decompose(More, 1);
12456 Decompose(
Less, -1);
12460 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12461 for (
const auto &[S,
Mul] : Multiplicity) {
12466 return std::nullopt;
12468 }
else if (
Mul == -1) {
12470 return std::nullopt;
12473 return std::nullopt;
12477 if (NewMore == More || NewLess ==
Less)
12478 return std::nullopt;
12484 if (!More && !
Less)
12488 if (!More || !
Less)
12489 return std::nullopt;
12493 return std::nullopt;
12496bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12518 const auto *Latch = L->getLoopLatch();
12521 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12530 const auto *Latch = L->getLoopLatch();
12533 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12543bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12546 const SCEV *FoundLHS,
12547 const SCEV *FoundRHS) {
12556 if (!AddRecFoundLHS)
12563 const Loop *
L = AddRecFoundLHS->getLoop();
12564 if (L != AddRecLHS->getLoop())
12603 if (!RDiff || *LDiff != *RDiff)
12606 if (LDiff->isMinValue())
12609 APInt FoundRHSLimit;
12612 FoundRHSLimit = -(*RDiff);
12624bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12625 const SCEV *
RHS,
const SCEV *FoundLHS,
12626 const SCEV *FoundRHS,
unsigned Depth) {
12627 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12631 bool Erased = PendingMerges.erase(LPhi);
12632 assert(Erased &&
"Failed to erase LPhi!");
12636 bool Erased = PendingMerges.erase(RPhi);
12637 assert(Erased &&
"Failed to erase RPhi!");
12645 if (!PendingMerges.insert(Phi).second)
12659 if (!PendingMerges.insert(Phi).second)
12665 if (!LPhi && !RPhi)
12676 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12680 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12681 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12682 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12683 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12686 if (RPhi && RPhi->getParent() == LBB) {
12693 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12694 if (!ProvedEasily(L, R))
12705 auto *RLoop = RAR->
getLoop();
12706 auto *Predecessor = RLoop->getLoopPredecessor();
12707 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12709 if (!ProvedEasily(L1, RAR->
getStart()))
12711 auto *Latch = RLoop->getLoopLatch();
12712 assert(Latch &&
"Loop with AddRec with no latch?");
12733 if (
auto *
Loop = LI.getLoopFor(LBB))
12736 if (!ProvedEasily(L,
RHS))
12743bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12746 const SCEV *FoundLHS,
12747 const SCEV *FoundRHS) {
12750 if (
RHS == FoundRHS) {
12755 if (
LHS != FoundLHS)
12762 Value *Shiftee, *ShiftValue;
12764 using namespace PatternMatch;
12765 if (
match(SUFoundRHS->getValue(),
12767 auto *ShifteeS =
getSCEV(Shiftee);
12785bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12786 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12787 const SCEV *FoundRHS) {
12819 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12827 return Diff == FoundDiff;
12830bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12832 const SCEV *FoundLHS,
12833 const SCEV *FoundRHS,
12834 const Instruction *CtxI) {
12835 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12837 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12839 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12840 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12842 isImpliedCondOperandsViaMatchingDiff(Pred,
LHS,
RHS, FoundLHS,
12844 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12848template <
typename MinMaxExprType>
12850 const SCEV *Candidate) {
12855 return is_contained(MinMaxExpr->operands(), Candidate);
12868 const SCEV *LStart, *RStart, *Step;
12965bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12967 const SCEV *FoundLHS,
12968 const SCEV *FoundRHS,
12972 "LHS and RHS have different sizes?");
12975 "FoundLHS and FoundRHS have different sizes?");
13009 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
13011 return Ext->getOperand();
13018 auto *OrigLHS =
LHS;
13019 auto *OrigFoundLHS = FoundLHS;
13020 LHS = GetOpFromSExt(
LHS);
13021 FoundLHS = GetOpFromSExt(FoundLHS);
13024 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
13027 FoundRHS,
Depth + 1);
13040 if (!LHSAddExpr->hasNoSignedWrap())
13043 SCEVUse LL = LHSAddExpr->getOperand(0);
13044 SCEVUse LR = LHSAddExpr->getOperand(1);
13048 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
13049 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
13054 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
13060 using namespace llvm::PatternMatch;
13079 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13087 auto *DTy = Denominator->getType();
13088 auto *FRHSTy = FoundRHS->
getType();
13089 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13108 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13119 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13121 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13129 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13162bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13166 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13170 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13173bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13176 const SCEV *FoundLHS,
13177 const SCEV *FoundRHS) {
13213 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13219bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13220 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13221 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13235 ConstantRange FoundLHSRange =
13239 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13246 return LHSRange.
icmp(Pred, ConstRHS);
13249bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13250 bool IsSigned,
bool Invert) {
13257 APInt MaxRHS = getRangeMax(
RHS,
true, Invert);
13262 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13265 APInt MaxRHS = getRangeMax(
RHS,
false, Invert);
13270 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13283ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
const SCEV *Stride,
13285 bool IsSigned,
bool Invert) {
13300 APInt MinStart = getRangeMin(Start, IsSigned, Invert);
13313 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13319 APInt MaxEnd = getRangeMax(
End, IsSigned, Invert);
13325 :
APIntOps::umax(MaxEnd, MinStart);
13327 APInt Delta = MaxEnd - MinStart;
13331 const SCEV *DeltaExpr =
13339ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13340 const Loop *L,
bool IsSigned,
bool Invert,
13341 bool ControlsOnlyExit,
bool AllowPredicates) {
13345 std::optional<LoopGuards> CachedGuards;
13346 auto getGuards = [&]() ->
const LoopGuards & {
13349 return *CachedGuards;
13357 bool PredicatedIV =
false;
13359 if (!
IV && !Invert) {
13363 auto canProveNUW = [&]() {
13366 if (!ControlsOnlyExit)
13387 Limit = Limit.
zext(OuterBitWidth);
13400 Type *Ty = ZExt->getType();
13410 if (!
IV && AllowPredicates) {
13415 PredicatedIV =
true;
13419 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13433 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13440 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13443 const SCEV *GuardedStride = Stride;
13447 bool IVMayOverflow =
true;
13451 if (!PositiveStride) {
13452 const SCEV *LoopGuardedStride =
applyLoopGuards(Stride, getGuards());
13454 GuardedStride = LoopGuardedStride;
13455 PositiveStride =
true;
13462 if (!PositiveStride) {
13511 const SCEVPredicate *
P =
13532 auto wouldZeroStrideBeUB = [&]() {
13544 if (!wouldZeroStrideBeUB()) {
13551 IVMayOverflow = canIVOverflowOnLT(
RHS, GuardedStride, IsSigned, Invert);
13552 if (IVMayOverflow && !NoWrap)
13565 const SCEV *
Start =
IV->getStart();
13571 const SCEV *OrigStart =
Start;
13572 const SCEV *OrigRHS =
RHS;
13573 if (
Start->getType()->isPointerTy()) {
13587 assert(!Invert &&
"RHS must be loop-invariant for Invert");
13589 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13590 any(RHSAddRec->getNoWrapFlags())) {
13603 const SCEV *RHSStart = RHSAddRec->getStart();
13604 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13616 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13625 BECountIfBackedgeTaken =
13652 bool AddingStrideMinusOneMayOverflow = IVMayOverflow && [&] {
13699 if (!Invert && (Start == Stride || Start ==
getMinusSCEV(Stride, One))) {
13716 auto StepBack = [&](
const SCEV *
V,
const SCEV *
Offset) ->
const SCEV * {
13721 auto Distance = [&](
const SCEV *From,
const SCEV *To) {
13725 const SCEV *OrigPrevStart = StepBack(OrigStart, Stride);
13732 if ((!AddingStrideMinusOneMayOverflow ||
13764 const SCEV *Numerator =
13770 auto canProveRHSIsAtOrBeyondStart = [&]() {
13775 auto SwapIfInverted = [&](
const SCEV *
A,
const SCEV *
B) {
13776 return Invert ? std::pair(
B,
A) : std::pair(
A,
B);
13785 auto [GELHS, GERHS] = SwapIfInverted(OrigRHS, OrigStart);
13800 auto [GTLHS, GTRHS] = SwapIfInverted(OrigRHS, StepBack(OrigStart, One));
13806 if (canProveRHSIsAtOrBeyondStart()) {
13829 const SCEV *Delta = Distance(Start,
End);
13830 if (!AddingStrideMinusOneMayOverflow) {
13842 const SCEV *ConstantMaxBECount;
13843 bool MaxOrZero =
false;
13845 ConstantMaxBECount = BECount;
13847 ConstantMaxBECount = computeMaxBECountForLT(
13854 const APInt *IfTaken, *RangeMax;
13857 IfTaken->
ugt(*RangeMax)) {
13858 ConstantMaxBECount =
getZero(BECountIfBackedgeTaken->getType());
13860 ConstantMaxBECount = BECountIfBackedgeTaken;
13870 const SCEV *SymbolicMaxBECount =
13872 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13878 if (
Range.isFullSet())
13883 if (!SC->getValue()->isZero()) {
13889 return ShiftedAddRec->getNumIterationsInRange(
13890 Range.subtract(SC->getAPInt()), SE);
13934 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13935 "Linear scev computation is off in a bad way!");
13966 assert(!
Last->isZero() &&
"Recurrency with zero step?");
13999 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14001 SE->ConstantEvolutionLoopExitValue.erase(PN);
14002 SE->eraseValueFromMap(getValPtr());
14006void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
14007 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14017 : CallbackVH(
V), SE(se) {}
14026 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
14028 LoopDispositions(64), BlockDispositions(64) {
14040 F.getParent(), Intrinsic::experimental_guard);
14041 HasGuards = GuardDecl && !GuardDecl->use_empty();
14045 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
14046 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14047 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14048 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14049 PendingMerges(
std::
move(Arg.PendingMerges)),
14050 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14051 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14052 PredicatedBackedgeTakenCounts(
14053 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14054 BECountUsers(
std::
move(Arg.BECountUsers)),
14055 ConstantEvolutionLoopExitValue(
14056 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14057 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14058 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14059 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14060 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14061 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14062 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14063 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14064 SignedRanges(
std::
move(Arg.SignedRanges)),
14065 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14066 UniquePreds(
std::
move(Arg.UniquePreds)),
14067 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14068 ConstantSCEVs(
std::
move(Arg.ConstantSCEVs)),
14069 LoopUsers(
std::
move(Arg.LoopUsers)),
14070 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14071 FirstUnknown(Arg.FirstUnknown),
14072 NextUnknownOrderID(Arg.NextUnknownOrderID) {
14073 Arg.FirstUnknown =
nullptr;
14082 Tmp->~SCEVUnknown();
14084 FirstUnknown =
nullptr;
14086 ExprValueMap.clear();
14087 ValueExprMap.clear();
14089 BackedgeTakenCounts.clear();
14090 PredicatedBackedgeTakenCounts.clear();
14092 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14093 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14094 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14095 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14117 L->getHeader()->printAsOperand(OS,
false);
14121 L->getExitingBlocks(ExitingBlocks);
14122 if (ExitingBlocks.
size() != 1)
14123 OS <<
"<multiple exits> ";
14127 OS <<
"backedge-taken count is ";
14130 OS <<
"Unpredictable backedge-taken count.";
14133 if (ExitingBlocks.
size() > 1)
14134 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14135 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14143 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14146 OS <<
"\n Predicates:\n";
14147 for (
const auto *
P : Predicates)
14155 L->getHeader()->printAsOperand(OS,
false);
14160 OS <<
"constant max backedge-taken count is ";
14163 OS <<
", actual taken count either this or zero.";
14165 OS <<
"Unpredictable constant max backedge-taken count. ";
14170 L->getHeader()->printAsOperand(OS,
false);
14175 OS <<
"symbolic max backedge-taken count is ";
14178 OS <<
", actual taken count either this or zero.";
14180 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14184 if (ExitingBlocks.
size() > 1)
14185 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14186 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14196 OS <<
"\n predicated symbolic max exit count for "
14197 << ExitingBlock->
getName() <<
": ";
14199 OS <<
"\n Predicates:\n";
14200 for (
const auto *
P : Predicates)
14211 L->getHeader()->printAsOperand(OS,
false);
14214 OS <<
"Predicated backedge-taken count is ";
14217 OS <<
"Unpredictable predicated backedge-taken count.";
14219 OS <<
" Predicates:\n";
14220 for (
const auto *
P : Preds)
14225 auto *PredConstantMax =
14227 if (PredConstantMax != ConstantBTC) {
14229 L->getHeader()->printAsOperand(OS,
false);
14232 OS <<
"Predicated constant max backedge-taken count is ";
14235 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14237 OS <<
" Predicates:\n";
14238 for (
const auto *
P : Preds)
14243 auto *PredSymbolicMax =
14245 if (SymbolicBTC != PredSymbolicMax) {
14247 L->getHeader()->printAsOperand(OS,
false);
14250 OS <<
"Predicated symbolic max backedge-taken count is ";
14253 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14255 OS <<
" Predicates:\n";
14256 for (
const auto *
P : Preds)
14262 L->getHeader()->printAsOperand(OS,
false);
14289 OS <<
"Computable";
14299 OS <<
"DoesNotDominate";
14305 OS <<
"ProperlyDominates";
14322 OS <<
"Classifying expressions for: ";
14323 F.printAsOperand(OS,
false);
14338 const Loop *L = LI.getLoopFor(
I.getParent());
14353 OS <<
"\t\t" "Exits: ";
14356 OS <<
"<<Unknown>>";
14362 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14364 Iter->getHeader()->printAsOperand(OS,
false);
14372 InnerL->getHeader()->printAsOperand(OS,
false);
14383 OS <<
"Determining loop execution counts for: ";
14384 F.printAsOperand(OS,
false);
14392 auto &
Values = LoopDispositions[S];
14393 for (
auto &V :
Values) {
14394 if (V.getPointer() == L)
14399 auto &Values2 = LoopDispositions[S];
14401 if (V.getPointer() == L) {
14410ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14428 if (L->contains(AR->
getLoop()) &&
14430 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14435 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14436 " dominate the contained loop's header?");
14463 bool HasVarying =
false;
14464 bool HasUniform =
false;
14506 auto &
Values = BlockDispositions[S];
14507 for (
auto &V :
Values) {
14508 if (V.getPointer() == BB)
14513 auto &Values2 = BlockDispositions[S];
14515 if (V.getPointer() == BB) {
14524ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14553 bool Proper =
true;
14564 if (Instruction *
I =
14566 if (
I->getParent() == BB)
14568 if (DT.properlyDominates(
I->getParent(), BB))
14587void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14590 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14591 auto It = BECounts.find(L);
14592 if (It != BECounts.end()) {
14593 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14594 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14596 auto UserIt = BECountUsers.find(S);
14597 assert(UserIt != BECountUsers.end());
14602 BECounts.erase(It);
14610 while (!Worklist.
empty()) {
14612 auto Users = SCEVUsers.find(Curr);
14613 if (
Users != SCEVUsers.end())
14614 for (
const auto *User :
Users->second)
14615 if (ToForget.
insert(User).second)
14619 for (
const auto *S : ToForget)
14620 forgetMemoizedResultsImpl(S);
14622 PredicatedSCEVRewrites.remove_if(
14623 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14626void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14627 LoopDispositions.erase(S);
14628 BlockDispositions.erase(S);
14629 UnsignedRanges.erase(S);
14630 SignedRanges.erase(S);
14631 HasRecMap.erase(S);
14632 ConstantMultipleCache.erase(S);
14635 UnsignedWrapViaInductionTried.erase(AR);
14636 SignedWrapViaInductionTried.erase(AR);
14639 auto ExprIt = ExprValueMap.find(S);
14640 if (ExprIt != ExprValueMap.end()) {
14641 for (
Value *V : ExprIt->second) {
14642 auto ValueIt = ValueExprMap.find_as(V);
14643 if (ValueIt != ValueExprMap.end())
14644 ValueExprMap.erase(ValueIt);
14646 ExprValueMap.erase(ExprIt);
14649 auto ScopeIt = ValuesAtScopes.find(S);
14650 if (ScopeIt != ValuesAtScopes.end()) {
14651 for (
const auto &Pair : ScopeIt->second)
14653 llvm::erase(ValuesAtScopesUsers[Pair.second.getPointer()],
14654 std::make_pair(Pair.first, S));
14655 ValuesAtScopes.erase(ScopeIt);
14658 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14659 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14660 for (
const auto &Pair : ScopeUserIt->second)
14663 llvm::erase_if(ValuesAtScopes[Pair.second], [&](
const auto &LS) {
14664 return LS.first == Pair.first && LS.second.getPointer() == S;
14666 ValuesAtScopesUsers.erase(ScopeUserIt);
14669 auto BEUsersIt = BECountUsers.find(S);
14670 if (BEUsersIt != BECountUsers.end()) {
14672 auto Copy = BEUsersIt->second;
14673 for (
const auto &Pair : Copy)
14674 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14675 BECountUsers.erase(BEUsersIt);
14678 auto FoldUser = FoldCacheUser.find(S);
14679 if (FoldUser != FoldCacheUser.end())
14680 for (
auto &KV : FoldUser->second)
14681 FoldCache.erase(KV);
14682 FoldCacheUser.erase(S);
14686ScalarEvolution::getUsedLoops(
const SCEV *S,
14688 struct FindUsedLoops {
14689 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14690 : LoopsUsed(LoopsUsed) {}
14691 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14692 bool follow(
const SCEV *S) {
14698 bool isDone()
const {
return false; }
14701 FindUsedLoops
F(LoopsUsed);
14702 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14705void ScalarEvolution::getReachableBlocks(
14708 Worklist.
push_back(&F.getEntryBlock());
14709 while (!Worklist.
empty()) {
14711 if (!Reachable.
insert(BB).second)
14719 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14726 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14730 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14765 SCEVMapper SCM(SE2);
14767 SE2.getReachableBlocks(ReachableBlocks, F);
14769 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14787 while (!LoopStack.
empty()) {
14793 if (!ReachableBlocks.
contains(L->getHeader()))
14798 auto It = BackedgeTakenCounts.find(L);
14799 if (It == BackedgeTakenCounts.end())
14803 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14823 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14824 if (Delta && !Delta->
isZero()) {
14825 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14826 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14827 dbgs() <<
"New: " << *NewBECount <<
"\n";
14828 dbgs() <<
"Delta: " << *Delta <<
"\n";
14836 while (!Worklist.
empty()) {
14838 if (ValidLoops.
insert(L).second)
14839 Worklist.
append(L->begin(), L->end());
14841 for (
const auto &KV : ValueExprMap) {
14846 "AddRec references invalid loop");
14851 auto It = ExprValueMap.find(KV.second);
14852 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14853 dbgs() <<
"Value " << *KV.first
14854 <<
" is in ValueExprMap but not in ExprValueMap\n";
14859 if (!ReachableBlocks.
contains(
I->getParent()))
14861 const SCEV *OldSCEV = SCM.visit(KV.second);
14863 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14864 if (Delta && !Delta->
isZero()) {
14865 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14866 <<
"Old: " << *OldSCEV <<
"\n"
14867 <<
"New: " << *NewSCEV <<
"\n"
14868 <<
"Delta: " << *Delta <<
"\n";
14874 for (
const auto &KV : ExprValueMap) {
14875 for (
Value *V : KV.second) {
14876 const SCEV *S = ValueExprMap.lookup(V);
14878 dbgs() <<
"Value " << *V
14879 <<
" is in ExprValueMap but not in ValueExprMap\n";
14882 if (S != KV.first) {
14883 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14884 << *KV.first <<
"\n";
14891 for (
const auto &S : UniqueSCEVs) {
14896 auto It = SCEVUsers.find(
Op);
14897 if (It != SCEVUsers.end() && It->second.count(&S))
14899 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14900 <<
" is not being tracked!\n";
14906 for (
const auto &ValueAndVec : ValuesAtScopes) {
14908 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14909 const Loop *L = LoopAndValueAtScope.first;
14910 SCEVUse ValueAtScope = LoopAndValueAtScope.second;
14912 auto It = ValuesAtScopesUsers.find(ValueAtScope.
getPointer());
14913 if (It != ValuesAtScopesUsers.end() &&
14916 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14917 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14923 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14924 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14925 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14926 const Loop *L = LoopAndValue.first;
14927 const SCEV *
Value = LoopAndValue.second;
14929 auto It = ValuesAtScopes.find(
Value);
14932 if (It != ValuesAtScopes.end() &&
any_of(It->second, [&](
const auto &LS) {
14933 return LS.first == L && LS.second.getPointer() == ValueAtScope;
14936 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14937 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14943 auto VerifyBECountUsers = [&](
bool Predicated) {
14945 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14946 for (
const auto &LoopAndBEInfo : BECounts) {
14947 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14948 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14950 auto UserIt = BECountUsers.find(S);
14951 if (UserIt != BECountUsers.end() &&
14952 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14954 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14955 <<
" missing from BECountUsers\n";
14962 VerifyBECountUsers(
false);
14963 VerifyBECountUsers(
true);
14966 for (
auto &[S,
Values] : LoopDispositions) {
14967 for (
auto [
Loop, CachedDisposition] :
Values) {
14969 if (CachedDisposition != RecomputedDisposition) {
14970 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
14971 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
14972 << RecomputedDisposition <<
"\n";
14979 for (
auto &[S,
Values] : BlockDispositions) {
14980 for (
auto [BB, CachedDisposition] :
Values) {
14982 if (CachedDisposition != RecomputedDisposition) {
14983 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
14984 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
14985 <<
", actual " << RecomputedDisposition <<
"\n";
14992 for (
auto [
FoldID, Expr] : FoldCache) {
14993 auto I = FoldCacheUser.find(Expr);
14994 if (
I == FoldCacheUser.end()) {
14995 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
15000 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
15004 for (
auto [Expr, IDs] : FoldCacheUser) {
15005 for (
auto &
FoldID : IDs) {
15008 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
15013 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
15014 <<
" != " << *Expr <<
"!\n";
15025 for (
auto [S, Multiple] : ConstantMultipleCache) {
15027 if ((Multiple != 0 && RecomputedMultiple != 0 &&
15028 Multiple.
urem(RecomputedMultiple) != 0 &&
15029 RecomputedMultiple.
urem(Multiple) != 0)) {
15030 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
15031 << *S <<
" : Computed " << RecomputedMultiple
15032 <<
" but cache contains " << Multiple <<
"!\n";
15040 FunctionAnalysisManager::Invalidator &Inv) {
15072 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15073 <<
F.getName() <<
"':\n";
15079 "Scalar Evolution Analysis",
false,
true)
15128 const SCEV *LHS,
const SCEV *RHS) {
15130 assert(LHS->getType() == RHS->getType() &&
15131 "Type mismatch between LHS and RHS");
15134 ID.AddInteger(Pred);
15135 ID.AddPointer(LHS);
15136 ID.AddPointer(RHS);
15138 if (
const auto *S = UniquePreds.lookup(ID, Token))
15142 UniquePreds.insert(Eq, Token);
15153 ID.AddInteger(AddedFlags);
15155 if (
const auto *S = UniquePreds.lookup(ID, Token))
15157 auto *OF =
new (SCEVAllocator)
15159 UniquePreds.insert(OF, Token);
15179 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15180 return Rewriter.visit(S);
15186 for (
const auto *Pred : U->getPredicates())
15188 if (IPred->getLHS() == Expr &&
15190 return IPred->getRHS();
15192 if (IPred->getLHS() == Expr &&
15193 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15194 return IPred->getRHS();
15197 return convertToAddRecWithPreds(Expr);
15200 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15216 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15233 explicit SCEVPredicateRewriter(
15234 const Loop *L, ScalarEvolution &SE,
15235 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15236 const SCEVPredicate *Pred)
15237 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15239 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15242 return Pred && Pred->
implies(
P, SE);
15248 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15251 return addOverflowAssumption(
A);
15260 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15264 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15266 if (!PredicatedRewrite)
15268 for (
const auto *
P : PredicatedRewrite->second){
15271 if (L != WP->getExpr()->getLoop())
15274 if (!addOverflowAssumption(
P))
15277 return PredicatedRewrite->first;
15280 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15281 const SCEVPredicate *Pred;
15290 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15297 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15317 if (!Step->
isOne())
15342 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15343 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15356 return Op->LHS == LHS &&
Op->RHS == RHS;
15363 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15365 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15390 const SCEV *Start = AR->getStart();
15391 const SCEV *OpStart =
Op->AR->getStart();
15396 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15405 const SCEV *Step = AR->getStepRecurrence(SE);
15406 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15427 SCEVFlags ScevFlags = AR->getNoWrapFlags();
15449 for (
const auto *
P : Preds)
15462 return this->implies(I, SE);
15474 const Loop *L = NWrap->getExpr()->getLoop();
15481 return RewrittenAR &&
15487 for (
const auto *Pred : Preds)
15488 Pred->print(OS,
Depth);
15493 for (
const auto *Pred : Set->Preds)
15501 bool CheckImplies = Preds.
size() < 16;
15504 if (CheckImplies &&
implies(
N, SE))
15510 for (
auto *
P : Preds) {
15511 if (CheckImplies &&
N->implies(
P, SE))
15515 Preds = std::move(PrunedPreds);
15516 Preds.push_back(
N);
15523 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15532 SCEVUsers[
Op].insert(
User);
15536 const SCEV *Expr = SE.getSCEV(V);
15541 RewriteEntry &Entry = RewriteMap[Expr];
15544 if (Entry.second && Generation == Entry.first)
15545 return Entry.second;
15550 Expr = Entry.second;
15552 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15553 Entry = {Generation, NewSCEV};
15559 if (!BackedgeCount) {
15561 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15562 for (
const auto *
P : Preds)
15565 return BackedgeCount;
15569 if (!SymbolicMaxBackedgeCount) {
15571 SymbolicMaxBackedgeCount =
15572 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15573 for (
const auto *
P : Preds)
15576 return SymbolicMaxBackedgeCount;
15580 if (!SmallConstantMaxTripCount) {
15582 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15583 for (
const auto *
P : Preds)
15586 return *SmallConstantMaxTripCount;
15590 if (Preds->implies(&Pred, SE))
15595 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15596 updateGeneration();
15609void PredicatedScalarEvolution::updateGeneration() {
15611 if (++Generation == 0) {
15612 for (
auto &
II : RewriteMap) {
15613 const SCEV *Rewritten =
II.second.second;
15623 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15629 ExtraPreds->
append(NewPreds);
15635 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15641 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15644 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15648 for (
auto *BB : L.getBlocks())
15649 for (
auto &
I : *BB) {
15650 if (!SE.isSCEVable(
I.getType()))
15653 auto *Expr = SE.getSCEV(&
I);
15654 auto II = RewriteMap.find(Expr);
15656 if (
II == RewriteMap.end())
15660 if (
II->second.second == Expr)
15665 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15673 LoopGuards Guards(SE);
15681void ScalarEvolution::LoopGuards::collectFromPHI(
15689 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15690 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15704 auto &RewriteMap =
G->second.RewriteMap;
15705 if (RewriteMap.empty())
15707 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15708 if (S == RewriteMap.end())
15714 return {C0, SM->getSCEVType()};
15717 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15718 MinMaxPattern
P2) -> MinMaxPattern {
15719 auto [C1,
T1] =
P1;
15720 auto [C2, T2] =
P2;
15721 if (!C1 || !C2 ||
T1 != T2)
15725 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15727 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15729 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15731 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15736 auto P = GetMinMaxConst(0);
15737 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15740 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15743 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15746 Guards.RewriteMap.insert({
LHS,
RHS});
15754 const APInt &DivisorVal,
15756 const APInt *ExprVal;
15769 const APInt &DivisorVal,
15771 const APInt *ExprVal;
15779 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15793 const SCEV *URemRHS =
nullptr;
15797 const SCEV *Multiple =
15799 DivInfo[URemLHS] = Multiple;
15801 Multiples[URemLHS] =
C->getAPInt();
15821 auto IsMinMaxSCEVWithNonNegativeConstant =
15825 if (
MinMax->getNumOperands() != 2)
15828 if (
C->getAPInt().isNegative())
15830 SCTy =
MinMax->getSCEVType();
15839 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15841 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15846 auto *DivisibleExpr =
15854void ScalarEvolution::LoopGuards::collectFromBlock(
15856 const BasicBlock *
Block,
const BasicBlock *Pred,
15864 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15875 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15877 if (From == FromRewritten)
15879 RewriteMap[From] = To;
15885 auto GetMaybeRewritten = [&](
const SCEV *S) {
15886 return RewriteMap.lookup_or(S, S);
15893 const SCEV *MatchLHS,
15894 const SCEV *MatchRHS) {
15895 const SCEVConstant *C1;
15898 if (!
match(MatchLHS,
15910 const SCEV *RewrittenLHS = GetMaybeRewritten(LHSUnknown);
15911 ExactRegion = ExactRegion.intersectWith(SE.
getUnsignedRange(RewrittenLHS),
15916 if (ExactRegion.isEmptySet() || ExactRegion.isWrappedSet() ||
15917 ExactRegion.isFullSet())
15920 const SCEV *RegionMin = SE.
getConstant(ExactRegion.getUnsignedMin());
15921 const SCEV *RegionMax = SE.
getConstant(ExactRegion.getUnsignedMax());
15922 const SCEV *ClampedLHS =
15924 AddRewrite(LHSUnknown, RewrittenLHS, ClampedLHS);
15927 if (MatchRangeCheckIdiom(Predicate,
LHS,
RHS))
15940 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15942 const APInt &DividesBy =
15957 switch (Predicate) {
15986 SmallPtrSet<const SCEV *, 16> Visited;
15988 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
15992 while (!Worklist.
empty()) {
15996 if (!Visited.
insert(From).second)
15998 const SCEV *FromRewritten = GetMaybeRewritten(From);
15999 const SCEV *To =
nullptr;
16001 switch (Predicate) {
16006 EnqueueOperands(
UMax);
16012 EnqueueOperands(
SMax);
16018 EnqueueOperands(
UMin);
16024 EnqueueOperands(
SMin);
16032 const SCEV *OneAlignedUp =
16034 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16046 const SCEVConstant *
C;
16055 Guards.NotEqual.insert({
LHS,
RHS});
16064 AddRewrite(From, FromRewritten, To);
16081 SE.F.
getParent(), Intrinsic::experimental_guard);
16083 for (
const auto *GU : GuardDecl->users())
16085 if (Guard->getFunction() ==
Block->getParent() &&
16094 unsigned NumCollectedConditions = 0;
16096 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16098 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16100 const CondBrInst *LoopEntryPredicate =
16102 if (!LoopEntryPredicate)
16107 NumCollectedConditions++;
16111 if (
Depth > 0 && NumCollectedConditions == 2)
16119 if (Pair.second->hasNPredecessorsOrMore(2) &&
16121 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16122 for (
auto &Phi : Pair.second->phis())
16133 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16134 SmallVector<Value *, 8> Worklist;
16135 SmallPtrSet<Value *, 8> Visited;
16137 while (!Worklist.
empty()) {
16144 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16168 DenseMap<const SCEV *, APInt> Multiples;
16170 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16177 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16178 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16182 for (
const auto &[K, Divisor] : Multiples) {
16183 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16184 Guards.RewriteMap[
K] =
16186 Guards.
rewrite(K), Divisor, SE),
16195 Guards.PreserveNUW =
true;
16196 Guards.PreserveNSW =
true;
16197 for (
const SCEV *Expr : ExprsToRewrite) {
16198 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16199 Guards.PreserveNUW &=
16201 Guards.PreserveNSW &=
16208 if (ExprsToRewrite.size() > 1) {
16209 for (
const SCEV *Expr : ExprsToRewrite) {
16210 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16211 Guards.RewriteMap.erase(Expr);
16212 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16221 class SCEVLoopGuardRewriter
16232 NotEqual(Guards.NotEqual) {
16233 if (Guards.PreserveNUW)
16235 if (Guards.PreserveNSW)
16242 return Map.lookup_or(Expr, Expr);
16246 if (
const SCEV *S = Map.lookup(Expr))
16253 if (
const SCEV *S = Map.lookup(Expr))
16260 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16261 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16262 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16264 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16265 if (
const SCEV *S = Map.lookup(NarrowExt))
16266 return SE.getZeroExtendExpr(S, Ty);
16267 Bitwidth = Bitwidth / 2;
16275 if (
const SCEV *S = Map.lookup(Expr))
16282 if (
const SCEV *S = Map.lookup(Expr))
16288 if (
const SCEV *S = Map.lookup(Expr))
16294 if (
const SCEV *S = Map.lookup(Expr))
16299 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16304 if (NotEqual.contains({LHS, RHS})) {
16306 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16307 return SE.getUMaxExpr(OneAlignedUp, S);
16314 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16325 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16326 return SE.getAddExpr(
16329 if (
const SCEV *S = Map.lookup(
Add))
16330 return SE.getAddExpr(Expr->
getOperand(0), S);
16338 const SCEV *S =
nullptr;
16345 S = Map.lookup(SE.getAddExpr(NewC, Expr->
getOperand(1)));
16348 return SE.getAddExpr(S, SE.getMinusOne(Expr->
getType()));
16383 if (RewriteMap.empty() && NotEqual.empty())
16386 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16387 return Rewriter.visit(Expr);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Expand Atomic instructions
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
static bool isSigned(unsigned Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
Value * getPointer(Value *Ptr)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This defines the Use class.
iv Induction Variable Users
static bool hasNoUnsignedWrap(BinaryOperator &I)
static constexpr Value * getValue(Ty &ValueOrUse)
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
PowerPC Reduce CR logical Operation
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
const SmallVectorImpl< MachineOperand > & Cond
static DominatorTree getDomTree(Function &F)
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
SI optimize exec mask operations pre RA
static void visit(BasicBlock &Start, std::function< bool(BasicBlock *)> op)
This file provides utility classes that use RAII to save and restore values.
bool SCEVMinMaxExprContains(const SCEV *Root, const SCEV *OperandToFind, SCEVTypes RootKind)
static cl::opt< unsigned > MaxAddRecSize("scalar-evolution-max-add-rec-size", cl::Hidden, cl::desc("Max coefficients in AddRec during evolving"), cl::init(8))
static cl::opt< unsigned > RangeIterThreshold("scev-range-iter-threshold", cl::Hidden, cl::desc("Threshold for switching to iteratively computing SCEV ranges"), cl::init(32))
static const Loop * isIntegerLoopHeaderPHI(const PHINode *PN, LoopInfo &LI)
static unsigned getConstantTripCount(const SCEVConstant *ExitCount)
static int CompareValueComplexity(const LoopInfo *const LI, Value *LV, Value *RV, unsigned Depth)
Compare the two values LV and RV in terms of their "complexity" where "complexity" is a partial (and ...
static const SCEV * getNextSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static void PushLoopPHIs(const Loop *L, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push PHI nodes in the header of the given loop onto the given Worklist.
static void insertFoldCacheEntry(const ScalarEvolution::FoldID &ID, const SCEV *S, DenseMap< ScalarEvolution::FoldID, const SCEV * > &FoldCache, DenseMap< const SCEV *, SmallVector< ScalarEvolution::FoldID, 2 > > &FoldCacheUser)
static cl::opt< bool > ClassifyExpressions("scalar-evolution-classify-expressions", cl::Hidden, cl::init(true), cl::desc("When printing analysis, include information on every instruction"))
static bool hasHugeExpression(ArrayRef< SCEVUse > Ops)
Returns true if Ops contains a huge SCEV (the subtree of S contains at least HugeExprThreshold nodes)...
static cl::opt< unsigned > AddOpsInlineThreshold("scev-addops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining addition operands into a SCEV"), cl::init(500))
static cl::opt< unsigned > MaxLoopGuardCollectionDepth("scalar-evolution-max-loop-guard-collection-depth", cl::Hidden, cl::desc("Maximum depth for recursive loop guard collection"), cl::init(1))
static cl::opt< bool > VerifyIR("scev-verify-ir", cl::Hidden, cl::desc("Verify IR correctness when making sensitive SCEV queries (slow)"), cl::init(false))
static bool RangeRefPHIAllowedOperands(DominatorTree &DT, PHINode *PHI)
static bool IsKnownPredicateViaAddRecMonotonicity(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Is LHS Pred RHS true because one of them is an AddRec that is known not to go below its own start val...
static std::optional< APInt > MinOptional(std::optional< APInt > X, std::optional< APInt > Y)
Helper function to compare optional APInts: (a) if X and Y both exist, return min(X,...
static PHINode * getConstantEvolvingPHI(Value *V, const Loop *L, const TargetLibraryInfo *TLI)
getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node in the loop that V is deri...
static bool canConstantFold(const Instruction *I, const TargetLibraryInfo *TLI)
Return true if we can constant fold an instruction of the specified type, assuming that all operands ...
static cl::opt< unsigned > MulOpsInlineThreshold("scev-mulops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining multiplication operands into a SCEV"), cl::init(32))
static BinaryOperator * getCommonInstForPHI(PHINode *PN)
static PHINode * getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L, DenseMap< Instruction *, PHINode * > &PHIMap, const TargetLibraryInfo *TLI, unsigned Depth)
getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by recursing through each instructi...
static bool isDivisibilityGuard(const SCEV *LHS, const SCEV *RHS, ScalarEvolution &SE)
static std::optional< const SCEV * > createNodeForSelectViaUMinSeq(ScalarEvolution *SE, const SCEV *CondExpr, const SCEV *TrueExpr, const SCEV *FalseExpr)
static Constant * BuildConstantFromSCEV(const SCEV *V)
This builds up a Constant using the ConstantExpr interface.
static ConstantInt * EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C, ScalarEvolution &SE)
static const SCEV * BinomialCoefficient(const SCEV *It, unsigned K, ScalarEvolution &SE, Type *ResultTy)
Compute BC(It, K). The result has width W. Assume, K > 0.
static cl::opt< unsigned > MaxCastDepth("scalar-evolution-max-cast-depth", cl::Hidden, cl::desc("Maximum depth of recursive SExt/ZExt/Trunc"), cl::init(8))
static bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr, const SCEV *Candidate)
Is MaybeMinMaxExpr an (U|S)(Min|Max) of Candidate and some other values?
static SCEVFlags getNoWrapFlagsForGEP(GEPOperator *GEP, const SCEV *Accum, ScalarEvolution &SE)
static const SCEV * SolveLinEquationWithOverflow(const APInt &A, const SCEV *B, SmallVectorImpl< const SCEVPredicate * > *Predicates, ScalarEvolution &SE, const Loop *L)
Finds the minimum unsigned root of the following equation:
static cl::opt< unsigned > MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, cl::desc("Maximum number of iterations SCEV will " "symbolically execute a constant " "derived loop"), cl::init(100))
static uint64_t umul_ov(uint64_t i, uint64_t j, bool &Overflow)
static void PrintSCEVWithTypeHint(raw_ostream &OS, const SCEV *S)
When printing a top-level SCEV for trip counts, it's helpful to include a type for constants which ar...
static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE, const Loop *L)
static bool containsConstantInAddMulChain(const SCEV *StartExpr)
Determine if any of the operands in this SCEV are a constant or if any of the add or multiply express...
static const SCEV * getExtendAddRecStart(const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE, unsigned Depth)
static bool CollectAddOperandsWithScales(SmallDenseMap< SCEVUse, APInt, 16 > &M, SmallVectorImpl< SCEVUse > &NewOps, APInt &AccumulatedConstant, ArrayRef< SCEVUse > Ops, const APInt &Scale, ScalarEvolution &SE)
Process the given Ops list, which is a list of operands to be added under the given scale,...
static const SCEV * constantFoldAndGroupOps(ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT, SmallVectorImpl< SCEVUse > &Ops, FoldT Fold, IsIdentityT IsIdentity, IsAbsorberT IsAbsorber)
Performs a number of common optimizations on the passed Ops.
static bool IsKnownPredicateViaAddRecStart(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
static const SCEV * getPreStartForExtend(const SCEVAddRecExpr *AR, ScalarEvolution *SE, unsigned Depth)
static void GroupByComplexity(SmallVectorImpl< SCEVUse > &Ops, LoopInfo *LI, DominatorTree &DT)
Given a list of SCEV objects, order them by their complexity, and group objects of the same complexit...
static bool collectDivisibilityInformation(ICmpInst::Predicate Predicate, const SCEV *LHS, const SCEV *RHS, DenseMap< const SCEV *, const SCEV * > &DivInfo, DenseMap< const SCEV *, APInt > &Multiples, ScalarEvolution &SE)
static cl::opt< unsigned > MaxSCEVOperationsImplicationDepth("scalar-evolution-max-scev-operations-implication-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV operations implication analysis"), cl::init(2))
static void PushDefUseChildren(Instruction *I, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push users of the given Instruction onto the given Worklist.
static std::optional< APInt > SolveQuadraticAddRecRange(const SCEVAddRecExpr *AddRec, const ConstantRange &Range, ScalarEvolution &SE)
Let c(n) be the value of the quadratic chrec {0,+,M,+,N} after n iterations.
static cl::opt< bool > UseContextForNoWrapFlagInference("scalar-evolution-use-context-for-no-wrap-flag-strenghening", cl::Hidden, cl::desc("Infer nuw/nsw flags using context where suitable"), cl::init(true))
static cl::opt< bool > EnableFiniteLoopControl("scalar-evolution-finite-loop", cl::Hidden, cl::desc("Handle <= and >= in finite loops"), cl::init(true))
static bool getOperandsForSelectLikePHI(DominatorTree &DT, PHINode *PN, Value *&Cond, Value *&LHS, Value *&RHS)
static std::optional< std::tuple< APInt, APInt, APInt, APInt, unsigned > > GetQuadraticEquation(const SCEVAddRecExpr *AddRec)
For a given quadratic addrec, generate coefficients of the corresponding quadratic equation,...
static bool isKnownPredicateExtendIdiom(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
static std::optional< APInt > SolveQuadraticAddRecExact(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE)
Let c(n) be the value of the quadratic chrec {L,+,M,+,N} after n iterations.
static std::optional< APInt > TruncIfPossible(std::optional< APInt > X, unsigned BitWidth)
Helper function to truncate an optional APInt to a given BitWidth.
static 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()
static LLVM_ABI LoopGuards collect(const Loop *L, ScalarEvolution &SE)
Collect rewrite map for loop guards for loop L, together with flags indicating if NUW and NSW can be ...
LLVM_ABI const SCEV * rewrite(const SCEV *Expr) const
Try to apply the collected loop guards to Expr.
The main scalar evolution driver.
LLVM_ABI const SCEV * getUDivExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
LLVM_ABI bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
LLVM_ABI bool isKnownOnEveryIteration(CmpPredicate Pred, const SCEVAddRecExpr *LHS, const SCEV *RHS)
Test if the condition described by Pred, LHS, RHS is known to be true on every iteration of the loop ...
static bool hasFlags(SCEVFlags Flags, SCEVFlags TestFlags)
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterationsImpl(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
LLVM_ABI const SCEV * getZeroExtendExpr(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEV * getUDivCeilSCEV(const SCEV *N, const SCEV *D)
Compute ceil(N / D).
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterations(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L at given Context duri...
LLVM_ABI Type * getWiderType(Type *Ty1, Type *Ty2) const
LLVM_ABI const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)
LLVM_ABI bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
LLVM_ABI const SCEV * getElementCount(Type *Ty, ElementCount EC, SCEVFlags Flags=SCEV::FlagNone)
LLVM_ABI bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
LLVM_ABI const SCEV * getPredicatedConstantMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getConstantMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
LLVM_ABI bool isLoopEntryGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
LLVM_ABI bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
LLVM_ABI const SCEV * getURemExpr(SCEVUse LHS, SCEVUse RHS)
Represents an unsigned remainder expression based on unsigned division.
LLVM_ABI const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
LLVM_ABI const SCEV * getSMinExpr(SCEVUse LHS, SCEVUse RHS)
LLVM_ABI const SCEV * getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS)
Promote the operands to the wider of the types using zero-extension, and then perform a umax operatio...
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
LLVM_ABI bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?
LLVM_ABI const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEVFlags Flags=SCEV::FlagNone, unsigned Depth=0)
Return LHS-RHS.
LLVM_ABI ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsOnlyExit, bool AllowPredicates=false)
Compute the number of times the backedge of the specified loop will execute if its exit condition wer...
LLVM_ABI const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &Operands)
LLVM_ABI const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
LLVM_ABI SCEVUse getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
LLVM_ABI uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
LLVM_ABI void registerUser(const SCEV *User, ArrayRef< SCEVUse > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
LLVM_ABI const SCEV * getConstant(ConstantInt *V)
LLVM_ABI const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
LLVM_ABI const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
static SCEVFlags setFlags(SCEVFlags Flags, SCEVFlags OnFlags)
static LLVM_ABI bool isGuaranteedNotToBePoison(const SCEV *Op)
Returns true if Op is guaranteed to not be poison.
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
LLVM_ABI const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
LLVM_ABI ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI)
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LLVM_ABI const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI void forgetValues(ArrayRef< Value * > Values)
Batched forgetValue: invalidates all Values in one shared def-use walk, avoiding the redundant re-tra...
LLVM_ABI const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &Operands)
LLVM_ABI const SCEV * getCastExpr(SCEVTypes Kind, SCEVUse Op, Type *Ty)
LLVM_ABI std::optional< bool > evaluatePredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Check whether the condition described by Pred, LHS, and RHS is true or false in the given Context.
LLVM_ABI SCEVUse getAddRecExpr(SCEVUse Start, SCEVUse Step, const Loop *L, SCEVFlagsPair Flags)
Get an add recurrence expression for the specified loop.
LLVM_ABI unsigned getSmallConstantMaxTripCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Returns the upper bound of the loop trip count as a normal unsigned value.
LLVM_ABI bool isKnownMultipleOf(const SCEV *S, uint64_t M, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Check that S is a multiple of M.
LLVM_ABI bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
LLVM_ABI void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
LLVM_ABI bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
LLVM_ABI bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
LLVM_ABI bool SimplifyICmpOperands(CmpPredicate &Pred, SCEVUse &LHS, SCEVUse &RHS, unsigned Depth=0)
Simplify LHS and RHS in a comparison with predicate Pred.
APInt getUnsignedRangeMin(const SCEV *S)
Determine the min of the unsigned range for a particular SCEV.
static SCEVFlags clearFlags(SCEVFlags Flags, SCEVFlags OffFlags)
LLVM_ABI const SCEV * getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo)
Return an expression for offsetof on the given field with type IntTy.
LLVM_ABI LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
static SCEVFlags maskFlags(SCEVFlags Flags, SCEVFlags Mask)
Convenient SCEVFlags manipulation.
LLVM_ABI bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
LLVM_ABI const SCEV * getTruncateExpr(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI SCEVUse getAddExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlagsPair Flags={}, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
LLVM_ABI const SCEV * getZeroExtendExprImpl(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
LLVM_ABI Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
LLVM_ABI const SCEVPredicate * getComparePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
LLVM_ABI bool haveSameSign(const SCEV *S1, const SCEV *S2)
Return true if we know that S1 and S2 must have the same sign.
LLVM_ABI const SCEV * getNotSCEV(const SCEV *V)
Return the SCEV object corresponding to ~V.
LLVM_ABI bool instructionCouldExistWithOperands(const SCEV *A, const SCEV *B)
Return true if there exists a point in the program at which both A and B could be operands to the sam...
LLVM_ABI std::optional< SCEVFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
LLVM_ABI void print(raw_ostream &OS) const
LLVM_ABI const SCEV * getAnyExtendExpr(SCEVUse Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
LLVM_ABI const SCEV * getPredicatedExitCount(const Loop *L, const BasicBlock *ExitingBlock, SmallVectorImpl< const SCEVPredicate * > *Predicates, ExitCountKind Kind=Exact)
Same as above except this uses the predicated backedge taken info and may require predicates.
LLVM_ABI void forgetTopmostLoop(const Loop *L)
LLVM_ABI void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
APInt getSignedRangeMin(const SCEV *S)
Determine the min of the signed range for a particular SCEV.
LLVM_ABI bool isLoopUniform(const SCEV *S, const Loop *L)
Returns true if the given SCEV is loop-uniform with respect to the specified loop L.
LLVM_ABI const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
LLVM_ABI const SCEV * getSignExtendExpr(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEV * getUMaxExpr(SCEVUse LHS, SCEVUse RHS)
@ MonotonicallyDecreasing
@ MonotonicallyIncreasing
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI=nullptr)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L, return a LoopInvaria...
LLVM_ABI const SCEV * getStoreSizeOfExpr(Type *IntTy, Type *StoreTy)
Return an expression for the store size of StoreTy that is type IntTy.
LLVM_ABI const SCEVPredicate * getWrapPredicate(const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
LLVM_ABI bool isLoopBackedgeGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether the backedge of the loop is protected by a conditional between LHS and RHS.
LLVM_ABI APInt getNonZeroConstantMultiple(const SCEV *S)
const SCEV * getMinusOne(Type *Ty)
Return a SCEV for the constant -1 of a specific type.
LLVM_ABI bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
LLVM_ABI BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB)
Return the "disposition" of the given SCEV with respect to the given block.
LLVM_ABI const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
LLVM_ABI const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
Promote the operands to the wider of the types using zero-extension, and then perform a umin operatio...
LLVM_ABI bool loopIsFiniteByAssumption(const Loop *L)
Return true if this loop is finite by assumption.
LLVM_ABI SCEVUse getSCEVAtExit(const SCEV *S, const Loop *L, const BasicBlock *ExitingBlock)
Return the SCEV expression at the specified loop exit.
LLVM_ABI const SCEV * getExistingSCEV(Value *V)
Return an existing SCEV for V if there is one, otherwise return nullptr.
LLVM_ABI APInt getConstantMultiple(const SCEV *S, const Instruction *CtxI=nullptr)
Returns the max constant multiple of S.
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
@ LoopComputable
The SCEV varies predictably with the loop.
@ LoopVariant
The SCEV is loop-variant (unknown).
@ LoopInvariant
The SCEV is loop-invariant.
@ LoopUniform
The SCEV is loop-uniform.
friend class SCEVCallbackVH
LLVM_ABI bool isKnownToBeAPowerOfTwo(const SCEV *S, bool OrZero=false, bool OrNegative=false)
Test if the given expression is known to be a power of 2.
LLVM_ABI void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)
Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...
LLVM_ABI bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
LLVM_ABI std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
LLVM_ABI const SCEV * getCouldNotCompute()
LLVM_ABI bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
LLVM_ABI uint32_t getMinTrailingZeros(const SCEV *S, const Instruction *CtxI=nullptr)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
@ DominatesBlock
The SCEV dominates the block.
@ ProperlyDominatesBlock
The SCEV properly dominates the block.
@ DoesNotDominateBlock
The SCEV does not dominate the block.
LLVM_ABI const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
LLVM_ABI void getPoisonGeneratingValues(SmallPtrSetImpl< const Value * > &Result, const SCEV *S)
Return the set of Values that, if poison, will definitively result in S being poison as well.
LLVM_ABI void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEVFlags Flags)
Update no-wrap flags of an AddRec.
LLVM_ABI void forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
LLVM_ABI const SCEV * getVScale(Type *Ty)
LLVM_ABI SCEVUse getMulExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlagsPair Flags={}, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
LLVM_ABI unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
LLVM_ABI bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
LLVM_ABI const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
LLVM_ABI void forgetAllLoops()
LLVM_ABI const SCEV * getSignExtendExprImpl(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
APInt getUnsignedRangeMax(const SCEV *S)
Determine the max of the unsigned range for a particular SCEV.
ExitCountKind
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of ...
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
@ ConstantMaximum
A constant which provides an upper bound on the exact trip count.
@ Exact
An expression exactly describing the number of times the backedge has executed when a loop is exited.
LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
LLVM_ABI const SCEV * getPtrToAddrExpr(const SCEV *Op)
LLVM_ABI const SCEVAddRecExpr * convertSCEVToAddRecWithPredicates(const SCEV *S, const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Preds)
Tries to convert the S expression to an AddRec expression, adding additional predicates to Preds as r...
LLVM_ABI const SCEV * getSMaxExpr(SCEVUse LHS, SCEVUse RHS)
LLVM_ABI const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
LLVM_ABI const SCEV * getSizeOfExpr(Type *IntTy, TypeSize Size)
Return an expression for a TypeSize.
LLVM_ABI std::optional< bool > evaluatePredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Check whether the condition described by Pred, LHS, and RHS is true or false.
LLVM_ABI const SCEV * getUnknown(Value *V)
LLVM_ABI std::optional< std::pair< const SCEV *, SmallVector< const SCEVPredicate *, 3 > > > createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI)
Checks if SymbolicPHI can be rewritten as an AddRecExpr under some Predicates.
LLVM_ABI const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool isKnownViaInduction(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
We'd like to check the predicate on every iteration of the most dominated loop between loops used in ...
LLVM_ABI std::optional< APInt > computeConstantDifference(const SCEV *LHS, const SCEV *RHS)
Compute LHS - RHS and returns the result as an APInt if it is a constant, and std::nullopt if it isn'...
LLVM_ABI bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEVFlags Flags=SCEV::FlagNone)
Return the SCEV object corresponding to -V.
LLVM_ABI const SCEV * getUDivExactExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
LLVM_ABI const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
LLVM_ABI std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
LLVM_ABI bool canReuseInstruction(const SCEV *S, Instruction *I, SmallVectorImpl< Instruction * > &DropPoisonGeneratingInsts)
Check whether it is poison-safe to represent the expression S using the instruction I.
LLVM_ABI bool isKnownPredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * getPredicatedSymbolicMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getSymbolicMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI ~ScalarEvolution()
LLVM_ABI const SCEV * getGEPExpr(GEPOperator *GEP, ArrayRef< SCEVUse > IndexExprs)
Returns an expression for a GEP.
LLVM_ABI const SCEV * getUMinExpr(SCEVUse LHS, SCEVUse RHS, bool Sequential=false)
LLVM_ABI bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the basic block is protected by a conditional between LHS and RHS.
LLVM_ABI const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool containsErasedValue(const SCEV *S) const
Return true if the SCEV expression contains a Value that has been optimised out and is now a nullptr.
const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
LLVM_ABI void verify() const
LLVMContext & getContext() const
This class represents the LLVM 'select' instruction.
Implements a dense probed hash-table based set with some number of buckets stored inline.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
TypeSize getElementOffset(unsigned Idx) const
TypeSize getSizeInBits() const
Class to represent struct types.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
static LLVM_ABI IntegerType * getIntNTy(LLVMContext &C, unsigned N)
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< user_iterator > users()
unsigned getValueID() const
Return an ID for the concrete type of this object.
LLVM_ABI void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
LLVM_ABI std::optional< APInt > SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, unsigned RangeWidth)
Let q(n) = An^2 + Bn + C, and BW = bit width of the value range (e.g.
LLVM_ABI APInt GreatestCommonDivisor(APInt A, APInt B, bool IsSigned=false)
Compute GCD of two APInt values.
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
constexpr bool any(E Val)
@ BasicBlock
Various leaf nodes.
LLVM_ABI Function * getDeclarationIfExists(const Module *M, ID id)
Look up the Function declaration of the intrinsic id in the Module M and return it if it exists.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
auto m_BasicBlock()
Match an arbitrary basic block value and ignore it.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
auto m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
match_bind< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
brc_match< Cond_t, match_bind< BasicBlock >, match_bind< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
CastOperator_match< OpTy, Instruction::PtrToInt > m_PtrToInt(const OpTy &Op)
Matches PtrToInt.
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
bind_cst_ty m_scev_APInt(const APInt *&C)
Match an SCEV constant and bind it to an APInt.
cst_pred_ty< is_all_ones > m_scev_AllOnes()
Match an integer with all bits set.
SCEVUnaryExpr_match< SCEVZeroExtendExpr, Op0_t > m_scev_ZExt(const Op0_t &Op0)
is_undef_or_poison m_scev_UndefOrPoison()
Match an SCEVUnknown wrapping undef or poison.
cst_pred_ty< is_one > m_scev_One()
Match an integer 1.
specificloop_ty m_SpecificLoop(const Loop *L)
SCEVUnaryExpr_match< SCEVSignExtendExpr, Op0_t > m_scev_SExt(const Op0_t &Op0)
match_bind< const SCEVMulExpr > m_scev_Mul(const SCEVMulExpr *&V)
cst_pred_ty< is_zero > m_scev_Zero()
Match an integer 0.
SCEVUnaryExpr_match< SCEVTruncateExpr, Op0_t > m_scev_Trunc(const Op0_t &Op0)
bool match(const SCEV *S, const Pattern &P)
SCEVBinaryExpr_match< SCEVUDivExpr, Op0_t, Op1_t > m_scev_UDiv(const Op0_t &Op0, const Op1_t &Op1)
specificscev_ty m_scev_Specific(const SCEV *S)
Match if we have a specific specified SCEV.
SCEVAffineAddRec_match< Op0_t, Op1_t, match_isa< const Loop > > m_scev_AffineAddRec(const Op0_t &Op0, const Op1_t &Op1)
match_bind< const SCEVUnknown > m_SCEVUnknown(const SCEVUnknown *&V)
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagNUW, true > m_scev_c_NUWMul(const Op0_t &Op0, const Op1_t &Op1)
SCEVBinaryExpr_match< SCEVSMaxExpr, Op0_t, Op1_t, SCEV::FlagNone, true > m_scev_SMax(const Op0_t &Op0, const Op1_t &Op1)
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagNone, true > m_scev_c_Mul(const Op0_t &Op0, const Op1_t &Op1)
match_bind< const SCEVAddExpr > m_scev_Add(const SCEVAddExpr *&V)
SCEVURem_match< Op0_t, Op1_t > m_scev_URem(Op0_t LHS, Op1_t RHS, ScalarEvolution &SE)
Match the mathematical pattern A - (A / B) * B, where A and B can be arbitrary expressions.
@ Valid
The data is already valid.
initializer< Ty > init(const Ty &Val)
LocationClass< Ty > location(Ty &L)
@ Switch
The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...
NodeAddr< PhiNode * > Phi
friend class Instruction
Iterator for Instructions in a `BasicBlock.
unsigned getOpcode(const VPValue *V)
Return the instruction opcode for the recipe defining V or 0 for unsupported recipes and VPValues not...
This is an optimization pass for GlobalISel generic memory operations.
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
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