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"),
334#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
352 OS <<
"(ptrtoaddr " << *
Op->getType() <<
" " <<
Op <<
" to "
359 OS <<
"(trunc " << *
Op->getType() <<
" " <<
Op <<
" to "
366 OS <<
"(zext " << *
Op->getType() <<
" " <<
Op <<
" to " << *ZExt->
getType()
373 OS <<
"(sext " << *
Op->getType() <<
" " <<
Op <<
" to " << *SExt->
getType()
402 const char *OpStr =
nullptr;
415 OpStr =
" umin_seq ";
437 OS <<
"(" << UDiv->
getLHS() <<
" /u " << UDiv->
getRHS() <<
")";
444 OS <<
"***COULDNOTCOMPUTE***";
486 if (!
Mul)
return false;
490 if (!SC)
return false;
504 auto &Entry = ConstantSCEVs[V];
513 static_cast<SCEVConstant *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP)))
516 new (SCEVAllocator)
SCEVConstant(ID.Intern(SCEVAllocator), V);
517 UniqueSCEVs.InsertNode(S, IP);
532 ConstantInt::get(ITy, V,
isSigned,
true));
540 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
542 SCEV *S =
new (SCEVAllocator)
SCEVVScale(ID.Intern(SCEVAllocator), Ty);
543 UniqueSCEVs.InsertNode(S, IP);
564 "Must be a non-bit-width-changing pointer-to-integer cast!");
576 "Cannot truncate non-integer value!");
583 "Cannot zero extend non-integer value!");
590 "Cannot sign extend non-integer value!");
595 SE->forgetMemoizedResults({
this});
598 SE->UniqueSCEVs.RemoveNode(
this);
604void SCEVUnknown::allUsesReplacedWith(
Value *New) {
606 SE->forgetMemoizedResults({
this});
609 SE->UniqueSCEVs.RemoveNode(
this);
631 if (LIsPointer != RIsPointer)
632 return (
int)LIsPointer - (int)RIsPointer;
637 return (
int)LID - (int)RID;
642 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
643 return (
int)LArgNo - (int)RArgNo;
649 if (
auto L = LGV->getLinkage() - RGV->getLinkage())
652 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
653 auto LT = GV->getLinkage();
660 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
661 return LGV->getName().compare(RGV->getName());
672 if (LParent != RParent) {
675 if (LDepth != RDepth)
676 return (
int)LDepth - (int)RDepth;
680 unsigned LNumOps = LInst->getNumOperands(),
681 RNumOps = RInst->getNumOperands();
682 if (LNumOps != RNumOps)
683 return (
int)LNumOps - (int)RNumOps;
685 for (
unsigned Idx :
seq(LNumOps)) {
687 RInst->getOperand(Idx),
Depth + 1);
701static std::optional<int>
711 return (
int)LType - (int)RType;
736 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
737 if (LBitWidth != RBitWidth)
738 return (
int)LBitWidth - (int)RBitWidth;
739 return LA.
ult(
RA) ? -1 : 1;
745 return LTy->getBitWidth() - RTy->getBitWidth();
756 if (LLoop != RLoop) {
758 assert(LHead != RHead &&
"Two loops share the same header?");
762 "No dominance between recurrences used by one SCEV?");
785 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
786 if (LNumOps != RNumOps)
787 return (
int)LNumOps - (int)RNumOps;
789 for (
unsigned i = 0; i != LNumOps; ++i) {
815 if (
Ops.size() < 2)
return;
820 return Complexity && *Complexity < 0;
822 if (
Ops.size() == 2) {
826 if (IsLessComplex(
RHS,
LHS))
839 for (
unsigned i = 0, e =
Ops.size(); i != e-2; ++i) {
845 for (
unsigned j = i+1; j != e &&
Ops[j]->getSCEVType() == Complexity; ++j) {
850 if (i == e-2)
return;
872template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
876 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
878 for (
unsigned Idx = 0; Idx <
Ops.size();) {
886 Ops.erase(
Ops.begin() + Idx);
893 assert(Folded &&
"Must have folded value");
897 if (Folded && IsAbsorber(Folded->
getAPInt()))
901 if (Folded && !IsIdentity(Folded->
getAPInt()))
902 Ops.insert(
Ops.begin(), Folded);
904 return Ops.size() == 1 ?
Ops[0] :
nullptr;
979 APInt OddFactorial(W, 1);
981 for (
unsigned i = 3; i <= K; ++i) {
984 OddFactorial *= (i >> TwoFactors);
988 unsigned CalculationBits = W +
T;
1002 for (
unsigned i = 1; i != K; ++i) {
1035 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1064 ConversionFn CreatePtrCast;
1068 ConversionFn CreatePtrCast)
1069 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
1072 Type *TargetTy, ConversionFn CreatePtrCast) {
1074 return Rewriter.visit(Scev);
1110 "Should only reach pointer-typed SCEVUnknown's.");
1115 return SE.getZero(TargetTy);
1116 return CreatePtrCast(Expr);
1121 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1125 if (DL.hasUnstableRepresentation(
Op->getType()))
1128 Type *Ty = DL.getAddressType(
Op->getType());
1139 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
1141 SCEV *S =
new (SCEVAllocator)
1143 UniqueSCEVs.InsertNode(S, IP);
1146 return static_cast<const SCEV *
>(S);
1149 "We must have succeeded in sinking the cast, "
1150 "and ending up with an integer-typed expression!");
1157 "This is not a truncating conversion!");
1159 "This is not a conversion to a SCEVable type!");
1160 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1165 ID.AddPointer(
Op.getOpaqueValue());
1168 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1190 UniqueSCEVs.InsertNode(S, IP);
1203 unsigned numTruncs = 0;
1204 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1212 if (numTruncs < 2) {
1222 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
1229 for (
const SCEV *
Op : AddRec->operands())
1244 UniqueSCEVs.InsertNode(S, IP);
1285struct ExtendOpTraitsBase {
1286 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
SCEVUse,
Type *,
1291template <
typename ExtendOp>
struct ExtendOpTraits {
1307 static const GetExtendExprTy GetExtendExpr;
1309 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1310 ICmpInst::Predicate *Pred,
1311 ScalarEvolution *SE) {
1316const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1323 static const GetExtendExprTy GetExtendExpr;
1325 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1326 ICmpInst::Predicate *Pred,
1327 ScalarEvolution *SE) {
1332const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1344template <
typename ExtendOpTy>
1347 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1348 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1364 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1377 auto PreStartFlags =
1395 const SCEV *OperandExtendedStart =
1397 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1398 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1410 const SCEV *OverflowLimit =
1411 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1413 if (OverflowLimit &&
1421template <
typename ExtendOpTy>
1425 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1433 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1468template <
typename ExtendOpTy>
1469bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1472 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1482 APInt StartAI = StartC->
getAPInt();
1484 for (
unsigned Delta : {-2, -1, 1, 2}) {
1485 const SCEV *PreStart =
getConstant(StartAI - Delta);
1487 FoldingSetNodeID
ID;
1489 ID.AddPointer(PreStart);
1490 ID.AddPointer(Step);
1494 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
1498 if (PreAR &&
any(PreAR->getNoWrapFlags(WrapType))) {
1501 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1502 DeltaS, &Pred,
this);
1520 const unsigned BitWidth =
C.getBitWidth();
1538 const APInt &ConstantStart,
1553 auto I = FoldCache.
insert({ID, S});
1557 auto &UserIDs = FoldCacheUser[
I.first->second];
1558 assert(
count(UserIDs, ID) == 1 &&
"unexpected duplicates in UserIDs");
1559 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1560 if (UserIDs[
I] == ID) {
1565 I.first->second = S;
1567 FoldCacheUser[S].push_back(ID);
1573 "This is not an extending conversion!");
1575 "This is not a conversion to a SCEVable type!");
1576 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1580 if (
const SCEV *S = FoldCache.lookup(ID))
1592 "This is not an extending conversion!");
1594 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1606 const SCEV *Start, *Step;
1611 if (AR->hasNoUnsignedWrap()) {
1622 ID.AddPointer(
Op.getOpaqueValue());
1625 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1629 UniqueSCEVs.InsertNode(S, IP);
1639 const SCEV *
X = ST->getOperand();
1672 const SCEV *CastedMaxBECount =
1676 if (MaxBECount == RecastedMaxBECount) {
1685 const SCEV *WideMaxBECount =
1687 const SCEV *OperandExtendedAdd =
1693 if (ZAdd == OperandExtendedAdd) {
1704 OperandExtendedAdd =
1710 if (ZAdd == OperandExtendedAdd) {
1731 !AC.assumptions().empty()) {
1733 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1735 if (AR->hasNoUnsignedWrap()) {
1770 const APInt &
C = SC->getAPInt();
1774 const SCEV *SResidual =
1782 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1806 if (SA->hasNoUnsignedWrap()) {
1819 if (SA->hasNoSignedWrap() &&
1822 C->isNegative() && !
C->isMinSignedValue() && C2->
sge(
C->abs())) {
1841 const SCEV *SResidual =
1852 if (SM->hasNoUnsignedWrap()) {
1874 const SCEV *TruncRHS;
1911 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1914 UniqueSCEVs.InsertNode(S, IP);
1923 "This is not an extending conversion!");
1925 "This is not a conversion to a SCEVable type!");
1926 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1930 if (
const SCEV *S = FoldCache.lookup(ID))
1942 "This is not an extending conversion!");
1944 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1961 const SCEV *Start, *Step;
1966 if (AR->hasNoSignedWrap()) {
1977 ID.AddPointer(
Op.getOpaqueValue());
1980 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1985 UniqueSCEVs.InsertNode(S, IP);
1995 const SCEV *
X = ST->getOperand();
2006 if (SA->hasNoSignedWrap()) {
2028 const SCEV *SResidual =
2061 const SCEV *CastedMaxBECount =
2065 if (MaxBECount == RecastedMaxBECount) {
2074 const SCEV *WideMaxBECount =
2076 const SCEV *OperandExtendedAdd =
2082 if (SAdd == OperandExtendedAdd) {
2093 OperandExtendedAdd =
2099 if (SAdd == OperandExtendedAdd) {
2119 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2121 if (AR->hasNoSignedWrap()) {
2135 const APInt &
C = SC->getAPInt();
2139 const SCEV *SResidual =
2147 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2174 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
2177 UniqueSCEVs.InsertNode(S, IP);
2193 assert(Expr->
getType() == Ty &&
"requested type must match");
2205 "This is not an extending conversion!");
2207 "This is not a conversion to a SCEVable type!");
2212 if (SC->getAPInt().isNegative())
2217 const SCEV *NewOp =
T->getOperand();
2236 for (
const SCEV *
Op : AR->operands())
2274 APInt &AccumulatedConstant,
2278 bool Interesting =
false;
2285 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2287 AccumulatedConstant += Scale *
C->getAPInt();
2292 for (; i !=
Ops.size(); ++i) {
2301 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2307 auto Pair = M.insert({
Key, NewScale});
2311 Pair.first->second += NewScale;
2319 auto Pair = M.insert({
Ops[i], Scale});
2323 Pair.first->second += Scale;
2342 case Instruction::Add:
2345 case Instruction::Sub:
2348 case Instruction::Mul:
2362 const SCEV *
A = (this->*Extension)(
2364 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2365 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2373 if (BinOp == Instruction::Mul)
2379 APInt C = RHSC->getAPInt();
2380 unsigned NumBits =
C.getBitWidth();
2381 bool IsSub = (BinOp == Instruction::Sub);
2382 bool IsNegativeConst = (
Signed &&
C.isNegative());
2384 bool OverflowDown = IsSub ^ IsNegativeConst;
2386 if (IsNegativeConst) {
2399 APInt Limit = Min + Magnitude;
2405 APInt Limit = Max - Magnitude;
2410std::optional<SCEV::NoWrapFlags>
2415 return std::nullopt;
2424 bool Deduced =
false;
2430 bool CanUseNSW =
true;
2431 const APInt *ShiftAmt;
2436 return std::nullopt;
2440 Opcode = Instruction::Mul;
2442 }
else if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
2443 Opcode != Instruction::Mul) {
2444 return std::nullopt;
2463 return std::nullopt;
2473 using namespace std::placeholders;
2480 assert(CanAnalyze &&
"don't call from other places!");
2487 auto IsKnownNonNegative = [&](
SCEVUse U) {
2496 if (SignOrUnsignWrap != SignOrUnsignMask &&
2503 return Instruction::Add;
2505 return Instruction::Mul;
2516 Opcode,
C, OBO::NoSignedWrap);
2524 Opcode,
C, OBO::NoUnsignedWrap);
2534 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2541 if (UDiv->getOperand(1) ==
Ops[1])
2544 if (UDiv->getOperand(1) ==
Ops[0])
2560 "only nuw or nsw allowed");
2561 assert(!
Ops.empty() &&
"Cannot get empty add!");
2562 if (
Ops.size() == 1)
return Ops[0];
2565 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2567 "SCEVAddExpr operand types don't match!");
2569 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2570 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2575 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2576 [](
const APInt &
C) {
return C.isZero(); },
2577 [](
const APInt &
C) {
return false; });
2590 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2595 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2596 Add->setNoWrapFlags(ComputeFlags(
Ops));
2604 bool FoundMatch =
false;
2605 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2606 if (
Ops[i] ==
Ops[i+1]) {
2618 --i; e -=
Count - 1;
2628 auto FindTruncSrcType = [&]() ->
Type * {
2634 return T->getOperand()->getType();
2636 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2638 return T->getOperand()->getType();
2642 if (
auto *SrcType = FindTruncSrcType()) {
2649 if (
T->getOperand()->getType() != SrcType) {
2658 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2661 if (
T->getOperand()->getType() != SrcType) {
2689 if (
Ops.size() == 2) {
2699 auto C2 =
C->getAPInt();
2702 APInt ConstAdd = C1 + C2;
2703 auto AddFlags = AddExpr->getNoWrapFlags();
2744 if (
Ops.size() == 2 &&
2755 if (Idx <
Ops.size()) {
2756 bool DeletedAdd =
false;
2767 Ops.erase(
Ops.begin()+Idx);
2770 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2793 struct APIntCompare {
2794 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2795 return LHS.ult(RHS);
2802 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2803 for (
const SCEV *NewOp : NewOps)
2804 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2807 if (AccumulatedConstant != 0)
2809 for (
auto &MulOp : MulOpLists) {
2810 if (MulOp.first == 1) {
2812 }
else if (MulOp.first != 0) {
2821 if (
Ops.size() == 1)
2830 if (M->getNumOperands() == 2)
2831 return M->getOperand(OpIdx == 0);
2833 append_range(Remaining, M->operands().drop_front(OpIdx + 1));
2842 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2846 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2854 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp) {
2855 if (MulOpSCEV ==
Ops[AddOp]) {
2866 for (
unsigned OMulOp = 0, OE = OtherMul->
getNumOperands(); OMulOp != OE;
2868 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2870 Cofactors.
push_back(StripFactor(OtherMul, OMulOp));
2879 if (!Cofactors.
empty()) {
2887 if (
Ops.size() == DeadIndices.
size() + 1)
2894 Ops.erase(
Ops.begin() + Idx);
2898 Ops.push_back(OuterMul);
2917 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2920 Ops.erase(
Ops.begin()+i);
2925 if (!LIOps.
empty()) {
2950 auto *DefI = getDefiningScopeBound(LIOps);
2952 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2964 if (
Ops.size() == 1)
return NewRec;
2967 for (
unsigned i = 0;; ++i)
2968 if (
Ops[i] == AddRec) {
2978 for (
unsigned OtherIdx = Idx+1;
2986 "AddRecExprs are not sorted in reverse dominance order?");
2993 if (OtherAddRec->getLoop() == AddRecLoop) {
2994 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2996 if (i >= AddRecOps.
size()) {
2997 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
3001 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
3004 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3019 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
3027 ID.AddPointer(
Op.getOpaqueValue());
3030 static_cast<SCEVAddExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
3034 S =
new (SCEVAllocator)
3036 UniqueSCEVs.InsertNode(S, IP);
3047 FoldingSetNodeID
ID;
3050 ID.AddPointer(
Op.getOpaqueValue());
3054 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
3058 S =
new (SCEVAllocator)
3059 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3060 UniqueSCEVs.InsertNode(S, IP);
3062 LoopUsers[
L].push_back(S);
3071 FoldingSetNodeID
ID;
3074 ID.AddPointer(
Op.getOpaqueValue());
3077 static_cast<SCEVMulExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
3081 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3083 UniqueSCEVs.InsertNode(S, IP);
3092 FoldingSetNodeID
ID;
3094 ID.AddPointer(
LHS.getOpaqueValue());
3095 ID.AddPointer(
RHS.getOpaqueValue());
3097 SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
3099 S =
new (SCEVAllocator) SCEVUDivExpr(
ID.Intern(SCEVAllocator),
LHS,
RHS);
3100 UniqueSCEVs.InsertNode(S, IP);
3109 if (j > 1 && k / j != i) Overflow =
true;
3125 if (n == 0 || n == k)
return 1;
3126 if (k > n)
return 0;
3132 for (
uint64_t i = 1; i <= k; ++i) {
3133 r =
umul_ov(r, n-(i-1), Overflow);
3142 struct FindConstantInAddMulChain {
3143 bool FoundConstant =
false;
3145 bool follow(
const SCEV *S) {
3150 bool isDone()
const {
3151 return FoundConstant;
3155 FindConstantInAddMulChain
F;
3157 ST.visitAll(StartExpr);
3158 return F.FoundConstant;
3166 "only nuw or nsw allowed");
3167 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3168 if (
Ops.size() == 1)
return Ops[0];
3170 Type *ETy =
Ops[0]->getType();
3172 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3174 "SCEVMulExpr operand types don't match!");
3179 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3180 [](
const APInt &
C) {
return C.isOne(); },
3181 [](
const APInt &
C) {
return C.isZero(); });
3192 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3197 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3198 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3203 if (
Ops.size() == 2) {
3211 const SCEV *Op0, *Op1;
3219 if (
Ops[0]->isAllOnesValue()) {
3224 bool AnyFolded =
false;
3225 for (
const SCEV *AddOp :
Add->operands()) {
3245 if (AddRec->hasNoSignedWrap()) {
3252 AddRec->getNoWrapFlags(FlagsMask));
3275 APInt C1V = LHSC->getAPInt();
3285 const SCEV *NewMul =
nullptr;
3289 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3304 if (Idx <
Ops.size()) {
3305 bool DeletedMul =
false;
3311 Ops.erase(
Ops.begin()+Idx);
3335 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3338 Ops.erase(
Ops.begin()+i);
3343 if (!LIOps.
empty()) {
3356 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3372 if (
Ops.size() == 1)
return NewRec;
3375 for (
unsigned i = 0;; ++i)
3376 if (
Ops[i] == AddRec) {
3397 bool OpsModified =
false;
3398 for (
unsigned OtherIdx = Idx+1;
3412 bool Overflow =
false;
3419 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3420 uint64_t Coeff1 =
Choose(x, 2*x - y, Overflow);
3423 z < ze && !Overflow; ++z) {
3424 uint64_t Coeff2 =
Choose(2*x - y, x-z, Overflow);
3426 if (LargerThan64Bits)
3427 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3429 Coeff = Coeff1*Coeff2;
3444 if (
Ops.size() == 2)
return NewAddRec;
3445 Ops[Idx] = NewAddRec;
3446 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3462 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3469 "SCEVURemExpr operand types don't match!");
3474 if (RHSC->getValue()->isOne())
3475 return getZero(LHS->getType());
3478 if (RHSC->getAPInt().isPowerOf2()) {
3479 Type *FullTy = LHS->getType();
3495 assert(!LHS->getType()->isPointerTy() &&
3496 "SCEVUDivExpr operand can't be pointer!");
3497 assert(LHS->getType() == RHS->getType() &&
3498 "SCEVUDivExpr operand types don't match!");
3509 if (RHSC->getValue()->isOne())
3514 if (!RHSC->getValue()->isZero()) {
3518 Type *Ty = LHS->getType();
3519 unsigned LZ = RHSC->getAPInt().countl_zero();
3523 if (!RHSC->getAPInt().isPowerOf2())
3531 const APInt &StepInt = Step->getAPInt();
3532 const APInt &DivInt = RHSC->getAPInt();
3533 if (!StepInt.
urem(DivInt) &&
3539 for (
const SCEV *
Op : AR->operands())
3545 const APInt *StartRem;
3558 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3562 const SCEV *NewStart =
3564 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3566 const SCEV *NewLHS =
3576 if (M->hasNoUnsignedWrap()) {
3578 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3579 const SCEV *
Op = M->getOperand(i);
3606 if (
auto *DivisorConstant =
3608 bool Overflow =
false;
3610 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3621 if (
A->hasNoUnsignedWrap()) {
3623 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3630 if (
Operands.size() ==
A->getNumOperands())
3642 const APInt &
N = RHSC->getAPInt();
3643 const APInt *NMinusM, *M;
3647 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3648 *NMinusM ==
N - *M) {
3657 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3667 return getZero(LHS->getType());
3671 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3672 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3673 if (
Mul->getOperand(i) == RHS) {
3684 const SCEV *NewLHS, *NewRHS;
3689 return getOrCreateUDivExpr(LHS, RHS);
3709 if (StepChrec->getLoop() == L) {
3728 "SCEVAddRecExpr operand types don't match!");
3729 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3733 "SCEVAddRecExpr operand is not available at loop entry!");
3751 const Loop *NestedLoop = NestedAR->getLoop();
3752 if (L->contains(NestedLoop)
3755 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3757 Operands[0] = NestedAR->getStart();
3761 bool AllInvariant =
all_of(
3773 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3784 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3794 return getOrCreateAddRecExpr(
Operands, L, Flags);
3810 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3814 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3828 bool FirstIter =
true;
3830 for (
SCEVUse IndexExpr : IndexExprs) {
3837 Offsets.push_back(FieldOffset);
3840 CurTy = STy->getTypeAtIndex(Index);
3845 "The first index of a GEP indexes a pointer");
3846 CurTy = SrcElementTy;
3857 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3858 Offsets.push_back(LocalOffset);
3863 if (Offsets.empty())
3876 "GEP should not change type mid-flight.");
3880SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3885 ID.AddPointer(
Op.getOpaqueValue());
3887 return UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
3897 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3898 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3899 if (
Ops.size() == 1)
return Ops[0];
3902 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3904 "Operand types don't match!");
3907 "min/max should be consistently pointerish");
3933 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3935 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3940 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3942 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3948 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3954 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3959 if (Idx <
Ops.size()) {
3960 bool DeletedAny =
false;
3961 while (
Ops[Idx]->getSCEVType() == Kind) {
3963 Ops.erase(
Ops.begin()+Idx);
3981 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3982 if (
Ops[i] ==
Ops[i + 1] ||
3983 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3986 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3989 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3992 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3998 if (
Ops.size() == 1)
return Ops[0];
4000 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
4007 ID.AddPointer(
Op.getOpaqueValue());
4009 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
4011 return ExistingSCEV;
4014 SCEV *S =
new (SCEVAllocator)
4017 UniqueSCEVs.InsertNode(S, IP);
4025class SCEVSequentialMinMaxDeduplicatingVisitor final
4026 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4027 std::optional<const SCEV *>> {
4028 using RetVal = std::optional<const SCEV *>;
4036 bool canRecurseInto(
SCEVTypes Kind)
const {
4039 return RootKind == Kind || NonSequentialRootKind == Kind;
4042 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
4044 "Only for min/max expressions.");
4047 if (!canRecurseInto(Kind))
4057 return std::nullopt;
4064 RetVal
visit(
const SCEV *S) {
4066 if (!SeenOps.
insert(S).second)
4067 return std::nullopt;
4068 return Base::visit(S);
4072 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4074 : SE(SE), RootKind(RootKind),
4075 NonSequentialRootKind(
4076 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4080 SmallVectorImpl<SCEVUse> &NewOps) {
4085 for (
const SCEV *
Op : OrigOps) {
4090 Ops.emplace_back(*NewOp);
4094 NewOps = std::move(
Ops);
4098 RetVal visitConstant(
const SCEVConstant *Constant) {
return Constant; }
4100 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4102 RetVal visitPtrToAddrExpr(
const SCEVPtrToAddrExpr *Expr) {
return Expr; }
4104 RetVal visitTruncateExpr(
const SCEVTruncateExpr *Expr) {
return Expr; }
4106 RetVal visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
return Expr; }
4108 RetVal visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
return Expr; }
4110 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4112 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4114 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4116 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4118 RetVal visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
4119 return visitAnyMinMaxExpr(Expr);
4122 RetVal visitUMaxExpr(
const SCEVUMaxExpr *Expr) {
4123 return visitAnyMinMaxExpr(Expr);
4126 RetVal visitSMinExpr(
const SCEVSMinExpr *Expr) {
4127 return visitAnyMinMaxExpr(Expr);
4130 RetVal visitUMinExpr(
const SCEVUMinExpr *Expr) {
4131 return visitAnyMinMaxExpr(Expr);
4134 RetVal visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *Expr) {
4135 return visitAnyMinMaxExpr(Expr);
4138 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4140 RetVal visitCouldNotCompute(
const SCEVCouldNotCompute *Expr) {
return Expr; }
4182struct SCEVPoisonCollector {
4183 bool LookThroughMaybePoisonBlocking;
4184 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4185 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4186 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4188 bool follow(
const SCEV *S) {
4189 if (!LookThroughMaybePoisonBlocking &&
4199 bool isDone()
const {
return false; }
4209 SCEVPoisonCollector PC1(
true);
4214 if (PC1.MaybePoison.empty())
4220 SCEVPoisonCollector PC2(
false);
4230 SCEVPoisonCollector PC(
false);
4253 while (!Worklist.
empty()) {
4255 if (!Visited.
insert(V).second)
4259 if (Visited.
size() > 16)
4275 if (PDI->isDisjoint())
4282 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4289 if (
I->hasPoisonGeneratingAnnotations())
4300 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4301 "Not a SCEVSequentialMinMaxExpr!");
4302 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4303 if (
Ops.size() == 1)
4307 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4309 "Operand types don't match!");
4312 "min/max should be consistently pointerish");
4320 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4327 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4337 bool DeletedAny =
false;
4338 while (Idx <
Ops.size()) {
4339 if (
Ops[Idx]->getSCEVType() != Kind) {
4344 Ops.erase(
Ops.begin() + Idx);
4345 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4346 SMME->operands().end());
4354 const SCEV *SaturationPoint;
4365 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4366 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4378 Ops.erase(
Ops.begin() + i);
4383 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4384 Ops.erase(
Ops.begin() + i);
4394 ID.AddPointer(
Op.getOpaqueValue());
4396 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
4398 return ExistingSCEV;
4402 SCEV *S =
new (SCEVAllocator)
4405 UniqueSCEVs.InsertNode(S, IP);
4453 if (
Size.isScalable())
4474 "Cannot get offset for structure containing scalable vector types");
4488 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) {
4490 "Stale SCEVUnknown in uniquing map!");
4493 SCEV *S =
new (SCEVAllocator)
SCEVUnknown(ID.Intern(SCEVAllocator), V,
this,
4496 UniqueSCEVs.InsertNode(S, IP);
4511 return Ty->isIntOrPtrTy();
4518 if (Ty->isPointerTy())
4529 if (Ty->isIntegerTy())
4533 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4545 bool PreciseA, PreciseB;
4546 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4547 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4548 if (!PreciseA || !PreciseB)
4551 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4552 DT.dominates(ScopeB, ScopeA);
4556 return CouldNotCompute.get();
4559bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4562 return SU && SU->getValue() ==
nullptr;
4565 return !ContainsNulls;
4570 if (
I != HasRecMap.end())
4575 HasRecMap.insert({S, FoundAddRec});
4583 if (
SI == ExprValueMap.
end())
4585 return SI->second.getArrayRef();
4591void ScalarEvolution::eraseValueFromMap(
Value *V) {
4593 if (
I != ValueExprMap.end()) {
4594 auto EVIt = ExprValueMap.find(
I->second);
4595 bool Removed = EVIt->second.remove(V);
4597 assert(Removed &&
"Value not in ExprValueMap?");
4598 ValueExprMap.erase(
I);
4602void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4606 auto It = ValueExprMap.find_as(V);
4607 if (It == ValueExprMap.end()) {
4609 ExprValueMap[S].insert(V);
4620 return createSCEVIter(V);
4627 if (
I != ValueExprMap.end()) {
4628 const SCEV *S =
I->second;
4629 assert(checkValidity(S) &&
4630 "existing SCEV has not been properly invalidated");
4643 Type *Ty = V->getType();
4659 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4672 return (
const SCEV *)
nullptr;
4678 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4682 Type *Ty = V->getType();
4688 assert(
P->getType()->isPointerTy());
4703 if (AddOp->getType()->isPointerTy()) {
4704 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4722 return getZero(LHS->getType());
4727 if (RHS->getType()->isPointerTy()) {
4728 if (!LHS->getType()->isPointerTy() ||
4738 const bool RHSIsNotMinSigned =
4769 Type *SrcTy = V->getType();
4770 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4771 "Cannot truncate or zero extend with non-integer arguments!");
4781 Type *SrcTy = V->getType();
4782 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4783 "Cannot truncate or zero extend with non-integer arguments!");
4792 Type *SrcTy = V->getType();
4793 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4794 "Cannot noop or zero extend with non-integer arguments!");
4796 "getNoopOrZeroExtend cannot truncate!");
4803 Type *SrcTy = V->getType();
4804 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4805 "Cannot noop or sign extend with non-integer arguments!");
4807 "getNoopOrSignExtend cannot truncate!");
4814 Type *SrcTy = V->getType();
4815 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4816 "Cannot noop or any extend with non-integer arguments!");
4818 "getNoopOrAnyExtend cannot truncate!");
4825 Type *SrcTy = V->getType();
4826 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4827 "Cannot truncate or noop with non-integer arguments!");
4829 "getTruncateOrNoop cannot extend!");
4837 const SCEV *PromotedLHS = LHS;
4838 const SCEV *PromotedRHS = RHS;
4858 assert(!
Ops.empty() &&
"At least one operand must be!");
4860 if (
Ops.size() == 1)
4864 Type *MaxType =
nullptr;
4870 assert(MaxType &&
"Failed to find maximum type!");
4883 if (!V->getType()->isPointerTy())
4888 V = AddRec->getStart();
4890 const SCEV *PtrOp =
nullptr;
4891 for (
const SCEV *AddOp :
Add->operands()) {
4892 if (AddOp->getType()->isPointerTy()) {
4893 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4897 assert(PtrOp &&
"Must have pointer op");
4909 for (
User *U :
I->users()) {
4911 if (Visited.
insert(UserInsn).second)
4925 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4926 bool IgnoreOtherLoops =
true) {
4929 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4931 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4936 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4938 SeenLoopVariantSCEVUnknown =
true;
4942 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4946 SeenOtherLoops =
true;
4950 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4952 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4955 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4956 : SCEVRewriteVisitor(SE),
L(
L) {}
4959 bool SeenLoopVariantSCEVUnknown =
false;
4960 bool SeenOtherLoops =
false;
4969 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4970 SCEVPostIncRewriter
Rewriter(L, SE);
4972 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4977 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4979 SeenLoopVariantSCEVUnknown =
true;
4983 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4987 SeenOtherLoops =
true;
4991 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4993 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4996 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4997 : SCEVRewriteVisitor(SE),
L(
L) {}
5000 bool SeenLoopVariantSCEVUnknown =
false;
5001 bool SeenOtherLoops =
false;
5007class SCEVBackedgeConditionFolder
5010 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5011 ScalarEvolution &SE) {
5012 bool IsPosBECond =
false;
5013 Value *BECond =
nullptr;
5014 if (BasicBlock *Latch =
L->getLoopLatch()) {
5016 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
5017 "Both outgoing branches should not target same header!");
5018 BECond = BI->getCondition();
5019 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
5024 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
5028 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5029 const SCEV *
Result = Expr;
5034 switch (
I->getOpcode()) {
5035 case Instruction::Select: {
5037 std::optional<const SCEV *> Res =
5038 compareWithBackedgeCondition(
SI->getCondition());
5046 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5057 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5058 bool IsPosBECond, ScalarEvolution &SE)
5059 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5060 IsPositiveBECond(IsPosBECond) {}
5062 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5066 Value *BackedgeCond =
nullptr;
5068 bool IsPositiveBECond;
5071std::optional<const SCEV *>
5072SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5077 if (BackedgeCond == IC)
5080 return std::nullopt;
5085 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5086 ScalarEvolution &SE) {
5092 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5099 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5109 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5110 : SCEVRewriteVisitor(SE),
L(
L) {}
5118void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5134 const APInt &BECountAP = BECountMax->getAPInt();
5135 unsigned NoOverflowBitWidth =
5144ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5154 if (!SignedWrapViaInductionTried.insert(AR).second)
5179 AC.assumptions().empty())
5187 const SCEV *OverflowLimit =
5189 if (OverflowLimit &&
5197ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5207 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5232 AC.assumptions().empty())
5241 const SCEV *OverflowLimit =
5270 IsNSW = OBO->hasNoSignedWrap();
5271 IsNUW = OBO->hasNoUnsignedWrap();
5277 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5289 return std::nullopt;
5295 switch (
Op->getOpcode()) {
5296 case Instruction::Add:
5297 case Instruction::Sub:
5298 case Instruction::Mul:
5299 case Instruction::UDiv:
5300 case Instruction::URem:
5301 case Instruction::And:
5302 case Instruction::AShr:
5303 case Instruction::Shl:
5306 case Instruction::Or: {
5309 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5319 case Instruction::Xor:
5323 if (RHSC->getValue().isSignMask())
5324 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5326 if (V->getType()->isIntegerTy(1))
5327 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5330 case Instruction::LShr:
5339 if (SA->getValue().ult(
BitWidth)) {
5341 ConstantInt::get(SA->getContext(),
5343 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5348 case Instruction::ExtractValue: {
5350 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5358 bool Signed = WO->isSigned();
5361 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5366 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5377 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5378 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5380 return std::nullopt;
5406 if (
Op == SymbolicPHI)
5411 if (SourceBits != NewBits)
5429 if (!L || L->getHeader() != PN->
getParent())
5487std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5488ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5496 assert(L &&
"Expecting an integer loop header phi");
5501 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5502 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5503 Value *
V = PN->getIncomingValue(i);
5504 if (
L->contains(PN->getIncomingBlock(i))) {
5507 }
else if (BEValueV != V) {
5511 }
else if (!StartValueV) {
5513 }
else if (StartValueV != V) {
5514 StartValueV =
nullptr;
5518 if (!BEValueV || !StartValueV)
5519 return std::nullopt;
5521 const SCEV *BEValue =
getSCEV(BEValueV);
5528 return std::nullopt;
5532 unsigned FoundIndex =
Add->getNumOperands();
5533 Type *TruncTy =
nullptr;
5535 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5538 if (FoundIndex == e) {
5543 if (FoundIndex ==
Add->getNumOperands())
5544 return std::nullopt;
5548 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5549 if (i != FoundIndex)
5550 Ops.push_back(
Add->getOperand(i));
5556 return std::nullopt;
5609 const SCEV *StartVal =
getSCEV(StartValueV);
5610 const SCEV *PHISCEV =
5637 auto getExtendedExpr = [&](
const SCEV *Expr,
5638 bool CreateSignExtend) ->
const SCEV * {
5641 const SCEV *ExtendedExpr =
5644 return ExtendedExpr;
5652 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5653 const SCEV *ExtendedExpr) ->
bool {
5654 return Expr != ExtendedExpr &&
5658 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5659 if (PredIsKnownFalse(StartVal, StartExtended)) {
5661 return std::nullopt;
5666 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5667 if (PredIsKnownFalse(Accum, AccumExtended)) {
5669 return std::nullopt;
5672 auto AppendPredicate = [&](
const SCEV *Expr,
5673 const SCEV *ExtendedExpr) ->
void {
5674 if (Expr != ExtendedExpr &&
5682 AppendPredicate(StartVal, StartExtended);
5683 AppendPredicate(Accum, AccumExtended);
5691 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5692 std::make_pair(NewAR, Predicates);
5694 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5698std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5703 return std::nullopt;
5706 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5707 if (
I != PredicatedSCEVRewrites.end()) {
5708 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5711 if (Rewrite.first == SymbolicPHI)
5712 return std::nullopt;
5716 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5720 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5721 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5726 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5727 return std::nullopt;
5747 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5748 if (Expr1 != Expr2 &&
5749 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5750 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5767const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5769 Value *StartValueV) {
5772 assert(BEValueV && StartValueV);
5778 if (BO->Opcode != Instruction::Add)
5781 const SCEV *Accum =
nullptr;
5782 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5784 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5798 insertValueToMap(PN, PHISCEV);
5801 inferNoWrapViaConstantRanges(AR);
5808 "Accum is defined outside L, but is not invariant?");
5809 if (isAddRecNeverPoison(BEInst, L))
5816const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5824 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5830 }
else if (BEValueV != V) {
5834 }
else if (!StartValueV) {
5836 }
else if (StartValueV != V) {
5837 StartValueV =
nullptr;
5841 if (!BEValueV || !StartValueV)
5844 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5845 "PHI node already processed?");
5849 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5854 insertValueToMap(PN, SymbolicName);
5858 const SCEV *BEValue =
getSCEV(BEValueV);
5868 unsigned FoundIndex =
Add->getNumOperands();
5869 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5870 if (
Add->getOperand(i) == SymbolicName)
5871 if (FoundIndex == e) {
5876 if (FoundIndex !=
Add->getNumOperands()) {
5879 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5880 if (i != FoundIndex)
5881 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5893 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5900 if (
GEP->getOperand(0) == PN) {
5901 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
5919 const SCEV *StartVal =
getSCEV(StartValueV);
5920 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5925 forgetMemoizedResults({SymbolicName});
5926 insertValueToMap(PN, PHISCEV);
5929 inferNoWrapViaConstantRanges(AR);
5953 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5954 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5956 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5957 const SCEV *StartVal =
getSCEV(StartValueV);
5958 if (Start == StartVal) {
5962 forgetMemoizedResults({SymbolicName});
5963 insertValueToMap(PN, Shifted);
5973 eraseValueFromMap(PN);
5988 Use &LeftUse =
Merge->getOperandUse(0);
5989 Use &RightUse =
Merge->getOperandUse(1);
6025 assert(IDom &&
"At least the entry block should dominate PN");
6033const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
6038 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6055 CommonInst = IncomingInst;
6071ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6077 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6078 bool SCEVExprsIdentical =
6080 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6081 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6084const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6085 if (
const SCEV *S = createAddRecFromPHI(PN))
6095 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6098 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6107 struct FindClosure {
6108 const SCEV *OperandToFind;
6114 bool canRecurseInto(
SCEVTypes Kind)
const {
6117 return RootKind == Kind || NonSequentialRootKind == Kind ||
6122 : OperandToFind(OperandToFind), RootKind(RootKind),
6123 NonSequentialRootKind(
6127 bool follow(
const SCEV *S) {
6128 Found = S == OperandToFind;
6130 return !isDone() && canRecurseInto(S->
getSCEVType());
6133 bool isDone()
const {
return Found; }
6136 FindClosure FC(OperandToFind, RootKind);
6141std::optional<const SCEV *>
6142ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6152 switch (ICI->getPredicate()) {
6166 bool Signed = ICI->isSigned();
6167 const SCEV *LA =
getSCEV(TrueVal);
6175 if (LA == LS &&
RA == RS)
6177 if (LA == RS &&
RA == LS)
6180 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6181 if (
Op->getType()->isPointerTy()) {
6192 LS = CoerceOperand(LS);
6193 RS = CoerceOperand(RS);
6217 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6218 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6232 X = ZExt->getOperand();
6234 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6245 return std::nullopt;
6248static std::optional<const SCEV *>
6250 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6254 "Unexpected operands of a select.");
6266 return std::nullopt;
6281static std::optional<const SCEV *>
6285 return std::nullopt;
6288 const auto *SETrue = SE->
getSCEV(TrueVal);
6289 const auto *SEFalse = SE->
getSCEV(FalseVal);
6293const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6295 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6297 V->getType() ==
TrueVal->getType() &&
6298 "Types of select hands and of the result must match.");
6301 if (!
V->getType()->isIntegerTy(1))
6304 if (std::optional<const SCEV *> S =
6317 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6321 if (std::optional<const SCEV *> S =
6322 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6328 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6334 assert(
GEP->getSourceElementType()->isSized() &&
6335 "GEP source element type must be sized");
6338 for (
Value *Index :
GEP->indices())
6343APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6346 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6349 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6351 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6354 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6372 return GetShiftedByZeros(TZ);
6382 return GetShiftedByZeros(TZ);
6386 if (
M->hasNoUnsignedWrap()) {
6389 for (
const SCEV *Operand :
M->operands().drop_front())
6397 for (
const SCEV *Operand :
M->operands())
6399 return GetShiftedByZeros(TZ);
6404 if (
N->hasNoUnsignedWrap())
6405 return GetGCDMultiple(
N);
6408 for (
const SCEV *Operand :
N->operands().drop_front())
6410 return GetShiftedByZeros(TZ);
6427 CtxI = &*F.getEntryBlock().begin();
6434 .allowEphemerals(
true))
6435 .countMinTrailingZeros();
6436 return GetShiftedByZeros(
Known);
6449 return getConstantMultipleImpl(S, CtxI);
6451 auto I = ConstantMultipleCache.find(S);
6452 if (
I != ConstantMultipleCache.end())
6455 APInt Result = getConstantMultipleImpl(S, CtxI);
6456 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6457 assert(InsertPair.second &&
"Should insert a new key");
6458 return InsertPair.first->second;
6475 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6478 if (std::optional<ConstantRange>
Range = CB->getRange())
6482 if (std::optional<ConstantRange>
Range =
A->getRange())
6485 return std::nullopt;
6492 UnsignedRanges.erase(AddRec);
6493 SignedRanges.erase(AddRec);
6494 ConstantMultipleCache.erase(AddRec);
6499getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6525 Value *Start, *Step;
6532 assert(L && L->getHeader() ==
P->getParent());
6545 case Instruction::AShr:
6546 case Instruction::LShr:
6547 case Instruction::Shl:
6562 KnownStep.getBitWidth() ==
BitWidth);
6565 auto MaxShiftAmt = KnownStep.getMaxValue();
6567 bool Overflow =
false;
6568 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6575 case Instruction::AShr: {
6583 if (KnownStart.isNonNegative())
6586 KnownStart.getMaxValue() + 1);
6587 if (KnownStart.isNegative())
6590 KnownEnd.getMaxValue() + 1);
6593 case Instruction::LShr: {
6602 KnownStart.getMaxValue() + 1);
6604 case Instruction::Shl: {
6608 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6609 return ConstantRange(KnownStart.getMinValue(),
6610 KnownEnd.getMaxValue() + 1);
6635 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6642ScalarEvolution::getRangeRefIter(
const SCEV *S,
6643 ScalarEvolution::RangeSignHint SignHint) {
6644 DenseMap<const SCEV *, ConstantRange> &Cache =
6645 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6648 SmallPtrSet<const SCEV *, 8> Seen;
6652 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6653 if (!Seen.
insert(Expr).second)
6686 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6687 const SCEV *
P = WorkList[
I];
6691 for (
const SCEV *
Op :
P->operands())
6704 if (!WorkList.
empty()) {
6709 getRangeRef(
P, SignHint);
6713 return getRangeRef(S, SignHint, 0);
6716const APInt *ScalarEvolution::getConstantAPIntOrNull(
const SCEV *S) {
6718 return &
C->getAPInt();
6726 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6727 DenseMap<const SCEV *, ConstantRange> &Cache =
6728 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6735 auto I = Cache.
find(S);
6736 if (
I != Cache.
end())
6740 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6745 return getRangeRefIter(S, SignHint);
6748 ConstantRange ConservativeResult(
BitWidth,
true);
6749 using OBO = OverflowingBinaryOperator;
6753 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6757 ConservativeResult =
6764 ConservativeResult = ConstantRange(
6780 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6787 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6794 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6799 return setRange(Cast, SignHint,
X);
6804 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6805 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6807 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6808 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6809 ConservativeResult =
6810 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6812 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6813 unsigned WrapType = OBO::AnyWrap;
6814 if (
Add->hasNoSignedWrap())
6815 WrapType |= OBO::NoSignedWrap;
6816 if (
Add->hasNoUnsignedWrap())
6817 WrapType |= OBO::NoUnsignedWrap;
6819 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6821 return setRange(
Add, SignHint,
6822 ConservativeResult.intersectWith(
X, RangeType));
6826 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6828 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6829 return setRange(
Mul, SignHint,
6830 ConservativeResult.intersectWith(
X, RangeType));
6834 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6835 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6836 return setRange(UDiv, SignHint,
6837 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6845 if (!UnsignedMinValue.
isZero())
6846 ConservativeResult = ConservativeResult.intersectWith(
6847 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6856 bool AllNonNeg =
true;
6857 bool AllNonPos =
true;
6858 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6865 ConservativeResult = ConservativeResult.intersectWith(
6870 ConservativeResult = ConservativeResult.intersectWith(
6879 const SCEV *MaxBEScev =
6893 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6895 ConservativeResult =
6896 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6899 auto RangeFromFactoring = getRangeViaFactoring(
6901 ConservativeResult =
6902 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6908 const SCEV *SymbolicMaxBECount =
6913 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6914 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6915 ConservativeResult =
6916 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6921 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6931 ID = Intrinsic::umax;
6934 ID = Intrinsic::smax;
6938 ID = Intrinsic::umin;
6941 ID = Intrinsic::smin;
6948 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6949 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6951 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6952 return setRange(S, SignHint,
6953 ConservativeResult.intersectWith(
X, RangeType));
6962 ConservativeResult =
6963 ConservativeResult.intersectWith(*MDRange, RangeType);
6968 auto CR = getRangeForUnknownRecurrence(U);
6969 ConservativeResult = ConservativeResult.intersectWith(CR);
6980 if (
U->getType()->isPointerTy()) {
6983 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
6984 int ptrIdxDiff = ptrSize -
BitWidth;
6985 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
6991 if (!
Known.Zero.getHiBits(NS).isZero())
6992 Known.Zero.setHighBits(NS);
6993 if (!
Known.One.getHiBits(NS).isZero())
6994 Known.One.setHighBits(NS);
6997 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
6998 ConservativeResult = ConservativeResult.intersectWith(
6999 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
7002 ConservativeResult = ConservativeResult.intersectWith(
7007 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
7011 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
7012 DL, CanBeNull,
nullptr);
7028 ConservativeResult = ConservativeResult.intersectWith(
7038 return getRangeRef(AR, SignHint,
Depth + 1);
7042 ConstantRange RangeFromOps(
BitWidth,
false);
7044 for (
const auto &
Op :
Phi->operands()) {
7046 RangeFromOps = RangeFromOps.unionWith(OpRange);
7048 if (RangeFromOps.isFullSet())
7051 ConservativeResult =
7052 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7058 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7060 ConservativeResult = ConservativeResult.difference(Disallowed);
7063 return setRange(U, SignHint, std::move(ConservativeResult));
7069 return setRange(S, SignHint, std::move(ConservativeResult));
7077static std::pair<ConstantRange, bool>
7085 if (Step == 0 || MaxBECount == 0)
7086 return {StartRange,
true};
7092 return {ConstantRange::getFull(
BitWidth),
false};
7108 return {ConstantRange::getFull(
BitWidth),
false};
7121 APInt MovedBoundary;
7126 MovedBoundary = StartLower - std::move(
Offset);
7129 MovedBoundary = StartUpper + std::move(
Offset);
7133 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7140 if (StartRange.
contains(MovedBoundary))
7141 return {ConstantRange::getFull(
BitWidth),
false};
7144 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7146 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7154std::pair<ConstantRange, SCEV::NoWrapFlags>
7155ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7156 const APInt &MaxBECount) {
7160 "mismatched bit widths");
7169 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7171 StartSRange, MaxBECount,
7173 ConstantRange SR = SR1.unionWith(SR2);
7190ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7192 ScalarEvolution::RangeSignHint SignHint) {
7193 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7195 "This only works for non-self-wrapping AddRecs!");
7196 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7200 return ConstantRange::getFull(
BitWidth);
7208 return ConstantRange::getFull(
BitWidth);
7212 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7214 MaxItersWithoutWrap))
7215 return ConstantRange::getFull(
BitWidth);
7236 ConstantRange StartRange = getRangeRef(Start, SignHint);
7237 ConstantRange EndRange = getRangeRef(End, SignHint);
7238 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7242 return RangeBetween;
7247 return ConstantRange::getFull(
BitWidth);
7250 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7251 return RangeBetween;
7253 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7254 return RangeBetween;
7255 return ConstantRange::getFull(
BitWidth);
7260 const APInt &MaxBECount) {
7267 "mismatched bit widths");
7269 struct SelectPattern {
7270 Value *Condition =
nullptr;
7274 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7276 std::optional<unsigned> CastOp;
7290 CastOp = SCast->getSCEVType();
7291 S = SCast->getOperand();
7294 using namespace llvm::PatternMatch;
7301 Condition =
nullptr;
7333 bool isRecognized() {
return Condition !=
nullptr; }
7336 SelectPattern StartPattern(*
this,
BitWidth, Start);
7337 if (!StartPattern.isRecognized())
7338 return ConstantRange::getFull(
BitWidth);
7340 SelectPattern StepPattern(*
this,
BitWidth, Step);
7341 if (!StepPattern.isRecognized())
7342 return ConstantRange::getFull(
BitWidth);
7344 if (StartPattern.Condition != StepPattern.Condition) {
7348 return ConstantRange::getFull(
BitWidth);
7359 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7360 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7361 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7362 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7364 ConstantRange TrueRange =
7365 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7366 ConstantRange FalseRange =
7367 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7379 PDI && PDI->isDisjoint()) {
7394ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7407 SmallPtrSet<const SCEV *, 16> Visited;
7409 auto pushOp = [&](
const SCEV *S) {
7410 if (!Visited.
insert(S).second)
7413 if (Visited.
size() > 30) {
7424 while (!Worklist.
empty()) {
7426 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7427 if (!Bound || DT.dominates(Bound, DefI))
7434 return Bound ? Bound : &*F.getEntryBlock().begin();
7440 return getDefiningScopeBound(
Ops, Discard);
7443bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7445 if (
A->getParent() ==
B->getParent() &&
7450 auto *BLoop = LI.getLoopFor(
B->getParent());
7451 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7452 BLoop->getLoopPreheader() ==
A->getParent() &&
7454 A->getParent()->end()) &&
7462 SCEVPoisonCollector PC(
true);
7464 return PC.MaybePoison.empty();
7467bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7477bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7494 for (
const Use &
Op :
I->operands()) {
7500 auto *DefI = getDefiningScopeBound(SCEVOps);
7501 return isGuaranteedToTransferExecutionTo(DefI,
I);
7504bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7506 if (isSCEVExprNeverPoison(
I))
7517 auto *ExitingBB =
L->getExitingBlock();
7521 SmallPtrSet<const Value *, 16> KnownPoison;
7530 while (!Worklist.
empty()) {
7533 for (
const Use &U :
Poison->uses()) {
7536 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7540 if (KnownPoison.
insert(PoisonUser).second)
7548ScalarEvolution::LoopProperties
7549ScalarEvolution::getLoopProperties(
const Loop *L) {
7550 using LoopProperties = ScalarEvolution::LoopProperties;
7552 auto Itr = LoopPropertiesCache.find(L);
7553 if (Itr == LoopPropertiesCache.end()) {
7556 return !
SI->isSimple();
7566 return I->mayWriteToMemory();
7569 LoopProperties LP = {
true,
7572 for (
auto *BB :
L->getBlocks())
7573 for (
auto &
I : *BB) {
7575 LP.HasNoAbnormalExits =
false;
7576 if (HasSideEffects(&
I))
7577 LP.HasNoSideEffects =
false;
7578 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7582 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7583 assert(InsertPair.second &&
"We just checked!");
7584 Itr = InsertPair.first;
7597const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7603 Stack.emplace_back(V,
false);
7604 while (!Stack.empty()) {
7605 auto E = Stack.back();
7606 Value *CurV = E.getPointer();
7614 const SCEV *CreatedSCEV =
nullptr;
7617 CreatedSCEV = createSCEV(CurV);
7622 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7626 insertValueToMap(CurV, CreatedSCEV);
7629 Stack.back().setInt(
true);
7632 Stack.emplace_back(
Op,
false);
7649 if (!DT.isReachableFromEntry(
I->getParent()))
7662 switch (BO->Opcode) {
7663 case Instruction::Add:
7664 case Instruction::Mul: {
7671 Ops.push_back(BO->
Op);
7675 Ops.push_back(BO->RHS);
7679 (BO->Opcode == Instruction::Add &&
7680 (NewBO->Opcode != Instruction::Add &&
7681 NewBO->Opcode != Instruction::Sub)) ||
7682 (BO->Opcode == Instruction::Mul &&
7683 NewBO->Opcode != Instruction::Mul)) {
7684 Ops.push_back(BO->LHS);
7689 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7692 Ops.push_back(BO->LHS);
7700 case Instruction::Sub:
7701 case Instruction::UDiv:
7702 case Instruction::URem:
7704 case Instruction::AShr:
7705 case Instruction::Shl:
7706 case Instruction::Xor:
7710 case Instruction::And:
7711 case Instruction::Or:
7715 case Instruction::LShr:
7722 Ops.push_back(BO->LHS);
7723 Ops.push_back(BO->RHS);
7727 switch (
U->getOpcode()) {
7728 case Instruction::Trunc:
7729 case Instruction::ZExt:
7730 case Instruction::SExt:
7731 case Instruction::PtrToAddr:
7732 case Instruction::PtrToInt:
7733 Ops.push_back(
U->getOperand(0));
7736 case Instruction::BitCast:
7738 Ops.push_back(
U->getOperand(0));
7743 case Instruction::SDiv:
7744 case Instruction::SRem:
7745 Ops.push_back(
U->getOperand(0));
7746 Ops.push_back(
U->getOperand(1));
7749 case Instruction::GetElementPtr:
7751 "GEP source element type must be sized");
7755 case Instruction::IntToPtr:
7758 case Instruction::PHI:
7789 Ops.push_back(CondICmp->getOperand(0));
7790 Ops.push_back(CondICmp->getOperand(1));
7810 case Instruction::Select: {
7812 auto CanSimplifyToUnknown = [
this,
U]() {
7830 if (CanSimplifyToUnknown())
7837 case Instruction::Call:
7838 case Instruction::Invoke:
7845 switch (
II->getIntrinsicID()) {
7846 case Intrinsic::abs:
7847 Ops.push_back(
II->getArgOperand(0));
7849 case Intrinsic::umax:
7850 case Intrinsic::umin:
7851 case Intrinsic::smax:
7852 case Intrinsic::smin:
7853 case Intrinsic::usub_sat:
7854 case Intrinsic::uadd_sat:
7855 Ops.push_back(
II->getArgOperand(0));
7856 Ops.push_back(
II->getArgOperand(1));
7858 case Intrinsic::start_loop_iterations:
7859 case Intrinsic::annotation:
7860 case Intrinsic::ptr_annotation:
7861 Ops.push_back(
II->getArgOperand(0));
7873const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7882 if (!DT.isReachableFromEntry(
I->getParent()))
7897 switch (BO->Opcode) {
7898 case Instruction::Add: {
7924 if (BO->Opcode == Instruction::Sub)
7932 if (BO->Opcode == Instruction::Sub)
7939 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7940 NewBO->Opcode != Instruction::Sub)) {
7950 case Instruction::Mul: {
7971 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7980 case Instruction::UDiv:
7984 case Instruction::URem:
7988 case Instruction::Sub: {
7991 Flags = getNoWrapFlagsFromUB(BO->
Op);
7996 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
7999 if (HasPtrLHS || HasPtrRHS) {
8004 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
8005 bool BothPtr) ->
const SCEV * {
8008 const SCEV *PtrSCEV =
getSCEV(PtrOp);
8018 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
8019 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
8027 case Instruction::And:
8033 if (CI->isMinusOne())
8035 const APInt &
A = CI->getValue();
8041 unsigned LZ =
A.countl_zero();
8042 unsigned TZ =
A.countr_zero();
8047 APInt EffectiveMask =
8049 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
8052 const SCEV *ShiftedLHS =
nullptr;
8056 unsigned MulZeros = OpC->getAPInt().countr_zero();
8057 unsigned GCD = std::min(MulZeros, TZ);
8062 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8084 case Instruction::Or:
8093 case Instruction::Xor:
8096 if (CI->isMinusOne())
8105 if (LBO->getOpcode() == Instruction::And &&
8106 LCI->getValue() == CI->getValue())
8107 if (
const SCEVZeroExtendExpr *Z =
8110 const SCEV *Z0 =
Z->getOperand();
8117 if (CI->getValue().isMask(Z0TySize))
8123 APInt Trunc = CI->getValue().trunc(Z0TySize);
8132 case Instruction::Shl:
8150 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8159 ConstantInt *
X = ConstantInt::get(
8165 case Instruction::AShr:
8187 const SCEV *AddTruncateExpr =
nullptr;
8188 ConstantInt *ShlAmtCI =
nullptr;
8189 const SCEV *AddConstant =
nullptr;
8191 if (L &&
L->getOpcode() == Instruction::Add) {
8199 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8206 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8214 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8219 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8224 if (AddTruncateExpr && ShlAmtCI) {
8236 const APInt &ShlAmt = ShlAmtCI->
getValue();
8240 const SCEV *CompositeExpr =
8242 if (
L->getOpcode() != Instruction::Shl)
8243 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8252 switch (
U->getOpcode()) {
8253 case Instruction::Trunc:
8256 case Instruction::ZExt:
8259 case Instruction::SExt:
8269 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8270 Type *Ty =
U->getType();
8278 case Instruction::BitCast:
8284 case Instruction::PtrToAddr: {
8291 case Instruction::PtrToInt: {
8297 const SCEV *PtrSCEV =
getSCEV(
U->getOperand(0));
8306 case Instruction::IntToPtr:
8310 case Instruction::SDiv:
8317 case Instruction::SRem:
8324 case Instruction::GetElementPtr:
8327 case Instruction::PHI:
8330 case Instruction::Select:
8331 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8334 case Instruction::Call:
8335 case Instruction::Invoke:
8340 switch (
II->getIntrinsicID()) {
8341 case Intrinsic::abs:
8345 case Intrinsic::umax:
8349 case Intrinsic::umin:
8353 case Intrinsic::smax:
8357 case Intrinsic::smin:
8361 case Intrinsic::usub_sat: {
8362 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8363 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8367 case Intrinsic::uadd_sat: {
8368 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8369 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8373 case Intrinsic::start_loop_iterations:
8374 case Intrinsic::annotation:
8375 case Intrinsic::ptr_annotation:
8379 case Intrinsic::vscale:
8399 auto *ExitCountType = ExitCount->
getType();
8400 assert(ExitCountType->isIntegerTy());
8402 1 + ExitCountType->getScalarSizeInBits());
8415 auto CanAddOneWithoutOverflow = [&]() {
8417 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8428 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8458 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8459 assert(L->isLoopExiting(ExitingBlock) &&
8460 "Exiting block must actually branch out of the loop!");
8469 const auto *MaxExitCount =
8477 L->getExitingBlocks(ExitingBlocks);
8479 std::optional<unsigned> Res;
8480 for (
auto *ExitingBB : ExitingBlocks) {
8484 Res = std::gcd(*Res, Multiple);
8486 return Res.value_or(1);
8490 const SCEV *ExitCount) {
8520 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8521 assert(L->isLoopExiting(ExitingBlock) &&
8522 "Exiting block must actually branch out of the loop!");
8532 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8534 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8536 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8546 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8549 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8552 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8560 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8567 return getBackedgeTakenInfo(L).getExact(L,
this);
8569 return getBackedgeTakenInfo(L).getConstantMax(
this);
8571 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8578 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8583 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8587 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8597 for (
PHINode &PN : Header->phis())
8598 if (Visited.
insert(&PN).second)
8602ScalarEvolution::BackedgeTakenInfo &
8603ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8604 auto &BTI = getBackedgeTakenInfo(L);
8605 if (BTI.hasFullInfo())
8608 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8611 return Pair.first->second;
8613 BackedgeTakenInfo
Result =
8614 computeBackedgeTakenCount(L,
true);
8616 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8619ScalarEvolution::BackedgeTakenInfo &
8620ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8626 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8627 BackedgeTakenCounts.try_emplace(L);
8629 return Pair.first->second;
8634 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8641 if (
Result.hasAnyInfo()) {
8644 auto LoopUsersIt = LoopUsers.find(L);
8645 if (LoopUsersIt != LoopUsers.end())
8647 forgetMemoizedResults(ToForget);
8650 for (PHINode &PN :
L->getHeader()->phis())
8651 ConstantEvolutionLoopExitValue.erase(&PN);
8659 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8668 BackedgeTakenCounts.clear();
8669 PredicatedBackedgeTakenCounts.clear();
8670 BECountUsers.clear();
8671 LoopPropertiesCache.clear();
8672 ConstantEvolutionLoopExitValue.clear();
8673 ValueExprMap.clear();
8674 ValuesAtScopes.clear();
8675 ValuesAtScopesUsers.clear();
8676 LoopDispositions.clear();
8677 BlockDispositions.clear();
8678 UnsignedRanges.clear();
8679 SignedRanges.clear();
8680 ExprValueMap.clear();
8682 ConstantMultipleCache.clear();
8683 PredicatedSCEVRewrites.clear();
8685 FoldCacheUser.clear();
8687void ScalarEvolution::visitAndClearUsers(
8691 while (!Worklist.
empty()) {
8698 if (It != ValueExprMap.
end()) {
8700 eraseValueFromMap(It->first);
8702 ConstantEvolutionLoopExitValue.erase(PN);
8716 while (!LoopWorklist.
empty()) {
8720 forgetBackedgeTakenCounts(CurrL,
false);
8721 forgetBackedgeTakenCounts(CurrL,
true);
8724 PredicatedSCEVRewrites.remove_if(
8725 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8727 auto LoopUsersItr = LoopUsers.find(CurrL);
8728 if (LoopUsersItr != LoopUsers.end())
8733 visitAndClearUsers(Worklist, Visited, ToForget);
8735 LoopPropertiesCache.erase(CurrL);
8738 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8740 forgetMemoizedResults(ToForget);
8757 visitAndClearUsers(Worklist, Visited, ToForget);
8759 forgetMemoizedResults(ToForget);
8767 auto InvalidateValue = [&](
Value *Val) {
8771 struct InvalidationRootCollector {
8775 InvalidationRootCollector(
Loop *L) : L(L) {}
8777 bool follow(
const SCEV *S) {
8783 if (L->contains(AddRec->
getLoop()))
8788 bool isDone()
const {
return false; }
8791 InvalidationRootCollector
C(L);
8793 forgetMemoizedResults(
C.Roots);
8803 return isa<WithOverflowInst>(Inc);
8817 BlockDispositions.clear();
8818 LoopDispositions.clear();
8835 while (!Worklist.
empty()) {
8837 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8838 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8839 if (!LoopDispoRemoved && !BlockDispoRemoved)
8841 auto Users = SCEVUsers.find(Curr);
8842 if (
Users != SCEVUsers.end())
8855const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8859 if (!isComplete() || ExitNotTaken.
empty())
8870 for (
const auto &ENT : ExitNotTaken) {
8871 const SCEV *BECount = ENT.ExactNotTaken;
8874 "We should only have known counts for exiting blocks that dominate "
8877 Ops.push_back(BECount);
8882 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8883 "Predicate should be always true!");
8892const ScalarEvolution::ExitNotTakenInfo *
8893ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8894 const BasicBlock *ExitingBlock,
8895 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8896 for (
const auto &ENT : ExitNotTaken)
8897 if (ENT.ExitingBlock == ExitingBlock) {
8898 if (ENT.hasAlwaysTruePredicate())
8900 else if (Predicates) {
8910const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8912 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8913 if (!getConstantMax())
8916 for (
const auto &ENT : ExitNotTaken)
8917 if (!ENT.hasAlwaysTruePredicate()) {
8925 "No point in having a non-constant max backedge taken count!");
8926 return getConstantMax();
8929const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8931 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8939 for (
const auto &ENT : ExitNotTaken) {
8940 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8943 "We should only have known counts for exiting blocks that "
8949 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8950 "Predicate should be always true!");
8953 if (ExitCounts.
empty())
8962bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8964 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8965 return !ENT.hasAlwaysTruePredicate();
8967 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8983 this->ExactNotTaken = E = ConstantMaxNotTaken;
8984 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8989 "Exact is not allowed to be less precise than Constant Max");
8992 "Exact is not allowed to be less precise than Symbolic Max");
8995 "Symbolic Max is not allowed to be less precise than Constant Max");
8998 "No point in having a non-constant max backedge taken count!");
9000 for (
const auto PredList : PredLists)
9001 for (
const auto *
P : PredList) {
9009 "Backedge count should be int");
9012 "Max backedge count should be int");
9025ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
9027 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
9028 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
9029 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9031 ExitNotTaken.reserve(ExitCounts.
size());
9032 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
9033 std::back_inserter(ExitNotTaken),
9034 [&](
const EdgeExitInfo &EEI) {
9035 BasicBlock *ExitBB = EEI.first;
9036 const ExitLimit &EL = EEI.second;
9037 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
9038 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
9043 "No point in having a non-constant max backedge taken count!");
9047ScalarEvolution::BackedgeTakenInfo
9048ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
9049 bool AllowPredicates) {
9051 L->getExitingBlocks(ExitingBlocks);
9053 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9056 bool CouldComputeBECount =
true;
9058 const SCEV *MustExitMaxBECount =
nullptr;
9059 const SCEV *MayExitMaxBECount =
nullptr;
9060 bool MustExitMaxOrZero =
false;
9061 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9072 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9073 if (ExitIfTrue == CI->
isZero())
9077 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9079 assert((AllowPredicates || EL.Predicates.empty()) &&
9080 "Predicated exit limit when predicates are not allowed!");
9085 ++NumExitCountsComputed;
9089 CouldComputeBECount =
false;
9096 "Exact is known but symbolic isn't?");
9097 ++NumExitCountsNotComputed;
9112 DT.dominates(ExitBB, Latch)) {
9113 if (!MustExitMaxBECount) {
9114 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9115 MustExitMaxOrZero = EL.MaxOrZero;
9118 EL.ConstantMaxNotTaken);
9122 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9125 EL.ConstantMaxNotTaken);
9129 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9133 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9139 for (
const auto &Pair : ExitCounts) {
9141 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9143 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9144 {
L, AllowPredicates});
9146 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9147 MaxBECount, MaxOrZero);
9150ScalarEvolution::ExitLimit
9151ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9152 bool IsOnlyExit,
bool AllowPredicates) {
9153 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9157 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9162 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9163 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9164 "It should have one successor in loop and one exit block!");
9175 if (!
L->contains(SBB)) {
9180 assert(Exit &&
"Exiting block must have at least one exit");
9181 return computeExitLimitFromSingleExitSwitch(
9182 L, SI, Exit, IsOnlyExit);
9189 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9190 bool AllowPredicates) {
9191 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9192 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9193 ControlsOnlyExit, AllowPredicates);
9196std::optional<ScalarEvolution::ExitLimit>
9197ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9198 bool ExitIfTrue,
bool ControlsOnlyExit,
9199 bool AllowPredicates) {
9201 (void)this->ExitIfTrue;
9202 (void)this->AllowPredicates;
9204 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9205 this->AllowPredicates == AllowPredicates &&
9206 "Variance in assumed invariant key components!");
9207 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9208 if (Itr == TripCountMap.end())
9209 return std::nullopt;
9213void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9215 bool ControlsOnlyExit,
9216 bool AllowPredicates,
9218 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9219 this->AllowPredicates == AllowPredicates &&
9220 "Variance in assumed invariant key components!");
9222 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9223 assert(InsertResult.second &&
"Expected successful insertion!");
9228ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9229 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9230 bool ControlsOnlyExit,
bool AllowPredicates) {
9232 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9236 ExitLimit EL = computeExitLimitFromCondImpl(
9237 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9238 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9242ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9243 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9244 bool ControlsOnlyExit,
bool AllowPredicates) {
9246 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9247 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9248 return *LimitFromBinOp;
9254 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9255 if (EL.hasFullInfo() || !AllowPredicates)
9259 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9279 const WithOverflowInst *WO;
9294 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9295 ControlsOnlyExit, AllowPredicates);
9296 if (EL.hasAnyInfo())
9301 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9304std::optional<ScalarEvolution::ExitLimit>
9305ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9309 bool AllowPredicates) {
9318 return std::nullopt;
9322 ExitLimit EL0 = computeExitLimitFromCondCached(
9323 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9324 ExitLimit EL1 = computeExitLimitFromCondCached(
9325 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9330 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9335 if (EitherMayExit) {
9345 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9347 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9350 EL1.ConstantMaxNotTaken);
9352 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9354 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9357 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9361 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9362 BECount = EL0.ExactNotTaken;
9375 SymbolicMaxBECount =
9377 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9381ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9382 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9383 bool AllowPredicates) {
9395 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9397 if (EL.hasAnyInfo())
9400 auto *ExhaustiveCount =
9401 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9404 return ExhaustiveCount;
9406 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9409ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9411 bool ControlsOnlyExit,
bool AllowPredicates) {
9436 ConstantRange CompRange =
9454 InnerLHS = ZExt->getOperand();
9501 if (EL.hasAnyInfo())
9518 if (EL.hasAnyInfo())
return EL;
9550 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9552 if (EL.hasAnyInfo())
9568 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9570 if (EL.hasAnyInfo())
9581ScalarEvolution::ExitLimit
9582ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9584 BasicBlock *ExitingBlock,
9585 bool ControlsOnlyExit) {
9586 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9589 if (
Switch->getDefaultDest() == ExitingBlock)
9593 "Default case must not exit the loop!");
9599 if (EL.hasAnyInfo())
9611 "Evaluation of SCEV at constant didn't fold correctly?");
9615ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9625 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9632 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9634 unsigned &OutShiftAmt) {
9635 using namespace PatternMatch;
9637 ConstantInt *ShiftAmt;
9639 OutOpCode = Instruction::LShr;
9641 OutOpCode = Instruction::AShr;
9643 OutOpCode = Instruction::Shl;
9648 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9663 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9665 unsigned &ShiftAmtOut) {
9666 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9682 if (MatchPositiveShift(
LHS, V, OpC, Amt)) {
9683 PostShiftOpCode = OpC;
9689 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9692 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9698 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9705 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9711 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9723 ConstantInt *StableValue =
nullptr;
9728 case Instruction::AShr: {
9735 if (
Known.isNonNegative())
9736 StableValue = ConstantInt::get(Ty, 0);
9737 else if (
Known.isNegative())
9738 StableValue = ConstantInt::get(Ty, -1,
true);
9744 case Instruction::LShr:
9745 case Instruction::Shl:
9755 "Otherwise cannot be an operand to a branch instruction");
9757 if (
Result->isNullValue()) {
9766 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9768 const SCEV *StartSCEV =
getSCEV(StartValue);
9772 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9773 MaxBTC = std::min(MaxBTC, RangeBTC);
9777 const SCEV *UpperBound =
9794 if (
const Function *
F = CI->getCalledFunction())
9803 if (!L->contains(
I))
return false;
9808 return L->getHeader() ==
I->getParent();
9884 if (!
I)
return nullptr;
9897 std::vector<Constant*>
Operands(
I->getNumOperands());
9899 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9908 if (!
C)
return nullptr;
9930 if (IncomingVal != CurrentVal) {
9933 IncomingVal = CurrentVal;
9945ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9948 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9957 DenseMap<Instruction *, Constant *> CurrentIterVals;
9959 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9965 for (PHINode &
PHI : Header->phis()) {
9967 CurrentIterVals[&
PHI] = StartCST;
9969 if (!CurrentIterVals.
count(PN))
9970 return RetVal =
nullptr;
9976 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9979 unsigned IterationNum = 0;
9981 for (; ; ++IterationNum) {
9982 if (IterationNum == NumIterations)
9983 return RetVal = CurrentIterVals[PN];
9987 DenseMap<Instruction *, Constant *> NextIterVals;
9992 NextIterVals[PN] = NextPHI;
9994 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
10000 for (
const auto &
I : CurrentIterVals) {
10002 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
10007 for (
const auto &
I : PHIsToCompute) {
10008 PHINode *
PHI =
I.first;
10011 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10014 if (NextPHI !=
I.second)
10015 StoppedEvolving =
false;
10020 if (StoppedEvolving)
10021 return RetVal = CurrentIterVals[PN];
10023 CurrentIterVals.swap(NextIterVals);
10027const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
10037 DenseMap<Instruction *, Constant *> CurrentIterVals;
10039 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10042 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
10044 for (PHINode &
PHI : Header->phis()) {
10046 CurrentIterVals[&
PHI] = StartCST;
10048 if (!CurrentIterVals.
count(PN))
10056 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10063 if (CondVal->getValue() ==
uint64_t(ExitWhen)) {
10064 ++NumBruteForceTripCountsComputed;
10069 DenseMap<Instruction *, Constant *> NextIterVals;
10075 for (
const auto &
I : CurrentIterVals) {
10077 if (!
PHI ||
PHI->getParent() != Header)
continue;
10080 for (PHINode *
PHI : PHIsToCompute) {
10082 if (NextPHI)
continue;
10084 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10087 CurrentIterVals.
swap(NextIterVals);
10100 return LS.second ? LS.second : V;
10102 Values.emplace_back(L,
nullptr);
10105 const SCEV *
C = computeSCEVAtScope(V, L);
10106 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10107 if (LS.first == L) {
10110 ValuesAtScopesUsers[
C].push_back({L, V});
10121 switch (V->getSCEVType()) {
10154 assert(!
C->getType()->isPointerTy() &&
10155 "Can only have one pointer, and it must be last");
10180const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10181 SmallVectorImpl<SCEVUse> &NewOps) {
10215const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10216 switch (
V->getSCEVType()) {
10227 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10238 for (++i; i !=
e; ++i)
10282 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10292 for (++i; i !=
e; ++i) {
10297 return getWithOperands(V, NewOps);
10312 const Loop *CurrLoop = this->LI[
I->getParent()];
10323 if (BackedgeTakenCount->
isZero()) {
10324 Value *InitValue =
nullptr;
10325 bool MultipleInitValues =
false;
10331 MultipleInitValues =
true;
10336 if (!MultipleInitValues && InitValue)
10345 unsigned InLoopPred =
10356 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10370 SmallVector<Constant *, 4>
Operands;
10372 bool MadeImprovement =
false;
10387 MadeImprovement |= OrigV != OpV;
10392 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10397 if (!MadeImprovement)
10418const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10420 return stripInjectiveFunctions(ZExt->getOperand());
10422 return stripInjectiveFunctions(SExt->getOperand());
10440 assert(
A != 0 &&
"A must be non-zero.");
10456 if (MinTZ < Mult2 && L->getLoopPredecessor())
10458 if (MinTZ < Mult2) {
10481 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10501static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10507 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10508 << *AddRec <<
'\n');
10511 if (!LC || !MC || !
NC) {
10512 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10513 return std::nullopt;
10519 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10527 N =
N.sext(NewWidth);
10528 M = M.sext(NewWidth);
10529 L = L.sext(NewWidth);
10546 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10547 <<
", multiplied by " <<
T <<
'\n');
10556 std::optional<APInt>
Y) {
10558 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10561 return XW.
slt(YW) ? *
X : *
Y;
10564 return std::nullopt;
10565 return X ? *
X : *
Y;
10582 return std::nullopt;
10583 unsigned W =
X->getBitWidth();
10603static std::optional<APInt>
10609 return std::nullopt;
10612 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10613 std::optional<APInt>
X =
10616 return std::nullopt;
10621 return std::nullopt;
10636static std::optional<APInt>
10640 "Starting value of addrec should be 0");
10641 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10642 <<
Range <<
", addrec " << *AddRec <<
'\n');
10646 "Addrec's initial value should be in range");
10652 return std::nullopt;
10662 auto SolveForBoundary =
10663 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10666 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10667 << Bound <<
" (before multiplying by " << M <<
")\n");
10670 std::optional<APInt> SO;
10673 "signed overflow\n");
10677 "unsigned overflow\n");
10678 std::optional<APInt> UO =
10681 auto LeavesRange = [&] (
const APInt &
X) {
10689 if (
Range.contains(
V1->getValue()))
10698 return {std::nullopt,
false};
10703 if (LeavesRange(*Min))
10704 return { Min,
true };
10705 std::optional<APInt> Max = Min == SO ? UO : SO;
10706 if (LeavesRange(*Max))
10707 return { Max,
true };
10710 return {std::nullopt,
true};
10717 auto SL = SolveForBoundary(
Lower);
10718 auto SU = SolveForBoundary(
Upper);
10721 if (!SL.second || !SU.second)
10722 return std::nullopt;
10765ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10767 bool ControlsOnlyExit,
10768 bool AllowPredicates) {
10779 if (
C->getValue()->isZero())
return C;
10783 const SCEVAddRecExpr *AddRec =
10786 if (!AddRec && AllowPredicates)
10792 if (!AddRec || AddRec->
getLoop() != L)
10803 return ExitLimit(R, R, R,
false, Predicates);
10861 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10887 const SCEV *
Exact =
10895 const SCEV *SymbolicMax =
10897 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10906 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10914 return ExitLimit(
E, M, S,
false, Predicates);
10917ScalarEvolution::ExitLimit
10918ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10926 if (!
C->getValue()->isZero())
10936std::pair<const BasicBlock *, const BasicBlock *>
10937ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10948 if (
const Loop *L = LI.getLoopFor(BB))
10949 return {
L->getLoopPredecessor(),
L->getHeader()};
10951 return {
nullptr, BB};
10960 if (
A ==
B)
return true;
10975 if (ComputesEqualValues(AI, BI))
10983 const SCEV *Op0, *Op1;
11002 auto TrivialCase = [&](
bool TriviallyTrue) {
11011 const SCEV *NewLHS, *NewRHS;
11035 return TrivialCase(
false);
11036 return TrivialCase(
true);
11055 RAdd->hasNoSignedWrap()) ||
11057 RAdd->hasNoUnsignedWrap())) {
11077 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
11078 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
11081 C->getAPInt().isStrictlyPositive()) ||
11105 const APInt &
RA = RC->getAPInt();
11107 bool SimplifiedByConstantRange =
false;
11112 return TrivialCase(
true);
11114 return TrivialCase(
false);
11123 Changed = SimplifiedByConstantRange =
true;
11127 if (!SimplifiedByConstantRange) {
11144 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11150 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11156 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11162 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11174 return TrivialCase(
true);
11176 return TrivialCase(
false);
11281 auto NonRecursive = [OrNegative](
const SCEV *S) {
11283 return C->getAPInt().isPowerOf2() ||
11284 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11290 if (NonRecursive(S))
11300 const SCEV *S, uint64_t M,
11316 APInt C = Cst->getAPInt();
11317 return C.urem(M) == 0;
11325 const SCEV *SmodM =
11340 for (
auto *
A : Assumptions)
11341 if (
A->implies(
P, *
this))
11354std::pair<const SCEV *, const SCEV *>
11357 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11359 return { Start, Start };
11361 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11370 getUsedLoops(LHS, LoopsUsed);
11371 getUsedLoops(RHS, LoopsUsed);
11373 if (LoopsUsed.
empty())
11378 for (
const auto *L1 : LoopsUsed)
11379 for (
const auto *L2 : LoopsUsed)
11380 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11381 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11382 "Domination relationship is not a linear order");
11412 SplitRHS.second) &&
11424 if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
11428 return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11438 return std::nullopt;
11453 if (KnownWithoutContext)
11454 return KnownWithoutContext;
11461 return std::nullopt;
11467 const Loop *L = LHS->getLoop();
11472std::optional<ScalarEvolution::MonotonicPredicateType>
11475 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11481 auto ResultSwapped =
11484 assert(*ResultSwapped != *Result &&
11485 "monotonicity should flip as we flip the predicate");
11492std::optional<ScalarEvolution::MonotonicPredicateType>
11493ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11507 return std::nullopt;
11511 "Should be greater or less!");
11515 if (!LHS->hasNoUnsignedWrap())
11516 return std::nullopt;
11520 "Relational predicate is either signed or unsigned!");
11521 if (!
LHS->hasNoSignedWrap())
11522 return std::nullopt;
11524 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11532 return std::nullopt;
11535std::optional<ScalarEvolution::LoopInvariantPredicate>
11542 return std::nullopt;
11549 if (!ArLHS || ArLHS->
getLoop() != L)
11550 return std::nullopt;
11554 return std::nullopt;
11580 return std::nullopt;
11617 return std::nullopt;
11620std::optional<ScalarEvolution::LoopInvariantPredicate>
11625 Pred, LHS, RHS, L, CtxI, MaxIter))
11635 Pred, LHS, RHS, L, CtxI,
Op))
11637 return std::nullopt;
11640std::optional<ScalarEvolution::LoopInvariantPredicate>
11655 return std::nullopt;
11662 if (!AR || AR->
getLoop() != L)
11663 return std::nullopt;
11668 Pred = Pred.dropSameSign();
11672 return std::nullopt;
11678 if (Step != One && Step != MinusOne)
11679 return std::nullopt;
11685 return std::nullopt;
11691 return std::nullopt;
11699 if (Step == MinusOne)
11703 return std::nullopt;
11709bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11715 auto CheckRange = [&](
bool IsSigned) {
11718 return RangeLHS.
icmp(Pred, RangeRHS);
11727 if (CheckRange(
true) || CheckRange(
false))
11736bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11745 SCEVUse XNonConstOp, XConstOp;
11746 SCEVUse YNonConstOp, YConstOp;
11750 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11753 XFlagsPresent = ExpectedFlags;
11758 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11761 YFlagsPresent = ExpectedFlags;
11764 if (YNonConstOp != XNonConstOp)
11772 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11775 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11835bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11856bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11857 const SCEV *
LHS,
const SCEV *
RHS) {
11862 return any_of(*BB, [&](
const Instruction &
I) {
11863 using namespace llvm::PatternMatch;
11868 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11882 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11887 "This cannot be done on broken IR!");
11890 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11899 if (LoopContinuePredicate &&
11900 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11901 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11906 if (WalkingBEDominatingConds)
11912 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11913 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11920 const SCEV *LoopCounter =
11928 for (
auto &AssumeVH : AC.assumptions()) {
11935 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11939 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11942 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11943 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11944 assert(DTN &&
"should reach the loop header before reaching the root!");
11947 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11965 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
11978 if (!DT.isReachableFromEntry(BB))
11982 "This cannot be done on broken IR!");
11990 const bool ProvingStrictComparison =
11992 bool ProvedNonStrictComparison =
false;
11993 bool ProvedNonEquality =
false;
11996 if (!ProvedNonStrictComparison)
11997 ProvedNonStrictComparison = Fn(NonStrictPredicate);
11998 if (!ProvedNonEquality)
12000 if (ProvedNonStrictComparison && ProvedNonEquality)
12005 if (ProvingStrictComparison) {
12007 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
12009 if (SplitAndProve(ProofFn))
12014 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
12016 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
12018 if (ProvingStrictComparison) {
12020 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
12022 if (SplitAndProve(ProofFn))
12031 const Loop *ContainingLoop = LI.getLoopFor(BB);
12033 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
12037 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
12038 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
12041 if (!BlockEntryPredicate)
12050 for (
auto &AssumeVH : AC.assumptions()) {
12054 if (!DT.dominates(CI, BB))
12057 if (ProveViaCond(CI->getArgOperand(0),
false))
12063 F.getParent(), Intrinsic::experimental_guard);
12065 for (
const auto *GU : GuardDecl->users())
12067 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12068 if (ProveViaCond(Guard->getArgOperand(0),
false))
12083 "LHS is not available at Loop Entry");
12085 "RHS is not available at Loop Entry");
12087 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12098 if (FoundCondValue ==
12102 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12106 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12109 const Value *Op0, *Op1;
12112 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12116 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12117 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12121 if (!ICI)
return false;
12125 CmpPredicate FoundPred;
12134 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12137bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12138 const SCEV *
RHS, CmpPredicate FoundPred,
12139 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12140 const Instruction *CtxI) {
12150 auto *WideType = FoundLHS->
getType();
12162 TruncFoundLHS, TruncFoundRHS, CtxI))
12188 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12192bool ScalarEvolution::isImpliedCondBalancedTypes(
12197 "Types should be balanced!");
12204 if (FoundLHS == FoundRHS)
12208 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12220 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12237 LHS, FoundLHS, FoundRHS, CtxI);
12239 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12261 assert(P1 != P2 &&
"Handled earlier!");
12265 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12269 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12272 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12273 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12274 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12279 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12290 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12291 CanonicalRHS, CanonicalFoundLHS,
12292 CanonicalFoundRHS);
12297 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12298 CanonicalRHS, CanonicalFoundLHS,
12299 CanonicalFoundRHS);
12306 const SCEVConstant *
C =
nullptr;
12307 const SCEV *
V =
nullptr;
12325 if (Min ==
C->getAPInt()) {
12330 APInt SharperMin = Min + 1;
12333 case ICmpInst::ICMP_SGE:
12334 case ICmpInst::ICMP_UGE:
12337 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12342 case ICmpInst::ICMP_SGT:
12343 case ICmpInst::ICMP_UGT:
12353 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12358 case ICmpInst::ICMP_SLE:
12359 case ICmpInst::ICMP_ULE:
12360 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12361 LHS, V, getConstant(SharperMin), CtxI))
12365 case ICmpInst::ICMP_SLT:
12366 case ICmpInst::ICMP_ULT:
12367 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12368 LHS, V, getConstant(Min), CtxI))
12382 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12386 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12389 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12405std::optional<APInt>
12412 APInt DiffMul(BW, 1);
12415 for (
unsigned I = 0;
I < 8; ++
I) {
12424 if (LAR->getLoop() != MAR->getLoop())
12425 return std::nullopt;
12429 if (!LAR->isAffine() || !MAR->isAffine())
12430 return std::nullopt;
12432 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12433 return std::nullopt;
12435 Less = LAR->getStart();
12436 More = MAR->getStart();
12441 auto MatchConstMul =
12442 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12447 return std::nullopt;
12449 if (
auto MatchedMore = MatchConstMul(More)) {
12450 if (
auto MatchedLess = MatchConstMul(
Less)) {
12451 if (MatchedMore->second == MatchedLess->second) {
12452 More = MatchedMore->first;
12453 Less = MatchedLess->first;
12454 DiffMul *= MatchedMore->second;
12465 Diff +=
C->getAPInt() * DiffMul;
12468 Diff -=
C->getAPInt() * DiffMul;
12471 Multiplicity[S] +=
Mul;
12473 auto Decompose = [&](
const SCEV *S,
int Mul) {
12480 Decompose(More, 1);
12481 Decompose(
Less, -1);
12485 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12486 for (
const auto &[S,
Mul] : Multiplicity) {
12491 return std::nullopt;
12493 }
else if (
Mul == -1) {
12495 return std::nullopt;
12498 return std::nullopt;
12502 if (NewMore == More || NewLess ==
Less)
12503 return std::nullopt;
12509 if (!More && !
Less)
12513 if (!More || !
Less)
12514 return std::nullopt;
12518 return std::nullopt;
12521bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12543 const auto *Latch = L->getLoopLatch();
12546 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12555 const auto *Latch = L->getLoopLatch();
12558 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12568bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12571 const SCEV *FoundLHS,
12572 const SCEV *FoundRHS) {
12581 if (!AddRecFoundLHS)
12588 const Loop *
L = AddRecFoundLHS->getLoop();
12589 if (L != AddRecLHS->getLoop())
12628 if (!RDiff || *LDiff != *RDiff)
12631 if (LDiff->isMinValue())
12634 APInt FoundRHSLimit;
12637 FoundRHSLimit = -(*RDiff);
12649bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12650 const SCEV *
RHS,
const SCEV *FoundLHS,
12651 const SCEV *FoundRHS,
unsigned Depth) {
12652 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12656 bool Erased = PendingMerges.erase(LPhi);
12657 assert(Erased &&
"Failed to erase LPhi!");
12661 bool Erased = PendingMerges.erase(RPhi);
12662 assert(Erased &&
"Failed to erase RPhi!");
12670 if (!PendingMerges.insert(Phi).second)
12684 if (!PendingMerges.insert(Phi).second)
12690 if (!LPhi && !RPhi)
12701 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12705 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12706 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12707 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12708 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12711 if (RPhi && RPhi->getParent() == LBB) {
12718 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12719 if (!ProvedEasily(L, R))
12730 auto *RLoop = RAR->
getLoop();
12731 auto *Predecessor = RLoop->getLoopPredecessor();
12732 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12734 if (!ProvedEasily(L1, RAR->
getStart()))
12736 auto *Latch = RLoop->getLoopLatch();
12737 assert(Latch &&
"Loop with AddRec with no latch?");
12758 if (
auto *
Loop = LI.getLoopFor(LBB))
12761 if (!ProvedEasily(L,
RHS))
12768bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12771 const SCEV *FoundLHS,
12772 const SCEV *FoundRHS) {
12775 if (
RHS == FoundRHS) {
12780 if (
LHS != FoundLHS)
12787 Value *Shiftee, *ShiftValue;
12789 using namespace PatternMatch;
12790 if (
match(SUFoundRHS->getValue(),
12792 auto *ShifteeS =
getSCEV(Shiftee);
12810bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12811 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12812 const SCEV *FoundRHS) {
12844 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12852 return Diff == FoundDiff;
12855bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12857 const SCEV *FoundLHS,
12858 const SCEV *FoundRHS,
12859 const Instruction *CtxI) {
12860 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12862 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12864 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12865 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12867 isImpliedCondOperandsViaMatchingDiff(Pred,
LHS,
RHS, FoundLHS,
12869 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12873template <
typename MinMaxExprType>
12875 const SCEV *Candidate) {
12880 return is_contained(MinMaxExpr->operands(), Candidate);
12893 const SCEV *LStart, *RStart, *Step;
12966bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12968 const SCEV *FoundLHS,
12969 const SCEV *FoundRHS,
12973 "LHS and RHS have different sizes?");
12976 "FoundLHS and FoundRHS have different sizes?");
13010 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
13012 return Ext->getOperand();
13019 auto *OrigLHS =
LHS;
13020 auto *OrigFoundLHS = FoundLHS;
13021 LHS = GetOpFromSExt(
LHS);
13022 FoundLHS = GetOpFromSExt(FoundLHS);
13025 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
13028 FoundRHS,
Depth + 1);
13041 if (!LHSAddExpr->hasNoSignedWrap())
13044 SCEVUse LL = LHSAddExpr->getOperand(0);
13045 SCEVUse LR = LHSAddExpr->getOperand(1);
13049 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
13050 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
13055 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
13061 using namespace llvm::PatternMatch;
13080 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13088 auto *DTy = Denominator->getType();
13089 auto *FRHSTy = FoundRHS->
getType();
13090 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13109 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13120 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13122 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13130 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13163bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13167 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13170 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13173bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13176 const SCEV *FoundLHS,
13177 const SCEV *FoundRHS) {
13213 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13219bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13220 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13221 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13235 ConstantRange FoundLHSRange =
13239 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13246 return LHSRange.
icmp(Pred, ConstRHS);
13249bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13262 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13270 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13273bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
13285 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
13293 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
13305const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
13306 const SCEV *Stride,
13337 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13348 :
APIntOps::umax(MaxEnd, MinStart);
13355ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13356 const Loop *L,
bool IsSigned,
13357 bool ControlsOnlyExit,
bool AllowPredicates) {
13361 bool PredicatedIV =
false;
13366 auto canProveNUW = [&]() {
13369 if (!ControlsOnlyExit)
13390 Limit = Limit.
zext(OuterBitWidth);
13402 Type *Ty = ZExt->getType();
13413 if (!
IV && AllowPredicates) {
13418 PredicatedIV =
true;
13422 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13436 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13439 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13444 if (!PositiveStride) {
13496 auto wouldZeroStrideBeUB = [&]() {
13508 if (!wouldZeroStrideBeUB()) {
13512 }
else if (!NoWrap) {
13515 if (canIVOverflowOnLT(
RHS, Stride, IsSigned))
13528 const SCEV *
Start =
IV->getStart();
13534 const SCEV *OrigStart =
Start;
13535 const SCEV *OrigRHS =
RHS;
13536 if (
Start->getType()->isPointerTy()) {
13547 const SCEV *End =
nullptr, *BECount =
nullptr,
13548 *BECountIfBackedgeTaken =
nullptr;
13551 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13552 any(RHSAddRec->getNoWrapFlags())) {
13565 const SCEV *RHSStart = RHSAddRec->getStart();
13566 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13578 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13587 BECountIfBackedgeTaken =
13592 if (BECount ==
nullptr) {
13597 const SCEV *MaxBECount = computeMaxBECountForLT(
13600 MaxBECount,
false , Predicates);
13607 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13634 const SCEV *Numerator =
13640 auto canProveRHSGreaterThanEqualStart = [&]() {
13659 auto *StartMinusOne =
13666 if (canProveRHSGreaterThanEqualStart()) {
13681 BECountIfBackedgeTaken =
13697 bool MayAddOverflow = [&] {
13743 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13757 if (!MayAddOverflow) {
13769 const SCEV *ConstantMaxBECount;
13770 bool MaxOrZero =
false;
13772 ConstantMaxBECount = BECount;
13773 }
else if (BECountIfBackedgeTaken &&
13778 ConstantMaxBECount = BECountIfBackedgeTaken;
13781 ConstantMaxBECount = computeMaxBECountForLT(
13789 const SCEV *SymbolicMaxBECount =
13791 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13795ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13796 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13797 bool ControlsOnlyExit,
bool AllowPredicates) {
13804 if (!
IV && AllowPredicates)
13811 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13815 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13828 bool MayAddOverflow =
false;
13829 const SCEV *
Start =
IV->getStart();
13830 const SCEV *End =
RHS;
13831 if (!Stride->
isOne() && canIVOverflowOnGT(
RHS, Stride, IsSigned)) {
13834 MayAddOverflow =
true;
13847 if (
Start->getType()->isPointerTy()) {
13859 const SCEV *BECount;
13860 if (MayAddOverflow) {
13891 const SCEV *ConstantMaxBECount =
13898 ConstantMaxBECount = BECount;
13899 const SCEV *SymbolicMaxBECount =
13902 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13908 if (
Range.isFullSet())
13913 if (!SC->getValue()->isZero()) {
13919 return ShiftedAddRec->getNumIterationsInRange(
13920 Range.subtract(SC->getAPInt()), SE);
13951 APInt ExitVal = (End +
A).udiv(
A);
13964 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13965 "Linear scev computation is off in a bad way!");
13996 assert(!
Last->isZero() &&
"Recurrency with zero step?");
14022 Ty =
Store->getValueOperand()->getType();
14023 PtrTy =
Store->getPointerOperandType();
14025 Ty =
Load->getType();
14026 PtrTy =
Load->getPointerOperandType();
14040 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14042 SE->ConstantEvolutionLoopExitValue.erase(PN);
14043 SE->eraseValueFromMap(getValPtr());
14047void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
14048 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14058 : CallbackVH(
V), SE(se) {}
14067 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
14069 LoopDispositions(64), BlockDispositions(64) {
14081 F.getParent(), Intrinsic::experimental_guard);
14082 HasGuards = GuardDecl && !GuardDecl->use_empty();
14086 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
14087 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14088 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14089 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14090 PendingMerges(
std::
move(Arg.PendingMerges)),
14091 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14092 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14093 PredicatedBackedgeTakenCounts(
14094 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14095 BECountUsers(
std::
move(Arg.BECountUsers)),
14096 ConstantEvolutionLoopExitValue(
14097 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14098 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14099 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14100 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14101 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14102 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14103 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14104 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14105 SignedRanges(
std::
move(Arg.SignedRanges)),
14106 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14107 UniquePreds(
std::
move(Arg.UniquePreds)),
14108 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14109 ConstantSCEVs(
std::
move(Arg.ConstantSCEVs)),
14110 LoopUsers(
std::
move(Arg.LoopUsers)),
14111 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14112 FirstUnknown(Arg.FirstUnknown) {
14113 Arg.FirstUnknown =
nullptr;
14122 Tmp->~SCEVUnknown();
14124 FirstUnknown =
nullptr;
14126 ExprValueMap.clear();
14127 ValueExprMap.clear();
14129 BackedgeTakenCounts.clear();
14130 PredicatedBackedgeTakenCounts.clear();
14132 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14133 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14134 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14135 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14157 L->getHeader()->printAsOperand(OS,
false);
14161 L->getExitingBlocks(ExitingBlocks);
14162 if (ExitingBlocks.
size() != 1)
14163 OS <<
"<multiple exits> ";
14167 OS <<
"backedge-taken count is ";
14170 OS <<
"Unpredictable backedge-taken count.";
14173 if (ExitingBlocks.
size() > 1)
14174 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14175 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14183 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14186 OS <<
"\n Predicates:\n";
14187 for (
const auto *
P : Predicates)
14195 L->getHeader()->printAsOperand(OS,
false);
14200 OS <<
"constant max backedge-taken count is ";
14203 OS <<
", actual taken count either this or zero.";
14205 OS <<
"Unpredictable constant max backedge-taken count. ";
14210 L->getHeader()->printAsOperand(OS,
false);
14215 OS <<
"symbolic max backedge-taken count is ";
14218 OS <<
", actual taken count either this or zero.";
14220 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14224 if (ExitingBlocks.
size() > 1)
14225 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14226 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14236 OS <<
"\n predicated symbolic max exit count for "
14237 << ExitingBlock->
getName() <<
": ";
14239 OS <<
"\n Predicates:\n";
14240 for (
const auto *
P : Predicates)
14251 L->getHeader()->printAsOperand(OS,
false);
14254 OS <<
"Predicated backedge-taken count is ";
14257 OS <<
"Unpredictable predicated backedge-taken count.";
14259 OS <<
" Predicates:\n";
14260 for (
const auto *
P : Preds)
14265 auto *PredConstantMax =
14267 if (PredConstantMax != ConstantBTC) {
14269 L->getHeader()->printAsOperand(OS,
false);
14272 OS <<
"Predicated constant max backedge-taken count is ";
14275 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14277 OS <<
" Predicates:\n";
14278 for (
const auto *
P : Preds)
14283 auto *PredSymbolicMax =
14285 if (SymbolicBTC != PredSymbolicMax) {
14287 L->getHeader()->printAsOperand(OS,
false);
14290 OS <<
"Predicated symbolic max backedge-taken count is ";
14293 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14295 OS <<
" Predicates:\n";
14296 for (
const auto *
P : Preds)
14302 L->getHeader()->printAsOperand(OS,
false);
14329 OS <<
"Computable";
14339 OS <<
"DoesNotDominate";
14345 OS <<
"ProperlyDominates";
14362 OS <<
"Classifying expressions for: ";
14363 F.printAsOperand(OS,
false);
14378 const Loop *L = LI.getLoopFor(
I.getParent());
14393 OS <<
"\t\t" "Exits: ";
14396 OS <<
"<<Unknown>>";
14402 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14404 Iter->getHeader()->printAsOperand(OS,
false);
14412 InnerL->getHeader()->printAsOperand(OS,
false);
14423 OS <<
"Determining loop execution counts for: ";
14424 F.printAsOperand(OS,
false);
14432 auto &
Values = LoopDispositions[S];
14433 for (
auto &V :
Values) {
14434 if (V.getPointer() == L)
14439 auto &Values2 = LoopDispositions[S];
14441 if (V.getPointer() == L) {
14450ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14468 if (L->contains(AR->
getLoop()) &&
14470 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14475 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14476 " dominate the contained loop's header?");
14503 bool HasVarying =
false;
14504 bool HasUniform =
false;
14546 auto &
Values = BlockDispositions[S];
14547 for (
auto &V :
Values) {
14548 if (V.getPointer() == BB)
14553 auto &Values2 = BlockDispositions[S];
14555 if (V.getPointer() == BB) {
14564ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14593 bool Proper =
true;
14604 if (Instruction *
I =
14606 if (
I->getParent() == BB)
14608 if (DT.properlyDominates(
I->getParent(), BB))
14631void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14634 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14635 auto It = BECounts.find(L);
14636 if (It != BECounts.end()) {
14637 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14638 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14640 auto UserIt = BECountUsers.find(S);
14641 assert(UserIt != BECountUsers.end());
14646 BECounts.erase(It);
14654 while (!Worklist.
empty()) {
14656 auto Users = SCEVUsers.find(Curr);
14657 if (
Users != SCEVUsers.end())
14658 for (
const auto *User :
Users->second)
14659 if (ToForget.
insert(User).second)
14663 for (
const auto *S : ToForget)
14664 forgetMemoizedResultsImpl(S);
14666 PredicatedSCEVRewrites.remove_if(
14667 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14670void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14671 LoopDispositions.erase(S);
14672 BlockDispositions.erase(S);
14673 UnsignedRanges.erase(S);
14674 SignedRanges.erase(S);
14675 HasRecMap.erase(S);
14676 ConstantMultipleCache.erase(S);
14679 UnsignedWrapViaInductionTried.erase(AR);
14680 SignedWrapViaInductionTried.erase(AR);
14683 auto ExprIt = ExprValueMap.find(S);
14684 if (ExprIt != ExprValueMap.end()) {
14685 for (
Value *V : ExprIt->second) {
14686 auto ValueIt = ValueExprMap.find_as(V);
14687 if (ValueIt != ValueExprMap.end())
14688 ValueExprMap.erase(ValueIt);
14690 ExprValueMap.erase(ExprIt);
14693 auto ScopeIt = ValuesAtScopes.find(S);
14694 if (ScopeIt != ValuesAtScopes.end()) {
14695 for (
const auto &Pair : ScopeIt->second)
14698 std::make_pair(Pair.first, S));
14699 ValuesAtScopes.erase(ScopeIt);
14702 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14703 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14704 for (
const auto &Pair : ScopeUserIt->second)
14705 llvm::erase(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
14706 ValuesAtScopesUsers.erase(ScopeUserIt);
14709 auto BEUsersIt = BECountUsers.find(S);
14710 if (BEUsersIt != BECountUsers.end()) {
14712 auto Copy = BEUsersIt->second;
14713 for (
const auto &Pair : Copy)
14714 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14715 BECountUsers.erase(BEUsersIt);
14718 auto FoldUser = FoldCacheUser.find(S);
14719 if (FoldUser != FoldCacheUser.end())
14720 for (
auto &KV : FoldUser->second)
14721 FoldCache.erase(KV);
14722 FoldCacheUser.erase(S);
14726ScalarEvolution::getUsedLoops(
const SCEV *S,
14728 struct FindUsedLoops {
14729 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14730 : LoopsUsed(LoopsUsed) {}
14731 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14732 bool follow(
const SCEV *S) {
14738 bool isDone()
const {
return false; }
14741 FindUsedLoops
F(LoopsUsed);
14742 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14745void ScalarEvolution::getReachableBlocks(
14748 Worklist.
push_back(&F.getEntryBlock());
14749 while (!Worklist.
empty()) {
14751 if (!Reachable.
insert(BB).second)
14759 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14766 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14770 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14805 SCEVMapper SCM(SE2);
14807 SE2.getReachableBlocks(ReachableBlocks, F);
14809 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14827 while (!LoopStack.
empty()) {
14833 if (!ReachableBlocks.
contains(L->getHeader()))
14838 auto It = BackedgeTakenCounts.find(L);
14839 if (It == BackedgeTakenCounts.end())
14843 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14863 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14864 if (Delta && !Delta->
isZero()) {
14865 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14866 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14867 dbgs() <<
"New: " << *NewBECount <<
"\n";
14868 dbgs() <<
"Delta: " << *Delta <<
"\n";
14876 while (!Worklist.
empty()) {
14878 if (ValidLoops.
insert(L).second)
14879 Worklist.
append(L->begin(), L->end());
14881 for (
const auto &KV : ValueExprMap) {
14886 "AddRec references invalid loop");
14891 auto It = ExprValueMap.find(KV.second);
14892 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14893 dbgs() <<
"Value " << *KV.first
14894 <<
" is in ValueExprMap but not in ExprValueMap\n";
14899 if (!ReachableBlocks.
contains(
I->getParent()))
14901 const SCEV *OldSCEV = SCM.visit(KV.second);
14903 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14904 if (Delta && !Delta->
isZero()) {
14905 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14906 <<
"Old: " << *OldSCEV <<
"\n"
14907 <<
"New: " << *NewSCEV <<
"\n"
14908 <<
"Delta: " << *Delta <<
"\n";
14914 for (
const auto &KV : ExprValueMap) {
14915 for (
Value *V : KV.second) {
14916 const SCEV *S = ValueExprMap.lookup(V);
14918 dbgs() <<
"Value " << *V
14919 <<
" is in ExprValueMap but not in ValueExprMap\n";
14922 if (S != KV.first) {
14923 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14924 << *KV.first <<
"\n";
14931 for (
const auto &S : UniqueSCEVs) {
14936 auto It = SCEVUsers.find(
Op);
14937 if (It != SCEVUsers.end() && It->second.count(&S))
14939 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14940 <<
" is not being tracked!\n";
14946 for (
const auto &ValueAndVec : ValuesAtScopes) {
14948 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14949 const Loop *L = LoopAndValueAtScope.first;
14950 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
14952 auto It = ValuesAtScopesUsers.find(ValueAtScope);
14953 if (It != ValuesAtScopesUsers.end() &&
14956 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14957 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14963 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14964 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14965 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14966 const Loop *L = LoopAndValue.first;
14967 const SCEV *
Value = LoopAndValue.second;
14969 auto It = ValuesAtScopes.find(
Value);
14970 if (It != ValuesAtScopes.end() &&
14971 is_contained(It->second, std::make_pair(L, ValueAtScope)))
14973 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14974 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14980 auto VerifyBECountUsers = [&](
bool Predicated) {
14982 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14983 for (
const auto &LoopAndBEInfo : BECounts) {
14984 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14985 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14987 auto UserIt = BECountUsers.find(S);
14988 if (UserIt != BECountUsers.end() &&
14989 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14991 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14992 <<
" missing from BECountUsers\n";
14999 VerifyBECountUsers(
false);
15000 VerifyBECountUsers(
true);
15003 for (
auto &[S,
Values] : LoopDispositions) {
15004 for (
auto [
Loop, CachedDisposition] :
Values) {
15006 if (CachedDisposition != RecomputedDisposition) {
15007 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
15008 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
15009 << RecomputedDisposition <<
"\n";
15016 for (
auto &[S,
Values] : BlockDispositions) {
15017 for (
auto [BB, CachedDisposition] :
Values) {
15019 if (CachedDisposition != RecomputedDisposition) {
15020 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
15021 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
15022 <<
", actual " << RecomputedDisposition <<
"\n";
15029 for (
auto [
FoldID, Expr] : FoldCache) {
15030 auto I = FoldCacheUser.find(Expr);
15031 if (
I == FoldCacheUser.end()) {
15032 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
15037 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
15041 for (
auto [Expr, IDs] : FoldCacheUser) {
15042 for (
auto &
FoldID : IDs) {
15045 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
15050 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
15051 <<
" != " << *Expr <<
"!\n";
15062 for (
auto [S, Multiple] : ConstantMultipleCache) {
15064 if ((Multiple != 0 && RecomputedMultiple != 0 &&
15065 Multiple.
urem(RecomputedMultiple) != 0 &&
15066 RecomputedMultiple.
urem(Multiple) != 0)) {
15067 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
15068 << *S <<
" : Computed " << RecomputedMultiple
15069 <<
" but cache contains " << Multiple <<
"!\n";
15077 FunctionAnalysisManager::Invalidator &Inv) {
15109 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15110 <<
F.getName() <<
"':\n";
15116 "Scalar Evolution Analysis",
false,
true)
15165 const SCEV *LHS,
const SCEV *RHS) {
15167 assert(LHS->getType() == RHS->getType() &&
15168 "Type mismatch between LHS and RHS");
15171 ID.AddInteger(Pred);
15172 ID.AddPointer(LHS);
15173 ID.AddPointer(RHS);
15174 void *IP =
nullptr;
15175 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(ID, IP))
15179 UniquePreds.InsertNode(Eq, IP);
15190 ID.AddInteger(AddedFlags);
15191 void *IP =
nullptr;
15192 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(ID, IP))
15194 auto *OF =
new (SCEVAllocator)
15196 UniquePreds.InsertNode(OF, IP);
15216 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15217 return Rewriter.visit(S);
15223 for (
const auto *Pred : U->getPredicates())
15225 if (IPred->getLHS() == Expr &&
15227 return IPred->getRHS();
15229 if (IPred->getLHS() == Expr &&
15230 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15231 return IPred->getRHS();
15234 return convertToAddRecWithPreds(Expr);
15237 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15253 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15270 explicit SCEVPredicateRewriter(
15271 const Loop *L, ScalarEvolution &SE,
15272 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15273 const SCEVPredicate *Pred)
15274 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15276 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15279 return Pred && Pred->
implies(
P, SE);
15285 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15288 return addOverflowAssumption(
A);
15297 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15301 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15303 if (!PredicatedRewrite)
15305 for (
const auto *
P : PredicatedRewrite->second){
15308 if (L != WP->getExpr()->getLoop())
15311 if (!addOverflowAssumption(
P))
15314 return PredicatedRewrite->first;
15317 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15318 const SCEVPredicate *Pred;
15327 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15334 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15354 if (!Step->
isOne())
15379 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15380 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15393 return Op->LHS == LHS &&
Op->RHS == RHS;
15400 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15402 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15427 const SCEV *Start = AR->getStart();
15428 const SCEV *OpStart =
Op->AR->getStart();
15433 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15442 const SCEV *Step = AR->getStepRecurrence(SE);
15443 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15496 if (Step->getValue()->getValue().isNonNegative())
15500 return ImpliedFlags;
15507 for (
const auto *
P : Preds)
15520 return this->implies(I, SE);
15532 const Loop *L = NWrap->getExpr()->getLoop();
15539 return RewrittenAR &&
15545 for (
const auto *Pred : Preds)
15546 Pred->print(OS,
Depth);
15551 for (
const auto *Pred : Set->Preds)
15559 bool CheckImplies = Preds.
size() < 16;
15562 if (CheckImplies &&
implies(
N, SE))
15568 for (
auto *
P : Preds) {
15569 if (CheckImplies &&
N->implies(
P, SE))
15573 Preds = std::move(PrunedPreds);
15574 Preds.push_back(
N);
15581 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15586 for (
const auto *
Op :
Ops)
15591 SCEVUsers[
Op].insert(
User);
15600 SCEVUsers[
Op].insert(
User);
15604 const SCEV *Expr = SE.getSCEV(V);
15609 RewriteEntry &Entry = RewriteMap[Expr];
15612 if (Entry.second && Generation == Entry.first)
15613 return Entry.second;
15618 Expr = Entry.second;
15620 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15621 Entry = {Generation, NewSCEV};
15627 if (!BackedgeCount) {
15629 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15630 for (
const auto *
P : Preds)
15633 return BackedgeCount;
15637 if (!SymbolicMaxBackedgeCount) {
15639 SymbolicMaxBackedgeCount =
15640 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15641 for (
const auto *
P : Preds)
15644 return SymbolicMaxBackedgeCount;
15648 if (!SmallConstantMaxTripCount) {
15650 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15651 for (
const auto *
P : Preds)
15654 return *SmallConstantMaxTripCount;
15658 if (Preds->implies(&Pred, SE))
15663 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15664 updateGeneration();
15677void PredicatedScalarEvolution::updateGeneration() {
15679 if (++Generation == 0) {
15680 for (
auto &
II : RewriteMap) {
15681 const SCEV *Rewritten =
II.second.second;
15703 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15709 ExtraPreds->
append(NewPreds);
15715 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15721 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15724 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15728 for (
auto *BB : L.getBlocks())
15729 for (
auto &
I : *BB) {
15730 if (!SE.isSCEVable(
I.getType()))
15733 auto *Expr = SE.getSCEV(&
I);
15734 auto II = RewriteMap.find(Expr);
15736 if (
II == RewriteMap.end())
15740 if (
II->second.second == Expr)
15745 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15753 LoopGuards Guards(SE);
15761void ScalarEvolution::LoopGuards::collectFromPHI(
15769 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15770 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15784 auto &RewriteMap =
G->second.RewriteMap;
15785 if (RewriteMap.empty())
15787 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15788 if (S == RewriteMap.end())
15794 return {C0, SM->getSCEVType()};
15797 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15798 MinMaxPattern
P2) -> MinMaxPattern {
15799 auto [C1,
T1] =
P1;
15800 auto [C2, T2] =
P2;
15801 if (!C1 || !C2 ||
T1 != T2)
15805 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15807 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15809 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15811 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15816 auto P = GetMinMaxConst(0);
15817 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15820 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15823 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15826 Guards.RewriteMap.insert({
LHS,
RHS});
15834 const APInt &DivisorVal,
15836 const APInt *ExprVal;
15849 const APInt &DivisorVal,
15851 const APInt *ExprVal;
15859 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15873 const SCEV *URemRHS =
nullptr;
15877 const SCEV *Multiple =
15879 DivInfo[URemLHS] = Multiple;
15881 Multiples[URemLHS] =
C->getAPInt();
15901 auto IsMinMaxSCEVWithNonNegativeConstant =
15905 if (
MinMax->getNumOperands() != 2)
15908 if (
C->getAPInt().isNegative())
15910 SCTy =
MinMax->getSCEVType();
15919 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15921 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15926 auto *DivisibleExpr =
15934void ScalarEvolution::LoopGuards::collectFromBlock(
15936 const BasicBlock *
Block,
const BasicBlock *Pred,
15944 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15955 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15957 if (From == FromRewritten)
15959 RewriteMap[From] = To;
15965 auto GetMaybeRewritten = [&](
const SCEV *S) {
15966 return RewriteMap.lookup_or(S, S);
15973 const SCEV *MatchLHS,
15974 const SCEV *MatchRHS) {
15975 const SCEVConstant *C1;
15978 if (!
match(MatchLHS,
15990 const SCEV *RewrittenLHS = GetMaybeRewritten(LHSUnknown);
15991 ExactRegion = ExactRegion.intersectWith(SE.
getUnsignedRange(RewrittenLHS),
15996 if (ExactRegion.isEmptySet() || ExactRegion.isWrappedSet() ||
15997 ExactRegion.isFullSet())
16000 const SCEV *RegionMin = SE.
getConstant(ExactRegion.getUnsignedMin());
16001 const SCEV *RegionMax = SE.
getConstant(ExactRegion.getUnsignedMax());
16002 const SCEV *ClampedLHS =
16004 AddRewrite(LHSUnknown, RewrittenLHS, ClampedLHS);
16007 if (MatchRangeCheckIdiom(Predicate,
LHS,
RHS))
16020 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
16022 const APInt &DividesBy =
16037 switch (Predicate) {
16066 SmallPtrSet<const SCEV *, 16> Visited;
16068 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
16072 while (!Worklist.
empty()) {
16076 if (!Visited.
insert(From).second)
16078 const SCEV *FromRewritten = GetMaybeRewritten(From);
16079 const SCEV *To =
nullptr;
16081 switch (Predicate) {
16086 EnqueueOperands(
UMax);
16092 EnqueueOperands(
SMax);
16098 EnqueueOperands(
UMin);
16104 EnqueueOperands(
SMin);
16112 const SCEV *OneAlignedUp =
16114 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16126 const SCEVConstant *
C;
16135 Guards.NotEqual.insert({
LHS,
RHS});
16144 AddRewrite(From, FromRewritten, To);
16161 SE.F.
getParent(), Intrinsic::experimental_guard);
16163 for (
const auto *GU : GuardDecl->users())
16165 if (Guard->getFunction() ==
Block->getParent() &&
16174 unsigned NumCollectedConditions = 0;
16176 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16178 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16180 const CondBrInst *LoopEntryPredicate =
16182 if (!LoopEntryPredicate)
16187 NumCollectedConditions++;
16191 if (
Depth > 0 && NumCollectedConditions == 2)
16199 if (Pair.second->hasNPredecessorsOrMore(2) &&
16201 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16202 for (
auto &Phi : Pair.second->phis())
16213 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16214 SmallVector<Value *, 8> Worklist;
16215 SmallPtrSet<Value *, 8> Visited;
16217 while (!Worklist.
empty()) {
16224 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16248 DenseMap<const SCEV *, APInt> Multiples;
16250 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16257 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16258 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16262 for (
const auto &[K, Divisor] : Multiples) {
16263 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16264 Guards.RewriteMap[
K] =
16266 Guards.
rewrite(K), Divisor, SE),
16275 Guards.PreserveNUW =
true;
16276 Guards.PreserveNSW =
true;
16277 for (
const SCEV *Expr : ExprsToRewrite) {
16278 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16279 Guards.PreserveNUW &=
16281 Guards.PreserveNSW &=
16288 if (ExprsToRewrite.size() > 1) {
16289 for (
const SCEV *Expr : ExprsToRewrite) {
16290 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16291 Guards.RewriteMap.erase(Expr);
16292 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16301 class SCEVLoopGuardRewriter
16312 NotEqual(Guards.NotEqual) {
16313 if (Guards.PreserveNUW)
16315 if (Guards.PreserveNSW)
16322 return Map.lookup_or(Expr, Expr);
16326 if (
const SCEV *S = Map.lookup(Expr))
16333 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16334 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16335 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16337 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16338 if (
const SCEV *S = Map.lookup(NarrowExt))
16339 return SE.getZeroExtendExpr(S, Ty);
16340 Bitwidth = Bitwidth / 2;
16348 if (
const SCEV *S = Map.lookup(Expr))
16355 if (
const SCEV *S = Map.lookup(Expr))
16361 if (
const SCEV *S = Map.lookup(Expr))
16367 if (
const SCEV *S = Map.lookup(Expr))
16372 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16377 if (NotEqual.contains({LHS, RHS})) {
16379 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16380 return SE.getUMaxExpr(OneAlignedUp, S);
16387 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16398 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16399 return SE.getAddExpr(
16402 if (
const SCEV *S = Map.lookup(
Add))
16403 return SE.getAddExpr(Expr->
getOperand(0), S);
16411 const SCEV *S =
nullptr;
16418 S = Map.lookup(SE.getAddExpr(NewC, Expr->
getOperand(1)));
16421 return SE.getAddExpr(S, SE.getMinusOne(Expr->
getType()));
16456 if (RewriteMap.empty() && NotEqual.empty())
16459 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16460 return Rewriter.visit(Expr);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Expand Atomic instructions
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
static bool isSigned(unsigned Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
Value * getPointer(Value *Ptr)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This defines the Use class.
iv Induction Variable Users
static constexpr Value * getValue(Ty &ValueOrUse)
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
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 bool CanConstantFold(const Instruction *I)
Return true if we can constant fold an instruction of the specified type, assuming that all operands ...
static cl::opt< unsigned > AddOpsInlineThreshold("scev-addops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining addition operands into a SCEV"), cl::init(500))
static cl::opt< unsigned > MaxLoopGuardCollectionDepth("scalar-evolution-max-loop-guard-collection-depth", cl::Hidden, cl::desc("Maximum depth for recursive loop guard collection"), cl::init(1))
static cl::opt< bool > VerifyIR("scev-verify-ir", cl::Hidden, cl::desc("Verify IR correctness when making sensitive SCEV queries (slow)"), cl::init(false))
static bool RangeRefPHIAllowedOperands(DominatorTree &DT, PHINode *PHI)
static const SCEV * getPreStartForExtend(const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE, unsigned Depth)
static std::optional< APInt > MinOptional(std::optional< APInt > X, std::optional< APInt > Y)
Helper function to compare optional APInts: (a) if X and Y both exist, return min(X,...
static cl::opt< unsigned > MulOpsInlineThreshold("scev-mulops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining multiplication operands into a SCEV"), cl::init(32))
static BinaryOperator * getCommonInstForPHI(PHINode *PN)
static bool isDivisibilityGuard(const SCEV *LHS, const SCEV *RHS, ScalarEvolution &SE)
static std::optional< const SCEV * > createNodeForSelectViaUMinSeq(ScalarEvolution *SE, const SCEV *CondExpr, const SCEV *TrueExpr, const SCEV *FalseExpr)
static Constant * BuildConstantFromSCEV(const SCEV *V)
This builds up a Constant using the ConstantExpr interface.
static ConstantInt * EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C, ScalarEvolution &SE)
static const SCEV * BinomialCoefficient(const SCEV *It, unsigned K, ScalarEvolution &SE, Type *ResultTy)
Compute BC(It, K). The result has width W. Assume, K > 0.
static cl::opt< unsigned > MaxCastDepth("scalar-evolution-max-cast-depth", cl::Hidden, cl::desc("Maximum depth of recursive SExt/ZExt/Trunc"), cl::init(8))
static bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr, const SCEV *Candidate)
Is MaybeMinMaxExpr an (U|S)(Min|Max) of Candidate and some other values?
static PHINode * getConstantEvolvingPHI(Value *V, const Loop *L)
getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node in the loop that V is deri...
static const SCEV * SolveLinEquationWithOverflow(const APInt &A, const SCEV *B, SmallVectorImpl< const SCEVPredicate * > *Predicates, ScalarEvolution &SE, const Loop *L)
Finds the minimum unsigned root of the following equation:
static cl::opt< unsigned > MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, cl::desc("Maximum number of iterations SCEV will " "symbolically execute a constant " "derived loop"), cl::init(100))
static uint64_t umul_ov(uint64_t i, uint64_t j, bool &Overflow)
static void PrintSCEVWithTypeHint(raw_ostream &OS, const SCEV *S)
When printing a top-level SCEV for trip counts, it's helpful to include a type for constants which ar...
static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE, const Loop *L)
static SCEV::NoWrapFlags StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, ArrayRef< SCEVUse > Ops, SCEV::NoWrapFlags Flags)
static bool containsConstantInAddMulChain(const SCEV *StartExpr)
Determine if any of the operands in this SCEV are a constant or if any of the add or multiply express...
static const SCEV * getExtendAddRecStart(const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE, unsigned Depth)
static bool CollectAddOperandsWithScales(SmallDenseMap< SCEVUse, APInt, 16 > &M, SmallVectorImpl< SCEVUse > &NewOps, APInt &AccumulatedConstant, ArrayRef< SCEVUse > Ops, const APInt &Scale, ScalarEvolution &SE)
Process the given Ops list, which is a list of operands to be added under the given scale,...
static const SCEV * constantFoldAndGroupOps(ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT, SmallVectorImpl< SCEVUse > &Ops, FoldT Fold, IsIdentityT IsIdentity, IsAbsorberT IsAbsorber)
Performs a number of common optimizations on the passed Ops.
static bool IsKnownPredicateViaAddRecStart(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
static void GroupByComplexity(SmallVectorImpl< SCEVUse > &Ops, LoopInfo *LI, DominatorTree &DT)
Given a list of SCEV objects, order them by their complexity, and group objects of the same complexit...
static bool collectDivisibilityInformation(ICmpInst::Predicate Predicate, const SCEV *LHS, const SCEV *RHS, DenseMap< const SCEV *, const SCEV * > &DivInfo, DenseMap< const SCEV *, APInt > &Multiples, ScalarEvolution &SE)
static cl::opt< unsigned > MaxSCEVOperationsImplicationDepth("scalar-evolution-max-scev-operations-implication-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV operations implication analysis"), cl::init(2))
static void PushDefUseChildren(Instruction *I, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push users of the given Instruction onto the given Worklist.
static std::optional< APInt > SolveQuadraticAddRecRange(const SCEVAddRecExpr *AddRec, const ConstantRange &Range, ScalarEvolution &SE)
Let c(n) be the value of the quadratic chrec {0,+,M,+,N} after n iterations.
static cl::opt< bool > UseContextForNoWrapFlagInference("scalar-evolution-use-context-for-no-wrap-flag-strenghening", cl::Hidden, cl::desc("Infer nuw/nsw flags using context where suitable"), cl::init(true))
static cl::opt< bool > EnableFiniteLoopControl("scalar-evolution-finite-loop", cl::Hidden, cl::desc("Handle <= and >= in finite loops"), cl::init(true))
static bool getOperandsForSelectLikePHI(DominatorTree &DT, PHINode *PN, Value *&Cond, Value *&LHS, Value *&RHS)
static std::optional< std::tuple< APInt, APInt, APInt, APInt, unsigned > > GetQuadraticEquation(const SCEVAddRecExpr *AddRec)
For a given quadratic addrec, generate coefficients of the corresponding quadratic equation,...
static bool isKnownPredicateExtendIdiom(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
static std::optional< BinaryOp > MatchBinaryOp(Value *V, const DataLayout &DL, AssumptionCache &AC, const DominatorTree &DT, const Instruction *CxtI)
Try to map V into a BinaryOp, and return std::nullopt on failure.
static std::optional< APInt > SolveQuadraticAddRecExact(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE)
Let c(n) be the value of the quadratic chrec {L,+,M,+,N} after n iterations.
static std::optional< APInt > TruncIfPossible(std::optional< APInt > X, unsigned BitWidth)
Helper function to truncate an optional APInt to a given BitWidth.
static cl::opt< unsigned > MaxSCEVCompareDepth("scalar-evolution-max-scev-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV complexity comparisons"), cl::init(32))
static APInt extractConstantWithoutWrapping(ScalarEvolution &SE, const SCEVConstant *ConstantTerm, const SCEVAddExpr *WholeAddExpr)
static cl::opt< unsigned > MaxConstantEvolvingDepth("scalar-evolution-max-constant-evolving-depth", cl::Hidden, cl::desc("Maximum depth of recursive constant evolving"), cl::init(32))
static bool MatchBinarySub(const SCEV *S, SCEVUse &LHS, SCEVUse &RHS)
static std::optional< ConstantRange > GetRangeFromMetadata(Value *V)
Helper method to assign a range to V from metadata present in the IR.
static cl::opt< unsigned > HugeExprThreshold("scalar-evolution-huge-expr-threshold", cl::Hidden, cl::desc("Size of the expression which is considered huge"), cl::init(4096))
static Type * isSimpleCastedPHI(const SCEV *Op, const SCEVUnknown *SymbolicPHI, bool &Signed, ScalarEvolution &SE)
Helper function to createAddRecFromPHIWithCasts.
static Constant * EvaluateExpression(Value *V, const Loop *L, DenseMap< Instruction *, Constant * > &Vals, const DataLayout &DL, const TargetLibraryInfo *TLI)
EvaluateExpression - Given an expression that passes the getConstantEvolvingPHI predicate,...
static const SCEV * getPreviousSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static const SCEV * MatchNotExpr(const SCEV *Expr)
If Expr computes ~A, return A else return nullptr.
static std::pair< ConstantRange, bool > getRangeForAffineARHelper(APInt Step, const ConstantRange &StartRange, const APInt &MaxBECount, bool Signed)
static cl::opt< unsigned > MaxValueCompareDepth("scalar-evolution-max-value-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive value complexity comparisons"), cl::init(2))
static const SCEV * applyDivisibilityOnMinMaxExpr(const SCEV *MinMaxExpr, APInt Divisor, ScalarEvolution &SE)
static cl::opt< bool, true > VerifySCEVOpt("verify-scev", cl::Hidden, cl::location(VerifySCEV), cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"))
static const SCEV * getSignedOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static cl::opt< unsigned > MaxArithDepth("scalar-evolution-max-arith-depth", cl::Hidden, cl::desc("Maximum depth of recursive arithmetics"), cl::init(32))
static bool HasSameValue(const SCEV *A, const SCEV *B)
SCEV structural equivalence is usually sufficient for testing whether two expressions are equal,...
static uint64_t Choose(uint64_t n, uint64_t k, bool &Overflow)
Compute the result of "n choose k", the binomial coefficient.
static std::optional< int > CompareSCEVComplexity(const LoopInfo *const LI, const SCEV *LHS, const SCEV *RHS, DominatorTree &DT, unsigned Depth=0)
static bool canConstantEvolve(Instruction *I, const Loop *L)
Determine whether this instruction can constant evolve within this loop assuming its operands can all...
static PHINode * getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L, DenseMap< Instruction *, PHINode * > &PHIMap, unsigned Depth)
getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by recursing through each instructi...
static bool scevUnconditionallyPropagatesPoisonFromOperands(SCEVTypes Kind)
static cl::opt< bool > VerifySCEVStrict("verify-scev-strict", cl::Hidden, cl::desc("Enable stricter verification with -verify-scev is passed"))
static Constant * getOtherIncomingValue(PHINode *PN, BasicBlock *BB)
static cl::opt< bool > UseExpensiveRangeSharpening("scalar-evolution-use-expensive-range-sharpening", cl::Hidden, cl::init(false), cl::desc("Use more powerful methods of sharpening expression ranges. May " "be costly in terms of compile time"))
static const SCEV * getUnsignedOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static bool IsKnownPredicateViaMinOrMax(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Is LHS Pred RHS true on the virtue of LHS or RHS being a Min or Max expression?
static bool BrPHIToSelect(DominatorTree &DT, CondBrInst *BI, PHINode *Merge, Value *&C, Value *&LHS, Value *&RHS)
This file defines the scope_exit class, which executes user-defined cleanup logic at scope exit.
static bool InBlock(const Value *V, const BasicBlock *BB)
Provides some synthesis utilities to produce sequences of values.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
static SymbolRef::Type getType(const Symbol *Sym)
LocallyHashedType DenseMapInfo< LocallyHashedType >::Empty
static std::optional< bool > isImpliedCondOperands(CmpInst::Predicate Pred, const Value *ALHS, const Value *ARHS, const Value *BLHS, const Value *BRHS)
Return true if "icmp Pred BLHS BRHS" is true whenever "icmp PredALHS ARHS" is true.
Virtual Register Rewriter
static const uint32_t IV[8]
SCEVCastSinkingRewriter(ScalarEvolution &SE, Type *TargetTy, ConversionFn CreatePtrCast)
static const SCEV * rewrite(const SCEV *Scev, ScalarEvolution &SE, Type *TargetTy, ConversionFn CreatePtrCast)
const SCEV * visitUnknown(const SCEVUnknown *Expr)
const SCEV * visitMulExpr(const SCEVMulExpr *Expr)
const SCEV * visitAddExpr(const SCEVAddExpr *Expr)
const SCEV * visit(const SCEV *S)
Class for arbitrary precision integers.
LLVM_ABI APInt umul_ov(const APInt &RHS, bool &Overflow) const
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
uint64_t getZExtValue() const
Get zero extended value.
unsigned getActiveBits() const
Compute the number of active bits in the value.
LLVM_ABI APInt trunc(unsigned width) const
Truncate to new width.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
APInt abs() const
Get the absolute value.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool isSignMask() const
Check if the APInt's value is returned by getSignMask.
LLVM_ABI APInt urem(const APInt &RHS) const
Unsigned remainder operation.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
bool isNegative() const
Determine sign of this APInt.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
LLVM_ABI APInt uadd_ov(const APInt &RHS, bool &Overflow) const
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
bool isNonPositive() const
Determine if this APInt Value is non-positive (<= 0).
unsigned countTrailingZeros() const
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
unsigned logBase2() const
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
LLVM_ABI APInt multiplicativeInverse() const
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
LLVM_ABI APInt sext(unsigned width) const
Sign extend to a new width.
APInt shl(unsigned shiftAmt) const
Left-shift function.
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
bool isSignBitSet() const
Determine if sign bit of this APInt is set.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
This templated class represents "all analyses that operate over <aparticular IR unit>" (e....
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
AnalysisUsage & addRequiredTransitive()
Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
Get the array size.
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
MutableArrayRef< WeakVH > assumptions()
Access the list of assumption handles currently tracked for this function.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
LLVM_ABI unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
LLVM_ABI Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
BinaryOps getOpcode() const
This class represents a function call, abstracting a target machine's calling convention.
virtual void deleted()
Callback for Value destruction.
bool isFalseWhenEqual() const
This is just a convenience.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ ICMP_UGE
unsigned greater or equal
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
@ ICMP_SGE
signed greater or equal
@ ICMP_ULE
unsigned less or equal
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
bool isTrueWhenEqual() const
This is just a convenience.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
static LLVM_ABI std::optional< CmpPredicate > getMatching(CmpPredicate A, CmpPredicate B)
Compares two CmpPredicates taking samesign into account and returns the canonicalized CmpPredicate if...
LLVM_ABI CmpInst::Predicate getPreferredSignedPredicate() const
Attempts to return a signed CmpInst::Predicate from the CmpPredicate.
CmpInst::Predicate dropSameSign() const
Drops samesign information.
Conditional Branch instruction.
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
static LLVM_ABI Constant * getNot(Constant *C)
static Constant * getPtrAdd(Constant *Ptr, Constant *Offset, GEPNoWrapFlags NW=GEPNoWrapFlags::none(), std::optional< ConstantRange > InRange=std::nullopt, Type *OnlyIfReduced=nullptr)
Create a getelementptr i8, ptr, offset constant expression.
static LLVM_ABI Constant * getPtrToAddr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static LLVM_ABI Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
static LLVM_ABI Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
This is the shared class of boolean and integer constants.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
static LLVM_ABI ConstantInt * getBool(LLVMContext &Context, bool V)
This class represents a range of values.
LLVM_ABI ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
LLVM_ABI ConstantRange zextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
PreferredRangeType
If represented precisely, the result of some range operations may consist of multiple disjoint ranges...
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI ConstantRange urem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned remainder operation of...
LLVM_ABI bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
LLVM_ABI bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other?
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI ConstantRange zeroExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
LLVM_ABI bool isSignWrappedSet() const
Return true if this set wraps around the signed domain.
LLVM_ABI APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
LLVM_ABI bool isWrappedSet() const
Return true if this set wraps around the unsigned domain.
LLVM_ABI void print(raw_ostream &OS) const
Print out the bounds to a stream.
LLVM_ABI ConstantRange truncate(uint32_t BitWidth, unsigned NoWrapKind=0) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
LLVM_ABI ConstantRange signExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI bool contains(const APInt &Val) const
Return true if the specified value is in the set.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
LLVM_ABI ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
LLVM_ABI APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
static LLVM_ABI ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
LLVM_ABI unsigned getMinSignedBits() const
Compute the maximal number of bits needed to represent every value in this signed range.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
LLVM_ABI ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
LLVM_ABI ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
static LLVM_ABI ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)
Produce the range that contains X if and only if "X BinOp Other" does not wrap.
This is an important base class in LLVM.
A parsed version of the target data layout string in and methods for querying it.
LLVM_ABI const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
LLVM_ABI unsigned getIndexTypeSizeInBits(Type *Ty) const
The size in bits of the index used in GEP calculation for this type.
LLVM_ABI IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
TypeSize getTypeSizeInBits(Type *Ty) const
Size examples:
ValueT lookup(const_arg_type_t< KeyT > Val) const
Return the entry for the specified key, or a default constructed value if no such entry exists.
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive,...
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Analysis pass which computes a DominatorTree.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
This class describes a reference to an interned FoldingSetNodeID, which can be a useful to store node...
This class is used to gather all the unique data bits of a node.
void AddInteger(signed I)
Represents flags for the getelementptr instruction/expression.
bool hasNoUnsignedSignedWrap() const
bool hasNoUnsignedWrap() const
static GEPNoWrapFlags none()
static LLVM_ABI Type * getTypeAtIndex(Type *Ty, Value *Idx)
Return the type of the element at the given index of an indexable type.
Module * getParent()
Get the module that this global value is contained inside of...
static bool isPrivateLinkage(LinkageTypes Linkage)
static bool isInternalLinkage(LinkageTypes Linkage)
This instruction compares its operands according to the predicate given to the constructor.
CmpPredicate getCmpPredicate() const
static bool isGE(Predicate P)
Return true if the predicate is SGE or UGE.
CmpPredicate getSwappedCmpPredicate() const
static LLVM_ABI bool compare(const APInt &LHS, const APInt &RHS, ICmpInst::Predicate Pred)
Return result of LHS Pred RHS comparison.
static bool isLT(Predicate P)
Return true if the predicate is SLT or ULT.
CmpPredicate getInverseCmpPredicate() const
Predicate getNonStrictCmpPredicate() const
For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.
static bool isGT(Predicate P)
Return true if the predicate is SGT or UGT.
Predicate getFlippedSignednessPredicate() const
For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->EQ.
static CmpPredicate getInverseCmpPredicate(CmpPredicate Pred)
bool isEquality() const
Return true if this predicate is either EQ or NE.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
static bool isLE(Predicate P)
Return true if the predicate is SLE or ULE.
LLVM_ABI bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
LLVM_ABI bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
LLVM_ABI bool isIdenticalToWhenDefined(const Instruction *I, bool IntersectAttrs=false) const LLVM_READONLY
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...
Class to represent integer types.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
A helper class to return the specified delimiter string after the first invocation of operator String...
An instruction for reading from memory.
Analysis pass that exposes the LoopInfo for a function.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within this loop.
BlockT * getHeader() const
unsigned getLoopDepth() const
Return the nesting level of this loop.
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
A Module instance is used to store all the information related to an LLVM module.
unsigned getOpcode() const
Return the opcode for this Instruction or ConstantExpr.
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
bool hasNoSignedWrap() const
Test whether this operation is known to never undergo signed overflow, aka the nsw property.
bool hasNoUnsignedWrap() const
Test whether this operation is known to never undergo unsigned overflow, aka the nuw property.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
PointerIntPair - This class implements a pair of a pointer and small integer.
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
LLVM_ABI void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
LLVM_ABI const SCEVPredicate & getPredicate() const
LLVM_ABI const SCEV * getPredicatedSCEV(const SCEV *Expr)
Returns the rewritten SCEV for Expr in the context of the current SCEV predicate.
LLVM_ABI bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2, ArrayRef< const SCEVPredicate * > ExtraPreds={}) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds and ExtraPreds.
LLVM_ABI bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've statically proved that V doesn't wrap.
LLVM_ABI const SCEVAddRecExpr * getAsAddRec(Value *V, SmallVectorImpl< const SCEVPredicate * > *WrapPredsAdded=nullptr)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
LLVM_ABI void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
LLVM_ABI PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
LLVM_ABI unsigned getSmallConstantMaxTripCount()
Returns the upper bound of the loop trip count as a normal unsigned value, or 0 if the trip count is ...
LLVM_ABI void addPredicates(ArrayRef< const SCEVPredicate * > Preds)
Adds all predicates in Preds.
LLVM_ABI const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSymbolicMaxBackedgeTakenCount()
Get the (predicated) symbolic max backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
constexpr bool isValid() const
This node represents an addition of some number of SCEVs.
This node represents a polynomial recurrence on the trip count of the specified loop.
friend class ScalarEvolution
LLVM_ABI const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a recurrence without clearing any previously set flags.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
bool isQuadratic() const
Return true if this represents an expression A + B*x + C*x^2 where A, B and C are loop invariant valu...
LLVM_ABI const SCEV * getNumIterationsInRange(const ConstantRange &Range, ScalarEvolution &SE) const
Return the number of iterations of this loop that produce values in the specified constant range.
LLVM_ABI const SCEVAddRecExpr * getPostIncExpr(ScalarEvolution &SE) const
Return an expression representing the value of this expression one iteration of the loop ahead.
const Loop * getLoop() const
SCEVUse getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
This is the base class for unary cast operator classes.
SCEVUse getOperand() const
LLVM_ABI SCEVCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, SCEVUse op, Type *ty)
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a non-recurrence without clearing previously set flags.
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
SCEVComparePredicate(const FoldingSetNodeIDRef ID, const ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Implementation of the SCEVPredicate interface.
This class represents a constant integer value.
ConstantInt * getValue() const
const APInt & getAPInt() const
This is the base class for unary integral cast operator classes.
LLVM_ABI SCEVIntegralCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, SCEVUse op, Type *ty)
This node is the base class min/max selections.
static enum SCEVTypes negate(enum SCEVTypes T)
This node represents multiplication of some number of SCEVs.
This node is a base class providing common functionality for n'ary operators.
bool hasNoUnsignedWrap() const
ArrayRef< SCEVUse > operands() const
bool hasNoSelfWrap() const
size_t getNumOperands() const
bool hasNoSignedWrap() const
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
SCEVUse getOperand(unsigned i) const
This class represents an assumption made using SCEV expressions which can be checked at run-time.
SCEVPredicate(const SCEVPredicate &)=default
virtual bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const =0
Returns true if this predicate implies N.
This class represents a cast from a pointer to a pointer-sized integer value, without capturing the p...
This visitor recursively visits a SCEV expression and re-writes it.
const SCEV * visitSignExtendExpr(const SCEVSignExtendExpr *Expr)
const SCEV * visit(const SCEV *S)
const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)
const SCEV * visitSMinExpr(const SCEVSMinExpr *Expr)
SCEVRewriteVisitor(ScalarEvolution &SE)
const SCEV * visitUMinExpr(const SCEVUMinExpr *Expr)
This class represents a signed minimum selection.
This node is the base class for sequential/in-order min/max selections.
static SCEVTypes getEquivalentNonSequentialSCEVType(SCEVTypes Ty)
This class represents a sign extension of a small integer value to a larger integer value.
Visit all nodes in the expression tree using worklist traversal.
This class represents a truncation of an integer value to a smaller integer value.
This class represents a binary unsigned division operation.
This class represents an unsigned minimum selection.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
void print(raw_ostream &OS, unsigned Depth) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Returns true if this predicate implies N.
SCEVUnionPredicate(ArrayRef< const SCEVPredicate * > Preds, ScalarEvolution &SE)
Union predicates don't get cached so create a dummy set ID for it.
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
SCEVUnionPredicate getUnionWith(const SCEVPredicate *N, ScalarEvolution &SE) const
Returns a new SCEVUnionPredicate that is the union of this predicate and the given predicate N.
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents the value of vscale, as used when defining the length of a scalable vector or r...
This class represents an assumption made on an AddRec expression.
IncrementWrapFlags
Similar to SCEV::NoWrapFlags, but with slightly different semantics for FlagNUSW.
SCEVWrapPredicate(const FoldingSetNodeIDRef ID, const SCEVAddRecExpr *AR, IncrementWrapFlags Flags)
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Returns true if this predicate implies N.
static SCEVWrapPredicate::IncrementWrapFlags setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OnFlags)
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
const SCEVAddRecExpr * getExpr() const
Implementation of the SCEVPredicate interface.
static SCEVWrapPredicate::IncrementWrapFlags clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OffFlags)
Convenient IncrementWrapFlags manipulation methods.
static SCEVWrapPredicate::IncrementWrapFlags getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE)
Returns the set of SCEVWrapPredicate no wrap flags implied by a SCEVAddRecExpr.
IncrementWrapFlags getFlags() const
Returns the set assumed no overflow flags.
This class represents a zero extension of a small integer value to a larger integer value.
This class represents an analyzed expression in the program.
unsigned short getExpressionSize() const
SCEVNoWrapFlags NoWrapFlags
LLVM_ABI bool isOne() const
Return true if the expression is a constant one.
SCEV(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, unsigned short ExpressionSize, Type *Ty)
static constexpr auto FlagNUW
LLVM_ABI void computeAndSetCanonical(ScalarEvolution &SE)
Compute and set the canonical SCEV, by constructing a SCEV with the same operands,...
LLVM_ABI bool isZero() const
Return true if the expression is a constant zero.
const SCEV * CanonicalSCEV
Pointer to the canonical version of the SCEV, i.e.
static constexpr auto FlagAnyWrap
LLVM_ABI void dump() const
This method is used for debugging.
LLVM_ABI bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
LLVM_ABI bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
static constexpr auto FlagNSW
LLVM_ABI ArrayRef< SCEVUse > operands() const
Return operands of this SCEV expression.
Type * getType() const
Return the LLVM type of this SCEV expression.
LLVM_ABI void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
SCEVTypes getSCEVType() const
static constexpr auto FlagNW
Analysis pass that exposes the ScalarEvolution for a function.
LLVM_ABI ScalarEvolution run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
void print(raw_ostream &OS, const Module *=nullptr) const override
print - Print out the internal state of the pass.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
ScalarEvolutionWrapperPass()
static LLVM_ABI LoopGuards collect(const Loop *L, ScalarEvolution &SE)
Collect rewrite map for loop guards for loop L, together with flags indicating if NUW and NSW can be ...
LLVM_ABI const SCEV * rewrite(const SCEV *Expr) const
Try to apply the collected loop guards to Expr.
The main scalar evolution driver.
LLVM_ABI const SCEV * getUDivExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
static bool hasFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags TestFlags)
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
LLVM_ABI bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
LLVM_ABI bool isKnownOnEveryIteration(CmpPredicate Pred, const SCEVAddRecExpr *LHS, const SCEV *RHS)
Test if the condition described by Pred, LHS, RHS is known to be true on every iteration of the loop ...
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterationsImpl(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
LLVM_ABI const SCEV * 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 * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
LLVM_ABI const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
LLVM_ABI const SCEV * getSMinExpr(SCEVUse LHS, SCEVUse RHS)
LLVM_ABI void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags)
Update no-wrap flags of an AddRec.
LLVM_ABI const SCEV * getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS)
Promote the operands to the wider of the types using zero-extension, and then perform a umax operatio...
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
LLVM_ABI bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?
LLVM_ABI ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsOnlyExit, bool AllowPredicates=false)
Compute the number of times the backedge of the specified loop will execute if its exit condition wer...
LLVM_ABI const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &Operands)
LLVM_ABI const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
LLVM_ABI uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
LLVM_ABI const SCEV * getConstant(ConstantInt *V)
LLVM_ABI const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
LLVM_ABI const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
LLVM_ABI const SCEV * getAddRecExpr(SCEVUse Start, SCEVUse Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
LLVM_ABI const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
static LLVM_ABI bool isGuaranteedNotToBePoison(const SCEV *Op)
Returns true if Op is guaranteed to not be poison.
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
LLVM_ABI const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
LLVM_ABI ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI)
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LLVM_ABI const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI const SCEV * 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 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 isKnownMultipleOf(const SCEV *S, uint64_t M, SmallVectorImpl< const SCEVPredicate * > &Assumptions)
Check that S is a multiple of M.
LLVM_ABI bool isKnownToBeAPowerOfTwo(const SCEV *S, bool OrZero=false, bool OrNegative=false)
Test if the given expression is known to be a power of 2.
LLVM_ABI std::optional< SCEV::NoWrapFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
LLVM_ABI void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)
Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...
LLVM_ABI bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
LLVM_ABI std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
LLVM_ABI const SCEV * getCouldNotCompute()
LLVM_ABI const SCEV * getMulExpr(SmallVectorImpl< SCEVUse > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
LLVM_ABI bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
LLVM_ABI uint32_t getMinTrailingZeros(const SCEV *S, const Instruction *CtxI=nullptr)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
@ DominatesBlock
The SCEV dominates the block.
@ ProperlyDominatesBlock
The SCEV properly dominates the block.
@ DoesNotDominateBlock
The SCEV does not dominate the block.
LLVM_ABI const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
LLVM_ABI 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.
LLVM_ABI const SCEV * getAddExpr(SmallVectorImpl< SCEVUse > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
ExitCountKind
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of ...
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
@ ConstantMaximum
A constant which provides an upper bound on the exact trip count.
@ Exact
An expression exactly describing the number of times the backedge has executed when a loop is exited.
LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
LLVM_ABI const SCEV * getPtrToAddrExpr(const SCEV *Op)
LLVM_ABI const SCEVAddRecExpr * convertSCEVToAddRecWithPredicates(const SCEV *S, const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Preds)
Tries to convert the S expression to an AddRec expression, adding additional predicates to Preds as r...
LLVM_ABI const SCEV * getSMaxExpr(SCEVUse LHS, SCEVUse RHS)
LLVM_ABI const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
LLVM_ABI const SCEV * getSizeOfExpr(Type *IntTy, TypeSize Size)
Return an expression for a TypeSize.
LLVM_ABI std::optional< bool > evaluatePredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Check whether the condition described by Pred, LHS, and RHS is true or false.
LLVM_ABI const SCEV * getUnknown(Value *V)
LLVM_ABI std::optional< std::pair< const SCEV *, SmallVector< const SCEVPredicate *, 3 > > > createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI)
Checks if SymbolicPHI can be rewritten as an AddRecExpr under some Predicates.
LLVM_ABI const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool isKnownViaInduction(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
We'd like to check the predicate on every iteration of the most dominated loop between loops used in ...
LLVM_ABI std::optional< APInt > computeConstantDifference(const SCEV *LHS, const SCEV *RHS)
Compute LHS - RHS and returns the result as an APInt if it is a constant, and std::nullopt if it isn'...
LLVM_ABI bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
LLVM_ABI const SCEV * getUDivExactExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
LLVM_ABI const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
LLVM_ABI std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
LLVM_ABI bool canReuseInstruction(const SCEV *S, Instruction *I, SmallVectorImpl< Instruction * > &DropPoisonGeneratingInsts)
Check whether it is poison-safe to represent the expression S using the instruction I.
LLVM_ABI bool isKnownPredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * getPredicatedSymbolicMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getSymbolicMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI ~ScalarEvolution()
LLVM_ABI const SCEV * getGEPExpr(GEPOperator *GEP, ArrayRef< SCEVUse > IndexExprs)
Returns an expression for a GEP.
LLVM_ABI const SCEV * getUMinExpr(SCEVUse LHS, SCEVUse RHS, bool Sequential=false)
LLVM_ABI void registerUser(const SCEV *User, ArrayRef< const SCEV * > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
LLVM_ABI bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the basic block is protected by a conditional between LHS and RHS.
LLVM_ABI const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool containsErasedValue(const SCEV *S) const
Return true if the SCEV expression contains a Value that has been optimised out and is now a nullptr.
const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
LLVM_ABI void verify() const
LLVMContext & getContext() const
Implements a dense probed hash-table based set with some number of buckets stored inline.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
TypeSize getElementOffset(unsigned Idx) const
TypeSize getSizeInBits() const
Class to represent struct types.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
static LLVM_ABI IntegerType * getIntNTy(LLVMContext &C, unsigned N)
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
LLVMContext & getContext() const
All values hold a context through their type.
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.
LLVM_ABI bool canConstantFoldCallTo(const CallBase *Call, const Function *F)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
InterleavedRange< Range > interleaved(const Range &R, StringRef Separator=", ", StringRef Prefix="", StringRef Suffix="")
Output range R as a sequence of interleaved elements.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
auto successors(const MachineBasicBlock *BB)
scope_exit(Callable) -> scope_exit< Callable >
@ BinaryOp
One of the operands is a binary op.
@ Load
The value being inserted comes from a load (InsertElement only).
@ Store
The extracted value is stored (ExtractElement only).
constexpr from_range_t from_range
auto dyn_cast_if_present(const Y &Val)
dyn_cast_if_present<X> - Functionally identical to dyn_cast, except that a null (or none in the case ...
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
auto uninitialized_copy(R &&Src, IterTy Dst)
bool isa_and_nonnull(const Y &Val)
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO, const DominatorTree &DT)
Returns true if the arithmetic part of the WO 's result is used only along the paths control dependen...
DomTreeNodeBase< BasicBlock > DomTreeNode
LLVM_ABI bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step)
Attempt to match a simple first order recurrence cycle of the form: iv = phi Ty [Start,...
auto dyn_cast_or_null(const Y &Val)
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
auto reverse(ContainerTy &&C)
LLVM_ABI bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
LLVM_ABI bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
LLVM_ABI bool isFinite(const Loop *L)
Return true if this loop can be assumed to run for a finite number of iterations.
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
unsigned short computeExpressionSize(ArrayRef< SCEVUse > Args)
LLVM_ABI bool programUndefinedIfPoison(const Instruction *Inst)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isPointerTy(const Type *T)
LLVM_ABI ConstantRange getVScaleRange(const Function *F, unsigned BitWidth)
Determine the possible constant range of vscale with the given bit width, based on the vscale_range f...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
LLVM_ABI bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)
Return true if the given value is known to be non-zero when defined.
constexpr T divideCeil(U Numerator, V Denominator)
Returns the integer ceil(Numerator / Denominator).
LLVM_ABI bool propagatesPoison(const Use &PoisonOp)
Return true if PoisonOp's user yields poison or raises UB if its operand PoisonOp is poison.
@ UMin
Unsigned integer min implemented in terms of select(cmp()).
@ Mul
Product of integers.
@ SMax
Signed integer max implemented in terms of select(cmp()).
@ SMin
Signed integer min implemented in terms of select(cmp()).
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
DWARFExpression::Operation Op
auto max_element(R &&Range)
Provide wrappers to std::max_element which take ranges instead of having to pass begin/end explicitly...
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
ArrayRef(const T &OneElt) -> ArrayRef< T >
LLVM_ABI unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Return the number of times the sign bit of the register is replicated into the other bits.
constexpr unsigned BitWidth
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
constexpr auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
constexpr bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
iterator_range< df_iterator< T > > depth_first(const T &G)
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be poison, but may be undef.
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
SCEVUseT< const SCEV * > SCEVUse
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
Implement std::hash so that hash_code can be used in STL containers.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
A special type used by analysis passes to provide an address that identifies that particular analysis...
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
static LLVM_ABI KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for ashr(LHS, RHS).
static LLVM_ABI KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for lshr(LHS, RHS).
static LLVM_ABI KnownBits shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW=false, bool NSW=false, bool ShAmtNonZero=false)
Compute known bits for shl(LHS, RHS).
An object of this class is returned by queries that could not be answered.
LLVM_ABI SCEVCouldNotCompute()
static LLVM_ABI bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This class defines a simple visitor class that may be used for various SCEV analysis purposes.
A utility class that uses RAII to save and restore the value of a variable.
Information about the number of loop iterations for which a loop exit's branch condition evaluates to...
LLVM_ABI ExitLimit(const SCEV *E)
Construct either an exact exit limit from a constant, or an unknown one from a SCEVCouldNotCompute.
const SCEV * ExactNotTaken
const SCEV * SymbolicMaxNotTaken
SmallVector< const SCEVPredicate *, 4 > Predicates
A vector of predicate guards for this ExitLimit.
const SCEV * ConstantMaxNotTaken