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"));
242 "scalar-evolution-max-scc-analysis-depth",
cl::Hidden,
243 cl::desc(
"Maximum amount of nodes to process while searching SCEVUnknown "
244 "Phi strongly connected components"),
249 cl::desc(
"Handle <= and >= in finite loops"),
253 "scalar-evolution-use-context-for-no-wrap-flag-strenghening",
cl::Hidden,
254 cl::desc(
"Infer nuw/nsw flags using context where suitable"),
340#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
358 OS <<
"(ptrtoaddr " << *
Op->getType() <<
" " << *
Op <<
" to "
365 OS <<
"(trunc " << *
Op->getType() <<
" " << *
Op <<
" to "
372 OS <<
"(zext " << *
Op->getType() <<
" " << *
Op <<
" to "
379 OS <<
"(sext " << *
Op->getType() <<
" " << *
Op <<
" to "
408 const char *OpStr =
nullptr;
421 OpStr =
" umin_seq ";
445 OS <<
"(" << *UDiv->
getLHS() <<
" /u " << *UDiv->
getRHS() <<
")";
452 OS <<
"***COULDNOTCOMPUTE***";
494 if (!
Mul)
return false;
498 if (!SC)
return false;
512 auto &Entry = ConstantSCEVs[V];
521 static_cast<SCEVConstant *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP)))
524 new (SCEVAllocator)
SCEVConstant(ID.Intern(SCEVAllocator), V);
525 UniqueSCEVs.InsertNode(S, IP);
540 ConstantInt::get(ITy, V,
isSigned,
true));
548 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
550 SCEV *S =
new (SCEVAllocator)
SCEVVScale(ID.Intern(SCEVAllocator), Ty);
551 UniqueSCEVs.InsertNode(S, IP);
572 "Must be a non-bit-width-changing pointer-to-integer cast!");
584 "Cannot truncate non-integer value!");
591 "Cannot zero extend non-integer value!");
598 "Cannot sign extend non-integer value!");
603 SE->forgetMemoizedResults({
this});
606 SE->UniqueSCEVs.RemoveNode(
this);
612void SCEVUnknown::allUsesReplacedWith(
Value *New) {
614 SE->forgetMemoizedResults({
this});
617 SE->UniqueSCEVs.RemoveNode(
this);
639 if (LIsPointer != RIsPointer)
640 return (
int)LIsPointer - (int)RIsPointer;
645 return (
int)LID - (int)RID;
650 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
651 return (
int)LArgNo - (int)RArgNo;
657 if (
auto L = LGV->getLinkage() - RGV->getLinkage())
660 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
661 auto LT = GV->getLinkage();
668 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
669 return LGV->getName().compare(RGV->getName());
680 if (LParent != RParent) {
683 if (LDepth != RDepth)
684 return (
int)LDepth - (int)RDepth;
688 unsigned LNumOps = LInst->getNumOperands(),
689 RNumOps = RInst->getNumOperands();
690 if (LNumOps != RNumOps)
691 return (
int)LNumOps - (int)RNumOps;
693 for (
unsigned Idx :
seq(LNumOps)) {
695 RInst->getOperand(Idx),
Depth + 1);
709static std::optional<int>
719 return (
int)LType - (int)RType;
744 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
745 if (LBitWidth != RBitWidth)
746 return (
int)LBitWidth - (int)RBitWidth;
747 return LA.
ult(
RA) ? -1 : 1;
753 return LTy->getBitWidth() - RTy->getBitWidth();
764 if (LLoop != RLoop) {
766 assert(LHead != RHead &&
"Two loops share the same header?");
770 "No dominance between recurrences used by one SCEV?");
793 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
794 if (LNumOps != RNumOps)
795 return (
int)LNumOps - (int)RNumOps;
797 for (
unsigned i = 0; i != LNumOps; ++i) {
823 if (
Ops.size() < 2)
return;
828 return Complexity && *Complexity < 0;
830 if (
Ops.size() == 2) {
834 if (IsLessComplex(
RHS,
LHS))
847 for (
unsigned i = 0, e =
Ops.size(); i != e-2; ++i) {
853 for (
unsigned j = i+1; j != e &&
Ops[j]->getSCEVType() == Complexity; ++j) {
858 if (i == e-2)
return;
880template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
884 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
886 for (
unsigned Idx = 0; Idx <
Ops.size();) {
894 Ops.erase(
Ops.begin() + Idx);
901 assert(Folded &&
"Must have folded value");
905 if (Folded && IsAbsorber(Folded->
getAPInt()))
909 if (Folded && !IsIdentity(Folded->
getAPInt()))
910 Ops.insert(
Ops.begin(), Folded);
912 return Ops.size() == 1 ?
Ops[0] :
nullptr;
987 APInt OddFactorial(W, 1);
989 for (
unsigned i = 3; i <= K; ++i) {
992 OddFactorial *= (i >> TwoFactors);
996 unsigned CalculationBits = W +
T;
1010 for (
unsigned i = 1; i != K; ++i) {
1043 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1072 ConversionFn CreatePtrCast;
1076 ConversionFn CreatePtrCast)
1077 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
1080 Type *TargetTy, ConversionFn CreatePtrCast) {
1082 return Rewriter.visit(Scev);
1118 "Should only reach pointer-typed SCEVUnknown's.");
1123 return SE.getZero(TargetTy);
1124 return CreatePtrCast(Expr);
1129 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1133 if (DL.hasUnstableRepresentation(
Op->getType()))
1136 Type *Ty = DL.getAddressType(
Op->getType());
1147 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
1149 SCEV *S =
new (SCEVAllocator)
1151 UniqueSCEVs.InsertNode(S, IP);
1154 return static_cast<const SCEV *
>(S);
1157 "We must have succeeded in sinking the cast, "
1158 "and ending up with an integer-typed expression!");
1165 "This is not a truncating conversion!");
1167 "This is not a conversion to a SCEVable type!");
1168 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1176 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1198 UniqueSCEVs.InsertNode(S, IP);
1211 unsigned numTruncs = 0;
1212 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1220 if (numTruncs < 2) {
1230 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
1237 for (
const SCEV *
Op : AddRec->operands())
1252 UniqueSCEVs.InsertNode(S, IP);
1293struct ExtendOpTraitsBase {
1294 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
const SCEV *,
Type *,
1299template <
typename ExtendOp>
struct ExtendOpTraits {
1315 static const GetExtendExprTy GetExtendExpr;
1317 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1318 ICmpInst::Predicate *Pred,
1319 ScalarEvolution *SE) {
1324const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1331 static const GetExtendExprTy GetExtendExpr;
1333 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1334 ICmpInst::Predicate *Pred,
1335 ScalarEvolution *SE) {
1340const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1352template <
typename ExtendOpTy>
1355 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1356 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1372 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1385 auto PreStartFlags =
1403 const SCEV *OperandExtendedStart =
1405 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1406 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1418 const SCEV *OverflowLimit =
1419 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1421 if (OverflowLimit &&
1429template <
typename ExtendOpTy>
1433 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1441 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1476template <
typename ExtendOpTy>
1477bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1480 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1490 APInt StartAI = StartC->
getAPInt();
1492 for (
unsigned Delta : {-2, -1, 1, 2}) {
1493 const SCEV *PreStart =
getConstant(StartAI - Delta);
1495 FoldingSetNodeID
ID;
1497 ID.AddPointer(PreStart);
1498 ID.AddPointer(Step);
1502 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
1506 if (PreAR &&
any(PreAR->getNoWrapFlags(WrapType))) {
1509 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1510 DeltaS, &Pred,
this);
1528 const unsigned BitWidth =
C.getBitWidth();
1546 const APInt &ConstantStart,
1561 auto I = FoldCache.
insert({ID, S});
1565 auto &UserIDs = FoldCacheUser[
I.first->second];
1566 assert(
count(UserIDs, ID) == 1 &&
"unexpected duplicates in UserIDs");
1567 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1568 if (UserIDs[
I] == ID) {
1573 I.first->second = S;
1575 FoldCacheUser[S].push_back(ID);
1581 "This is not an extending conversion!");
1583 "This is not a conversion to a SCEVable type!");
1584 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1588 if (
const SCEV *S = FoldCache.lookup(ID))
1600 "This is not an extending conversion!");
1602 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1614 const SCEV *Start, *Step;
1619 if (AR->hasNoUnsignedWrap()) {
1633 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1637 UniqueSCEVs.InsertNode(S, IP);
1647 const SCEV *
X = ST->getOperand();
1680 const SCEV *CastedMaxBECount =
1684 if (MaxBECount == RecastedMaxBECount) {
1693 const SCEV *WideMaxBECount =
1695 const SCEV *OperandExtendedAdd =
1701 if (ZAdd == OperandExtendedAdd) {
1712 OperandExtendedAdd =
1718 if (ZAdd == OperandExtendedAdd) {
1739 !AC.assumptions().empty()) {
1741 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1743 if (AR->hasNoUnsignedWrap()) {
1778 const APInt &
C = SC->getAPInt();
1782 const SCEV *SResidual =
1790 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1814 if (SA->hasNoUnsignedWrap()) {
1827 if (SA->hasNoSignedWrap() &&
1830 C->isNegative() && !
C->isMinSignedValue() && C2->
sge(
C->abs())) {
1849 const SCEV *SResidual =
1860 if (SM->hasNoUnsignedWrap()) {
1882 const SCEV *TruncRHS;
1919 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1922 UniqueSCEVs.InsertNode(S, IP);
1931 "This is not an extending conversion!");
1933 "This is not a conversion to a SCEVable type!");
1934 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1938 if (
const SCEV *S = FoldCache.lookup(ID))
1950 "This is not an extending conversion!");
1952 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1969 const SCEV *Start, *Step;
1974 if (AR->hasNoSignedWrap()) {
1988 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1993 UniqueSCEVs.InsertNode(S, IP);
2003 const SCEV *
X = ST->getOperand();
2014 if (SA->hasNoSignedWrap()) {
2036 const SCEV *SResidual =
2069 const SCEV *CastedMaxBECount =
2073 if (MaxBECount == RecastedMaxBECount) {
2082 const SCEV *WideMaxBECount =
2084 const SCEV *OperandExtendedAdd =
2090 if (SAdd == OperandExtendedAdd) {
2101 OperandExtendedAdd =
2107 if (SAdd == OperandExtendedAdd) {
2127 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2129 if (AR->hasNoSignedWrap()) {
2143 const APInt &
C = SC->getAPInt();
2147 const SCEV *SResidual =
2155 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2182 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
2185 UniqueSCEVs.InsertNode(S, IP);
2202 assert(Expr->
getType() == Ty &&
"requested type must match");
2215 "This is not an extending conversion!");
2217 "This is not a conversion to a SCEVable type!");
2222 if (SC->getAPInt().isNegative())
2227 const SCEV *NewOp =
T->getOperand();
2246 for (
const SCEV *
Op : AR->operands())
2284 APInt &AccumulatedConstant,
2288 bool Interesting =
false;
2295 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2297 AccumulatedConstant += Scale *
C->getAPInt();
2302 for (; i !=
Ops.size(); ++i) {
2311 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2317 auto Pair = M.insert({
Key, NewScale});
2321 Pair.first->second += NewScale;
2329 auto Pair = M.insert({
Ops[i], Scale});
2333 Pair.first->second += Scale;
2352 case Instruction::Add:
2355 case Instruction::Sub:
2358 case Instruction::Mul:
2372 const SCEV *
A = (this->*Extension)(
2374 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2375 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2383 if (BinOp == Instruction::Mul)
2389 APInt C = RHSC->getAPInt();
2390 unsigned NumBits =
C.getBitWidth();
2391 bool IsSub = (BinOp == Instruction::Sub);
2392 bool IsNegativeConst = (
Signed &&
C.isNegative());
2394 bool OverflowDown = IsSub ^ IsNegativeConst;
2396 if (IsNegativeConst) {
2409 APInt Limit = Min + Magnitude;
2415 APInt Limit = Max - Magnitude;
2420std::optional<SCEV::NoWrapFlags>
2425 return std::nullopt;
2434 bool Deduced =
false;
2440 bool CanUseNSW =
true;
2441 const APInt *ShiftAmt;
2446 return std::nullopt;
2450 Opcode = Instruction::Mul;
2452 }
else if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
2453 Opcode != Instruction::Mul) {
2454 return std::nullopt;
2473 return std::nullopt;
2483 using namespace std::placeholders;
2490 assert(CanAnalyze &&
"don't call from other places!");
2497 auto IsKnownNonNegative = [&](
SCEVUse U) {
2506 if (SignOrUnsignWrap != SignOrUnsignMask &&
2513 return Instruction::Add;
2515 return Instruction::Mul;
2526 Opcode,
C, OBO::NoSignedWrap);
2534 Opcode,
C, OBO::NoUnsignedWrap);
2544 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2551 if (UDiv->getOperand(1) ==
Ops[1])
2554 if (UDiv->getOperand(1) ==
Ops[0])
2570 "only nuw or nsw allowed");
2571 assert(!
Ops.empty() &&
"Cannot get empty add!");
2572 if (
Ops.size() == 1)
return Ops[0];
2575 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2577 "SCEVAddExpr operand types don't match!");
2579 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2580 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2585 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2586 [](
const APInt &
C) {
return C.isZero(); },
2587 [](
const APInt &
C) {
return false; });
2600 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2605 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2606 Add->setNoWrapFlags(ComputeFlags(
Ops));
2614 bool FoundMatch =
false;
2615 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2616 if (
Ops[i] ==
Ops[i+1]) {
2628 --i; e -=
Count - 1;
2638 auto FindTruncSrcType = [&]() ->
Type * {
2644 return T->getOperand()->getType();
2646 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2648 return T->getOperand()->getType();
2652 if (
auto *SrcType = FindTruncSrcType()) {
2659 if (
T->getOperand()->getType() != SrcType) {
2668 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2671 if (
T->getOperand()->getType() != SrcType) {
2699 if (
Ops.size() == 2) {
2709 auto C2 =
C->getAPInt();
2712 APInt ConstAdd = C1 + C2;
2713 auto AddFlags = AddExpr->getNoWrapFlags();
2754 if (
Ops.size() == 2 &&
2765 if (Idx <
Ops.size()) {
2766 bool DeletedAdd =
false;
2777 Ops.erase(
Ops.begin()+Idx);
2780 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2803 struct APIntCompare {
2804 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2805 return LHS.ult(RHS);
2812 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2813 for (
const SCEV *NewOp : NewOps)
2814 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2817 if (AccumulatedConstant != 0)
2819 for (
auto &MulOp : MulOpLists) {
2820 if (MulOp.first == 1) {
2822 }
else if (MulOp.first != 0) {
2831 if (
Ops.size() == 1)
2840 if (M->getNumOperands() == 2)
2841 return M->getOperand(
OpIdx == 0);
2852 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2856 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2864 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp) {
2865 if (MulOpSCEV ==
Ops[AddOp]) {
2876 for (
unsigned OMulOp = 0, OE = OtherMul->
getNumOperands(); OMulOp != OE;
2878 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2880 Cofactors.
push_back(StripFactor(OtherMul, OMulOp));
2889 if (!Cofactors.
empty()) {
2897 if (
Ops.size() == DeadIndices.
size() + 1)
2904 Ops.erase(
Ops.begin() + Idx);
2908 Ops.push_back(OuterMul);
2927 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2930 Ops.erase(
Ops.begin()+i);
2935 if (!LIOps.
empty()) {
2960 auto *DefI = getDefiningScopeBound(LIOps);
2962 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2974 if (
Ops.size() == 1)
return NewRec;
2977 for (
unsigned i = 0;; ++i)
2978 if (
Ops[i] == AddRec) {
2988 for (
unsigned OtherIdx = Idx+1;
2996 "AddRecExprs are not sorted in reverse dominance order?");
3003 if (OtherAddRec->getLoop() == AddRecLoop) {
3004 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
3006 if (i >= AddRecOps.
size()) {
3007 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
3011 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
3014 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3029 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
3040 static_cast<SCEVAddExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
3044 S =
new (SCEVAllocator)
3046 UniqueSCEVs.InsertNode(S, IP);
3057 FoldingSetNodeID
ID;
3059 for (
const SCEV *
Op :
Ops)
3064 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
3068 S =
new (SCEVAllocator)
3069 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3070 UniqueSCEVs.InsertNode(S, IP);
3072 LoopUsers[
L].push_back(S);
3081 FoldingSetNodeID
ID;
3083 for (
const SCEV *
Op :
Ops)
3087 static_cast<SCEVMulExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
3091 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3093 UniqueSCEVs.InsertNode(S, IP);
3103 if (j > 1 && k / j != i) Overflow =
true;
3119 if (n == 0 || n == k)
return 1;
3120 if (k > n)
return 0;
3126 for (
uint64_t i = 1; i <= k; ++i) {
3127 r =
umul_ov(r, n-(i-1), Overflow);
3136 struct FindConstantInAddMulChain {
3137 bool FoundConstant =
false;
3139 bool follow(
const SCEV *S) {
3144 bool isDone()
const {
3145 return FoundConstant;
3149 FindConstantInAddMulChain
F;
3151 ST.visitAll(StartExpr);
3152 return F.FoundConstant;
3160 "only nuw or nsw allowed");
3161 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3162 if (
Ops.size() == 1)
return Ops[0];
3164 Type *ETy =
Ops[0]->getType();
3166 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3168 "SCEVMulExpr operand types don't match!");
3173 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3174 [](
const APInt &
C) {
return C.isOne(); },
3175 [](
const APInt &
C) {
return C.isZero(); });
3186 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3191 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3192 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3197 if (
Ops.size() == 2) {
3205 const SCEV *Op0, *Op1;
3213 if (
Ops[0]->isAllOnesValue()) {
3218 bool AnyFolded =
false;
3219 for (
const SCEV *AddOp :
Add->operands()) {
3239 if (AddRec->hasNoSignedWrap()) {
3246 AddRec->getNoWrapFlags(FlagsMask));
3269 APInt C1V = LHSC->getAPInt();
3279 const SCEV *NewMul =
nullptr;
3283 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3298 if (Idx <
Ops.size()) {
3299 bool DeletedMul =
false;
3305 Ops.erase(
Ops.begin()+Idx);
3329 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3332 Ops.erase(
Ops.begin()+i);
3337 if (!LIOps.
empty()) {
3350 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3366 if (
Ops.size() == 1)
return NewRec;
3369 for (
unsigned i = 0;; ++i)
3370 if (
Ops[i] == AddRec) {
3391 bool OpsModified =
false;
3392 for (
unsigned OtherIdx = Idx+1;
3406 bool Overflow =
false;
3413 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3417 z < ze && !Overflow; ++z) {
3420 if (LargerThan64Bits)
3421 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3423 Coeff = Coeff1*Coeff2;
3438 if (
Ops.size() == 2)
return NewAddRec;
3439 Ops[Idx] = NewAddRec;
3440 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3456 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3463 "SCEVURemExpr operand types don't match!");
3468 if (RHSC->getValue()->isOne())
3469 return getZero(LHS->getType());
3472 if (RHSC->getAPInt().isPowerOf2()) {
3473 Type *FullTy = LHS->getType();
3489 assert(!LHS->getType()->isPointerTy() &&
3490 "SCEVUDivExpr operand can't be pointer!");
3491 assert(LHS->getType() == RHS->getType() &&
3492 "SCEVUDivExpr operand types don't match!");
3499 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
3507 if (RHSC->getValue()->isOne())
3512 if (!RHSC->getValue()->isZero()) {
3516 Type *Ty = LHS->getType();
3517 unsigned LZ = RHSC->getAPInt().countl_zero();
3521 if (!RHSC->getAPInt().isPowerOf2())
3529 const APInt &StepInt = Step->getAPInt();
3530 const APInt &DivInt = RHSC->getAPInt();
3531 if (!StepInt.
urem(DivInt) &&
3537 for (
const SCEV *
Op : AR->operands())
3543 const APInt *StartRem;
3556 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3560 const SCEV *NewStart =
3562 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3564 const SCEV *NewLHS =
3567 if (LHS != NewLHS) {
3577 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
3586 for (
const SCEV *
Op : M->operands())
3590 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3591 const SCEV *
Op = M->getOperand(i);
3618 if (
auto *DivisorConstant =
3620 bool Overflow =
false;
3622 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3633 for (
const SCEV *
Op :
A->operands())
3637 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3644 if (
Operands.size() ==
A->getNumOperands())
3656 const APInt &
N = RHSC->getAPInt();
3657 const APInt *NMinusM, *M;
3661 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3662 *NMinusM ==
N - *M) {
3671 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3681 return getZero(LHS->getType());
3685 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3686 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3687 if (
Mul->getOperand(i) == RHS) {
3698 const SCEV *NewLHS, *NewRHS;
3706 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
3709 UniqueSCEVs.InsertNode(S, IP);
3746 if (StepChrec->getLoop() == L) {
3765 "SCEVAddRecExpr operand types don't match!");
3766 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3770 "SCEVAddRecExpr operand is not available at loop entry!");
3788 const Loop *NestedLoop = NestedAR->getLoop();
3789 if (L->contains(NestedLoop)
3792 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3794 Operands[0] = NestedAR->getStart();
3798 bool AllInvariant =
all_of(
3810 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3821 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3831 return getOrCreateAddRecExpr(
Operands, L, Flags);
3847 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3851 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3865 bool FirstIter =
true;
3867 for (
SCEVUse IndexExpr : IndexExprs) {
3874 Offsets.push_back(FieldOffset);
3877 CurTy = STy->getTypeAtIndex(Index);
3882 "The first index of a GEP indexes a pointer");
3883 CurTy = SrcElementTy;
3894 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3895 Offsets.push_back(LocalOffset);
3900 if (Offsets.empty())
3913 "GEP should not change type mid-flight.");
3917SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3924 return UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
3927SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3934 return UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
3944 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3945 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3946 if (
Ops.size() == 1)
return Ops[0];
3949 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3951 "Operand types don't match!");
3954 "min/max should be consistently pointerish");
3980 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3982 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3987 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3989 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3995 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
4001 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
4006 if (Idx <
Ops.size()) {
4007 bool DeletedAny =
false;
4008 while (
Ops[Idx]->getSCEVType() == Kind) {
4010 Ops.erase(
Ops.begin()+Idx);
4028 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
4029 if (
Ops[i] ==
Ops[i + 1] ||
4030 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
4033 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
4036 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
4039 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
4045 if (
Ops.size() == 1)
return Ops[0];
4047 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
4056 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
4058 return ExistingSCEV;
4061 SCEV *S =
new (SCEVAllocator)
4064 UniqueSCEVs.InsertNode(S, IP);
4072class SCEVSequentialMinMaxDeduplicatingVisitor final
4073 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4074 std::optional<const SCEV *>> {
4075 using RetVal = std::optional<const SCEV *>;
4083 bool canRecurseInto(
SCEVTypes Kind)
const {
4086 return RootKind == Kind || NonSequentialRootKind == Kind;
4089 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
4091 "Only for min/max expressions.");
4094 if (!canRecurseInto(Kind))
4104 return std::nullopt;
4111 RetVal
visit(
const SCEV *S) {
4113 if (!SeenOps.
insert(S).second)
4114 return std::nullopt;
4115 return Base::visit(S);
4119 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4121 : SE(SE), RootKind(RootKind),
4122 NonSequentialRootKind(
4123 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4127 SmallVectorImpl<SCEVUse> &NewOps) {
4132 for (
const SCEV *
Op : OrigOps) {
4137 Ops.emplace_back(*NewOp);
4141 NewOps = std::move(
Ops);
4145 RetVal visitConstant(
const SCEVConstant *Constant) {
return Constant; }
4147 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4149 RetVal visitPtrToAddrExpr(
const SCEVPtrToAddrExpr *Expr) {
return Expr; }
4151 RetVal visitTruncateExpr(
const SCEVTruncateExpr *Expr) {
return Expr; }
4153 RetVal visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
return Expr; }
4155 RetVal visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
return Expr; }
4157 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4159 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4161 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4163 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4165 RetVal visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
4166 return visitAnyMinMaxExpr(Expr);
4169 RetVal visitUMaxExpr(
const SCEVUMaxExpr *Expr) {
4170 return visitAnyMinMaxExpr(Expr);
4173 RetVal visitSMinExpr(
const SCEVSMinExpr *Expr) {
4174 return visitAnyMinMaxExpr(Expr);
4177 RetVal visitUMinExpr(
const SCEVUMinExpr *Expr) {
4178 return visitAnyMinMaxExpr(Expr);
4181 RetVal visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *Expr) {
4182 return visitAnyMinMaxExpr(Expr);
4185 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4187 RetVal visitCouldNotCompute(
const SCEVCouldNotCompute *Expr) {
return Expr; }
4229struct SCEVPoisonCollector {
4230 bool LookThroughMaybePoisonBlocking;
4231 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4232 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4233 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4235 bool follow(
const SCEV *S) {
4236 if (!LookThroughMaybePoisonBlocking &&
4246 bool isDone()
const {
return false; }
4256 SCEVPoisonCollector PC1(
true);
4261 if (PC1.MaybePoison.empty())
4267 SCEVPoisonCollector PC2(
false);
4277 SCEVPoisonCollector PC(
false);
4300 while (!Worklist.
empty()) {
4302 if (!Visited.
insert(V).second)
4306 if (Visited.
size() > 16)
4322 if (PDI->isDisjoint())
4329 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4336 if (
I->hasPoisonGeneratingAnnotations())
4347 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4348 "Not a SCEVSequentialMinMaxExpr!");
4349 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4350 if (
Ops.size() == 1)
4354 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4356 "Operand types don't match!");
4359 "min/max should be consistently pointerish");
4367 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4374 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4384 bool DeletedAny =
false;
4385 while (Idx <
Ops.size()) {
4386 if (
Ops[Idx]->getSCEVType() != Kind) {
4391 Ops.erase(
Ops.begin() + Idx);
4392 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4393 SMME->operands().end());
4401 const SCEV *SaturationPoint;
4412 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4413 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4425 Ops.erase(
Ops.begin() + i);
4430 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4431 Ops.erase(
Ops.begin() + i);
4443 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
4445 return ExistingSCEV;
4449 SCEV *S =
new (SCEVAllocator)
4452 UniqueSCEVs.InsertNode(S, IP);
4500 if (
Size.isScalable())
4521 "Cannot get offset for structure containing scalable vector types");
4535 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) {
4537 "Stale SCEVUnknown in uniquing map!");
4540 SCEV *S =
new (SCEVAllocator)
SCEVUnknown(ID.Intern(SCEVAllocator), V,
this,
4543 UniqueSCEVs.InsertNode(S, IP);
4558 return Ty->isIntOrPtrTy();
4565 if (Ty->isPointerTy())
4576 if (Ty->isIntegerTy())
4580 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4592 bool PreciseA, PreciseB;
4593 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4594 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4595 if (!PreciseA || !PreciseB)
4598 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4599 DT.dominates(ScopeB, ScopeA);
4603 return CouldNotCompute.get();
4606bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4609 return SU && SU->getValue() ==
nullptr;
4612 return !ContainsNulls;
4617 if (
I != HasRecMap.end())
4622 HasRecMap.insert({S, FoundAddRec});
4630 if (
SI == ExprValueMap.
end())
4632 return SI->second.getArrayRef();
4638void ScalarEvolution::eraseValueFromMap(
Value *V) {
4640 if (
I != ValueExprMap.end()) {
4641 auto EVIt = ExprValueMap.find(
I->second);
4642 bool Removed = EVIt->second.remove(V);
4644 assert(Removed &&
"Value not in ExprValueMap?");
4645 ValueExprMap.erase(
I);
4649void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4653 auto It = ValueExprMap.find_as(V);
4654 if (It == ValueExprMap.end()) {
4656 ExprValueMap[S].insert(V);
4667 return createSCEVIter(V);
4674 if (
I != ValueExprMap.end()) {
4675 const SCEV *S =
I->second;
4676 assert(checkValidity(S) &&
4677 "existing SCEV has not been properly invalidated");
4690 Type *Ty = V->getType();
4706 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4719 return (
const SCEV *)
nullptr;
4725 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4729 Type *Ty = V->getType();
4735 assert(
P->getType()->isPointerTy());
4750 if (AddOp->getType()->isPointerTy()) {
4751 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4769 return getZero(LHS->getType());
4774 if (RHS->getType()->isPointerTy()) {
4775 if (!LHS->getType()->isPointerTy() ||
4785 const bool RHSIsNotMinSigned =
4816 Type *SrcTy = V->getType();
4817 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4818 "Cannot truncate or zero extend with non-integer arguments!");
4828 Type *SrcTy = V->getType();
4829 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4830 "Cannot truncate or zero extend with non-integer arguments!");
4840 Type *SrcTy = V->getType();
4841 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4842 "Cannot noop or zero extend with non-integer arguments!");
4844 "getNoopOrZeroExtend cannot truncate!");
4852 Type *SrcTy = V->getType();
4853 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4854 "Cannot noop or sign extend with non-integer arguments!");
4856 "getNoopOrSignExtend cannot truncate!");
4864 Type *SrcTy = V->getType();
4865 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4866 "Cannot noop or any extend with non-integer arguments!");
4868 "getNoopOrAnyExtend cannot truncate!");
4876 Type *SrcTy = V->getType();
4877 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4878 "Cannot truncate or noop with non-integer arguments!");
4880 "getTruncateOrNoop cannot extend!");
4888 const SCEV *PromotedLHS = LHS;
4889 const SCEV *PromotedRHS = RHS;
4909 assert(!
Ops.empty() &&
"At least one operand must be!");
4911 if (
Ops.size() == 1)
4915 Type *MaxType =
nullptr;
4921 assert(MaxType &&
"Failed to find maximum type!");
4934 if (!V->getType()->isPointerTy())
4939 V = AddRec->getStart();
4941 const SCEV *PtrOp =
nullptr;
4942 for (
const SCEV *AddOp :
Add->operands()) {
4943 if (AddOp->getType()->isPointerTy()) {
4944 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4948 assert(PtrOp &&
"Must have pointer op");
4960 for (
User *U :
I->users()) {
4962 if (Visited.
insert(UserInsn).second)
4976 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4977 bool IgnoreOtherLoops =
true) {
4980 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4982 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4987 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4989 SeenLoopVariantSCEVUnknown =
true;
4993 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4997 SeenOtherLoops =
true;
5001 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
5003 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
5006 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
5007 : SCEVRewriteVisitor(SE),
L(
L) {}
5010 bool SeenLoopVariantSCEVUnknown =
false;
5011 bool SeenOtherLoops =
false;
5020 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
5021 SCEVPostIncRewriter
Rewriter(L, SE);
5023 return Rewriter.hasSeenLoopVariantSCEVUnknown()
5028 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5030 SeenLoopVariantSCEVUnknown =
true;
5034 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5038 SeenOtherLoops =
true;
5042 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
5044 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
5047 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
5048 : SCEVRewriteVisitor(SE),
L(
L) {}
5051 bool SeenLoopVariantSCEVUnknown =
false;
5052 bool SeenOtherLoops =
false;
5058class SCEVBackedgeConditionFolder
5061 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5062 ScalarEvolution &SE) {
5063 bool IsPosBECond =
false;
5064 Value *BECond =
nullptr;
5065 if (BasicBlock *Latch =
L->getLoopLatch()) {
5067 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
5068 "Both outgoing branches should not target same header!");
5069 BECond = BI->getCondition();
5070 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
5075 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
5079 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5080 const SCEV *
Result = Expr;
5085 switch (
I->getOpcode()) {
5086 case Instruction::Select: {
5088 std::optional<const SCEV *> Res =
5089 compareWithBackedgeCondition(
SI->getCondition());
5097 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5108 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5109 bool IsPosBECond, ScalarEvolution &SE)
5110 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5111 IsPositiveBECond(IsPosBECond) {}
5113 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5117 Value *BackedgeCond =
nullptr;
5119 bool IsPositiveBECond;
5122std::optional<const SCEV *>
5123SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5128 if (BackedgeCond == IC)
5131 return std::nullopt;
5136 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5137 ScalarEvolution &SE) {
5143 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5150 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5160 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5161 : SCEVRewriteVisitor(SE),
L(
L) {}
5169void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5185 const APInt &BECountAP = BECountMax->getAPInt();
5186 unsigned NoOverflowBitWidth =
5195ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5205 if (!SignedWrapViaInductionTried.insert(AR).second)
5230 AC.assumptions().empty())
5238 const SCEV *OverflowLimit =
5240 if (OverflowLimit &&
5248ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5258 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5284 AC.assumptions().empty())
5323 IsNSW = OBO->hasNoSignedWrap();
5324 IsNUW = OBO->hasNoUnsignedWrap();
5330 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5342 return std::nullopt;
5348 switch (
Op->getOpcode()) {
5349 case Instruction::Add:
5350 case Instruction::Sub:
5351 case Instruction::Mul:
5352 case Instruction::UDiv:
5353 case Instruction::URem:
5354 case Instruction::And:
5355 case Instruction::AShr:
5356 case Instruction::Shl:
5359 case Instruction::Or: {
5362 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5372 case Instruction::Xor:
5376 if (RHSC->getValue().isSignMask())
5377 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5379 if (V->getType()->isIntegerTy(1))
5380 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5383 case Instruction::LShr:
5392 if (SA->getValue().ult(
BitWidth)) {
5394 ConstantInt::get(SA->getContext(),
5396 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5401 case Instruction::ExtractValue: {
5403 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5411 bool Signed = WO->isSigned();
5414 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5419 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5430 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5431 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5433 return std::nullopt;
5459 if (
Op == SymbolicPHI)
5464 if (SourceBits != NewBits)
5482 if (!L || L->getHeader() != PN->
getParent())
5540std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5541ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5549 assert(L &&
"Expecting an integer loop header phi");
5554 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5555 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5556 Value *
V = PN->getIncomingValue(i);
5557 if (
L->contains(PN->getIncomingBlock(i))) {
5560 }
else if (BEValueV != V) {
5564 }
else if (!StartValueV) {
5566 }
else if (StartValueV != V) {
5567 StartValueV =
nullptr;
5571 if (!BEValueV || !StartValueV)
5572 return std::nullopt;
5574 const SCEV *BEValue =
getSCEV(BEValueV);
5581 return std::nullopt;
5585 unsigned FoundIndex =
Add->getNumOperands();
5586 Type *TruncTy =
nullptr;
5588 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5591 if (FoundIndex == e) {
5596 if (FoundIndex ==
Add->getNumOperands())
5597 return std::nullopt;
5601 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5602 if (i != FoundIndex)
5603 Ops.push_back(
Add->getOperand(i));
5609 return std::nullopt;
5662 const SCEV *StartVal =
getSCEV(StartValueV);
5663 const SCEV *PHISCEV =
5690 auto getExtendedExpr = [&](
const SCEV *Expr,
5691 bool CreateSignExtend) ->
const SCEV * {
5694 const SCEV *ExtendedExpr =
5697 return ExtendedExpr;
5705 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5706 const SCEV *ExtendedExpr) ->
bool {
5707 return Expr != ExtendedExpr &&
5711 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5712 if (PredIsKnownFalse(StartVal, StartExtended)) {
5714 return std::nullopt;
5719 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5720 if (PredIsKnownFalse(Accum, AccumExtended)) {
5722 return std::nullopt;
5725 auto AppendPredicate = [&](
const SCEV *Expr,
5726 const SCEV *ExtendedExpr) ->
void {
5727 if (Expr != ExtendedExpr &&
5735 AppendPredicate(StartVal, StartExtended);
5736 AppendPredicate(Accum, AccumExtended);
5744 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5745 std::make_pair(NewAR, Predicates);
5747 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5751std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5756 return std::nullopt;
5759 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5760 if (
I != PredicatedSCEVRewrites.end()) {
5761 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5764 if (Rewrite.first == SymbolicPHI)
5765 return std::nullopt;
5769 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5773 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5774 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5779 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5780 return std::nullopt;
5800 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5801 if (Expr1 != Expr2 &&
5802 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5803 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5820const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5822 Value *StartValueV) {
5825 assert(BEValueV && StartValueV);
5831 if (BO->Opcode != Instruction::Add)
5834 const SCEV *Accum =
nullptr;
5835 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5837 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5851 insertValueToMap(PN, PHISCEV);
5854 inferNoWrapViaConstantRanges(AR);
5861 "Accum is defined outside L, but is not invariant?");
5862 if (isAddRecNeverPoison(BEInst, L))
5869const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5870 const Loop *
L = LI.getLoopFor(PN->
getParent());
5877 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5883 }
else if (BEValueV != V) {
5887 }
else if (!StartValueV) {
5889 }
else if (StartValueV != V) {
5890 StartValueV =
nullptr;
5894 if (!BEValueV || !StartValueV)
5897 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5898 "PHI node already processed?");
5902 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5907 insertValueToMap(PN, SymbolicName);
5911 const SCEV *BEValue =
getSCEV(BEValueV);
5921 unsigned FoundIndex =
Add->getNumOperands();
5922 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5923 if (
Add->getOperand(i) == SymbolicName)
5924 if (FoundIndex == e) {
5929 if (FoundIndex !=
Add->getNumOperands()) {
5932 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5933 if (i != FoundIndex)
5934 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5946 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5953 if (
GEP->getOperand(0) == PN) {
5954 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
5972 const SCEV *StartVal =
getSCEV(StartValueV);
5973 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5978 forgetMemoizedResults({SymbolicName});
5979 insertValueToMap(PN, PHISCEV);
5982 inferNoWrapViaConstantRanges(AR);
6006 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
6007 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
6009 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
6010 const SCEV *StartVal =
getSCEV(StartValueV);
6011 if (Start == StartVal) {
6015 forgetMemoizedResults({SymbolicName});
6016 insertValueToMap(PN, Shifted);
6026 eraseValueFromMap(PN);
6041 Use &LeftUse =
Merge->getOperandUse(0);
6042 Use &RightUse =
Merge->getOperandUse(1);
6078 assert(IDom &&
"At least the entry block should dominate PN");
6086const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
6091 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6108 CommonInst = IncomingInst;
6124ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6130 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6131 bool SCEVExprsIdentical =
6133 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6134 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6137const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6138 if (
const SCEV *S = createAddRecFromPHI(PN))
6148 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6151 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6160 struct FindClosure {
6161 const SCEV *OperandToFind;
6167 bool canRecurseInto(
SCEVTypes Kind)
const {
6170 return RootKind == Kind || NonSequentialRootKind == Kind ||
6175 : OperandToFind(OperandToFind), RootKind(RootKind),
6176 NonSequentialRootKind(
6180 bool follow(
const SCEV *S) {
6181 Found = S == OperandToFind;
6183 return !isDone() && canRecurseInto(S->
getSCEVType());
6186 bool isDone()
const {
return Found; }
6189 FindClosure FC(OperandToFind, RootKind);
6194std::optional<const SCEV *>
6195ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6205 switch (ICI->getPredicate()) {
6219 bool Signed = ICI->isSigned();
6220 const SCEV *LA =
getSCEV(TrueVal);
6228 if (LA == LS &&
RA == RS)
6230 if (LA == RS &&
RA == LS)
6233 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6234 if (
Op->getType()->isPointerTy()) {
6245 LS = CoerceOperand(LS);
6246 RS = CoerceOperand(RS);
6270 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6271 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6285 X = ZExt->getOperand();
6287 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6298 return std::nullopt;
6301static std::optional<const SCEV *>
6303 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6307 "Unexpected operands of a select.");
6319 return std::nullopt;
6334static std::optional<const SCEV *>
6338 return std::nullopt;
6341 const auto *SETrue = SE->
getSCEV(TrueVal);
6342 const auto *SEFalse = SE->
getSCEV(FalseVal);
6346const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6348 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6350 V->getType() ==
TrueVal->getType() &&
6351 "Types of select hands and of the result must match.");
6354 if (!
V->getType()->isIntegerTy(1))
6357 if (std::optional<const SCEV *> S =
6370 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6374 if (std::optional<const SCEV *> S =
6375 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6381 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6387 assert(
GEP->getSourceElementType()->isSized() &&
6388 "GEP source element type must be sized");
6391 for (
Value *Index :
GEP->indices())
6396APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6399 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6402 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6404 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6407 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6425 return GetShiftedByZeros(TZ);
6435 return GetShiftedByZeros(TZ);
6439 if (
M->hasNoUnsignedWrap()) {
6442 for (
const SCEV *Operand :
M->operands().drop_front())
6450 for (
const SCEV *Operand :
M->operands())
6452 return GetShiftedByZeros(TZ);
6457 if (
N->hasNoUnsignedWrap())
6458 return GetGCDMultiple(
N);
6461 for (
const SCEV *Operand :
N->operands().drop_front())
6463 return GetShiftedByZeros(TZ);
6480 CtxI = &*F.getEntryBlock().begin();
6487 .allowEphemerals(
true))
6488 .countMinTrailingZeros();
6489 return GetShiftedByZeros(
Known);
6502 return getConstantMultipleImpl(S, CtxI);
6504 auto I = ConstantMultipleCache.find(S);
6505 if (
I != ConstantMultipleCache.end())
6508 APInt Result = getConstantMultipleImpl(S, CtxI);
6509 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6510 assert(InsertPair.second &&
"Should insert a new key");
6511 return InsertPair.first->second;
6528 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6531 if (std::optional<ConstantRange>
Range = CB->getRange())
6535 if (std::optional<ConstantRange>
Range =
A->getRange())
6538 return std::nullopt;
6545 UnsignedRanges.erase(AddRec);
6546 SignedRanges.erase(AddRec);
6547 ConstantMultipleCache.erase(AddRec);
6552getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6578 Value *Start, *Step;
6585 assert(L && L->getHeader() ==
P->getParent());
6598 case Instruction::AShr:
6599 case Instruction::LShr:
6600 case Instruction::Shl:
6615 KnownStep.getBitWidth() ==
BitWidth);
6618 auto MaxShiftAmt = KnownStep.getMaxValue();
6620 bool Overflow =
false;
6621 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6628 case Instruction::AShr: {
6636 if (KnownStart.isNonNegative())
6639 KnownStart.getMaxValue() + 1);
6640 if (KnownStart.isNegative())
6643 KnownEnd.getMaxValue() + 1);
6646 case Instruction::LShr: {
6655 KnownStart.getMaxValue() + 1);
6657 case Instruction::Shl: {
6661 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6662 return ConstantRange(KnownStart.getMinValue(),
6663 KnownEnd.getMaxValue() + 1);
6688 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6695ScalarEvolution::getRangeRefIter(
const SCEV *S,
6696 ScalarEvolution::RangeSignHint SignHint) {
6697 DenseMap<const SCEV *, ConstantRange> &Cache =
6698 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6701 SmallPtrSet<const SCEV *, 8> Seen;
6705 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6706 if (!Seen.
insert(Expr).second)
6739 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6740 const SCEV *
P = WorkList[
I];
6744 for (
const SCEV *
Op :
P->operands())
6757 if (!WorkList.
empty()) {
6762 getRangeRef(
P, SignHint);
6766 return getRangeRef(S, SignHint, 0);
6773 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6774 DenseMap<const SCEV *, ConstantRange> &Cache =
6775 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6782 auto I = Cache.
find(S);
6783 if (
I != Cache.
end())
6787 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6792 return getRangeRefIter(S, SignHint);
6795 ConstantRange ConservativeResult(
BitWidth,
true);
6796 using OBO = OverflowingBinaryOperator;
6800 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6804 ConservativeResult =
6811 ConservativeResult = ConstantRange(
6827 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6834 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6841 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6846 return setRange(Cast, SignHint,
X);
6851 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6852 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6854 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6855 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6856 ConservativeResult =
6857 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6859 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6860 unsigned WrapType = OBO::AnyWrap;
6861 if (
Add->hasNoSignedWrap())
6862 WrapType |= OBO::NoSignedWrap;
6863 if (
Add->hasNoUnsignedWrap())
6864 WrapType |= OBO::NoUnsignedWrap;
6866 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6868 return setRange(
Add, SignHint,
6869 ConservativeResult.intersectWith(
X, RangeType));
6873 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6875 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6876 return setRange(
Mul, SignHint,
6877 ConservativeResult.intersectWith(
X, RangeType));
6881 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6882 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6883 return setRange(UDiv, SignHint,
6884 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6892 if (!UnsignedMinValue.
isZero())
6893 ConservativeResult = ConservativeResult.intersectWith(
6894 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6903 bool AllNonNeg =
true;
6904 bool AllNonPos =
true;
6905 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6912 ConservativeResult = ConservativeResult.intersectWith(
6917 ConservativeResult = ConservativeResult.intersectWith(
6926 const SCEV *MaxBEScev =
6940 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6942 ConservativeResult =
6943 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6946 auto RangeFromFactoring = getRangeViaFactoring(
6948 ConservativeResult =
6949 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6955 const SCEV *SymbolicMaxBECount =
6960 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6961 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6962 ConservativeResult =
6963 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6968 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6978 ID = Intrinsic::umax;
6981 ID = Intrinsic::smax;
6985 ID = Intrinsic::umin;
6988 ID = Intrinsic::smin;
6995 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6996 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6998 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6999 return setRange(S, SignHint,
7000 ConservativeResult.intersectWith(
X, RangeType));
7009 ConservativeResult =
7010 ConservativeResult.intersectWith(*MDRange, RangeType);
7015 auto CR = getRangeForUnknownRecurrence(U);
7016 ConservativeResult = ConservativeResult.intersectWith(CR);
7027 if (
U->getType()->isPointerTy()) {
7030 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
7031 int ptrIdxDiff = ptrSize -
BitWidth;
7032 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
7038 if (!
Known.Zero.getHiBits(NS).isZero())
7039 Known.Zero.setHighBits(NS);
7040 if (!
Known.One.getHiBits(NS).isZero())
7041 Known.One.setHighBits(NS);
7044 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
7045 ConservativeResult = ConservativeResult.intersectWith(
7046 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
7049 ConservativeResult = ConservativeResult.intersectWith(
7054 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
7058 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
7059 DL, CanBeNull,
nullptr);
7069 uint64_t
Align =
U->getValue()->getPointerAlignment(DL).value();
7070 uint64_t Rem = MaxVal.
urem(Align);
7075 ConservativeResult = ConservativeResult.intersectWith(
7085 return getRangeRef(AR, SignHint,
Depth + 1);
7089 ConstantRange RangeFromOps(
BitWidth,
false);
7091 for (
const auto &
Op :
Phi->operands()) {
7093 RangeFromOps = RangeFromOps.unionWith(OpRange);
7095 if (RangeFromOps.isFullSet())
7098 ConservativeResult =
7099 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7105 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7107 ConservativeResult = ConservativeResult.difference(Disallowed);
7110 return setRange(U, SignHint, std::move(ConservativeResult));
7116 return setRange(S, SignHint, std::move(ConservativeResult));
7124static std::pair<ConstantRange, bool>
7132 if (Step == 0 || MaxBECount == 0)
7133 return {StartRange,
true};
7139 return {ConstantRange::getFull(
BitWidth),
false};
7155 return {ConstantRange::getFull(
BitWidth),
false};
7168 APInt MovedBoundary;
7173 MovedBoundary = StartLower - std::move(
Offset);
7176 MovedBoundary = StartUpper + std::move(
Offset);
7180 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7187 if (StartRange.
contains(MovedBoundary))
7188 return {ConstantRange::getFull(
BitWidth),
false};
7191 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7193 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7201std::pair<ConstantRange, SCEV::NoWrapFlags>
7202ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7203 const APInt &MaxBECount) {
7207 "mismatched bit widths");
7216 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7218 StartSRange, MaxBECount,
7220 ConstantRange SR = SR1.unionWith(SR2);
7237ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7239 ScalarEvolution::RangeSignHint SignHint) {
7240 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7242 "This only works for non-self-wrapping AddRecs!");
7243 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7247 return ConstantRange::getFull(
BitWidth);
7255 return ConstantRange::getFull(
BitWidth);
7259 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7261 MaxItersWithoutWrap))
7262 return ConstantRange::getFull(
BitWidth);
7283 ConstantRange StartRange = getRangeRef(Start, SignHint);
7284 ConstantRange EndRange = getRangeRef(End, SignHint);
7285 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7289 return RangeBetween;
7294 return ConstantRange::getFull(
BitWidth);
7297 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7298 return RangeBetween;
7300 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7301 return RangeBetween;
7302 return ConstantRange::getFull(
BitWidth);
7307 const APInt &MaxBECount) {
7314 "mismatched bit widths");
7316 struct SelectPattern {
7317 Value *Condition =
nullptr;
7321 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7323 std::optional<unsigned> CastOp;
7337 CastOp = SCast->getSCEVType();
7338 S = SCast->getOperand();
7341 using namespace llvm::PatternMatch;
7348 Condition =
nullptr;
7380 bool isRecognized() {
return Condition !=
nullptr; }
7383 SelectPattern StartPattern(*
this,
BitWidth, Start);
7384 if (!StartPattern.isRecognized())
7385 return ConstantRange::getFull(
BitWidth);
7387 SelectPattern StepPattern(*
this,
BitWidth, Step);
7388 if (!StepPattern.isRecognized())
7389 return ConstantRange::getFull(
BitWidth);
7391 if (StartPattern.Condition != StepPattern.Condition) {
7395 return ConstantRange::getFull(
BitWidth);
7406 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7407 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7408 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7409 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7411 ConstantRange TrueRange =
7412 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7413 ConstantRange FalseRange =
7414 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7426 PDI && PDI->isDisjoint()) {
7441ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7454 SmallPtrSet<const SCEV *, 16> Visited;
7456 auto pushOp = [&](
const SCEV *S) {
7457 if (!Visited.
insert(S).second)
7460 if (Visited.
size() > 30) {
7471 while (!Worklist.
empty()) {
7473 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7474 if (!Bound || DT.dominates(Bound, DefI))
7481 return Bound ? Bound : &*F.getEntryBlock().begin();
7487 return getDefiningScopeBound(
Ops, Discard);
7490bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7492 if (
A->getParent() ==
B->getParent() &&
7497 auto *BLoop = LI.getLoopFor(
B->getParent());
7498 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7499 BLoop->getLoopPreheader() ==
A->getParent() &&
7501 A->getParent()->end()) &&
7509 SCEVPoisonCollector PC(
true);
7511 return PC.MaybePoison.empty();
7514bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7524bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7541 for (
const Use &
Op :
I->operands()) {
7547 auto *DefI = getDefiningScopeBound(SCEVOps);
7548 return isGuaranteedToTransferExecutionTo(DefI,
I);
7551bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7553 if (isSCEVExprNeverPoison(
I))
7564 auto *ExitingBB =
L->getExitingBlock();
7568 SmallPtrSet<const Value *, 16> KnownPoison;
7577 while (!Worklist.
empty()) {
7580 for (
const Use &U :
Poison->uses()) {
7583 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7587 if (KnownPoison.
insert(PoisonUser).second)
7595ScalarEvolution::LoopProperties
7596ScalarEvolution::getLoopProperties(
const Loop *L) {
7597 using LoopProperties = ScalarEvolution::LoopProperties;
7599 auto Itr = LoopPropertiesCache.find(L);
7600 if (Itr == LoopPropertiesCache.end()) {
7603 return !
SI->isSimple();
7613 return I->mayWriteToMemory();
7616 LoopProperties LP = {
true,
7619 for (
auto *BB :
L->getBlocks())
7620 for (
auto &
I : *BB) {
7622 LP.HasNoAbnormalExits =
false;
7623 if (HasSideEffects(&
I))
7624 LP.HasNoSideEffects =
false;
7625 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7629 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7630 assert(InsertPair.second &&
"We just checked!");
7631 Itr = InsertPair.first;
7644const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7650 Stack.emplace_back(V,
false);
7651 while (!Stack.empty()) {
7652 auto E = Stack.back();
7653 Value *CurV = E.getPointer();
7661 const SCEV *CreatedSCEV =
nullptr;
7664 CreatedSCEV = createSCEV(CurV);
7669 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7673 insertValueToMap(CurV, CreatedSCEV);
7676 Stack.back().setInt(
true);
7679 Stack.emplace_back(
Op,
false);
7696 if (!DT.isReachableFromEntry(
I->getParent()))
7709 switch (BO->Opcode) {
7710 case Instruction::Add:
7711 case Instruction::Mul: {
7718 Ops.push_back(BO->
Op);
7722 Ops.push_back(BO->RHS);
7726 (BO->Opcode == Instruction::Add &&
7727 (NewBO->Opcode != Instruction::Add &&
7728 NewBO->Opcode != Instruction::Sub)) ||
7729 (BO->Opcode == Instruction::Mul &&
7730 NewBO->Opcode != Instruction::Mul)) {
7731 Ops.push_back(BO->LHS);
7736 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7739 Ops.push_back(BO->LHS);
7747 case Instruction::Sub:
7748 case Instruction::UDiv:
7749 case Instruction::URem:
7751 case Instruction::AShr:
7752 case Instruction::Shl:
7753 case Instruction::Xor:
7757 case Instruction::And:
7758 case Instruction::Or:
7762 case Instruction::LShr:
7769 Ops.push_back(BO->LHS);
7770 Ops.push_back(BO->RHS);
7774 switch (
U->getOpcode()) {
7775 case Instruction::Trunc:
7776 case Instruction::ZExt:
7777 case Instruction::SExt:
7778 case Instruction::PtrToAddr:
7779 case Instruction::PtrToInt:
7780 Ops.push_back(
U->getOperand(0));
7783 case Instruction::BitCast:
7785 Ops.push_back(
U->getOperand(0));
7790 case Instruction::SDiv:
7791 case Instruction::SRem:
7792 Ops.push_back(
U->getOperand(0));
7793 Ops.push_back(
U->getOperand(1));
7796 case Instruction::GetElementPtr:
7798 "GEP source element type must be sized");
7802 case Instruction::IntToPtr:
7805 case Instruction::PHI:
7836 Ops.push_back(CondICmp->getOperand(0));
7837 Ops.push_back(CondICmp->getOperand(1));
7857 case Instruction::Select: {
7859 auto CanSimplifyToUnknown = [
this,
U]() {
7877 if (CanSimplifyToUnknown())
7884 case Instruction::Call:
7885 case Instruction::Invoke:
7892 switch (
II->getIntrinsicID()) {
7893 case Intrinsic::abs:
7894 Ops.push_back(
II->getArgOperand(0));
7896 case Intrinsic::umax:
7897 case Intrinsic::umin:
7898 case Intrinsic::smax:
7899 case Intrinsic::smin:
7900 case Intrinsic::usub_sat:
7901 case Intrinsic::uadd_sat:
7902 Ops.push_back(
II->getArgOperand(0));
7903 Ops.push_back(
II->getArgOperand(1));
7905 case Intrinsic::start_loop_iterations:
7906 case Intrinsic::annotation:
7907 case Intrinsic::ptr_annotation:
7908 Ops.push_back(
II->getArgOperand(0));
7920const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7929 if (!DT.isReachableFromEntry(
I->getParent()))
7944 switch (BO->Opcode) {
7945 case Instruction::Add: {
7971 if (BO->Opcode == Instruction::Sub)
7979 if (BO->Opcode == Instruction::Sub)
7986 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7987 NewBO->Opcode != Instruction::Sub)) {
7997 case Instruction::Mul: {
8018 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
8027 case Instruction::UDiv:
8031 case Instruction::URem:
8035 case Instruction::Sub: {
8038 Flags = getNoWrapFlagsFromUB(BO->
Op);
8043 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
8046 if (HasPtrLHS || HasPtrRHS) {
8051 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
8052 bool BothPtr) ->
const SCEV * {
8055 const SCEV *PtrSCEV =
getSCEV(PtrOp);
8065 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
8066 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
8074 case Instruction::And:
8080 if (CI->isMinusOne())
8082 const APInt &
A = CI->getValue();
8088 unsigned LZ =
A.countl_zero();
8089 unsigned TZ =
A.countr_zero();
8094 APInt EffectiveMask =
8096 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
8099 const SCEV *ShiftedLHS =
nullptr;
8103 unsigned MulZeros = OpC->getAPInt().countr_zero();
8104 unsigned GCD = std::min(MulZeros, TZ);
8109 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8131 case Instruction::Or:
8140 case Instruction::Xor:
8143 if (CI->isMinusOne())
8152 if (LBO->getOpcode() == Instruction::And &&
8153 LCI->getValue() == CI->getValue())
8154 if (
const SCEVZeroExtendExpr *Z =
8157 const SCEV *Z0 =
Z->getOperand();
8164 if (CI->getValue().isMask(Z0TySize))
8170 APInt Trunc = CI->getValue().trunc(Z0TySize);
8179 case Instruction::Shl:
8197 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8206 ConstantInt *
X = ConstantInt::get(
8212 case Instruction::AShr:
8234 const SCEV *AddTruncateExpr =
nullptr;
8235 ConstantInt *ShlAmtCI =
nullptr;
8236 const SCEV *AddConstant =
nullptr;
8238 if (L &&
L->getOpcode() == Instruction::Add) {
8246 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8253 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8261 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8266 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8271 if (AddTruncateExpr && ShlAmtCI) {
8283 const APInt &ShlAmt = ShlAmtCI->
getValue();
8287 const SCEV *CompositeExpr =
8289 if (
L->getOpcode() != Instruction::Shl)
8290 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8299 switch (
U->getOpcode()) {
8300 case Instruction::Trunc:
8303 case Instruction::ZExt:
8306 case Instruction::SExt:
8316 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8317 Type *Ty =
U->getType();
8325 case Instruction::BitCast:
8331 case Instruction::PtrToAddr: {
8338 case Instruction::PtrToInt: {
8344 const SCEV *PtrSCEV =
getSCEV(
U->getOperand(0));
8353 case Instruction::IntToPtr:
8357 case Instruction::SDiv:
8364 case Instruction::SRem:
8371 case Instruction::GetElementPtr:
8374 case Instruction::PHI:
8377 case Instruction::Select:
8378 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8381 case Instruction::Call:
8382 case Instruction::Invoke:
8387 switch (
II->getIntrinsicID()) {
8388 case Intrinsic::abs:
8392 case Intrinsic::umax:
8396 case Intrinsic::umin:
8400 case Intrinsic::smax:
8404 case Intrinsic::smin:
8408 case Intrinsic::usub_sat: {
8409 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8410 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8414 case Intrinsic::uadd_sat: {
8415 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8416 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8420 case Intrinsic::start_loop_iterations:
8421 case Intrinsic::annotation:
8422 case Intrinsic::ptr_annotation:
8426 case Intrinsic::vscale:
8446 auto *ExitCountType = ExitCount->
getType();
8447 assert(ExitCountType->isIntegerTy());
8449 1 + ExitCountType->getScalarSizeInBits());
8462 auto CanAddOneWithoutOverflow = [&]() {
8464 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8475 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8505 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8506 assert(L->isLoopExiting(ExitingBlock) &&
8507 "Exiting block must actually branch out of the loop!");
8516 const auto *MaxExitCount =
8524 L->getExitingBlocks(ExitingBlocks);
8526 std::optional<unsigned> Res;
8527 for (
auto *ExitingBB : ExitingBlocks) {
8531 Res = std::gcd(*Res, Multiple);
8533 return Res.value_or(1);
8537 const SCEV *ExitCount) {
8567 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8568 assert(L->isLoopExiting(ExitingBlock) &&
8569 "Exiting block must actually branch out of the loop!");
8579 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8581 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8583 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8593 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8596 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8599 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8607 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8614 return getBackedgeTakenInfo(L).getExact(L,
this);
8616 return getBackedgeTakenInfo(L).getConstantMax(
this);
8618 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8625 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8630 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8634 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8644 for (
PHINode &PN : Header->phis())
8645 if (Visited.
insert(&PN).second)
8649ScalarEvolution::BackedgeTakenInfo &
8650ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8651 auto &BTI = getBackedgeTakenInfo(L);
8652 if (BTI.hasFullInfo())
8655 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8658 return Pair.first->second;
8660 BackedgeTakenInfo
Result =
8661 computeBackedgeTakenCount(L,
true);
8663 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8666ScalarEvolution::BackedgeTakenInfo &
8667ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8673 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8674 BackedgeTakenCounts.try_emplace(L);
8676 return Pair.first->second;
8681 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8688 if (
Result.hasAnyInfo()) {
8691 auto LoopUsersIt = LoopUsers.find(L);
8692 if (LoopUsersIt != LoopUsers.end())
8694 forgetMemoizedResults(ToForget);
8697 for (PHINode &PN :
L->getHeader()->phis())
8698 ConstantEvolutionLoopExitValue.erase(&PN);
8706 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8715 BackedgeTakenCounts.clear();
8716 PredicatedBackedgeTakenCounts.clear();
8717 BECountUsers.clear();
8718 LoopPropertiesCache.clear();
8719 ConstantEvolutionLoopExitValue.clear();
8720 ValueExprMap.clear();
8721 ValuesAtScopes.clear();
8722 ValuesAtScopesUsers.clear();
8723 LoopDispositions.clear();
8724 BlockDispositions.clear();
8725 UnsignedRanges.clear();
8726 SignedRanges.clear();
8727 ExprValueMap.clear();
8729 ConstantMultipleCache.clear();
8730 PredicatedSCEVRewrites.clear();
8732 FoldCacheUser.clear();
8734void ScalarEvolution::visitAndClearUsers(
8738 while (!Worklist.
empty()) {
8745 if (It != ValueExprMap.
end()) {
8747 eraseValueFromMap(It->first);
8749 ConstantEvolutionLoopExitValue.erase(PN);
8763 while (!LoopWorklist.
empty()) {
8767 forgetBackedgeTakenCounts(CurrL,
false);
8768 forgetBackedgeTakenCounts(CurrL,
true);
8771 PredicatedSCEVRewrites.remove_if(
8772 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8774 auto LoopUsersItr = LoopUsers.find(CurrL);
8775 if (LoopUsersItr != LoopUsers.end())
8780 visitAndClearUsers(Worklist, Visited, ToForget);
8782 LoopPropertiesCache.erase(CurrL);
8785 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8787 forgetMemoizedResults(ToForget);
8804 visitAndClearUsers(Worklist, Visited, ToForget);
8806 forgetMemoizedResults(ToForget);
8818 struct InvalidationRootCollector {
8822 InvalidationRootCollector(
Loop *L) : L(L) {}
8824 bool follow(
const SCEV *S) {
8830 if (L->contains(AddRec->
getLoop()))
8835 bool isDone()
const {
return false; }
8838 InvalidationRootCollector
C(L);
8840 forgetMemoizedResults(
C.Roots);
8853 BlockDispositions.clear();
8854 LoopDispositions.clear();
8871 while (!Worklist.
empty()) {
8873 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8874 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8875 if (!LoopDispoRemoved && !BlockDispoRemoved)
8877 auto Users = SCEVUsers.find(Curr);
8878 if (
Users != SCEVUsers.end())
8891const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8895 if (!isComplete() || ExitNotTaken.
empty())
8906 for (
const auto &ENT : ExitNotTaken) {
8907 const SCEV *BECount = ENT.ExactNotTaken;
8910 "We should only have known counts for exiting blocks that dominate "
8913 Ops.push_back(BECount);
8918 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8919 "Predicate should be always true!");
8928const ScalarEvolution::ExitNotTakenInfo *
8929ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8930 const BasicBlock *ExitingBlock,
8931 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8932 for (
const auto &ENT : ExitNotTaken)
8933 if (ENT.ExitingBlock == ExitingBlock) {
8934 if (ENT.hasAlwaysTruePredicate())
8936 else if (Predicates) {
8946const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8948 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8949 if (!getConstantMax())
8952 for (
const auto &ENT : ExitNotTaken)
8953 if (!ENT.hasAlwaysTruePredicate()) {
8961 "No point in having a non-constant max backedge taken count!");
8962 return getConstantMax();
8965const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8967 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8975 for (
const auto &ENT : ExitNotTaken) {
8976 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8979 "We should only have known counts for exiting blocks that "
8985 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8986 "Predicate should be always true!");
8989 if (ExitCounts.
empty())
8998bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
9000 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
9001 return !ENT.hasAlwaysTruePredicate();
9003 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
9019 this->ExactNotTaken = E = ConstantMaxNotTaken;
9020 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
9025 "Exact is not allowed to be less precise than Constant Max");
9028 "Exact is not allowed to be less precise than Symbolic Max");
9031 "Symbolic Max is not allowed to be less precise than Constant Max");
9034 "No point in having a non-constant max backedge taken count!");
9036 for (
const auto PredList : PredLists)
9037 for (
const auto *
P : PredList) {
9045 "Backedge count should be int");
9048 "Max backedge count should be int");
9061ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
9063 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
9064 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
9065 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9067 ExitNotTaken.reserve(ExitCounts.
size());
9068 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
9069 std::back_inserter(ExitNotTaken),
9070 [&](
const EdgeExitInfo &EEI) {
9071 BasicBlock *ExitBB = EEI.first;
9072 const ExitLimit &EL = EEI.second;
9073 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
9074 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
9079 "No point in having a non-constant max backedge taken count!");
9083ScalarEvolution::BackedgeTakenInfo
9084ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
9085 bool AllowPredicates) {
9087 L->getExitingBlocks(ExitingBlocks);
9089 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9092 bool CouldComputeBECount =
true;
9094 const SCEV *MustExitMaxBECount =
nullptr;
9095 const SCEV *MayExitMaxBECount =
nullptr;
9096 bool MustExitMaxOrZero =
false;
9097 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9108 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9109 if (ExitIfTrue == CI->
isZero())
9113 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9115 assert((AllowPredicates || EL.Predicates.empty()) &&
9116 "Predicated exit limit when predicates are not allowed!");
9121 ++NumExitCountsComputed;
9125 CouldComputeBECount =
false;
9132 "Exact is known but symbolic isn't?");
9133 ++NumExitCountsNotComputed;
9148 DT.dominates(ExitBB, Latch)) {
9149 if (!MustExitMaxBECount) {
9150 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9151 MustExitMaxOrZero = EL.MaxOrZero;
9154 EL.ConstantMaxNotTaken);
9158 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9161 EL.ConstantMaxNotTaken);
9165 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9169 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9175 for (
const auto &Pair : ExitCounts) {
9177 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9179 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9180 {
L, AllowPredicates});
9182 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9183 MaxBECount, MaxOrZero);
9186ScalarEvolution::ExitLimit
9187ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9188 bool IsOnlyExit,
bool AllowPredicates) {
9189 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9193 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9198 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9199 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9200 "It should have one successor in loop and one exit block!");
9211 if (!
L->contains(SBB)) {
9216 assert(Exit &&
"Exiting block must have at least one exit");
9217 return computeExitLimitFromSingleExitSwitch(
9218 L, SI, Exit, IsOnlyExit);
9225 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9226 bool AllowPredicates) {
9227 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9228 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9229 ControlsOnlyExit, AllowPredicates);
9232std::optional<ScalarEvolution::ExitLimit>
9233ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9234 bool ExitIfTrue,
bool ControlsOnlyExit,
9235 bool AllowPredicates) {
9237 (void)this->ExitIfTrue;
9238 (void)this->AllowPredicates;
9240 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9241 this->AllowPredicates == AllowPredicates &&
9242 "Variance in assumed invariant key components!");
9243 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9244 if (Itr == TripCountMap.end())
9245 return std::nullopt;
9249void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9251 bool ControlsOnlyExit,
9252 bool AllowPredicates,
9254 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9255 this->AllowPredicates == AllowPredicates &&
9256 "Variance in assumed invariant key components!");
9258 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9259 assert(InsertResult.second &&
"Expected successful insertion!");
9264ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9265 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9266 bool ControlsOnlyExit,
bool AllowPredicates) {
9268 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9272 ExitLimit EL = computeExitLimitFromCondImpl(
9273 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9274 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9278ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9279 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9280 bool ControlsOnlyExit,
bool AllowPredicates) {
9282 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9283 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9284 return *LimitFromBinOp;
9290 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9291 if (EL.hasFullInfo() || !AllowPredicates)
9295 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9315 const WithOverflowInst *WO;
9330 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9331 ControlsOnlyExit, AllowPredicates);
9332 if (EL.hasAnyInfo())
9337 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9340std::optional<ScalarEvolution::ExitLimit>
9341ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9345 bool AllowPredicates) {
9354 return std::nullopt;
9358 ExitLimit EL0 = computeExitLimitFromCondCached(
9359 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9360 ExitLimit EL1 = computeExitLimitFromCondCached(
9361 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9366 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9371 if (EitherMayExit) {
9381 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9383 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9386 EL1.ConstantMaxNotTaken);
9388 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9390 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9393 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9397 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9398 BECount = EL0.ExactNotTaken;
9411 SymbolicMaxBECount =
9413 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9417ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9418 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9419 bool AllowPredicates) {
9431 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9433 if (EL.hasAnyInfo())
9436 auto *ExhaustiveCount =
9437 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9440 return ExhaustiveCount;
9442 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9445ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9447 bool ControlsOnlyExit,
bool AllowPredicates) {
9472 ConstantRange CompRange =
9490 InnerLHS = ZExt->getOperand();
9537 if (EL.hasAnyInfo())
9554 if (EL.hasAnyInfo())
return EL;
9586 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9588 if (EL.hasAnyInfo())
9604 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9606 if (EL.hasAnyInfo())
9617ScalarEvolution::ExitLimit
9618ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9620 BasicBlock *ExitingBlock,
9621 bool ControlsOnlyExit) {
9622 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9625 if (
Switch->getDefaultDest() == ExitingBlock)
9629 "Default case must not exit the loop!");
9635 if (EL.hasAnyInfo())
9647 "Evaluation of SCEV at constant didn't fold correctly?");
9651ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9661 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9668 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9670 unsigned &OutShiftAmt) {
9671 using namespace PatternMatch;
9673 ConstantInt *ShiftAmt;
9675 OutOpCode = Instruction::LShr;
9677 OutOpCode = Instruction::AShr;
9679 OutOpCode = Instruction::Shl;
9684 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9699 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9701 unsigned &ShiftAmtOut) {
9702 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9718 if (MatchPositiveShift(
LHS, V, OpC, Amt)) {
9719 PostShiftOpCode = OpC;
9725 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9728 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9734 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9741 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9747 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9759 ConstantInt *StableValue =
nullptr;
9764 case Instruction::AShr: {
9771 if (
Known.isNonNegative())
9772 StableValue = ConstantInt::get(Ty, 0);
9773 else if (
Known.isNegative())
9774 StableValue = ConstantInt::get(Ty, -1,
true);
9780 case Instruction::LShr:
9781 case Instruction::Shl:
9791 "Otherwise cannot be an operand to a branch instruction");
9793 if (
Result->isNullValue()) {
9802 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9804 const SCEV *StartSCEV =
getSCEV(StartValue);
9808 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9809 MaxBTC = std::min(MaxBTC, RangeBTC);
9813 const SCEV *UpperBound =
9830 if (
const Function *
F = CI->getCalledFunction())
9839 if (!L->contains(
I))
return false;
9844 return L->getHeader() ==
I->getParent();
9920 if (!
I)
return nullptr;
9933 std::vector<Constant*>
Operands(
I->getNumOperands());
9935 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9944 if (!
C)
return nullptr;
9966 if (IncomingVal != CurrentVal) {
9969 IncomingVal = CurrentVal;
9981ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9984 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9993 DenseMap<Instruction *, Constant *> CurrentIterVals;
9995 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10001 for (PHINode &
PHI : Header->phis()) {
10003 CurrentIterVals[&
PHI] = StartCST;
10005 if (!CurrentIterVals.
count(PN))
10006 return RetVal =
nullptr;
10012 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
10015 unsigned IterationNum = 0;
10017 for (; ; ++IterationNum) {
10018 if (IterationNum == NumIterations)
10019 return RetVal = CurrentIterVals[PN];
10023 DenseMap<Instruction *, Constant *> NextIterVals;
10028 NextIterVals[PN] = NextPHI;
10030 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
10036 for (
const auto &
I : CurrentIterVals) {
10038 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
10043 for (
const auto &
I : PHIsToCompute) {
10044 PHINode *
PHI =
I.first;
10047 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10050 if (NextPHI !=
I.second)
10051 StoppedEvolving =
false;
10056 if (StoppedEvolving)
10057 return RetVal = CurrentIterVals[PN];
10059 CurrentIterVals.swap(NextIterVals);
10063const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
10073 DenseMap<Instruction *, Constant *> CurrentIterVals;
10075 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10078 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
10080 for (PHINode &
PHI : Header->phis()) {
10082 CurrentIterVals[&
PHI] = StartCST;
10084 if (!CurrentIterVals.
count(PN))
10092 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10099 if (CondVal->getValue() == uint64_t(ExitWhen)) {
10100 ++NumBruteForceTripCountsComputed;
10105 DenseMap<Instruction *, Constant *> NextIterVals;
10111 for (
const auto &
I : CurrentIterVals) {
10113 if (!
PHI ||
PHI->getParent() != Header)
continue;
10116 for (PHINode *
PHI : PHIsToCompute) {
10118 if (NextPHI)
continue;
10120 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10123 CurrentIterVals.
swap(NextIterVals);
10136 return LS.second ? LS.second : V;
10138 Values.emplace_back(L,
nullptr);
10141 const SCEV *
C = computeSCEVAtScope(V, L);
10142 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10143 if (LS.first == L) {
10146 ValuesAtScopesUsers[
C].push_back({L, V});
10157 switch (V->getSCEVType()) {
10190 assert(!
C->getType()->isPointerTy() &&
10191 "Can only have one pointer, and it must be last");
10216const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10217 SmallVectorImpl<SCEVUse> &NewOps) {
10251const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10252 switch (
V->getSCEVType()) {
10263 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10274 for (++i; i !=
e; ++i)
10318 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10328 for (++i; i !=
e; ++i) {
10333 return getWithOperands(V, NewOps);
10348 const Loop *CurrLoop = this->LI[
I->getParent()];
10359 if (BackedgeTakenCount->
isZero()) {
10360 Value *InitValue =
nullptr;
10361 bool MultipleInitValues =
false;
10367 MultipleInitValues =
true;
10372 if (!MultipleInitValues && InitValue)
10381 unsigned InLoopPred =
10392 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10406 SmallVector<Constant *, 4>
Operands;
10408 bool MadeImprovement =
false;
10423 MadeImprovement |= OrigV != OpV;
10428 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10433 if (!MadeImprovement)
10454const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10456 return stripInjectiveFunctions(ZExt->getOperand());
10458 return stripInjectiveFunctions(SExt->getOperand());
10476 assert(
A != 0 &&
"A must be non-zero.");
10492 if (MinTZ < Mult2 && L->getLoopPredecessor())
10494 if (MinTZ < Mult2) {
10517 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10537static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10543 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10544 << *AddRec <<
'\n');
10547 if (!LC || !MC || !
NC) {
10548 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10549 return std::nullopt;
10555 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10563 N =
N.sext(NewWidth);
10564 M = M.sext(NewWidth);
10565 L = L.sext(NewWidth);
10582 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10583 <<
", multiplied by " <<
T <<
'\n');
10592 std::optional<APInt>
Y) {
10594 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10597 return XW.
slt(YW) ? *
X : *
Y;
10600 return std::nullopt;
10601 return X ? *
X : *
Y;
10618 return std::nullopt;
10619 unsigned W =
X->getBitWidth();
10639static std::optional<APInt>
10645 return std::nullopt;
10648 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10649 std::optional<APInt>
X =
10652 return std::nullopt;
10657 return std::nullopt;
10672static std::optional<APInt>
10676 "Starting value of addrec should be 0");
10677 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10678 <<
Range <<
", addrec " << *AddRec <<
'\n');
10682 "Addrec's initial value should be in range");
10688 return std::nullopt;
10698 auto SolveForBoundary =
10699 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10702 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10703 << Bound <<
" (before multiplying by " << M <<
")\n");
10706 std::optional<APInt> SO;
10709 "signed overflow\n");
10713 "unsigned overflow\n");
10714 std::optional<APInt> UO =
10717 auto LeavesRange = [&] (
const APInt &
X) {
10725 if (
Range.contains(
V1->getValue()))
10734 return {std::nullopt,
false};
10739 if (LeavesRange(*Min))
10740 return { Min,
true };
10741 std::optional<APInt> Max = Min == SO ? UO : SO;
10742 if (LeavesRange(*Max))
10743 return { Max,
true };
10746 return {std::nullopt,
true};
10753 auto SL = SolveForBoundary(
Lower);
10754 auto SU = SolveForBoundary(
Upper);
10757 if (!SL.second || !SU.second)
10758 return std::nullopt;
10801ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10803 bool ControlsOnlyExit,
10804 bool AllowPredicates) {
10815 if (
C->getValue()->isZero())
return C;
10819 const SCEVAddRecExpr *AddRec =
10822 if (!AddRec && AllowPredicates)
10828 if (!AddRec || AddRec->
getLoop() != L)
10839 return ExitLimit(R, R, R,
false, Predicates);
10897 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10923 const SCEV *
Exact =
10931 const SCEV *SymbolicMax =
10933 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10942 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10950 return ExitLimit(
E, M, S,
false, Predicates);
10953ScalarEvolution::ExitLimit
10954ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10962 if (!
C->getValue()->isZero())
10972std::pair<const BasicBlock *, const BasicBlock *>
10973ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10984 if (
const Loop *L = LI.getLoopFor(BB))
10985 return {
L->getLoopPredecessor(),
L->getHeader()};
10987 return {
nullptr, BB};
10996 if (
A ==
B)
return true;
11011 if (ComputesEqualValues(AI, BI))
11019 const SCEV *Op0, *Op1;
11038 auto TrivialCase = [&](
bool TriviallyTrue) {
11047 const SCEV *NewLHS, *NewRHS;
11071 return TrivialCase(
false);
11072 return TrivialCase(
true);
11091 RAdd->hasNoSignedWrap()) ||
11093 RAdd->hasNoUnsignedWrap())) {
11113 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
11114 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
11117 C->getAPInt().isStrictlyPositive()) ||
11141 const APInt &
RA = RC->getAPInt();
11143 bool SimplifiedByConstantRange =
false;
11148 return TrivialCase(
true);
11150 return TrivialCase(
false);
11159 Changed = SimplifiedByConstantRange =
true;
11163 if (!SimplifiedByConstantRange) {
11180 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11186 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11192 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11198 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11210 return TrivialCase(
true);
11212 return TrivialCase(
false);
11317 auto NonRecursive = [OrNegative](
const SCEV *S) {
11319 return C->getAPInt().isPowerOf2() ||
11320 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11326 if (NonRecursive(S))
11352 APInt C = Cst->getAPInt();
11353 return C.urem(M) == 0;
11361 const SCEV *SmodM =
11376 for (
auto *
A : Assumptions)
11377 if (
A->implies(
P, *
this))
11390std::pair<const SCEV *, const SCEV *>
11393 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11395 return { Start, Start };
11397 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11406 getUsedLoops(LHS, LoopsUsed);
11407 getUsedLoops(RHS, LoopsUsed);
11409 if (LoopsUsed.
empty())
11414 for (
const auto *L1 : LoopsUsed)
11415 for (
const auto *L2 : LoopsUsed)
11416 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11417 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11418 "Domination relationship is not a linear order");
11448 SplitRHS.second) &&
11460 if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
11464 return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11474 return std::nullopt;
11489 if (KnownWithoutContext)
11490 return KnownWithoutContext;
11497 return std::nullopt;
11503 const Loop *L = LHS->getLoop();
11508std::optional<ScalarEvolution::MonotonicPredicateType>
11511 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11517 auto ResultSwapped =
11520 assert(*ResultSwapped != *Result &&
11521 "monotonicity should flip as we flip the predicate");
11528std::optional<ScalarEvolution::MonotonicPredicateType>
11529ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11543 return std::nullopt;
11547 "Should be greater or less!");
11551 if (!LHS->hasNoUnsignedWrap())
11552 return std::nullopt;
11556 "Relational predicate is either signed or unsigned!");
11557 if (!
LHS->hasNoSignedWrap())
11558 return std::nullopt;
11560 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11568 return std::nullopt;
11571std::optional<ScalarEvolution::LoopInvariantPredicate>
11578 return std::nullopt;
11585 if (!ArLHS || ArLHS->
getLoop() != L)
11586 return std::nullopt;
11590 return std::nullopt;
11616 return std::nullopt;
11653 return std::nullopt;
11656std::optional<ScalarEvolution::LoopInvariantPredicate>
11661 Pred, LHS, RHS, L, CtxI, MaxIter))
11671 Pred, LHS, RHS, L, CtxI,
Op))
11673 return std::nullopt;
11676std::optional<ScalarEvolution::LoopInvariantPredicate>
11691 return std::nullopt;
11698 if (!AR || AR->
getLoop() != L)
11699 return std::nullopt;
11704 Pred = Pred.dropSameSign();
11708 return std::nullopt;
11714 if (Step != One && Step != MinusOne)
11715 return std::nullopt;
11721 return std::nullopt;
11727 return std::nullopt;
11735 if (Step == MinusOne)
11739 return std::nullopt;
11745bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11751 auto CheckRange = [&](
bool IsSigned) {
11754 return RangeLHS.
icmp(Pred, RangeRHS);
11763 if (CheckRange(
true) || CheckRange(
false))
11772bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11781 SCEVUse XNonConstOp, XConstOp;
11782 SCEVUse YNonConstOp, YConstOp;
11786 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11789 XFlagsPresent = ExpectedFlags;
11794 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11797 YFlagsPresent = ExpectedFlags;
11800 if (YNonConstOp != XNonConstOp)
11808 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11811 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11871bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11892bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11893 const SCEV *
LHS,
const SCEV *
RHS) {
11898 return any_of(*BB, [&](
const Instruction &
I) {
11899 using namespace llvm::PatternMatch;
11904 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11918 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11923 "This cannot be done on broken IR!");
11926 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11935 if (LoopContinuePredicate &&
11936 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11937 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11942 if (WalkingBEDominatingConds)
11948 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11949 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11956 const SCEV *LoopCounter =
11964 for (
auto &AssumeVH : AC.assumptions()) {
11971 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11975 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11978 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11979 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11980 assert(DTN &&
"should reach the loop header before reaching the root!");
11983 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
12001 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
12014 if (!DT.isReachableFromEntry(BB))
12018 "This cannot be done on broken IR!");
12026 const bool ProvingStrictComparison =
12028 bool ProvedNonStrictComparison =
false;
12029 bool ProvedNonEquality =
false;
12032 if (!ProvedNonStrictComparison)
12033 ProvedNonStrictComparison = Fn(NonStrictPredicate);
12034 if (!ProvedNonEquality)
12036 if (ProvedNonStrictComparison && ProvedNonEquality)
12041 if (ProvingStrictComparison) {
12043 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
12045 if (SplitAndProve(ProofFn))
12050 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
12052 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
12054 if (ProvingStrictComparison) {
12056 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
12058 if (SplitAndProve(ProofFn))
12067 const Loop *ContainingLoop = LI.getLoopFor(BB);
12069 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
12073 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
12074 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
12077 if (!BlockEntryPredicate)
12086 for (
auto &AssumeVH : AC.assumptions()) {
12090 if (!DT.dominates(CI, BB))
12093 if (ProveViaCond(CI->getArgOperand(0),
false))
12099 F.getParent(), Intrinsic::experimental_guard);
12101 for (
const auto *GU : GuardDecl->users())
12103 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12104 if (ProveViaCond(Guard->getArgOperand(0),
false))
12119 "LHS is not available at Loop Entry");
12121 "RHS is not available at Loop Entry");
12123 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12134 if (FoundCondValue ==
12138 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12142 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12145 const Value *Op0, *Op1;
12148 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12152 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12153 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12157 if (!ICI)
return false;
12161 CmpPredicate FoundPred;
12170 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12173bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12174 const SCEV *
RHS, CmpPredicate FoundPred,
12175 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12176 const Instruction *CtxI) {
12186 auto *WideType = FoundLHS->
getType();
12198 TruncFoundLHS, TruncFoundRHS, CtxI))
12224 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12228bool ScalarEvolution::isImpliedCondBalancedTypes(
12233 "Types should be balanced!");
12240 if (FoundLHS == FoundRHS)
12244 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12256 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12273 LHS, FoundLHS, FoundRHS, CtxI);
12275 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12297 assert(P1 != P2 &&
"Handled earlier!");
12301 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12305 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12308 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12309 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12310 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12315 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12326 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12327 CanonicalRHS, CanonicalFoundLHS,
12328 CanonicalFoundRHS);
12333 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12334 CanonicalRHS, CanonicalFoundLHS,
12335 CanonicalFoundRHS);
12342 const SCEVConstant *
C =
nullptr;
12343 const SCEV *
V =
nullptr;
12361 if (Min ==
C->getAPInt()) {
12366 APInt SharperMin = Min + 1;
12369 case ICmpInst::ICMP_SGE:
12370 case ICmpInst::ICMP_UGE:
12373 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12378 case ICmpInst::ICMP_SGT:
12379 case ICmpInst::ICMP_UGT:
12389 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12394 case ICmpInst::ICMP_SLE:
12395 case ICmpInst::ICMP_ULE:
12396 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12397 LHS, V, getConstant(SharperMin), CtxI))
12401 case ICmpInst::ICMP_SLT:
12402 case ICmpInst::ICMP_ULT:
12403 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12404 LHS, V, getConstant(Min), CtxI))
12418 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12422 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12425 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12441std::optional<APInt>
12448 APInt DiffMul(BW, 1);
12451 for (
unsigned I = 0;
I < 8; ++
I) {
12460 if (LAR->getLoop() != MAR->getLoop())
12461 return std::nullopt;
12465 if (!LAR->isAffine() || !MAR->isAffine())
12466 return std::nullopt;
12468 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12469 return std::nullopt;
12471 Less = LAR->getStart();
12472 More = MAR->getStart();
12477 auto MatchConstMul =
12478 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12483 return std::nullopt;
12485 if (
auto MatchedMore = MatchConstMul(More)) {
12486 if (
auto MatchedLess = MatchConstMul(
Less)) {
12487 if (MatchedMore->second == MatchedLess->second) {
12488 More = MatchedMore->first;
12489 Less = MatchedLess->first;
12490 DiffMul *= MatchedMore->second;
12501 Diff +=
C->getAPInt() * DiffMul;
12504 Diff -=
C->getAPInt() * DiffMul;
12507 Multiplicity[S] +=
Mul;
12509 auto Decompose = [&](
const SCEV *S,
int Mul) {
12516 Decompose(More, 1);
12517 Decompose(
Less, -1);
12521 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12522 for (
const auto &[S,
Mul] : Multiplicity) {
12527 return std::nullopt;
12529 }
else if (
Mul == -1) {
12531 return std::nullopt;
12534 return std::nullopt;
12538 if (NewMore == More || NewLess ==
Less)
12539 return std::nullopt;
12545 if (!More && !
Less)
12549 if (!More || !
Less)
12550 return std::nullopt;
12554 return std::nullopt;
12557bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12579 const auto *Latch = L->getLoopLatch();
12582 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12591 const auto *Latch = L->getLoopLatch();
12594 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12604bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12607 const SCEV *FoundLHS,
12608 const SCEV *FoundRHS) {
12617 if (!AddRecFoundLHS)
12624 const Loop *
L = AddRecFoundLHS->getLoop();
12625 if (L != AddRecLHS->getLoop())
12664 if (!RDiff || *LDiff != *RDiff)
12667 if (LDiff->isMinValue())
12670 APInt FoundRHSLimit;
12673 FoundRHSLimit = -(*RDiff);
12685bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12686 const SCEV *
RHS,
const SCEV *FoundLHS,
12687 const SCEV *FoundRHS,
unsigned Depth) {
12688 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12692 bool Erased = PendingMerges.erase(LPhi);
12693 assert(Erased &&
"Failed to erase LPhi!");
12697 bool Erased = PendingMerges.erase(RPhi);
12698 assert(Erased &&
"Failed to erase RPhi!");
12706 if (!PendingMerges.insert(Phi).second)
12720 if (!PendingMerges.insert(Phi).second)
12726 if (!LPhi && !RPhi)
12737 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12741 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12742 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12743 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12744 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12747 if (RPhi && RPhi->getParent() == LBB) {
12754 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12755 if (!ProvedEasily(L, R))
12766 auto *RLoop = RAR->
getLoop();
12767 auto *Predecessor = RLoop->getLoopPredecessor();
12768 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12770 if (!ProvedEasily(L1, RAR->
getStart()))
12772 auto *Latch = RLoop->getLoopLatch();
12773 assert(Latch &&
"Loop with AddRec with no latch?");
12794 if (
auto *Loop = LI.getLoopFor(LBB))
12797 if (!ProvedEasily(L,
RHS))
12804bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12807 const SCEV *FoundLHS,
12808 const SCEV *FoundRHS) {
12811 if (
RHS == FoundRHS) {
12816 if (
LHS != FoundLHS)
12823 Value *Shiftee, *ShiftValue;
12825 using namespace PatternMatch;
12826 if (
match(SUFoundRHS->getValue(),
12828 auto *ShifteeS =
getSCEV(Shiftee);
12846bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12847 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12848 const SCEV *FoundRHS) {
12880 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12888 return Diff == FoundDiff;
12891bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12893 const SCEV *FoundLHS,
12894 const SCEV *FoundRHS,
12895 const Instruction *CtxI) {
12896 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12898 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12900 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12901 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12903 isImpliedCondOperandsViaMatchingDiff(Pred,
LHS,
RHS, FoundLHS,
12905 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12909template <
typename MinMaxExprType>
12911 const SCEV *Candidate) {
12916 return is_contained(MinMaxExpr->operands(), Candidate);
12929 const SCEV *LStart, *RStart, *Step;
13002bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
13004 const SCEV *FoundLHS,
13005 const SCEV *FoundRHS,
13009 "LHS and RHS have different sizes?");
13012 "FoundLHS and FoundRHS have different sizes?");
13046 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
13048 return Ext->getOperand();
13055 auto *OrigLHS =
LHS;
13056 auto *OrigFoundLHS = FoundLHS;
13057 LHS = GetOpFromSExt(
LHS);
13058 FoundLHS = GetOpFromSExt(FoundLHS);
13061 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
13064 FoundRHS,
Depth + 1);
13077 if (!LHSAddExpr->hasNoSignedWrap())
13080 SCEVUse LL = LHSAddExpr->getOperand(0);
13081 SCEVUse LR = LHSAddExpr->getOperand(1);
13085 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
13086 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
13091 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
13097 using namespace llvm::PatternMatch;
13116 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13124 auto *DTy = Denominator->getType();
13125 auto *FRHSTy = FoundRHS->
getType();
13126 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13145 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13156 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13158 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13166 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13199bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13203 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13206 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13209bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13212 const SCEV *FoundLHS,
13213 const SCEV *FoundRHS) {
13249 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13255bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13256 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13257 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13271 ConstantRange FoundLHSRange =
13275 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13282 return LHSRange.
icmp(Pred, ConstRHS);
13285bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13298 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13306 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13309bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
13321 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
13329 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
13341const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
13342 const SCEV *Stride,
13373 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13384 :
APIntOps::umax(MaxEnd, MinStart);
13391ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13392 const Loop *L,
bool IsSigned,
13393 bool ControlsOnlyExit,
bool AllowPredicates) {
13397 bool PredicatedIV =
false;
13402 auto canProveNUW = [&]() {
13405 if (!ControlsOnlyExit)
13426 Limit = Limit.
zext(OuterBitWidth);
13438 Type *Ty = ZExt->getType();
13449 if (!
IV && AllowPredicates) {
13454 PredicatedIV =
true;
13458 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13472 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13475 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13480 if (!PositiveStride) {
13532 auto wouldZeroStrideBeUB = [&]() {
13544 if (!wouldZeroStrideBeUB()) {
13548 }
else if (!NoWrap) {
13551 if (canIVOverflowOnLT(
RHS, Stride, IsSigned))
13564 const SCEV *
Start =
IV->getStart();
13570 const SCEV *OrigStart =
Start;
13571 const SCEV *OrigRHS =
RHS;
13572 if (
Start->getType()->isPointerTy()) {
13583 const SCEV *End =
nullptr, *BECount =
nullptr,
13584 *BECountIfBackedgeTaken =
nullptr;
13587 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13588 any(RHSAddRec->getNoWrapFlags())) {
13601 const SCEV *RHSStart = RHSAddRec->getStart();
13602 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13614 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13623 BECountIfBackedgeTaken =
13628 if (BECount ==
nullptr) {
13633 const SCEV *MaxBECount = computeMaxBECountForLT(
13636 MaxBECount,
false , Predicates);
13643 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13670 const SCEV *Numerator =
13676 auto canProveRHSGreaterThanEqualStart = [&]() {
13695 auto *StartMinusOne =
13702 if (canProveRHSGreaterThanEqualStart()) {
13717 BECountIfBackedgeTaken =
13733 bool MayAddOverflow = [&] {
13779 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13793 if (!MayAddOverflow) {
13805 const SCEV *ConstantMaxBECount;
13806 bool MaxOrZero =
false;
13808 ConstantMaxBECount = BECount;
13809 }
else if (BECountIfBackedgeTaken &&
13814 ConstantMaxBECount = BECountIfBackedgeTaken;
13817 ConstantMaxBECount = computeMaxBECountForLT(
13825 const SCEV *SymbolicMaxBECount =
13827 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13831ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13832 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13833 bool ControlsOnlyExit,
bool AllowPredicates) {
13840 if (!
IV && AllowPredicates)
13847 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13851 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13864 if (!Stride->
isOne() && !NoWrap)
13865 if (canIVOverflowOnGT(
RHS, Stride, IsSigned))
13868 const SCEV *
Start =
IV->getStart();
13869 const SCEV *End =
RHS;
13880 if (
Start->getType()->isPointerTy()) {
13915 const SCEV *ConstantMaxBECount =
13922 ConstantMaxBECount = BECount;
13923 const SCEV *SymbolicMaxBECount =
13926 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13932 if (
Range.isFullSet())
13937 if (!SC->getValue()->isZero()) {
13943 return ShiftedAddRec->getNumIterationsInRange(
13944 Range.subtract(SC->getAPInt()), SE);
13975 APInt ExitVal = (End +
A).udiv(
A);
13988 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13989 "Linear scev computation is off in a bad way!");
14020 assert(!
Last->isZero() &&
"Recurrency with zero step?");
14046 Ty =
Store->getValueOperand()->getType();
14047 PtrTy =
Store->getPointerOperandType();
14049 Ty =
Load->getType();
14050 PtrTy =
Load->getPointerOperandType();
14064 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14066 SE->ConstantEvolutionLoopExitValue.erase(PN);
14067 SE->eraseValueFromMap(getValPtr());
14071void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
14072 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14082 : CallbackVH(
V), SE(se) {}
14091 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
14093 LoopDispositions(64), BlockDispositions(64) {
14105 F.getParent(), Intrinsic::experimental_guard);
14106 HasGuards = GuardDecl && !GuardDecl->use_empty();
14110 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
14111 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14112 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14113 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14114 PendingMerges(
std::
move(Arg.PendingMerges)),
14115 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14116 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14117 PredicatedBackedgeTakenCounts(
14118 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14119 BECountUsers(
std::
move(Arg.BECountUsers)),
14120 ConstantEvolutionLoopExitValue(
14121 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14122 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14123 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14124 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14125 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14126 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14127 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14128 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14129 SignedRanges(
std::
move(Arg.SignedRanges)),
14130 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14131 UniquePreds(
std::
move(Arg.UniquePreds)),
14132 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14133 ConstantSCEVs(
std::
move(Arg.ConstantSCEVs)),
14134 LoopUsers(
std::
move(Arg.LoopUsers)),
14135 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14136 FirstUnknown(Arg.FirstUnknown) {
14137 Arg.FirstUnknown =
nullptr;
14146 Tmp->~SCEVUnknown();
14148 FirstUnknown =
nullptr;
14150 ExprValueMap.clear();
14151 ValueExprMap.clear();
14153 BackedgeTakenCounts.clear();
14154 PredicatedBackedgeTakenCounts.clear();
14156 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14157 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14158 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14159 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14181 L->getHeader()->printAsOperand(OS,
false);
14185 L->getExitingBlocks(ExitingBlocks);
14186 if (ExitingBlocks.
size() != 1)
14187 OS <<
"<multiple exits> ";
14191 OS <<
"backedge-taken count is ";
14194 OS <<
"Unpredictable backedge-taken count.";
14197 if (ExitingBlocks.
size() > 1)
14198 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14199 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14207 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14210 OS <<
"\n Predicates:\n";
14211 for (
const auto *
P : Predicates)
14219 L->getHeader()->printAsOperand(OS,
false);
14224 OS <<
"constant max backedge-taken count is ";
14227 OS <<
", actual taken count either this or zero.";
14229 OS <<
"Unpredictable constant max backedge-taken count. ";
14234 L->getHeader()->printAsOperand(OS,
false);
14239 OS <<
"symbolic max backedge-taken count is ";
14242 OS <<
", actual taken count either this or zero.";
14244 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14248 if (ExitingBlocks.
size() > 1)
14249 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14250 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14260 OS <<
"\n predicated symbolic max exit count for "
14261 << ExitingBlock->
getName() <<
": ";
14263 OS <<
"\n Predicates:\n";
14264 for (
const auto *
P : Predicates)
14275 L->getHeader()->printAsOperand(OS,
false);
14278 OS <<
"Predicated backedge-taken count is ";
14281 OS <<
"Unpredictable predicated backedge-taken count.";
14283 OS <<
" Predicates:\n";
14284 for (
const auto *
P : Preds)
14289 auto *PredConstantMax =
14291 if (PredConstantMax != ConstantBTC) {
14293 L->getHeader()->printAsOperand(OS,
false);
14296 OS <<
"Predicated constant max backedge-taken count is ";
14299 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14301 OS <<
" Predicates:\n";
14302 for (
const auto *
P : Preds)
14307 auto *PredSymbolicMax =
14309 if (SymbolicBTC != PredSymbolicMax) {
14311 L->getHeader()->printAsOperand(OS,
false);
14314 OS <<
"Predicated symbolic max backedge-taken count is ";
14317 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14319 OS <<
" Predicates:\n";
14320 for (
const auto *
P : Preds)
14326 L->getHeader()->printAsOperand(OS,
false);
14353 OS <<
"Computable";
14363 OS <<
"DoesNotDominate";
14369 OS <<
"ProperlyDominates";
14386 OS <<
"Classifying expressions for: ";
14387 F.printAsOperand(OS,
false);
14402 const Loop *L = LI.getLoopFor(
I.getParent());
14417 OS <<
"\t\t" "Exits: ";
14420 OS <<
"<<Unknown>>";
14426 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14428 Iter->getHeader()->printAsOperand(OS,
false);
14436 InnerL->getHeader()->printAsOperand(OS,
false);
14447 OS <<
"Determining loop execution counts for: ";
14448 F.printAsOperand(OS,
false);
14456 auto &
Values = LoopDispositions[S];
14457 for (
auto &V :
Values) {
14458 if (V.getPointer() == L)
14463 auto &Values2 = LoopDispositions[S];
14465 if (V.getPointer() == L) {
14474ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14492 if (L->contains(AR->
getLoop()) &&
14494 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14499 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14500 " dominate the contained loop's header?");
14527 bool HasVarying =
false;
14528 bool HasUniform =
false;
14570 auto &
Values = BlockDispositions[S];
14571 for (
auto &V :
Values) {
14572 if (V.getPointer() == BB)
14577 auto &Values2 = BlockDispositions[S];
14579 if (V.getPointer() == BB) {
14588ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14617 bool Proper =
true;
14628 if (Instruction *
I =
14630 if (
I->getParent() == BB)
14632 if (DT.properlyDominates(
I->getParent(), BB))
14655void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14658 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14659 auto It = BECounts.find(L);
14660 if (It != BECounts.end()) {
14661 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14662 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14664 auto UserIt = BECountUsers.find(S);
14665 assert(UserIt != BECountUsers.end());
14670 BECounts.erase(It);
14678 while (!Worklist.
empty()) {
14680 auto Users = SCEVUsers.find(Curr);
14681 if (
Users != SCEVUsers.end())
14682 for (
const auto *User :
Users->second)
14683 if (ToForget.
insert(User).second)
14687 for (
const auto *S : ToForget)
14688 forgetMemoizedResultsImpl(S);
14690 PredicatedSCEVRewrites.remove_if(
14691 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14694void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14695 LoopDispositions.erase(S);
14696 BlockDispositions.erase(S);
14697 UnsignedRanges.erase(S);
14698 SignedRanges.erase(S);
14699 HasRecMap.erase(S);
14700 ConstantMultipleCache.erase(S);
14703 UnsignedWrapViaInductionTried.erase(AR);
14704 SignedWrapViaInductionTried.erase(AR);
14707 auto ExprIt = ExprValueMap.find(S);
14708 if (ExprIt != ExprValueMap.end()) {
14709 for (
Value *V : ExprIt->second) {
14710 auto ValueIt = ValueExprMap.find_as(V);
14711 if (ValueIt != ValueExprMap.end())
14712 ValueExprMap.erase(ValueIt);
14714 ExprValueMap.erase(ExprIt);
14717 auto ScopeIt = ValuesAtScopes.find(S);
14718 if (ScopeIt != ValuesAtScopes.end()) {
14719 for (
const auto &Pair : ScopeIt->second)
14722 std::make_pair(Pair.first, S));
14723 ValuesAtScopes.erase(ScopeIt);
14726 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14727 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14728 for (
const auto &Pair : ScopeUserIt->second)
14729 llvm::erase(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
14730 ValuesAtScopesUsers.erase(ScopeUserIt);
14733 auto BEUsersIt = BECountUsers.find(S);
14734 if (BEUsersIt != BECountUsers.end()) {
14736 auto Copy = BEUsersIt->second;
14737 for (
const auto &Pair : Copy)
14738 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14739 BECountUsers.erase(BEUsersIt);
14742 auto FoldUser = FoldCacheUser.find(S);
14743 if (FoldUser != FoldCacheUser.end())
14744 for (
auto &KV : FoldUser->second)
14745 FoldCache.erase(KV);
14746 FoldCacheUser.erase(S);
14750ScalarEvolution::getUsedLoops(
const SCEV *S,
14752 struct FindUsedLoops {
14753 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14754 : LoopsUsed(LoopsUsed) {}
14755 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14756 bool follow(
const SCEV *S) {
14762 bool isDone()
const {
return false; }
14765 FindUsedLoops
F(LoopsUsed);
14766 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14769void ScalarEvolution::getReachableBlocks(
14772 Worklist.
push_back(&F.getEntryBlock());
14773 while (!Worklist.
empty()) {
14775 if (!Reachable.
insert(BB).second)
14783 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14790 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14794 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14829 SCEVMapper SCM(SE2);
14831 SE2.getReachableBlocks(ReachableBlocks, F);
14833 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14851 while (!LoopStack.
empty()) {
14857 if (!ReachableBlocks.
contains(L->getHeader()))
14862 auto It = BackedgeTakenCounts.find(L);
14863 if (It == BackedgeTakenCounts.end())
14867 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14887 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14888 if (Delta && !Delta->
isZero()) {
14889 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14890 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14891 dbgs() <<
"New: " << *NewBECount <<
"\n";
14892 dbgs() <<
"Delta: " << *Delta <<
"\n";
14900 while (!Worklist.
empty()) {
14902 if (ValidLoops.
insert(L).second)
14903 Worklist.
append(L->begin(), L->end());
14905 for (
const auto &KV : ValueExprMap) {
14910 "AddRec references invalid loop");
14915 auto It = ExprValueMap.find(KV.second);
14916 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14917 dbgs() <<
"Value " << *KV.first
14918 <<
" is in ValueExprMap but not in ExprValueMap\n";
14923 if (!ReachableBlocks.
contains(
I->getParent()))
14925 const SCEV *OldSCEV = SCM.visit(KV.second);
14927 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14928 if (Delta && !Delta->
isZero()) {
14929 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14930 <<
"Old: " << *OldSCEV <<
"\n"
14931 <<
"New: " << *NewSCEV <<
"\n"
14932 <<
"Delta: " << *Delta <<
"\n";
14938 for (
const auto &KV : ExprValueMap) {
14939 for (
Value *V : KV.second) {
14940 const SCEV *S = ValueExprMap.lookup(V);
14942 dbgs() <<
"Value " << *V
14943 <<
" is in ExprValueMap but not in ValueExprMap\n";
14946 if (S != KV.first) {
14947 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14948 << *KV.first <<
"\n";
14955 for (
const auto &S : UniqueSCEVs) {
14960 auto It = SCEVUsers.find(
Op);
14961 if (It != SCEVUsers.end() && It->second.count(&S))
14963 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14964 <<
" is not being tracked!\n";
14970 for (
const auto &ValueAndVec : ValuesAtScopes) {
14972 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14973 const Loop *L = LoopAndValueAtScope.first;
14974 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
14976 auto It = ValuesAtScopesUsers.find(ValueAtScope);
14977 if (It != ValuesAtScopesUsers.end() &&
14980 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14981 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14987 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14988 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14989 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14990 const Loop *L = LoopAndValue.first;
14991 const SCEV *
Value = LoopAndValue.second;
14993 auto It = ValuesAtScopes.find(
Value);
14994 if (It != ValuesAtScopes.end() &&
14995 is_contained(It->second, std::make_pair(L, ValueAtScope)))
14997 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14998 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
15004 auto VerifyBECountUsers = [&](
bool Predicated) {
15006 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
15007 for (
const auto &LoopAndBEInfo : BECounts) {
15008 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
15009 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
15011 auto UserIt = BECountUsers.find(S);
15012 if (UserIt != BECountUsers.end() &&
15013 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
15015 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
15016 <<
" missing from BECountUsers\n";
15023 VerifyBECountUsers(
false);
15024 VerifyBECountUsers(
true);
15027 for (
auto &[S,
Values] : LoopDispositions) {
15028 for (
auto [
Loop, CachedDisposition] :
Values) {
15030 if (CachedDisposition != RecomputedDisposition) {
15031 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
15032 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
15033 << RecomputedDisposition <<
"\n";
15040 for (
auto &[S,
Values] : BlockDispositions) {
15041 for (
auto [BB, CachedDisposition] :
Values) {
15043 if (CachedDisposition != RecomputedDisposition) {
15044 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
15045 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
15046 <<
", actual " << RecomputedDisposition <<
"\n";
15053 for (
auto [
FoldID, Expr] : FoldCache) {
15054 auto I = FoldCacheUser.find(Expr);
15055 if (
I == FoldCacheUser.end()) {
15056 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
15061 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
15065 for (
auto [Expr, IDs] : FoldCacheUser) {
15066 for (
auto &
FoldID : IDs) {
15069 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
15074 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
15075 <<
" != " << *Expr <<
"!\n";
15086 for (
auto [S, Multiple] : ConstantMultipleCache) {
15088 if ((Multiple != 0 && RecomputedMultiple != 0 &&
15089 Multiple.
urem(RecomputedMultiple) != 0 &&
15090 RecomputedMultiple.
urem(Multiple) != 0)) {
15091 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
15092 << *S <<
" : Computed " << RecomputedMultiple
15093 <<
" but cache contains " << Multiple <<
"!\n";
15101 FunctionAnalysisManager::Invalidator &Inv) {
15133 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15134 <<
F.getName() <<
"':\n";
15140 "Scalar Evolution Analysis",
false,
true)
15189 const SCEV *LHS,
const SCEV *RHS) {
15191 assert(LHS->getType() == RHS->getType() &&
15192 "Type mismatch between LHS and RHS");
15195 ID.AddInteger(Pred);
15196 ID.AddPointer(LHS);
15197 ID.AddPointer(RHS);
15198 void *IP =
nullptr;
15199 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(ID, IP))
15203 UniquePreds.InsertNode(Eq, IP);
15214 ID.AddInteger(AddedFlags);
15215 void *IP =
nullptr;
15216 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(ID, IP))
15218 auto *OF =
new (SCEVAllocator)
15220 UniquePreds.InsertNode(OF, IP);
15240 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15241 return Rewriter.visit(S);
15247 for (
const auto *Pred : U->getPredicates())
15249 if (IPred->getLHS() == Expr &&
15251 return IPred->getRHS();
15253 if (IPred->getLHS() == Expr &&
15254 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15255 return IPred->getRHS();
15258 return convertToAddRecWithPreds(Expr);
15261 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15277 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15294 explicit SCEVPredicateRewriter(
15295 const Loop *L, ScalarEvolution &SE,
15296 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15297 const SCEVPredicate *Pred)
15298 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15300 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15303 return Pred && Pred->
implies(
P, SE);
15309 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15312 return addOverflowAssumption(
A);
15321 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15325 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15327 if (!PredicatedRewrite)
15329 for (
const auto *
P : PredicatedRewrite->second){
15332 if (L != WP->getExpr()->getLoop())
15335 if (!addOverflowAssumption(
P))
15338 return PredicatedRewrite->first;
15341 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15342 const SCEVPredicate *Pred;
15351 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15358 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15378 if (!Step->
isOne())
15403 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15404 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15417 return Op->LHS == LHS &&
Op->RHS == RHS;
15424 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15426 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15451 const SCEV *Start = AR->getStart();
15452 const SCEV *OpStart =
Op->AR->getStart();
15457 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15466 const SCEV *Step = AR->getStepRecurrence(SE);
15467 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15520 if (Step->getValue()->getValue().isNonNegative())
15524 return ImpliedFlags;
15531 for (
const auto *
P : Preds)
15544 return this->implies(I, SE);
15556 const Loop *L = NWrap->getExpr()->getLoop();
15563 return RewrittenAR &&
15569 for (
const auto *Pred : Preds)
15570 Pred->print(OS,
Depth);
15575 for (
const auto *Pred : Set->Preds)
15583 bool CheckImplies = Preds.
size() < 16;
15586 if (CheckImplies &&
implies(
N, SE))
15592 for (
auto *
P : Preds) {
15593 if (CheckImplies &&
N->implies(
P, SE))
15597 Preds = std::move(PrunedPreds);
15598 Preds.push_back(
N);
15605 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15610 for (
const auto *
Op :
Ops)
15615 SCEVUsers[
Op].insert(
User);
15624 SCEVUsers[
Op].insert(
User);
15628 const SCEV *Expr = SE.getSCEV(V);
15633 RewriteEntry &Entry = RewriteMap[Expr];
15636 if (Entry.second && Generation == Entry.first)
15637 return Entry.second;
15642 Expr = Entry.second;
15644 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15645 Entry = {Generation, NewSCEV};
15651 if (!BackedgeCount) {
15653 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15654 for (
const auto *
P : Preds)
15657 return BackedgeCount;
15661 if (!SymbolicMaxBackedgeCount) {
15663 SymbolicMaxBackedgeCount =
15664 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15665 for (
const auto *
P : Preds)
15668 return SymbolicMaxBackedgeCount;
15672 if (!SmallConstantMaxTripCount) {
15674 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15675 for (
const auto *
P : Preds)
15678 return *SmallConstantMaxTripCount;
15682 if (Preds->implies(&Pred, SE))
15687 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15688 updateGeneration();
15701void PredicatedScalarEvolution::updateGeneration() {
15703 if (++Generation == 0) {
15704 for (
auto &
II : RewriteMap) {
15705 const SCEV *Rewritten =
II.second.second;
15727 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15733 ExtraPreds->
append(NewPreds);
15739 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15745 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15748 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15752 for (
auto *BB : L.getBlocks())
15753 for (
auto &
I : *BB) {
15754 if (!SE.isSCEVable(
I.getType()))
15757 auto *Expr = SE.getSCEV(&
I);
15758 auto II = RewriteMap.find(Expr);
15760 if (
II == RewriteMap.end())
15764 if (
II->second.second == Expr)
15769 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15777 LoopGuards Guards(SE);
15785void ScalarEvolution::LoopGuards::collectFromPHI(
15793 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15794 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15808 auto &RewriteMap =
G->second.RewriteMap;
15809 if (RewriteMap.empty())
15811 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15812 if (S == RewriteMap.end())
15818 return {C0, SM->getSCEVType()};
15821 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15822 MinMaxPattern
P2) -> MinMaxPattern {
15823 auto [C1,
T1] =
P1;
15824 auto [C2, T2] =
P2;
15825 if (!C1 || !C2 ||
T1 != T2)
15829 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15831 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15833 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15835 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15840 auto P = GetMinMaxConst(0);
15841 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15844 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15847 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15850 Guards.RewriteMap.insert({
LHS,
RHS});
15858 const APInt &DivisorVal,
15860 const APInt *ExprVal;
15873 const APInt &DivisorVal,
15875 const APInt *ExprVal;
15883 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15897 const SCEV *URemRHS =
nullptr;
15901 const SCEV *Multiple =
15903 DivInfo[URemLHS] = Multiple;
15905 Multiples[URemLHS] =
C->getAPInt();
15925 auto IsMinMaxSCEVWithNonNegativeConstant =
15929 if (
MinMax->getNumOperands() != 2)
15932 if (
C->getAPInt().isNegative())
15934 SCTy =
MinMax->getSCEVType();
15943 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15945 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15950 auto *DivisibleExpr =
15958void ScalarEvolution::LoopGuards::collectFromBlock(
15960 const BasicBlock *
Block,
const BasicBlock *Pred,
15968 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15979 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15981 if (From == FromRewritten)
15983 RewriteMap[From] = To;
15989 auto GetMaybeRewritten = [&](
const SCEV *S) {
15990 return RewriteMap.lookup_or(S, S);
15997 const SCEV *MatchLHS,
15998 const SCEV *MatchRHS) {
15999 const SCEVConstant *C1;
16002 if (!
match(MatchLHS,
16014 const SCEV *RewrittenLHS = GetMaybeRewritten(LHSUnknown);
16015 ExactRegion = ExactRegion.intersectWith(SE.
getUnsignedRange(RewrittenLHS),
16020 if (ExactRegion.isEmptySet() || ExactRegion.isWrappedSet() ||
16021 ExactRegion.isFullSet())
16024 const SCEV *RegionMin = SE.
getConstant(ExactRegion.getUnsignedMin());
16025 const SCEV *RegionMax = SE.
getConstant(ExactRegion.getUnsignedMax());
16026 const SCEV *ClampedLHS =
16028 AddRewrite(LHSUnknown, RewrittenLHS, ClampedLHS);
16031 if (MatchRangeCheckIdiom(Predicate,
LHS,
RHS))
16044 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
16046 const APInt &DividesBy =
16061 switch (Predicate) {
16090 SmallPtrSet<const SCEV *, 16> Visited;
16092 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
16096 while (!Worklist.
empty()) {
16100 if (!Visited.
insert(From).second)
16102 const SCEV *FromRewritten = GetMaybeRewritten(From);
16103 const SCEV *To =
nullptr;
16105 switch (Predicate) {
16110 EnqueueOperands(
UMax);
16116 EnqueueOperands(
SMax);
16122 EnqueueOperands(
UMin);
16128 EnqueueOperands(
SMin);
16136 const SCEV *OneAlignedUp =
16138 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16150 const SCEVConstant *
C;
16159 Guards.NotEqual.insert({
LHS,
RHS});
16168 AddRewrite(From, FromRewritten, To);
16185 SE.F.
getParent(), Intrinsic::experimental_guard);
16187 for (
const auto *GU : GuardDecl->users())
16189 if (Guard->getFunction() ==
Block->getParent() &&
16198 unsigned NumCollectedConditions = 0;
16200 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16202 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16204 const CondBrInst *LoopEntryPredicate =
16206 if (!LoopEntryPredicate)
16211 NumCollectedConditions++;
16215 if (
Depth > 0 && NumCollectedConditions == 2)
16223 if (Pair.second->hasNPredecessorsOrMore(2) &&
16225 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16226 for (
auto &Phi : Pair.second->phis())
16237 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16238 SmallVector<Value *, 8> Worklist;
16239 SmallPtrSet<Value *, 8> Visited;
16241 while (!Worklist.
empty()) {
16248 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16272 DenseMap<const SCEV *, APInt> Multiples;
16274 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16281 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16282 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16286 for (
const auto &[K, Divisor] : Multiples) {
16287 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16288 Guards.RewriteMap[
K] =
16290 Guards.
rewrite(K), Divisor, SE),
16299 Guards.PreserveNUW =
true;
16300 Guards.PreserveNSW =
true;
16301 for (
const SCEV *Expr : ExprsToRewrite) {
16302 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16303 Guards.PreserveNUW &=
16305 Guards.PreserveNSW &=
16312 if (ExprsToRewrite.size() > 1) {
16313 for (
const SCEV *Expr : ExprsToRewrite) {
16314 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16315 Guards.RewriteMap.erase(Expr);
16316 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16325 class SCEVLoopGuardRewriter
16336 NotEqual(Guards.NotEqual) {
16337 if (Guards.PreserveNUW)
16339 if (Guards.PreserveNSW)
16346 return Map.lookup_or(Expr, Expr);
16350 if (
const SCEV *S = Map.lookup(Expr))
16357 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16358 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16359 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16361 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16362 if (
const SCEV *S = Map.lookup(NarrowExt))
16363 return SE.getZeroExtendExpr(S, Ty);
16364 Bitwidth = Bitwidth / 2;
16372 if (
const SCEV *S = Map.lookup(Expr))
16379 if (
const SCEV *S = Map.lookup(Expr))
16385 if (
const SCEV *S = Map.lookup(Expr))
16391 if (
const SCEV *S = Map.lookup(Expr))
16396 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16401 if (NotEqual.contains({LHS, RHS})) {
16403 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16404 return SE.getUMaxExpr(OneAlignedUp, S);
16411 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16422 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16423 return SE.getAddExpr(
16426 if (
const SCEV *S = Map.lookup(
Add))
16427 return SE.getAddExpr(Expr->
getOperand(0), S);
16435 const SCEV *S =
nullptr;
16442 S = Map.lookup(SE.getAddExpr(NewC, Expr->
getOperand(1)));
16445 return SE.getAddExpr(S, SE.getMinusOne(Expr->
getType()));
16480 if (RewriteMap.empty() && NotEqual.empty())
16483 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16484 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)
MachineInstr unsigned OpIdx
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 cl::opt< unsigned > MaxPhiSCCAnalysisSize("scalar-evolution-max-scc-analysis-depth", cl::Hidden, cl::desc("Maximum amount of nodes to process while searching SCEVUnknown " "Phi strongly connected components"), cl::init(8))
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 * 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 * getZeroExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
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 * getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty)
LLVM_ABI const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &Operands)
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 * getSignExtendExprImpl(const SCEV *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 * getZeroExtendExpr(const SCEV *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 * 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 * getTruncateExpr(const SCEV *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 const SCEV * getAnyExtendExpr(const SCEV *Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
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 const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
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 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.
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.
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
LLVM_ABI APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
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< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagAnyWrap, true > m_scev_c_Mul(const Op0_t &Op0, const Op1_t &Op1)
SCEVBinaryExpr_match< SCEVSMaxExpr, Op0_t, Op1_t > m_scev_SMax(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.
LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt gcd(const DynamicAPInt &A, const DynamicAPInt &B)
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.
iterator_range< pointee_iterator< WrappedIteratorT > > make_pointee_range(RangeT &&Range)
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