83#include "llvm/Config/llvm-config.h"
138#define DEBUG_TYPE "scalar-evolution"
141 "Number of loop exits with predictable exit counts");
143 "Number of loop exits without predictable exit counts");
145 "Number of loops with trip counts computed by force");
147#ifdef EXPENSIVE_CHECKS
155 cl::desc(
"Maximum number of iterations SCEV will "
156 "symbolically execute a constant "
162 cl::desc(
"Verify ScalarEvolution's backedge taken counts (slow)"));
165 cl::desc(
"Enable stricter verification with -verify-scev is passed"));
169 cl::desc(
"Verify IR correctness when making sensitive SCEV queries (slow)"),
174 cl::desc(
"Threshold for inlining multiplication operands into a SCEV"),
179 cl::desc(
"Threshold for inlining addition operands into a SCEV"),
183 "scalar-evolution-max-scev-compare-depth",
cl::Hidden,
184 cl::desc(
"Maximum depth of recursive SCEV complexity comparisons"),
188 "scalar-evolution-max-scev-operations-implication-depth",
cl::Hidden,
189 cl::desc(
"Maximum depth of recursive SCEV operations implication analysis"),
193 "scalar-evolution-max-value-compare-depth",
cl::Hidden,
194 cl::desc(
"Maximum depth of recursive value complexity comparisons"),
199 cl::desc(
"Maximum depth of recursive arithmetics"),
203 "scalar-evolution-max-constant-evolving-depth",
cl::Hidden,
208 cl::desc(
"Maximum depth of recursive SExt/ZExt/Trunc"),
213 cl::desc(
"Max coefficients in AddRec during evolving"),
218 cl::desc(
"Size of the expression which is considered huge"),
223 cl::desc(
"Threshold for switching to iteratively computing SCEV ranges"),
227 "scalar-evolution-max-loop-guard-collection-depth",
cl::Hidden,
228 cl::desc(
"Maximum depth for recursive loop guard collection"),
cl::init(1));
233 cl::desc(
"When printing analysis, include information on every instruction"));
236 "scalar-evolution-use-expensive-range-sharpening",
cl::Hidden,
238 cl::desc(
"Use more powerful methods of sharpening expression ranges. May "
239 "be costly in terms of compile time"));
243 cl::desc(
"Handle <= and >= in finite loops"),
247 "scalar-evolution-use-context-for-no-wrap-flag-strenghening",
cl::Hidden,
248 cl::desc(
"Infer nuw/nsw flags using context where suitable"),
290#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
308 OS <<
"(ptrtoaddr " << *
Op->getType() <<
" " <<
Op <<
" to "
315 OS <<
"(trunc " << *
Op->getType() <<
" " <<
Op <<
" to "
322 OS <<
"(zext " << *
Op->getType() <<
" " <<
Op <<
" to " << *ZExt->
getType()
329 OS <<
"(sext " << *
Op->getType() <<
" " <<
Op <<
" to " << *SExt->
getType()
358 const char *OpStr =
nullptr;
371 OpStr =
" umin_seq ";
393 OS <<
"(" << UDiv->
getLHS() <<
" /u " << UDiv->
getRHS() <<
")";
400 OS <<
"***COULDNOTCOMPUTE***";
442 if (!
Mul)
return false;
446 if (!SC)
return false;
460 auto &Entry = ConstantSCEVs[V];
469 static_cast<SCEVConstant *
>(UniqueSCEVs.lookup(ID, Token)))
472 new (SCEVAllocator)
SCEVConstant(ID.Intern(SCEVAllocator), V);
473 UniqueSCEVs.insert(S, Token);
488 ConstantInt::get(ITy, V,
isSigned,
true));
496 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
498 SCEV *S =
new (SCEVAllocator)
SCEVVScale(ID.Intern(SCEVAllocator), Ty);
499 UniqueSCEVs.insert(S, Token);
520 "Must be a non-bit-width-changing pointer-to-integer cast!");
532 "Cannot truncate non-integer value!");
539 "Cannot zero extend non-integer value!");
546 "Cannot sign extend non-integer value!");
551 SE->forgetMemoizedResults({
this});
554 SE->UniqueSCEVs.erase(
this);
560void SCEVUnknown::allUsesReplacedWith(
Value *New) {
562 SE->forgetMemoizedResults({
this});
565 SE->UniqueSCEVs.erase(
this);
587 if (LIsPointer != RIsPointer)
588 return (
int)LIsPointer - (int)RIsPointer;
593 return (
int)LID - (int)RID;
598 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
599 return (
int)LArgNo - (int)RArgNo;
605 if (
auto L = LGV->getLinkage() - RGV->getLinkage())
608 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
609 auto LT = GV->getLinkage();
616 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
617 return LGV->getName().compare(RGV->getName());
628 if (LParent != RParent) {
631 if (LDepth != RDepth)
632 return (
int)LDepth - (int)RDepth;
636 unsigned LNumOps = LInst->getNumOperands(),
637 RNumOps = RInst->getNumOperands();
638 if (LNumOps != RNumOps)
639 return (
int)LNumOps - (int)RNumOps;
641 for (
unsigned Idx :
seq(LNumOps)) {
643 RInst->getOperand(Idx),
Depth + 1);
657static std::optional<int>
667 return (
int)LType - (int)RType;
692 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
693 if (LBitWidth != RBitWidth)
694 return (
int)LBitWidth - (int)RBitWidth;
695 return LA.
ult(
RA) ? -1 : 1;
701 return LTy->getBitWidth() - RTy->getBitWidth();
712 if (LLoop != RLoop) {
714 assert(LHead != RHead &&
"Two loops share the same header?");
718 "No dominance between recurrences used by one SCEV?");
741 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
742 if (LNumOps != RNumOps)
743 return (
int)LNumOps - (int)RNumOps;
745 for (
unsigned i = 0; i != LNumOps; ++i) {
771 if (
Ops.size() < 2)
return;
776 return Complexity && *Complexity < 0;
778 if (
Ops.size() == 2) {
782 if (IsLessComplex(
RHS,
LHS))
795 for (
unsigned i = 0, e =
Ops.size(); i != e-2; ++i) {
801 for (
unsigned j = i+1; j != e &&
Ops[j]->getSCEVType() == Complexity; ++j) {
806 if (i == e-2)
return;
828template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
832 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
834 for (
unsigned Idx = 0; Idx <
Ops.size();) {
842 Ops.erase(
Ops.begin() + Idx);
849 assert(Folded &&
"Must have folded value");
853 if (Folded && IsAbsorber(Folded->
getAPInt()))
857 if (Folded && !IsIdentity(Folded->
getAPInt()))
858 Ops.insert(
Ops.begin(), Folded);
860 return Ops.size() == 1 ?
Ops[0] :
nullptr;
935 APInt OddFactorial(W, 1);
937 for (
unsigned i = 3; i <=
K; ++i) {
940 OddFactorial *= (i >> TwoFactors);
944 unsigned CalculationBits = W +
T;
958 for (
unsigned i = 1; i !=
K; ++i) {
991 "use-specific flags only supported for affine AddRecs");
993 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1033 ConversionFn CreatePtrCast;
1037 ConversionFn CreatePtrCast)
1038 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
1041 Type *TargetTy, ConversionFn CreatePtrCast) {
1043 return Rewriter.visit(Scev);
1069 "Should only reach pointer-typed SCEVUnknown's.");
1074 return SE.getZero(TargetTy);
1075 return CreatePtrCast(Expr);
1080 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1084 if (DL.hasUnstableRepresentation(
Op->getType()))
1087 Type *Ty = DL.getAddressType(
Op->getType());
1098 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1100 SCEV *S =
new (SCEVAllocator)
1102 UniqueSCEVs.insert(S, Token);
1105 return static_cast<const SCEV *
>(S);
1108 "We must have succeeded in sinking the cast, "
1109 "and ending up with an integer-typed expression!");
1116 "This is not a truncating conversion!");
1118 "This is not a conversion to a SCEVable type!");
1119 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1124 ID.AddPointer(
Op.getOpaqueValue());
1127 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1150 UniqueSCEVs.insert(S, Token);
1163 unsigned numTruncs = 0;
1164 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1172 if (numTruncs < 2) {
1182 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1189 for (
const SCEV *
Op : AddRec->operands())
1204 UniqueSCEVs.insert(S, Token);
1245struct ExtendOpTraitsBase {
1246 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
SCEVUse,
Type *,
1251template <
typename ExtendOp>
struct ExtendOpTraits {
1267 static const GetExtendExprTy GetExtendExpr;
1269 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1270 ICmpInst::Predicate *Pred,
1271 ScalarEvolution *SE) {
1276const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1283 static const GetExtendExprTy GetExtendExpr;
1285 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1286 ICmpInst::Predicate *Pred,
1287 ScalarEvolution *SE) {
1292const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1304template <
typename ExtendOpTy>
1307 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1308 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1324 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1337 auto PreStartFlags =
1355 const SCEV *OperandExtendedStart =
1357 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1358 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1370 const SCEV *OverflowLimit =
1371 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1373 if (OverflowLimit &&
1381template <
typename ExtendOpTy>
1385 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1393 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1428template <
typename ExtendOpTy>
1429bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1432 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1442 APInt StartAI = StartC->
getAPInt();
1444 for (
unsigned Delta : {-2, -1, 1, 2}) {
1445 const SCEV *PreStart =
getConstant(StartAI - Delta);
1447 FoldingSetNodeID
ID;
1449 ID.AddPointer(PreStart);
1450 ID.AddPointer(Step);
1452 FoldingSetInsertToken Token;
1454 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.lookup(ID, Token));
1458 if (PreAR &&
any(PreAR->getNoWrapFlags(WrapType))) {
1461 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1462 DeltaS, &Pred,
this);
1480 const unsigned BitWidth =
C.getBitWidth();
1498 const APInt &ConstantStart,
1513 auto I = FoldCache.
insert({ID, S});
1517 auto &UserIDs = FoldCacheUser[
I.first->second];
1518 assert(
count(UserIDs, ID) == 1 &&
"unexpected duplicates in UserIDs");
1519 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1520 if (UserIDs[
I] == ID) {
1525 I.first->second = S;
1527 FoldCacheUser[S].push_back(ID);
1533 "This is not an extending conversion!");
1535 "This is not a conversion to a SCEVable type!");
1536 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1540 if (
const SCEV *S = FoldCache.lookup(ID))
1552 "This is not an extending conversion!");
1554 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1566 const SCEV *Start, *Step;
1571 if (AR->hasNoUnsignedWrap()) {
1582 ID.AddPointer(
Op.getOpaqueValue());
1585 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1590 UniqueSCEVs.insert(S, Token);
1600 const SCEV *
X = ST->getOperand();
1633 const SCEV *CastedMaxBECount =
1637 if (MaxBECount == RecastedMaxBECount) {
1646 const SCEV *WideMaxBECount =
1648 const SCEV *OperandExtendedAdd =
1654 if (ZAdd == OperandExtendedAdd) {
1665 OperandExtendedAdd =
1671 if (ZAdd == OperandExtendedAdd) {
1692 !AC.assumptions().empty()) {
1694 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1696 if (AR->hasNoUnsignedWrap()) {
1731 const APInt &
C = SC->getAPInt();
1735 const SCEV *SResidual =
1743 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1767 if (SA->hasNoUnsignedWrap()) {
1780 if (SA->hasNoSignedWrap() &&
1783 C->isNegative() && !
C->isMinSignedValue() && C2->
sge(
C->abs())) {
1802 const SCEV *SResidual =
1813 if (SM->hasNoUnsignedWrap()) {
1835 const SCEV *TruncRHS;
1872 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1876 UniqueSCEVs.insert(S, Token);
1885 "This is not an extending conversion!");
1887 "This is not a conversion to a SCEVable type!");
1888 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1892 if (
const SCEV *S = FoldCache.lookup(ID))
1904 "This is not an extending conversion!");
1906 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1923 const SCEV *Start, *Step;
1928 if (AR->hasNoSignedWrap()) {
1939 ID.AddPointer(
Op.getOpaqueValue());
1942 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1948 UniqueSCEVs.insert(S, Token);
1958 const SCEV *
X = ST->getOperand();
1969 if (SA->hasNoSignedWrap()) {
1991 const SCEV *SResidual =
2024 const SCEV *CastedMaxBECount =
2028 if (MaxBECount == RecastedMaxBECount) {
2037 const SCEV *WideMaxBECount =
2039 const SCEV *OperandExtendedAdd =
2045 if (SAdd == OperandExtendedAdd) {
2056 OperandExtendedAdd =
2062 if (SAdd == OperandExtendedAdd) {
2082 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2084 if (AR->hasNoSignedWrap()) {
2098 const APInt &
C = SC->getAPInt();
2102 const SCEV *SResidual =
2110 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2137 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
2141 UniqueSCEVs.insert(S, Token);
2157 assert(Expr->
getType() == Ty &&
"requested type must match");
2169 "This is not an extending conversion!");
2171 "This is not a conversion to a SCEVable type!");
2176 if (SC->getAPInt().isNegative())
2181 const SCEV *NewOp =
T->getOperand();
2200 for (
const SCEV *
Op : AR->operands())
2238 APInt &AccumulatedConstant,
2242 bool Interesting =
false;
2249 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2251 AccumulatedConstant += Scale *
C->getAPInt();
2256 for (; i !=
Ops.size(); ++i) {
2265 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2271 auto Pair = M.insert({
Key, NewScale});
2275 Pair.first->second += NewScale;
2283 auto Pair = M.insert({
Ops[i], Scale});
2287 Pair.first->second += Scale;
2305 case Instruction::Add:
2307 case Instruction::Sub:
2309 case Instruction::Mul:
2323 const SCEV *
A = (this->*Extension)(
Operation(LHS, RHS), WideTy, 0);
2324 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2325 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2333 if (BinOp == Instruction::Mul)
2339 APInt C = RHSC->getAPInt();
2340 unsigned NumBits =
C.getBitWidth();
2341 bool IsSub = (BinOp == Instruction::Sub);
2342 bool IsNegativeConst = (
Signed &&
C.isNegative());
2344 bool OverflowDown = IsSub ^ IsNegativeConst;
2346 if (IsNegativeConst) {
2359 APInt Limit = Min + Magnitude;
2365 APInt Limit = Max - Magnitude;
2370std::optional<SCEV::NoWrapFlags>
2375 return std::nullopt;
2384 bool Deduced =
false;
2390 bool CanUseNSW =
true;
2391 const APInt *ShiftAmt;
2396 return std::nullopt;
2400 Opcode = Instruction::Mul;
2402 }
else if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
2403 Opcode != Instruction::Mul) {
2404 return std::nullopt;
2423 return std::nullopt;
2433 using namespace std::placeholders;
2440 assert(CanAnalyze &&
"don't call from other places!");
2447 auto IsKnownNonNegative = [&](
SCEVUse U) {
2456 if (SignOrUnsignWrap != SignOrUnsignMask &&
2463 return Instruction::Add;
2465 return Instruction::Mul;
2476 Opcode,
C, OBO::NoSignedWrap);
2484 Opcode,
C, OBO::NoUnsignedWrap);
2494 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2501 if (UDiv->getOperand(1) ==
Ops[1])
2504 if (UDiv->getOperand(1) ==
Ops[0])
2521 "only nuw or nsw allowed");
2523 "only nuw or nsw allowed");
2524 assert(!
Ops.empty() &&
"Cannot get empty add!");
2525 if (
Ops.size() == 1)
return Ops[0];
2528 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2530 "SCEVAddExpr operand types don't match!");
2532 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2533 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2538 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2539 [](
const APInt &
C) {
return C.isZero(); },
2540 [](
const APInt &
C) {
return false; });
2559 return {getOrCreateAddExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
2564 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2565 Add->setNoWrapFlags(ComputeFlags(
Ops));
2566 return {S, UseFlags};
2573 bool FoundMatch =
false;
2574 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2575 if (
Ops[i] ==
Ops[i+1]) {
2587 --i; e -=
Count - 1;
2597 auto FindTruncSrcType = [&]() ->
Type * {
2603 return T->getOperand()->getType();
2605 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2607 return T->getOperand()->getType();
2611 if (
auto *SrcType = FindTruncSrcType()) {
2618 if (
T->getOperand()->getType() != SrcType) {
2627 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2630 if (
T->getOperand()->getType() != SrcType) {
2658 if (
Ops.size() == 2) {
2668 auto C2 =
C->getAPInt();
2671 APInt ConstAdd = C1 + C2;
2672 auto AddFlags = AddExpr->getNoWrapFlags();
2713 if (
Ops.size() == 2 &&
2724 if (Idx <
Ops.size()) {
2725 bool DeletedAdd =
false;
2736 Ops.erase(
Ops.begin()+Idx);
2739 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2762 struct APIntCompare {
2763 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2764 return LHS.ult(RHS);
2771 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2772 for (
const SCEV *NewOp : NewOps)
2773 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2776 if (AccumulatedConstant != 0)
2778 for (
auto &MulOp : MulOpLists) {
2779 if (MulOp.first == 1) {
2781 }
else if (MulOp.first != 0) {
2790 if (
Ops.size() == 1)
2799 if (M->getNumOperands() == 2)
2800 return M->getOperand(OpIdx == 0);
2802 append_range(Remaining, M->operands().drop_front(OpIdx + 1));
2811 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2815 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2823 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp) {
2824 if (MulOpSCEV ==
Ops[AddOp]) {
2835 for (
unsigned OMulOp = 0, OE = OtherMul->
getNumOperands(); OMulOp != OE;
2837 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2839 Cofactors.
push_back(StripFactor(OtherMul, OMulOp));
2848 if (!Cofactors.
empty()) {
2856 if (
Ops.size() == DeadIndices.
size() + 1)
2863 Ops.erase(
Ops.begin() + Idx);
2867 Ops.push_back(OuterMul);
2886 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2889 Ops.erase(
Ops.begin()+i);
2894 if (!LIOps.
empty()) {
2919 auto *DefI = getDefiningScopeBound(LIOps);
2921 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2933 if (
Ops.size() == 1)
return NewRec;
2936 for (
unsigned i = 0;; ++i)
2937 if (
Ops[i] == AddRec) {
2947 for (
unsigned OtherIdx = Idx+1;
2955 "AddRecExprs are not sorted in reverse dominance order?");
2962 if (OtherAddRec->getLoop() == AddRecLoop) {
2963 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2965 if (i >= AddRecOps.
size()) {
2966 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2970 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
2973 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
2989 "Tried to add SCEVUse flags after operands changed");
2990 return {getOrCreateAddExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
2998 ID.AddPointer(
Op.getOpaqueValue());
3004 S =
new (SCEVAllocator)
3006 UniqueSCEVs.insert(S, Token);
3017 FoldingSetNodeID
ID;
3020 ID.AddPointer(
Op.getOpaqueValue());
3022 FoldingSetInsertToken Token;
3024 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.lookup(ID, Token));
3028 S =
new (SCEVAllocator)
3029 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3030 UniqueSCEVs.insert(S, Token);
3032 LoopUsers[
L].push_back(S);
3041 FoldingSetNodeID
ID;
3044 ID.AddPointer(
Op.getOpaqueValue());
3045 FoldingSetInsertToken Token;
3046 SCEVMulExpr *S =
static_cast<SCEVMulExpr *
>(UniqueSCEVs.lookup(ID, Token));
3050 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3052 UniqueSCEVs.insert(S, Token);
3061 FoldingSetNodeID
ID;
3063 ID.AddPointer(
LHS.getOpaqueValue());
3064 ID.AddPointer(
RHS.getOpaqueValue());
3065 FoldingSetInsertToken Token;
3066 SCEV *S = UniqueSCEVs.lookup(ID, Token);
3068 S =
new (SCEVAllocator) SCEVUDivExpr(
ID.Intern(SCEVAllocator),
LHS,
RHS);
3069 UniqueSCEVs.insert(S, Token);
3078 if (j > 1 && k / j != i) Overflow =
true;
3094 if (n == 0 || n == k)
return 1;
3095 if (k > n)
return 0;
3101 for (
uint64_t i = 1; i <= k; ++i) {
3102 r =
umul_ov(r, n-(i-1), Overflow);
3111 struct FindConstantInAddMulChain {
3112 bool FoundConstant =
false;
3114 bool follow(
const SCEV *S) {
3119 bool isDone()
const {
3120 return FoundConstant;
3124 FindConstantInAddMulChain
F;
3126 ST.visitAll(StartExpr);
3127 return F.FoundConstant;
3136 "only nuw or nsw allowed");
3138 "only nuw or nsw allowed");
3139 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3140 if (
Ops.size() == 1)
return Ops[0];
3142 Type *ETy =
Ops[0]->getType();
3144 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3146 "SCEVMulExpr operand types don't match!");
3151 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3152 [](
const APInt &
C) {
return C.isOne(); },
3153 [](
const APInt &
C) {
return C.isZero(); });
3170 return {getOrCreateMulExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
3175 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3176 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3177 return {S, UseFlags};
3181 if (
Ops.size() == 2) {
3189 const SCEV *Op0, *Op1;
3197 if (
Ops[0]->isAllOnesValue()) {
3202 bool AnyFolded =
false;
3203 for (
const SCEV *AddOp :
Add->operands()) {
3223 if (AddRec->hasNoSignedWrap()) {
3230 AddRec->getNoWrapFlags(FlagsMask));
3254 APInt C1V = LHSC->getAPInt();
3264 const SCEV *NewMul =
nullptr;
3268 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3283 if (Idx <
Ops.size()) {
3284 bool DeletedMul =
false;
3290 Ops.erase(
Ops.begin()+Idx);
3314 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3317 Ops.erase(
Ops.begin()+i);
3322 if (!LIOps.
empty()) {
3335 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3351 if (
Ops.size() == 1)
return NewRec;
3354 for (
unsigned i = 0;; ++i)
3355 if (
Ops[i] == AddRec) {
3376 bool OpsModified =
false;
3377 for (
unsigned OtherIdx = Idx+1;
3391 bool Overflow =
false;
3398 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3399 uint64_t Coeff1 =
Choose(x, 2*x - y, Overflow);
3402 z < ze && !Overflow; ++z) {
3403 uint64_t Coeff2 =
Choose(2*x - y, x-z, Overflow);
3405 if (LargerThan64Bits)
3406 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3408 Coeff = Coeff1*Coeff2;
3423 if (
Ops.size() == 2)
return NewAddRec;
3424 Ops[Idx] = NewAddRec;
3425 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3442 "Tried to add SCEVUse flags after operands changed");
3443 return {getOrCreateMulExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
3450 "SCEVURemExpr operand types don't match!");
3455 if (RHSC->getValue()->isOne())
3456 return getZero(LHS->getType());
3459 if (RHSC->getAPInt().isPowerOf2()) {
3460 Type *FullTy = LHS->getType();
3476 assert(!LHS->getType()->isPointerTy() &&
3477 "SCEVUDivExpr operand can't be pointer!");
3478 assert(LHS->getType() == RHS->getType() &&
3479 "SCEVUDivExpr operand types don't match!");
3489 if (RHSC->getValue()->isOne())
3494 if (!RHSC->getValue()->isZero()) {
3498 Type *Ty = LHS->getType();
3499 unsigned LZ = RHSC->getAPInt().countl_zero();
3503 if (!RHSC->getAPInt().isPowerOf2())
3511 const APInt &StepInt = Step->getAPInt();
3512 const APInt &DivInt = RHSC->getAPInt();
3513 if (!StepInt.
urem(DivInt) &&
3519 for (
const SCEV *
Op : AR->operands())
3525 const APInt *StartRem;
3538 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3542 const SCEV *NewStart =
3544 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3546 const SCEV *NewLHS =
3556 if (M->hasNoUnsignedWrap()) {
3558 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3559 const SCEV *
Op = M->getOperand(i);
3586 if (
auto *DivisorConstant =
3588 bool Overflow =
false;
3590 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3601 if (
A->hasNoUnsignedWrap()) {
3603 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3610 if (
Operands.size() ==
A->getNumOperands())
3622 const APInt &
N = RHSC->getAPInt();
3623 const APInt *NMinusM, *M;
3627 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3628 *NMinusM ==
N - *M) {
3637 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3647 return getZero(LHS->getType());
3651 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3652 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3653 if (
Mul->getOperand(i) == RHS) {
3664 const SCEV *NewLHS, *NewRHS;
3669 return getOrCreateUDivExpr(LHS, RHS);
3688 if (StepChrec->getLoop() == L) {
3707 "only nuw or nsw allowed");
3713 "SCEVAddRecExpr operand types don't match!");
3714 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3718 "SCEVAddRecExpr operand is not available at loop entry!");
3740 const Loop *NestedLoop = NestedAR->getLoop();
3741 if (L->contains(NestedLoop)
3744 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3746 Operands[0] = NestedAR->getStart();
3750 bool AllInvariant =
all_of(
3762 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3773 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3784 "Tried to add SCEVUse flags after operands changed");
3785 return {getOrCreateAddRecExpr(
Operands, L, Flags), UseFlags};
3801 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3805 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3819 bool FirstIter =
true;
3821 for (
SCEVUse IndexExpr : IndexExprs) {
3828 Offsets.push_back(FieldOffset);
3831 CurTy = STy->getTypeAtIndex(Index);
3836 "The first index of a GEP indexes a pointer");
3837 CurTy = SrcElementTy;
3848 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3849 Offsets.push_back(LocalOffset);
3854 if (Offsets.empty())
3867 "GEP should not change type mid-flight.");
3871SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3876 ID.AddPointer(
Op.getOpaqueValue());
3878 return UniqueSCEVs.lookup(ID, Token);
3888 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3889 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3890 if (
Ops.size() == 1)
return Ops[0];
3893 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3895 "Operand types don't match!");
3898 "min/max should be consistently pointerish");
3924 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3926 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3931 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3933 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3939 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3945 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3950 if (Idx <
Ops.size()) {
3951 bool DeletedAny =
false;
3952 while (
Ops[Idx]->getSCEVType() == Kind) {
3954 Ops.erase(
Ops.begin()+Idx);
3972 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3973 if (
Ops[i] ==
Ops[i + 1] ||
3974 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3977 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3980 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3983 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3989 if (
Ops.size() == 1)
return Ops[0];
3991 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
3998 ID.AddPointer(
Op.getOpaqueValue());
4000 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
4002 return ExistingSCEV;
4005 SCEV *S =
new (SCEVAllocator)
4008 UniqueSCEVs.insert(S, Token);
4016class SCEVSequentialMinMaxDeduplicatingVisitor final
4017 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4018 std::optional<const SCEV *>> {
4019 using RetVal = std::optional<const SCEV *>;
4026 bool canRecurseInto(
SCEVTypes Kind)
const {
4029 return RootKind == Kind || NonSequentialRootKind == Kind;
4034 if (!SeenOps.
insert(S).second)
4035 return std::nullopt;
4039 if (!canRecurseInto(Kind))
4049 return std::nullopt;
4059 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4061 : SE(SE), RootKind(RootKind),
4062 NonSequentialRootKind(
4063 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4067 SmallVectorImpl<SCEVUse> &NewOps) {
4072 for (
const SCEV *
Op : OrigOps) {
4077 Ops.emplace_back(*NewOp);
4081 NewOps = std::move(
Ops);
4125struct SCEVPoisonCollector {
4126 bool LookThroughMaybePoisonBlocking;
4127 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4128 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4129 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4131 bool follow(
const SCEV *S) {
4132 if (!LookThroughMaybePoisonBlocking &&
4142 bool isDone()
const {
return false; }
4152 SCEVPoisonCollector PC1(
true);
4157 if (PC1.MaybePoison.
empty())
4163 SCEVPoisonCollector PC2(
false);
4173 SCEVPoisonCollector PC(
false);
4196 while (!Worklist.
empty()) {
4198 if (!Visited.
insert(V).second)
4202 if (Visited.
size() > 16)
4218 if (PDI->isDisjoint())
4225 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4232 if (
I->hasPoisonGeneratingAnnotations())
4243 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4244 "Not a SCEVSequentialMinMaxExpr!");
4245 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4246 if (
Ops.size() == 1)
4250 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4252 "Operand types don't match!");
4255 "min/max should be consistently pointerish");
4263 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4270 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4280 bool DeletedAny =
false;
4281 while (Idx <
Ops.size()) {
4282 if (
Ops[Idx]->getSCEVType() != Kind) {
4287 Ops.erase(
Ops.begin() + Idx);
4288 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4289 SMME->operands().end());
4297 const SCEV *SaturationPoint;
4308 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4309 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4321 Ops.erase(
Ops.begin() + i);
4326 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4327 Ops.erase(
Ops.begin() + i);
4337 ID.AddPointer(
Op.getOpaqueValue());
4339 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
4341 return ExistingSCEV;
4345 SCEV *S =
new (SCEVAllocator)
4348 UniqueSCEVs.insert(S, Token);
4396 if (
Size.isScalable())
4417 "Cannot get offset for structure containing scalable vector types");
4431 if (
SCEV *S = UniqueSCEVs.lookup(ID, Token)) {
4433 "Stale SCEVUnknown in uniquing map!");
4436 SCEV *S =
new (SCEVAllocator)
SCEVUnknown(ID.Intern(SCEVAllocator), V,
this,
4439 UniqueSCEVs.insert(S, Token);
4454 return Ty->isIntOrPtrTy();
4461 if (Ty->isPointerTy())
4472 if (Ty->isIntegerTy())
4476 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4488 bool PreciseA, PreciseB;
4489 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4490 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4491 if (!PreciseA || !PreciseB)
4494 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4495 DT.dominates(ScopeB, ScopeA);
4499 return CouldNotCompute.get();
4502bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4505 return SU && SU->getValue() ==
nullptr;
4508 return !ContainsNulls;
4513 if (
I != HasRecMap.end())
4518 HasRecMap.insert({S, FoundAddRec});
4526 if (
SI == ExprValueMap.
end())
4528 return SI->second.getArrayRef();
4534void ScalarEvolution::eraseValueFromMap(
Value *V) {
4536 if (
I != ValueExprMap.end()) {
4537 auto EVIt = ExprValueMap.find(
I->second);
4538 bool Removed = EVIt->second.remove(V);
4540 assert(Removed &&
"Value not in ExprValueMap?");
4541 ValueExprMap.erase(
I);
4545void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4549 auto It = ValueExprMap.find_as(V);
4550 if (It == ValueExprMap.end()) {
4552 ExprValueMap[S].insert(V);
4563 return createSCEVIter(V);
4570 if (
I != ValueExprMap.end()) {
4571 const SCEV *S =
I->second;
4572 assert(checkValidity(S) &&
4573 "existing SCEV has not been properly invalidated");
4586 Type *Ty = V->getType();
4602 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4615 return (
const SCEV *)
nullptr;
4621 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4625 Type *Ty = V->getType();
4631 assert(
P->getType()->isPointerTy());
4646 if (AddOp->getType()->isPointerTy()) {
4647 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4665 return getZero(LHS->getType());
4670 if (RHS->getType()->isPointerTy()) {
4671 if (!LHS->getType()->isPointerTy() ||
4681 const bool RHSIsNotMinSigned =
4712 Type *SrcTy = V->getType();
4713 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4714 "Cannot truncate or zero extend with non-integer arguments!");
4724 Type *SrcTy = V->getType();
4725 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4726 "Cannot truncate or zero extend with non-integer arguments!");
4735 Type *SrcTy = V->getType();
4736 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4737 "Cannot noop or zero extend with non-integer arguments!");
4739 "getNoopOrZeroExtend cannot truncate!");
4746 Type *SrcTy = V->getType();
4747 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4748 "Cannot noop or sign extend with non-integer arguments!");
4750 "getNoopOrSignExtend cannot truncate!");
4757 Type *SrcTy = V->getType();
4758 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4759 "Cannot noop or any extend with non-integer arguments!");
4761 "getNoopOrAnyExtend cannot truncate!");
4768 Type *SrcTy = V->getType();
4769 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4770 "Cannot truncate or noop with non-integer arguments!");
4772 "getTruncateOrNoop cannot extend!");
4780 const SCEV *PromotedLHS = LHS;
4781 const SCEV *PromotedRHS = RHS;
4801 assert(!
Ops.empty() &&
"At least one operand must be!");
4803 if (
Ops.size() == 1)
4807 Type *MaxType =
nullptr;
4813 assert(MaxType &&
"Failed to find maximum type!");
4826 if (!V->getType()->isPointerTy())
4831 V = AddRec->getStart();
4833 const SCEV *PtrOp =
nullptr;
4834 for (
const SCEV *AddOp :
Add->operands()) {
4835 if (AddOp->getType()->isPointerTy()) {
4836 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4840 assert(PtrOp &&
"Must have pointer op");
4852 for (
User *U :
I->users()) {
4854 if (Visited.
insert(UserInsn).second)
4868 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4869 bool IgnoreOtherLoops =
true) {
4872 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4874 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4879 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4881 SeenLoopVariantSCEVUnknown =
true;
4885 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4889 SeenOtherLoops =
true;
4893 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4895 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4898 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4899 : SCEVRewriteVisitor(SE),
L(
L) {}
4902 bool SeenLoopVariantSCEVUnknown =
false;
4903 bool SeenOtherLoops =
false;
4912 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4913 SCEVPostIncRewriter
Rewriter(L, SE);
4915 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4920 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4922 SeenLoopVariantSCEVUnknown =
true;
4926 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4930 SeenOtherLoops =
true;
4934 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4936 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4939 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4940 : SCEVRewriteVisitor(SE),
L(
L) {}
4943 bool SeenLoopVariantSCEVUnknown =
false;
4944 bool SeenOtherLoops =
false;
4950class SCEVBackedgeConditionFolder
4953 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4954 ScalarEvolution &SE) {
4955 bool IsPosBECond =
false;
4956 Value *BECond =
nullptr;
4957 if (BasicBlock *Latch =
L->getLoopLatch()) {
4959 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
4960 "Both outgoing branches should not target same header!");
4961 BECond = BI->getCondition();
4962 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
4967 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
4971 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4972 const SCEV *
Result = Expr;
4977 switch (
I->getOpcode()) {
4978 case Instruction::Select: {
4980 std::optional<const SCEV *> Res =
4981 compareWithBackedgeCondition(
SI->getCondition());
4989 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5000 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5001 bool IsPosBECond, ScalarEvolution &SE)
5002 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5003 IsPositiveBECond(IsPosBECond) {}
5005 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5009 Value *BackedgeCond =
nullptr;
5011 bool IsPositiveBECond;
5014std::optional<const SCEV *>
5015SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5020 if (BackedgeCond == IC)
5023 return std::nullopt;
5028 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5029 ScalarEvolution &SE) {
5035 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5042 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5052 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5053 : SCEVRewriteVisitor(SE),
L(
L) {}
5061void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5077 const APInt &BECountAP = BECountMax->getAPInt();
5078 unsigned NoOverflowBitWidth =
5087ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5097 if (!SignedWrapViaInductionTried.insert(AR).second)
5122 AC.assumptions().empty())
5130 const SCEV *OverflowLimit =
5132 if (OverflowLimit &&
5140ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5150 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5175 AC.assumptions().empty())
5184 const SCEV *OverflowLimit =
5213 IsNSW = OBO->hasNoSignedWrap();
5214 IsNUW = OBO->hasNoUnsignedWrap();
5220 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5232 return std::nullopt;
5238 switch (
Op->getOpcode()) {
5239 case Instruction::Add:
5240 case Instruction::Sub:
5241 case Instruction::Mul:
5242 case Instruction::UDiv:
5243 case Instruction::URem:
5244 case Instruction::And:
5245 case Instruction::AShr:
5246 case Instruction::Shl:
5249 case Instruction::Or: {
5252 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5262 case Instruction::Xor:
5266 if (RHSC->getValue().isSignMask())
5267 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5269 if (V->getType()->isIntegerTy(1))
5270 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5273 case Instruction::LShr:
5282 if (SA->getValue().ult(
BitWidth)) {
5284 ConstantInt::get(SA->getContext(),
5286 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5291 case Instruction::ExtractValue: {
5293 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5301 bool Signed = WO->isSigned();
5304 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5309 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5320 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5321 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5323 return std::nullopt;
5349 if (
Op == SymbolicPHI)
5354 if (SourceBits != NewBits)
5372 if (!L || L->getHeader() != PN->
getParent())
5430std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5431ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5439 assert(L &&
"Expecting an integer loop header phi");
5444 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5445 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5446 Value *
V = PN->getIncomingValue(i);
5447 if (
L->contains(PN->getIncomingBlock(i))) {
5450 }
else if (BEValueV != V) {
5454 }
else if (!StartValueV) {
5456 }
else if (StartValueV != V) {
5457 StartValueV =
nullptr;
5461 if (!BEValueV || !StartValueV)
5462 return std::nullopt;
5464 const SCEV *BEValue =
getSCEV(BEValueV);
5471 return std::nullopt;
5475 unsigned FoundIndex =
Add->getNumOperands();
5476 Type *TruncTy =
nullptr;
5478 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5481 if (FoundIndex == e) {
5486 if (FoundIndex ==
Add->getNumOperands())
5487 return std::nullopt;
5491 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5492 if (i != FoundIndex)
5493 Ops.push_back(
Add->getOperand(i));
5499 return std::nullopt;
5552 const SCEV *StartVal =
getSCEV(StartValueV);
5553 const SCEV *PHISCEV =
5580 auto getExtendedExpr = [&](
const SCEV *Expr,
5581 bool CreateSignExtend) ->
const SCEV * {
5584 const SCEV *ExtendedExpr =
5587 return ExtendedExpr;
5595 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5596 const SCEV *ExtendedExpr) ->
bool {
5597 return Expr != ExtendedExpr &&
5601 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5602 if (PredIsKnownFalse(StartVal, StartExtended)) {
5604 return std::nullopt;
5609 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5610 if (PredIsKnownFalse(Accum, AccumExtended)) {
5612 return std::nullopt;
5615 auto AppendPredicate = [&](
const SCEV *Expr,
5616 const SCEV *ExtendedExpr) ->
void {
5617 if (Expr != ExtendedExpr &&
5625 AppendPredicate(StartVal, StartExtended);
5626 AppendPredicate(Accum, AccumExtended);
5634 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5635 std::make_pair(NewAR, Predicates);
5637 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5641std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5646 return std::nullopt;
5649 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5650 if (
I != PredicatedSCEVRewrites.end()) {
5651 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5654 if (Rewrite.first == SymbolicPHI)
5655 return std::nullopt;
5659 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5663 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5664 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5669 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5670 return std::nullopt;
5690 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5691 if (Expr1 != Expr2 &&
5692 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5693 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5728const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5730 Value *StartValueV) {
5733 assert(BEValueV && StartValueV);
5735 const SCEV *Accum =
nullptr;
5738 if (BO->Opcode != Instruction::Add)
5741 if (BO->LHS == PN &&
L->isLoopInvariant(BO->RHS))
5743 else if (BO->RHS == PN &&
L->isLoopInvariant(BO->LHS))
5757 if (!
GEP ||
GEP->getPointerOperand() != PN ||
GEP->getNumIndices() != 1)
5760 if (!
L->isLoopInvariant(Idx))
5769 const SCEV *StartVal =
getSCEV(StartValueV);
5770 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5771 insertValueToMap(PN, PHISCEV);
5774 inferNoWrapViaConstantRanges(AR);
5781 "Accum is defined outside L, but is not invariant?");
5782 if (isAddRecNeverPoison(BEInst, L))
5789const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5797 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5803 }
else if (BEValueV != V) {
5807 }
else if (!StartValueV) {
5809 }
else if (StartValueV != V) {
5810 StartValueV =
nullptr;
5814 if (!BEValueV || !StartValueV)
5817 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5818 "PHI node already processed?");
5822 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5827 insertValueToMap(PN, SymbolicName);
5831 const SCEV *BEValue =
getSCEV(BEValueV);
5841 unsigned FoundIndex =
Add->getNumOperands();
5842 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5843 if (
Add->getOperand(i) == SymbolicName)
5844 if (FoundIndex == e) {
5849 if (FoundIndex !=
Add->getNumOperands()) {
5852 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5853 if (i != FoundIndex)
5854 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5866 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5873 if (
GEP->getOperand(0) == PN)
5881 const SCEV *StartVal =
getSCEV(StartValueV);
5882 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5887 forgetMemoizedResults({SymbolicName});
5888 insertValueToMap(PN, PHISCEV);
5891 inferNoWrapViaConstantRanges(AR);
5915 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5916 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5918 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5919 const SCEV *StartVal =
getSCEV(StartValueV);
5920 if (Start == StartVal) {
5924 forgetMemoizedResults({SymbolicName});
5925 insertValueToMap(PN, Shifted);
5935 eraseValueFromMap(PN);
5950 Use &LeftUse =
Merge->getOperandUse(0);
5951 Use &RightUse =
Merge->getOperandUse(1);
5987 assert(IDom &&
"At least the entry block should dominate PN");
5995const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
6000 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6017 CommonInst = IncomingInst;
6033ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6039 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6040 bool SCEVExprsIdentical =
6042 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6043 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6046const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6047 if (
const SCEV *S = createAddRecFromPHI(PN))
6057 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6060 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6069 struct FindClosure {
6070 const SCEV *OperandToFind;
6076 bool canRecurseInto(
SCEVTypes Kind)
const {
6079 return RootKind == Kind || NonSequentialRootKind == Kind ||
6084 : OperandToFind(OperandToFind), RootKind(RootKind),
6085 NonSequentialRootKind(
6089 bool follow(
const SCEV *S) {
6090 Found = S == OperandToFind;
6092 return !isDone() && canRecurseInto(S->
getSCEVType());
6095 bool isDone()
const {
return Found; }
6098 FindClosure FC(OperandToFind, RootKind);
6103std::optional<const SCEV *>
6104ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6114 switch (ICI->getPredicate()) {
6128 bool Signed = ICI->isSigned();
6129 const SCEV *LA =
getSCEV(TrueVal);
6137 if (LA == LS &&
RA == RS)
6139 if (LA == RS &&
RA == LS)
6142 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6143 if (
Op->getType()->isPointerTy()) {
6154 LS = CoerceOperand(LS);
6155 RS = CoerceOperand(RS);
6179 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6180 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6194 X = ZExt->getOperand();
6196 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6207 return std::nullopt;
6210static std::optional<const SCEV *>
6212 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6216 "Unexpected operands of a select.");
6228 return std::nullopt;
6243static std::optional<const SCEV *>
6247 return std::nullopt;
6250 const auto *SETrue = SE->
getSCEV(TrueVal);
6251 const auto *SEFalse = SE->
getSCEV(FalseVal);
6255const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6257 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6259 V->getType() ==
TrueVal->getType() &&
6260 "Types of select hands and of the result must match.");
6263 if (!
V->getType()->isIntegerTy(1))
6266 if (std::optional<const SCEV *> S =
6279 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6283 if (std::optional<const SCEV *> S =
6284 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6290 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6296 assert(
GEP->getSourceElementType()->isSized() &&
6297 "GEP source element type must be sized");
6300 for (
Value *Index :
GEP->indices())
6305APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6308 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6311 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6313 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6316 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6334 return GetShiftedByZeros(TZ);
6344 return GetShiftedByZeros(TZ);
6348 if (
M->hasNoUnsignedWrap()) {
6351 for (
const SCEV *Operand :
M->operands().drop_front())
6359 for (
const SCEV *Operand :
M->operands())
6361 return GetShiftedByZeros(TZ);
6366 if (
N->hasNoUnsignedWrap())
6367 return GetGCDMultiple(
N);
6370 for (
const SCEV *Operand :
N->operands().drop_front())
6372 return GetShiftedByZeros(TZ);
6389 CtxI = &*F.getEntryBlock().begin();
6396 .allowEphemerals(
true))
6397 .countMinTrailingZeros();
6398 return GetShiftedByZeros(
Known);
6411 return getConstantMultipleImpl(S, CtxI);
6413 auto I = ConstantMultipleCache.find(S);
6414 if (
I != ConstantMultipleCache.end())
6417 APInt Result = getConstantMultipleImpl(S, CtxI);
6418 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6419 assert(InsertPair.second &&
"Should insert a new key");
6420 return InsertPair.first->second;
6437 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6440 if (std::optional<ConstantRange>
Range = CB->getRange())
6444 if (std::optional<ConstantRange>
Range =
A->getRange())
6447 return std::nullopt;
6454 UnsignedRanges.erase(AddRec);
6455 SignedRanges.erase(AddRec);
6456 ConstantMultipleCache.erase(AddRec);
6461getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6487 Value *Start, *Step;
6494 assert(L && L->getHeader() ==
P->getParent());
6507 case Instruction::AShr:
6508 case Instruction::LShr:
6509 case Instruction::Shl:
6524 KnownStep.getBitWidth() ==
BitWidth);
6527 auto MaxShiftAmt = KnownStep.getMaxValue();
6529 bool Overflow =
false;
6530 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6537 case Instruction::AShr: {
6545 if (KnownStart.isNonNegative())
6548 KnownStart.getMaxValue() + 1);
6549 if (KnownStart.isNegative())
6552 KnownEnd.getMaxValue() + 1);
6555 case Instruction::LShr: {
6564 KnownStart.getMaxValue() + 1);
6566 case Instruction::Shl: {
6570 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6571 return ConstantRange(KnownStart.getMinValue(),
6572 KnownEnd.getMaxValue() + 1);
6597 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6604ScalarEvolution::getRangeRefIter(
const SCEV *S,
6605 ScalarEvolution::RangeSignHint SignHint) {
6606 DenseMap<const SCEV *, ConstantRange> &Cache =
6607 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6610 SmallPtrSet<const SCEV *, 8> Seen;
6614 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6615 if (!Seen.
insert(Expr).second)
6648 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6649 const SCEV *
P = WorkList[
I];
6653 for (
const SCEV *
Op :
P->operands())
6666 if (!WorkList.
empty()) {
6671 getRangeRef(
P, SignHint);
6675 return getRangeRef(S, SignHint, 0);
6678const APInt *ScalarEvolution::getConstantAPIntOrNull(
const SCEV *S) {
6680 return &
C->getAPInt();
6688 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6689 DenseMap<const SCEV *, ConstantRange> &Cache =
6690 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6697 auto I = Cache.
find(S);
6698 if (
I != Cache.
end())
6702 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6707 return getRangeRefIter(S, SignHint);
6710 ConstantRange ConservativeResult(
BitWidth,
true);
6711 using OBO = OverflowingBinaryOperator;
6715 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6719 ConservativeResult =
6726 ConservativeResult = ConstantRange(
6742 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6749 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6756 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6761 return setRange(Cast, SignHint,
X);
6766 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6767 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6769 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6770 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6771 ConservativeResult =
6772 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6774 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6775 unsigned WrapType = OBO::AnyWrap;
6776 if (
Add->hasNoSignedWrap())
6777 WrapType |= OBO::NoSignedWrap;
6778 if (
Add->hasNoUnsignedWrap())
6779 WrapType |= OBO::NoUnsignedWrap;
6781 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6783 return setRange(
Add, SignHint,
6784 ConservativeResult.intersectWith(
X, RangeType));
6788 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6790 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6791 return setRange(
Mul, SignHint,
6792 ConservativeResult.intersectWith(
X, RangeType));
6796 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6797 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6798 return setRange(UDiv, SignHint,
6799 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6807 if (!UnsignedMinValue.
isZero())
6808 ConservativeResult = ConservativeResult.intersectWith(
6809 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6818 bool AllNonNeg =
true;
6819 bool AllNonPos =
true;
6820 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6827 ConservativeResult = ConservativeResult.intersectWith(
6832 ConservativeResult = ConservativeResult.intersectWith(
6841 const SCEV *MaxBEScev =
6855 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6857 ConservativeResult =
6858 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6861 auto RangeFromFactoring = getRangeViaFactoring(
6863 ConservativeResult =
6864 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6870 const SCEV *SymbolicMaxBECount =
6875 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6876 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6877 ConservativeResult =
6878 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6883 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6893 ID = Intrinsic::umax;
6896 ID = Intrinsic::smax;
6900 ID = Intrinsic::umin;
6903 ID = Intrinsic::smin;
6910 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6911 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6913 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6914 return setRange(S, SignHint,
6915 ConservativeResult.intersectWith(
X, RangeType));
6924 ConservativeResult =
6925 ConservativeResult.intersectWith(*MDRange, RangeType);
6930 auto CR = getRangeForUnknownRecurrence(U);
6931 ConservativeResult = ConservativeResult.intersectWith(CR);
6942 if (
U->getType()->isPointerTy()) {
6945 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
6946 int ptrIdxDiff = ptrSize -
BitWidth;
6947 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
6953 if (!
Known.Zero.getHiBits(NS).isZero())
6954 Known.Zero.setHighBits(NS);
6955 if (!
Known.One.getHiBits(NS).isZero())
6956 Known.One.setHighBits(NS);
6959 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
6960 ConservativeResult = ConservativeResult.intersectWith(
6961 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
6964 ConservativeResult = ConservativeResult.intersectWith(
6969 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6973 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
6974 DL, CanBeNull,
nullptr);
6990 ConservativeResult = ConservativeResult.intersectWith(
7000 return getRangeRef(AR, SignHint,
Depth + 1);
7004 ConstantRange RangeFromOps(
BitWidth,
false);
7006 for (
const auto &
Op :
Phi->operands()) {
7008 RangeFromOps = RangeFromOps.unionWith(OpRange);
7010 if (RangeFromOps.isFullSet())
7013 ConservativeResult =
7014 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7020 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7022 ConservativeResult = ConservativeResult.difference(Disallowed);
7025 return setRange(U, SignHint, std::move(ConservativeResult));
7031 return setRange(S, SignHint, std::move(ConservativeResult));
7039static std::pair<ConstantRange, bool>
7047 if (Step == 0 || MaxBECount == 0)
7048 return {StartRange,
true};
7054 return {ConstantRange::getFull(
BitWidth),
false};
7070 return {ConstantRange::getFull(
BitWidth),
false};
7083 APInt MovedBoundary;
7088 MovedBoundary = StartLower - std::move(
Offset);
7091 MovedBoundary = StartUpper + std::move(
Offset);
7095 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7102 if (StartRange.
contains(MovedBoundary))
7103 return {ConstantRange::getFull(
BitWidth),
false};
7106 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7108 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7116std::pair<ConstantRange, SCEV::NoWrapFlags>
7117ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7118 const APInt &MaxBECount) {
7122 "mismatched bit widths");
7131 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7133 StartSRange, MaxBECount,
7135 ConstantRange SR = SR1.unionWith(SR2);
7152ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7154 ScalarEvolution::RangeSignHint SignHint) {
7155 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7157 "This only works for non-self-wrapping AddRecs!");
7158 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7162 return ConstantRange::getFull(
BitWidth);
7170 return ConstantRange::getFull(
BitWidth);
7174 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7176 MaxItersWithoutWrap))
7177 return ConstantRange::getFull(
BitWidth);
7198 ConstantRange StartRange = getRangeRef(Start, SignHint);
7199 ConstantRange EndRange = getRangeRef(End, SignHint);
7200 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7204 return RangeBetween;
7209 return ConstantRange::getFull(
BitWidth);
7212 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7213 return RangeBetween;
7215 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7216 return RangeBetween;
7217 return ConstantRange::getFull(
BitWidth);
7222 const APInt &MaxBECount) {
7229 "mismatched bit widths");
7231 struct SelectPattern {
7232 Value *Condition =
nullptr;
7236 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7238 std::optional<unsigned> CastOp;
7252 CastOp = SCast->getSCEVType();
7253 S = SCast->getOperand();
7256 using namespace llvm::PatternMatch;
7263 Condition =
nullptr;
7295 bool isRecognized() {
return Condition !=
nullptr; }
7298 SelectPattern StartPattern(*
this,
BitWidth, Start);
7299 if (!StartPattern.isRecognized())
7300 return ConstantRange::getFull(
BitWidth);
7302 SelectPattern StepPattern(*
this,
BitWidth, Step);
7303 if (!StepPattern.isRecognized())
7304 return ConstantRange::getFull(
BitWidth);
7306 if (StartPattern.Condition != StepPattern.Condition) {
7310 return ConstantRange::getFull(
BitWidth);
7321 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7322 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7323 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7324 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7326 ConstantRange TrueRange =
7327 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7328 ConstantRange FalseRange =
7329 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7341 PDI && PDI->isDisjoint()) {
7356ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7369 SmallPtrSet<const SCEV *, 16> Visited;
7371 auto pushOp = [&](
const SCEV *S) {
7372 if (!Visited.
insert(S).second)
7375 if (Visited.
size() > 30) {
7386 while (!Worklist.
empty()) {
7388 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7389 if (!Bound || DT.dominates(Bound, DefI))
7396 return Bound ? Bound : &*F.getEntryBlock().begin();
7402 return getDefiningScopeBound(
Ops, Discard);
7405bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7407 if (
A->getParent() ==
B->getParent() &&
7412 auto *BLoop = LI.getLoopFor(
B->getParent());
7413 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7414 BLoop->getLoopPreheader() ==
A->getParent() &&
7416 A->getParent()->end()) &&
7424 SCEVPoisonCollector PC(
true);
7426 return PC.MaybePoison.
empty();
7429bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7439bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7456 for (
const Use &
Op :
I->operands()) {
7462 auto *DefI = getDefiningScopeBound(SCEVOps);
7463 return isGuaranteedToTransferExecutionTo(DefI,
I);
7466bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7468 if (isSCEVExprNeverPoison(
I))
7479 auto *ExitingBB =
L->getExitingBlock();
7483 SmallPtrSet<const Value *, 16> KnownPoison;
7492 while (!Worklist.
empty()) {
7495 for (
const Use &U :
Poison->uses()) {
7498 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7502 if (KnownPoison.
insert(PoisonUser).second)
7510ScalarEvolution::LoopProperties
7511ScalarEvolution::getLoopProperties(
const Loop *L) {
7512 using LoopProperties = ScalarEvolution::LoopProperties;
7514 auto Itr = LoopPropertiesCache.find(L);
7515 if (Itr == LoopPropertiesCache.end()) {
7518 return !
SI->isSimple();
7528 return I->mayWriteToMemory();
7531 LoopProperties LP = {
true,
7534 for (
auto *BB :
L->getBlocks())
7535 for (
auto &
I : *BB) {
7537 LP.HasNoAbnormalExits =
false;
7538 if (HasSideEffects(&
I))
7539 LP.HasNoSideEffects =
false;
7540 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7544 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7545 assert(InsertPair.second &&
"We just checked!");
7546 Itr = InsertPair.first;
7559const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7565 Stack.emplace_back(V,
false);
7566 while (!Stack.empty()) {
7567 auto E = Stack.back();
7568 Value *CurV = E.getPointer();
7576 const SCEV *CreatedSCEV =
nullptr;
7579 CreatedSCEV = createSCEV(CurV);
7584 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7588 insertValueToMap(CurV, CreatedSCEV);
7591 Stack.back().setInt(
true);
7594 Stack.emplace_back(
Op,
false);
7611 if (!DT.isReachableFromEntry(
I->getParent()))
7624 switch (BO->Opcode) {
7625 case Instruction::Add:
7626 case Instruction::Mul: {
7633 Ops.push_back(BO->
Op);
7637 Ops.push_back(BO->RHS);
7641 (BO->Opcode == Instruction::Add &&
7642 (NewBO->Opcode != Instruction::Add &&
7643 NewBO->Opcode != Instruction::Sub)) ||
7644 (BO->Opcode == Instruction::Mul &&
7645 NewBO->Opcode != Instruction::Mul)) {
7646 Ops.push_back(BO->LHS);
7651 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7654 Ops.push_back(BO->LHS);
7662 case Instruction::Sub:
7663 case Instruction::UDiv:
7664 case Instruction::URem:
7666 case Instruction::AShr:
7667 case Instruction::Shl:
7668 case Instruction::Xor:
7672 case Instruction::And:
7673 case Instruction::Or:
7677 case Instruction::LShr:
7684 Ops.push_back(BO->LHS);
7685 Ops.push_back(BO->RHS);
7689 switch (
U->getOpcode()) {
7690 case Instruction::Trunc:
7691 case Instruction::ZExt:
7692 case Instruction::SExt:
7693 case Instruction::PtrToAddr:
7694 case Instruction::PtrToInt:
7695 Ops.push_back(
U->getOperand(0));
7698 case Instruction::BitCast:
7700 Ops.push_back(
U->getOperand(0));
7705 case Instruction::SDiv:
7706 case Instruction::SRem:
7707 Ops.push_back(
U->getOperand(0));
7708 Ops.push_back(
U->getOperand(1));
7711 case Instruction::GetElementPtr:
7713 "GEP source element type must be sized");
7717 case Instruction::IntToPtr:
7720 case Instruction::PHI:
7751 Ops.push_back(CondICmp->getOperand(0));
7752 Ops.push_back(CondICmp->getOperand(1));
7772 case Instruction::Select: {
7774 auto CanSimplifyToUnknown = [
this,
U]() {
7792 if (CanSimplifyToUnknown())
7799 case Instruction::Call:
7800 case Instruction::Invoke:
7807 switch (
II->getIntrinsicID()) {
7808 case Intrinsic::abs:
7809 Ops.push_back(
II->getArgOperand(0));
7811 case Intrinsic::umax:
7812 case Intrinsic::umin:
7813 case Intrinsic::smax:
7814 case Intrinsic::smin:
7815 case Intrinsic::usub_sat:
7816 case Intrinsic::uadd_sat:
7817 Ops.push_back(
II->getArgOperand(0));
7818 Ops.push_back(
II->getArgOperand(1));
7820 case Intrinsic::start_loop_iterations:
7821 case Intrinsic::annotation:
7822 case Intrinsic::ptr_annotation:
7823 Ops.push_back(
II->getArgOperand(0));
7835const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7844 if (!DT.isReachableFromEntry(
I->getParent()))
7859 switch (BO->Opcode) {
7860 case Instruction::Add: {
7886 if (BO->Opcode == Instruction::Sub)
7894 if (BO->Opcode == Instruction::Sub)
7901 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7902 NewBO->Opcode != Instruction::Sub)) {
7912 case Instruction::Mul: {
7933 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7942 case Instruction::UDiv:
7946 case Instruction::URem:
7950 case Instruction::Sub: {
7953 Flags = getNoWrapFlagsFromUB(BO->
Op);
7958 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
7961 if (HasPtrLHS || HasPtrRHS) {
7966 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
7967 bool BothPtr) ->
const SCEV * {
7970 const SCEV *PtrSCEV =
getSCEV(PtrOp);
7980 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
7981 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
7989 case Instruction::And:
7995 if (CI->isMinusOne())
7997 const APInt &
A = CI->getValue();
8003 unsigned LZ =
A.countl_zero();
8004 unsigned TZ =
A.countr_zero();
8009 APInt EffectiveMask =
8011 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
8014 const SCEV *ShiftedLHS =
nullptr;
8018 unsigned MulZeros = OpC->getAPInt().countr_zero();
8019 unsigned GCD = std::min(MulZeros, TZ);
8024 const SCEV *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8046 case Instruction::Or:
8055 case Instruction::Xor:
8058 if (CI->isMinusOne())
8067 if (LBO->getOpcode() == Instruction::And &&
8068 LCI->getValue() == CI->getValue())
8069 if (
const SCEVZeroExtendExpr *Z =
8072 const SCEV *Z0 =
Z->getOperand();
8079 if (CI->getValue().isMask(Z0TySize))
8085 APInt Trunc = CI->getValue().trunc(Z0TySize);
8094 case Instruction::Shl:
8112 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8121 ConstantInt *
X = ConstantInt::get(
8127 case Instruction::AShr:
8149 const SCEV *AddTruncateExpr =
nullptr;
8150 ConstantInt *ShlAmtCI =
nullptr;
8151 const SCEV *AddConstant =
nullptr;
8153 if (L &&
L->getOpcode() == Instruction::Add) {
8161 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8168 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8176 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8181 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8186 if (AddTruncateExpr && ShlAmtCI) {
8198 const APInt &ShlAmt = ShlAmtCI->
getValue();
8202 const SCEV *CompositeExpr =
8204 if (
L->getOpcode() != Instruction::Shl)
8205 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8214 switch (
U->getOpcode()) {
8215 case Instruction::Trunc:
8218 case Instruction::ZExt:
8221 case Instruction::SExt:
8231 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8232 Type *Ty =
U->getType();
8240 case Instruction::BitCast:
8246 case Instruction::PtrToAddr: {
8253 case Instruction::PtrToInt:
8257 case Instruction::IntToPtr:
8261 case Instruction::SDiv:
8268 case Instruction::SRem:
8275 case Instruction::GetElementPtr:
8278 case Instruction::PHI:
8281 case Instruction::Select:
8282 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8285 case Instruction::Call:
8286 case Instruction::Invoke:
8291 switch (
II->getIntrinsicID()) {
8292 case Intrinsic::abs:
8296 case Intrinsic::umax:
8300 case Intrinsic::umin:
8304 case Intrinsic::smax:
8308 case Intrinsic::smin:
8312 case Intrinsic::usub_sat: {
8313 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8314 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8318 case Intrinsic::uadd_sat: {
8319 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8320 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8324 case Intrinsic::start_loop_iterations:
8325 case Intrinsic::annotation:
8326 case Intrinsic::ptr_annotation:
8330 case Intrinsic::vscale:
8350 auto *ExitCountType = ExitCount->
getType();
8351 assert(ExitCountType->isIntegerTy());
8353 1 + ExitCountType->getScalarSizeInBits());
8366 auto CanAddOneWithoutOverflow = [&]() {
8368 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8379 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8409 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8410 assert(L->isLoopExiting(ExitingBlock) &&
8411 "Exiting block must actually branch out of the loop!");
8420 const auto *MaxExitCount =
8428 L->getExitingBlocks(ExitingBlocks);
8431 if (ExitingBlocks.
empty() ||
8447 const LoopGuards &Guards) {
8451 const SCEV *TCExpr =
8459 : (
unsigned)Multiple.getZExtValue();
8463 const SCEV *ExitCount) {
8485 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8486 assert(L->isLoopExiting(ExitingBlock) &&
8487 "Exiting block must actually branch out of the loop!");
8497 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8499 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8501 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8511 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8514 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8517 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8525 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8532 return getBackedgeTakenInfo(L).getExact(L,
this);
8534 return getBackedgeTakenInfo(L).getConstantMax(
this);
8536 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8543 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8548 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8552 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8562 for (
PHINode &PN : Header->phis())
8563 if (Visited.
insert(&PN).second)
8567ScalarEvolution::BackedgeTakenInfo &
8568ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8569 auto &BTI = getBackedgeTakenInfo(L);
8570 if (BTI.hasFullInfo())
8573 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8576 return Pair.first->second;
8578 BackedgeTakenInfo
Result =
8579 computeBackedgeTakenCount(L,
true);
8581 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8584ScalarEvolution::BackedgeTakenInfo &
8585ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8591 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8592 BackedgeTakenCounts.try_emplace(L);
8594 return Pair.first->second;
8599 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8606 if (
Result.hasAnyInfo()) {
8609 auto LoopUsersIt = LoopUsers.find(L);
8610 if (LoopUsersIt != LoopUsers.end())
8612 forgetMemoizedResults(ToForget);
8615 for (PHINode &PN :
L->getHeader()->phis())
8616 ConstantEvolutionLoopExitValue.erase(&PN);
8624 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8633 BackedgeTakenCounts.clear();
8634 PredicatedBackedgeTakenCounts.clear();
8635 BECountUsers.clear();
8636 LoopPropertiesCache.clear();
8637 ConstantEvolutionLoopExitValue.clear();
8638 ValueExprMap.clear();
8639 ValuesAtScopes.clear();
8640 ValuesAtScopesUsers.clear();
8641 LoopDispositions.clear();
8642 BlockDispositions.clear();
8643 UnsignedRanges.clear();
8644 SignedRanges.clear();
8645 ExprValueMap.clear();
8647 ConstantMultipleCache.clear();
8648 PredicatedSCEVRewrites.clear();
8650 FoldCacheUser.clear();
8652void ScalarEvolution::visitAndClearUsers(
8656 while (!Worklist.
empty()) {
8663 if (It != ValueExprMap.
end()) {
8665 eraseValueFromMap(It->first);
8667 ConstantEvolutionLoopExitValue.erase(PN);
8681 while (!LoopWorklist.
empty()) {
8685 forgetBackedgeTakenCounts(CurrL,
false);
8686 forgetBackedgeTakenCounts(CurrL,
true);
8689 PredicatedSCEVRewrites.remove_if(
8690 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8692 auto LoopUsersItr = LoopUsers.find(CurrL);
8693 if (LoopUsersItr != LoopUsers.end())
8698 visitAndClearUsers(Worklist, Visited, ToForget);
8700 LoopPropertiesCache.erase(CurrL);
8703 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8705 forgetMemoizedResults(ToForget);
8722 visitAndClearUsers(Worklist, Visited, ToForget);
8724 forgetMemoizedResults(ToForget);
8735 visitAndClearUsers(Worklist, Visited, ToForget);
8737 forgetMemoizedResults(ToForget);
8745 auto InvalidateValue = [&](
Value *Val) {
8749 struct InvalidationRootCollector {
8753 InvalidationRootCollector(
Loop *L) : L(L) {}
8755 bool follow(
const SCEV *S) {
8761 if (L->contains(AddRec->
getLoop()))
8766 bool isDone()
const {
return false; }
8769 InvalidationRootCollector
C(L);
8771 forgetMemoizedResults(
C.Roots);
8794 BlockDispositions.clear();
8795 LoopDispositions.clear();
8812 while (!Worklist.
empty()) {
8814 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8815 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8816 if (!LoopDispoRemoved && !BlockDispoRemoved)
8818 auto Users = SCEVUsers.find(Curr);
8819 if (
Users != SCEVUsers.end())
8832const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8836 if (!isComplete() || ExitNotTaken.
empty())
8847 for (
const auto &ENT : ExitNotTaken) {
8848 const SCEV *BECount = ENT.ExactNotTaken;
8851 "We should only have known counts for exiting blocks that dominate "
8854 Ops.push_back(BECount);
8859 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8860 "Predicate should be always true!");
8869const ScalarEvolution::ExitNotTakenInfo *
8870ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8871 const BasicBlock *ExitingBlock,
8872 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8873 for (
const auto &ENT : ExitNotTaken)
8874 if (ENT.ExitingBlock == ExitingBlock) {
8875 if (ENT.hasAlwaysTruePredicate())
8877 else if (Predicates) {
8887const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8889 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8890 if (!getConstantMax())
8893 for (
const auto &ENT : ExitNotTaken)
8894 if (!ENT.hasAlwaysTruePredicate()) {
8902 "No point in having a non-constant max backedge taken count!");
8903 return getConstantMax();
8906const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8908 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8916 for (
const auto &ENT : ExitNotTaken) {
8917 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8920 "We should only have known counts for exiting blocks that "
8926 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8927 "Predicate should be always true!");
8930 if (ExitCounts.
empty())
8939bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8941 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8942 return !ENT.hasAlwaysTruePredicate();
8944 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8960 this->ExactNotTaken = E = ConstantMaxNotTaken;
8961 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8966 "Exact is not allowed to be less precise than Constant Max");
8969 "Exact is not allowed to be less precise than Symbolic Max");
8972 "Symbolic Max is not allowed to be less precise than Constant Max");
8975 "No point in having a non-constant max backedge taken count!");
8977 for (
const auto PredList : PredLists)
8978 for (
const auto *
P : PredList) {
8986 "Backedge count should be int");
8989 "Max backedge count should be int");
9002ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
9004 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
9005 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
9006 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9008 ExitNotTaken.reserve(ExitCounts.
size());
9009 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
9010 std::back_inserter(ExitNotTaken),
9011 [&](
const EdgeExitInfo &EEI) {
9012 BasicBlock *ExitBB = EEI.first;
9013 const ExitLimit &EL = EEI.second;
9014 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
9015 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
9020 "No point in having a non-constant max backedge taken count!");
9024ScalarEvolution::BackedgeTakenInfo
9025ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
9026 bool AllowPredicates) {
9028 L->getExitingBlocks(ExitingBlocks);
9030 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9033 bool CouldComputeBECount =
true;
9035 const SCEV *MustExitMaxBECount =
nullptr;
9036 const SCEV *MayExitMaxBECount =
nullptr;
9037 bool MustExitMaxOrZero =
false;
9038 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9049 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9050 if (ExitIfTrue == CI->
isZero())
9054 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9056 assert((AllowPredicates || EL.Predicates.empty()) &&
9057 "Predicated exit limit when predicates are not allowed!");
9062 ++NumExitCountsComputed;
9066 CouldComputeBECount =
false;
9073 "Exact is known but symbolic isn't?");
9074 ++NumExitCountsNotComputed;
9089 DT.dominates(ExitBB, Latch)) {
9090 if (!MustExitMaxBECount) {
9091 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9092 MustExitMaxOrZero = EL.MaxOrZero;
9095 EL.ConstantMaxNotTaken);
9099 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9102 EL.ConstantMaxNotTaken);
9106 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9110 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9116 for (
const auto &Pair : ExitCounts) {
9118 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9120 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9121 {
L, AllowPredicates});
9123 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9124 MaxBECount, MaxOrZero);
9127ScalarEvolution::ExitLimit
9128ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9129 bool IsOnlyExit,
bool AllowPredicates) {
9130 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9134 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9139 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9140 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9141 "It should have one successor in loop and one exit block!");
9152 if (!
L->contains(SBB)) {
9157 assert(Exit &&
"Exiting block must have at least one exit");
9158 return computeExitLimitFromSingleExitSwitch(
9159 L, SI, Exit, IsOnlyExit);
9166 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9167 bool AllowPredicates) {
9168 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9169 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9170 ControlsOnlyExit, AllowPredicates);
9173std::optional<ScalarEvolution::ExitLimit>
9174ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9175 bool ExitIfTrue,
bool ControlsOnlyExit,
9176 bool AllowPredicates) {
9178 (void)this->ExitIfTrue;
9179 (void)this->AllowPredicates;
9181 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9182 this->AllowPredicates == AllowPredicates &&
9183 "Variance in assumed invariant key components!");
9184 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9185 if (Itr == TripCountMap.end())
9186 return std::nullopt;
9190void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9192 bool ControlsOnlyExit,
9193 bool AllowPredicates,
9195 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9196 this->AllowPredicates == AllowPredicates &&
9197 "Variance in assumed invariant key components!");
9199 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9200 assert(InsertResult.second &&
"Expected successful insertion!");
9205ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9206 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9207 bool ControlsOnlyExit,
bool AllowPredicates) {
9209 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9213 ExitLimit EL = computeExitLimitFromCondImpl(
9214 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9215 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9219ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9220 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9221 bool ControlsOnlyExit,
bool AllowPredicates) {
9223 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9224 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9225 return *LimitFromBinOp;
9231 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9232 if (EL.hasFullInfo() || !AllowPredicates)
9236 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9256 const WithOverflowInst *WO;
9271 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9272 ControlsOnlyExit, AllowPredicates);
9273 if (EL.hasAnyInfo())
9278 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9281std::optional<ScalarEvolution::ExitLimit>
9282ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9286 bool AllowPredicates) {
9295 return std::nullopt;
9299 ExitLimit EL0 = computeExitLimitFromCondCached(
9300 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9301 ExitLimit EL1 = computeExitLimitFromCondCached(
9302 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9307 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9312 if (EitherMayExit) {
9322 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9324 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9327 EL1.ConstantMaxNotTaken);
9329 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9331 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9334 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9338 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9339 BECount = EL0.ExactNotTaken;
9352 SymbolicMaxBECount =
9354 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9358ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9359 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9360 bool AllowPredicates) {
9372 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9374 if (EL.hasAnyInfo())
9377 auto *ExhaustiveCount =
9378 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9381 return ExhaustiveCount;
9383 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9386ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9388 bool ControlsOnlyExit,
bool AllowPredicates) {
9413 ConstantRange CompRange =
9431 InnerLHS = ZExt->getOperand();
9478 if (EL.hasAnyInfo())
9495 if (EL.hasAnyInfo())
return EL;
9527 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9529 if (EL.hasAnyInfo())
9545 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9547 if (EL.hasAnyInfo())
9558ScalarEvolution::ExitLimit
9559ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9561 BasicBlock *ExitingBlock,
9562 bool ControlsOnlyExit) {
9563 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9566 if (
Switch->getDefaultDest() == ExitingBlock)
9570 "Default case must not exit the loop!");
9576 if (EL.hasAnyInfo())
9588 "Evaluation of SCEV at constant didn't fold correctly?");
9592ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9602 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9609 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9611 unsigned &OutShiftAmt) {
9612 using namespace PatternMatch;
9614 ConstantInt *ShiftAmt;
9616 OutOpCode = Instruction::LShr;
9618 OutOpCode = Instruction::AShr;
9620 OutOpCode = Instruction::Shl;
9625 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9640 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9642 unsigned &ShiftAmtOut) {
9643 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9659 if (MatchPositiveShift(
LHS, V, OpC, Amt)) {
9660 PostShiftOpCode = OpC;
9666 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9669 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9675 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9682 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9688 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9700 ConstantInt *StableValue =
nullptr;
9705 case Instruction::AShr: {
9712 if (
Known.isNonNegative())
9713 StableValue = ConstantInt::get(Ty, 0);
9714 else if (
Known.isNegative())
9715 StableValue = ConstantInt::get(Ty, -1,
true);
9721 case Instruction::LShr:
9722 case Instruction::Shl:
9732 "Otherwise cannot be an operand to a branch instruction");
9734 if (
Result->isNullValue()) {
9743 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9745 const SCEV *StartSCEV =
getSCEV(StartValue);
9749 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9750 MaxBTC = std::min(MaxBTC, RangeBTC);
9754 const SCEV *UpperBound =
9772 if (
const Function *
F = CI->getCalledFunction())
9782 if (!L->contains(
I))
return false;
9787 return L->getHeader() ==
I->getParent();
9866 if (!
I)
return nullptr;
9880 std::vector<Constant*>
Operands(
I->getNumOperands());
9882 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9891 if (!
C)
return nullptr;
9913 if (IncomingVal != CurrentVal) {
9916 IncomingVal = CurrentVal;
9928ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9931 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9940 DenseMap<Instruction *, Constant *> CurrentIterVals;
9942 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9948 for (PHINode &
PHI : Header->phis()) {
9950 CurrentIterVals[&
PHI] = StartCST;
9952 if (!CurrentIterVals.
count(PN))
9953 return RetVal =
nullptr;
9959 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9962 unsigned IterationNum = 0;
9964 for (; ; ++IterationNum) {
9965 if (IterationNum == NumIterations)
9966 return RetVal = CurrentIterVals[PN];
9970 DenseMap<Instruction *, Constant *> NextIterVals;
9975 NextIterVals[PN] = NextPHI;
9977 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9983 for (
const auto &
I : CurrentIterVals) {
9985 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9990 for (
const auto &
I : PHIsToCompute) {
9991 PHINode *
PHI =
I.first;
9994 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9997 if (NextPHI !=
I.second)
9998 StoppedEvolving =
false;
10003 if (StoppedEvolving)
10004 return RetVal = CurrentIterVals[PN];
10006 CurrentIterVals.swap(NextIterVals);
10010const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
10020 DenseMap<Instruction *, Constant *> CurrentIterVals;
10022 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10025 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
10027 for (PHINode &
PHI : Header->phis()) {
10029 CurrentIterVals[&
PHI] = StartCST;
10031 if (!CurrentIterVals.
count(PN))
10039 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10046 if (CondVal->getValue() ==
uint64_t(ExitWhen)) {
10047 ++NumBruteForceTripCountsComputed;
10052 DenseMap<Instruction *, Constant *> NextIterVals;
10058 for (
const auto &
I : CurrentIterVals) {
10060 if (!
PHI ||
PHI->getParent() != Header)
continue;
10063 for (PHINode *
PHI : PHIsToCompute) {
10065 if (NextPHI)
continue;
10067 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10070 CurrentIterVals.
swap(NextIterVals);
10078 auto &
Values = ValuesAtScopes[V];
10082 return LS.second ? LS.second :
SCEVUse(V);
10084 Values.emplace_back(L,
nullptr);
10087 SCEVUse C = computeSCEVAtScope(V, L);
10088 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10089 if (LS.first == L) {
10095 ValuesAtScopesUsers[
C.getPointer()].push_back({L, V});
10106 switch (V->getSCEVType()) {
10139 assert(!
C->getType()->isPointerTy() &&
10140 "Can only have one pointer, and it must be last");
10165const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10166 SmallVectorImpl<SCEVUse> &NewOps) {
10200SCEVUse ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10201 switch (
V->getSCEVType()) {
10212 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10223 for (++i; i !=
e; ++i)
10263 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10273 for (++i; i !=
e; ++i) {
10278 return getWithOperands(V, NewOps);
10293 const Loop *CurrLoop = this->LI[
I->getParent()];
10304 if (BackedgeTakenCount->
isZero()) {
10305 Value *InitValue =
nullptr;
10306 bool MultipleInitValues =
false;
10312 MultipleInitValues =
true;
10317 if (!MultipleInitValues && InitValue)
10326 unsigned InLoopPred =
10337 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10351 SmallVector<Constant *, 4>
Operands;
10353 bool MadeImprovement =
false;
10368 MadeImprovement |= OrigV != OpV;
10373 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10378 if (!MadeImprovement)
10399const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10401 return stripInjectiveFunctions(ZExt->getOperand());
10403 return stripInjectiveFunctions(SExt->getOperand());
10421 assert(
A != 0 &&
"A must be non-zero.");
10437 if (MinTZ < Mult2 && L->getLoopPredecessor())
10439 if (MinTZ < Mult2) {
10462 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10482static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10488 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10489 << *AddRec <<
'\n');
10492 if (!LC || !MC || !
NC) {
10493 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10494 return std::nullopt;
10500 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10508 N =
N.sext(NewWidth);
10509 M = M.sext(NewWidth);
10510 L = L.sext(NewWidth);
10527 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10528 <<
", multiplied by " <<
T <<
'\n');
10537 std::optional<APInt>
Y) {
10539 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10542 return XW.
slt(YW) ? *
X : *
Y;
10545 return std::nullopt;
10546 return X ? *
X : *
Y;
10563 return std::nullopt;
10564 unsigned W =
X->getBitWidth();
10584static std::optional<APInt>
10590 return std::nullopt;
10593 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10594 std::optional<APInt>
X =
10597 return std::nullopt;
10602 return std::nullopt;
10617static std::optional<APInt>
10621 "Starting value of addrec should be 0");
10622 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10623 <<
Range <<
", addrec " << *AddRec <<
'\n');
10627 "Addrec's initial value should be in range");
10633 return std::nullopt;
10643 auto SolveForBoundary =
10644 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10647 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10648 << Bound <<
" (before multiplying by " << M <<
")\n");
10651 std::optional<APInt> SO;
10654 "signed overflow\n");
10658 "unsigned overflow\n");
10659 std::optional<APInt> UO =
10662 auto LeavesRange = [&] (
const APInt &
X) {
10665 if (
Range.contains(V0->getValue()))
10670 if (
Range.contains(
V1->getValue()))
10679 return {std::nullopt,
false};
10684 if (LeavesRange(*Min))
10685 return { Min,
true };
10686 std::optional<APInt> Max = Min == SO ? UO : SO;
10687 if (LeavesRange(*Max))
10688 return { Max,
true };
10691 return {std::nullopt,
true};
10698 auto SL = SolveForBoundary(
Lower);
10699 auto SU = SolveForBoundary(
Upper);
10702 if (!SL.second || !SU.second)
10703 return std::nullopt;
10746ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10748 bool ControlsOnlyExit,
10749 bool AllowPredicates) {
10760 if (
C->getValue()->isZero())
return C;
10764 const SCEVAddRecExpr *AddRec =
10767 if (!AddRec && AllowPredicates)
10773 if (!AddRec || AddRec->
getLoop() != L)
10784 return ExitLimit(R, R, R,
false, Predicates);
10842 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10872 const SCEV *
Exact =
10880 const SCEV *SymbolicMax =
10882 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10891 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10899 return ExitLimit(
E, M, S,
false, Predicates);
10902ScalarEvolution::ExitLimit
10903ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10911 if (!
C->getValue()->isZero())
10921std::pair<const BasicBlock *, const BasicBlock *>
10922ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10933 if (
const Loop *L = LI.getLoopFor(BB))
10934 return {
L->getLoopPredecessor(),
L->getHeader()};
10936 return {
nullptr, BB};
10945 if (
A ==
B)
return true;
10960 if (ComputesEqualValues(AI, BI))
10968 const SCEV *Op0, *Op1;
10987 auto TrivialCase = [&](
bool TriviallyTrue) {
10996 const SCEV *NewLHS, *NewRHS;
11020 return TrivialCase(
false);
11021 return TrivialCase(
true);
11040 RAdd->hasNoSignedWrap()) ||
11042 RAdd->hasNoUnsignedWrap())) {
11062 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
11063 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
11066 C->getAPInt().isStrictlyPositive()) ||
11090 const APInt &
RA = RC->getAPInt();
11092 bool SimplifiedByConstantRange =
false;
11097 return TrivialCase(
true);
11099 return TrivialCase(
false);
11108 Changed = SimplifiedByConstantRange =
true;
11112 if (!SimplifiedByConstantRange) {
11129 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11135 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11141 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11147 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11167 return TrivialCase(
true);
11169 return TrivialCase(
false);
11274 auto NonRecursive = [OrNegative](
const SCEV *S) {
11276 return C->getAPInt().isPowerOf2() ||
11277 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11283 if (NonRecursive(S))
11293 const SCEV *S, uint64_t M,
11302 APInt C = Cst->getAPInt();
11303 return C.urem(M) == 0;
11309 const SCEV *SmodM =
11330 [&](
SCEVUse Op) { return isKnownMultipleOf(Op, M, Predicates); }))
11337 return isKnownMultipleOf(Op, M, Predicates);
11343 return isKnownMultipleOf(Op, M, Predicates);
11350 for (
auto *
A : *Predicates)
11351 if (
A->implies(
P, *
this))
11364std::pair<const SCEV *, const SCEV *>
11367 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11369 return { Start, Start };
11371 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11380 getUsedLoops(LHS, LoopsUsed);
11381 getUsedLoops(RHS, LoopsUsed);
11383 if (LoopsUsed.
empty())
11388 for (
const auto *L1 : LoopsUsed)
11389 for (
const auto *L2 : LoopsUsed)
11390 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11391 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11392 "Domination relationship is not a linear order");
11422 SplitRHS.second) &&
11432 isKnownPredicateViaSplitting(Pred, LHS, RHS) ||
11433 isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11443 return std::nullopt;
11458 if (KnownWithoutContext)
11459 return KnownWithoutContext;
11466 return std::nullopt;
11472 const Loop *L = LHS->getLoop();
11477std::optional<ScalarEvolution::MonotonicPredicateType>
11480 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11486 auto ResultSwapped =
11489 assert(*ResultSwapped != *Result &&
11490 "monotonicity should flip as we flip the predicate");
11497std::optional<ScalarEvolution::MonotonicPredicateType>
11498ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11512 return std::nullopt;
11516 "Should be greater or less!");
11520 if (!LHS->hasNoUnsignedWrap())
11521 return std::nullopt;
11525 "Relational predicate is either signed or unsigned!");
11526 if (!
LHS->hasNoSignedWrap())
11527 return std::nullopt;
11529 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11537 return std::nullopt;
11540std::optional<ScalarEvolution::LoopInvariantPredicate>
11547 return std::nullopt;
11554 if (!ArLHS || ArLHS->
getLoop() != L)
11555 return std::nullopt;
11559 return std::nullopt;
11585 return std::nullopt;
11622 return std::nullopt;
11625std::optional<ScalarEvolution::LoopInvariantPredicate>
11630 Pred, LHS, RHS, L, CtxI, MaxIter))
11640 Pred, LHS, RHS, L, CtxI,
Op))
11642 return std::nullopt;
11645std::optional<ScalarEvolution::LoopInvariantPredicate>
11660 return std::nullopt;
11667 if (!AR || AR->
getLoop() != L)
11668 return std::nullopt;
11673 Pred = Pred.dropSameSign();
11677 return std::nullopt;
11683 if (Step != One && Step != MinusOne)
11684 return std::nullopt;
11690 return std::nullopt;
11696 return std::nullopt;
11704 if (Step == MinusOne)
11708 return std::nullopt;
11714bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11720 auto CheckRange = [&](
bool IsSigned) {
11723 return RangeLHS.
icmp(Pred, RangeRHS);
11732 if (CheckRange(
true) || CheckRange(
false))
11741bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11750 SCEVUse XNonConstOp, XConstOp;
11751 SCEVUse YNonConstOp, YConstOp;
11755 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11758 XFlagsPresent = ExpectedFlags;
11763 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11766 YFlagsPresent = ExpectedFlags;
11769 if (YNonConstOp != XNonConstOp)
11777 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11780 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11840bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11861bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11862 const SCEV *
LHS,
const SCEV *
RHS) {
11867 return any_of(*BB, [&](
const Instruction &
I) {
11868 using namespace llvm::PatternMatch;
11873 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11887 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11892 "This cannot be done on broken IR!");
11895 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11904 if (LoopContinuePredicate &&
11905 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11906 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11911 if (WalkingBEDominatingConds)
11917 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11918 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11925 const SCEV *LoopCounter =
11933 for (
auto &AssumeVH : AC.assumptions()) {
11940 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11944 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11947 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11948 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11949 assert(DTN &&
"should reach the loop header before reaching the root!");
11952 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11970 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
11983 if (!DT.isReachableFromEntry(BB))
11987 "This cannot be done on broken IR!");
11995 const bool ProvingStrictComparison =
11997 bool ProvedNonStrictComparison =
false;
11998 bool ProvedNonEquality =
false;
12001 if (!ProvedNonStrictComparison)
12002 ProvedNonStrictComparison = Fn(NonStrictPredicate);
12003 if (!ProvedNonEquality)
12005 if (ProvedNonStrictComparison && ProvedNonEquality)
12010 if (ProvingStrictComparison) {
12012 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
12014 if (SplitAndProve(ProofFn))
12019 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
12021 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
12023 if (ProvingStrictComparison) {
12025 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
12027 if (SplitAndProve(ProofFn))
12036 const Loop *ContainingLoop = LI.getLoopFor(BB);
12038 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
12042 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
12043 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
12046 if (!BlockEntryPredicate)
12055 for (
auto &AssumeVH : AC.assumptions()) {
12059 if (!DT.dominates(CI, BB))
12062 if (ProveViaCond(CI->getArgOperand(0),
false))
12068 F.getParent(), Intrinsic::experimental_guard);
12070 for (
const auto *GU : GuardDecl->users())
12072 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12073 if (ProveViaCond(Guard->getArgOperand(0),
false))
12088 "LHS is not available at Loop Entry");
12090 "RHS is not available at Loop Entry");
12092 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12103 if (FoundCondValue ==
12107 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12111 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12114 const Value *Op0, *Op1;
12117 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12121 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12122 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12126 if (!ICI)
return false;
12130 CmpPredicate FoundPred;
12139 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12142bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12143 const SCEV *
RHS, CmpPredicate FoundPred,
12144 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12145 const Instruction *CtxI) {
12155 auto *WideType = FoundLHS->
getType();
12167 TruncFoundLHS, TruncFoundRHS, CtxI))
12193 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12197bool ScalarEvolution::isImpliedCondBalancedTypes(
12202 "Types should be balanced!");
12209 if (FoundLHS == FoundRHS)
12213 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12225 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12242 LHS, FoundLHS, FoundRHS, CtxI);
12244 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12266 assert(P1 != P2 &&
"Handled earlier!");
12270 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12274 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12277 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12278 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12279 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12284 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12295 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12296 CanonicalRHS, CanonicalFoundLHS,
12297 CanonicalFoundRHS);
12302 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12303 CanonicalRHS, CanonicalFoundLHS,
12304 CanonicalFoundRHS);
12311 const SCEVConstant *
C =
nullptr;
12312 const SCEV *
V =
nullptr;
12330 if (Min ==
C->getAPInt()) {
12335 APInt SharperMin = Min + 1;
12338 case ICmpInst::ICMP_SGE:
12339 case ICmpInst::ICMP_UGE:
12342 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12347 case ICmpInst::ICMP_SGT:
12348 case ICmpInst::ICMP_UGT:
12358 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12363 case ICmpInst::ICMP_SLE:
12364 case ICmpInst::ICMP_ULE:
12365 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12366 LHS, V, getConstant(SharperMin), CtxI))
12370 case ICmpInst::ICMP_SLT:
12371 case ICmpInst::ICMP_ULT:
12372 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12373 LHS, V, getConstant(Min), CtxI))
12387 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12391 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12394 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12410std::optional<APInt>
12417 APInt DiffMul(BW, 1);
12420 for (
unsigned I = 0;
I < 8; ++
I) {
12429 if (LAR->getLoop() != MAR->getLoop())
12430 return std::nullopt;
12434 if (!LAR->isAffine() || !MAR->isAffine())
12435 return std::nullopt;
12437 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12438 return std::nullopt;
12440 Less = LAR->getStart();
12441 More = MAR->getStart();
12446 auto MatchConstMul =
12447 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12452 return std::nullopt;
12454 if (
auto MatchedMore = MatchConstMul(More)) {
12455 if (
auto MatchedLess = MatchConstMul(
Less)) {
12456 if (MatchedMore->second == MatchedLess->second) {
12457 More = MatchedMore->first;
12458 Less = MatchedLess->first;
12459 DiffMul *= MatchedMore->second;
12470 Diff +=
C->getAPInt() * DiffMul;
12473 Diff -=
C->getAPInt() * DiffMul;
12476 Multiplicity[S] +=
Mul;
12478 auto Decompose = [&](
const SCEV *S,
int Mul) {
12485 Decompose(More, 1);
12486 Decompose(
Less, -1);
12490 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12491 for (
const auto &[S,
Mul] : Multiplicity) {
12496 return std::nullopt;
12498 }
else if (
Mul == -1) {
12500 return std::nullopt;
12503 return std::nullopt;
12507 if (NewMore == More || NewLess ==
Less)
12508 return std::nullopt;
12514 if (!More && !
Less)
12518 if (!More || !
Less)
12519 return std::nullopt;
12523 return std::nullopt;
12526bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12548 const auto *Latch = L->getLoopLatch();
12551 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12560 const auto *Latch = L->getLoopLatch();
12563 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12573bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12576 const SCEV *FoundLHS,
12577 const SCEV *FoundRHS) {
12586 if (!AddRecFoundLHS)
12593 const Loop *
L = AddRecFoundLHS->getLoop();
12594 if (L != AddRecLHS->getLoop())
12633 if (!RDiff || *LDiff != *RDiff)
12636 if (LDiff->isMinValue())
12639 APInt FoundRHSLimit;
12642 FoundRHSLimit = -(*RDiff);
12654bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12655 const SCEV *
RHS,
const SCEV *FoundLHS,
12656 const SCEV *FoundRHS,
unsigned Depth) {
12657 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12661 bool Erased = PendingMerges.erase(LPhi);
12662 assert(Erased &&
"Failed to erase LPhi!");
12666 bool Erased = PendingMerges.erase(RPhi);
12667 assert(Erased &&
"Failed to erase RPhi!");
12675 if (!PendingMerges.insert(Phi).second)
12689 if (!PendingMerges.insert(Phi).second)
12695 if (!LPhi && !RPhi)
12706 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12710 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12711 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12712 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12713 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12716 if (RPhi && RPhi->getParent() == LBB) {
12723 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12724 if (!ProvedEasily(L, R))
12735 auto *RLoop = RAR->
getLoop();
12736 auto *Predecessor = RLoop->getLoopPredecessor();
12737 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12739 if (!ProvedEasily(L1, RAR->
getStart()))
12741 auto *Latch = RLoop->getLoopLatch();
12742 assert(Latch &&
"Loop with AddRec with no latch?");
12763 if (
auto *
Loop = LI.getLoopFor(LBB))
12766 if (!ProvedEasily(L,
RHS))
12773bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12776 const SCEV *FoundLHS,
12777 const SCEV *FoundRHS) {
12780 if (
RHS == FoundRHS) {
12785 if (
LHS != FoundLHS)
12792 Value *Shiftee, *ShiftValue;
12794 using namespace PatternMatch;
12795 if (
match(SUFoundRHS->getValue(),
12797 auto *ShifteeS =
getSCEV(Shiftee);
12815bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12816 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12817 const SCEV *FoundRHS) {
12849 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12857 return Diff == FoundDiff;
12860bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12862 const SCEV *FoundLHS,
12863 const SCEV *FoundRHS,
12864 const Instruction *CtxI) {
12865 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12867 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12869 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12870 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12872 isImpliedCondOperandsViaMatchingDiff(Pred,
LHS,
RHS, FoundLHS,
12874 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12878template <
typename MinMaxExprType>
12880 const SCEV *Candidate) {
12885 return is_contained(MinMaxExpr->operands(), Candidate);
12898 const SCEV *LStart, *RStart, *Step;
12996bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12998 const SCEV *FoundLHS,
12999 const SCEV *FoundRHS,
13003 "LHS and RHS have different sizes?");
13006 "FoundLHS and FoundRHS have different sizes?");
13040 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
13042 return Ext->getOperand();
13049 auto *OrigLHS =
LHS;
13050 auto *OrigFoundLHS = FoundLHS;
13051 LHS = GetOpFromSExt(
LHS);
13052 FoundLHS = GetOpFromSExt(FoundLHS);
13055 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
13058 FoundRHS,
Depth + 1);
13071 if (!LHSAddExpr->hasNoSignedWrap())
13074 SCEVUse LL = LHSAddExpr->getOperand(0);
13075 SCEVUse LR = LHSAddExpr->getOperand(1);
13079 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
13080 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
13085 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
13091 using namespace llvm::PatternMatch;
13110 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13118 auto *DTy = Denominator->getType();
13119 auto *FRHSTy = FoundRHS->
getType();
13120 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13139 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13150 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13152 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13160 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13193bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13197 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13201 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13204bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13207 const SCEV *FoundLHS,
13208 const SCEV *FoundRHS) {
13244 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13250bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13251 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13252 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13266 ConstantRange FoundLHSRange =
13270 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13277 return LHSRange.
icmp(Pred, ConstRHS);
13280bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13293 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13301 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13304bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
13316 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
13324 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
13336const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
13337 const SCEV *Stride,
13368 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13379 :
APIntOps::umax(MaxEnd, MinStart);
13386ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13387 const Loop *L,
bool IsSigned,
13388 bool ControlsOnlyExit,
bool AllowPredicates) {
13392 bool PredicatedIV =
false;
13397 auto canProveNUW = [&]() {
13400 if (!ControlsOnlyExit)
13421 Limit = Limit.
zext(OuterBitWidth);
13433 Type *Ty = ZExt->getType();
13444 if (!
IV && AllowPredicates) {
13449 PredicatedIV =
true;
13453 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13467 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13470 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13471 const SCEV *GuardedStride = Stride;
13474 bool IVMayOverflow =
true;
13478 if (!PositiveStride) {
13481 GuardedStride = LoopGuardedStride;
13482 PositiveStride =
true;
13489 if (!PositiveStride) {
13541 auto wouldZeroStrideBeUB = [&]() {
13553 if (!wouldZeroStrideBeUB()) {
13560 IVMayOverflow = canIVOverflowOnLT(
RHS, GuardedStride, IsSigned);
13561 if (IVMayOverflow && !NoWrap)
13574 const SCEV *
Start =
IV->getStart();
13580 const SCEV *OrigStart =
Start;
13581 const SCEV *OrigRHS =
RHS;
13582 if (
Start->getType()->isPointerTy()) {
13597 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13598 any(RHSAddRec->getNoWrapFlags())) {
13611 const SCEV *RHSStart = RHSAddRec->getStart();
13612 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13624 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13633 BECountIfBackedgeTaken =
13659 bool AddingStrideMinusOneMayOverflow = IVMayOverflow && [&] {
13705 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13718 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13725 if ((!AddingStrideMinusOneMayOverflow ||
13757 const SCEV *Numerator =
13763 auto canProveRHSGreaterThanEqualStart = [&]() {
13782 const SCEV *StartMinusOne =
13789 if (canProveRHSGreaterThanEqualStart()) {
13804 BECountIfBackedgeTaken =
13809 if (!AddingStrideMinusOneMayOverflow) {
13821 const SCEV *ConstantMaxBECount;
13822 bool MaxOrZero =
false;
13824 ConstantMaxBECount = BECount;
13829 ConstantMaxBECount = BECountIfBackedgeTaken;
13832 ConstantMaxBECount = computeMaxBECountForLT(
13840 const SCEV *SymbolicMaxBECount =
13842 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13846ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13847 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13848 bool ControlsOnlyExit,
bool AllowPredicates) {
13855 if (!
IV && AllowPredicates)
13862 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13866 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13879 bool MayAddOverflow =
false;
13880 const SCEV *
Start =
IV->getStart();
13881 const SCEV *End =
RHS;
13882 if (!Stride->
isOne() && canIVOverflowOnGT(
RHS, Stride, IsSigned)) {
13885 MayAddOverflow =
true;
13898 if (
Start->getType()->isPointerTy()) {
13910 const SCEV *BECount;
13911 if (MayAddOverflow) {
13942 const SCEV *ConstantMaxBECount =
13949 ConstantMaxBECount = BECount;
13950 const SCEV *SymbolicMaxBECount =
13953 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13959 if (
Range.isFullSet())
13964 if (!SC->getValue()->isZero()) {
13970 return ShiftedAddRec->getNumIterationsInRange(
13971 Range.subtract(SC->getAPInt()), SE);
14002 APInt ExitVal = (End +
A).udiv(
A);
14015 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
14016 "Linear scev computation is off in a bad way!");
14047 assert(!
Last->isZero() &&
"Recurrency with zero step?");
14081 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14083 SE->ConstantEvolutionLoopExitValue.erase(PN);
14084 SE->eraseValueFromMap(getValPtr());
14088void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
14089 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14099 : CallbackVH(
V), SE(se) {}
14108 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
14110 LoopDispositions(64), BlockDispositions(64) {
14122 F.getParent(), Intrinsic::experimental_guard);
14123 HasGuards = GuardDecl && !GuardDecl->use_empty();
14127 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
14128 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14129 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14130 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14131 PendingMerges(
std::
move(Arg.PendingMerges)),
14132 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14133 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14134 PredicatedBackedgeTakenCounts(
14135 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14136 BECountUsers(
std::
move(Arg.BECountUsers)),
14137 ConstantEvolutionLoopExitValue(
14138 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14139 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14140 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14141 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14142 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14143 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14144 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14145 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14146 SignedRanges(
std::
move(Arg.SignedRanges)),
14147 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14148 UniquePreds(
std::
move(Arg.UniquePreds)),
14149 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14150 ConstantSCEVs(
std::
move(Arg.ConstantSCEVs)),
14151 LoopUsers(
std::
move(Arg.LoopUsers)),
14152 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14153 FirstUnknown(Arg.FirstUnknown) {
14154 Arg.FirstUnknown =
nullptr;
14163 Tmp->~SCEVUnknown();
14165 FirstUnknown =
nullptr;
14167 ExprValueMap.clear();
14168 ValueExprMap.clear();
14170 BackedgeTakenCounts.clear();
14171 PredicatedBackedgeTakenCounts.clear();
14173 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14174 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14175 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14176 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14198 L->getHeader()->printAsOperand(OS,
false);
14202 L->getExitingBlocks(ExitingBlocks);
14203 if (ExitingBlocks.
size() != 1)
14204 OS <<
"<multiple exits> ";
14208 OS <<
"backedge-taken count is ";
14211 OS <<
"Unpredictable backedge-taken count.";
14214 if (ExitingBlocks.
size() > 1)
14215 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14216 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14224 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14227 OS <<
"\n Predicates:\n";
14228 for (
const auto *
P : Predicates)
14236 L->getHeader()->printAsOperand(OS,
false);
14241 OS <<
"constant max backedge-taken count is ";
14244 OS <<
", actual taken count either this or zero.";
14246 OS <<
"Unpredictable constant max backedge-taken count. ";
14251 L->getHeader()->printAsOperand(OS,
false);
14256 OS <<
"symbolic max backedge-taken count is ";
14259 OS <<
", actual taken count either this or zero.";
14261 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14265 if (ExitingBlocks.
size() > 1)
14266 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14267 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14277 OS <<
"\n predicated symbolic max exit count for "
14278 << ExitingBlock->
getName() <<
": ";
14280 OS <<
"\n Predicates:\n";
14281 for (
const auto *
P : Predicates)
14292 L->getHeader()->printAsOperand(OS,
false);
14295 OS <<
"Predicated backedge-taken count is ";
14298 OS <<
"Unpredictable predicated backedge-taken count.";
14300 OS <<
" Predicates:\n";
14301 for (
const auto *
P : Preds)
14306 auto *PredConstantMax =
14308 if (PredConstantMax != ConstantBTC) {
14310 L->getHeader()->printAsOperand(OS,
false);
14313 OS <<
"Predicated constant max backedge-taken count is ";
14316 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14318 OS <<
" Predicates:\n";
14319 for (
const auto *
P : Preds)
14324 auto *PredSymbolicMax =
14326 if (SymbolicBTC != PredSymbolicMax) {
14328 L->getHeader()->printAsOperand(OS,
false);
14331 OS <<
"Predicated symbolic max backedge-taken count is ";
14334 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14336 OS <<
" Predicates:\n";
14337 for (
const auto *
P : Preds)
14343 L->getHeader()->printAsOperand(OS,
false);
14370 OS <<
"Computable";
14380 OS <<
"DoesNotDominate";
14386 OS <<
"ProperlyDominates";
14403 OS <<
"Classifying expressions for: ";
14404 F.printAsOperand(OS,
false);
14419 const Loop *L = LI.getLoopFor(
I.getParent());
14434 OS <<
"\t\t" "Exits: ";
14437 OS <<
"<<Unknown>>";
14443 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14445 Iter->getHeader()->printAsOperand(OS,
false);
14453 InnerL->getHeader()->printAsOperand(OS,
false);
14464 OS <<
"Determining loop execution counts for: ";
14465 F.printAsOperand(OS,
false);
14473 auto &
Values = LoopDispositions[S];
14474 for (
auto &V :
Values) {
14475 if (V.getPointer() == L)
14480 auto &Values2 = LoopDispositions[S];
14482 if (V.getPointer() == L) {
14491ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14509 if (L->contains(AR->
getLoop()) &&
14511 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14516 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14517 " dominate the contained loop's header?");
14544 bool HasVarying =
false;
14545 bool HasUniform =
false;
14587 auto &
Values = BlockDispositions[S];
14588 for (
auto &V :
Values) {
14589 if (V.getPointer() == BB)
14594 auto &Values2 = BlockDispositions[S];
14596 if (V.getPointer() == BB) {
14605ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14634 bool Proper =
true;
14645 if (Instruction *
I =
14647 if (
I->getParent() == BB)
14649 if (DT.properlyDominates(
I->getParent(), BB))
14672void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14675 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14676 auto It = BECounts.find(L);
14677 if (It != BECounts.end()) {
14678 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14679 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14681 auto UserIt = BECountUsers.find(S);
14682 assert(UserIt != BECountUsers.end());
14687 BECounts.erase(It);
14695 while (!Worklist.
empty()) {
14697 auto Users = SCEVUsers.find(Curr);
14698 if (
Users != SCEVUsers.end())
14699 for (
const auto *User :
Users->second)
14700 if (ToForget.
insert(User).second)
14704 for (
const auto *S : ToForget)
14705 forgetMemoizedResultsImpl(S);
14707 PredicatedSCEVRewrites.remove_if(
14708 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14711void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14712 LoopDispositions.erase(S);
14713 BlockDispositions.erase(S);
14714 UnsignedRanges.erase(S);
14715 SignedRanges.erase(S);
14716 HasRecMap.erase(S);
14717 ConstantMultipleCache.erase(S);
14720 UnsignedWrapViaInductionTried.erase(AR);
14721 SignedWrapViaInductionTried.erase(AR);
14724 auto ExprIt = ExprValueMap.find(S);
14725 if (ExprIt != ExprValueMap.end()) {
14726 for (
Value *V : ExprIt->second) {
14727 auto ValueIt = ValueExprMap.find_as(V);
14728 if (ValueIt != ValueExprMap.end())
14729 ValueExprMap.erase(ValueIt);
14731 ExprValueMap.erase(ExprIt);
14734 auto ScopeIt = ValuesAtScopes.find(S);
14735 if (ScopeIt != ValuesAtScopes.end()) {
14736 for (
const auto &Pair : ScopeIt->second)
14738 llvm::erase(ValuesAtScopesUsers[Pair.second.getPointer()],
14739 std::make_pair(Pair.first, S));
14740 ValuesAtScopes.erase(ScopeIt);
14743 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14744 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14745 for (
const auto &Pair : ScopeUserIt->second)
14748 llvm::erase_if(ValuesAtScopes[Pair.second], [&](
const auto &LS) {
14749 return LS.first == Pair.first && LS.second.getPointer() == S;
14751 ValuesAtScopesUsers.erase(ScopeUserIt);
14754 auto BEUsersIt = BECountUsers.find(S);
14755 if (BEUsersIt != BECountUsers.end()) {
14757 auto Copy = BEUsersIt->second;
14758 for (
const auto &Pair : Copy)
14759 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14760 BECountUsers.erase(BEUsersIt);
14763 auto FoldUser = FoldCacheUser.find(S);
14764 if (FoldUser != FoldCacheUser.end())
14765 for (
auto &KV : FoldUser->second)
14766 FoldCache.erase(KV);
14767 FoldCacheUser.erase(S);
14771ScalarEvolution::getUsedLoops(
const SCEV *S,
14773 struct FindUsedLoops {
14774 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14775 : LoopsUsed(LoopsUsed) {}
14776 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14777 bool follow(
const SCEV *S) {
14783 bool isDone()
const {
return false; }
14786 FindUsedLoops
F(LoopsUsed);
14787 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14790void ScalarEvolution::getReachableBlocks(
14793 Worklist.
push_back(&F.getEntryBlock());
14794 while (!Worklist.
empty()) {
14796 if (!Reachable.
insert(BB).second)
14804 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14811 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14815 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14850 SCEVMapper SCM(SE2);
14852 SE2.getReachableBlocks(ReachableBlocks, F);
14854 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14872 while (!LoopStack.
empty()) {
14878 if (!ReachableBlocks.
contains(L->getHeader()))
14883 auto It = BackedgeTakenCounts.find(L);
14884 if (It == BackedgeTakenCounts.end())
14888 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14908 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14909 if (Delta && !Delta->
isZero()) {
14910 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14911 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14912 dbgs() <<
"New: " << *NewBECount <<
"\n";
14913 dbgs() <<
"Delta: " << *Delta <<
"\n";
14921 while (!Worklist.
empty()) {
14923 if (ValidLoops.
insert(L).second)
14924 Worklist.
append(L->begin(), L->end());
14926 for (
const auto &KV : ValueExprMap) {
14931 "AddRec references invalid loop");
14936 auto It = ExprValueMap.find(KV.second);
14937 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14938 dbgs() <<
"Value " << *KV.first
14939 <<
" is in ValueExprMap but not in ExprValueMap\n";
14944 if (!ReachableBlocks.
contains(
I->getParent()))
14946 const SCEV *OldSCEV = SCM.visit(KV.second);
14948 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14949 if (Delta && !Delta->
isZero()) {
14950 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14951 <<
"Old: " << *OldSCEV <<
"\n"
14952 <<
"New: " << *NewSCEV <<
"\n"
14953 <<
"Delta: " << *Delta <<
"\n";
14959 for (
const auto &KV : ExprValueMap) {
14960 for (
Value *V : KV.second) {
14961 const SCEV *S = ValueExprMap.lookup(V);
14963 dbgs() <<
"Value " << *V
14964 <<
" is in ExprValueMap but not in ValueExprMap\n";
14967 if (S != KV.first) {
14968 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14969 << *KV.first <<
"\n";
14976 for (
const auto &S : UniqueSCEVs) {
14981 auto It = SCEVUsers.find(
Op);
14982 if (It != SCEVUsers.end() && It->second.count(&S))
14984 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14985 <<
" is not being tracked!\n";
14991 for (
const auto &ValueAndVec : ValuesAtScopes) {
14993 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14994 const Loop *L = LoopAndValueAtScope.first;
14995 SCEVUse ValueAtScope = LoopAndValueAtScope.second;
14997 auto It = ValuesAtScopesUsers.find(ValueAtScope.
getPointer());
14998 if (It != ValuesAtScopesUsers.end() &&
15001 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
15002 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
15008 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
15009 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
15010 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
15011 const Loop *L = LoopAndValue.first;
15012 const SCEV *
Value = LoopAndValue.second;
15014 auto It = ValuesAtScopes.find(
Value);
15017 if (It != ValuesAtScopes.end() &&
any_of(It->second, [&](
const auto &LS) {
15018 return LS.first == L && LS.second.getPointer() == ValueAtScope;
15021 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
15022 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
15028 auto VerifyBECountUsers = [&](
bool Predicated) {
15030 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
15031 for (
const auto &LoopAndBEInfo : BECounts) {
15032 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
15033 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
15035 auto UserIt = BECountUsers.find(S);
15036 if (UserIt != BECountUsers.end() &&
15037 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
15039 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
15040 <<
" missing from BECountUsers\n";
15047 VerifyBECountUsers(
false);
15048 VerifyBECountUsers(
true);
15051 for (
auto &[S,
Values] : LoopDispositions) {
15052 for (
auto [
Loop, CachedDisposition] :
Values) {
15054 if (CachedDisposition != RecomputedDisposition) {
15055 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
15056 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
15057 << RecomputedDisposition <<
"\n";
15064 for (
auto &[S,
Values] : BlockDispositions) {
15065 for (
auto [BB, CachedDisposition] :
Values) {
15067 if (CachedDisposition != RecomputedDisposition) {
15068 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
15069 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
15070 <<
", actual " << RecomputedDisposition <<
"\n";
15077 for (
auto [
FoldID, Expr] : FoldCache) {
15078 auto I = FoldCacheUser.find(Expr);
15079 if (
I == FoldCacheUser.end()) {
15080 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
15085 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
15089 for (
auto [Expr, IDs] : FoldCacheUser) {
15090 for (
auto &
FoldID : IDs) {
15093 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
15098 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
15099 <<
" != " << *Expr <<
"!\n";
15110 for (
auto [S, Multiple] : ConstantMultipleCache) {
15112 if ((Multiple != 0 && RecomputedMultiple != 0 &&
15113 Multiple.
urem(RecomputedMultiple) != 0 &&
15114 RecomputedMultiple.
urem(Multiple) != 0)) {
15115 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
15116 << *S <<
" : Computed " << RecomputedMultiple
15117 <<
" but cache contains " << Multiple <<
"!\n";
15125 FunctionAnalysisManager::Invalidator &Inv) {
15157 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15158 <<
F.getName() <<
"':\n";
15164 "Scalar Evolution Analysis",
false,
true)
15213 const SCEV *LHS,
const SCEV *RHS) {
15215 assert(LHS->getType() == RHS->getType() &&
15216 "Type mismatch between LHS and RHS");
15219 ID.AddInteger(Pred);
15220 ID.AddPointer(LHS);
15221 ID.AddPointer(RHS);
15223 if (
const auto *S = UniquePreds.lookup(ID, Token))
15227 UniquePreds.insert(Eq, Token);
15238 ID.AddInteger(AddedFlags);
15240 if (
const auto *S = UniquePreds.lookup(ID, Token))
15242 auto *OF =
new (SCEVAllocator)
15244 UniquePreds.insert(OF, Token);
15264 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15265 return Rewriter.visit(S);
15271 for (
const auto *Pred : U->getPredicates())
15273 if (IPred->getLHS() == Expr &&
15275 return IPred->getRHS();
15277 if (IPred->getLHS() == Expr &&
15278 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15279 return IPred->getRHS();
15282 return convertToAddRecWithPreds(Expr);
15285 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15301 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15318 explicit SCEVPredicateRewriter(
15319 const Loop *L, ScalarEvolution &SE,
15320 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15321 const SCEVPredicate *Pred)
15322 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15324 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15327 return Pred && Pred->
implies(
P, SE);
15333 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15336 return addOverflowAssumption(
A);
15345 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15349 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15351 if (!PredicatedRewrite)
15353 for (
const auto *
P : PredicatedRewrite->second){
15356 if (L != WP->getExpr()->getLoop())
15359 if (!addOverflowAssumption(
P))
15362 return PredicatedRewrite->first;
15365 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15366 const SCEVPredicate *Pred;
15375 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15382 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15402 if (!Step->
isOne())
15427 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15428 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15441 return Op->LHS == LHS &&
Op->RHS == RHS;
15448 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15450 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15475 const SCEV *Start = AR->getStart();
15476 const SCEV *OpStart =
Op->AR->getStart();
15481 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15490 const SCEV *Step = AR->getStepRecurrence(SE);
15491 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15544 if (Step->getValue()->getValue().isNonNegative())
15548 return ImpliedFlags;
15555 for (
const auto *
P : Preds)
15568 return this->implies(I, SE);
15580 const Loop *L = NWrap->getExpr()->getLoop();
15587 return RewrittenAR &&
15593 for (
const auto *Pred : Preds)
15594 Pred->print(OS,
Depth);
15599 for (
const auto *Pred : Set->Preds)
15607 bool CheckImplies = Preds.
size() < 16;
15610 if (CheckImplies &&
implies(
N, SE))
15616 for (
auto *
P : Preds) {
15617 if (CheckImplies &&
N->implies(
P, SE))
15621 Preds = std::move(PrunedPreds);
15622 Preds.push_back(
N);
15629 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15638 SCEVUsers[
Op].insert(
User);
15642 const SCEV *Expr = SE.getSCEV(V);
15647 RewriteEntry &Entry = RewriteMap[Expr];
15650 if (Entry.second && Generation == Entry.first)
15651 return Entry.second;
15656 Expr = Entry.second;
15658 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15659 Entry = {Generation, NewSCEV};
15665 if (!BackedgeCount) {
15667 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15668 for (
const auto *
P : Preds)
15671 return BackedgeCount;
15675 if (!SymbolicMaxBackedgeCount) {
15677 SymbolicMaxBackedgeCount =
15678 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15679 for (
const auto *
P : Preds)
15682 return SymbolicMaxBackedgeCount;
15686 if (!SmallConstantMaxTripCount) {
15688 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15689 for (
const auto *
P : Preds)
15692 return *SmallConstantMaxTripCount;
15696 if (Preds->implies(&Pred, SE))
15701 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15702 updateGeneration();
15715void PredicatedScalarEvolution::updateGeneration() {
15717 if (++Generation == 0) {
15718 for (
auto &
II : RewriteMap) {
15719 const SCEV *Rewritten =
II.second.second;
15741 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15747 ExtraPreds->
append(NewPreds);
15753 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15759 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15762 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15766 for (
auto *BB : L.getBlocks())
15767 for (
auto &
I : *BB) {
15768 if (!SE.isSCEVable(
I.getType()))
15771 auto *Expr = SE.getSCEV(&
I);
15772 auto II = RewriteMap.find(Expr);
15774 if (
II == RewriteMap.end())
15778 if (
II->second.second == Expr)
15783 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15791 LoopGuards Guards(SE);
15799void ScalarEvolution::LoopGuards::collectFromPHI(
15807 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15808 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15822 auto &RewriteMap =
G->second.RewriteMap;
15823 if (RewriteMap.empty())
15825 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15826 if (S == RewriteMap.end())
15832 return {C0, SM->getSCEVType()};
15835 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15836 MinMaxPattern
P2) -> MinMaxPattern {
15837 auto [C1,
T1] =
P1;
15838 auto [C2, T2] =
P2;
15839 if (!C1 || !C2 ||
T1 != T2)
15843 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15845 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15847 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15849 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15854 auto P = GetMinMaxConst(0);
15855 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15858 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15861 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15864 Guards.RewriteMap.insert({
LHS,
RHS});
15872 const APInt &DivisorVal,
15874 const APInt *ExprVal;
15887 const APInt &DivisorVal,
15889 const APInt *ExprVal;
15897 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15911 const SCEV *URemRHS =
nullptr;
15915 const SCEV *Multiple =
15917 DivInfo[URemLHS] = Multiple;
15919 Multiples[URemLHS] =
C->getAPInt();
15939 auto IsMinMaxSCEVWithNonNegativeConstant =
15943 if (
MinMax->getNumOperands() != 2)
15946 if (
C->getAPInt().isNegative())
15948 SCTy =
MinMax->getSCEVType();
15957 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15959 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15964 auto *DivisibleExpr =
15972void ScalarEvolution::LoopGuards::collectFromBlock(
15974 const BasicBlock *
Block,
const BasicBlock *Pred,
15982 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15993 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15995 if (From == FromRewritten)
15997 RewriteMap[From] = To;
16003 auto GetMaybeRewritten = [&](
const SCEV *S) {
16004 return RewriteMap.lookup_or(S, S);
16011 const SCEV *MatchLHS,
16012 const SCEV *MatchRHS) {
16013 const SCEVConstant *C1;
16016 if (!
match(MatchLHS,
16028 const SCEV *RewrittenLHS = GetMaybeRewritten(LHSUnknown);
16029 ExactRegion = ExactRegion.intersectWith(SE.
getUnsignedRange(RewrittenLHS),
16034 if (ExactRegion.isEmptySet() || ExactRegion.isWrappedSet() ||
16035 ExactRegion.isFullSet())
16038 const SCEV *RegionMin = SE.
getConstant(ExactRegion.getUnsignedMin());
16039 const SCEV *RegionMax = SE.
getConstant(ExactRegion.getUnsignedMax());
16040 const SCEV *ClampedLHS =
16042 AddRewrite(LHSUnknown, RewrittenLHS, ClampedLHS);
16045 if (MatchRangeCheckIdiom(Predicate,
LHS,
RHS))
16058 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
16060 const APInt &DividesBy =
16075 switch (Predicate) {
16104 SmallPtrSet<const SCEV *, 16> Visited;
16106 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
16110 while (!Worklist.
empty()) {
16114 if (!Visited.
insert(From).second)
16116 const SCEV *FromRewritten = GetMaybeRewritten(From);
16117 const SCEV *To =
nullptr;
16119 switch (Predicate) {
16124 EnqueueOperands(
UMax);
16130 EnqueueOperands(
SMax);
16136 EnqueueOperands(
UMin);
16142 EnqueueOperands(
SMin);
16150 const SCEV *OneAlignedUp =
16152 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16164 const SCEVConstant *
C;
16173 Guards.NotEqual.insert({
LHS,
RHS});
16182 AddRewrite(From, FromRewritten, To);
16199 SE.F.
getParent(), Intrinsic::experimental_guard);
16201 for (
const auto *GU : GuardDecl->users())
16203 if (Guard->getFunction() ==
Block->getParent() &&
16212 unsigned NumCollectedConditions = 0;
16214 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16216 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16218 const CondBrInst *LoopEntryPredicate =
16220 if (!LoopEntryPredicate)
16225 NumCollectedConditions++;
16229 if (
Depth > 0 && NumCollectedConditions == 2)
16237 if (Pair.second->hasNPredecessorsOrMore(2) &&
16239 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16240 for (
auto &Phi : Pair.second->phis())
16251 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16252 SmallVector<Value *, 8> Worklist;
16253 SmallPtrSet<Value *, 8> Visited;
16255 while (!Worklist.
empty()) {
16262 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16286 DenseMap<const SCEV *, APInt> Multiples;
16288 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16295 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16296 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16300 for (
const auto &[K, Divisor] : Multiples) {
16301 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16302 Guards.RewriteMap[
K] =
16304 Guards.
rewrite(K), Divisor, SE),
16313 Guards.PreserveNUW =
true;
16314 Guards.PreserveNSW =
true;
16315 for (
const SCEV *Expr : ExprsToRewrite) {
16316 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16317 Guards.PreserveNUW &=
16319 Guards.PreserveNSW &=
16326 if (ExprsToRewrite.size() > 1) {
16327 for (
const SCEV *Expr : ExprsToRewrite) {
16328 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16329 Guards.RewriteMap.erase(Expr);
16330 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16339 class SCEVLoopGuardRewriter
16350 NotEqual(Guards.NotEqual) {
16351 if (Guards.PreserveNUW)
16353 if (Guards.PreserveNSW)
16360 return Map.lookup_or(Expr, Expr);
16364 if (
const SCEV *S = Map.lookup(Expr))
16371 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16372 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16373 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16375 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16376 if (
const SCEV *S = Map.lookup(NarrowExt))
16377 return SE.getZeroExtendExpr(S, Ty);
16378 Bitwidth = Bitwidth / 2;
16386 if (
const SCEV *S = Map.lookup(Expr))
16393 if (
const SCEV *S = Map.lookup(Expr))
16399 if (
const SCEV *S = Map.lookup(Expr))
16405 if (
const SCEV *S = Map.lookup(Expr))
16410 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16415 if (NotEqual.contains({LHS, RHS})) {
16417 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16418 return SE.getUMaxExpr(OneAlignedUp, S);
16425 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16436 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16437 return SE.getAddExpr(
16440 if (
const SCEV *S = Map.lookup(
Add))
16441 return SE.getAddExpr(Expr->
getOperand(0), S);
16449 const SCEV *S =
nullptr;
16456 S = Map.lookup(SE.getAddExpr(NewC, Expr->
getOperand(1)));
16459 return SE.getAddExpr(S, SE.getMinusOne(Expr->
getType()));
16494 if (RewriteMap.empty() && NotEqual.empty())
16497 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16498 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 SCEV::NoWrapFlags getNoWrapFlagsForGEP(GEPOperator *GEP, const SCEV *Accum, ScalarEvolution &SE)
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 const SCEV * SolveLinEquationWithOverflow(const APInt &A, const SCEV *B, SmallVectorImpl< const SCEVPredicate * > *Predicates, ScalarEvolution &SE, const Loop *L)
Finds the minimum unsigned root of the following equation:
static cl::opt< unsigned > MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, cl::desc("Maximum number of iterations SCEV will " "symbolically execute a constant " "derived loop"), cl::init(100))
static uint64_t umul_ov(uint64_t i, uint64_t j, bool &Overflow)
static void PrintSCEVWithTypeHint(raw_ostream &OS, const SCEV *S)
When printing a top-level SCEV for trip counts, it's helpful to include a type for constants which ar...
static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE, const Loop *L)
static SCEV::NoWrapFlags StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, ArrayRef< SCEVUse > Ops, SCEV::NoWrapFlags Flags)
static bool containsConstantInAddMulChain(const SCEV *StartExpr)
Determine if any of the operands in this SCEV are a constant or if any of the add or multiply express...
static const SCEV * getExtendAddRecStart(const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE, unsigned Depth)
static bool CollectAddOperandsWithScales(SmallDenseMap< SCEVUse, APInt, 16 > &M, SmallVectorImpl< SCEVUse > &NewOps, APInt &AccumulatedConstant, ArrayRef< SCEVUse > Ops, const APInt &Scale, ScalarEvolution &SE)
Process the given Ops list, which is a list of operands to be added under the given scale,...
static const SCEV * constantFoldAndGroupOps(ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT, SmallVectorImpl< SCEVUse > &Ops, FoldT Fold, IsIdentityT IsIdentity, IsAbsorberT IsAbsorber)
Performs a number of common optimizations on the passed Ops.
static 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< BinaryOp > MatchBinaryOp(Value *V, const DataLayout &DL, AssumptionCache &AC, const DominatorTree &DT, const Instruction *CxtI)
Try to map V into a BinaryOp, and return std::nullopt on failure.
static std::optional< APInt > SolveQuadraticAddRecExact(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE)
Let c(n) be the value of the quadratic chrec {L,+,M,+,N} after n iterations.
static std::optional< APInt > TruncIfPossible(std::optional< APInt > X, unsigned BitWidth)
Helper function to truncate an optional APInt to a given BitWidth.
static cl::opt< unsigned > MaxSCEVCompareDepth("scalar-evolution-max-scev-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV complexity comparisons"), cl::init(32))
static APInt extractConstantWithoutWrapping(ScalarEvolution &SE, const SCEVConstant *ConstantTerm, const SCEVAddExpr *WholeAddExpr)
static cl::opt< unsigned > MaxConstantEvolvingDepth("scalar-evolution-max-constant-evolving-depth", cl::Hidden, cl::desc("Maximum depth of recursive constant evolving"), cl::init(32))
static bool canConstantEvolve(Instruction *I, const Loop *L, const TargetLibraryInfo *TLI)
Determine whether this instruction can constant evolve within this loop assuming its operands can all...
static bool MatchBinarySub(const SCEV *S, SCEVUse &LHS, SCEVUse &RHS)
static std::optional< ConstantRange > GetRangeFromMetadata(Value *V)
Helper method to assign a range to V from metadata present in the IR.
static cl::opt< unsigned > HugeExprThreshold("scalar-evolution-huge-expr-threshold", cl::Hidden, cl::desc("Size of the expression which is considered huge"), cl::init(4096))
static Type * isSimpleCastedPHI(const SCEV *Op, const SCEVUnknown *SymbolicPHI, bool &Signed, ScalarEvolution &SE)
Helper function to createAddRecFromPHIWithCasts.
static Constant * EvaluateExpression(Value *V, const Loop *L, DenseMap< Instruction *, Constant * > &Vals, const DataLayout &DL, const TargetLibraryInfo *TLI)
EvaluateExpression - Given an expression that passes the getConstantEvolvingPHI predicate,...
static const SCEV * getPreviousSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static const SCEV * MatchNotExpr(const SCEV *Expr)
If Expr computes ~A, return A else return nullptr.
static std::pair< ConstantRange, bool > getRangeForAffineARHelper(APInt Step, const ConstantRange &StartRange, const APInt &MaxBECount, bool Signed)
static cl::opt< unsigned > MaxValueCompareDepth("scalar-evolution-max-value-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive value complexity comparisons"), cl::init(2))
static const SCEV * applyDivisibilityOnMinMaxExpr(const SCEV *MinMaxExpr, APInt Divisor, ScalarEvolution &SE)
static cl::opt< bool, true > VerifySCEVOpt("verify-scev", cl::Hidden, cl::location(VerifySCEV), cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"))
static const SCEV * getSignedOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static cl::opt< unsigned > MaxArithDepth("scalar-evolution-max-arith-depth", cl::Hidden, cl::desc("Maximum depth of recursive arithmetics"), cl::init(32))
static bool HasSameValue(const SCEV *A, const SCEV *B)
SCEV structural equivalence is usually sufficient for testing whether two expressions are equal,...
static uint64_t Choose(uint64_t n, uint64_t k, bool &Overflow)
Compute the result of "n choose k", the binomial coefficient.
static std::optional< int > CompareSCEVComplexity(const LoopInfo *const LI, const SCEV *LHS, const SCEV *RHS, DominatorTree &DT, unsigned Depth=0)
static bool scevUnconditionallyPropagatesPoisonFromOperands(SCEVTypes Kind)
static cl::opt< bool > VerifySCEVStrict("verify-scev-strict", cl::Hidden, cl::desc("Enable stricter verification with -verify-scev is passed"))
static Constant * getOtherIncomingValue(PHINode *PN, BasicBlock *BB)
static cl::opt< bool > UseExpensiveRangeSharpening("scalar-evolution-use-expensive-range-sharpening", cl::Hidden, cl::init(false), cl::desc("Use more powerful methods of sharpening expression ranges. May " "be costly in terms of compile time"))
static const SCEV * getUnsignedOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static bool IsKnownPredicateViaMinOrMax(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Is LHS Pred RHS true on the virtue of LHS or RHS being a Min or Max expression?
static bool BrPHIToSelect(DominatorTree &DT, CondBrInst *BI, PHINode *Merge, Value *&C, Value *&LHS, Value *&RHS)
This file defines the scope_exit class, which executes user-defined cleanup logic at scope exit.
static bool InBlock(const Value *V, const BasicBlock *BB)
Provides some synthesis utilities to produce sequences of values.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
static SymbolRef::Type getType(const Symbol *Sym)
LocallyHashedType DenseMapInfo< LocallyHashedType >::Empty
static std::optional< bool > isImpliedCondOperands(CmpInst::Predicate Pred, const Value *ALHS, const Value *ARHS, const Value *BLHS, const Value *BRHS)
Return true if "icmp Pred BLHS BRHS" is true whenever "icmp PredALHS ARHS" is true.
Virtual Register Rewriter
static const uint32_t IV[8]
SCEVCastSinkingRewriter(ScalarEvolution &SE, Type *TargetTy, ConversionFn CreatePtrCast)
static const SCEV * rewrite(const SCEV *Scev, ScalarEvolution &SE, Type *TargetTy, ConversionFn CreatePtrCast)
const SCEV * visitUnknown(const SCEVUnknown *Expr)
const SCEV * visitAddExpr(const SCEVAddExpr *Expr)
const SCEV * visit(const SCEV *S)
Class for arbitrary precision integers.
LLVM_ABI APInt umul_ov(const APInt &RHS, bool &Overflow) const
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
uint64_t getZExtValue() const
Get zero extended value.
unsigned getActiveBits() const
Compute the number of active bits in the value.
LLVM_ABI APInt trunc(unsigned width) const
Truncate to new width.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
APInt abs() const
Get the absolute value.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool isSignMask() const
Check if the APInt's value is returned by getSignMask.
LLVM_ABI APInt urem(const APInt &RHS) const
Unsigned remainder operation.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
bool isNegative() const
Determine sign of this APInt.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
LLVM_ABI APInt uadd_ov(const APInt &RHS, bool &Overflow) const
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
bool isNonPositive() const
Determine if this APInt Value is non-positive (<= 0).
unsigned countTrailingZeros() const
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
unsigned logBase2() const
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
LLVM_ABI APInt multiplicativeInverse() const
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
LLVM_ABI APInt sext(unsigned width) const
Sign extend to a new width.
APInt shl(unsigned shiftAmt) const
Left-shift function.
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
bool isSignBitSet() const
Determine if sign bit of this APInt is set.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
This templated class represents "all analyses that operate over <aparticular IR unit>" (e....
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
AnalysisUsage & addRequiredTransitive()
Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
Get the array size.
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
MutableArrayRef< WeakVH > assumptions()
Access the list of assumption handles currently tracked for this function.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
LLVM_ABI unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
LLVM_ABI Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
BinaryOps getOpcode() const
This class represents a function call, abstracting a target machine's calling convention.
virtual void deleted()
Callback for Value destruction.
This is the base class for all instructions that perform data casts.
This class is the base class for the comparison instructions.
bool isFalseWhenEqual() const
This is just a convenience.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ ICMP_UGE
unsigned greater or equal
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
@ ICMP_SGE
signed greater or equal
@ ICMP_ULE
unsigned less or equal
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
bool isTrueWhenEqual() const
This is just a convenience.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
static LLVM_ABI std::optional< CmpPredicate > getMatching(CmpPredicate A, CmpPredicate B)
Compares two CmpPredicates taking samesign into account and returns the canonicalized CmpPredicate if...
LLVM_ABI CmpInst::Predicate getPreferredSignedPredicate() const
Attempts to return a signed CmpInst::Predicate from the CmpPredicate.
CmpInst::Predicate dropSameSign() const
Drops samesign information.
Conditional Branch instruction.
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
static LLVM_ABI Constant * getNot(Constant *C)
static Constant * getPtrAdd(Constant *Ptr, Constant *Offset, GEPNoWrapFlags NW=GEPNoWrapFlags::none(), std::optional< ConstantRange > InRange=std::nullopt, Type *OnlyIfReduced=nullptr)
Create a getelementptr i8, ptr, offset constant expression.
static LLVM_ABI Constant * getPtrToAddr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static LLVM_ABI Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
static LLVM_ABI Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
This is the shared class of boolean and integer constants.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
static LLVM_ABI ConstantInt * getBool(LLVMContext &Context, bool V)
This class represents a range of values.
LLVM_ABI ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
LLVM_ABI ConstantRange zextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
PreferredRangeType
If represented precisely, the result of some range operations may consist of multiple disjoint ranges...
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI ConstantRange urem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned remainder operation of...
LLVM_ABI bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
LLVM_ABI bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other?
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI ConstantRange zeroExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
LLVM_ABI bool isSignWrappedSet() const
Return true if this set wraps around the signed domain.
LLVM_ABI APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
LLVM_ABI bool isWrappedSet() const
Return true if this set wraps around the unsigned domain.
LLVM_ABI void print(raw_ostream &OS) const
Print out the bounds to a stream.
LLVM_ABI ConstantRange truncate(uint32_t BitWidth, unsigned NoWrapKind=0) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
LLVM_ABI ConstantRange signExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI bool contains(const APInt &Val) const
Return true if the specified value is in the set.
LLVM_ABI ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
LLVM_ABI APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
static LLVM_ABI ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
LLVM_ABI unsigned getMinSignedBits() const
Compute the maximal number of bits needed to represent every value in this signed range.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
LLVM_ABI ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
LLVM_ABI ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
static LLVM_ABI ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)
Produce the range that contains X if and only if "X BinOp Other" does not wrap.
This is an important base class in LLVM.
A parsed version of the target data layout string in and methods for querying it.
LLVM_ABI const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
LLVM_ABI unsigned getIndexTypeSizeInBits(Type *Ty) const
The size in bits of the index used in GEP calculation for this type.
LLVM_ABI IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
TypeSize getTypeSizeInBits(Type *Ty) const
Size examples:
ValueT lookup(const_arg_type_t< KeyT > Val) const
Return the entry for the specified key, or a default constructed value if no such entry exists.
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive,...
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Analysis pass which computes a DominatorTree.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
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 bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've statically proved that V doesn't wrap.
LLVM_ABI const SCEVAddRecExpr * getAsAddRec(Value *V, SmallVectorImpl< const SCEVPredicate * > *WrapPredsAdded=nullptr)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
LLVM_ABI void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
LLVM_ABI PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
LLVM_ABI unsigned getSmallConstantMaxTripCount()
Returns the upper bound of the loop trip count as a normal unsigned value, or 0 if the trip count is ...
LLVM_ABI void addPredicates(ArrayRef< const SCEVPredicate * > Preds)
Adds all predicates in Preds.
LLVM_ABI const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSymbolicMaxBackedgeTakenCount()
Get the (predicated) symbolic max backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
constexpr bool isValid() const
This node represents an addition of some number of SCEVs.
This node represents a polynomial recurrence on the trip count of the specified loop.
friend class ScalarEvolution
LLVM_ABI 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(NoWrapFlags Flags)
Set flags for a recurrence without clearing any previously set flags.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
bool isQuadratic() const
Return true if this represents an expression A + B*x + C*x^2 where A, B and C are loop invariant valu...
LLVM_ABI const SCEV * getNumIterationsInRange(const ConstantRange &Range, ScalarEvolution &SE) const
Return the number of iterations of this loop that produce values in the specified constant range.
LLVM_ABI const SCEVAddRecExpr * getPostIncExpr(ScalarEvolution &SE) const
Return an expression representing the value of this expression one iteration of the loop ahead.
const Loop * getLoop() const
SCEVUse getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
This is the base class for unary cast operator classes.
SCEVUse getOperand() const
LLVM_ABI SCEVCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, SCEVUse op, Type *ty)
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a non-recurrence without clearing previously set flags.
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
SCEVComparePredicate(const FoldingSetNodeIDRef ID, const ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Implementation of the SCEVPredicate interface.
This class represents a constant integer value.
ConstantInt * getValue() const
const APInt & getAPInt() const
This is the base class for unary integral cast operator classes.
LLVM_ABI SCEVIntegralCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, SCEVUse op, Type *ty)
This node is the base class min/max selections.
static enum SCEVTypes negate(enum SCEVTypes T)
This node represents multiplication of some number of SCEVs.
This node is a base class providing common functionality for n'ary operators.
bool hasNoUnsignedWrap() const
ArrayRef< SCEVUse > operands() const
bool hasNoSelfWrap() const
size_t getNumOperands() const
bool hasNoSignedWrap() const
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
SCEVUse getOperand(unsigned i) const
This class represents an assumption made using SCEV expressions which can be checked at run-time.
SCEVPredicate(const SCEVPredicate &)=default
virtual bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const =0
Returns true if this predicate implies N.
This class represents a cast from a pointer to a pointer-sized integer value, without capturing the p...
This visitor recursively visits a SCEV expression and re-writes it.
const SCEV * visitSignExtendExpr(const SCEVSignExtendExpr *Expr)
const SCEV * visit(const SCEV *S)
const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)
const SCEV * visitSMinExpr(const SCEVSMinExpr *Expr)
SCEVRewriteVisitor(ScalarEvolution &SE)
const SCEV * visitUMinExpr(const SCEVUMinExpr *Expr)
This class represents a signed minimum selection.
This node is the base class for sequential/in-order min/max selections.
static SCEVTypes getEquivalentNonSequentialSCEVType(SCEVTypes Ty)
This class represents a sign extension of a small integer value to a larger integer value.
Visit all nodes in the expression tree using worklist traversal.
This class represents a truncation of an integer value to a smaller integer value.
This class represents a binary unsigned division operation.
This class represents an unsigned minimum selection.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
void print(raw_ostream &OS, unsigned Depth) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Returns true if this predicate implies N.
SCEVUnionPredicate(ArrayRef< const SCEVPredicate * > Preds, ScalarEvolution &SE)
Union predicates don't get cached so create a dummy set ID for it.
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
SCEVUnionPredicate getUnionWith(const SCEVPredicate *N, ScalarEvolution &SE) const
Returns a new SCEVUnionPredicate that is the union of this predicate and the given predicate N.
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents the value of vscale, as used when defining the length of a scalable vector or r...
This class represents an assumption made on an AddRec expression.
IncrementWrapFlags
Similar to SCEV::NoWrapFlags, but with slightly different semantics for FlagNUSW.
SCEVWrapPredicate(const FoldingSetNodeIDRef ID, const SCEVAddRecExpr *AR, IncrementWrapFlags Flags)
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Returns true if this predicate implies N.
static SCEVWrapPredicate::IncrementWrapFlags setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OnFlags)
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
const SCEVAddRecExpr * getExpr() const
Implementation of the SCEVPredicate interface.
static SCEVWrapPredicate::IncrementWrapFlags clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OffFlags)
Convenient IncrementWrapFlags manipulation methods.
static SCEVWrapPredicate::IncrementWrapFlags getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE)
Returns the set of SCEVWrapPredicate no wrap flags implied by a SCEVAddRecExpr.
IncrementWrapFlags getFlags() const
Returns the set assumed no overflow flags.
This class represents a zero extension of a small integer value to a larger integer value.
This class represents an analyzed expression in the program.
unsigned short getExpressionSize() const
SCEVNoWrapFlags NoWrapFlags
LLVM_ABI bool isOne() const
Return true if the expression is a constant one.
SCEV(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, unsigned short ExpressionSize, Type *Ty)
static constexpr auto FlagNUW
LLVM_ABI void computeAndSetCanonical(ScalarEvolution &SE)
Compute and set the canonical SCEV, by constructing a SCEV with the same operands,...
LLVM_ABI bool isZero() const
Return true if the expression is a constant zero.
const SCEV * CanonicalSCEV
Pointer to the canonical version of the SCEV, i.e.
static constexpr auto FlagAnyWrap
LLVM_ABI void dump() const
This method is used for debugging.
LLVM_ABI bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
LLVM_ABI bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
static constexpr auto FlagNSW
LLVM_ABI ArrayRef< SCEVUse > operands() const
Return operands of this SCEV expression.
Type * getType() const
Return the LLVM type of this SCEV expression.
LLVM_ABI void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
SCEVTypes getSCEVType() const
static constexpr auto FlagNW
Analysis pass that exposes the ScalarEvolution for a function.
LLVM_ABI ScalarEvolution run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
void print(raw_ostream &OS, const Module *=nullptr) const override
print - Print out the internal state of the pass.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
ScalarEvolutionWrapperPass()
static LLVM_ABI LoopGuards collect(const Loop *L, ScalarEvolution &SE)
Collect rewrite map for loop guards for loop L, together with flags indicating if NUW and NSW can be ...
LLVM_ABI const SCEV * rewrite(const SCEV *Expr) const
Try to apply the collected loop guards to Expr.
The main scalar evolution driver.
LLVM_ABI const SCEV * getUDivExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
static bool hasFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags TestFlags)
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
LLVM_ABI bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
LLVM_ABI bool isKnownOnEveryIteration(CmpPredicate Pred, const SCEVAddRecExpr *LHS, const SCEV *RHS)
Test if the condition described by Pred, LHS, RHS is known to be true on every iteration of the loop ...
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterationsImpl(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
LLVM_ABI const SCEV * 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 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 void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags)
Update no-wrap flags of an AddRec.
LLVM_ABI const SCEV * getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS)
Promote the operands to the wider of the types using zero-extension, and then perform a umax operatio...
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
LLVM_ABI bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?
LLVM_ABI ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsOnlyExit, bool AllowPredicates=false)
Compute the number of times the backedge of the specified loop will execute if its exit condition wer...
LLVM_ABI const SCEV * 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.
LLVM_ABI const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
LLVM_ABI const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
static LLVM_ABI bool isGuaranteedNotToBePoison(const SCEV *Op)
Returns true if Op is guaranteed to not be poison.
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
LLVM_ABI const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
LLVM_ABI ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI)
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LLVM_ABI const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI 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 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.
LLVM_ABI const SCEV * getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo)
Return an expression for offsetof on the given field with type IntTy.
LLVM_ABI LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
LLVM_ABI bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
LLVM_ABI const SCEV * getTruncateExpr(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool hasOperand(const SCEV *S, const SCEV *Op) const
Test whether the given SCEV has Op as a direct or indirect operand.
LLVM_ABI const SCEV * 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 const SCEV * getElementCount(Type *Ty, ElementCount EC, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
LLVM_ABI bool instructionCouldExistWithOperands(const SCEV *A, const SCEV *B)
Return true if there exists a point in the program at which both A and B could be operands to the sam...
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
LLVM_ABI void print(raw_ostream &OS) const
LLVM_ABI const SCEV * 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.
static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
LLVM_ABI void forgetTopmostLoop(const Loop *L)
LLVM_ABI void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
APInt getSignedRangeMin(const SCEV *S)
Determine the min of the signed range for a particular SCEV.
LLVM_ABI bool isLoopUniform(const SCEV *S, const Loop *L)
Returns true if the given SCEV is loop-uniform with respect to the specified loop L.
LLVM_ABI const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
LLVM_ABI const SCEV * getSignExtendExpr(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEV * getUMaxExpr(SCEVUse LHS, SCEVUse RHS)
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags Mask)
Convenient NoWrapFlags manipulation.
@ MonotonicallyDecreasing
@ MonotonicallyIncreasing
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI=nullptr)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L, return a LoopInvaria...
LLVM_ABI const SCEV * getStoreSizeOfExpr(Type *IntTy, Type *StoreTy)
Return an expression for the store size of StoreTy that is type IntTy.
LLVM_ABI const SCEVPredicate * getWrapPredicate(const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
LLVM_ABI bool isLoopBackedgeGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether the backedge of the loop is protected by a conditional between LHS and RHS.
LLVM_ABI APInt getNonZeroConstantMultiple(const SCEV *S)
const SCEV * getMinusOne(Type *Ty)
Return a SCEV for the constant -1 of a specific type.
static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
LLVM_ABI bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
LLVM_ABI BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB)
Return the "disposition" of the given SCEV with respect to the given block.
LLVM_ABI const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
LLVM_ABI const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
Promote the operands to the wider of the types using zero-extension, and then perform a umin operatio...
LLVM_ABI bool loopIsFiniteByAssumption(const Loop *L)
Return true if this loop is finite by assumption.
LLVM_ABI const SCEV * getExistingSCEV(Value *V)
Return an existing SCEV for V if there is one, otherwise return nullptr.
LLVM_ABI APInt getConstantMultiple(const SCEV *S, const Instruction *CtxI=nullptr)
Returns the max constant multiple of S.
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
@ LoopComputable
The SCEV varies predictably with the loop.
@ LoopVariant
The SCEV is loop-variant (unknown).
@ LoopInvariant
The SCEV is loop-invariant.
@ LoopUniform
The SCEV is loop-uniform.
friend class SCEVCallbackVH
LLVM_ABI bool isKnownToBeAPowerOfTwo(const SCEV *S, bool OrZero=false, bool OrNegative=false)
Test if the given expression is known to be a power of 2.
LLVM_ABI std::optional< SCEV::NoWrapFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
LLVM_ABI void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)
Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...
LLVM_ABI bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
LLVM_ABI std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
LLVM_ABI const SCEV * getCouldNotCompute()
LLVM_ABI bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
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 forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
LLVM_ABI const SCEV * getVScale(Type *Ty)
LLVM_ABI unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
LLVM_ABI bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
LLVM_ABI const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
LLVM_ABI void forgetAllLoops()
LLVM_ABI 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 * 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 SCEVUse getMulExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlags Flags={}, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
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.
LLVM_ABI SCEVUse getAddRecExpr(SCEVUse Start, SCEVUse Step, const Loop *L, SCEVFlags Flags)
Get an add recurrence expression for the specified loop.
LLVM_ABI SCEVUse getAddExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlags Flags={}, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
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)
int getMinValue(MCInstrInfo const &MCII, MCInst const &MCI)
Return the minimum value of an extendable operand.
@ BasicBlock
Various leaf nodes.
LLVM_ABI Function * getDeclarationIfExists(const Module *M, ID id)
Look up the Function declaration of the intrinsic id in the Module M and return it if it exists.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
auto m_BasicBlock()
Match an arbitrary basic block value and ignore it.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
auto m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
match_bind< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
brc_match< Cond_t, match_bind< BasicBlock >, match_bind< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
CastOperator_match< OpTy, Instruction::PtrToInt > m_PtrToInt(const OpTy &Op)
Matches PtrToInt.
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
bind_cst_ty m_scev_APInt(const APInt *&C)
Match an SCEV constant and bind it to an APInt.
cst_pred_ty< is_all_ones > m_scev_AllOnes()
Match an integer with all bits set.
SCEVUnaryExpr_match< SCEVZeroExtendExpr, Op0_t > m_scev_ZExt(const Op0_t &Op0)
is_undef_or_poison m_scev_UndefOrPoison()
Match an SCEVUnknown wrapping undef or poison.
cst_pred_ty< is_one > m_scev_One()
Match an integer 1.
specificloop_ty m_SpecificLoop(const Loop *L)
SCEVUnaryExpr_match< SCEVSignExtendExpr, Op0_t > m_scev_SExt(const Op0_t &Op0)
match_bind< const SCEVMulExpr > m_scev_Mul(const SCEVMulExpr *&V)
cst_pred_ty< is_zero > m_scev_Zero()
Match an integer 0.
SCEVUnaryExpr_match< SCEVTruncateExpr, Op0_t > m_scev_Trunc(const Op0_t &Op0)
bool match(const SCEV *S, const Pattern &P)
SCEVBinaryExpr_match< SCEVUDivExpr, Op0_t, Op1_t > m_scev_UDiv(const Op0_t &Op0, const Op1_t &Op1)
specificscev_ty m_scev_Specific(const SCEV *S)
Match if we have a specific specified SCEV.
SCEVAffineAddRec_match< Op0_t, Op1_t, match_isa< const Loop > > m_scev_AffineAddRec(const Op0_t &Op0, const Op1_t &Op1)
match_bind< const SCEVUnknown > m_SCEVUnknown(const SCEVUnknown *&V)
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagNUW, true > m_scev_c_NUWMul(const Op0_t &Op0, const Op1_t &Op1)
match_bind< const SCEVAddExpr > m_scev_Add(const SCEVAddExpr *&V)
SCEVBinaryExpr_match< SCEVSMaxExpr, Op0_t, Op1_t, SCEV::FlagAnyWrap, true > m_scev_SMax(const Op0_t &Op0, const Op1_t &Op1)
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagAnyWrap, true > m_scev_c_Mul(const Op0_t &Op0, const Op1_t &Op1)
SCEVURem_match< Op0_t, Op1_t > m_scev_URem(Op0_t LHS, Op1_t RHS, ScalarEvolution &SE)
Match the mathematical pattern A - (A / B) * B, where A and B can be arbitrary expressions.
@ Valid
The data is already valid.
initializer< Ty > init(const Ty &Val)
LocationClass< Ty > location(Ty &L)
@ Switch
The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...
NodeAddr< PhiNode * > Phi
friend class Instruction
Iterator for Instructions in a `BasicBlock.
unsigned getOpcode(const VPValue *V)
Return the instruction opcode for the recipe defining V or 0 for unsupported recipes and VPValues not...
This is an optimization pass for GlobalISel generic memory operations.
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
void stable_sort(R &&Range)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
SaveAndRestore(T &) -> SaveAndRestore< T >
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)
LLVM_ABI bool canCreatePoison(const Operator *Op, bool ConsiderFlagsAndMetadata=true)
LLVM_ABI bool mustTriggerUB(const Instruction *I, const SmallPtrSetImpl< const Value * > &KnownPoison)
Return true if the given instruction must trigger undefined behavior when I is executed with any oper...
RelativeUniformCounterPtr Values
@ Known
Known to have no common set bits.
InterleavedRange< Range > interleaved(const Range &R, StringRef Separator=", ", StringRef Prefix="", StringRef Suffix="")
Output range R as a sequence of interleaved elements.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
auto successors(const MachineBasicBlock *BB)
scope_exit(Callable) -> scope_exit< Callable >
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
@ BinaryOp
One of the operands is a binary op.
constexpr from_range_t from_range
auto dyn_cast_if_present(const Y &Val)
dyn_cast_if_present<X> - Functionally identical to dyn_cast, except that a null (or none in the case ...
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
auto uninitialized_copy(R &&Src, IterTy Dst)
bool isa_and_nonnull(const Y &Val)
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
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,...
auto dyn_cast_or_null(const Y &Val)
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
auto reverse(ContainerTy &&C)
LLVM_ABI bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
LLVM_ABI bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
LLVM_ABI bool isFinite(const Loop *L)
Return true if this loop can be assumed to run for a finite number of iterations.
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
unsigned short computeExpressionSize(ArrayRef< SCEVUse > Args)
LLVM_ABI bool programUndefinedIfPoison(const Instruction *Inst)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isPointerTy(const Type *T)
LLVM_ABI ConstantRange getVScaleRange(const Function *F, unsigned BitWidth)
Determine the possible constant range of vscale with the given bit width, based on the vscale_range f...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
LLVM_ABI bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)
Return true if the given value is known to be non-zero when defined.
constexpr T divideCeil(U Numerator, V Denominator)
Returns the integer ceil(Numerator / Denominator).
LLVM_ABI bool propagatesPoison(const Use &PoisonOp)
Return true if PoisonOp's user yields poison or raises UB if its operand PoisonOp is poison.
@ UMin
Unsigned integer min implemented in terms of select(cmp()).
@ Mul
Product of integers.
@ SMax
Signed integer max implemented in terms of select(cmp()).
@ SMin
Signed integer min implemented in terms of select(cmp()).
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
DWARFExpression::Operation Op
auto max_element(R &&Range)
Provide wrappers to std::max_element which take ranges instead of having to pass begin/end explicitly...
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
ArrayRef(const T &OneElt) -> ArrayRef< T >
LLVM_ABI unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Return the number of times the sign bit of the register is replicated into the other bits.
constexpr unsigned BitWidth
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
constexpr auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
constexpr bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
iterator_range< df_iterator< T > > depth_first(const T &G)
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
LLVM_ABI bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be poison, but may be undef.
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
constexpr detail::IsaCheckPredicate< Types... > IsaPred
Function object wrapper for the llvm::isa type check.
SCEVUseT< const SCEV * > SCEVUse
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
Implement std::hash so that hash_code can be used in STL containers.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
A special type used by analysis passes to provide an address that identifies that particular analysis...
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
static LLVM_ABI KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for ashr(LHS, RHS).
static LLVM_ABI KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for lshr(LHS, RHS).
static LLVM_ABI KnownBits shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW=false, bool NSW=false, bool ShAmtNonZero=false)
Compute known bits for shl(LHS, RHS).
An object of this class is returned by queries that could not be answered.
LLVM_ABI SCEVCouldNotCompute()
static LLVM_ABI bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
The no-wrap flags to apply when creating a SCEV expression, to the expression and use respectively.
SCEVNoWrapFlags UseFlags
Flags only applied to a SCEVUse.
SCEVNoWrapFlags ExprFlags
Flags applied directly to a SCEV expression, must be valid wherever the expression is valid.
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